Per cpu structures for SLUB

The following patchset introduces per cpu structures for SLUB. These are very small (and multiples of these may fit into one cacheline) and (apart from performance improvements) allow the addressing of several isues in SLUB:

1. The number of objects per slab is no longer limited to a 16 bit number.

2. Room is freed up in the page struct. We can avoid using the mapping field which allows to get rid of the #ifdef CONFIG_SLUB in page_mapping().

3. We will have an easier time adding new things like Peter Z.s reserve management.

The RFC for this patchset was discussed on lkml a while ago:

http://marc.info/?l=linux-kernel&m=118386677704534&w=2

(And no this patchset does not include the use of cmpxchg_local that we discussed recently on lkml nor the cmpxchg implementation mentioned in the RFC)

Performance
-----------

Norm = 2.6.23-rc3
PCPU = Adds page allocator pass through plus per cpu structure patches

IA64 8p 4n NUMA Altix

Single threaded Concurrent Alloc

Kmalloc Alloc/Free Kmalloc Alloc/Free
Size Norm PCPU Norm PCPU Norm PCPU Norm PCPU
-------------------------------------------------------------------

    8	132	84	93	104	98	90	95	106
   16    98	92	93	104	115	98	95	106
   32   112	105	93	104	146	111	95	106
   64	119	112	93	104	214	133	95	106
  128   132	119	94	104	321	163	95	106
  256+  83255	176	106	115	415	224	108	117
  512   191	176	106	115	487	341	108	117
 1024   252	246	106	115	937	609	108	117
 2048   308	292	107	115	2494	1207	108	117
 4096   341	319	107	115	2497	1217	108	117
 8192   402	380	107	115	2367	1188	108	117
16384*  560	474	106	434	4464	1904	108	478

X86_64 2p SMP (Dual Core Pentium 940)

Single threaded Concurrent Alloc

Kmalloc Alloc/Free Kmalloc Alloc/Free
Size Norm PCPU Norm PCPU Norm PCPU Norm PCPU
--------------------------------------------------------------------

    8	313	227	314	324	207	208	314	323
   16   202	203	315	324	209	211	312	321
   32	212	207	314	324	251	243	312	321
   64	240	237	314	326	329	306	312	321
  128	301	302	314	324	511	416	313	324
  256   498	554	327	332	970	837	326	332
  512   532	553	324	332	1025	932	326	335
 1024   705	718	325	333	1489	1231	324	330
 2048   764	767	324	334	2708	2175	324	332

4096* 1033 476 325 674 4727 782 324 678

Notes:

Worst case:
-----------
We generally loose in the alloc free test (x86_64 3%, IA64 5-10%) since the processing overhead increases because we need to lookup the per cpu structure. Alloc/Free is simply kfree(kmalloc(size, mask)). So objects with the shortest lifetime possible. We would never use objects in that way but the measurement is important to show the worst case overhead created.

Single Threaded:
----------------
The single threaded kmalloc test shows behavior of a continual stream of allocation without contention. In the SMP case the losses are minimal. In the NUMA case we already have a winner there because the per cpu structure is placed local to the processor. So in the single threaded case we already win around 5% just by placing things better.

Concurrent Alloc:
-----------------
We have varying gains up to a 50% on NUMA because we are now never updating a cacheline used by the other processor and the data structures are local to the processor.

The SMP case shows gains but they are smaller (especially since this is the smallest SMP system possible.... 2 CPUs). So only up to 25%.

Page allocator pass through
---------------------------
There is a significant difference in the columns marked with a * because of the way that allocations for page sized objects are handled. If we handle the allocations in the slab allocator (Norm) then the alloc free tests results are superb since we can use the per cpu slab to just pass a pointer back and forth. The page allocator pass through (PCPU) shows that the page allocator may have problems with giving back the same page after a free. Or there something else in the page allocator that creates significant overhead compared to slab. Needs to be checked out I guess.

However, the page allocator pass through is a win in the other cases since we can cut out the page allocator overhead. That is the more typical load of allocating a sequence of objects and we should optimize for that.

(+ = Must be some cache artifact here or code crossing a TLB boundary. The result is reproducable)

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)

---
 include/linux/slub_def.h |    9 +-
 mm/slub.c                |  192 ++++++++++++++++++++++++++++-------------------
 2 files changed, 126 insertions(+), 75 deletions(-)

Index: linux-2.6.23-rc3-mm1/include/linux/slub_def.h
===================================================================
@@ -11,6 +11,13 @@
 #include <linux/workqueue.h>
 #include <linux/kobject.h>
 
+struct kmem_cache_cpu {
+	void **freelist;
+	struct page *page;
+	int node;
+	/* Lots of wasted space */
+} ____cacheline_aligned_in_smp;
+
 struct kmem_cache_node {
 	spinlock_t list_lock;	/* Protect partial list and nr_partial */
 	unsigned long nr_partial;

@@ -54,7 +61,7 @@ struct kmem_cache {
 	int defrag_ratio;
 	struct kmem_cache_node *node[MAX_NUMNODES];
 #endif
-	struct page *cpu_slab[NR_CPUS];
+	struct kmem_cache_cpu cpu_slab[NR_CPUS];
 };
 
 /*

After moving the lockless_freelist to kmem_cache_cpu we no longer need page->lockless_freelist. Restructure the use of the struct page fields in such a way that we never touch the mapping field.

This is turn allows us to remove the special casing of SLUB when determining the mapping of a page (needed for corner cases of virtual caches machines that need to flush caches of processors mapping a page).

---
 include/linux/mm_types.h |    9 ++-------
 mm/slub.c                |    2 --
 2 files changed, 2 insertions(+), 9 deletions(-)

Index: linux-2.6.23-rc3-mm1/include/linux/mm_types.h
===================================================================
@@ -62,13 +62,8 @@ struct page {
 #if NR_CPUS >= CONFIG_SPLIT_PTLOCK_CPUS
 	    spinlock_t ptl;
 #endif
-	    struct {			/* SLUB uses */
-	    	void **lockless_freelist;
-		struct kmem_cache *slab;	/* Pointer to slab */
-	    };
-	    struct {
-		struct page *first_page;	/* Compound pages */
-	    };
+	    struct kmem_cache *slab;	/* SLUB: Pointer to slab */
+	    struct page *first_page;	/* Compound tail pages */
 	};
 	union {
 		pgoff_t index;		/* Our offset within mapping. */

Index: linux-2.6.23-rc3-mm1/mm/slub.c
===================================================================
@@ -1125,7 +1125,6 @@ static struct page *new_slab(struct kmem
 	set_freepointer(s, last, NULL);
 
 	page->freelist = start;
-	page->lockless_freelist = NULL;
 	page->inuse = 0;
 out:
 	if (flags & __GFP_WAIT)

@@ -1151,7 +1150,6 @@ static void __free_slab(struct kmem_cach
 		NR_SLAB_RECLAIMABLE : NR_SLAB_UNRECLAIMABLE,
 		- pages);
 
-	page->mapping = NULL;
 	__free_pages(page, s->order);
 }
 

We need the offset from the page struct during slab_alloc and slab_free. In both cases we also reference the cacheline of the kmem_cache_cpu structure. We can therefore move the offset field into the kmem_cache_cpu structure freeing up 16 bits in the page struct.

Moving the offset allows an allocation from slab_alloc() without touching the page struct in the hot path.

The only thing left in slab_free() that touches the page struct cacheline for per cpu freeing is the checking of SlabDebug(page). The next patch deals with that.

Use the available 16 bits to broaden page->inuse. More than 64k objects per slab become possible and we can get rid of the checks for that limitation.

No need anymore to shrink the order of slabs if we boot with 2M sized slabs (slub_min_order=9).

No need anymore to switch off the offset calculation for very large slabs since the field in the kmem_cache_cpu structure is 32 bits and so the offset field can now handle slab sizes of up to 8GB.

---
 include/linux/mm_types.h |    5 --
 include/linux/slub_def.h |    1 
 mm/slub.c                |   80 +++++++++--------------------------------------
 3 files changed, 18 insertions(+), 68 deletions(-)

Index: linux-2.6.23-rc3-mm1/include/linux/mm_types.h
===================================================================
@@ -37,10 +37,7 @@ struct page {
 					 * to show when page is mapped
 					 * & limit reverse map searches.
 					 */
-		struct {	/* SLUB uses */
-			short unsigned int inuse;
-			short unsigned int offset;
-		};
+		unsigned int inuse;	/* SLUB: Nr of objects */
 	};
 	union {
 	    struct {

Index: linux-2.6.23-rc3-mm1/include/linux/slub_def.h
===================================================================
@@ -15,6 +15,7 @@ struct kmem_cache_cpu {
 	void **freelist;
 	struct page *page;
 	int node;
+	unsigned int offset;
 	/* Lots of wasted space */
 } ____cacheline_aligned_in_smp;
 

Set c->node to -1 if we allocate from a debug slab instead for SlabDebug which requires access the page struct cacheline.

---
 mm/slub.c |    6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

Index: linux-2.6.23-rc3-mm1/mm/slub.c
===================================================================
@@ -1517,6 +1517,7 @@ debug:
 
 	c->page->inuse++;
 	c->page->freelist = object[c->offset];
+	c->node = -1;
 	slab_unlock(c->page);
 	return object;
 }

@@ -1540,8 +1541,7 @@ static void __always_inline *slab_alloc(
 
 	local_irq_save(flags);
 	c = get_cpu_slab(s, smp_processor_id());
-	if (unlikely(!c->page || !c->freelist ||
-					!node_match(c, node)))
+	if (unlikely(!c->freelist || !node_match(c, node)))
 
 		object = __slab_alloc(s, gfpflags, node, addr, c);
 

@@ -1650,7 +1650,7 @@ static void __always_inline slab_free(st
 	local_irq_save(flags);
 	debug_check_no_locks_freed(object, s->objsize);
 	c = get_cpu_slab(s, smp_processor_id());
-	if (likely(page == c->page && !SlabDebug(page))) {
+	if (likely(page == c->page && c->node >= 0)) {
 		object[c->offset] = c->freelist;
 		c->freelist = object;
 	} else

this relies on node_match() which will only ever return !1 when CONFIG_NUMA

Yup the later cmpxchg patches papered that over for awhile.

So we need to also check for -1 if !NUMA

---
 mm/slub.c |    4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

Index: linux-2.6.23-rc3-mm1/mm/slub.c
===================================================================
@@ -1424,8 +1424,10 @@ static void flush_all(struct kmem_cache 
  */
 static inline int node_match(struct kmem_cache_cpu *c, int node)
 {
+	if (node == -1)
+		return 0;
 #ifdef CONFIG_NUMA
-	if (node != -1 && c->node != node)
+	if (c->node != node)
 		return 0;
 #endif
 	return 1;

Sorry. No we do not need this fix. The patch is fine as is.

In slab_alloc() the slow path is entered if c->lockless is NULL. So it does not matter for slow path determination that node_match always returns 1 in the !NUMA case.

c->node only needs to be checked for slow path determination in slab_free(). And there the node_match is not called.

The kmem_cache_cpu structures introduced are currently an array placed in the kmem_cache struct. Meaning the kmem_cache_cpu structures are overwhelmingly on the wrong node for systems with a higher amount of nodes. These are performance critical structures since the per node information has to be touched for every alloc and free in a slab.

In order to place the kmem_cache_cpu structure optimally we put an array of pointers to kmem_cache_cpu structs in kmem_cache (similar to SLAB).

However, the kmem_cache_cpu structures can now be allocated in a more intelligent way.

We would like to put per cpu structures for the same cpu but different slab caches in cachelines together to save space and decrease the cache footprint. However, the slab allocators itself control only allocations per node. We set up a simple per cpu array for every processor with 100 per cpu structures which is usually enough to get them all set up right. If we run out then we fall back to kmalloc_node. This also solves the bootstrap problem since we do not have to use slab allocator functions early in boot to get memory for the small per cpu structures.

Pro:
- NUMA aware placement improves memory performance
- All global structures in struct kmem_cache become readonly
- Dense packing of per cpu structures reduces cacheline footprint in SMP and NUMA.
- Potential avoidance of exclusive cacheline fetches on the free and alloc hotpath since multiple kmem_cache_cpu structures are in one cacheline. This is particularly important for the kmalloc array.

Cons:
- Additional reference to one read only cacheline (per cpu array of pointers to kmem_cache_cpu) in both slab_alloc() and slab_free().

---
 include/linux/slub_def.h |    9 +-
 mm/slub.c                |  162 ++++++++++++++++++++++++++++++++++++++++++-----
 2 files changed, 154 insertions(+), 17 deletions(-)

Index: linux-2.6.23-rc3-mm1/include/linux/slub_def.h
===================================================================
@@ -16,8 +16,7 @@ struct kmem_cache_cpu {
 	struct page *page;
 	int node;
 	unsigned int offset;
-	/* Lots of wasted space */
-} ____cacheline_aligned_in_smp;
+};
 
 struct kmem_cache_node {
 	spinlock_t list_lock;	/* Protect partial list and nr_partial */

@@ -62,7 +61,11 @@ struct kmem_cache {
 	int defrag_ratio;
 	struct kmem_cache_node *node[MAX_NUMNODES];
 #endif
-	struct kmem_cache_cpu cpu_slab[NR_CPUS];
+#ifdef CONFIG_SMP
+	struct kmem_cache_cpu *cpu_slab[NR_CPUS];
+#else
+	struct kmem_cache_cpu cpu_slab;
+#endif
 };
 
 /*

We touch a cacheline in the kmem_cache structure for zeroing to get the size. However, the hot paths in slab_alloc and slab_free do not reference any other fields in kmem_cache, so we may have to just bring in the cacheline for this one access.

Add a new field to kmem_cache_cpu that contains the object size. That cacheline must already be used in the hotpaths. So we save one cacheline on every slab_alloc if we zero.

We need to update the kmem_cache_cpu object size if an aliasing operation changes the objsize of an non debug slab.

---
 include/linux/slub_def.h |    1 +
 mm/slub.c                |   14 ++++++++++++--
 2 files changed, 13 insertions(+), 2 deletions(-)

Index: linux-2.6.23-rc3-mm1/include/linux/slub_def.h
===================================================================
@@ -16,6 +16,7 @@ struct kmem_cache_cpu {
 	struct page *page;
 	int node;
 	unsigned int offset;
+	unsigned int objsize;
 };
 
 struct kmem_cache_node {

Index: linux-2.6.23-rc3-mm1/mm/slub.c
===================================================================
@@ -1556,7 +1556,7 @@ static void __always_inline *slab_alloc(
 	local_irq_restore(flags);
 
 	if (unlikely((gfpflags & __GFP_ZERO) && object))
-		memset(object, 0, s->objsize);
+		memset(object, 0, c->objsize);
 
 	return object;
 }

@@ -1843,8 +1843,9 @@ static void init_kmem_cache_cpu(struct k
 {
 	c->page = NULL;
 	c->freelist = NULL;
-	c->offset = s->offset / sizeof(void *);
 	c->node = 0;
+	c->offset = s->offset / sizeof(void *);
+	c->objsize = s->objsize;
 }
 
 static void init_kmem_cache_node(struct kmem_cache_node *n)

@@ -2842,12 +2843,21 @@ struct kmem_cache *kmem_cache_create(con
 	down_write(&slub_lock);
 	s = find_mergeable(size, align, flags, ctor);
 	if (s) {
+		int cpu;
+
 		s->refcount++;
 		/*
 		 * Adjust the object sizes so that we clear
 		 * the complete object on kzalloc.
 		 */
 		s->objsize = max(s->objsize, (int)size);
+
+		/*
+		 * And then we need to update the object size in the
+		 * per cpu structures
+		 */
+		for_each_online_cpu(cpu)
+			get_cpu_slab(s, cpu)->objsize = s->objsize;
 		s->inuse = max_t(int, s->inuse, ALIGN(size, sizeof(void *)));
 		up_write(&slub_lock);
 		if (sysfs_slab_alias(s, name))

Hi,

while I like this patch set I'm at odds with the interaction of this and making the alloc/free fast paths lockless.

The main race is s->cpu_slab[] and c->freelist. How does one close that gap?

(btw, have you looked at my -rt slub patch?)

By either reloading the cpu slab after disabling interupts (my initial approach) or by disabling preemption.

I skimmed over it. Not sure what to make of it.

I'm struggling a bit to understand these numbers. Bigger is better, I assume? In what units are these numbers?

OK, but what happened to the third pair of columns (Concurrent Alloc, Kmalloc) for 1024 and 2048-byte allocations? They seem to have become significantly slower?

Thanks for running the numbers, but it's still a bit hard to work out whether these changes are an aggregate benefit?

Most Linux machines are uniprocessor. We should keep an eye on what effect a change like this has on code size and performance for CONFIG_SMP=n builds..

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

No less is better. These are cycle counts. Hmmm... We discussed these cycle counts so much in the last week that I forgot to mention that.

There is a significant performance increase there. That is the main point of the patch.

There is a drawback because of the additional code introduced in the fast path. However, the regular kmalloc case shows improvements throughout. This is in particular of importance for SMP systems. We see an improvement even for 2 processors.

There is an #ifdef around ther per cpu structure management code. All of this will vanish (including the lookup of the per cpu address from the fast path) if SMP is off.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

umm, OK. When you have time, could you please whizz up a clearer changelog for this one?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>