Slab allocator array operations V2

mm/slab_common.c +4 -0

+ */
+int __kmem_cache_alloc_array(struct kmem_cache *s,
+		gfp_t flags, size_t nr, void **p)
+{

This patch adds the basic infrastructure for alloc / free operations on pointer arrays. It includes a fallback function that can perform the array operations using the single alloc and free that every slab allocator performs.

Allocators must define _HAVE_SLAB_ALLOCATOR_OPERATIONS in their header files in order to implement their own fast version for these array operations.

Array operations allow a reduction of the processing overhead during allocation and therefore speed up acquisition of larger amounts of objects.

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

Index: linux/include/linux/slab.h
===================================================================

include/linux/slab.h +3 -0

@@ -123,6 +123,7 @@ struct kmem_cache *memcg_create_kmem_cac
 void kmem_cache_destroy(struct kmem_cache *);
 int kmem_cache_shrink(struct kmem_cache *);
 void kmem_cache_free(struct kmem_cache *, void *);
+void kmem_cache_free_array(struct kmem_cache *, size_t, void **);
 
 /*
  * Please use this macro to create slab caches. Simply specify the

@@ -289,6 +290,8 @@ static __always_inline int kmalloc_index
 
 void *__kmalloc(size_t size, gfp_t flags);
 void *kmem_cache_alloc(struct kmem_cache *, gfp_t flags);
+int kmem_cache_alloc_array(struct kmem_cache *, gfp_t gfpflags,
+				size_t nr, void **);
 
 #ifdef CONFIG_NUMA
 void *__kmalloc_node(size_t size, gfp_t flags, int node);

Index: linux/mm/slab_common.c
===================================================================

mm/slab_common.c +10 -0

@@ -105,6 +105,83 @@ static inline int kmem_cache_sanity_chec
 }
 #endif
 
+/*
+ * Fallback function that just calls kmem_cache_alloc
+ * for each element. This may be used if not all
+ * objects can be allocated or as a generic fallback
+ * if the allocator cannot support buik operations.
+ */
+int __kmem_cache_alloc_array(struct kmem_cache *s,
+		gfp_t flags, size_t nr, void **p)
+{
+	int i;

mm/slab_common.c +16 -0

+
+int kmem_cache_alloc_array(struct kmem_cache *s,
+		gfp_t flags, size_t nr, void **p)
+{
+	int i = 0;
+
+#ifdef _HAVE_SLAB_ALLOCATOR_ARRAY_OPERATIONS
+	/*
+	 * First extract objects from partial lists in order to
+	 * avoid further fragmentation.
+	 */
+	i += slab_array_alloc_from_partial(s, nr - i, p + i);
+
+	/*
+	 * If there are still a larger number of objects to be allocated
+	 * use the page allocator directly.

mm/slab_common.c +21 -0

+	/*
+	 * If a fully filled array has been requested then fill it
+	 * up if there are objects missing using the regular kmem_cache_alloc()
+	 */
+	if (i < nr)
+		i += __kmem_cache_alloc_array(s, flags, nr - i, p + i);
+
+	return i;
+}
+EXPORT_SYMBOL(kmem_cache_alloc_array);
+
+/*
+ * Fallback function for objects that an allocator does not want
+ * to deal with or for allocators that do not support bulk operations.
+ */
+void __kmem_cache_free_array(struct kmem_cache *s, size_t nr, void **p)
+{
+	int i;
+
+	for (i = 0; i < nr; i++)
+		kmem_cache_free(s, p[i]);

mm/slab.h +6 -0

+
+int slab_array_alloc_from_partial(struct kmem_cache *s, size_t nr, void **p);
+int slab_array_alloc_from_local(struct kmem_cache *s, size_t nr, void **p);
+int slab_array_alloc_from_page_allocator(struct kmem_cache *s, gfp_t flags,
+					size_t nr, void **p);
+
 #endif /* MM_SLAB_H */

Index: linux/mm/slub.c
===================================================================

mm/slub.c +0 -0

@@ -332,6 +332,11 @@ static inline int oo_objects(struct kmem
 	return x.x & OO_MASK;

The major portions are there but there is no support yet for directly allocating per cpu objects. There could also be more sophisticated code to exploit the batch freeing.

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

Index: linux/mm/slub.c
===================================================================

mm/slub.c +0 -0

mm/slub.c +4 -0

@@ -2516,8 +2521,78 @@ EXPORT_SYMBOL(kmem_cache_alloc_node_trac
 #endif
 #endif
 
+int slab_array_alloc_from_partial(struct kmem_cache *s,
+			size_t nr, void **p)
+{
+	void **end = p + nr;

Quoted 7 lines

mm/slab_common.c +7 -0

+int kmem_cache_alloc_array(struct kmem_cache *s,
+		gfp_t flags, size_t nr, void **p)
+{
+	int i = 0;
+
+#ifdef _HAVE_SLAB_ALLOCATOR_ARRAY_OPERATIONS
+	/*

mm/slab_common.c static inline int kmem_cache_sanity_chec · line 153

Quoted 3 lines

mm/slab_common.c +3 -0

+		i += slab_array_alloc_from_local(s, nr - i, p + i);
+
+#endif

This patch is referencing functions that don't exist and can do so since it's not compiled, but I think this belongs in the next patch. I also think that this particular implementation may be slub-specific so I would have expected just a call to an allocator-defined __kmem_cache_alloc_array() here with i = __kmem_cache_alloc_array().

return 0 instead of using _HAVE_SLAB_ALLOCATOR_ARRAY_OPERATIONS at all.

mm/slab_common.c static inline int kmem_cache_sanity_chec · line 184

Quoted 8 lines

mm/slab_common.c +8 -0

+#ifndef _HAVE_SLAB_ALLOCATOR_ARRAY_OPERATIONS
+void kmem_cache_free_array(struct kmem_cache *s, size_t nr, void **p)
+{
+	__kmem_cache_free_array(s, nr, p);
+}
+EXPORT_SYMBOL(kmem_cache_free_array);
+#endif
+

Hmm, not sure why the allocator would be required to do the EXPORT_SYMBOL() if it defines kmem_cache_free_array() itself. This

mm/slub.c EXPORT_SYMBOL(kmem_cache_alloc_node_trac · line 2537

Quoted 3 lines

mm/slub.c +3 -0

+
+
+	spin_lock_irqsave(&n->list_lock, flags);

This is quite an expensive lock with irqsave.

Yet another lock cost.

Review

Quoted 2 lines

(quoted diff) +2 -0

+	spin_unlock_irqrestore(&n->list_lock, flags);
+	return allocated;

I estimate (on my CPU) the locking cost itself is more than 32ns, plus the irqsave (which I've also found quite expensive, alone 14ns). Thus, estimated 46ns. Single elem slub fast path cost is 18-19ns. Thus 3-4 elem bulking should be enough to amortized the cost, guess we are still good :-)

Quoted 5 lines

This patch is referencing functions that don't exist and can do so since it's not compiled, but I think this belongs in the next patch. I also think that this particular implementation may be slub-specific so I would have expected just a call to an allocator-defined __kmem_cache_alloc_array() here with i = __kmem_cache_alloc_array().

The implementation is generic and can be used in the same way for SLAB. SLOB does not have these types of object though.

Quoted 1 line

return 0 instead of using _HAVE_SLAB_ALLOCATOR_ARRAY_OPERATIONS at all.

Ok that is a good idea. I'll just drop that macro and have all allocators provide dummy functions.

Quoted 11 lines

mm/slab_common.c static inline int kmem_cache_sanity_chec · line 184

Quoted 8 lines

mm/slab_common.c +8 -0

+#ifndef _HAVE_SLAB_ALLOCATOR_ARRAY_OPERATIONS
+void kmem_cache_free_array(struct kmem_cache *s, size_t nr, void **p)
+{
+	__kmem_cache_free_array(s, nr, p);
+}
+EXPORT_SYMBOL(kmem_cache_free_array);
+#endif
+

Hmm, not sure why the allocator would be required to do the EXPORT_SYMBOL() if it defines kmem_cache_free_array() itself. This

Keeping the EXPORT with the definition is the custom as far as I could tell.

Quoted 5 lines · Jesper Dangaard Brouer

mm/slub.c EXPORT_SYMBOL(kmem_cache_alloc_node_trac · line 2537

Quoted 3 lines

mm/slub.c +3 -0

+
+
+	spin_lock_irqsave(&n->list_lock, flags);

This is quite an expensive lock with irqsave.

Yes but we take it for all partial pages.

Quoted 1 line

Yet another lock cost.

Yup the page access is shared but there is one per page. Contention is unlikely.

Quoted 8 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+	spin_unlock_irqrestore(&n->list_lock, flags);
+	return allocated;

I estimate (on my CPU) the locking cost itself is more than 32ns, plus the irqsave (which I've also found quite expensive, alone 14ns). Thus, estimated 46ns. Single elem slub fast path cost is 18-19ns. Thus 3-4 elem bulking should be enough to amortized the cost, guess we are still good :-)

We can require that interrupt are off when the functions are called. Then we can avoid the "save" part?

Quoted 4 lines

Quoted 3 lines

Hmm, not sure why the allocator would be required to do the EXPORT_SYMBOL() if it defines kmem_cache_free_array() itself. This

Quoted 3 lines

Keeping the EXPORT with the definition is the custom as far as I could tell.

If you do dummy functions for all the allocators, then this should be as simple as unconditionally defining kmem_cache_free_array() and doing EXPORT_SYMBOL() here and then using your current implementation of __kmem_cache_free_array() for mm/slab.c.

Quoted 3 lines

Quoted 1 line

This is quite an expensive lock with irqsave.

Yes but we take it for all partial pages.

Sure, that is good, but this might be a contention point. In a micro benchmark, this contention should be visible, but in real use-cases the given subsystem also need to spend time to use these elements before requesting a new batch (as long as NIC cleanup cycles don't get too synchronized)

Quoted 2 lines

Yup the page access is shared but there is one per page. Contention is unlikely.

Yes, contention is unlikely, but every atomic operation is expensive. On my system the measured cost is 8ns, and a lock/unlock does two, thus 16ns. Which we then do per page freelist.

Quoted 2 lines

We can require that interrupt are off when the functions are called. Then we can avoid the "save" part?

Yes, we could also do so with an "_irqoff" variant of the func call, but given we are defining the API we can just require this from the start.

Quoted 1 line · Jesper Dangaard Brouer

Quoted 1 line

Quoted 1 line

This is quite an expensive lock with irqsave.

Quoted 6 lines

Quoted 2 lines

We can require that interrupt are off when the functions are called. Then we can avoid the "save" part?

Yes, we could also do so with an "_irqoff" variant of the func call, but given we are defining the API we can just require this from the start.

Allright. Lets do that then.

Quoted 7 lines

Quoted 6 lines

Quoted 2 lines

Hmm, not sure why the allocator would be required to do the EXPORT_SYMBOL() if it defines kmem_cache_free_array() itself. This

Keeping the EXPORT with the definition is the custom as far as I could tell.

Quoted 4 lines

If you do dummy functions for all the allocators, then this should be as simple as unconditionally defining kmem_cache_free_array() and doing EXPORT_SYMBOL() here and then using your current implementation of __kmem_cache_free_array() for mm/slab.c.

That works if I put an EXPORT_SYMBOL in mm/slab_common.c and define the function in mm/slub.c?

Measured on my laptop CPU i7-2620M CPU @ 2.70GHz:

* 12.775 ns - "clean" spin_lock_unlock
* 21.099 ns - irqsave variant spinlock
* 22.808 ns - "manual" irqsave before spin_lock
* 14.618 ns - "manual" local_irq_disable + spin_lock

Reproducible via my github repo:
https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/lib/time_bench_sample.c

The clean spin_lock_unlock is 8.324 ns faster than irqsave variant. The irqsave variant is actually faster than expected, as the measurement of an isolated local_irq_save_restore were 13.256 ns.

Quoted 6 lines · Christoph Lameter

Quoted 5 lines

This patch is referencing functions that don't exist and can do so since it's not compiled, but I think this belongs in the next patch. I also think that this particular implementation may be slub-specific so I would have expected just a call to an allocator-defined __kmem_cache_alloc_array() here with i = __kmem_cache_alloc_array().

Quoted 3 lines

The implementation is generic and can be used in the same way for SLAB. SLOB does not have these types of object though.

Ok, I didn't know if the slab implementation would follow the same format with the same callbacks or whether this would need to be cleaned up later.

The major portions are there but there is no support yet for directly allocating per cpu objects. There could also be more sophisticated code to exploit the batch freeing.

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

Index: linux/include/linux/slub_def.h
===================================================================

include/linux/slub_def.h +1 -0

@@ -110,4 +110,5 @@ static inline void sysfs_slab_remove(str
 }
 #endif
 
+#define _HAVE_SLAB_ALLOCATOR_ARRAY_OPERATIONS
 #endif /* _LINUX_SLUB_DEF_H */

Index: linux/mm/slub.c
===================================================================

mm/slub.c +13 -31

@@ -1379,13 +1379,9 @@ static void setup_object(struct kmem_cac
 		s->ctor(object);
 }
 
-static struct page *new_slab(struct kmem_cache *s, gfp_t flags, int node)
+static struct page *__new_slab(struct kmem_cache *s, gfp_t flags, int node)
 {
 	struct page *page;
-	void *start;
-	void *p;
-	int order;
-	int idx;
 
 	if (unlikely(flags & GFP_SLAB_BUG_MASK)) {
 		pr_emerg("gfp: %u\n", flags & GFP_SLAB_BUG_MASK);

@@ -1394,33 +1390,42 @@ static struct page *new_slab(struct kmem
 
 	page = allocate_slab(s,
 		flags & (GFP_RECLAIM_MASK | GFP_CONSTRAINT_MASK), node);
-	if (!page)
-		goto out;
+	if (page) {
+		inc_slabs_node(s, page_to_nid(page), page->objects);
+		page->slab_cache = s;
+		__SetPageSlab(page);
+		if (page->pfmemalloc)
+			SetPageSlabPfmemalloc(page);
+	}
 
-	order = compound_order(page);
-	inc_slabs_node(s, page_to_nid(page), page->objects);
-	page->slab_cache = s;
-	__SetPageSlab(page);
-	if (page->pfmemalloc)
-		SetPageSlabPfmemalloc(page);
-
-	start = page_address(page);
-
-	if (unlikely(s->flags & SLAB_POISON))
-		memset(start, POISON_INUSE, PAGE_SIZE << order);
-
-	for_each_object_idx(p, idx, s, start, page->objects) {
-		setup_object(s, page, p);
-		if (likely(idx < page->objects))
-			set_freepointer(s, p, p + s->size);
-		else
-			set_freepointer(s, p, NULL);
-	}
-
-	page->freelist = start;
-	page->inuse = page->objects;
-	page->frozen = 1;
-out:
+	return page;
+}
+
+static struct page *new_slab(struct kmem_cache *s, gfp_t flags, int node)
+{

mm/slub.c +25 -0

+
+		for_each_object_idx(p, idx, s, start, page->objects) {
+			setup_object(s, page, p);
+			if (likely(idx < page->objects))
+				set_freepointer(s, p, p + s->size);
+			else
+				set_freepointer(s, p, NULL);
+		}
+
+		page->freelist = start;
+		page->inuse = page->objects;
+		page->frozen = 1;
+	}
 	return page;
 }
 

@@ -2516,8 +2521,78 @@ EXPORT_SYMBOL(kmem_cache_alloc_node_trac
 #endif
 #endif
 
+int slab_array_alloc_from_partial(struct kmem_cache *s,
+			size_t nr, void **p)
+{
+	void **end = p + nr;
+	struct kmem_cache_node *n = get_node(s, numa_mem_id());
+	int allocated = 0;
+	unsigned long flags;
+	struct page *page, *page2;
+
+	if (!n->nr_partial)
+		return 0;
+

I also think that this implementation is slub-specific. For example, in slab case, it is always better to access local cpu cache first than page allocator since slab doesn't use list to manage free objects and there is no cache line overhead like as slub. I think that, in kmem_cache_alloc_array(), just call to allocator-defined __kmem_cache_alloc_array() is better approach.

mm/slub.c EXPORT_SYMBOL(kmem_cache_alloc_node_trac · line 2555

Quoted 4 lines

mm/slub.c +4 -0

+			*p++ = freelist;
+			freelist = get_freepointer(s, freelist);
+			allocated++;
+		}

Fetching all objects with holding node lock could result in enomourous lock contention. How about getting free ojbect pointer without holding the node lock? We can temporarilly store all head of freelists in array p and can fetch each object pointer without holding node lock.

Quoted 6 lines

I also think that this implementation is slub-specific. For example, in slab case, it is always better to access local cpu cache first than page allocator since slab doesn't use list to manage free objects and there is no cache line overhead like as slub. I think that, in kmem_cache_alloc_array(), just call to allocator-defined __kmem_cache_alloc_array() is better approach.

What do you mean by "better"? Please be specific as to where you would see a difference. And slab definititely manages free objects although differently than slub. SLAB manages per cpu (local) objects, per node partial lists etc. Same as SLUB. The cache line overhead is there but no that big a difference in terms of choosing objects to get first.

Quoted 7 lines · Joonsoo Kim

I also think that this implementation is slub-specific. For example, in slab case, it is always better to access local cpu cache first than page allocator since slab doesn't use list to manage free objects and there is no cache line overhead like as slub. I think that, in kmem_cache_alloc_array(), just call to allocator-defined __kmem_cache_alloc_array() is better approach.

What do you mean by "better"? Please be specific as to where you would see a difference. And slab definititely manages free objects although differently than slub. SLAB manages per cpu (local) objects, per node partial lists etc. Same as SLUB. The cache line overhead is there but no that big a difference in terms of choosing objects to get first.

For a large allocation it is beneficial for both allocators to fist reduce the list of partial allocated slab pages on a node.

Going to the local objects first is enticing since these are cache hot but there are only a limited number of these available and there are issues with acquiring a large number of objects. For SLAB the objects dispersed and not spatially local. For SLUB the number of objects is usually much more limited than SLAB (but that is configurable these days via the cpu partial pages). SLUB allocates spatially local objects from one page before moving to the other. This is an advantage. However, it has to traverse a linked list instead of an array (SLAB).

Quoted 9 lines · Joonsoo Kim

mm/slub.c EXPORT_SYMBOL(kmem_cache_alloc_node_trac · line 2555

Quoted 4 lines

mm/slub.c +4 -0

+			*p++ = freelist;
+			freelist = get_freepointer(s, freelist);
+			allocated++;
+		}

Fetching all objects with holding node lock could result in enomourous lock contention. How about getting free ojbect pointer without holding the node lock? We can temporarilly store all head of freelists in array p and can fetch each object pointer without holding node lock.

Could do that but lets first see if there is really an issue. The other cpu sharing the same partial lists presumaly have cpu local objects to get through first before they hit this lock.

Hmm...so far, SLAB focus on temporal locality rather than spatial locality as you know. Why SLAB need to consider spatial locality first in this kmem_cache_alloc_array() case?

And, although we use partial list first, we can't reduce fragmentation as much as SLUB. Local cache may keep some free objects of the partial slab so just exhausting free objects of partial slab doesn't means that there is no free object left. For SLUB, exhausting free objects of partial slab means there is no free object left.

If we allocate objects from local cache as much as possible, we can keep temporal locality and return objects as fast as possible since returing objects from local cache just needs memcpy from local array cache to destination array.

As David said, there is no implementation for SLAB yet and we have different opinion about implementation for SLAB. It's better to delay detailed implementation of kmem_cache_alloc_array() until implementation for SLAB is agreed. Before it, calling __kmem_cache_alloc_array() in kmem_cache_alloc_array() is sufficient to provide functionality.

On Tue, 17 Feb 2015, Joonsoo Kim wrote:

Quoted 4 lines

If we allocate objects from local cache as much as possible, we can keep temporal locality and return objects as fast as possible since returing objects from local cache just needs memcpy from local array cache to destination array.

I thought the point was that this is used to allocate very large amounts of objects. The hotness is not that big of an issue.

Its not that detailed. It is just layin out the basic strategy for the array allocs. First go to the partial lists to decrease fragmentation. Then bypass the allocator layers completely and go direct to the page allocator if all objects that the page will accomodate can be put into the array. Lastly use the cpu hot objects to fill in the leftover (which would in any case be less than the objects in a page).

(My use-case is in area of 32-64 elems)

Quoted 6 lines

Its not that detailed. It is just layin out the basic strategy for the array allocs. First go to the partial lists to decrease fragmentation. Then bypass the allocator layers completely and go direct to the page allocator if all objects that the page will accomodate can be put into the array. Lastly use the cpu hot objects to fill in the leftover (which would in any case be less than the objects in a page).

IMHO this strategy is a bit off, from what I was looking for.

I would prefer the first elements to be cache hot, and the later/rest of the elements can be more cache-cold. Reasoning behind this is, subsystem calling this alloc_array have likely ran out of elems (from it's local store/prev-call) and need to handout one elem immediately after this call returns.