Re: [PATCH 5.10 1/1] ipc: replace costly bailout check in sysvipc_find_ipc()

[Greg KH <greg@kroah.com>]

On Fri, Aug 30, 2024 at 11:38:29AM +0200, hsimeliere.opensource@witekio.com wrote:
> From: Rafael Aquini <aquini@redhat.com>
> 
> 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@redhat.com
> Signed-off-by: Rafael Aquini <aquini@redhat.com>
> Acked-by: Davidlohr Bueso <dbueso@suse.de>
> Acked-by: Manfred Spraul <manfred@colorfullife.com>
> Cc: Waiman Long <llong@redhat.com>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> Signed-off-by: Hugo SIMELIERE <hsimeliere.opensource@witekio.com>
> ---
>  ipc/util.c | 16 ++++------------
>  1 file changed, 4 insertions(+), 12 deletions(-)

Now queued up, thanks.

greg k-h