lkml.org 
[lkml]   [2021]   [Aug]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
SubjectRe: [PATCH] ipc: replace costly bailout check in sysvipc_find_ipc()
Date
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

\
 
 \ /
  Last update: 2021-08-20 21:43    [W:0.120 / U:0.796 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site