• Christoph Lameter's avatar
    SLUB: Avoid page struct cacheline bouncing due to remote frees to cpu slab · dfb4f096
    Christoph Lameter authored
    A remote free may access the same page struct that also contains the lockless
    freelist for the cpu slab. If objects have a short lifetime and are freed by
    a different processor then remote frees back to the slab from which we are
    currently allocating are frequent. The cacheline with the page struct needs
    to be repeately acquired in exclusive mode by both the allocating thread and
    the freeing thread. If this is frequent enough then performance will suffer
    because of cacheline bouncing.
    
    This patchset puts the lockless_freelist pointer in its own cacheline. In
    order to make that happen we introduce a per cpu structure called
    kmem_cache_cpu.
    
    Instead of keeping an array of pointers to page structs we now keep an array
    to a per cpu structure that--among other things--contains the pointer to the
    lockless freelist. The freeing thread can then keep possession of exclusive
    access to the page struct cacheline while the allocating thread keeps its
    exclusive access to the cacheline containing the per cpu structure.
    
    This works as long as the allocating cpu is able to service its request
    from the lockless freelist. If the lockless freelist runs empty then the
    allocating thread needs to acquire exclusive access to the cacheline with
    the page struct lock the slab.
    
    The allocating thread will then check if new objects were freed to the per
    cpu slab. If so it will keep the slab as the cpu slab and continue with the
    recently remote freed objects. So the allocating thread can take a series
    of just freed remote pages and dish them out again. Ideally allocations
    could be just recycling objects in the same slab this way which will lead
    to an ideal allocation / remote free pattern.
    
    The number of objects that can be handled in this way is limited by the
    capacity of one slab. Increasing slab size via slub_min_objects/
    slub_max_order may increase the number of objects and therefore performance.
    
    If the allocating thread runs out of objects and finds that no objects were
    put back by the remote processor then it will retrieve a new slab (from the
    partial lists or from the page allocator) and start with a whole
    new set of objects while the remote thread may still be freeing objects to
    the old cpu slab. This may then repeat until the new slab is also exhausted.
    If remote freeing has freed objects in the earlier slab then that earlier
    slab will now be on the partial freelist and the allocating thread will
    pick that slab next for allocation. So the loop is extended. However,
    both threads need to take the list_lock to make the swizzling via
    the partial list happen.
    
    It is likely that this kind of scheme will keep the objects being passed
    around to a small set that can be kept in the cpu caches leading to increased
    performance.
    
    More code cleanups become possible:
    
    - Instead of passing a cpu we can now pass a kmem_cache_cpu structure around.
      Allows reducing the number of parameters to various functions.
    - Can define a new node_match() function for NUMA to encapsulate locality
      checks.
    
    Effect on allocations:
    
    Cachelines touched before this patch:
    
    	Write:	page cache struct and first cacheline of object
    
    Cachelines touched after this patch:
    
    	Write:	kmem_cache_cpu cacheline and first cacheline of object
    	Read: page cache struct (but see later patch that avoids touching
    		that cacheline)
    
    The handling when the lockless alloc list runs empty gets to be a bit more
    complicated since another cacheline has now to be written to. But that is
    halfway out of the hot path.
    
    Effect on freeing:
    
    Cachelines touched before this patch:
    
    	Write: page_struct and first cacheline of object
    
    Cachelines touched after this patch depending on how we free:
    
      Write(to cpu_slab):	kmem_cache_cpu struct and first cacheline of object
      Write(to other):	page struct and first cacheline of object
    
      Read(to cpu_slab):	page struct to id slab etc. (but see later patch that
      			avoids touching the page struct on free)
      Read(to other):	cpu local kmem_cache_cpu struct to verify its not
      			the cpu slab.
    
    Summary:
    
    Pro:
    	- Distinct cachelines so that concurrent remote frees and local
    	  allocs on a cpuslab can occur without cacheline bouncing.
    	- Avoids potential bouncing cachelines because of neighboring
    	  per cpu pointer updates in kmem_cache's cpu_slab structure since
    	  it now grows to a cacheline (Therefore remove the comment
    	  that talks about that concern).
    
    Cons:
    	- Freeing objects now requires the reading of one additional
    	  cacheline. That can be mitigated for some cases by the following
    	  patches but its not possible to completely eliminate these
    	  references.
    
    	- Memory usage grows slightly.
    
    	The size of each per cpu object is blown up from one word
    	(pointing to the page_struct) to one cacheline with various data.
    	So this is NR_CPUS*NR_SLABS*L1_BYTES more memory use. Lets say
    	NR_SLABS is 100 and a cache line size of 128 then we have just
    	increased SLAB metadata requirements by 12.8k per cpu.
    	(Another later patch reduces these requirements)
    Signed-off-by: default avatarChristoph Lameter <clameter@sgi.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    dfb4f096
slub.c 90.5 KB