From: akpm@linux-foundation.org
To: mm-commits@vger.kernel.org, manfred@colorfullife.com,
llong@redhat.com, dbueso@suse.de, aquini@redhat.com
Subject: + ipc-replace-costly-bailout-check-in-sysvipc_find_ipc.patch added to -mm tree
Date: Tue, 10 Aug 2021 21:32:41 -0700 [thread overview]
Message-ID: <20210811043241.SD44R%akpm@linux-foundation.org> (raw)
The patch titled
Subject: ipc: replace costly bailout check in sysvipc_find_ipc()
has been added to the -mm tree. Its filename is
ipc-replace-costly-bailout-check-in-sysvipc_find_ipc.patch
This patch should soon appear at
https://ozlabs.org/~akpm/mmots/broken-out/ipc-replace-costly-bailout-check-in-sysvipc_find_ipc.patch
and later at
https://ozlabs.org/~akpm/mmotm/broken-out/ipc-replace-costly-bailout-check-in-sysvipc_find_ipc.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Rafael Aquini <aquini@redhat.com>
Subject: ipc: replace costly bailout check in sysvipc_find_ipc()
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>
Cc: Manfred Spraul <manfred@colorfullife.com>
Cc: Waiman Long <llong@redhat.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
ipc/util.c | 16 ++++------------
1 file changed, 4 insertions(+), 12 deletions(-)
--- a/ipc/util.c~ipc-replace-costly-bailout-check-in-sysvipc_find_ipc
+++ a/ipc/util.c
@@ -788,21 +788,13 @@ struct pid_namespace *ipc_seq_pid_ns(str
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;
+ struct kern_ipc_perm *ipc = NULL;
+ int max_idx = ipc_get_maxidx(ids);
- total = 0;
- for (id = 0; id < pos && total < ids->in_use; id++) {
- ipc = idr_find(&ids->ipcs_idr, id);
- if (ipc != NULL)
- total++;
- }
-
- 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();
_
Patches currently in -mm which might be from aquini@redhat.com are
ipc-replace-costly-bailout-check-in-sysvipc_find_ipc.patch
reply other threads:[~2021-08-11 4:32 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210811043241.SD44R%akpm@linux-foundation.org \
--to=akpm@linux-foundation.org \
--cc=aquini@redhat.com \
--cc=dbueso@suse.de \
--cc=linux-kernel@vger.kernel.org \
--cc=llong@redhat.com \
--cc=manfred@colorfullife.com \
--cc=mm-commits@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).