SLUB: Optional fastpath using cmpxchg_local

Provide an alternate implementation of the SLUB fastpaths for alloc
and free using cmpxchg_local. The cmpxchg_local fastpath is selected
for arches that have CONFIG_FAST_CMPXCHG_LOCAL set. An arch should only
set CONFIG_FAST_CMPXCHG_LOCAL if the cmpxchg_local is faster than an
interrupt enable/disable sequence. This is known to be true for both
x86 platforms so set FAST_CMPXCHG_LOCAL for both arches.

The cmpxchg_local fastpath is only selected if the machine supports SMP.

The advantages of a cmpxchg_local based fastpath are:

1. Lower cycle count (30-40% faster)

2. There is no need to disable and enable interrupts on the fastpath.
   Currently interrupts have to be disabled and enabled on every
   slab operation. This is likely saving a signficant percentage
   of interrupt off / on sequences in the kernel.

3. The disposal of freed slabs can occur with interrupts enabled.

4. The enabling of interrupts is no longer depending on the setting
   of __GFP_WAIT. We can simply operate with the status of the interrupt
   when the slab operation was called. (only works if __GFP_WAIT reflects
   the actual interrupt enable/disable status but I think that is a
   valid assumption?)

The alternate path is realized using #ifdef's. Several attempts to do the
same with macros and inline functions resulted in a mess. #ifdef here seem
to be the way to go.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

---
 arch/i386/Kconfig   |    4 ++
 arch/x86_64/Kconfig |    4 ++
 mm/slub.c           |   88 ++++++++++++++++++++++++++++++++++++++++++++++++++--
 3 files changed, 94 insertions(+), 2 deletions(-)

Index: linux-2.6/mm/slub.c
===================================================================
--- linux-2.6.orig/mm/slub.c	2007-10-19 15:11:13.000000000 -0700
+++ linux-2.6/mm/slub.c	2007-10-19 15:11:58.000000000 -0700
@@ -168,6 +168,16 @@ static inline void ClearSlabDebug(struct
 #endif
 
 /*
+ * Switch on the cmpxchg local fast path if the arch supports fast
+ * cmpxchges.
+ */
+#ifdef CONFIG_SMP
+#ifdef CONFIG_FAST_CMPXCHG_LOCAL
+#define FASTPATH_CMPXCHG
+#endif
+#endif
+
+/*
  * Mininum number of partial slabs. These will be left on the partial
  * lists even if they are empty. kmem_cache_shrink may reclaim them.
  */
@@ -1483,7 +1493,11 @@ static void *__slab_alloc(struct kmem_ca
 {
 	void **object;
 	struct page *new;
+#ifdef FASTPATH_CMPXCHG
+	unsigned long flags;
 
+	local_irq_save(flags);
+#endif
 	if (!c->page)
 		goto new_slab;
 
@@ -1505,6 +1519,9 @@ load_freelist:
 unlock_out:
 	slab_unlock(c->page);
 out:
+#ifdef FASTPATH_CMPXCHG
+	local_irq_restore(flags);
+#endif
 	return object;
 
 another_slab:
@@ -1517,6 +1534,16 @@ new_slab:
 		goto load_freelist;
 	}
 
+#ifdef FASTPATH_CMPXCHG
+	local_irq_restore(flags);
+	put_cpu();
+
+	new = new_slab(s, gfpflags, node);
+
+	get_cpu();
+	local_irq_save(flags);
+#else
+
 	if (gfpflags & __GFP_WAIT)
 		local_irq_enable();
 
@@ -1524,6 +1551,7 @@ new_slab:
 
 	if (gfpflags & __GFP_WAIT)
 		local_irq_disable();
+#endif
 
 	if (new) {
 		c = get_cpu_slab(s, smp_processor_id());
@@ -1579,9 +1607,26 @@ static void __always_inline *slab_alloc(
 		gfp_t gfpflags, int node, void *addr)
 {
 	void **object;
-	unsigned long flags;
 	struct kmem_cache_cpu *c;
 
+#ifdef FASTPATH_CMPXCHG
+	c = get_cpu_slab(s, get_cpu());
+	do {
+		object = c->freelist;
+		if (unlikely(is_end(object))) {
+			object = __slab_alloc(s, gfpflags, node, addr, c);
+			if (unlikely(!object)) {
+				put_cpu();
+				return NULL;
+			}
+			break;
+		}
+	} while (cmpxchg_local(&c->freelist, object, object[c->offset])
+								!= object);
+	put_cpu();
+#else
+	unsigned long flags;
+
 	local_irq_save(flags);
 	c = get_cpu_slab(s, smp_processor_id());
 	if (unlikely(is_end(c->freelist) || !node_match(c, node))) {
@@ -1596,6 +1641,7 @@ static void __always_inline *slab_alloc(
 		c->freelist = object[c->offset];
 	}
 	local_irq_restore(flags);
+#endif
 
 	if (unlikely((gfpflags & __GFP_ZERO)))
 		memset(object, 0, c->objsize);
@@ -1631,6 +1677,11 @@ static void __slab_free(struct kmem_cach
 	void *prior;
 	void **object = (void *)x;
 
+#ifdef FASTPATH_CMPXCHG
+	unsigned long flags;
+
+	local_irq_save(flags);
+#endif
 	slab_lock(page);
 
 	if (unlikely(SlabDebug(page)))
@@ -1656,6 +1707,9 @@ checks_ok:
 
 out_unlock:
 	slab_unlock(page);
+#ifdef FASTPATH_CMPXCHG
+	local_irq_save(flags);
+#endif
 	return;
 
 slab_empty:
@@ -1666,6 +1720,9 @@ slab_empty:
 		remove_partial(s, page);
 
 	slab_unlock(page);
+#ifdef FASTPATH_CMPXCHG
+	local_irq_restore(flags);
+#endif
 	discard_slab(s, page);
 	return;
 
@@ -1690,9 +1747,35 @@ 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;
 
+#ifdef FASTPATH_CMPXCHG
+	c = get_cpu_slab(s, get_cpu());
+	debug_check_no_locks_freed(object, s->objsize);
+	do {
+		object = c->freelist;
+		barrier();
+		/*
+		 * If the compiler would reorder the retrieval of c->page to
+		 * come before c->freelist then an interrupt could
+		 * change the cpu slab before we retrieve c->freelist. We
+		 * could be matching on a page no longer active and put the
+		 * object onto the freelist of the wrong slab.
+		 *
+		 * On the other hand: If we already have the freelist pointer
+		 * then any change of cpu_slab will cause the cmpxchg to fail
+		 * since the freelist pointers are unique per slab.
+		 */
+		if (unlikely(page != c->page || c->node < 0)) {
+			__slab_free(s, page, x, addr, c->offset);
+			break;
+		}
+		object[c->offset] = c->freelist;
+	} while (cmpxchg_local(&c->freelist, c->freelist, object) != object);
+	put_cpu();
+#else
+	unsigned long flags;
+
 	local_irq_save(flags);
 	debug_check_no_locks_freed(object, s->objsize);
 	c = get_cpu_slab(s, smp_processor_id());
@@ -1703,6 +1786,7 @@ static void __always_inline slab_free(st
 		__slab_free(s, page, x, addr, c->offset);
 
 	local_irq_restore(flags);
+#endif
 }
 
 void kmem_cache_free(struct kmem_cache *s, void *x)
Index: linux-2.6/arch/i386/Kconfig
===================================================================
--- linux-2.6.orig/arch/i386/Kconfig	2007-10-19 15:08:49.000000000 -0700
+++ linux-2.6/arch/i386/Kconfig	2007-10-19 15:11:29.000000000 -0700
@@ -51,6 +51,10 @@ config X86
 	bool
 	default y
 
+config FAST_CMPXCHG_LOCAL
+	bool
+	default y
+
 config MMU
 	bool
 	default y
Index: linux-2.6/arch/x86_64/Kconfig
===================================================================
--- linux-2.6.orig/arch/x86_64/Kconfig	2007-10-19 15:08:49.000000000 -0700
+++ linux-2.6/arch/x86_64/Kconfig	2007-10-19 15:11:29.000000000 -0700
@@ -97,6 +97,10 @@ config X86_CMPXCHG
 	bool
 	default y
 
+config FAST_CMPXCHG_LOCAL
+	bool
+	default y
+
 config EARLY_PRINTK
 	bool
 	default y