• Manfred Spraul's avatar
    ipc: do cyclic id allocation for the ipc object. · 99db46ea
    Manfred Spraul authored
    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).
    
    [akpm@linux-foundation.org: fix max() warning]
    Link: http://lkml.kernel.org/r/20190329204930.21620-3-longman@redhat.comSigned-off-by: default avatarManfred Spraul <manfred@colorfullife.com>
    Acked-by: default avatarWaiman Long <longman@redhat.com>
    Cc: "Luis R. Rodriguez" <mcgrof@kernel.org>
    Cc: Kees Cook <keescook@chromium.org>
    Cc: Jonathan Corbet <corbet@lwn.net>
    Cc: Al Viro <viro@zeniv.linux.org.uk>
    Cc: Matthew Wilcox <willy@infradead.org>
    Cc: "Eric W . Biederman" <ebiederm@xmission.com>
    Cc: Takashi Iwai <tiwai@suse.de>
    Cc: Davidlohr Bueso <dbueso@suse.de>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    99db46ea
ipc_sysctl.c 6.25 KB