SLUB: [RFC] Per cpu partial lists V2

PATCH In review Christoph Lameter 3 participants 8 messages Jun 20, 2011 – Jul 7, 2011

Subsystems (2)

Memory management Slab allocator

lore

Share & tools

lore

Christoph Lameter

author

2011-06-20 15:33 UTC #0 lore raw

cover SLUB: [RFC] Per cpu partial lists V2

The following patchset applied on top of the lockless patchset V7. It introduces per cpu partial lists which allow a performance increase of around ~15 during contention for the nodelock (can be tested using hackbench).

These lists help to avoid per nodelocking overhead. Allocator latency could be further reduced by making these operations work without disabling interrupts (like the fastpath and the free slowpath) as well as implementing better ways of handling ther cpu array with partial pages.

I am still not satisfied with the cleanliness of the code after these changes. Some review with suggestions as to how to restructure the code given these changes in operations would be appreciated.

It is interesting to note that BSD has gone to a scheme with partial pages only per cpu (source: Adrian). Transfer of cpu ownerships is done using IPIs. Probably too much overhead for our taste. The use of a few per cpu partial pages looks to be beneficial though.

Note that there is no performance gain when there is no contention.

Performance:

Before After
./hackbench 100 process 200000

				Time: 2299.072	1742.454
./hackbench 100 process 20000
				Time: 224.654	182.393
./hackbench 100 process 20000
				Time: 227.126	182.780
./hackbench 100 process 20000
				Time: 219.608	182.899
./hackbench 10 process 20000
				Time: 21.769	18.756
./hackbench 10 process 20000
				Time: 21.657	18.938
./hackbench 10 process 20000
				Time: 23.193	19.537
./hackbench 1 process 20000
				Time: 2.337	2.263
./hackbench 1 process 20000
				Time: 2.223	2.271
./hackbench 1 process 20000
				Time: 2.269	2.301

Christoph Lameter

author

2011-06-20 15:33 UTC #1 lore raw

PATCH 1/4 slub: Prepare inuse field in new_slab()

inuse will always be set to page->objects. There is no point in initializing the field to zero in new_slab() and then overwriting the value in __slab_alloc().

Signed-off-by Christoph Lameter <[email protected]>

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

mm/slub.c +2 -3

Index: linux-2.6/mm/slub.c
===================================================================
@@ -1341,7 +1341,7 @@ static struct page *new_slab(struct kmem
 	set_freepointer(s, last, NULL);
 
 	page->freelist = start;
-	page->inuse = 0;
+	page->inuse = page->objects;
 	page->frozen = 1;
 out:
 	return page;

@@ -2036,7 +2036,6 @@ new_slab:
 		 */
 		object = page->freelist;
 		page->freelist = NULL;
-		page->inuse = page->objects;
 
 		stat(s, ALLOC_SLAB);
 		c->node = page_to_nid(page);

@@ -2574,7 +2573,7 @@ static void early_kmem_cache_node_alloc(
 	n = page->freelist;
 	BUG_ON(!n);
 	page->freelist = get_freepointer(kmem_cache_node, n);
-	page->inuse++;
+	page->inuse = 1;
 	page->frozen = 0;
 	kmem_cache_node->node[node] = n;
 #ifdef CONFIG_SLUB_DEBUG

Christoph Lameter

author

2011-06-20 15:33 UTC #2 lore raw

PATCH 2/4 slub: pass kmem_cache_cpu pointer to get_partial()

In reply to Christoph Lameter

Pass the kmem_cache_cpu pointer to get_partial(). That way we can avoid the this_cpu_write() statements.

Signed-off-by Christoph Lameter <[email protected]>

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

mm/slub.c +15 ~~-15~~

Index: linux-2.6/mm/slub.c
===================================================================
@@ -1451,7 +1451,8 @@ static inline void remove_partial(struct
  * Must hold list_lock.
  */
 static inline int acquire_slab(struct kmem_cache *s,
-		struct kmem_cache_node *n, struct page *page)
+		struct kmem_cache_node *n, struct page *page,
+		struct kmem_cache_cpu *c)
 {
 	void *freelist;
 	unsigned long counters;

@@ -1480,9 +1481,9 @@ static inline int acquire_slab(struct km
 
 	if (freelist) {
 		/* Populate the per cpu freelist */
-		this_cpu_write(s->cpu_slab->freelist, freelist);
-		this_cpu_write(s->cpu_slab->page, page);
-		this_cpu_write(s->cpu_slab->node, page_to_nid(page));
+		c->freelist = freelist;
+		c->page = page;
+		c->node = page_to_nid(page);
 		return 1;
 	} else {
 		/*

@@ -1500,7 +1501,7 @@ static inline int acquire_slab(struct km
  * Try to allocate a partial slab from a specific node.
  */
 static struct page *get_partial_node(struct kmem_cache *s,
-					struct kmem_cache_node *n)
+		struct kmem_cache_node *n, struct kmem_cache_cpu *c)
 {
 	struct page *page;

@@ -1515,7 +1516,7 @@ static struct page *get_partial_node(str
 
 	spin_lock(&n->list_lock);
 	list_for_each_entry(page, &n->partial, lru)
-		if (acquire_slab(s, n, page))
+		if (acquire_slab(s, n, page, c))
 			goto out;
 	page = NULL;
 out:

@@ -1526,7 +1527,8 @@ out:
 /*
  * Get a page from somewhere. Search in increasing NUMA distances.
  */
-static struct page *get_any_partial(struct kmem_cache *s, gfp_t flags)
+static struct page *get_any_partial(struct kmem_cache *s, gfp_t flags,
+		struct kmem_cache_cpu *c)
 {
 #ifdef CONFIG_NUMA
 	struct zonelist *zonelist;

@@ -1566,7 +1568,7 @@ static struct page *get_any_partial(stru
 
 		if (n && cpuset_zone_allowed_hardwall(zone, flags) &&
 				n->nr_partial > s->min_partial) {
-			page = get_partial_node(s, n);
+			page = get_partial_node(s, n, c);
 			if (page) {
 				put_mems_allowed();
 				return page;

@@ -1581,16 +1583,17 @@ static struct page *get_any_partial(stru
 /*
  * Get a partial page, lock it and return it.
  */
-static struct page *get_partial(struct kmem_cache *s, gfp_t flags, int node)
+static struct page *get_partial(struct kmem_cache *s, gfp_t flags, int node,
+		struct kmem_cache_cpu *c)
 {
 	struct page *page;
 	int searchnode = (node == NUMA_NO_NODE) ? numa_node_id() : node;
 
-	page = get_partial_node(s, get_node(s, searchnode));
+	page = get_partial_node(s, get_node(s, searchnode), c);
 	if (page || node != NUMA_NO_NODE)
 		return page;
 
-	return get_any_partial(s, flags);
+	return get_any_partial(s, flags, c);
 }
 
 #ifdef CONFIG_PREEMPT

@@ -1659,9 +1662,6 @@ void init_kmem_cache_cpus(struct kmem_ca
 	for_each_possible_cpu(cpu)
 		per_cpu_ptr(s->cpu_slab, cpu)->tid = init_tid(cpu);
 }
-/*
- * Remove the cpu slab
- */
 
 /*
  * Remove the cpu slab

@@ -2013,7 +2013,7 @@ load_freelist:
 	return object;
 
 new_slab:
-	page = get_partial(s, gfpflags, node);
+	page = get_partial(s, gfpflags, node, c);
 	if (page) {
 		stat(s, ALLOC_FROM_PARTIAL);
 		object = c->freelist;

Christoph Lameter

author

2011-06-20 15:33 UTC #3 lore raw

PATCH 3/4 slub: return object pointer from get_partial() / new_slab().

In reply to Christoph Lameter

There is no need anymore to return the pointer to a slab page from get_partial() since it can be assigned to the kmem_cache_cpu structures "page" field.

Return an object pointer instead.

That in turn allows a simplification of the spaghetti code in __slab_alloc().

Signed-off-by Christoph Lameter <[email protected]>

---
 mm/slub.c |  130 ++++++++++++++++++++++++++++++++++----------------------------
 1 file changed, 73 insertions(+), 57 deletions(-)

mm/slub.c +73 ~~-57~~

Index: linux-2.6/mm/slub.c
===================================================================
@@ -1448,9 +1448,11 @@ static inline void remove_partial(struct
  * Lock slab, remove from the partial list and put the object into the
  * per cpu freelist.
  *
+ * Returns a list of objects or NULL if it fails.
+ *
  * Must hold list_lock.
  */
-static inline int acquire_slab(struct kmem_cache *s,
+static inline void *acquire_slab(struct kmem_cache *s,
 		struct kmem_cache_node *n, struct page *page,
 		struct kmem_cache_cpu *c)
 {

@@ -1481,10 +1483,11 @@ static inline int acquire_slab(struct km
 
 	if (freelist) {
 		/* Populate the per cpu freelist */
-		c->freelist = freelist;
 		c->page = page;
 		c->node = page_to_nid(page);
-		return 1;
+		stat(s, ALLOC_FROM_PARTIAL);
+
+		return freelist;
 	} else {
 		/*
 		 * Slab page came from the wrong list. No object to allocate

@@ -1493,17 +1496,18 @@ static inline int acquire_slab(struct km
 		 */
 		printk(KERN_ERR "SLUB: %s : Page without available objects on"
 			" partial list\n", s->name);
-		return 0;
+		return NULL;
 	}
 }
 
 /*
  * Try to allocate a partial slab from a specific node.
  */
-static struct page *get_partial_node(struct kmem_cache *s,
+static void *get_partial_node(struct kmem_cache *s,
 		struct kmem_cache_node *n, struct kmem_cache_cpu *c)
 {
 	struct page *page;
+	void *object;
 
 	/*
 	 * Racy check. If we mistakenly see no partial slabs then we

@@ -1515,13 +1519,15 @@ static struct page *get_partial_node(str
 		return NULL;
 
 	spin_lock(&n->list_lock);
-	list_for_each_entry(page, &n->partial, lru)
-		if (acquire_slab(s, n, page, c))
+	list_for_each_entry(page, &n->partial, lru) {
+		object = acquire_slab(s, n, page, c);
+		if (object)
 			goto out;
-	page = NULL;
+	}
+	object = NULL;
 out:
 	spin_unlock(&n->list_lock);
-	return page;
+	return object;
 }
 
 /*

@@ -1535,7 +1541,7 @@ static struct page *get_any_partial(stru
 	struct zoneref *z;
 	struct zone *zone;
 	enum zone_type high_zoneidx = gfp_zone(flags);
-	struct page *page;
+	void *object;
 
 	/*
 	 * The defrag ratio allows a configuration of the tradeoffs between

@@ -1568,10 +1574,10 @@ static struct page *get_any_partial(stru
 
 		if (n && cpuset_zone_allowed_hardwall(zone, flags) &&
 				n->nr_partial > s->min_partial) {
-			page = get_partial_node(s, n, c);
-			if (page) {
+			object = get_partial_node(s, n, c);
+			if (object) {
 				put_mems_allowed();
-				return page;
+				return object;
 			}
 		}
 	}

@@ -1583,15 +1589,15 @@ static struct page *get_any_partial(stru
 /*
  * Get a partial page, lock it and return it.
  */
-static struct page *get_partial(struct kmem_cache *s, gfp_t flags, int node,
+static void *get_partial(struct kmem_cache *s, gfp_t flags, int node,
 		struct kmem_cache_cpu *c)
 {
-	struct page *page;
+	void *object;
 	int searchnode = (node == NUMA_NO_NODE) ? numa_node_id() : node;
 
-	page = get_partial_node(s, get_node(s, searchnode), c);
-	if (page || node != NUMA_NO_NODE)
-		return page;
+	object = get_partial_node(s, get_node(s, searchnode), c);
+	if (object || node != NUMA_NO_NODE)
+		return object;
 
 	return get_any_partial(s, flags, c);
 }

@@ -1921,6 +1927,35 @@ slab_out_of_memory(struct kmem_cache *s,
 	}
 }
 
+static inline void *new_slab_objects(struct kmem_cache *s, gfp_t flags,
+			int node, struct kmem_cache_cpu **pc)
+{
+	void *object;
+	struct kmem_cache_cpu *c;
+	struct page *page = new_slab(s, flags, node);
+
+	if (page) {
+		c = __this_cpu_ptr(s->cpu_slab);
+		if (c->page)
+			flush_slab(s, c);
+
+		/*
+		 * No other reference to the page yet so we can
+		 * muck around with it freely without cmpxchg
+		 */
+		object = page->freelist;
+		page->freelist = NULL;
+
+		stat(s, ALLOC_SLAB);
+		c->node = page_to_nid(page);
+		c->page = page;
+		*pc = c;
+	} else
+		object = NULL;
+
+	return object;
+}
+
 /*
  * Slow path. The lockless freelist is empty or we need to perform
  * debugging duties.

@@ -1943,7 +1978,6 @@ static void *__slab_alloc(struct kmem_ca
 			  unsigned long addr, struct kmem_cache_cpu *c)
 {
 	void **object;
-	struct page *page;
 	unsigned long flags;
 	struct page new;
 	unsigned long counters;

@@ -1961,8 +1995,7 @@ static void *__slab_alloc(struct kmem_ca
 	/* We handle __GFP_ZERO in the caller */
 	gfpflags &= ~__GFP_ZERO;
 
-	page = c->page;
-	if (!page)
+	if (!c->page)
 		goto new_slab;
 
 	if (unlikely(!node_match(c, node))) {

@@ -1974,8 +2007,8 @@ static void *__slab_alloc(struct kmem_ca
 	stat(s, ALLOC_SLOWPATH);
 
 	do {
-		object = page->freelist;
-		counters = page->counters;
+		object = c->page->freelist;
+		counters = c->page->counters;
 		new.counters = counters;
 		VM_BUG_ON(!new.frozen);

@@ -1987,12 +2020,12 @@ static void *__slab_alloc(struct kmem_ca
 		 *
 		 * If there are objects left then we retrieve them
 		 * and use them to refill the per cpu queue.
-		*/
+		 */
 
-		new.inuse = page->objects;
+		new.inuse = c->page->objects;
 		new.frozen = object != NULL;
 
-	} while (!cmpxchg_double_slab(s, page,
+	} while (!cmpxchg_double_slab(s, c->page,
 			object, counters,
 			NULL, new.counters,
 			"__slab_alloc"));

@@ -2006,50 +2039,33 @@ static void *__slab_alloc(struct kmem_ca
 	stat(s, ALLOC_REFILL);
 
 load_freelist:
-	VM_BUG_ON(!page->frozen);
 	c->freelist = get_freepointer(s, object);
 	c->tid = next_tid(c->tid);
 	local_irq_restore(flags);
 	return object;
 
 new_slab:
-	page = get_partial(s, gfpflags, node, c);
-	if (page) {
-		stat(s, ALLOC_FROM_PARTIAL);
-		object = c->freelist;
+	object = get_partial(s, gfpflags, node, c);
 
-		if (kmem_cache_debug(s))
-			goto debug;
-		goto load_freelist;
-	}
+	if (unlikely(!object)) {
 
-	page = new_slab(s, gfpflags, node);
+		object = new_slab_objects(s, gfpflags, node, &c);
 
-	if (page) {
-		c = __this_cpu_ptr(s->cpu_slab);
-		if (c->page)
-			flush_slab(s, c);
+		if (unlikely(!object)) {
+			if (!(gfpflags & __GFP_NOWARN) && printk_ratelimit())
+				slab_out_of_memory(s, gfpflags, node);
 
-		/*
-		 * No other reference to the page yet so we can
-		 * muck around with it freely without cmpxchg
-		 */
-		object = page->freelist;
-		page->freelist = NULL;
+			local_irq_restore(flags);
+			return NULL;
+		}
+	}
 
-		stat(s, ALLOC_SLAB);
-		c->node = page_to_nid(page);
-		c->page = page;
+	if (likely(!kmem_cache_debug(s)))
 		goto load_freelist;
-	}
-	if (!(gfpflags & __GFP_NOWARN) && printk_ratelimit())
-		slab_out_of_memory(s, gfpflags, node);
-	local_irq_restore(flags);
-	return NULL;
 
-debug:
-	if (!object || !alloc_debug_processing(s, page, object, addr))
-		goto new_slab;
+	/* Only entered in the debug case */
+	if (!alloc_debug_processing(s, c->page, object, addr))
+		goto new_slab;	/* Slab failed checks. Next slab needed */
 
 	c->freelist = get_freepointer(s, object);
 	deactivate_slab(s, c);

Christoph Lameter

author

2011-06-20 15:33 UTC #4 lore raw

PATCH 4/4 slub: [RFC] per cpu cache for partial pages

In reply to Christoph Lameter

Allow filling out the rest of the kmem_cache_cpu cacheline with pointers to partial pages. The partial page list is used in slab_free() to avoid per node lock taking.

In __slab_alloc() we can then take multiple partial pages off the per node partial list in one go reducing node lock pressure.
We can also use the per cpu partial list in slab_alloc() to avoid scanning partial lists for pages with free objects.

The main effect of a per cpu partial list is that the per node list_lock is taken for batches of partial pages instead of individual ones.

This is only a first stab at this. There are some limitations:

1. We have to scan through an percpu array of page pointers. That is fast since we stick to a cacheline size.

2. The pickup in __slab_alloc() could consider NUMA locality instead of blindly picking the first partial block.

3. The "unfreeze()" function should have common code with deactivate_slab(). Maybe those can be unified.

Future enhancements:

1. The pickup from the partial list could be perhaps be done without disabling interrupts with some work. The free path already puts the page into the per cpu partial list without disabling interrupts.

2. Configure the size of the per cpu partial blocks dynamically like the other aspects of slab operations.

3. The __slab_free() likely has some code path that are unnecessary now or where code is duplicated.

4. We dump all partials if the per cpu array overflows. There must be some other better algorithm.

5. We could reduce list_lock overhead further by allocation a set of partial lists in slab alloc instead of only one.

Performance:

Before After
./hackbench 100 process 200000

				Time: 2299.072	1742.454
./hackbench 100 process 20000
				Time: 224.654	182.393
./hackbench 100 process 20000
				Time: 227.126	182.780
./hackbench 100 process 20000
				Time: 219.608	182.899
./hackbench 10 process 20000
				Time: 21.769	18.756
./hackbench 10 process 20000
				Time: 21.657	18.938
./hackbench 10 process 20000
				Time: 23.193	19.537
./hackbench 1 process 20000
				Time: 2.337	2.263
./hackbench 1 process 20000
				Time: 2.223	2.271
./hackbench 1 process 20000
				Time: 2.269	2.301

Signed-off-by Christoph Lameter <[email protected]>

---
 include/linux/slub_def.h |    4 
 mm/slub.c                |  286 +++++++++++++++++++++++++++++++++++++++--------
 2 files changed, 243 insertions(+), 47 deletions(-)

include/linux/slub_def.h +4 -0

Index: linux-2.6/include/linux/slub_def.h
===================================================================
@@ -36,6 +36,8 @@ enum stat_item {
 	ORDER_FALLBACK,		/* Number of times fallback was necessary */
 	CMPXCHG_DOUBLE_CPU_FAIL,/* Failure of this_cpu_cmpxchg_double */
 	CMPXCHG_DOUBLE_FAIL,	/* Number of times that cmpxchg double did not match */
+	CPU_PARTIAL_ALLOC,	/* Used cpu partial on alloc */
+	CPU_PARTIAL_FREE,	/* USed cpu partial on free */
 	NR_SLUB_STAT_ITEMS };
 
 struct kmem_cache_cpu {

@@ -46,6 +48,7 @@ struct kmem_cache_cpu {
 #ifdef CONFIG_SLUB_STATS
 	unsigned stat[NR_SLUB_STAT_ITEMS];
 #endif
+	struct page *partial[];	/* Partially allocated frozen slabs */
 };
 
 struct kmem_cache_node {

@@ -79,6 +82,7 @@ struct kmem_cache {
 	int size;		/* The size of an object including meta data */
 	int objsize;		/* The size of an object without meta data */
 	int offset;		/* Free pointer offset. */
+	int cpu_partial;	/* Number of per cpu partial pages to keep around */
 	struct kmem_cache_order_objects oo;
 
 	/* Allocation and freeing of slabs */

mm/slub.c +239 ~~-47~~

419 lines not on this page · raw message

Andi Kleen

2011-06-20 19:42 UTC #5 lore raw

In reply to Christoph Lameter

Quoted 4 lines · Christoph Lameter

The following patchset applied on top of the lockless patchset V7. It introduces per cpu partial lists which allow a performance increase of around ~15 during contention for the nodelock (can be tested using hackbench).

What size system did you test it on?

Quoted 5 lines

These lists help to avoid per nodelocking overhead. Allocator latency could be further reduced by making these operations work without disabling interrupts (like the fastpath and the free slowpath) as well as implementing better ways of handling ther cpu array with partial pages.

I think we really need better batching for the transfers.

-andi

Signature · 1 line

[email protected] -- Speaking for myself only.

Christoph Lameter

author

2011-06-20 20:01 UTC #6 lore raw

Quoted 7 lines · Andi Kleen

Quoted 4 lines · Christoph Lameter
The following patchset applied on top of the lockless patchset V7. It introduces per cpu partial lists which allow a performance increase of around ~15 during contention for the nodelock (can be tested using hackbench).
What size system did you test it on?

Sandybridge 4 core (8 cpus) 8G Ram.

Quoted 6 lines

Quoted 4 lines
These lists help to avoid per nodelocking overhead. Allocator latency could be further reduced by making these operations work without disabling interrupts (like the fastpath and the free slowpath) as well as implementing better ways of handling ther cpu array with partial pages.
I think we really need better batching for the transfers.

Could you elaborate on that cryptic remark?

Pekka Enberg

2011-07-07 19:05 UTC #7 lore raw

In reply to Christoph Lameter

Quoted 36 lines · Christoph Lameter

The following patchset applied on top of the lockless patchset V7. It introduces per cpu partial lists which allow a performance increase of around ~15 during contention for the nodelock (can be tested using hackbench).
These lists help to avoid per nodelocking overhead. Allocator latency could be further reduced by making these operations work without disabling interrupts (like the fastpath and the free slowpath) as well as implementing better ways of handling ther cpu array with partial pages.
I am still not satisfied with the cleanliness of the code after these changes. Some review with suggestions as to how to restructure the code given these changes in operations would be appreciated.
It is interesting to note that BSD has gone to a scheme with partial pages only per cpu (source: Adrian). Transfer of cpu ownerships is done using IPIs. Probably too much overhead for our taste. The use of a few per cpu partial pages looks to be beneficial though.
Note that there is no performance gain when there is no contention.
Performance:
Before After
./hackbench 100 process 200000
				Time: 2299.072	1742.454
./hackbench 100 process 20000
				Time: 224.654	182.393
./hackbench 100 process 20000
				Time: 227.126	182.780
./hackbench 100 process 20000
				Time: 219.608	182.899
./hackbench 10 process 20000
				Time: 21.769	18.756
./hackbench 10 process 20000
				Time: 21.657	18.938

Quoted 8 lines

./hackbench 10 process 20000

				Time: 23.193	19.537
./hackbench 1 process 20000
				Time: 2.337	2.263
./hackbench 1 process 20000
				Time: 2.223	2.271
./hackbench 1 process 20000
				Time: 2.269	2.301

Impressive numbers! David, comments on the series?

Pekka