[PATCH 0/1] ipc/util.{c,h}: Use binary search for max_idx

[PATCH 0/1] ipc/util.{c,h}: Use binary search for max_idx

[Manfred Spraul]

2nd version of the patch:
@Andrew: Could you add the patch to your mm tree, as candidate for
linux-next?

Note:
I have tried to remove the ids->max_idx cache entirely. Unfortunately,
this causes a significant slow-down of semstat(,,IPC_STAT):
   * no object allocated, no ipcmni_extended: +50%
   * no object allocated, with ipcmni_extended: +80%
   * 30 objects allocated, with large gaps, no ipcmni_extended:
           +350%
Thus I haven't removed ids->max_id.


--
	Manfred

[PATCH] ipc/util.c: Use binary search for max_idx

[Manfred Spraul]

If semctl(), msgctl() and shmctl() are called with IPC_INFO, SEM_INFO,
MSG_INFO or SHM_INFO, then the return value is the index of the highest
used index in the kernel's internal array recording information about
all SysV objects of the requested type for the current namespace.
(This information can be used with repeated ..._STAT or ..._STAT_ANY
operations to obtain information about all SysV objects on the system.)

There is a cache for this value. But when the cache needs up be updated,
then the highest used index is determined by looping over all possible
values. With the introduction of IPCMNI_EXTEND_SHIFT, this could be a
loop over 16 million entries. And due to /proc/sys/kernel/*next_id,
the index values do not need to be consecutive.

With <write 16000000 to msg_next_id>, msgget(), msgctl(,IPC_RMID) in
a loop, I have observed a performance increase of around factor 13000.

As there is no get_last() function for idr structures:
Implement a "get_last()" using a binary search.

As far as I see, ipc is the only user that needs get_last(), thus
implement it in ipc/util.c and not in a central location.

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 ipc/util.c | 44 +++++++++++++++++++++++++++++++++++++++-----
 ipc/util.h |  3 +++
 2 files changed, 42 insertions(+), 5 deletions(-)

diff --git a/ipc/util.c b/ipc/util.c
index cfa0045e748d..23cf5b5450ff 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -64,6 +64,7 @@
 #include <linux/memory.h>
 #include <linux/ipc_namespace.h>
 #include <linux/rhashtable.h>
+#include <linux/log2.h>
 
 #include <asm/unistd.h>
 
@@ -450,6 +451,41 @@ static void ipc_kht_remove(struct ipc_ids *ids, struct kern_ipc_perm *ipcp)
 				       ipc_kht_params);
 }
 
+/**
+ * ipc_search_maxidx - search the highest assigned index
+ * @ids: ipc identifier set
+ * @limit: known upper limit for highest assigned index
+ *
+ * The function determines the highest assigned index in @ids. It is intended
+ * to be called when ids->max_idx needs to be updated.
+ * Updating ids->max_idx is necessary when the current highest index ipc
+ * object is deleted.
+ * If no ipc object is allocated, then -1 is returned.
+ *
+ * ipc_ids.rwsem needs to be owned by the caller.
+ */
+static int ipc_search_maxidx(struct ipc_ids *ids, int limit)
+{
+	int tmpidx;
+	int i;
+	int retval;
+
+	i = ilog2(limit+1);
+
+	retval = 0;
+	for (; i >= 0; i--) {
+		tmpidx = retval | (1<<i);
+		/*
+		 * "0" is a possible index value, thus search using
+		 * e.g. 15,7,3,1,0 instead of 16,8,4,2,1.
+		 */
+		tmpidx = tmpidx-1;
+		if (idr_get_next(&ids->ipcs_idr, &tmpidx))
+			retval |= (1<<i);
+	}
+	return retval - 1;
+}
+
 /**
  * ipc_rmid - remove an ipc identifier
  * @ids: ipc identifier set
@@ -468,11 +504,9 @@ void ipc_rmid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp)
 	ipcp->deleted = true;
 
 	if (unlikely(idx == ids->max_idx)) {
-		do {
-			idx--;
-			if (idx == -1)
-				break;
-		} while (!idr_find(&ids->ipcs_idr, idx));
+		idx = ids->max_idx-1;
+		if (idx >= 0)
+			idx = ipc_search_maxidx(ids, idx);
 		ids->max_idx = idx;
 	}
 }
diff --git a/ipc/util.h b/ipc/util.h
index 5766c61aed0e..317c8fe15383 100644
--- a/ipc/util.h
+++ b/ipc/util.h
@@ -145,6 +145,9 @@ int ipcperms(struct ipc_namespace *ns, struct kern_ipc_perm *ipcp, short flg);
  * ipc_get_maxidx - get the highest assigned index
  * @ids: ipc identifier set
  *
+ * The function returns the highest assinged index for @ids. The function
+ * doesn't scan the idr tree, it uses a cached value.
+ *
  * Called with ipc_ids.rwsem held for reading.
  */
 static inline int ipc_get_maxidx(struct ipc_ids *ids)
-- 
2.30.2

Re: [PATCH 0/1] ipc/util.{c,h}: Use binary search for max_idx

[Davidlohr Bueso]

On Sun, 25 Apr 2021, Manfred Spraul wrote:

>2nd version of the patch:
>@Andrew: Could you add the patch to your mm tree, as candidate for
>linux-next?
>
>Note:
>I have tried to remove the ids->max_idx cache entirely. Unfortunately,
>this causes a significant slow-down of semstat(,,IPC_STAT):
>   * no object allocated, no ipcmni_extended: +50%
>   * no object allocated, with ipcmni_extended: +80%
>   * 30 objects allocated, with large gaps, no ipcmni_extended:
>           +350%
>Thus I haven't removed ids->max_id.

Right, IPC_STAT is the main usecase for max_id. But I'm not sure why
you were looking to remove it in the first place - or was it just to
avoid this patch altogether?

Thanks,
Davidlohr

Re: [PATCH 0/1] ipc/util.{c,h}: Use binary search for max_idx

[Manfred Spraul]

Hi Davidlohr,

On 4/25/21 8:07 PM, Davidlohr Bueso wrote:
> On Sun, 25 Apr 2021, Manfred Spraul wrote:
>
>> 2nd version of the patch:
>> @Andrew: Could you add the patch to your mm tree, as candidate for
>> linux-next?
>>
>> Note:
>> I have tried to remove the ids->max_idx cache entirely. Unfortunately,
>> this causes a significant slow-down of semstat(,,IPC_STAT):
>>   * no object allocated, no ipcmni_extended: +50%
>>   * no object allocated, with ipcmni_extended: +80%
>>   * 30 objects allocated, with large gaps, no ipcmni_extended:
>>           +350%
>> Thus I haven't removed ids->max_id.
>
> Right, IPC_STAT is the main usecase for max_id. But I'm not sure why
> you were looking to remove it in the first place - or was it just to
> avoid this patch altogether?
>
I had assumed that after removing the linear search, the lookup would be 
so fast that the cache can be removed entirely.
It would save ~20 lines of code and one int in struct ipc_ids (12 bytes 
per namespace?).

But: My assumption was wrong, the slowdown is too large.

--

     Manfred