[PATCH 0/2] ipc/util.c: Cleanup and improve sysvipc_find_ipc(), V2

[PATCH 0/2] ipc/util.c: Cleanup and improve sysvipc_find_ipc(), V2

[Manfred Spraul]

Update of the sysvipc_find_ipc() changes:

patch 01: 
	Unmodified patch from Rafael Aquini, already in mmotm.
	https://www.ozlabs.org/~akpm/mmotm/broken-out/ipc-replace-costly-bailout-check-in-sysvipc_find_ipc.patch
	
	Acked-by: Manfred Spraul <manfred@colorfullife.com>
	https://lore.kernel.org/lkml/42b60dd8-8393-5e0f-e576-da5303f29fe7@colorfullife.com/T/#m230673c8ef7261745e80ba458b9712bf1fad2251

patch 02:
	Performance improvement and further cleanup.

Especially, patch 02 tries to make sysvipc_find_ipc() more readable.

E.g.: There was a "+1" at the end of the function.
My first idea: "+1", as in "move to next".
No, the "+1" was "convert from index to pos".

@Andrew: Patch 01 is already in mmotm. Could you add
patch 02 to your tree and forward it as needed?

Thanks,
	Manfred

ipc: replace costly bailout check in sysvipc_find_ipc()

[Manfred Spraul]

From: Rafael Aquini <aquini@redhat.com>

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>
Cc: Manfred Spraul <manfred@colorfullife.com>
Cc: Waiman Long <llong@redhat.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 ipc/util.c |   16 ++++------------
 1 file changed, 4 insertions(+), 12 deletions(-)

--- a/ipc/util.c~ipc-replace-costly-bailout-check-in-sysvipc_find_ipc
+++ a/ipc/util.c
@@ -788,21 +788,13 @@ struct pid_namespace *ipc_seq_pid_ns(str
 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;
+	struct kern_ipc_perm *ipc = NULL;
+	int max_idx = ipc_get_maxidx(ids);
 
-	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)
+	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();
_

[PATCH 2/2] ipc/util.c: Cleanup and improve sysvipc_find_ipc(), V2

[Manfred Spraul]

sysvipc_find_ipc() can be simplified further:

- It uses a for() loop to locate the next entry in the idr.
  This can be replaced with idr_get_next().

- It receives two parameters (pos - which is actually
  and idr index and not a position, and new_pos, which
  is really a position).
  One parameter is sufficient.

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 ipc/util.c | 53 ++++++++++++++++++++++++++++++++---------------------
 1 file changed, 32 insertions(+), 21 deletions(-)

diff --git a/ipc/util.c b/ipc/util.c
index d48d8cfa1f3f..bc5000b2457a 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -782,28 +782,37 @@ struct pid_namespace *ipc_seq_pid_ns(struct seq_file *s)
 	return iter->pid_ns;
 }
 
-/*
- * This routine locks the ipc structure found at least at position pos.
+/**
+ * sysvipc_find_ipc - Find and lock the ipc structure based on seq pos
+ * @ids: ipc identifier set
+ * @pos: expected position
+ *
+ * The function finds an ipc structure, based on the sequence file
+ * position @pos. If there is no ipc structure at position @pos, then
+ * the successor is selected.
+ * If a structure is found, then it is locked (both rcu_read_lock() and
+ * ipc_lock_object()) and  @pos is set to the position needed to locate
+ * the found ipc structure.
+ * If nothing is found (i.e. EOF), @pos is not modified.
+ *
+ * The function returns the found ipc structure, or NULL at EOF.
  */
-static struct kern_ipc_perm *sysvipc_find_ipc(struct ipc_ids *ids, loff_t pos,
-					      loff_t *new_pos)
+static struct kern_ipc_perm *sysvipc_find_ipc(struct ipc_ids *ids, loff_t *pos)
 {
-	struct kern_ipc_perm *ipc = NULL;
-	int max_idx = ipc_get_maxidx(ids);
+	int tmpidx;
+	struct kern_ipc_perm *ipc;
 
-	if (max_idx == -1 || pos > max_idx)
-		goto out;
+	/* convert from position to idr index -> "-1" */
+	tmpidx = *pos - 1;
 
-	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);
+
+		/* convert from idr index to position  -> "+1" */
+		*pos = tmpidx + 1;
 	}
-out:
-	*new_pos = pos + 1;
 	return ipc;
 }
 
@@ -817,11 +826,13 @@ static void *sysvipc_proc_next(struct seq_file *s, void *it, loff_t *pos)
 	if (ipc && ipc != SEQ_START_TOKEN)
 		ipc_unlock(ipc);
 
-	return sysvipc_find_ipc(&iter->ns->ids[iface->ids], *pos, pos);
+	/* Next -> search for *pos+1 */
+	(*pos)++;
+	return sysvipc_find_ipc(&iter->ns->ids[iface->ids], 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)
@@ -846,8 +857,8 @@ 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 */
-	return sysvipc_find_ipc(ids, *pos - 1, pos);
+	/* Otherwise return the correct ipc structure */
+	return sysvipc_find_ipc(ids, pos);
 }
 
 static void sysvipc_proc_stop(struct seq_file *s, void *it)
-- 
2.31.1

Re: [PATCH 2/2] ipc/util.c: Cleanup and improve sysvipc_find_ipc(), V2

[Waiman Long]

On 9/3/21 1:20 AM, Manfred Spraul wrote:
> sysvipc_find_ipc() can be simplified further:
>
> - It uses a for() loop to locate the next entry in the idr.
>    This can be replaced with idr_get_next().
>
> - It receives two parameters (pos - which is actually
>    and idr index and not a position, and new_pos, which
Typo: "and" => "an"
>    is really a position).
>    One parameter is sufficient.
>
> Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
> ---
>   ipc/util.c | 53 ++++++++++++++++++++++++++++++++---------------------
>   1 file changed, 32 insertions(+), 21 deletions(-)
>
> diff --git a/ipc/util.c b/ipc/util.c
> index d48d8cfa1f3f..bc5000b2457a 100644
> --- a/ipc/util.c
> +++ b/ipc/util.c
> @@ -782,28 +782,37 @@ struct pid_namespace *ipc_seq_pid_ns(struct seq_file *s)
>   	return iter->pid_ns;
>   }
>   
> -/*
> - * This routine locks the ipc structure found at least at position pos.
> +/**
> + * sysvipc_find_ipc - Find and lock the ipc structure based on seq pos
> + * @ids: ipc identifier set
> + * @pos: expected position
> + *
> + * The function finds an ipc structure, based on the sequence file
> + * position @pos. If there is no ipc structure at position @pos, then
> + * the successor is selected.
> + * If a structure is found, then it is locked (both rcu_read_lock() and
> + * ipc_lock_object()) and  @pos is set to the position needed to locate
> + * the found ipc structure.
> + * If nothing is found (i.e. EOF), @pos is not modified.
> + *
> + * The function returns the found ipc structure, or NULL at EOF.
>    */
> -static struct kern_ipc_perm *sysvipc_find_ipc(struct ipc_ids *ids, loff_t pos,
> -					      loff_t *new_pos)
> +static struct kern_ipc_perm *sysvipc_find_ipc(struct ipc_ids *ids, loff_t *pos)
>   {
> -	struct kern_ipc_perm *ipc = NULL;
> -	int max_idx = ipc_get_maxidx(ids);
> +	int tmpidx;
> +	struct kern_ipc_perm *ipc;
>   
> -	if (max_idx == -1 || pos > max_idx)
> -		goto out;
> +	/* convert from position to idr index -> "-1" */
> +	tmpidx = *pos - 1;
>   
> -	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);
> +
> +		/* convert from idr index to position  -> "+1" */
> +		*pos = tmpidx + 1;
>   	}
> -out:
> -	*new_pos = pos + 1;
>   	return ipc;
>   }
>   
> @@ -817,11 +826,13 @@ static void *sysvipc_proc_next(struct seq_file *s, void *it, loff_t *pos)
>   	if (ipc && ipc != SEQ_START_TOKEN)
>   		ipc_unlock(ipc);
>   
> -	return sysvipc_find_ipc(&iter->ns->ids[iface->ids], *pos, pos);
> +	/* Next -> search for *pos+1 */
> +	(*pos)++;
> +	return sysvipc_find_ipc(&iter->ns->ids[iface->ids], 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)
> @@ -846,8 +857,8 @@ 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 */
> -	return sysvipc_find_ipc(ids, *pos - 1, pos);
> +	/* Otherwise return the correct ipc structure */
> +	return sysvipc_find_ipc(ids, pos);
>   }
>   
>   static void sysvipc_proc_stop(struct seq_file *s, void *it)

Other than the typo, the patch looks good to me.

Acked-by: Waiman Long <longman@redhat.com>