On Fri, Aug 30, 2024 at 11:38:29AM +0200, hsimeliere.opensource@xxxxxxxxxxx wrote:
> From: Rafael Aquini <aquini@xxxxxxxxxx>
>
> commit 20401d1058f3f841f35a594ac2fc1293710e55b9 upstream.
>
> 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@xxxxxxxxxx
> Signed-off-by: Rafael Aquini <aquini@xxxxxxxxxx>
> Acked-by: Davidlohr Bueso <dbueso@xxxxxxx>
> Acked-by: Manfred Spraul <manfred@xxxxxxxxxxxxxxxx>
> Cc: Waiman Long <llong@xxxxxxxxxx>
> Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
> Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
> Signed-off-by: Hugo SIMELIERE <hsimeliere.opensource@xxxxxxxxxxx>
> ---
> ipc/util.c | 16 ++++------------
> 1 file changed, 4 insertions(+), 12 deletions(-)
Now queued up, thanks.
greg k-h
