SLUB patches for more functionality, performance and maintenance

This series here contains a number of patches that need some discussion or evaluation. They apply on top of 2.6.22-rc6-mm1 + slub patches already in mm.

1. Page allocator pass through

SLOB does pass through all larger kmalloc requests directly to the page allocator. The advantage is that the allocator overhead is eliminated and that we do not need to provide kmalloc slabs >= PAGE_SIZE. This patch does the same thing in SLUB.

For allocation whose size is know the call to the slab may be converted to a call to the page allocator at compile time.

The result of doing so is also that the behavior of SLUB for pagesize and higher kmalloc allocation will conform to SLAB. Meaning large kmalloc allocations are no longer debuggable and are guaranteed to be page aligned.

Do we want this?

2. A series of performance enhancements patches

The patches improve the producer / consumer scenario. If objects are always allocated on one processor and released on another then both will use distinct cachelines to store their information in order to avoid a bouncing cacheline.

In order to do so we have to introduce a per cpu structure to keep per cpu allocation lists in distinct cachelines from the remote free information in the page struct. If we introduce a per cpu structure then we also need to allocate that in a NUMA aware fashion from the local node.

Having a per cpu structure allows to avoid the use of certain fields in the page struct which in turn allows us to avoid using page->mapping and increasing the maximum number of objects per slab. More optimizations become possible by shifting information from the kmem_cache structure that is used in the hotpath to the per cpu structure thereby minimizing cacheline coverage.

Finally there is an implementation of slab_alloc/slab_free using a cmpxchg instead of current interrupt enable disable approach. This was inspired by LTTng's approach. A cmpxchg is less costly than interrupt enabe/disable but means more complexity in managing the resulting race conditions. The disadvantage is that the allocation / free paths become very complex and fragile.

All of these patches need to be evaluated as to what impact they have on a variety of loads.

3. Removal of SLOB and SLAB.

We would like to consolidate and only have one slab allocator in the future. Two patches are included that remove SLOB and SLAB. There is only minimal justification for retaining SLOB. So I think we could remove SLOB for 2.6.23.

SLAB is the reference that SLUB must be measured against to avoid regressions. On the other hand it will be a problem to support new functionality like Slab defragmentation since its design makes it difficult to implement comparable features. So I think that we need to keep SLAB around for one more cycle and then we may be able to get rid of it. Or we can keep it in the tree for awhile and produce more and more shims for new slab functionality.

This gets rid of all kmalloc caches larger than page size. A kmalloc request larger than PAGE_SIZE > 2 is going to be passed through to the page allocator. This works both inline where we will call __get_free_pages instead of kmem_cache_alloc and in __kmalloc.

kfree is modified to check if the object is in a slab page. If not then the page is freed via the page allocator instead.

Drawbacks:
- No accounting for large kmalloc slab allocations anymore
- No debugging of large kmalloc slab allocations.
- Meshing of slab allocations and page allocator allocations become possible.
- Strange discontinuity in kmalloc operations. If larger than page size then full page allocator semantics apply. But SLOB is already doing that.
- kmalloc objects are aligned to ARCH_KMALLOC_MINALIGN if smaller than PAGE_SIZE otherwise they are
page aligned.
- Additional check of the size in kmalloc and kfree.

Advantages:
- Significantly reduces memory overhead for kmalloc array
- Large kmalloc operations are faster since they do not need to pass through the slab allocator to get to the page allocator.
- Large kmallocs yields page aligned object which is what SLAB does. Bad things like using page sized kmalloc allocations can be transparently handled and are not distinguishable from page allocator uses.
- Checking for too large objects can be removed since
it is done by the page allocator.

---
 include/linux/slub_def.h |   57 +++++++++++++++++-------------------------
 mm/slub.c                |   63 ++++++++++++++++++++++++++++-------------------
 2 files changed, 62 insertions(+), 58 deletions(-)

Index: linux-2.6.22-rc6-mm1/mm/slub.c
===================================================================
@@ -2239,11 +2239,11 @@ EXPORT_SYMBOL(kmem_cache_destroy);
  *		Kmalloc subsystem
  *******************************************************************/
 
-struct kmem_cache kmalloc_caches[KMALLOC_SHIFT_HIGH + 1] __cacheline_aligned;
+struct kmem_cache kmalloc_caches[PAGE_SHIFT] __cacheline_aligned;
 EXPORT_SYMBOL(kmalloc_caches);
 
 #ifdef CONFIG_ZONE_DMA
-static struct kmem_cache *kmalloc_caches_dma[KMALLOC_SHIFT_HIGH + 1];
+static struct kmem_cache *kmalloc_caches_dma[PAGE_SHIFT];
 #endif
 
 static int __init setup_slub_min_order(char *str)

@@ -2379,12 +2379,8 @@ static struct kmem_cache *get_slab(size_
 			return ZERO_SIZE_PTR;
 
 		index = size_index[(size - 1) / 8];
-	} else {
-		if (size > KMALLOC_MAX_SIZE)
-			return NULL;
-
+	} else
 		index = fls(size - 1);
-	}
 
 #ifdef CONFIG_ZONE_DMA
 	if (unlikely((flags & SLUB_DMA)))

@@ -2396,9 +2392,15 @@ static struct kmem_cache *get_slab(size_
 
 void *__kmalloc(size_t size, gfp_t flags)
 {
-	struct kmem_cache *s = get_slab(size, flags);
+	struct kmem_cache *s;
 
-	if (ZERO_OR_NULL_PTR(s))
+	if (unlikely(size > PAGE_SIZE / 2))
+		return (void *)__get_free_pages(flags | __GFP_COMP,
+							get_order(size));
+
+	s = get_slab(size, flags);
+
+	if (unlikely(ZERO_OR_NULL_PTR(s)))
 		return s;
 
 	return slab_alloc(s, flags, -1, __builtin_return_address(0));

@@ -2408,9 +2410,15 @@ EXPORT_SYMBOL(__kmalloc);
 #ifdef CONFIG_NUMA
 void *__kmalloc_node(size_t size, gfp_t flags, int node)
 {
-	struct kmem_cache *s = get_slab(size, flags);
+	struct kmem_cache *s;
 
-	if (ZERO_OR_NULL_PTR(s))
+	if (unlikely(size > PAGE_SIZE / 2))
+		return (void *)__get_free_pages(flags | __GFP_COMP,
+							get_order(size));
+
+	s = get_slab(size, flags);
+
+	if (unlikely(ZERO_OR_NULL_PTR(s)))
 		return s;
 
 	return slab_alloc(s, flags, node, __builtin_return_address(0));

@@ -2455,22 +2463,17 @@ EXPORT_SYMBOL(ksize);
 
 void kfree(const void *x)
 {
-	struct kmem_cache *s;
 	struct page *page;
 
-	/*
-	 * This has to be an unsigned comparison. According to Linus
-	 * some gcc version treat a pointer as a signed entity. Then
-	 * this comparison would be true for all "negative" pointers
-	 * (which would cover the whole upper half of the address space).
-	 */
 	if (ZERO_OR_NULL_PTR(x))
 		return;
 
 	page = virt_to_head_page(x);
-	s = page->slab;
-
-	slab_free(s, page, (void *)x, __builtin_return_address(0));
+	if (unlikely(!PageSlab(page))) {
+		put_page(page);
+		return;
+	}
+	slab_free(page->slab, page, (void *)x, __builtin_return_address(0));
 }
 EXPORT_SYMBOL(kfree);
 

@@ -2927,7 +2930,7 @@ void __init kmem_cache_init(void)
 		caches++;
 	}
 
-	for (i = KMALLOC_SHIFT_LOW; i <= KMALLOC_SHIFT_HIGH; i++) {
+	for (i = KMALLOC_SHIFT_LOW; i < PAGE_SHIFT; i++) {
 		create_kmalloc_cache(&kmalloc_caches[i],
 			"kmalloc", 1 << i, GFP_KERNEL);
 		caches++;

@@ -2954,7 +2957,7 @@ void __init kmem_cache_init(void)
 	slab_state = UP;
 
 	/* Provide the correct kmalloc names now that the caches are up */
-	for (i = KMALLOC_SHIFT_LOW; i <= KMALLOC_SHIFT_HIGH; i++)
+	for (i = KMALLOC_SHIFT_LOW; i < PAGE_SHIFT; i++)
 		kmalloc_caches[i]. name =
 			kasprintf(GFP_KERNEL, "kmalloc-%d", 1 << i);
 

@@ -3142,7 +3145,12 @@ static struct notifier_block __cpuinitda
 
 void *__kmalloc_track_caller(size_t size, gfp_t gfpflags, void *caller)
 {
-	struct kmem_cache *s = get_slab(size, gfpflags);
+	struct kmem_cache *s;
+
+	if (unlikely(size > PAGE_SIZE / 2))
+		return (void *)__get_free_pages(gfpflags | __GFP_COMP,
+							get_order(size));
+	s = get_slab(size, gfpflags);
 
 	if (ZERO_OR_NULL_PTR(s))
 		return s;

@@ -3153,7 +3161,12 @@ void *__kmalloc_track_caller(size_t size
 void *__kmalloc_node_track_caller(size_t size, gfp_t gfpflags,
 					int node, void *caller)
 {
-	struct kmem_cache *s = get_slab(size, gfpflags);
+	struct kmem_cache *s;
+
+	if (unlikely(size > PAGE_SIZE / 2))
+		return (void *)__get_free_pages(gfpflags | __GFP_COMP,
+							get_order(size));
+	s = get_slab(size, gfpflags);
 
 	if (ZERO_OR_NULL_PTR(s))
 		return s;

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                |  191 ++++++++++++++++++++++++++++-------------------
 2 files changed, 124 insertions(+), 76 deletions(-)

Index: linux-2.6.22-rc6-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;

@@ -63,7 +70,7 @@ struct kmem_cache {
 				 */
 	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.h       |    4 ----
 include/linux/mm_types.h |    9 ++-------
 mm/slub.c                |    2 --
 3 files changed, 2 insertions(+), 13 deletions(-)

Index: linux-2.6.22-rc6-mm1/include/linux/mm.h
===================================================================
@@ -632,10 +632,6 @@ static inline struct address_space *page
 	VM_BUG_ON(PageSlab(page));
 	if (unlikely(PageSwapCache(page)))
 		mapping = &swapper_space;
-#ifdef CONFIG_SLUB
-	else if (unlikely(PageSlab(page)))
-		mapping = NULL;
-#endif
 	else if (unlikely((unsigned long)mapping & PAGE_MAPPING_ANON))
 		mapping = NULL;
 	return mapping;

Index: linux-2.6.22-rc6-mm1/include/linux/mm_types.h
===================================================================
@@ -49,13 +49,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.22-rc6-mm1/mm/slub.c
===================================================================
@@ -1109,7 +1109,6 @@ static struct page *new_slab(struct kmem
 		atomic_long_inc(&n->nr_slabs);
 
 	page->inuse = 0;
-	page->lockless_freelist = NULL;
 	page->offset = s->offset / sizeof(void *);
 	page->slab = s;
 

@@ -1163,7 +1162,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 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 flags.

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. That way we can have more than 64k objects per slab and 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                |   75 ++++++++++-------------------------------------
 3 files changed, 19 insertions(+), 62 deletions(-)

Index: linux-2.6.22-rc6-mm1/mm/slub.c
===================================================================
@@ -207,11 +207,6 @@ static inline void ClearSlabDebug(struct
 #define ARCH_SLAB_MINALIGN __alignof__(unsigned long long)
 #endif
 
-/*
- * The page->inuse field is 16 bit thus we have this limitation
- */
-#define MAX_OBJECTS_PER_SLAB 65535
-
 /* Internal SLUB flags */
 #define __OBJECT_POISON 0x80000000	/* Poison object */
 

@@ -741,11 +736,6 @@ static int check_slab(struct kmem_cache 
 		slab_err(s, page, "Not a valid slab page");
 		return 0;
 	}
-	if (page->offset * sizeof(void *) != s->offset) {
-		slab_err(s, page, "Corrupted offset %lu",
-			(unsigned long)(page->offset * sizeof(void *)));
-		return 0;
-	}
 	if (page->inuse > s->objects) {
 		slab_err(s, page, "inuse %u > max %u",
 			s->name, page->inuse, s->objects);

@@ -884,8 +874,6 @@ bad:
 		slab_fix(s, "Marking all objects used");
 		page->inuse = s->objects;
 		page->freelist = NULL;
-		/* Fix up fields that may be corrupted */
-		page->offset = s->offset / sizeof(void *);
 	}
 	return 0;
 }

@@ -1001,30 +989,12 @@ __setup("slub_debug", setup_slub_debug);
 static void kmem_cache_open_debug_check(struct kmem_cache *s)
 {
 	/*
-	 * The page->offset field is only 16 bit wide. This is an offset
-	 * in units of words from the beginning of an object. If the slab
-	 * size is bigger then we cannot move the free pointer behind the
-	 * object anymore.
-	 *
-	 * On 32 bit platforms the limit is 256k. On 64bit platforms
-	 * the limit is 512k.
-	 *
-	 * Debugging or ctor may create a need to move the free
-	 * pointer. Fail if this happens.
+	 * Enable debugging if selected on the kernel commandline.
 	 */
-	if (s->objsize >= 65535 * sizeof(void *)) {
-		BUG_ON(s->flags & (SLAB_RED_ZONE | SLAB_POISON |
-				SLAB_STORE_USER | SLAB_DESTROY_BY_RCU));
-		BUG_ON(s->ctor);
-	}
-	else
-		/*
-		 * Enable debugging if selected on the kernel commandline.
-		 */
-		if (slub_debug && (!slub_debug_slabs ||
-		    strncmp(slub_debug_slabs, s->name,
-		    	strlen(slub_debug_slabs)) == 0))
-				s->flags |= slub_debug;
+	if (slub_debug && (!slub_debug_slabs ||
+	    strncmp(slub_debug_slabs, s->name,
+	    	strlen(slub_debug_slabs)) == 0))
+			s->flags |= slub_debug;
 }
 #else
 static inline void setup_object_debug(struct kmem_cache *s,

@@ -1109,7 +1079,6 @@ static struct page *new_slab(struct kmem
 		atomic_long_inc(&n->nr_slabs);
 
 	page->inuse = 0;
-	page->offset = s->offset / sizeof(void *);
 	page->slab = s;
 
 	start = page_address(page);

@@ -1410,10 +1379,10 @@ static void deactivate_slab(struct kmem_
 
 		/* Retrieve object from cpu_freelist */
 		object = c->freelist;
-		c->freelist = c->freelist[page->offset];
+		c->freelist = c->freelist[c->offset];
 
 		/* And put onto the regular freelist */
-		object[page->offset] = page->freelist;
+		object[c->offset] = page->freelist;
 		page->freelist = object;
 		page->inuse--;
 	}

@@ -1509,7 +1478,7 @@ load_freelist:
 		goto debug;
 
 	object = c->page->freelist;
-	c->freelist = object[c->page->offset];
+	c->freelist = object[c->offset];
 	c->page->inuse = s->objects;
 	c->page->freelist = NULL;
 	c->node = page_to_nid(c->page);

@@ -1561,7 +1530,7 @@ debug:
 		goto another_slab;
 
 	c->page->inuse++;
-	c->page->freelist = object[c->page->offset];
+	c->page->freelist = object[c->offset];
 	slab_unlock(c->page);
 	return object;
 }

@@ -1592,7 +1561,7 @@ static void __always_inline *slab_alloc(
 
 	else {
 		object = c->freelist;
-		c->freelist = object[c->page->offset];
+		c->freelist = object[c->offset];
 	}
 	local_irq_restore(flags);
 

@@ -1625,7 +1594,7 @@ EXPORT_SYMBOL(kmem_cache_alloc_node);
  * handling required then we can return immediately.
  */
 static void __slab_free(struct kmem_cache *s, struct page *page,
-					void *x, void *addr)
+				void *x, void *addr, unsigned int offset)
 {
 	void *prior;
 	void **object = (void *)x;

@@ -1635,7 +1604,7 @@ static void __slab_free(struct kmem_cach
 	if (unlikely(SlabDebug(page)))
 		goto debug;
 checks_ok:
-	prior = object[page->offset] = page->freelist;
+	prior = object[offset] = page->freelist;
 	page->freelist = object;
 	page->inuse--;
 

@@ -1695,10 +1664,10 @@ static void __always_inline slab_free(st
 	local_irq_save(flags);
 	c = get_cpu_slab(s, smp_processor_id());
 	if (likely(page == c->page && !SlabDebug(page))) {
-		object[page->offset] = c->freelist;
+		object[c->offset] = c->freelist;
 		c->freelist = object;
 	} else
-		__slab_free(s, page, x, addr);
+		__slab_free(s, page, x, addr, c->offset);
 
 	local_irq_restore(flags);
 }

@@ -1794,8 +1763,7 @@ static inline int slab_order(int size, i
 	 * If we would create too many object per slab then reduce
 	 * the slab order even if it goes below slub_min_order.
 	 */
-	while (min_order > 0 &&
-		(PAGE_SIZE << min_order) >= MAX_OBJECTS_PER_SLAB * size)
+	while (min_order > 0 && PAGE_SIZE << min_order)
 			min_order--;
 
 	for (order = max(min_order,

@@ -1812,9 +1780,6 @@ static inline int slab_order(int size, i
 		if (rem <= slab_size / fract_leftover)
 			break;
 
-		/* If the next size is too high then exit now */
-		if (slab_size * 2 >= MAX_OBJECTS_PER_SLAB * size)
-			break;
 	}
 
 	return order;

@@ -1894,6 +1859,7 @@ static void init_kmem_cache_cpu(struct k
 {
 	c->page = NULL;
 	c->freelist = NULL;
+	c->offset = s->offset / sizeof(void *);
 	c->node = 0;
 }
 

@@ -2115,14 +2081,7 @@ static int calculate_sizes(struct kmem_c
 	 */
 	s->objects = (PAGE_SIZE << s->order) / size;
 
-	/*
-	 * Verify that the number of objects is within permitted limits.
-	 * The page->inuse field is only 16 bit wide! So we cannot have
-	 * more than 64k objects per slab.
-	 */
-	if (!s->objects || s->objects > MAX_OBJECTS_PER_SLAB)
-		return 0;
-	return 1;
+	return !!s->objects;
 
 }
 

Index: linux-2.6.22-rc6-mm1/include/linux/mm_types.h
===================================================================
@@ -24,10 +24,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.22-rc6-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;
 

Instead of checking for SlabDebug which requires access the page struct contents simply check the per cpu freepointer if its not NULL. It can only be not NULL if !SlabDebug.

This means we will not free to the cpu slab if the per cpu list is empty. In that case it is likely that the cpu slab is soon being retired anyways. Not freeing to an empty freelist is also required to avoid races in the cmpxchg alloc/free version.

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

Index: linux-2.6.22-rc6-mm1/mm/slub.c
===================================================================
@@ -1525,6 +1531,7 @@ new_slab:
 	}
 	return NULL;
 debug:
+	c->freelist = NULL;
 	object = c->page->freelist;
 	if (!alloc_debug_processing(s, c->page, object, addr))
 		goto another_slab;

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

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).

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. Thus 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                |  163 ++++++++++++++++++++++++++++++++++++++++++-----
 2 files changed, 155 insertions(+), 17 deletions(-)

Index: linux-2.6.22-rc6-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 */

@@ -71,7 +70,11 @@ struct kmem_cache {
 				 */
 	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.

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

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.22-rc6-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.22-rc6-mm1/mm/slub.c
===================================================================
@@ -1571,7 +1571,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;
 }

@@ -1864,8 +1864,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)

@@ -3173,12 +3174,21 @@ struct kmem_cache *kmem_cache_create(con
 	down_write(&slub_lock);
 	s = find_mergeable(size, align, flags, ctor, ops);
 	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);
 

A cmpxchg allows us to avoid disabling and enabling interrupts. The cmpxchg is optimal to allow operations on per cpu freelist even if we may be moved to other processors while getting to the cmpxchg. So we do not need to be pinned to a cpu. This may be particularly useful for the RT kernel where we currently seem to have major SLAB issues with the per cpu structures. But the constant interrupt disable / enable of slab operations also increases the performance in general.

The hard binding to per cpu structures only comes into play when we enter the slow path (__slab_alloc and __slab_free). At that point we have to disable interrupts like before.

We have a problem of determining the page struct in slab_free due the issue that the freelist pointer is the only data value that we can reliably operate on. So we need to do a virt_to_page() on the freelist. This makes it impossible to use the fastpath for a full slab and increases overhead through a second virt_to_page for each slab_free(). We really need the virtual memmap patchset to get slab_free to good performance for this one.

Pro:

- Dirty single cacheline with a single instruction in slab_alloc to accomplish allocation.
- Critical section is also a single instruction in slab_free. (but we need to write to the cacheline of the object too)

Con:
- Complex freelist management. __slab_alloc has to deal with results of race conditions.
- Recalculation of per cpu structure address is necessary in __slab_alloc since process may be rescheduled while executing in slab_alloc.

---
 mm/slub.c |   21 ++++++++++++++-------
 1 file changed, 14 insertions(+), 7 deletions(-)

Index: linux-2.6.22-rc6-mm1/mm/slub.c
===================================================================
@@ -1370,34 +1370,38 @@ static void unfreeze_slab(struct kmem_ca
 /*
  * Remove the cpu slab
  */
-static void deactivate_slab(struct kmem_cache *s, struct kmem_cache_cpu *c)
+static void deactivate_slab(struct kmem_cache *s, struct kmem_cache_cpu *c,
+			void **freelist)
 {
 	struct page *page = c->page;
+
+	c->page = NULL;
 	/*
 	 * Merge cpu freelist into freelist. Typically we get here
 	 * because both freelists are empty. So this is unlikely
 	 * to occur.
 	 */
-	while (unlikely(c->freelist)) {
+	while (unlikely(freelist)) {
 		void **object;
 
 		/* Retrieve object from cpu_freelist */
-		object = c->freelist;
-		c->freelist = c->freelist[c->offset];
+		object = freelist;
+		freelist = freelist[c->offset];
 
 		/* And put onto the regular freelist */
 		object[c->offset] = page->freelist;
 		page->freelist = object;
 		page->inuse--;
 	}
-	c->page = NULL;
 	unfreeze_slab(s, page);
 }
 
 static inline void flush_slab(struct kmem_cache *s, struct kmem_cache_cpu *c)
 {
+	void **freelist = xchg(&c->freelist, NULL);
+
 	slab_lock(c->page);
-	deactivate_slab(s, c);
+	deactivate_slab(s, c, freelist);
 }
 
 /*

@@ -1467,10 +1471,13 @@ static void *__slab_alloc(struct kmem_ca
 {
 	void **object;
 	struct page *new;
+	void **freelist = NULL;
 
 	if (!c->page)
 		goto new_slab;
 
+	freelist = xchg(&c->freelist, NULL);
+
 	slab_lock(c->page);
 	if (unlikely(!node_match(c, node)))
 		goto another_slab;

@@ -1490,7 +1497,7 @@ load_freelist:
 	return object;
 
 another_slab:
-	deactivate_slab(s, c);
+	deactivate_slab(s, c, freelist);
 
 new_slab:
 	new = get_partial(s, gfpflags, node);

Maintenance of slab allocators becomes a problem as new features for allocators are developed. The SLOB allocator in particular has been lagging behind in many ways in the past:

- Had no support for SLAB_DESTROY_BY_RCU for years (but no one noticed)

- Still has no support for slab reclaim counters. This may currently not be necessary if one would restrict the supported configurations for functionality relying on these. But even that has not been done.

The only current advantage over SLUB in terms of memory savings is through SLOBs kmalloc layout that is not power of two based like SLAB and SLUB which allows to eliminate some memory waste.

Through that SLOB has still a slight memory advantage over SLUB of ~350k in for a standard server configuration. It is likely that the savings are is smaller for real embedded configurations that have less functionality.

The density of non kmalloc slabs is superior in SLUB since SLOB has the need to keep a per object structure in a page which leads to a minimal loss of 4 bytes. If cacheline alignment is necessary then the loss may need to be greater in order to align the objects. SLUB can avoid that through a linked list and can pack objects tighly together in a page with no objects in between.

We will likely be adding new slab features soon and we can avoid maintenance of SLOB if we remove it. SLOB has customarily been neglected. It is best to remove SLOB altogether given the minimal benefit that is remaining.

That no one noticed the lack of SLAB_DESTROY_BY_RCU for the longest time indicates also that the user base is minimal.

---
 include/linux/slab.h |    6 
 init/Kconfig         |   10 
 mm/Makefile          |    1 
 mm/slob.c            |  615 ---------------------------------------------------
 4 files changed, 2 insertions(+), 630 deletions(-)

Index: linux-2.6.22-rc6-mm1/init/Kconfig
===================================================================
@@ -624,16 +624,6 @@ config SLUB
 	   of queues of objects. SLUB can use memory efficiently
 	   and has enhanced diagnostics.
 
-config SLOB
-	depends on EMBEDDED && !SPARSEMEM
-	bool "SLOB (Simple Allocator)"
-	help
-	   SLOB replaces the SLAB allocator with a drastically simpler
-	   allocator.  SLOB is more space efficient than SLAB but does not
-	   scale well (single lock for all operations) and is also highly
-	   susceptible to fragmentation. SLUB can accomplish a higher object
-	   density. It is usually better to use SLUB instead of SLOB.
-
 endchoice
 
 config PROC_SMAPS

Index: linux-2.6.22-rc6-mm1/include/linux/slab.h
===================================================================
@@ -156,8 +156,6 @@ size_t ksize(const void *);
  */
 #ifdef CONFIG_SLUB
 #include <linux/slub_def.h>
-#elif defined(CONFIG_SLOB)
-#include <linux/slob_def.h>
 #else
 #include <linux/slab_def.h>
 #endif

@@ -220,7 +218,7 @@ static inline void *kcalloc(size_t n, si
 	return __kmalloc(n * size, flags | __GFP_ZERO);
 }
 
-#if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
+#if !defined(CONFIG_NUMA)
 /**
  * kmalloc_node - allocate memory from a specific node
  * @size: how many bytes of memory are required.

@@ -248,7 +246,7 @@ static inline void *kmem_cache_alloc_nod
 {
 	return kmem_cache_alloc(cachep, flags);
 }
-#endif /* !CONFIG_NUMA && !CONFIG_SLOB */
+#endif /* !CONFIG_NUMA */
 
 /*
  * kmalloc_track_caller is a special version of kmalloc that records the

Index: linux-2.6.22-rc6-mm1/mm/Makefile
===================================================================
@@ -22,7 +22,6 @@ obj-$(CONFIG_SPARSEMEM)	+= sparse.o
 obj-$(CONFIG_SHMEM) += shmem.o
 obj-$(CONFIG_TMPFS_POSIX_ACL) += shmem_acl.o
 obj-$(CONFIG_TINY_SHMEM) += tiny-shmem.o
-obj-$(CONFIG_SLOB) += slob.o
 obj-$(CONFIG_SLAB) += slab.o
 obj-$(CONFIG_SLUB) += slub.o
 obj-$(CONFIG_MEMORY_HOTPLUG) += memory_hotplug.o

(added Matt to the Cc: list)

actually, one real advantage of the SLOB is that it is a minimal, really simple allocator. Its text and data size is so small as well.

here's the size comparison:

text data bss dec hex filename

  10788     837      16   11641    2d79 mm/slab.o
   6205    4207     124   10536    2928 mm/slub.o

1640 44 4 1688 698 mm/slob.o

slab/slub have roughly the same footprint, but slob is 10% of that size. Would be a waste to throw this away.

A year ago the -rt kernel defaulted to the SLOB for a few releases, and barring some initial scalability issues (which were solved in -rt) it worked pretty well on generic PCs, so i dont buy the 'it doesnt work' argument either.

Ingo

It likely was not frequently used on SMP, I guess.

SLOB has so far run fine without any of these, hasn't it?

Wrong. All "slabs" allocate out of the same pool of memory in SLOB, so you also wind up with less waste via _external_ fragmentation, which is espeically important on small memory machines (the kmalloc layout issue is a problem of internal fragmentation). SLOB is also smaller and simpler code as Ingo pointed out.

When I last tested, I got similar savings with a pretty stripped down kernel and a small mem= available RAM. Ie. to the point where those 350K saved were a very significant chunk of remaining free memory after init comes up.

I said exactly the same thing last time this came up. I would love to remove code if its functionality can be adequately replaced by existing code, but I think your reasons for removing SLOB aren't that good, and just handwaving away the significant memory savings doesn't work.

People run 2.6 kernels with several MB of RAM, don't they? So losing several hundred K is as bad to them as a patch that causes an Altix to waste several hundred GB is to you.

It's actually recently been made to work on SMP, it is much more scalable to large memories, and some initial NUMA work is happening that some embedded guys are interested in, all without increasing static footprint too much, and it has actually decreased dynamic footprint too.

SUSE Labs, Novell Inc.

yeah. Also, the decision here is pretty easy: the behavior of the allocator is not really visible to applications. So this isnt like having a parallel IO scheduler or a parallel process scheduler (which cause problems to us by fragmenting the application space) - so the long-term cost to us kernel maintainers should be relatively low.

cool. I was referring to something else: people were running -rt on their beefy desktop boxes with several gigs of RAM they complained about the slowdown that is caused by SLOB's linear list walking.

Steve Rostedt did two nice changes to fix those scalability problems. I've attached Steve's two patches. With these in place SLOB was very usable for large systems as well, with no measurable overhead. (obviously the lack of per-cpu caching can still be measured, but it's a lot less of a problem in practice than the linear list walking was.)

Ingo

This patch uses the mem_map pages to find the bigblock descriptor for large allocations.

-- Steve

 mm/slob.c |   74 ++++++++++++++++++++++++++++++++++----------------------------
 1 file changed, 41 insertions(+), 33 deletions(-)

Index: linux/mm/slob.c
===================================================================
@@ -49,15 +49,42 @@ typedef struct slob_block slob_t;
 struct bigblock {
 	int order;
 	void *pages;
-	struct bigblock *next;
 };
 typedef struct bigblock bigblock_t;
 
 static slob_t arena = { .next = &arena, .units = 1 };
 static slob_t *slobfree = &arena;
-static bigblock_t *bigblocks;
 static DEFINE_SPINLOCK(slob_lock);
-static DEFINE_SPINLOCK(block_lock);
+
+#define __get_slob_block(b) ((unsigned long)(b) & ~(PAGE_SIZE-1))
+
+static inline struct page *get_slob_page(const void *mem)
+{
+	void *virt = (void*)__get_slob_block(mem);
+
+	return virt_to_page(virt);
+}
+
+static inline void zero_slob_block(const void *b)
+{
+	struct page *page;
+	page = get_slob_page(b);
+	memset(&page->lru, 0, sizeof(page->lru));
+}
+
+static inline void *get_slob_block(const void *b)
+{
+	struct page *page;
+	page = get_slob_page(b);
+	return page->lru.next;
+}
+
+static inline void set_slob_block(const void *b, void *data)
+{
+	struct page *page;
+	page = get_slob_page(b);
+	page->lru.next = data;
+}
 
 static void slob_free(void *b, int size);
 static void slob_timer_cbk(void);

@@ -109,6 +136,7 @@ static void *slob_alloc(size_t size, gfp
 			if (!cur)
 				return 0;
 
+			zero_slob_block(cur);
 			slob_free(cur, PAGE_SIZE);
 			spin_lock_irqsave(&slob_lock, flags);
 			cur = slobfree;

@@ -163,7 +191,6 @@ void *__kmalloc(size_t size, gfp_t gfp)
 {
 	slob_t *m;
 	bigblock_t *bb;
-	unsigned long flags;
 
 	if (size < PAGE_SIZE - SLOB_UNIT) {
 		m = slob_alloc(size + SLOB_UNIT, gfp, 0);

@@ -178,10 +205,7 @@ void *__kmalloc(size_t size, gfp_t gfp)
 	bb->pages = (void *)__get_free_pages(gfp, bb->order);
 
 	if (bb->pages) {
-		spin_lock_irqsave(&block_lock, flags);
-		bb->next = bigblocks;
-		bigblocks = bb;
-		spin_unlock_irqrestore(&block_lock, flags);
+		set_slob_block(bb->pages, bb);
 		return bb->pages;
 	}
 

@@ -192,25 +216,16 @@ EXPORT_SYMBOL(__kmalloc);
 
 void kfree(const void *block)
 {
-	bigblock_t *bb, **last = &bigblocks;
-	unsigned long flags;
+	bigblock_t *bb;
 
 	if (!block)
 		return;
 
-	if (!((unsigned long)block & (PAGE_SIZE-1))) {
-		/* might be on the big block list */
-		spin_lock_irqsave(&block_lock, flags);
-		for (bb = bigblocks; bb; last = &bb->next, bb = bb->next) {
-			if (bb->pages == block) {
-				*last = bb->next;
-				spin_unlock_irqrestore(&block_lock, flags);
-				free_pages((unsigned long)block, bb->order);
-				slob_free(bb, sizeof(bigblock_t));
-				return;
-			}
-		}
-		spin_unlock_irqrestore(&block_lock, flags);
+	bb = get_slob_block(block);
+	if (bb) {
+		free_pages((unsigned long)block, bb->order);
+		slob_free(bb, sizeof(bigblock_t));
+		return;
 	}
 
 	slob_free((slob_t *)block - 1, 0);

@@ -222,20 +237,13 @@ EXPORT_SYMBOL(kfree);
 unsigned int ksize(const void *block)
 {
 	bigblock_t *bb;
-	unsigned long flags;
 
 	if (!block)
 		return 0;
 
-	if (!((unsigned long)block & (PAGE_SIZE-1))) {
-		spin_lock_irqsave(&block_lock, flags);
-		for (bb = bigblocks; bb; bb = bb->next)
-			if (bb->pages == block) {
-				spin_unlock_irqrestore(&slob_lock, flags);
-				return PAGE_SIZE << bb->order;
-			}
-		spin_unlock_irqrestore(&block_lock, flags);
-	}
+	bb = get_slob_block(block);
+	if (bb)
+		return PAGE_SIZE << bb->order;
 
 	return ((slob_t *)block - 1)->units * SLOB_UNIT;
 }

---
 mm/slob.c |  290 ++++++++++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 235 insertions(+), 55 deletions(-)

Yep.

That is what I meant by scalable to large memories. It is not perfect, but it is much better now. I noticed huge slowdowns too when test booting the slob RCU patch on my 4GB desktop, so I did a few things to improve freelist walking as well (the patches are in -mm, prefixed with slob-).

Afterwards, performance seems to be fairly good (obviously not as good as SLAB or SLUB on such a configuration, but definitely usable and the desktop was not noticably slower).

Thanks for sending those. One is actually obsolete because we removed bigblock list completely, however I had not seen the other one. Such an approach could be used, OTOH, having all allocations come from the same pool does have its advantages in terms of memory usage.

I don't think it has been quite decided on the next step to take with SLOB, however I have an idea that if we had per-cpu freelists (where other lists could be used as a fallback), then that would go a long way to improving the SMP scalability, CPU cache hotness, and long list walking issues all at once.

However I like the fact that there is no need for a big rush to improve it, and so patches and ideas can be brewed up slowly :)

Thanks,
Nick

SUSE Labs, Novell Inc.

ah, good - i only looked at the upstream mm/slob.c git-log. I like those 4 slob-* patches in -mm: in particular slob-remove-bigblock-tracking.patch and slob-rework-freelist-handling.patch are really elegant. Simplicity of slob does not seem to suffer either.

Ingo

I don't think a saving of a few k of text would justify slob's retention.

A reason for retaining slob would be that it has some O(n) memory saving due to better packing, etc. Indeed that was the reason for merging it in the first place. If slob no longer retains that advantage (wrt slub) then we no longer need it.

Guys, look at this the other way. Suppose we only had slub, and someone came along and said "here's a whole new allocator which saves 4.5k of text", would we merge it on that basis? Hell no, it's not worth it. What we might do is to get motivated to see if we can make slub less porky under appropriate config settings.

Let's not get sentimental about these things: in general, if there's any reasonable way in which we can rid ourselves of any code at all, we should do so, no?

Probably not.

SLOB contains several significant O(1) and also O(n) memory savings that are so far impossible-by-design for SLUB. They are: slab external fragmentation is significantly reduced; kmalloc internal fragmentation is significantly reduced; order of magnitude smaller kmem_cache data type; order of magnitude less code...

Actually with an unscientific test boot of a semi-stripped down kernel and mem=16MB, SLOB (the version in -mm) uses 400K less than SLUB (or a full 50% more RAM free after booting into bash as the init).

Now it's not for me to say that this is significant enough to make SLOB worth keeping, or what sort of results it yields in the field, so I cc'ed Denis who is the busybox maintainer, and Erik who is ulibc maintainer in case they have anything to add.

In light of Denis's recent statement I saw "In busybox project people can kill for 1.7K", there might be a mass killing of kernel developers in Cambridge this year if SLOB gets removed ;)

Joking aside, the last time this came up, I thought we concluded that removal of SLOB would be a severe regression for a significant userbase.

Definitely. And this is exactly what we said last time as well. If the small memory embedded guys are happy for SLOB to go, then I'm happy too. So, the relevant question is -- are most/all current SLOB users are now happy to switch over to SLUB, in light of the recent advances to both allocators?

SUSE Labs, Novell Inc.

Hi Nick,

I assume with "slab external fragmentation" you mean allocating a whole page for a slab when there are not enough objects to fill the whole thing thus wasting memory? We could try to combat that by packing multiple variable-sized slabs within a single page. Also, adding some non-power-of-two kmalloc caches might help with internal fragmentation.

In any case, SLUB needs some serious tuning for smaller machines before we can get rid of SLOB.

Yep. Without really analysing it, I guess SLOB's savings here are O(1) over SLUB and will relatively diminish as the machine size gets larger, however with the number of slabs even a small kernel creates, this is likely to be significant on small memory systems.

Yeah, that could help.

That too, although of course it will work against the external fragmentation problem. This is more of an O(n) problem and may not be responsible for as much waste as the first issue on small memory machines (I haven't done detailed profiling so I don't know).

I would always be happy to see the default allocator become more space efficient... I think it would be most productive to get detailed profiles of exactly where the memory is being wasted on small mem= boots. Although I don't think matching SLOB would be an easy task at all.

SUSE Labs, Novell Inc.

Hi Nick,

Running the included script on my little Debian on UML with 32 MB of RAM shows anywhere from 20 KB up to 100 KB of wasted space on light load. What's interesting is that the wasted amount seems to stabilize around 70 KB and never goes below that.

Pekka

#!/bin/bash

total_wasted=0

for i in $(find /sys/slab -type d -mindepth 1 -maxdepth 1 | sort) do
nr_objs=$(cat $i/objects)
slabs=$(cat $i/slabs)
objs_per_slab=$(cat $i/objs_per_slab)
let "max_objs=$objs_per_slab*$slabs"

object_size=$(cat $i/object_size)
let "wasted=($max_objs-$nr_objs)*$object_size"

if [ "$wasted" -ne "0" ]; then
echo "$i: max_objs=$max_objs, nr_objs=$nr_objs, $wasted bytes wasted"
fi
let "total_wasted=$total_wasted+$wasted"
done

echo "Total wasted: $total_wasted"

Hi Nick,

I would have thought so too, but my crude hack to approximate internal fragmentation says otherwise. On the same Debian on UML virtual machine I see up to 190 KB of wasted space due to internal fragmentation (average allocation size being considerably smaller than object size for cache) with the biggest offender being kmalloc-512.

But, what we really need is some real workloads on small machines using something resembling my scripts to figure out the memory profile for SLUB.

Pekka

#!/bin/bash

total_wasted=0

for i in $(find /sys/slab -type d -mindepth 1 -maxdepth 1 | sort) do
slabs=$(cat $i/slabs)
objs_per_slab=$(cat $i/objs_per_slab)
let "max_objs=$objs_per_slab*$slabs"

  object_size=$(cat $i/object_size)
  average_alloc_size=$(cat $i/average_alloc_size)

if [ "0" -ne "$average_alloc_size" ]; then
let "wasted=($object_size-$average_alloc_size)*max_objs" echo "$i: object_size=$object_size,
average_alloc_size=$average_alloc_size, $wasted bytes wasted"
let "total_wasted=$total_wasted+$wasted"
fi
done
echo "Total internal fragmentation: $total_wasted bytes"

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

Index: 2.6/include/linux/slub_def.h
===================================================================
@@ -29,6 +29,7 @@ struct kmem_cache {
 	int objsize;		/* The size of an object without meta data */
 	int offset;		/* Free pointer offset. */
 	int order;
+	int average_alloc_size;
 
 	/*
 	 * Avoid an extra cache line for UP, SMP and for the node local to

Index: 2.6/mm/slub.c
===================================================================
@@ -2238,12 +2238,22 @@ 	BUG_ON(index < 0);
 	return &kmalloc_caches[index];
 }
 
+static void update_avg(struct kmem_cache *s, size_t size)
+{
+	if (s->average_alloc_size)
+		s->average_alloc_size = (s->average_alloc_size + size) / 2;
+	else
+		s->average_alloc_size = size;
+}
+
 void *__kmalloc(size_t size, gfp_t flags)
 {
 	struct kmem_cache *s = get_slab(size, flags);
 
-	if (s)
+	if (s) {
+		update_avg(s, size);
 		return slab_alloc(s, flags, -1, __builtin_return_address(0));
+	}
 	return ZERO_SIZE_PTR;
 }
 EXPORT_SYMBOL(__kmalloc);

@@ -2253,8 +2263,11 @@ void *__kmalloc_node(size_t size, gfp_t 
 {
 	struct kmem_cache *s = get_slab(size, flags);
 
-	if (s)
+	if (s) {
+		update_avg(s, size);
 		return slab_alloc(s, flags, node, __builtin_return_address(0));
+	}
+
 	return ZERO_SIZE_PTR;
 }
 EXPORT_SYMBOL(__kmalloc_node);

@@ -2677,6 +2690,8 @@ void *__kmalloc_track_caller(size_t size
 	if (!s)
 		return ZERO_SIZE_PTR;
 
+	update_avg(s, size);
+
 	return slab_alloc(s, gfpflags, -1, caller);
 }
 

@@ -2688,6 +2703,8 @@ void *__kmalloc_node_track_caller(size_t
 	if (!s)
 		return ZERO_SIZE_PTR;
 
+	update_avg(s, size);
+
 	return slab_alloc(s, gfpflags, node, caller);
 }
 

@@ -3268,6 +3285,12 @@ static ssize_t objects_show(struct kmem_
 }
 SLAB_ATTR_RO(objects);
 
+static ssize_t average_alloc_size_show(struct kmem_cache *s, char *buf)
+{
+	return sprintf(buf, "%d\n", s->average_alloc_size);
+}
+SLAB_ATTR_RO(average_alloc_size);
+
 static ssize_t sanity_checks_show(struct kmem_cache *s, char *buf)
 {
 	return sprintf(buf, "%d\n", !!(s->flags & SLAB_DEBUG_FREE));

@@ -3466,6 +3489,7 @@ static struct attribute * slab_attrs[] =
 	&order_attr.attr,
 	&objects_attr.attr,
 	&slabs_attr.attr,
+	&average_alloc_size_attr.attr,
 	&partial_attr.attr,
 	&cpu_slabs_attr.attr,
 	&ctor_attr.attr,

Ther are already non-power-of-two kmalloc caches for 96 and 192 bytes sizes.

Switch off CONFIG_SLUB_DEBUG to get memory savings.

--
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>

Hi Christoph,

I know that, but for my setup at least, there seems to be a need for a non-power of two cache between 512 and 1024. What I am seeing is average allocation size for kmalloc-512 being around 270-280 which wastes total of 10 KB of memory due to internal fragmentation. Might be a buggy caller that can be fixed with its own cache too.

Curious, /proc/meminfo immediately after boot shows:

SLUB (debugging enabled):

(none):~# cat /proc/meminfo 
MemTotal:        30260 kB
MemFree:         22096 kB

SLUB (debugging disabled):

(none):~# cat /proc/meminfo 
MemTotal:        30276 kB
MemFree:         22244 kB

SLOB:

(none):~# cat /proc/meminfo 
MemTotal:        30280 kB
MemFree:         22004 kB

That's 92 KB advantage for SLUB with debugging enabled and 240 KB when debugging is disabled.

Nick, Matt, care to retest SLUB and SLOB for your setups?

Pekka

--
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>

Interesting. What kernel version are you using?

I don't think there has been a significant change in the area of memory efficiency in either since I last tested, and Christoph and I both produced the same result.

I can't say where SLOB is losing its memory, but there are a few places that can still be improved, so I might get keen and take another look at it once all the improvements to both allocators gets upstream.

SUSE Labs, Novell Inc.

--
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>

Hi Nick,

Linus' git head from yesterday so the results are likely to be sensitive to workload and mine doesn't represent real embedded use.

--
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>

Hi Pekka,

There is one thing that the SLOB patches in -mm do besides result in slightly better packing and memory efficiency (which might be unlikely to explain the difference you are seeing), and that is that they do away with the delayed freeing of unused SLOB pages back to the page allocator.

In git head, these pages are freed via a timer so they can take a while to make their way back to the buddy allocator so they don't register as free memory as such.

Anyway, I would be very interested to see any situation where the SLOB in -mm uses more memory than SLUB, even on test configs like yours.

Thanks,
Nick

SUSE Labs, Novell Inc.

--
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>

Using 2.6.22-rc6-mm1 with a 64MB lguest and busybox, I'm seeing the following as the best MemFree numbers after several boots each:

SLAB: 54796
SLOB: 55044
SLUB: 53944
SLUB: 54788 (debug turned off)

These numbers bounce around a lot more from boot to boot than I remember, so take these numbers with a grain of salt.

Disabling the debug code in the build gives this, by the way:

mm/slub.c: In function a??init_kmem_cache_nodea??:
mm/slub.c:1873: error: a??struct kmem_cache_nodea?? has no member named a??fulla??

Mathematics is the supreme nostalgia of our time.

--
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>

Hi Matt,

To rule out userland, 2.6.22 with 32 MB defconfig UML and busybox [1] on i386:

SLOB: 26708
SLUB: 27212 (no debug)

Unfortunately UML is broken in 2.6.22-rc6-mm1, so I don't know if SLOB patches help there.

1. http://uml.nagafix.co.uk/BusyBox-1.5.0/BusyBox-1.5.0-x86-root_fs.bz2

Pekka

--
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>

That was without "slub_debug" as a parameter or with !CONFIG_SLUB_DEBUG?

Data size and code size will decrease if you compile with !CONFIG_SLUB_DEBUG. slub_debug on the command line governs if debug information is used.

A fix for that is in Andrew's tree.

Without the parameter, as the other way doesn't compile in -mm1.

Mathematics is the supreme nostalgia of our time.

--
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>

here is the patch that went into mm after mm1 was released.

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

Index: linux-2.6.22-rc6-mm1/mm/slub.c
===================================================================
@@ -1868,7 +1868,9 @@ static void init_kmem_cache_node(struct 
 	atomic_long_set(&n->nr_slabs, 0);
 	spin_lock_init(&n->list_lock);
 	INIT_LIST_HEAD(&n->partial);
+#ifdef CONFIG_SLUB_DEBUG
 	INIT_LIST_HEAD(&n->full);
+#endif
 }
 
 #ifdef CONFIG_NUMA

@@ -1898,8 +1900,10 @@ static struct kmem_cache_node * __init e
 	page->freelist = get_freepointer(kmalloc_caches, n);
 	page->inuse++;
 	kmalloc_caches->node[node] = n;
+#ifdef CONFIG_SLUB_DEBUG
 	init_object(kmalloc_caches, n, 1);
 	init_tracking(kmalloc_caches, n);
+#endif
 	init_kmem_cache_node(n);
 	atomic_long_inc(&n->nr_slabs);
 	add_partial(n, page);

--
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>

Well that is only true for kmalloc objects < PAGE_SIZE and to some extend offset by the need to keep per object data in SLUB. But yes the power of two caches are a necessary design feature of SLAB/SLUB that allows O(1) operations of kmalloc slabs which in turns causes memory wastage because of rounding of the alloc to the next power of two. SLUB has less wastage there than SLAB since it can fit power of two object tightly into a slab instead of having to place additional control information there like SLAB.

O(n) memory savings? What is that?

I've frequently wondered why we don't just create more caches for kmalloc:
make it denser than each-power-of-2-plus-a-few-others-in-between.

I assume the tradeoff here is better packing versus having a ridiculous number of caches. Is there any other cost?

Because even having 1024 caches wouldn't consume a terrible amount of memory and I bet it would result in aggregate savings.

Of course, a scheme which creates kmalloc caches on-demand would be better, but that would kill our compile-time cache selection, I suspect.

I have tried any number of approaches without too much success. Even one slab cache for every 8 bytes. This creates additional admin overhead through more control structure (that is pretty minimal but nevertheless exists)

The main issue is that kmallocs of different size must use different pages. If one allocates one 64 byte item and one 256 byte item and both 64 byte and 256 byte are empty then SLAB/SLUB will have to allocate 2 pages. SLUB can fit them into one. This is basically only relevant early after boot. The advantage goes away as the system starts to work and as more objects are allocated in the slabs but the power-of-two slab will always have to extend its size in page size chunks which leads to some overhead that SLOB can avoid by placing entities of multiple size in one slab. The tradeoff in SLOB is that is cannot be an O(1) allocator because it has to manage these variable sized objects by traversing the lists.

I think the advantage that SLOB generates here is pretty minimal and is easily offset by the problems of maintaining SLOB.

SLUB creates kmalloc caches on-demand for DMA caches already. But then we are not allowing compile time cache selection for DMA caches.

Sure. But I wasn't proposing this as a way to make slub cover slob's advantage. I was wondering what effect it would have on a more typical medium to large sized system.

Not much, really: if any particular subsystem is using a "lot" of slab memory then it should create its own cache rather than using kmalloc anyway, so forget it ;)

I don't get it. Have you got agreement from the small memory people that the advantages of SLOB are pretty minimal, or did you just decide that? If the latter, did you completely miss reading my email? What happens to the people who jump through hoops to save 1 or 2 K?

I don't see any problems with maintaining SLOB. It is simple enough that I was able to write a userspace test harness for it and hack away at it after reading the code the first time for half an hour or so. It is nothing even slightly comparable to the problems of SLAB, for example. And you don't have to maintain it at all anyway!

I like removing code as much as the next person, but I don't understand why you are so intent on removing SLOB and willing to dismiss its advantages so quickly.

SUSE Labs, Novell Inc.

I have to maintain it because I have to keep the slab APIs consistent (recently I added GFP_ZERO support and had to provide shims for slab defreag). It is not in a good state as described in the patch and has a history of not being maintained properly. Everyone that modifies the behavior of the slab allocator has to do something to avoid breaking SLOB. Its certainly fun to hack on but is that a criterion for keeping it in the tree?

Quickly? We have considered this for months now.

Pretty standard fare that when you add something or change APIs, most of the burden is on you to not break the kernel. I'd love nothing better than to remove all but about 3 filesystems :)

It is reasonable to expect some help from maintainers, but I notice you didn't even CC the SLOB maintainer in the patch to remove SLOB! So maybe if you tried working a bit closer with him you could get better results?

Quickly -- as in you quickly sweep the savings of 100s of K under the rug and just declare that it is insignificant :)

SUSE Labs, Novell Inc.

The maintainers last patch to SLOB was the initial submission of the allocator. Then he acked subsequent patches. Most of the modifications to SLOB are my work. Attempts to talk to the maintainer result in inventive explanations why SLOB does not have to conform to kernel standards. There is no reasonable expectation that this will change.

Well I really don't want to mediate, but even in the case of a completely MIA maintainer, that isn't really a good idea to throw out working and useful code.

But last time this discussion came up, IIRC you ended up handwaving about all the ways in which SLOB was broken but didn't actually come up with any real problems. Matt seemed willing to add those counters or whatever it was if/when doing so solved a real problem. And remember that SLOB doesn't have to have feature parity with SLUB, so long as it implements the slab API such that the kernel *works*.

SUSE Labs, Novell Inc.

No it does not have to have feature parity. And yes we identified areas in which SLOB may cause problems due to not implementing things (f.e. suspend resume). The counters are still missing and thus core development cannot rely on those being there.

Please remind me what these things are. Suspend and hibernate work fine here.

None of the VM makes real use of the SLAB counters. Nor will they ever make real use of them because the counters are not usefully defined. In other words, reclaimable is a lie. If SLAB claims there's 1M of reclaimable memory, the actual amount may more often than not be zero because we already tried to shrink the SLAB.

As I've said before, if you come up with a real use for these numbers, I will sacrifice the appropriate number of puppies to support it in SLOB. But I'd rather not crush any puppies here prematurely.

Mathematics is the supreme nostalgia of our time.

You're delusional.

http://www.kernel.org/hg/linux-2.6/annotate/tip/mm/slob.c

A grand total of 15 lines accounted to you, all of which are completely trivial. Most of them are turning no-op macros into no-op but non-inline functions. Not an improvement. Reverting that now on my todo list, thanks for drawing my attention to it. The remainder is just churn from your SLUB work.

While you're at it, note the lines from Dimitri, quickly fixing the breakage you introduced.

Count many more lines from Nick, Pekka, and Akinobu making useful changes. And note that all three of the real bugs fixed were fairly hard to hit. It's unlikely that anyone would have ever hit the RCU bug. The find_order bug only hit allocations of unlikely sizes like 8193 bytes. And SLAB_PANIC triggering is fairly unheard of, and simply makes the kernel crash slightly sooner anyway.

The only remaining known bug is arguably a problem in nommu that SLOB shouldn't be papering over.

That's pretty damn stable compared to the other allocators in the kernel.

Um.. would those be the same kernel standards you pulled out of your ass to argue SLOB shouldn't exist?

Mathematics is the supreme nostalgia of our time.

I've got another one for you: SLOB ignores ARCH_KMALLOC_MINALIGN so using SLOB in combination with DMA and non-coherent architectures causes data corruption.

That said, there are currently very few architectures that define ARCH_KMALLOC_MINALIGN, so I guess it might be something I'm doing wrong on avr32. But I'd really like to know how other non-coherent architectures handle DMA to buffers sharing cachelines with unrelated data...

Håvard

Should be fixed in mm, I believe: slob-improved-alignment-handling.patch

SUSE Labs, Novell Inc.

Indeed. Thanks, I'll give it a try later today.

Håvard

Git log says otherwise:

git log --pretty=short mm/slob.c

Author: Christoph Lameter <[email protected]>
Remove SLAB_CTOR_CONSTRUCTOR
Author: Christoph Lameter <[email protected]>
Slab allocators: Drop support for destructors
Author: Nick Piggin <[email protected]>
slob: implement RCU freeing
Author: Akinobu Mita <[email protected]>
slob: fix page order calculation on not 4KB page
Author: Christoph Lameter <[email protected]>
slab allocators: Remove obsolete SLAB_MUST_HWCACHE_ALIGN
Author: Akinobu Mita <[email protected]>
slob: handle SLAB_PANIC flag
Author: Pekka Enberg <[email protected]>
slab: introduce krealloc
Author: Dimitri Gorokhovik <[email protected]>
[PATCH] MM: SLOB is broken by recent cleanup of slab.h
Author: Christoph Lameter <[email protected]>
[PATCH] More slab.h cleanups
Author: Christoph Lameter <[email protected]>
[PATCH] Cleanup slab headers / API to allow easy addition of new slab allocators
Author: Alexey Dobriyan <[email protected]>
[PATCH] Make kmem_cache_destroy() return void
Author: Christoph Lameter <[email protected]>
[PATCH] ZVC: Support NR_SLAB_RECLAIMABLE / NR_SLAB_UNRECLAIMABLE
Author: Christoph Lameter <[email protected]>
[PATCH] Extract the allocpercpu functions from the slab allocator
Author: Jörn Engel <[email protected]>
Remove obsolete #include <linux/config.h>
Author: John Hawkes <[email protected]>
[PATCH] mm/slob.c: for_each_possible_cpu(), not NR_CPUS
Author: Pekka Enberg <[email protected]>
[PATCH] slab: introduce kmem_cache_zalloc allocator
Author: Ingo Molnar <[email protected]>

    [PATCH] SLOB=y && SMP=y fix

Author: Matt Mackall <[email protected]>
[PATCH] slob: introduce the SLOB allocator

A dozen trivial cleanups do not make you maintainer. Otherwise we'd all be sending our patches to Adrian rather than Linus.

Mathematics is the supreme nostalgia of our time.

Of course you are the maintainer but you only authored a single patch which was the original submission in all the time that SLOB was in the tree. I keep having to clean up the allocator that has--according to Pekka--more memory requirements than SLUB. There is no point in keeping it around anymore it seems.

Hi Christoph,

Well, it was a test setup with UML and busybox and didn't have all the SLOB optimizations Nick mentioned, so we shouldn't draw any definite conclusions from it. I couldn't get 2.6.22-rc6-mm1 to compile so I'll try again after Andrew pushes a new release out.

Furthermore, as much as I would like to see SLOB nuked too, we can't do that until Matt and Nick are satisfied with SLUB for small devices and what I can gather, they aren't.

Pekka

But you did get 2.6.22 to compile it seems.

Here is the fix against 2.6.22-rc6-mm1 again.

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

Index: linux-2.6.22-rc6-mm1/mm/slub.c
===================================================================
@@ -1868,7 +1868,9 @@ static void init_kmem_cache_node(struct 
 	atomic_long_set(&n->nr_slabs, 0);
 	spin_lock_init(&n->list_lock);
 	INIT_LIST_HEAD(&n->partial);
+#ifdef CONFIG_SLUB_DEBUG
 	INIT_LIST_HEAD(&n->full);
+#endif
 }
 
 #ifdef CONFIG_NUMA

@@ -1898,8 +1900,10 @@ static struct kmem_cache_node * __init e
 	page->freelist = get_freepointer(kmalloc_caches, n);
 	page->inuse++;
 	kmalloc_caches->node[node] = n;
+#ifdef CONFIG_SLUB_DEBUG
 	init_object(kmalloc_caches, n, 1);
 	init_tracking(kmalloc_caches, n);
+#endif
 	init_kmem_cache_node(n);
 	atomic_long_inc(&n->nr_slabs);
 	add_partial(n, page);

I didn't get so far to compile with SLUB. There's some UML architecture problem and SLOB missing __kmalloc which UML also needs.

Pekka

Just to be clear: I do really like SLUB of course. And if that was able to get as good or nearly as good (for appropriate values of nearly) memory efficiency as SLOB in relevant situations, that would be fantastic and SLOB could go away.

I don't really have a good knowledge of small memory devices being used, other than apparently they can boot with 2MB (maybe less with nommu?). So even a few K could be very significant for these.

SUSE Labs, Novell Inc.

It magnifies the fragmentation problem.

SLAB (and SLUB) makes the optimistic assumption that objects of the same type/size have similar lifetimes. But for some objects, it's not uncommon to do many temporary allocations but have some objects with indefinite lifespans. dcache is a very frequently encountered example, but there's no reason we couldn't see it with sockets and many other object types.

Every new arena introduces further opportunity for this sort of fragmentation. If we had, say, separate pools for 48 byte and 64 byte objects, an unfortunate usage pattern for 48-byte kmallocs could DoS requests for 64 byte objects that would work just fine if they both came out of the same pool. If we have 10 pools with long-lived objects, we're much worse off than if we had 1 or 2.

Mathematics is the supreme nostalgia of our time.

OK but we're talking about SLOB. And the number that matters is the amount of memory used, which is higher with SLUB than with SLOB in our tests.

Allocate n things and your memory waste is proportional to n (well that's O(n) waste, so I guess by savings I mean that SLOB's memory saving compared to SLUB are proportional to n).

SUSE Labs, Novell Inc.

n is the size of the object?

Its linear correlated to the object size. It does not grow exponentially as object size grows. Waste in the kmalloc array in the worst case is < objsize.

n things -- n number of things (n calls to kmem_cache_alloc()).

Just a fancy way of saying roughly that memory waste will increase as the size of the system increases. But that aspect of it I think is not really a problem for non-tiny systems anyway because the waste tends not to be too bad (and possibly the number of active allocations does not increase O(n) with the size of RAM either).

SUSE Labs, Novell Inc.

If active allocations doesn't increase O(n) with the size of RAM, what's all that RAM for?

If your memory isn't getting used for large VMAs or large amounts of page cache, that means it's getting used by task structs, radix_tree_nodes, sockets, dentries, inodes, etc.

Mathematics is the supreme nostalgia of our time.

Yeah you could be right. Actually you most likey _are_ right for many workloads.

SUSE Labs, Novell Inc.

N is the number of objects.

So, for large N, the overhead of SLUB of allocations of size m, where m % alignment == 0 (for simplicity):

kmem_cache_alloc case:

(PAGE_SIZE % m) / m

kmalloc case:

nextpowerof2(m) - m

And for SLOB (with Nick's improvements):

kmem_cache_alloc case:

0 (the remainder of the page is usable for other allocs)

kmalloc case:

2 bytes (or whatever the minimal arch alignment is)

SLUB wins by two bytes on kmallocs that happen to be a power of two, ties on kmem_cache_allocs that happen to evenly divide PAGE_SIZE and kmallocs 2 bytes smaller than a power of 2, and loses everywhere else.

It also loses whenever a particular type/size has both short-lived and long-lived objects because of pinning. This effect is worse on small machines as it's easier to pin all of memory.

The downsides of current SLOB are:

- single lock
- potentially long walks to find free blocks

The average case walk has been shortened quite a bit by Nick's patches. The combinatorics here are enough to make Knuth hand-wave, but we can in theory get close to O(1) performance when we don't have much memory pressure. Needs some serious benchmarking. When we DO have memory pressure, both SLOB and SLUB will degrade to forcing the kernel to walk a bunch of pages.

Mathematics is the supreme nostalgia of our time.

Well I think we would obviously throw out SLAB and SLUB if they weren't somewhat faster than SLOB. They're much more problematic and one of the big features that Christoph's pushing is a fix for a problem that SLOB simply doesn't have: huge numbers of SLAB/SLUB pages being held down by small numbers of objects.

I keep suggesting a Voyager Replacement Fund, but James isn't interested.

But seriously, I don't think it should be at all surprising that the allocator that's most appropriate for machines with < 32MB of RAM is different than the one for machines with > 1TB of RAM.

The maintenance overhead of SLOB is fairly minimal. The biggest outstanding SLOB problem is nommu's rather broken memory size reporting.

Mathematics is the supreme nostalgia of our time.

Last time I tried it, I cannot mount (or mount very slowly) jffs2 flash with slob.
Changing slob to slab fix the issue.

Matthieu

The last of my tests showed that SLOB is at about 50% of the size of SLUB. You need to compile SLUB in embedded mode with !CONFIG_SLUB_DEBUG to get a reduce code size.

First, WTF wasn't I cc:ed on this? Are you actually trying to me make me fuming mad?

We've been over this 50 times. The target users were never affected. And it's fixed. So why the HELL are you mentioning this again?

We've been over this 50 times. Last time around, I inspected all the code paths and demonstrated that despite your handwaving, IT DIDN'T MATTER.

Sometimes I do not think there is a cluebat large enough for you. 350K is FREAKING HUGE on a cell phone. That's most of a kernel!

Mathematics is the supreme nostalgia of our time.

The SLAB functionality has been supplanted by SLUB. Benefits of SLUB

- More compact data store. Less cache footprint
- Reporting function and tools
- Higher speed
- Eliminate SLAB bitrot

---
 fs/proc/proc_misc.c  |   47 
 include/linux/slab.h |   18 
 init/Kconfig         |   26 
 lib/Kconfig.debug    |   17 
 mm/Makefile          |    4 
 mm/slab.c            | 4448 ---------------------------------------------------
 6 files changed, 2 insertions(+), 4558 deletions(-)

Index: linux-2.6.22-rc6-mm1/include/linux/slab.h
===================================================================
@@ -16,7 +16,6 @@
 
 /*
  * Flags to pass to kmem_cache_create().
- * The ones marked DEBUG are only valid if CONFIG_SLAB_DEBUG is set.
  */
 #define SLAB_DEBUG_FREE		0x00000100UL	/* DEBUG: Perform (expensive) checks on free */
 #define SLAB_RED_ZONE		0x00000400UL	/* DEBUG: Red zone objs in a cache */

@@ -154,11 +153,7 @@ size_t ksize(const void *);
  * See each allocator definition file for additional comments and
  * implementation notes.
  */
-#ifdef CONFIG_SLUB
 #include <linux/slub_def.h>
-#else
-#include <linux/slab_def.h>
-#endif
 
 /**
  * kcalloc - allocate memory for an array. The memory is set to zero.

@@ -256,14 +251,9 @@ static inline void *kmem_cache_alloc_nod
  * allocator where we care about the real place the memory allocation
  * request comes from.
  */
-#if defined(CONFIG_DEBUG_SLAB) || defined(CONFIG_SLUB)
 extern void *__kmalloc_track_caller(size_t, gfp_t, void*);
 #define kmalloc_track_caller(size, flags) \
 	__kmalloc_track_caller(size, flags, __builtin_return_address(0))
-#else
-#define kmalloc_track_caller(size, flags) \
-	__kmalloc(size, flags)
-#endif /* DEBUG_SLAB */
 
 #ifdef CONFIG_NUMA
 /*

@@ -274,22 +264,16 @@ extern void *__kmalloc_track_caller(size
  * standard allocator where we care about the real place the memory
  * allocation request comes from.
  */
-#if defined(CONFIG_DEBUG_SLAB) || defined(CONFIG_SLUB)
 extern void *__kmalloc_node_track_caller(size_t, gfp_t, int, void *);
 #define kmalloc_node_track_caller(size, flags, node) \
 	__kmalloc_node_track_caller(size, flags, node, \
 			__builtin_return_address(0))
-#else
-#define kmalloc_node_track_caller(size, flags, node) \
-	__kmalloc_node(size, flags, node)
-#endif
-
 #else /* CONFIG_NUMA */
 
 #define kmalloc_node_track_caller(size, flags, node) \
 	kmalloc_track_caller(size, flags)
 
-#endif /* DEBUG_SLAB */
+#endif /* CONFIG_NUMA */
 
 /*
  * Shortcuts

Index: linux-2.6.22-rc6-mm1/init/Kconfig
===================================================================
@@ -594,38 +594,12 @@ config VM_EVENT_COUNTERS
 config SLUB_DEBUG
 	default y
 	bool "Enable SLUB debugging support" if EMBEDDED
-	depends on SLUB
 	help
 	  SLUB has extensive debug support features. Disabling these can
 	  result in significant savings in code size. This also disables
 	  SLUB sysfs support. /sys/slab will not exist and there will be
 	  no support for cache validation etc.
 
-choice
-	prompt "Choose SLAB allocator"
-	default SLUB
-	help
-	   This option allows to select a slab allocator.
-
-config SLAB
-	bool "SLAB"
-	help
-	  The regular slab allocator that is established and known to work
-	  well in all environments. It organizes cache hot objects in
-	  per cpu and per node queues. SLAB is the default choice for
-	  a slab allocator.
-
-config SLUB
-	bool "SLUB (Unqueued Allocator)"
-	help
-	   SLUB is a slab allocator that minimizes cache line usage
-	   instead of managing queues of cached objects (SLAB approach).
-	   Per cpu caching is realized using slabs of objects instead
-	   of queues of objects. SLUB can use memory efficiently
-	   and has enhanced diagnostics.
-
-endchoice
-
 config PROC_SMAPS
 	default y
 	bool "Enable /proc/pid/smaps support" if EMBEDDED && PROC_FS && MMU

Index: linux-2.6.22-rc6-mm1/mm/Makefile
===================================================================
@@ -11,7 +11,7 @@ obj-y			:= bootmem.o filemap.o mempool.o
 			   page_alloc.o page-writeback.o pdflush.o \
 			   readahead.o swap.o truncate.o vmscan.o \
 			   prio_tree.o util.o mmzone.o vmstat.o backing-dev.o \
-			   $(mmu-y)
+			   slub.o $(mmu-y)
 
 obj-$(CONFIG_BOUNCE)	+= bounce.o
 obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o thrash.o

@@ -22,8 +22,6 @@ obj-$(CONFIG_SPARSEMEM)	+= sparse.o
 obj-$(CONFIG_SHMEM) += shmem.o
 obj-$(CONFIG_TMPFS_POSIX_ACL) += shmem_acl.o
 obj-$(CONFIG_TINY_SHMEM) += tiny-shmem.o
-obj-$(CONFIG_SLAB) += slab.o
-obj-$(CONFIG_SLUB) += slub.o
 obj-$(CONFIG_MEMORY_HOTPLUG) += memory_hotplug.o
 obj-$(CONFIG_FS_XIP) += filemap_xip.o
 obj-$(CONFIG_MIGRATION) += migrate.o

Index: linux-2.6.22-rc6-mm1/lib/Kconfig.debug
===================================================================

Part of the diff is not shown here. View the raw message.

From: Christoph Lameter <[email protected]>
Date: Sat, 07 Jul 2007 20:49:52 -0700

This is cpu dependant, and in fact not true at all on Niagara and several of the cpus in the UltraSPARC family.

Hmmm... So have alternate aloc/free paths depending on the cpu?

From: Christoph Lameter <[email protected]>
Date: Mon, 9 Jul 2007 08:45:42 -0700 (PDT)

As Andi seemed to imply I don't even think cmpxchg is faster than interrupt enable/disable on current generation AMD x86_64 chips, so are you targetting this optimization solely at Intel x86 Core Duo 32-bit chips? That's the only one I can see which will benefit from this. Are you going to probe the cpu sub-type and patch SLUB?

I really don't think this optimization is wise as even if you could decide at build time, it's going to be a maintainence and debugging nightmare to have to field bug reports given two different locking schemes.

Please reconsider this change, thanks.

Not sure. The numbers I have seen in the papers indicate a potential speedup by a factor of 10 on x86 hardware. I have not done any benchmarking myself yet.

This is an RFC after all so nothing is fixed yet. Certainly I will keep this in mind.

That sounds wrong.

-Andi

Martin Bligh was able to significantly increase his LTTng performance by using cmpxchg. See his article in the 2007 proceedings of the OLS Volume 1, page 39.

His numbers were:

interrupts enable disable : 210.6ns
local cmpxchg : 9.0ns

--
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>

Those numbers came from Mathieu Desnoyers (LTTng) if you want more details.

--
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>

Okay the source for these numbers is in his paper for the OLS 2006: Volume 1 page 208-209? I do not see the exact number that you referred to there.

He seems to be comparing spinlock acquire / release vs. cmpxchg. So I guess you got your material from somewhere else?

Also the cmpxchg used there is the lockless variant. cmpxchg 29 cycles w/o lock prefix and 112 with lock prefix.

I see you reference another paper by Desnoyers:
http://tree.celinuxforum.org/CelfPubWiki/ELC2006Presentations?action=AttachFile&do=get&target=celf2006-desnoyers.pdf

I do not see anything relevant there. Where did those numbers come from?

The lockless cmpxchg is certainly an interesting idea. Certain for some platforms I could disable preempt and then do a lockless cmpxchg.

--
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>

Nope, he was a direct co-author on the paper, was
working here, and measured it.

Matheiu, can you give some more details? Obviously the exact numbers will vary by archicture, machine size, etc, but it's a good point for discussion.

M.

--
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>

Hi,

Hrm, the reference page number is wrong: it is in OLS 2006, Vol. 1 page 216 (section 4.5.2 Scalability). I originally pulled out the page number from my local paper copy. oops.

I ran a test specifically for this paper where I got this result comparing the local irq enable/disable to local cmpxchg.

Yep, I volountarily used the variant without lock prefix because the data is per cpu and I disable preemption.

Yes, preempt disabling or, eventually, the new thread migration disabling I just proposed as an RFC on LKML. (that would make -rt people happier)

Sure, also note that the UP cmpxchg (see asm-$ARCH/local.h in 2.6.22) is faster on architectures like powerpc and MIPS where it is possible to remove some memory barriers.

See 2.6.22 Documentation/local_ops.txt for a thorough discussion. Don't hesitate ping me if you have more questions.

Regards,

Mathieu

Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

--
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>

4.5.2 is on page 208 in my copy of the proceedings.

The numbers are pretty important and suggest that we can obtain a significant speed increase by avoid local irq disable enable in the slab allocator fast paths. Do you some more numbers? Any other publication that mentions these?

local_cmpxchg generates this?

Right.

UP cmpxchg meaning local_cmpxchg?

That is pretty thin and does not mention atomic_cmpxchg. You way want to expand on your ideas a bit.

--
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>

The original publication in which I released the idea was my LTTng paper at OLS 2006. Outside this, I have not found other paper that talks about this idea.

The test code is basically just disabling interrupts, reading the TSC at the beginning and end and does 20000 loops of local_cmpxchg. I can send you the code if you want it.

Yes.

Yes.

Sure, the idea goes as follow: if you have a per cpu variable that needs to be concurrently modified in a coherent manner by any context (NMI, irq, bh, process) running on the given CPU, you only need to use an operation atomic wrt to the given CPU. You just have to make sure that only this CPU will modify the variable (therefore, you must disable preemption around modification) and you have to make sure that the read-side, which can come from any CPU, is accessing this variable atomically. Also, you have to be aware that the read-side might see an older version of the other cpu's value because there is no SMP write memory barrier involved. The value, however, will always be up to date if the variable is read from the "local" CPU.

What applies to local_inc, given as example in the local_ops.txt document, applies integrally to local_cmpxchg. And I would say that local_cmpxchg is by far the cheapest locking mechanism I have found, and use today, for my kernel tracer. The idea emerged from my need to trace every execution context, including NMIs, while still providing good performances. local_cmpxchg was the perfect fit; that's why I deployed it in local.h in each and every architecture.

Mathieu

Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

--
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>

Does not work here. If I use

static void __always_inline *slab_alloc(struct kmem_cache *s,
gfp_t gfpflags, int node, void *addr)

{
        void **object;
        struct kmem_cache_cpu *c;

        preempt_disable();
        c = get_cpu_slab(s, smp_processor_id());
redo:
        object = c->freelist;
        if (unlikely(!object || !node_match(c, node)))
                return __slab_alloc(s, gfpflags, node, addr, c);

        if (cmpxchg_local(&c->freelist, object, object[c->offset]) != object)
                goto redo;

        preempt_enable();
        if (unlikely((gfpflags & __GFP_ZERO)))
                memset(object, 0, c->objsize);

        return object;
}

Then the code will include a lock prefix:

    3270:       48 8b 1a                mov    (%rdx),%rbx
    3273:       48 85 db                test   %rbx,%rbx
    3276:       74 23                   je     329b <kmem_cache_alloc+0x4b>
    3278:       8b 42 14                mov    0x14(%rdx),%eax
    327b:       4c 8b 0c c3             mov    (%rbx,%rax,8),%r9
    327f:       48 89 d8                mov    %rbx,%rax
    3282:       f0 4c 0f b1 0a          lock cmpxchg %r9,(%rdx)
    3287:       48 39 c3                cmp    %rax,%rbx
    328a:       75 e4                   jne    3270 <kmem_cache_alloc+0x20>
    328c:       66 85 f6                test   %si,%si
    328f:       78 19                   js     32aa <kmem_cache_alloc+0x5a>
    3291:       48 89 d8                mov    %rbx,%rax
    3294:       48 83 c4 08             add    $0x8,%rsp
    3298:       5b                      pop    %rbx
    3299:       c9                      leaveq
    329a:       c3                      retq

Great idea. The SLUB allocator may be able to use your idea to improve both the alloc and free path.

--
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>

You are completely right: on x86_64, a bit got lost in the move to cmpxchg.h, here is the fix. It applies on 2.6.22-rc6-mm1.

x86_64 - Use non locked version for local_cmpxchg()

local_cmpxchg() should not use any LOCK prefix. This change probably got lost in the move to cmpxchg.h.

---
 include/asm-x86_64/cmpxchg.h |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Index: linux-2.6-lttng/include/asm-x86_64/cmpxchg.h
===================================================================
@@ -128,7 +128,7 @@
 	((__typeof__(*(ptr)))__cmpxchg((ptr),(unsigned long)(o),\
 					(unsigned long)(n),sizeof(*(ptr))))
 #define cmpxchg_local(ptr,o,n)\
-	((__typeof__(*(ptr)))__cmpxchg((ptr),(unsigned long)(o),\
+	((__typeof__(*(ptr)))__cmpxchg_local((ptr),(unsigned long)(o),\
 					(unsigned long)(n),sizeof(*(ptr))))
 
 #endif

Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

--
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>

A trival fix. Make sure that it gets merged soon.

--
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>

Ok here is a replacement patch for the cmpxchg patch. Problems

1. cmpxchg_local is not available on all arches. If we wanted to do this then it needs to be universally available.

2. cmpxchg_local does generate the "lock" prefix. It should not do that. Without fixes to cmpxchg_local we cannot expect maximum performance.

3. The approach is x86 centric. It relies on a cmpxchg that does not synchronize with memory used by other cpus and therefore is more lightweight. As far as I know the IA64 cmpxchg cannot do that. Neither several other processors. I am not sure how cmpxchgless platforms would use that. We need a detailed comparison of interrupt enable /disable vs. cmpxchg cycle counts for cachelines in the cpu cache to evaluate the impact that such a change would have.

The cmpxchg (or its emulation) does not need any barriers since the accesses can only come from a single processor.

Mathieu measured a significant performance benefit coming from not using interrupt enable / disable.

Some rough processor cycle counts (anyone have better numbers?)

STI CLI CMPXCHG
IA32 36 26 1 (assume XCHG == CMPXCHG, sti/cli also need stack pushes/pulls)
IA64 12 12 1 (but ar.ccv needs 11 cycles to set comparator,
need register moves to preserve processors flags)

Looks like STI/CLI is pretty expensive and it seems that we may be able to optimize the alloc / free hotpath quite a bit if we could drop the interrupt enable / disable. But we need some measurements.

Draft of a new patch:

SLUB: Single atomic instruction alloc/free using cmpxchg_local

A cmpxchg allows us to avoid disabling and enabling interrupts. The cmpxchg is optimal to allow operations on per cpu freelist. We can stay on one processor by disabling preemption() and allowing concurrent interrupts thus avoiding the overhead of disabling and enabling interrupts.

Pro:
- No need to disable interrupts.
- Preempt disable /enable vanishes on non preempt kernels
Con:
- Slightly complexer handling.
- Updates to atomic instructions needed

---
 mm/slub.c |   72 ++++++++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 49 insertions(+), 23 deletions(-)

Index: linux-2.6.22-rc6-mm1/mm/slub.c
===================================================================
@@ -1467,12 +1467,14 @@ static void *__slab_alloc(struct kmem_ca
 {
 	void **object;
 	struct page *new;
+	unsigned long flags;
 
+	local_irq_save(flags);
 	if (!c->page)
 		goto new_slab;
 
 	slab_lock(c->page);
-	if (unlikely(!node_match(c, node)))
+	if (unlikely(!node_match(c, node) || c->freelist))
 		goto another_slab;
 load_freelist:
 	object = c->page->freelist;

@@ -1486,7 +1488,14 @@ load_freelist:
 	c->page->inuse = s->objects;
 	c->page->freelist = NULL;
 	c->node = page_to_nid(c->page);
+out:
 	slab_unlock(c->page);
+	local_irq_restore(flags);
+	preempt_enable();
+
+	if (unlikely((gfpflags & __GFP_ZERO)))
+		memset(object, 0, c->objsize);
+
 	return object;
 
 another_slab:

@@ -1527,6 +1536,8 @@ new_slab:
 		c->page = new;
 		goto load_freelist;
 	}
+	local_irq_restore(flags);
+	preempt_enable();
 	return NULL;
 debug:
 	c->freelist = NULL;

@@ -1536,8 +1547,7 @@ debug:
 
 	c->page->inuse++;
 	c->page->freelist = object[c->offset];
-	slab_unlock(c->page);
-	return object;
+	goto out;
 }
 
 /*

@@ -1554,23 +1564,20 @@ static void __always_inline *slab_alloc(
 		gfp_t gfpflags, int node, void *addr)
 {
 	void **object;
-	unsigned long flags;
 	struct kmem_cache_cpu *c;
 
-	local_irq_save(flags);
+	preempt_disable();
 	c = get_cpu_slab(s, smp_processor_id());
-	if (unlikely(!c->page || !c->freelist ||
-					!node_match(c, node)))
+redo:
+	object = c->freelist;
+	if (unlikely(!object || !node_match(c, node)))
+		return __slab_alloc(s, gfpflags, node, addr, c);
 
-		object = __slab_alloc(s, gfpflags, node, addr, c);
+	if (cmpxchg_local(&c->freelist, object, object[c->offset]) != object)
+		goto redo;
 
-	else {
-		object = c->freelist;
-		c->freelist = object[c->offset];
-	}
-	local_irq_restore(flags);
-
-	if (unlikely((gfpflags & __GFP_ZERO) && object))
+	preempt_enable();
+	if (unlikely((gfpflags & __GFP_ZERO)))
 		memset(object, 0, c->objsize);
 
 	return object;

@@ -1603,7 +1610,9 @@ static void __slab_free(struct kmem_cach
 {
 	void *prior;
 	void **object = (void *)x;
+	unsigned long flags;
 
+	local_irq_save(flags);
 	slab_lock(page);
 
 	if (unlikely(SlabDebug(page)))

@@ -1629,6 +1638,8 @@ checks_ok:
 
 out_unlock:
 	slab_unlock(page);
+	local_irq_restore(flags);
+	preempt_enable();
 	return;
 
 slab_empty:

@@ -1639,6 +1650,8 @@ slab_empty:
 		remove_partial(s, page);
 
 	slab_unlock(page);
+	local_irq_restore(flags);
+	preempt_enable();
 	discard_slab(s, page);
 	return;
 

@@ -1663,18 +1676,31 @@ static void __always_inline slab_free(st
 			struct page *page, void *x, void *addr)
 {
 	void **object = (void *)x;
-	unsigned long flags;
 	struct kmem_cache_cpu *c;
+	void **freelist;
 
-	local_irq_save(flags);
+	preempt_disable();
 	c = get_cpu_slab(s, smp_processor_id());
-	if (likely(page == c->page && c->freelist)) {
-		object[c->offset] = c->freelist;
-		c->freelist = object;
-	} else
-		__slab_free(s, page, x, addr, c->offset);
+redo:
+	freelist = c->freelist;
+	/*
+	 * Must read freelist before c->page. If a interrupt occurs and
+	 * changes c->page after we have read it here then it
+	 * will also have changed c->freelist and the cmpxchg will fail.
+	 *
+	 * If we would have checked c->page first then the freelist could
+	 * have been changed under us before we read c->freelist and we
+	 * would not be able to detect that situation.
+	 */
+	smp_rmb();
+	if (unlikely(page != c->page || !freelist))
+		return __slab_free(s, page, x, addr, c->offset);
+
+	object[c->offset] = freelist;
+	if (cmpxchg_local(&c->freelist, freelist, object) != freelist)
+		goto redo;
 
-	local_irq_restore(flags);
+	preempt_enable();
 }
 
 void kmem_cache_free(struct kmem_cache *s, void *x)

--
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>

cmpxchg_local is not available on all archs, but local_cmpxchg is. It expects a local_t type which is nothing else than a long. When the local atomic operation is not more efficient or not implemented on a given architecture, asm-generic/local.h falls back on atomic_long_t. If you want, you could work on the local_t type, which you could cast from a long to a pointer when you need so, since their size are, AFAIK, always the same (and some VM code even assume this is always the case).

Yup, see the patch I just posted for this.

Yes, expected improvements goes as follow:
x86, x86_64 : must faster due to non-LOCKed cmpxchg
alpha: should be faster due to memory barrier removal
mips: memory barriers removed
powerpc 32/64: memory barriers removed

On other architectures, either there is no better implementation than the standard atomic cmpxchg or it just has not been implemented.

I guess that a test series that would tell us how must improvement is seen on the optimized architectures (local cmpxchg vs interrupt enable/disable) and also what effect the standard cmpxchg has compared to interrupt disable/enable on the architectures where we can't do better than the standard cmpxchg will tell us if it is an interesting way to go. I would be happy to do these tests, but I don't have the hardware handy. I provide a test module to get these characteristics from various architectures in this email.

The measurements I get (in cycles):

enable interrupts (STI) disable interrupts (CLI) local CMPXCHG
IA32 (P4) 112 82 26
x86_64 AMD64 125 102 19

Test local cmpxchg vs int disable/enable. Please run on a 2.6.22 kernel (or recent 2.6.21-rcX-mmX) (with my cmpxchg local fix patch for x86_64). Make sure the TSC reads (get_cycles()) are reliable on your platform.

Mathieu

/* test-cmpxchg-nolock.c
*
* Compare local cmpxchg with irq disable / enable. */

#include <linux/jiffies.h>
#include <linux/compiler.h>
#include <linux/init.h>
#include <linux/module.h>
#include <linux/calc64.h>
#include <asm/timex.h>
#include <asm/system.h>

#define NR_LOOPS 20000

int test_val = 0;

static void do_test_cmpxchg(void)

{
	int ret;
	long flags;
	unsigned int i;
	cycles_t time1, time2, time;
	long rem;

	local_irq_save(flags);
	preempt_disable();
	time1 = get_cycles();
	for (i = 0; i < NR_LOOPS; i++) {
		ret = cmpxchg_local(&test_val, 0, 0);
	}
	time2 = get_cycles();
	local_irq_restore(flags);
	preempt_enable();
	time = time2 - time1;

	printk(KERN_ALERT "test results: time for non locked cmpxchg\n");
	printk(KERN_ALERT "number of loops: %d\n", NR_LOOPS);
	printk(KERN_ALERT "total time: %llu\n", time);
	time = div_long_long_rem(time, NR_LOOPS, &rem);
	printk(KERN_ALERT "-> non locked cmpxchg takes %llu cycles\n", time);
	printk(KERN_ALERT "test end\n");
}

/*
* This test will have a higher standard deviation due to incoming interrupts. */
static void do_test_enable_int(void)

{
	long flags;
	unsigned int i;
	cycles_t time1, time2, time;
	long rem;

	local_irq_save(flags);
	preempt_disable();
	time1 = get_cycles();
	for (i = 0; i < NR_LOOPS; i++) {
		local_irq_restore(flags);
	}
	time2 = get_cycles();
	local_irq_restore(flags);
	preempt_enable();
	time = time2 - time1;

	printk(KERN_ALERT "test results: time for enabling interrupts (STI)\n");
	printk(KERN_ALERT "number of loops: %d\n", NR_LOOPS);
	printk(KERN_ALERT "total time: %llu\n", time);
	time = div_long_long_rem(time, NR_LOOPS, &rem);
	printk(KERN_ALERT "-> enabling interrupts (STI) takes %llu cycles\n",
					time);
	printk(KERN_ALERT "test end\n");
}

static void do_test_disable_int(void)

{
	unsigned long flags, flags2;
	unsigned int i;
	cycles_t time1, time2, time;
	long rem;

	local_irq_save(flags);
	preempt_disable();
	time1 = get_cycles();
	for ( i = 0; i < NR_LOOPS; i++) {
		local_irq_save(flags2);
	}
	time2 = get_cycles();
	local_irq_restore(flags);
	preempt_enable();
	time = time2 - time1;

	printk(KERN_ALERT "test results: time for disabling interrupts (CLI)\n");
	printk(KERN_ALERT "number of loops: %d\n", NR_LOOPS);
	printk(KERN_ALERT "total time: %llu\n", time);
	time = div_long_long_rem(time, NR_LOOPS, &rem);
	printk(KERN_ALERT "-> disabling interrupts (CLI) takes %llu cycles\n",
				time);
	printk(KERN_ALERT "test end\n");
}

static int ltt_test_init(void)

{
	printk(KERN_ALERT "test init\n");
	
	do_test_cmpxchg();
	do_test_enable_int();
	do_test_disable_int();
	return -EAGAIN; /* Fail will directly unload the module */
}

static void ltt_test_exit(void)

{
	printk(KERN_ALERT "test exit\n");
}

module_init(ltt_test_init)
module_exit(ltt_test_exit)

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Mathieu Desnoyers");
MODULE_DESCRIPTION("Cmpxchg local test");

Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

--
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>

It would be cleaner to have cmpxchg_local on all arches. The type conversion is hacky. If this is really working then we should also use the mechanism for other things like the vm statistics.

Looks good and seems to indicate that we can at least double the speed of slab allocation.

--
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>

Another architecture tested

Comparison: irq enable/disable vs local CMPXCHG
enable interrupts (STI) disable interrupts (CLI) local CMPXCHG

IA32 (P4)               112                        82                       26
x86_64 AMD64            125                       102                       19

x86_64 Intel Core2 Quad 21 19 7

Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

--
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>

Some review here. I think we could do much better..

  page = c->page;

        || page != c->page)

Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

--
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>

Not sure as to what this may bring. If you read it earlier then you may get the wrong value and then may have to refetch the cacheline.

We cannot fetch c->freelist without determining c. I can remove the check for c->page == page so that the fetch of c->freelist comes immeidately after detemination of c. But that does not change performance.

Thought so too and I removed that smp_rmb and tested this modification on UP again without any performance gains. I think the cacheline fetches dominates the execution thread here and cmpxchg does not bring us anything.

--
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>