* Linux 5.10.y / ipc: replace costly bailout check in sysvipc_find_ipc()
@ 2023-10-11 23:13 Marek Vasut
2023-10-12 1:13 ` [PATCH 5.10.y] " Rafael Aquini
0 siblings, 1 reply; 3+ messages in thread
From: Marek Vasut @ 2023-10-11 23:13 UTC (permalink / raw)
To: linux-stable
Cc: Rafael Aquini, Davidlohr Bueso, Manfred Spraul, Waiman Long,
Andrew Morton, Linus Torvalds
Please backport to Linux 5.10.y :
20401d1058f3f841f35a594ac2fc1293710e55b9
ipc: replace costly bailout check in sysvipc_find_ipc()
This should address CVE-2021-3669
https://nvd.nist.gov/vuln/detail/CVE-2021-3669
Thank you
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH 5.10.y] ipc: replace costly bailout check in sysvipc_find_ipc()
2023-10-11 23:13 Linux 5.10.y / ipc: replace costly bailout check in sysvipc_find_ipc() Marek Vasut
@ 2023-10-12 1:13 ` Rafael Aquini
2023-10-12 17:36 ` Greg KH
0 siblings, 1 reply; 3+ messages in thread
From: Rafael Aquini @ 2023-10-12 1:13 UTC (permalink / raw)
To: stable
Cc: Marek Vasut, Manfred Spraul, Davidlohr Bueso, Waiman Long,
Andrew Morton, Linus Torvalds
commit 20401d1058f3f841f35a594ac2fc1293710e55b9 upstream
This is CVE-2021-3669
sysvipc_find_ipc() was left with a costly way to check if the offset
position fed to it is bigger than the total number of IPC IDs in use. So
much so that the time it takes to iterate over /proc/sysvipc/* files grows
exponentially for a custom benchmark that creates "N" SYSV shm segments
and then times the read of /proc/sysvipc/shm (milliseconds):
12 msecs to read 1024 segs from /proc/sysvipc/shm
18 msecs to read 2048 segs from /proc/sysvipc/shm
65 msecs to read 4096 segs from /proc/sysvipc/shm
325 msecs to read 8192 segs from /proc/sysvipc/shm
1303 msecs to read 16384 segs from /proc/sysvipc/shm
5182 msecs to read 32768 segs from /proc/sysvipc/shm
The root problem lies with the loop that computes the total amount of ids
in use to check if the "pos" feeded to sysvipc_find_ipc() grew bigger than
"ids->in_use". That is a quite inneficient way to get to the maximum
index in the id lookup table, specially when that value is already
provided by struct ipc_ids.max_idx.
This patch follows up on the optimization introduced via commit
15df03c879836 ("sysvipc: make get_maxid O(1) again") and gets rid of the
aforementioned costly loop replacing it by a simpler checkpoint based on
ipc_get_maxidx() returned value, which allows for a smooth linear increase
in time complexity for the same custom benchmark:
2 msecs to read 1024 segs from /proc/sysvipc/shm
2 msecs to read 2048 segs from /proc/sysvipc/shm
4 msecs to read 4096 segs from /proc/sysvipc/shm
9 msecs to read 8192 segs from /proc/sysvipc/shm
19 msecs to read 16384 segs from /proc/sysvipc/shm
39 msecs to read 32768 segs from /proc/sysvipc/shm
Link: https://lkml.kernel.org/r/20210809203554.1562989-1-aquini@redhat.com
Signed-off-by: Rafael Aquini <aquini@redhat.com>
Acked-by: Davidlohr Bueso <dbueso@suse.de>
Acked-by: Manfred Spraul <manfred@colorfullife.com>
Cc: Waiman Long <llong@redhat.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Rafael Aquini <aquini@redhat.com>
---
ipc/util.c | 16 ++++------------
1 file changed, 4 insertions(+), 12 deletions(-)
diff --git a/ipc/util.c b/ipc/util.c
index bbb5190af6d9..7c3601dad9bd 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -754,21 +754,13 @@ struct pid_namespace *ipc_seq_pid_ns(struct seq_file *s)
static struct kern_ipc_perm *sysvipc_find_ipc(struct ipc_ids *ids, loff_t pos,
loff_t *new_pos)
{
- struct kern_ipc_perm *ipc;
- int total, id;
-
- total = 0;
- for (id = 0; id < pos && total < ids->in_use; id++) {
- ipc = idr_find(&ids->ipcs_idr, id);
- if (ipc != NULL)
- total++;
- }
+ struct kern_ipc_perm *ipc = NULL;
+ int max_idx = ipc_get_maxidx(ids);
- ipc = NULL;
- if (total >= ids->in_use)
+ if (max_idx == -1 || pos > max_idx)
goto out;
- for (; pos < ipc_mni; pos++) {
+ for (; pos <= max_idx; pos++) {
ipc = idr_find(&ids->ipcs_idr, pos);
if (ipc != NULL) {
rcu_read_lock();
--
2.41.0
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH 5.10.y] ipc: replace costly bailout check in sysvipc_find_ipc()
2023-10-12 1:13 ` [PATCH 5.10.y] " Rafael Aquini
@ 2023-10-12 17:36 ` Greg KH
0 siblings, 0 replies; 3+ messages in thread
From: Greg KH @ 2023-10-12 17:36 UTC (permalink / raw)
To: Rafael Aquini
Cc: stable, Marek Vasut, Manfred Spraul, Davidlohr Bueso,
Waiman Long, Andrew Morton, Linus Torvalds
On Wed, Oct 11, 2023 at 09:13:41PM -0400, Rafael Aquini wrote:
> commit 20401d1058f3f841f35a594ac2fc1293710e55b9 upstream
>
> This is CVE-2021-3669
>
> sysvipc_find_ipc() was left with a costly way to check if the offset
> position fed to it is bigger than the total number of IPC IDs in use. So
> much so that the time it takes to iterate over /proc/sysvipc/* files grows
> exponentially for a custom benchmark that creates "N" SYSV shm segments
> and then times the read of /proc/sysvipc/shm (milliseconds):
>
> 12 msecs to read 1024 segs from /proc/sysvipc/shm
> 18 msecs to read 2048 segs from /proc/sysvipc/shm
> 65 msecs to read 4096 segs from /proc/sysvipc/shm
> 325 msecs to read 8192 segs from /proc/sysvipc/shm
> 1303 msecs to read 16384 segs from /proc/sysvipc/shm
> 5182 msecs to read 32768 segs from /proc/sysvipc/shm
>
> The root problem lies with the loop that computes the total amount of ids
> in use to check if the "pos" feeded to sysvipc_find_ipc() grew bigger than
> "ids->in_use". That is a quite inneficient way to get to the maximum
> index in the id lookup table, specially when that value is already
> provided by struct ipc_ids.max_idx.
>
> This patch follows up on the optimization introduced via commit
> 15df03c879836 ("sysvipc: make get_maxid O(1) again") and gets rid of the
> aforementioned costly loop replacing it by a simpler checkpoint based on
> ipc_get_maxidx() returned value, which allows for a smooth linear increase
> in time complexity for the same custom benchmark:
>
> 2 msecs to read 1024 segs from /proc/sysvipc/shm
> 2 msecs to read 2048 segs from /proc/sysvipc/shm
> 4 msecs to read 4096 segs from /proc/sysvipc/shm
> 9 msecs to read 8192 segs from /proc/sysvipc/shm
> 19 msecs to read 16384 segs from /proc/sysvipc/shm
> 39 msecs to read 32768 segs from /proc/sysvipc/shm
>
> Link: https://lkml.kernel.org/r/20210809203554.1562989-1-aquini@redhat.com
> Signed-off-by: Rafael Aquini <aquini@redhat.com>
> Acked-by: Davidlohr Bueso <dbueso@suse.de>
> Acked-by: Manfred Spraul <manfred@colorfullife.com>
> Cc: Waiman Long <llong@redhat.com>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> Signed-off-by: Rafael Aquini <aquini@redhat.com>
Marek, you did not sign off on this patch, why not?
And how did you test this? Are you sure it's really needed? Is that
cve actually valid and something that you have had problems with in the
real world?
thanks,
greg k-h
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-10-12 17:38 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-10-11 23:13 Linux 5.10.y / ipc: replace costly bailout check in sysvipc_find_ipc() Marek Vasut
2023-10-12 1:13 ` [PATCH 5.10.y] " Rafael Aquini
2023-10-12 17:36 ` Greg KH
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.