slub: Rework allocator fastpaths

Rework the allocation paths so that updates of the page freelist, frozen state
and number of objects use cmpxchg_double_slab().

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

1 files changed, 280 insertions, 129 deletions

diff --git a/mm/slub.c b/mm/slub.c
index 5cf98ff09360..5f0346c97c5f 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -992,11 +992,6 @@ static noinline int alloc_debug_processing(struct kmem_cache *s, struct page *pa
         if (!check_slab(s, page))
                 goto bad;
 
-        if (!on_freelist(s, page, object)) {
-                object_err(s, page, object, "Object already allocated");
-                goto bad;
-        }
-
         if (!check_valid_pointer(s, page, object)) {
                 object_err(s, page, object, "Freelist Pointer check fails");
                 goto bad;
@@ -1060,14 +1055,6 @@ static noinline int free_debug_processing(struct kmem_cache *s,
                 goto fail;
         }
 
-        /* Special debug activities for freeing objects */
-        if (!page->frozen && !page->freelist) {
-                struct kmem_cache_node *n = get_node(s, page_to_nid(page));
-
-                spin_lock(&n->list_lock);
-                remove_full(s, page);
-                spin_unlock(&n->list_lock);
-        }
         if (s->flags & SLAB_STORE_USER)
                 set_track(s, object, TRACK_FREE, addr);
         trace(s, page, object, 0);
@@ -1178,6 +1165,7 @@ static inline int check_object(struct kmem_cache *s, struct page *page,
                         void *object, u8 val) { return 1; }
 static inline void add_full(struct kmem_cache *s, struct kmem_cache_node *n,
                                         struct page *page) {}
+static inline void remove_full(struct kmem_cache *s, struct page *page) {}
 static inline unsigned long kmem_cache_flags(unsigned long objsize,
         unsigned long flags, const char *name,
         void (*ctor)(void *))
@@ -1460,11 +1448,52 @@ static inline void remove_partial(struct kmem_cache_node *n,
 static inline int lock_and_freeze_slab(struct kmem_cache *s,
                 struct kmem_cache_node *n, struct page *page)
 {
-        if (slab_trylock(page)) {
-                remove_partial(n, page);
+        void *freelist;
+        unsigned long counters;
+        struct page new;
+
+
+        if (!slab_trylock(page))
+                return 0;
+
+        /*
+         * Zap the freelist and set the frozen bit.
+         * The old freelist is the list of objects for the
+         * per cpu allocation list.
+         */
+        do {
+                freelist = page->freelist;
+                counters = page->counters;
+                new.counters = counters;
+                new.inuse = page->objects;
+
+                VM_BUG_ON(new.frozen);
+                new.frozen = 1;
+
+        } while (!cmpxchg_double_slab(s, page,
+                        freelist, counters,
+                        NULL, new.counters,
+                        "lock and freeze"));
+
+        remove_partial(n, page);
+
+        if (freelist) {
+                /* Populate the per cpu freelist */
+                this_cpu_write(s->cpu_slab->freelist, freelist);
+                this_cpu_write(s->cpu_slab->page, page);
+                this_cpu_write(s->cpu_slab->node, page_to_nid(page));
                 return 1;
+        } 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);
+                slab_unlock(page);
+                return 0;
         }
-        return 0;
 }
 
 /*
@@ -1564,59 +1593,6 @@ static struct page *get_partial(struct kmem_cache *s, gfp_t flags, int node)
         return get_any_partial(s, flags);
 }
 
-/*
- * Move a page back to the lists.
- *
- * Must be called with the slab lock held.
- *
- * On exit the slab lock will have been dropped.
- */
-static void unfreeze_slab(struct kmem_cache *s, struct page *page, int tail)
-        __releases(bitlock)
-{
-        struct kmem_cache_node *n = get_node(s, page_to_nid(page));
-
-        if (page->inuse) {
-
-                if (page->freelist) {
-                        spin_lock(&n->list_lock);
-                        add_partial(n, page, tail);
-                        spin_unlock(&n->list_lock);
-                        stat(s, tail ? DEACTIVATE_TO_TAIL : DEACTIVATE_TO_HEAD);
-                } else {
-                        stat(s, DEACTIVATE_FULL);
-                        if (kmem_cache_debug(s) && (s->flags & SLAB_STORE_USER)) {
-                                spin_lock(&n->list_lock);
-                                add_full(s, n, page);
-                                spin_unlock(&n->list_lock);
-                        }
-                }
-                slab_unlock(page);
-        } else {
-                stat(s, DEACTIVATE_EMPTY);
-                if (n->nr_partial < s->min_partial) {
-                        /*
-                         * Adding an empty slab to the partial slabs in order
-                         * to avoid page allocator overhead. This slab needs
-                         * to come after the other slabs with objects in
-                         * so that the others get filled first. That way the
-                         * size of the partial list stays small.
-                         *
-                         * kmem_cache_shrink can reclaim any empty slabs from
-                         * the partial list.
-                         */
-                        spin_lock(&n->list_lock);
-                        add_partial(n, page, 1);
-                        spin_unlock(&n->list_lock);
-                        slab_unlock(page);
-                } else {
-                        slab_unlock(page);
-                        stat(s, FREE_SLAB);
-                        discard_slab(s, page);
-                }
-        }
-}
-
 #ifdef CONFIG_PREEMPT
 /*
  * Calculate the next globally unique transaction for disambiguiation
@@ -1686,37 +1662,158 @@ void init_kmem_cache_cpus(struct kmem_cache *s)
 /*
  * Remove the cpu slab
  */
+
+/*
+ * Remove the cpu slab
+ */
 static void deactivate_slab(struct kmem_cache *s, struct kmem_cache_cpu *c)
-        __releases(bitlock)
 {
+        enum slab_modes { M_NONE, M_PARTIAL, M_FULL, M_FREE };
         struct page *page = c->page;
-        int tail = 1;
-
-        if (page->freelist)
+        struct kmem_cache_node *n = get_node(s, page_to_nid(page));
+        int lock = 0;
+        enum slab_modes l = M_NONE, m = M_NONE;
+        void *freelist;
+        void *nextfree;
+        int tail = 0;
+        struct page new;
+        struct page old;
+
+        if (page->freelist) {
                 stat(s, DEACTIVATE_REMOTE_FREES);
+                tail = 1;
+        }
+
+        c->tid = next_tid(c->tid);
+        c->page = NULL;
+        freelist = c->freelist;
+        c->freelist = NULL;
+
         /*
-         * Merge cpu freelist into slab freelist. Typically we get here
-         * because both freelists are empty. So this is unlikely
-         * to occur.
+         * Stage one: Free all available per cpu objects back
+         * to the page freelist while it is still frozen. Leave the
+         * last one.
+         *
+         * There is no need to take the list->lock because the page
+         * is still frozen.
          */
-        while (unlikely(c->freelist)) {
-                void **object;
+        while (freelist && (nextfree = get_freepointer(s, freelist))) {
+                void *prior;
+                unsigned long counters;
+
+                do {
+                        prior = page->freelist;
+                        counters = page->counters;
+                        set_freepointer(s, freelist, prior);
+                        new.counters = counters;
+                        new.inuse--;
+                        VM_BUG_ON(!new.frozen);
+
+                } while (!cmpxchg_double_slab(s, page,
+                        prior, counters,
+                        freelist, new.counters,
+                        "drain percpu freelist"));
+
+                freelist = nextfree;
+        }
 
-                tail = 0;       /* Hot objects. Put the slab first */
+        /*
+         * Stage two: Ensure that the page is unfrozen while the
+         * list presence reflects the actual number of objects
+         * during unfreeze.
+         *
+         * We setup the list membership and then perform a cmpxchg
+         * with the count. If there is a mismatch then the page
+         * is not unfrozen but the page is on the wrong list.
+         *
+         * Then we restart the process which may have to remove
+         * the page from the list that we just put it on again
+         * because the number of objects in the slab may have
+         * changed.
+         */
+redo:
 
-                /* Retrieve object from cpu_freelist */
-                object = c->freelist;
-                c->freelist = get_freepointer(s, c->freelist);
+        old.freelist = page->freelist;
+        old.counters = page->counters;
+        VM_BUG_ON(!old.frozen);
 
-                /* And put onto the regular freelist */
-                set_freepointer(s, object, page->freelist);
-                page->freelist = object;
-                page->inuse--;
+        /* Determine target state of the slab */
+        new.counters = old.counters;
+        if (freelist) {
+                new.inuse--;
+                set_freepointer(s, freelist, old.freelist);
+                new.freelist = freelist;
+        } else
+                new.freelist = old.freelist;
+
+        new.frozen = 0;
+
+        if (!new.inuse && n->nr_partial < s->min_partial)
+                m = M_FREE;
+        else if (new.freelist) {
+                m = M_PARTIAL;
+                if (!lock) {
+                        lock = 1;
+                        /*
+                         * Taking the spinlock removes the possiblity
+                         * that acquire_slab() will see a slab page that
+                         * is frozen
+                         */
+                        spin_lock(&n->list_lock);
+                }
+        } else {
+                m = M_FULL;
+                if (kmem_cache_debug(s) && !lock) {
+                        lock = 1;
+                        /*
+                         * This also ensures that the scanning of full
+                         * slabs from diagnostic functions will not see
+                         * any frozen slabs.
+                         */
+                        spin_lock(&n->list_lock);
+                }
+        }
+
+        if (l != m) {
+
+                if (l == M_PARTIAL)
+
+                        remove_partial(n, page);
+
+                else if (l == M_FULL)
+
+                        remove_full(s, page);
+
+                if (m == M_PARTIAL) {
+
+                        add_partial(n, page, tail);
+                        stat(s, tail ? DEACTIVATE_TO_TAIL : DEACTIVATE_TO_HEAD);
+
+                } else if (m == M_FULL) {
+
+                        stat(s, DEACTIVATE_FULL);
+                        add_full(s, n, page);
+
+                }
+        }
+
+        l = m;
+        if (!cmpxchg_double_slab(s, page,
+                                old.freelist, old.counters,
+                                new.freelist, new.counters,
+                                "unfreezing slab"))
+                goto redo;
+
+        slab_unlock(page);
+
+        if (lock)
+                spin_unlock(&n->list_lock);
+
+        if (m == M_FREE) {
+                stat(s, DEACTIVATE_EMPTY);
+                discard_slab(s, page);
+                stat(s, FREE_SLAB);
         }
-        c->page = NULL;
-        c->tid = next_tid(c->tid);
-        page->frozen = 0;
-        unfreeze_slab(s, page, tail);
 }
 
 static inline void flush_slab(struct kmem_cache *s, struct kmem_cache_cpu *c)
@@ -1851,6 +1948,8 @@ static void *__slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
         void **object;
         struct page *page;
         unsigned long flags;
+        struct page new;
+        unsigned long counters;
 
         local_irq_save(flags);
 #ifdef CONFIG_PREEMPT
@@ -1873,25 +1972,33 @@ static void *__slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
         if (unlikely(!node_match(c, node)))
                 goto another_slab;
 
-        stat(s, ALLOC_REFILL);
+        stat(s, ALLOC_SLOWPATH);
+
+        do {
+                object = page->freelist;
+                counters = page->counters;
+                new.counters = counters;
+                new.inuse = page->objects;
+                VM_BUG_ON(!new.frozen);
+
+        } while (!cmpxchg_double_slab(s, page,
+                        object, counters,
+                        NULL, new.counters,
+                        "__slab_alloc"));
 
 load_freelist:
         VM_BUG_ON(!page->frozen);
 
-        object = page->freelist;
         if (unlikely(!object))
                 goto another_slab;
-        if (kmem_cache_debug(s))
-                goto debug;
 
-        c->freelist = get_freepointer(s, object);
-        page->inuse = page->objects;
-        page->freelist = NULL;
+        stat(s, ALLOC_REFILL);
 
         slab_unlock(page);
+
+        c->freelist = get_freepointer(s, object);
         c->tid = next_tid(c->tid);
         local_irq_restore(flags);
-        stat(s, ALLOC_SLOWPATH);
         return object;
 
 another_slab:
@@ -1901,9 +2008,10 @@ new_slab:
         page = get_partial(s, gfpflags, node);
         if (page) {
                 stat(s, ALLOC_FROM_PARTIAL);
-                page->frozen = 1;
-                c->node = page_to_nid(page);
-                c->page = page;
+                object = c->freelist;
+
+                if (kmem_cache_debug(s))
+                        goto debug;
                 goto load_freelist;
         }
 
@@ -1911,12 +2019,19 @@ new_slab:
 
         if (page) {
                 c = __this_cpu_ptr(s->cpu_slab);
-                stat(s, ALLOC_SLAB);
                 if (c->page)
                         flush_slab(s, c);
 
+                /*
+                 * No other reference to the page yet so we can
+                 * muck around with it freely without cmpxchg
+                 */
+                object = page->freelist;
+                page->freelist = NULL;
+                page->inuse = page->objects;
+
+                stat(s, ALLOC_SLAB);
                 slab_lock(page);
-                page->frozen = 1;
                 c->node = page_to_nid(page);
                 c->page = page;
                 goto load_freelist;
@@ -1925,12 +2040,12 @@ new_slab:
                 slab_out_of_memory(s, gfpflags, node);
         local_irq_restore(flags);
         return NULL;
+
 debug:
-        if (!alloc_debug_processing(s, page, object, addr))
-                goto another_slab;
+        if (!object || !alloc_debug_processing(s, page, object, addr))
+                goto new_slab;
 
-        page->inuse++;
-        page->freelist = get_freepointer(s, object);
+        c->freelist = get_freepointer(s, object);
         deactivate_slab(s, c);
         c->page = NULL;
         c->node = NUMA_NO_NODE;
@@ -2082,6 +2197,11 @@ static void __slab_free(struct kmem_cache *s, struct page *page,
 {
         void *prior;
         void **object = (void *)x;
+        int was_frozen;
+        int inuse;
+        struct page new;
+        unsigned long counters;
+        struct kmem_cache_node *n = NULL;
         unsigned long uninitialized_var(flags);
 
         local_irq_save(flags);
@@ -2091,32 +2211,65 @@ static void __slab_free(struct kmem_cache *s, struct page *page,
         if (kmem_cache_debug(s) && !free_debug_processing(s, page, x, addr))
                 goto out_unlock;
 
-        prior = page->freelist;
-        set_freepointer(s, object, prior);
-        page->freelist = object;
-        page->inuse--;
+        do {
+                prior = page->freelist;
+                counters = page->counters;
+                set_freepointer(s, object, prior);
+                new.counters = counters;
+                was_frozen = new.frozen;
+                new.inuse--;
+                if ((!new.inuse || !prior) && !was_frozen && !n) {
+                        n = get_node(s, page_to_nid(page));
+                        /*
+                         * Speculatively acquire the list_lock.
+                         * If the cmpxchg does not succeed then we may
+                         * drop the list_lock without any processing.
+                         *
+                         * Otherwise the list_lock will synchronize with
+                         * other processors updating the list of slabs.
+                         */
+                        spin_lock(&n->list_lock);
+                }
+                inuse = new.inuse;
 
-        if (unlikely(page->frozen)) {
-                stat(s, FREE_FROZEN);
-                goto out_unlock;
-        }
+        } while (!cmpxchg_double_slab(s, page,
+                prior, counters,
+                object, new.counters,
+                "__slab_free"));
 
-        if (unlikely(!page->inuse))
-                goto slab_empty;
+        if (likely(!n)) {
+                /*
+                 * The list lock was not taken therefore no list
+                 * activity can be necessary.
+                 */
+                if (was_frozen)
+                        stat(s, FREE_FROZEN);
+                goto out_unlock;
+        }
 
         /*
-         * Objects left in the slab. If it was not on the partial list before
-         * then add it.
+         * was_frozen may have been set after we acquired the list_lock in
+         * an earlier loop. So we need to check it here again.
          */
-        if (unlikely(!prior)) {
-                struct kmem_cache_node *n = get_node(s, page_to_nid(page));
+        if (was_frozen)
+                stat(s, FREE_FROZEN);
+        else {
+                if (unlikely(!inuse && n->nr_partial > s->min_partial))
+                        goto slab_empty;
 
-                spin_lock(&n->list_lock);
-                add_partial(get_node(s, page_to_nid(page)), page, 1);
-                spin_unlock(&n->list_lock);
-                stat(s, FREE_ADD_PARTIAL);
+                /*
+                 * Objects left in the slab. If it was not on the partial list before
+                 * then add it.
+                 */
+                if (unlikely(!prior)) {
+                        remove_full(s, page);
+                        add_partial(n, page, 0);
+                        stat(s, FREE_ADD_PARTIAL);
+                }
         }
 
+        spin_unlock(&n->list_lock);
+
 out_unlock:
         slab_unlock(page);
         local_irq_restore(flags);
@@ -2127,13 +2280,11 @@ slab_empty:
                 /*
                  * Slab still on the partial list.
                  */
-                struct kmem_cache_node *n = get_node(s, page_to_nid(page));
-
-                spin_lock(&n->list_lock);
                 remove_partial(n, page);
-                spin_unlock(&n->list_lock);
                 stat(s, FREE_REMOVE_PARTIAL);
         }
+
+        spin_unlock(&n->list_lock);
         slab_unlock(page);
         local_irq_restore(flags);
         stat(s, FREE_SLAB);