ipc: replace costly bailout check in sysvipc_find_ipc()
PATCH 1/1 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
--- ipc/util.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-)
ipc/util.c +4 -12
@@ -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 ();
Signature · 1 line
2.26.3
Quoted 57 lines · Rafael Aquini
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/shm1303 msecs to read 16384 segs from
/proc/sysvipc/shm5182 msecs to read 32768 segs from/proc/sysvipc/shmThe 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: makeget_maxidO(1) again") and gets rid of the aforementioned costly loop replacing it by a simpler checkpoint based onipc_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/shm19 msecs to read 16384 segs from
/proc/sysvipc/shm39 msecs to read 32768 segs from/proc/sysvipc/shmSigned-off-by Rafael Aquini <[email protected]>--- ipc/util.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-)ipc/util.c +2
-9@@ -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/util.c struct pid_namespace *ipc_seq_pid_ns(struct seq_file *s) · line 800
Quoted 10 lines
ipc/util.c +2
-3- 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 ();
The "pos > max_idx" check is redundant and so is not really necessary. Other than that, the patch looks good to me.
Quoted 25 lines · Rafael Aquini
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/shm1303 msecs to read 16384 segs from
/proc/sysvipc/shm5182 msecs to read 32768 segs from/proc/sysvipc/shmThe 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: makeget_maxidO(1) again") and gets rid of the aforementioned costly loop replacing it by a simpler checkpoint based onipc_get_maxidx()returned value, which allows for a smooth linear increase in time complexity for the same custom benchmark:
Quoted 8 lines
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/shm19 msecs to read 16384 segs from
/proc/sysvipc/shm39 msecs to read 32768 segs from/proc/sysvipc/shmSigned-off-by Rafael Aquini <[email protected]>
Hello Rafael,
I still try to understand the code. It seems, it is more or less unchanged from 2009:
|
Quoted 18 lines · Rafael Aquini
ipc/util.c +2
-9@@ -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/util.c struct pid_namespace *ipc_seq_pid_ns(struct seq_file *s) · line 800
Quoted 10 lines
ipc/util.c +2
-3- 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 ();
The change looks as correct to me. But I'm still not sure that I really understand what the current code does:
- first, loop over index values in the idr, starting from 0, count found entries.
- if we found all entries before we are at index=pos: fail
- then search up to ipc_nmi for the next entry with an index >=pos.
- if something is found: use it. otherwise fail.
It seems the code tries to avoid that we loop until ipc_mni after the last entry was found, and therefore we loop every time from 0.
From what I see, the change looks to be correct: You now remove the first loop, and instead of searching until ipc_mni, the search ends at <= max_idx.
I'll try to find some time to test it.
But: What about using idr_get_next() instead of the idr_find()?
We want to find the next used index, thus idr_get_next() should be even better than the for loop, ...
--
Manfred
Hi Rafael,
Quoted 25 lines · Rafael Aquini
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/shm1303 msecs to read 16384 segs from
/proc/sysvipc/shm5182 msecs to read 32768 segs from/proc/sysvipc/shmThe 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: makeget_maxidO(1) again") and gets rid of the aforementioned costly loop replacing it by a simpler checkpoint based onipc_get_maxidx()returned value, which allows for a smooth linear increase in time complexity for the same custom benchmark:
Quoted 6 lines
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/shm19 msecs to read 16384 segs from
/proc/sysvipc/shm39 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 <[email protected]>
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/[email protected]/
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.
--- ipc/util.c | 43 ++++++++++++++++++++----------------------- 1 file changed, 20 insertions(+), 23 deletions(-)
ipc/util.c +20 -23
@@ -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); }
Signature · 1 line
2.31.1
Quoted 28 lines · Manfred Spraul
Hi Rafael,
Quoted 25 lines · Rafael Aquini
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/shm1303 msecs to read 16384 segs from
/proc/sysvipc/shm5182 msecs to read 32768 segs from/proc/sysvipc/shmThe 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: makeget_maxidO(1) again") and gets rid of the aforementioned costly loop replacing it by a simpler checkpoint based onipc_get_maxidx()returned value, which allows for a smooth linear increase in time complexity for the same custom benchmark:
Quoted 9 lines
Quoted 6 lines
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/shm19 msecs to read 16384 segs from
/proc/sysvipc/shm39 msecs to read 32768 segs from/proc/sysvipc/shmCould you run your test with the attached patch?
Manfred,
Sorry it took me a while to get back to you here. (coming back from a short leave). I'll take a look into your approach and report back in a few days.
Cheers,
-- Rafael
Quoted 133 lines
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/msgwith 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
4b7975d712db27c3d08731e0ebe4efd684256ca4Mon Sep 17 00:00:00 2001
From: Manfred Spraul <[email protected]>
Date: Fri, 20 Aug 2021 21:08:12 +0200
Subject: [PATCH] [PATCH] Improvesysvipc_find_ipc()Initially noticed by Rafael Aquini, see
https://lore.kernel.org/lkml/[email protected]/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 useidr_get_next().In addition: Update a few comments.
Signed-off-by Manfred Spraul <[email protected]>--- ipc/util.c | 43 ++++++++++++++++++++----------------------- 1 file changed, 20 insertions(+), 23 deletions(-)ipc/util.c +20
-23@@ -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); }Signature · 1 line
2.31.1
Quoted 36 lines · Rafael Aquini
Quoted 35 lines · Manfred Spraul
Hi Rafael,
Quoted 31 lines · Rafael Aquini
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/shm1303 msecs to read 16384 segs from
/proc/sysvipc/shm5182 msecs to read 32768 segs from/proc/sysvipc/shmThe 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: makeget_maxidO(1) again") and gets rid of the aforementioned costly loop replacing it by a simpler checkpoint based onipc_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/shm19 msecs to read 16384 segs from
/proc/sysvipc/shm39 msecs to read 32768 segs from/proc/sysvipc/shm
Quoted 8 lines
Quoted 2 lines
Could you run your test with the attached patch?
Manfred,
Sorry it took me a while to get back to you here. (coming back from a short leave). I'll take a look into your approach and report back in a few days.
Manfred,
as promised I re-ran the tests, adjusting the shm workload to leave a gap in the ids between the runs (effectivelly deleting all previously created segments before recreating the batch for the next turn), and the outcome between the two patches is virtually the same:
* your patch:
1 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 24 msecs to read 16384 segs from /proc/sysvipc/shm 44 msecs to read 32768 segs from /proc/sysvipc/shm
* my patch:
1 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 22 msecs to read 16384 segs from /proc/sysvipc/shm 45 msecs to read 32768 segs from /proc/sysvipc/shm
and even perf stat numbers are virtually the same for reading 32768 segments from /proc/sysvipc/shm:
* your patch
Performance counter stats for 'cat /proc/sysvipc/shm' (10 runs):
45.03 msec task-clock # 0.990 CPUs utilized ( +- 0.27% )
0 context-switches # 0.004 K/sec ( +-100.00% )
0 cpu-migrations # 0.004 K/sec ( +-100.00% )
70 page-faults # 0.002 M/sec ( +- 0.61% )
149,631,684 cycles # 3.323 GHz ( +- 0.25% ) (82.23%)
2,148,928 stalled-cycles-frontend # 1.44% frontend cycles idle ( +- 2.21% ) (82.24%)
67,488,510 stalled-cycles-backend # 45.10% backend cycles idle ( +- 0.73% ) (83.32%)
249,186,578 instructions # 1.67 insn per cycle
# 0.27 stalled cycles per insn ( +- 0.03% ) (84.31%)
62,268,386 branches # 1382.790 M/sec ( +- 0.02% ) (84.45%)
83,170 branch-misses # 0.13% of all branches ( +- 1.57% ) (83.44%)0.045485 +- 0.000142 seconds time elapsed ( +- 0.31% )
* my patch:
Performance counter stats for 'cat /proc/sysvipc/shm' (10 runs):
45.22 msec task-clock # 0.990 CPUs utilized ( +- 0.24% )
0 context-switches # 0.002 K/sec ( +-100.00% )
0 cpu-migrations # 0.000 K/sec
70 page-faults # 0.002 M/sec ( +- 0.92% )
150,273,699 cycles # 3.323 GHz ( +- 0.25% ) (82.31%)
12,288,154 stalled-cycles-frontend # 8.18% frontend cycles idle ( +- 0.95% ) (82.31%)
61,198,482 stalled-cycles-backend # 40.72% backend cycles idle ( +- 0.91% ) (83.14%)
245,485,497 instructions # 1.63 insn per cycle
# 0.25 stalled cycles per insn ( +- 0.03% ) (84.41%)
61,736,363 branches # 1365.267 M/sec ( +- 0.02% ) (84.52%)
82,381 branch-misses # 0.13% of all branches ( +- 1.17% ) (83.31%)0.045671 +- 0.000125 seconds time elapsed ( +- 0.27% )
I'll leave it up to you, as clearly both approaches do pretty good in reducing the noted overhead imposed by the old approach.
Since my patch is already in linux-next, may I ask you to ack it and follow it up there if you decide on going with your approach? The diff below applies cleanly on top of linux-next head (it's the one I used on tests).
Cheers!
Rafael
--
ipc/util.c +18 -14
@@ -788,22 +788,26 @@ 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 =NULL ; -int max_idx =ipc_get_maxidx (ids); +struct kern_ipc_perm *ipc; +int tmpidx = pos; -if (max_idx ==-1 || pos > max_idx) - goto out; - -for (; pos <= max_idx; 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; }
Hi Rafael,
Quoted 25 lines · Rafael Aquini
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/shm1303 msecs to read 16384 segs from
/proc/sysvipc/shm5182 msecs to read 32768 segs from/proc/sysvipc/shmThe 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: makeget_maxidO(1) again") and gets rid of the aforementioned costly loop replacing it by a simpler checkpoint based onipc_get_maxidx()returned value, which allows for a smooth linear increase in time complexity for the same custom benchmark:
Quoted 8 lines
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/shm19 msecs to read 16384 segs from
/proc/sysvipc/shm39 msecs to read 32768 segs from/proc/sysvipc/shmSigned-off-by Rafael Aquini <[email protected]>
I've tested the patch, no issues or objections.
Thus: Let's merge your patch, and then switch to ipc_get_next() later.
--
Manfred