The patch titled
Subject: ipc: do cyclic id allocation for the ipc object.
has been added to the -mm tree. Its filename is
ipc-do-cyclic-id-allocation-for-the-ipc-object.patch
This patch should soon appear at
http://ozlabs.org/~akpm/mmots/broken-out/ipc-do-cyclic-id-allocation-for-the-ipc-object.patch
and later at
http://ozlabs.org/~akpm/mmotm/broken-out/ipc-do-cyclic-id-allocation-for-the-ipc-object.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Manfred Spraul <manfred@xxxxxxxxxxxxxxxx>
Subject: ipc: do cyclic id allocation for the ipc object.
For ipcmni_extend mode, the sequence number space is only 7 bits. So the
chance of id reuse is relatively high compared with the non-extended mode.
To alleviate this id reuse problem, this patch enables cyclic allocation
for the index to the radix tree (idx). The disadvantage is that this can
cause a slight slow-down of the fast path, as the radix tree could be
higher than necessary.
To limit the radix tree height, I have chosen the following limits:
- 1) The cycling is done over in_use*1.5.
- 2) At least, the cycling is done over
"normal" ipcnmi mode: RADIX_TREE_MAP_SIZE elements
"ipcmni_extended": 4096 elements
Result:
- for normal mode:
No change for <= 42 active ipc elements. With more than 42
active ipc elements, a 2nd level would be added to the radix
tree.
Without cyclic allocation, a 2nd level would be added only with
more than 63 active elements.
- for extended mode:
Cycling creates always at least a 2-level radix tree.
With more than 2730 active objects, a 3rd level would be
added, instead of > 4095 active objects until the 3rd level
is added without cyclic allocation.
For a 2-level radix tree compared to a 1-level radix tree, I have
observed < 1% performance impact.
Notes:
1) Normal "x=semget();y=semget();" is unaffected: Then the idx
is e.g. a and a+1, regardless if idr_alloc() or idr_alloc_cyclic()
is used.
2) The -1% happens in a microbenchmark after this situation:
x=semget();
for(i=0;i<4000;i++) {t=semget();semctl(t,0,IPC_RMID);}
y=semget();
Now perform semget calls on x and y that do not sleep.
3) The worst-case reuse cycle time is unfortunately unaffected:
If you have 2^24-1 ipc objects allocated, and get/remove the last
possible element in a loop, then the id is reused after 128
get/remove pairs.
Performance check:
A microbenchmark that performes no-op semop() randomly on two IDs,
with only these two IDs allocated.
The IDs were set using /proc/sys/kernel/sem_next_id.
The test was run 5 times, averages are shown.
1 & 2: Base (6.22 seconds for 10.000.000 semops)
1 & 40: -0.2%
1 & 3348: - 0.8%
1 & 27348: - 1.6%
1 & 15777204: - 3.2%
Or: ~12.6 cpu cycles per additional radix tree level.
The cpu is an Intel I3-5010U. ~1300 cpu cycles/syscall is slower
than what I remember (spectre impact?).
V2 of the patch:
- use "min" and "max"
- use RADIX_TREE_MAP_SIZE * RADIX_TREE_MAP_SIZE instead of
(2<<12).
Link: http://lkml.kernel.org/r/20190329204930.21620-3-longman@xxxxxxxxxx
Signed-off-by: Manfred Spraul <manfred@xxxxxxxxxxxxxxxx>
Acked-by: Waiman Long <longman@xxxxxxxxxx>
Cc: "Luis R. Rodriguez" <mcgrof@xxxxxxxxxx>
Cc: Kees Cook <keescook@xxxxxxxxxxxx>
Cc: Jonathan Corbet <corbet@xxxxxxx>
Cc: Al Viro <viro@xxxxxxxxxxxxxxxxxx>
Cc: Matthew Wilcox <willy@xxxxxxxxxxxxx>
Cc: "Eric W . Biederman" <ebiederm@xxxxxxxxxxxx>
Cc: Takashi Iwai <tiwai@xxxxxxx>
Cc: Davidlohr Bueso <dbueso@xxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
ipc/ipc_sysctl.c | 2 ++
ipc/util.c | 7 ++++++-
ipc/util.h | 3 +++
3 files changed, 11 insertions(+), 1 deletion(-)
--- a/ipc/ipc_sysctl.c~ipc-do-cyclic-id-allocation-for-the-ipc-object
+++ a/ipc/ipc_sysctl.c
@@ -122,6 +122,7 @@ static int one = 1;
static int int_max = INT_MAX;
int ipc_mni = IPCMNI;
int ipc_mni_shift = IPCMNI_SHIFT;
+int ipc_min_cycle = RADIX_TREE_MAP_SIZE;
static struct ctl_table ipc_kern_table[] = {
{
@@ -252,6 +253,7 @@ static int __init ipc_mni_extend(char *s
{
ipc_mni = IPCMNI_EXTEND;
ipc_mni_shift = IPCMNI_EXTEND_SHIFT;
+ ipc_min_cycle = IPCMNI_EXTEND_MIN_CYCLE;
pr_info("IPCMNI extended to %d.\n", ipc_mni);
return 0;
}
--- a/ipc/util.c~ipc-do-cyclic-id-allocation-for-the-ipc-object
+++ a/ipc/util.c
@@ -221,9 +221,14 @@ static inline int ipc_idr_alloc(struct i
*/
if (next_id < 0) { /* !CHECKPOINT_RESTORE or next_id is unset */
+ int max_idx;
+
+ max_idx = max(ids->in_use*3/2, ipc_min_cycle);
+ max_idx = min(max_idx, ipc_mni);
/* allocate the idx, with a NULL struct kern_ipc_perm */
- idx = idr_alloc(&ids->ipcs_idr, NULL, 0, 0, GFP_NOWAIT);
+ idx = idr_alloc_cyclic(&ids->ipcs_idr, NULL, 0, max_idx,
+ GFP_NOWAIT);
if (idx >= 0) {
/*
--- a/ipc/util.h~ipc-do-cyclic-id-allocation-for-the-ipc-object
+++ a/ipc/util.h
@@ -27,12 +27,14 @@
*/
#define IPCMNI_SHIFT 15
#define IPCMNI_EXTEND_SHIFT 24
+#define IPCMNI_EXTEND_MIN_CYCLE (RADIX_TREE_MAP_SIZE * RADIX_TREE_MAP_SIZE)
#define IPCMNI (1 << IPCMNI_SHIFT)
#define IPCMNI_EXTEND (1 << IPCMNI_EXTEND_SHIFT)
#ifdef CONFIG_SYSVIPC_SYSCTL
extern int ipc_mni;
extern int ipc_mni_shift;
+extern int ipc_min_cycle;
#define ipcmni_seq_shift() ipc_mni_shift
#define IPCMNI_IDX_MASK ((1 << ipc_mni_shift) - 1)
@@ -40,6 +42,7 @@ extern int ipc_mni_shift;
#else /* CONFIG_SYSVIPC_SYSCTL */
#define ipc_mni IPCMNI
+#define ipc_min_cycle RADIX_TREE_MAP_SIZE
#define ipcmni_seq_shift() IPCMNI_SHIFT
#define IPCMNI_IDX_MASK ((1 << IPCMNI_SHIFT) - 1)
#endif /* CONFIG_SYSVIPC_SYSCTL */
_
Patches currently in -mm which might be from manfred@xxxxxxxxxxxxxxxx are
ipc-conserve-sequence-numbers-in-ipcmni_extend-mode.patch
ipc-do-cyclic-id-allocation-for-the-ipc-object.patch
