Slab allocator array operations

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

@@ -290,6 +291,39 @@ static __always_inline int kmalloc_index
 void *__kmalloc(size_t size, gfp_t flags);
 void *kmem_cache_alloc(struct kmem_cache *, gfp_t flags);
 
+/*
+ * Additional flags that may be specified in kmem_cache_alloc_array()'s
+ * gfp flags.
+ *
+ * If no flags are specified then kmem_cache_alloc_array() will first exhaust
+ * the partial slab page lists of the local node, then allocate new pages from
+ * the page allocator as long as more than objects per page objects are wanted
+ * and fill up the rest from local cached objects. If that is not enough then
+ * the remaining objects will be allocated via kmem_cache_alloc()

IMHO, exposing these options is not a good idea. It's really implementation specific. And, this flag won't show consistent performance according to specific slab implementation. For example, to get best performance, if SLAB is used, GFP_SLAB_ARRAY_LOCAL would be the best option, but, for the same purpose, if SLUB is used, GFP_SLAB_ARRAY_NEW would be the best option. And, performance could also depend on number of objects and size.

And, overriding gfp flag isn't a good idea. Someday gfp could use these values and they can't notice that these are used in slab subsystem with different meaning.

Quoted 8 lines

IMHO, exposing these options is not a good idea. It's really implementation specific. And, this flag won't show consistent performance according to specific slab implementation. For example, to get best performance, if SLAB is used, GFP_SLAB_ARRAY_LOCAL would be the best option, but, for the same purpose, if SLUB is used, GFP_SLAB_ARRAY_NEW would be the best option. And, performance could also depend on number of objects and size.

Why would slab show a better performance? SLUB also can have partial allocated pages per cpu and could also get data quite fast if only a minimal number of objects are desired. SLAB is slightly better because the number of cachelines touches stays small due to the arrangement of the freelist on the slab page and the queueing approach that does not involve linked lists.

GFP_SLAB_ARRAY new is best for large quantities in either allocator since SLAB also has to construct local metadata structures.

Quoted 2 lines

GFP_SLAB_ARRAY new is best for large quantities in either allocator since SLAB also has to construct local metadata structures.

In case of SLAB, there is just a little more work to construct local metadata so GFP_SLAB_ARRAY_NEW would not show better performance
than GFP_SLAB_ARRAY_LOCAL, because it would cause more overhead due to more page allocations. Because of this characteristic, I said that which option is
the best is implementation specific and therefore we should not expose it.

Even if we narrow down the problem to the SLUB, choosing correct option is difficult enough. User should know how many objects are cached in this kmem_cache
in order to choose best option since relative quantity would make performance difference.

And, how many objects are cached in this kmem_cache could be changed whenever implementation changed.

Quoted 9 lines · Joonsoo Kim

Quoted 2 lines

GFP_SLAB_ARRAY new is best for large quantities in either allocator since SLAB also has to construct local metadata structures.

In case of SLAB, there is just a little more work to construct local metadata so GFP_SLAB_ARRAY_NEW would not show better performance
than GFP_SLAB_ARRAY_LOCAL, because it would cause more overhead due to more page allocations. Because of this characteristic, I said that which option is
the best is implementation specific and therefore we should not expose it.

For large amounts of objects (hundreds or higher) GFP_SLAB_ARRAY_LOCAL will never have enough objects. GFP_SLAB_ARRAY_NEW will go to the page allocator and bypass free table creation and all the queuing that objects go through normally in SLAB. AFAICT its going to be a significant win.

A similar situation is true for the freeing operation. If the freeing operation results in all objects in a page being freed then we can also bypass that and put the page directly back into the page allocator (to be implemented once we agree on an approach).

Quoted 5 lines

Even if we narrow down the problem to the SLUB, choosing correct option is difficult enough. User should know how many objects are cached in this kmem_cache
in order to choose best option since relative quantity would make performance difference.

Ok we can add a function call to calculate the number of objects cached per cpu and per node? But then that is rather fluid and could change any moment.

Quoted 2 lines

And, how many objects are cached in this kmem_cache could be changed whenever implementation changed.

The default when no options are specified is to first exhaust the node partial objects, then allocate new slabs as long as we have more than objects per page left and only then satisfy from cpu local object. I think that is satisfactory for the majority of the cases.

The detailed control options were requested at the meeting in Auckland at the LCA. I am fine with dropping those if they do not make sense. Makes the API and implementation simpler. Jesper, are you ok with this?

Quoted 2 lines · Christoph Lameter

On Wed, 28 Jan 2015, Joonsoo Kim wrote:

Quoted 9 lines

The default when no options are specified is to first exhaust the node partial objects, then allocate new slabs as long as we have more than objects per page left and only then satisfy from cpu local object. I think that is satisfactory for the majority of the cases.

The detailed control options were requested at the meeting in Auckland at the LCA. I am fine with dropping those if they do not make sense. Makes the API and implementation simpler. Jesper, are you ok with this?

IMHO, it'd be better to choose a proper way of allocation by slab itself and not to expose options to API user. We could decide the best option according to current status of kmem_cache and requested object number and internal implementation.

Is there any obvious example these option are needed for user?

Attached a series of 3 patches to implement functionality to allocate arrays of pointers to slab objects. This can be used by the slab allocators to offer more optimized allocation and free paths.

Quoted 3 lines · On Fri, 23 Jan 2015 15:37:27 -0600 Christoph Lameter <[email protected]> wrote:

Attached a series of 3 patches to implement functionality to allocate arrays of pointers to slab objects. This can be used by the slab allocators to offer more optimized allocation and free paths.

What's the driver for this? The networking people, I think? If so, some discussion about that would be useful: who is involved, why they have this need, who are the people we need to bug to get it tested, whether this implementation is found adequate, etc.

Quoted 2 lines · Andrew Morton

On Fri, 23 Jan 2015 15:37:27 -0600 Christoph Lameter <[email protected]> wrote:

Quoted 8 lines

Quoted 3 lines

Attached a series of 3 patches to implement functionality to allocate arrays of pointers to slab objects. This can be used by the slab allocators to offer more optimized allocation and free paths.

What's the driver for this? The networking people, I think? If so, some discussion about that would be useful: who is involved, why they have this need, who are the people we need to bug to get it tested, whether this implementation is found adequate, etc.

Jesper and I gave a talk at LCA about this. LWN has an article on it.

I promised Christoph that I will performance benchmark this. I'll start by writing/performing some micro benchmarks, but it first starts to get really interesting once we plug it into e.g. the networking stack, as effects as instruction-cache misses due to code size starts to play a role.