slub: per cpu cache for partial pages

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

In __slab_alloc() we can then take multiple partial pages off the per
node partial list in one go reducing node lock pressure.

We can also use the per cpu partial list in slab_alloc() to avoid scanning
partial lists for pages with free objects.

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

Potential future enhancements:

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

2. __slab_free() may have some code paths that could use optimization.

Performance:

				Before		After
./hackbench 100 process 200000
				Time: 1953.047	1564.614
./hackbench 100 process 20000
				Time: 207.176   156.940
./hackbench 100 process 20000
				Time: 204.468	156.940
./hackbench 100 process 20000
				Time: 204.879	158.772
./hackbench 10 process 20000
				Time: 20.153	15.853
./hackbench 10 process 20000
				Time: 20.153	15.986
./hackbench 10 process 20000
				Time: 19.363	16.111
./hackbench 1 process 20000
				Time: 2.518	2.307
./hackbench 1 process 20000
				Time: 2.258	2.339
./hackbench 1 process 20000
				Time: 2.864	2.163

Signed-off-by: Christoph Lameter <cl@linux.com>
Signed-off-by: Pekka Enberg <penberg@kernel.org>

3 files changed, 309 insertions, 48 deletions

diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
index 774b8952deb4..7870e473033c 100644
--- a/include/linux/mm_types.h
+++ b/include/linux/mm_types.h
@@ -79,9 +79,21 @@ struct page {
         };
 
         /* Third double word block */
-        struct list_head lru;           /* Pageout list, eg. active_list
+        union {
+                struct list_head lru;   /* Pageout list, eg. active_list
                                          * protected by zone->lru_lock !
                                          */
+                struct {                /* slub per cpu partial pages */
+                        struct page *next;      /* Next partial slab */
+#ifdef CONFIG_64BIT
+                        int pages;      /* Nr of partial slabs left */
+                        int pobjects;   /* Approximate # of objects */
+#else
+                        short int pages;
+                        short int pobjects;
+#endif
+                };
+        };
 
         /* Remainder is not double word aligned */
         union {
diff --git a/include/linux/slub_def.h b/include/linux/slub_def.h
index f58d6413d230..4890ef79d752 100644
--- a/include/linux/slub_def.h
+++ b/include/linux/slub_def.h
@@ -36,12 +36,15 @@ enum stat_item {
         ORDER_FALLBACK,         /* Number of times fallback was necessary */
         CMPXCHG_DOUBLE_CPU_FAIL,/* Failure of this_cpu_cmpxchg_double */
         CMPXCHG_DOUBLE_FAIL,    /* Number of times that cmpxchg double did not match */
+        CPU_PARTIAL_ALLOC,      /* Used cpu partial on alloc */
+        CPU_PARTIAL_FREE,       /* USed cpu partial on free */
         NR_SLUB_STAT_ITEMS };
 
 struct kmem_cache_cpu {
         void **freelist;        /* Pointer to next available object */
         unsigned long tid;      /* Globally unique transaction id */
         struct page *page;      /* The slab from which we are allocating */
+        struct page *partial;   /* Partially allocated frozen slabs */
         int node;               /* The node of the page (or -1 for debug) */
 #ifdef CONFIG_SLUB_STATS
         unsigned stat[NR_SLUB_STAT_ITEMS];
@@ -79,6 +82,7 @@ struct kmem_cache {
         int size;               /* The size of an object including meta data */
         int objsize;            /* The size of an object without meta data */
         int offset;             /* Free pointer offset. */
+        int cpu_partial;        /* Number of per cpu partial pages to keep around */
         struct kmem_cache_order_objects oo;
 
         /* Allocation and freeing of slabs */
diff --git a/mm/slub.c b/mm/slub.c
index df381af963b7..0e286acef62a 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -1560,7 +1560,7 @@ static inline void remove_partial(struct kmem_cache_node *n,
  */
 static inline void *acquire_slab(struct kmem_cache *s,
                 struct kmem_cache_node *n, struct page *page,
-                struct kmem_cache_cpu *c)
+                int mode)
 {
         void *freelist;
         unsigned long counters;
@@ -1575,7 +1575,8 @@ static inline void *acquire_slab(struct kmem_cache *s,
                 freelist = page->freelist;
                 counters = page->counters;
                 new.counters = counters;
-                new.inuse = page->objects;
+                if (mode)
+                        new.inuse = page->objects;
 
                 VM_BUG_ON(new.frozen);
                 new.frozen = 1;
@@ -1586,34 +1587,20 @@ static inline void *acquire_slab(struct kmem_cache *s,
                         "lock and freeze"));
 
         remove_partial(n, page);
-
-        if (freelist) {
-                /* Populate the per cpu freelist */
-                c->page = page;
-                c->node = page_to_nid(page);
-                stat(s, ALLOC_FROM_PARTIAL);
-
-                return freelist;
-        } else {
-                /*
-                 * Slab page came from the wrong list. No object to allocate
-                 * from. Put it onto the correct list and continue partial
-                 * scan.
-                 */
-                printk(KERN_ERR "SLUB: %s : Page without available objects on"
-                        " partial list\n", s->name);
-                return NULL;
-        }
+        return freelist;
 }
 
+static int put_cpu_partial(struct kmem_cache *s, struct page *page, int drain);
+
 /*
  * Try to allocate a partial slab from a specific node.
  */
 static void *get_partial_node(struct kmem_cache *s,
                 struct kmem_cache_node *n, struct kmem_cache_cpu *c)
 {
-        struct page *page;
-        void *object;
+        struct page *page, *page2;
+        void *object = NULL;
+        int count = 0;
 
         /*
          * Racy check. If we mistakenly see no partial slabs then we
@@ -1625,13 +1612,28 @@ static void *get_partial_node(struct kmem_cache *s,
                 return NULL;
 
         spin_lock(&n->list_lock);
-        list_for_each_entry(page, &n->partial, lru) {
-                object = acquire_slab(s, n, page, c);
-                if (object)
-                        goto out;
+        list_for_each_entry_safe(page, page2, &n->partial, lru) {
+                void *t = acquire_slab(s, n, page, count == 0);
+                int available;
+
+                if (!t)
+                        break;
+
+                if (!count) {
+                        c->page = page;
+                        c->node = page_to_nid(page);
+                        stat(s, ALLOC_FROM_PARTIAL);
+                        count++;
+                        object = t;
+                        available =  page->objects - page->inuse;
+                } else {
+                        page->freelist = t;
+                        available = put_cpu_partial(s, page, 0);
+                }
+                if (kmem_cache_debug(s) || available > s->cpu_partial / 2)
+                        break;
+
         }
-        object = NULL;
-out:
         spin_unlock(&n->list_lock);
         return object;
 }
@@ -1926,6 +1928,123 @@ redo:
         }
 }
 
+/* Unfreeze all the cpu partial slabs */
+static void unfreeze_partials(struct kmem_cache *s)
+{
+        struct kmem_cache_node *n = NULL;
+        struct kmem_cache_cpu *c = this_cpu_ptr(s->cpu_slab);
+        struct page *page;
+
+        while ((page = c->partial)) {
+                enum slab_modes { M_PARTIAL, M_FREE };
+                enum slab_modes l, m;
+                struct page new;
+                struct page old;
+
+                c->partial = page->next;
+                l = M_FREE;
+
+                do {
+
+                        old.freelist = page->freelist;