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

[Rafael Aquini]

On Fri, Aug 20, 2021 at 09:41:32PM +0200, Manfred Spraul wrote:
> 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?
>

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

> 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@xxxxxxxxxxxxxxxx>
> 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@xxxxxxxxxx/
> 
> 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@xxxxxxxxxxxxxxxx>
> ---
>  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
> 
>