* Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4
@ 2022-09-02 13:59 Varsha Teratipally
2022-09-02 13:59 ` [PATCH] ipc: replace costly bailout check in sysvipc_find_ipc() Varsha Teratipally
2022-09-02 14:27 ` Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4 Greg Kroah-Hartman
0 siblings, 2 replies; 6+ messages in thread
From: Varsha Teratipally @ 2022-09-02 13:59 UTC (permalink / raw)
To: Andrew Morton, Manfred Spraul, Greg Kroah-Hartman
Cc: Davidlohr Bueso, Rafael Aquini, Alexander Mikhalitsyn,
linux-kernel, stable
Hi all,
Commit 20401d1058f3f841f35a594ac2fc1293710e55b9("ipc: replace costly
bailout check in sysvipc_find_ipc()" fixes a high cve and optimizes the
costly loop by adding a checkpoint, which I think might be a good
candidate for the stable branches
Let me know what you think
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH] ipc: replace costly bailout check in sysvipc_find_ipc()
2022-09-02 13:59 Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4 Varsha Teratipally
@ 2022-09-02 13:59 ` Varsha Teratipally
2022-09-02 14:41 ` kernel test robot
2022-09-02 14:27 ` Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4 Greg Kroah-Hartman
1 sibling, 1 reply; 6+ messages in thread
From: Varsha Teratipally @ 2022-09-02 13:59 UTC (permalink / raw)
To: Andrew Morton, Manfred Spraul, Greg Kroah-Hartman
Cc: Davidlohr Bueso, Rafael Aquini, Alexander Mikhalitsyn,
linux-kernel, stable, Waiman Long, Linus Torvalds
From: Rafael Aquini <aquini@redhat.com>
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>
---
ipc/util.c | 16 ++++------------
1 file changed, 4 insertions(+), 12 deletions(-)
diff --git a/ipc/util.c b/ipc/util.c
index 0027e47626b7..d48d8cfa1f3f 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -788,21 +788,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();
--
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4
2022-09-02 13:59 Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4 Varsha Teratipally
2022-09-02 13:59 ` [PATCH] ipc: replace costly bailout check in sysvipc_find_ipc() Varsha Teratipally
@ 2022-09-02 14:27 ` Greg Kroah-Hartman
2022-09-04 17:38 ` Manfred Spraul
1 sibling, 1 reply; 6+ messages in thread
From: Greg Kroah-Hartman @ 2022-09-02 14:27 UTC (permalink / raw)
To: Varsha Teratipally
Cc: Andrew Morton, Manfred Spraul, Davidlohr Bueso, Rafael Aquini,
Alexander Mikhalitsyn, linux-kernel, stable
On Fri, Sep 02, 2022 at 01:59:11PM +0000, Varsha Teratipally wrote:
> Hi all,
>
> Commit 20401d1058f3f841f35a594ac2fc1293710e55b9("ipc: replace costly
> bailout check in sysvipc_find_ipc()" fixes a high cve and optimizes the
> costly loop by adding a checkpoint, which I think might be a good
> candidate for the stable branches
What do you mean by "high cve"?
And that feels like it's an artificial benchmark fixup, what real
workload benefits from this change?
thanks,
greg k-h
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] ipc: replace costly bailout check in sysvipc_find_ipc()
2022-09-02 13:59 ` [PATCH] ipc: replace costly bailout check in sysvipc_find_ipc() Varsha Teratipally
@ 2022-09-02 14:41 ` kernel test robot
0 siblings, 0 replies; 6+ messages in thread
From: kernel test robot @ 2022-09-02 14:41 UTC (permalink / raw)
To: Varsha Teratipally; +Cc: stable, kbuild-all
Hi,
Thanks for your patch.
FYI: kernel test robot notices the stable kernel rule is not satisfied.
Rule: 'Cc: stable@vger.kernel.org' or 'commit <sha1> upstream.'
Subject: [PATCH] ipc: replace costly bailout check in sysvipc_find_ipc()
Link: https://lore.kernel.org/stable/20220902135912.816188-2-teratipally%40google.com
The check is based on https://www.kernel.org/doc/html/latest/process/stable-kernel-rules.html
--
0-DAY CI Kernel Test Service
https://01.org/lkp
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4
2022-09-02 14:27 ` Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4 Greg Kroah-Hartman
@ 2022-09-04 17:38 ` Manfred Spraul
2022-09-05 5:20 ` Greg Kroah-Hartman
0 siblings, 1 reply; 6+ messages in thread
From: Manfred Spraul @ 2022-09-04 17:38 UTC (permalink / raw)
To: Greg Kroah-Hartman, Varsha Teratipally
Cc: Andrew Morton, Davidlohr Bueso, Rafael Aquini,
Alexander Mikhalitsyn, linux-kernel, stable
Hi,
On 9/2/22 16:27, Greg Kroah-Hartman wrote:
> On Fri, Sep 02, 2022 at 01:59:11PM +0000, Varsha Teratipally wrote:
>> Hi all,
>>
>> Commit 20401d1058f3f841f35a594ac2fc1293710e55b9("ipc: replace costly
>> bailout check in sysvipc_find_ipc()" fixes a high cve and optimizes the
>> costly loop by adding a checkpoint, which I think might be a good
>> candidate for the stable branches
> What do you mean by "high cve"?
>
> And that feels like it's an artificial benchmark fixup, what real
> workload benefits from this change?
Standard ipcs end up parsing /proc/sysvipc/*, thus there are real users
where the performance of /proc/sysvsem/* matters.
But:
The performance of the function was bad since 2007, i.e. why is is now
urgent? I do not see a bug that must be fixed.
Initial patch:
https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/ipc/util.c?id=7ca7e564e049d8b350ec9d958ff25eaa24226352
(core issue: The code needs to find the next entry in an idr. And
instead of using idr_get_next(), it uses idr_find() in a for(;;id++) loop.)
<<<
[manfred@localhost Input]$ rpm -qf /usr/bin/ipcs
util-linux-core-2.38-1.fc36.x86_64
[manfred@localhost Input]$ strace -e openat /usr/bin/ipcs
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
openat(AT_FDCWD, "/lib64/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
openat(AT_FDCWD, "/usr/lib/locale/locale-archive", O_RDONLY|O_CLOEXEC) = 3
openat(AT_FDCWD, "/usr/share/locale/locale.alias", O_RDONLY|O_CLOEXEC) = 3
openat(AT_FDCWD, "/usr/lib/locale/en_US.UTF-8/LC_TIME",
O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/usr/lib/locale/en_US.utf8/LC_TIME",
O_RDONLY|O_CLOEXEC) = 3
openat(AT_FDCWD, "/usr/lib64/gconv/gconv-modules.cache", O_RDONLY) = 3
openat(AT_FDCWD,
"/usr/share/locale/en_US.UTF-8/LC_MESSAGES/util-linux.mo", O_RDONLY) =
-1 ENOENT (No such file or directory)
openat(AT_FDCWD,
"/usr/share/locale/en_US.utf8/LC_MESSAGES/util-linux.mo", O_RDONLY) = -1
ENOENT (No such file or directory)
openat(AT_FDCWD, "/usr/share/locale/en_US/LC_MESSAGES/util-linux.mo",
O_RDONLY) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/usr/share/locale/en.UTF-8/LC_MESSAGES/util-linux.mo",
O_RDONLY) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/usr/share/locale/en.utf8/LC_MESSAGES/util-linux.mo",
O_RDONLY) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/usr/share/locale/en/LC_MESSAGES/util-linux.mo",
O_RDONLY) = -1 ENOENT (No such file or directory)
------ Message Queues --------
key msqid owner perms used-bytes messages
openat(AT_FDCWD, "/proc/sysvipc/msg", O_RDONLY) = 3
------ Shared Memory Segments --------
key shmid owner perms bytes nattch status
openat(AT_FDCWD, "/proc/sysvipc/shm", O_RDONLY) = 3
openat(AT_FDCWD, "/etc/nsswitch.conf", O_RDONLY|O_CLOEXEC) = 3
openat(AT_FDCWD, "/etc/passwd", O_RDONLY|O_CLOEXEC) = 3
0x00000000 18 manfred 600 524288 2 dest
openat(AT_FDCWD, "/etc/passwd", O_RDONLY|O_CLOEXEC) = 3
0x5125004a 19 manfred 600 3208 1
------ Semaphore Arrays --------
key semid owner perms nsems
openat(AT_FDCWD, "/proc/sysvipc/sem", O_RDONLY) = 3
openat(AT_FDCWD, "/etc/passwd", O_RDONLY|O_CLOEXEC) = 3
0x51250047 0 manfred 600 1
openat(AT_FDCWD, "/etc/passwd", O_RDONLY|O_CLOEXEC) = 3
0x51250049 2 manfred 600 1
>>>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4
2022-09-04 17:38 ` Manfred Spraul
@ 2022-09-05 5:20 ` Greg Kroah-Hartman
0 siblings, 0 replies; 6+ messages in thread
From: Greg Kroah-Hartman @ 2022-09-05 5:20 UTC (permalink / raw)
To: Manfred Spraul
Cc: Varsha Teratipally, Andrew Morton, Davidlohr Bueso, Rafael Aquini,
Alexander Mikhalitsyn, linux-kernel, stable
On Sun, Sep 04, 2022 at 07:38:30PM +0200, Manfred Spraul wrote:
> Hi,
>
> On 9/2/22 16:27, Greg Kroah-Hartman wrote:
> > On Fri, Sep 02, 2022 at 01:59:11PM +0000, Varsha Teratipally wrote:
> > > Hi all,
> > >
> > > Commit 20401d1058f3f841f35a594ac2fc1293710e55b9("ipc: replace costly
> > > bailout check in sysvipc_find_ipc()" fixes a high cve and optimizes the
> > > costly loop by adding a checkpoint, which I think might be a good
> > > candidate for the stable branches
> > What do you mean by "high cve"?
> >
> > And that feels like it's an artificial benchmark fixup, what real
> > workload benefits from this change?
>
> Standard ipcs end up parsing /proc/sysvipc/*, thus there are real users
> where the performance of /proc/sysvsem/* matters.
What real users are that? What workload needs that becides monitoring
tools?
>
> But:
>
> The performance of the function was bad since 2007, i.e. why is is now
> urgent? I do not see a bug that must be fixed.
Me either.
thanks,
greg k-h
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2022-09-05 5:20 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2022-09-02 13:59 Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4 Varsha Teratipally
2022-09-02 13:59 ` [PATCH] ipc: replace costly bailout check in sysvipc_find_ipc() Varsha Teratipally
2022-09-02 14:41 ` kernel test robot
2022-09-02 14:27 ` Request to cherry-pick 20401d1058f3f841f35a594ac2fc1293710e55b9 to v5.10 and v5.4 Greg Kroah-Hartman
2022-09-04 17:38 ` Manfred Spraul
2022-09-05 5:20 ` Greg Kroah-Hartman
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox