Messages in this thread Patch in this message | | | From | Manfred Spraul <> | Subject | Re: [PATCH] ipc: replace costly bailout check in sysvipc_find_ipc() | Date | Fri, 20 Aug 2021 21:41:32 +0200 |
| |
Hi Rafael,
On 8/9/21 10:35 PM, Rafael Aquini wrote: > 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
Could you run your test with the attached patch?
The patch switches the code to idr_get_next(), and I see a speedup of factor 400 for this test:
- boot with ipcmni_extend
- create ipc object
- echo 16000000 > /proc/sys/kernel/msg_next_id
- create ipc object
- time cat /proc/sysvipc/msg
with current mainline: 8.65 seconds
with the patch: 0.02 seconds
If there are no gaps, then I would assume there is no speed-up compared to your patch, but it would be create if you could check
[and check that there is no slow-down]
Thanks,
--
Manfred
From 4b7975d712db27c3d08731e0ebe4efd684256ca4 Mon Sep 17 00:00:00 2001 From: Manfred Spraul <manfred@colorfullife.com> Date: Fri, 20 Aug 2021 21:08:12 +0200 Subject: [PATCH] [PATCH] Improve sysvipc_find_ipc()
Initially noticed by Rafael Aquini, see https://lore.kernel.org/lkml/20210809203554.1562989-1-aquini@redhat.com/
The algorithm used in sysvipc_find_ipc() is highly inefficient. It actually needs to find the next used index in an idr, and it uses a for loop to locate that entry.
But: The IDR API contains idr_get_next(), thus switch the code to use idr_get_next().
In addition: Update a few comments.
Signed-off-by: Manfred Spraul <manfred@colorfullife.com> --- ipc/util.c | 43 ++++++++++++++++++++----------------------- 1 file changed, 20 insertions(+), 23 deletions(-)
diff --git a/ipc/util.c b/ipc/util.c index 0027e47626b7..083fd6dba1a1 100644 --- a/ipc/util.c +++ b/ipc/util.c @@ -783,35 +783,32 @@ struct pid_namespace *ipc_seq_pid_ns(struct seq_file *s) } /* - * This routine locks the ipc structure found at least at position pos. + * This routine locks the ipc structure found at least at index pos. */ static struct kern_ipc_perm *sysvipc_find_ipc(struct ipc_ids *ids, loff_t pos, loff_t *new_pos) { + int tmpidx; 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++; - } - ipc = NULL; - if (total >= ids->in_use) - goto out; + tmpidx = pos; - for (; pos < ipc_mni; pos++) { - ipc = idr_find(&ids->ipcs_idr, pos); - if (ipc != NULL) { - rcu_read_lock(); - ipc_lock_object(ipc); - break; - } + ipc = idr_get_next(&ids->ipcs_idr, &tmpidx); + if (ipc != NULL) { + rcu_read_lock(); + ipc_lock_object(ipc); + /* + * We found the object with the index tmpidx. + * For next search, start with tmpidx+1 + */ + *new_pos = tmpidx + 1; + } else { + /* + * EOF. seq_file can't notice that, thus + * move the offset by one. + */ + *new_pos = pos + 1; } -out: - *new_pos = pos + 1; return ipc; } @@ -829,7 +826,7 @@ static void *sysvipc_proc_next(struct seq_file *s, void *it, loff_t *pos) } /* - * File positions: pos 0 -> header, pos n -> ipc id = n - 1. + * File positions: pos 0 -> header, pos n -> ipc idx = n - 1. * SeqFile iterator: iterator value locked ipc pointer or SEQ_TOKEN_START. */ static void *sysvipc_proc_start(struct seq_file *s, loff_t *pos) @@ -854,7 +851,7 @@ static void *sysvipc_proc_start(struct seq_file *s, loff_t *pos) if (*pos == 0) return SEQ_START_TOKEN; - /* Find the (pos-1)th ipc */ + /* Find the ipc object with the index >= (pos-1) */ return sysvipc_find_ipc(ids, *pos - 1, pos); } -- 2.31.1
| |