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
===================================================================
--- linux.orig/include/linux/slab.h
+++ linux/include/linux/slab.h
@@ -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
===================================================================
--- linux.orig/mm/slab_common.c
+++ linux/mm/slab_common.c
@@ -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;
+
+ for (i = 0; i < nr; i++) {
+ void *x = kmem_cache_alloc(s, flags);
+
+ if (!x)
+ return i;
+ p[i] = x;
+ }
+ return i;
+}
+
+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.
+ */
+ if (nr - i > objects_per_slab_page(s))
+ i += slab_array_alloc_from_page_allocator(s,
+ flags, nr - i, p + i);
+
+ /* Get per cpu objects that may be available */
+ if (i < nr)
+ i += slab_array_alloc_from_local(s, nr - i, p + i);
+
+#endif
+ /*
+ * 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]);
+}
+
+#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
+
#ifdef CONFIG_MEMCG_KMEM
static int memcg_alloc_cache_params(struct mem_cgroup *memcg,
struct kmem_cache *s, struct kmem_cache *root_cache)
Index: linux/mm/slab.h
===================================================================
--- linux.orig/mm/slab.h
+++ linux/mm/slab.h
@@ -69,6 +69,9 @@ extern struct kmem_cache *kmem_cache;
unsigned long calculate_alignment(unsigned long flags,
unsigned long align, unsigned long size);
+/* Determine the number of objects per slab page */
+unsigned objects_per_slab_page(struct kmem_cache *);
+
#ifndef CONFIG_SLOB
/* Kmalloc array related functions */
void create_kmalloc_caches(unsigned long);
@@ -362,4 +365,12 @@ void *slab_next(struct seq_file *m, void
void slab_stop(struct seq_file *m, void *p);
int memcg_slab_show(struct seq_file *m, void *p);
+void __kmem_cache_free_array(struct kmem_cache *s, int nr, void **p);
+void __kmem_cache_alloc_array(struct kmem_cache *s, gfp_t flags, int nr, void **p);
+
+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
===================================================================
--- linux.orig/mm/slub.c
+++ linux/mm/slub.c
@@ -332,6 +332,11 @@ static inline int oo_objects(struct kmem
return x.x & OO_MASK;
}
+unsigned objects_per_slab_page(struct kmem_cache *s)
+{
+ return oo_objects(s->oo);
+}
+
/*
* Per slab locking using the pagelock
*/
On Tue, 10 Feb 2015 13:48:05 -0600 Christoph Lameter <[email protected]> wrote:
[...]
> Index: linux/mm/slab_common.c
> ===================================================================
> --- linux.orig/mm/slab_common.c
> +++ linux/mm/slab_common.c
> @@ -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.
^^^^
Minor typo "buik" -> "bulk"
> + */
> +int __kmem_cache_alloc_array(struct kmem_cache *s,
> + gfp_t flags, size_t nr, void **p)
> +{
[...]
--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Sr. Network Kernel Developer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer
On Tue, 10 Feb 2015, Christoph Lameter wrote:
> 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.
>
This doesn't apply to -mm because of commits f707780a2121 ("slab: embed
memcg_cache_params to kmem_cache") and 0d48f42820db ("memcg: free
memcg_caches slot on css offline"), but it should be trivial to resolve.
> Signed-off-by: Christoph Lameter <[email protected]>
>
> Index: linux/include/linux/slab.h
> ===================================================================
> --- linux.orig/include/linux/slab.h
> +++ linux/include/linux/slab.h
> @@ -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
> ===================================================================
> --- linux.orig/mm/slab_common.c
> +++ linux/mm/slab_common.c
> @@ -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;
> +
> + for (i = 0; i < nr; i++) {
> + void *x = kmem_cache_alloc(s, flags);
> +
> + if (!x)
> + return i;
> + p[i] = x;
> + }
> + return i;
> +}
If size_t is unsigned long and i is int and i overflows then bad things
happen. I don't expect that we'll have any callers that have such large
values of nr, but it shouldn't index negatively into an array.
> +
> +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.
> + */
> + if (nr - i > objects_per_slab_page(s))
> + i += slab_array_alloc_from_page_allocator(s,
> + flags, nr - i, p + i);
> +
> + /* Get per cpu objects that may be available */
> + if (i < nr)
> + 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().
If that's done, then slab and slob can just define a dummy inline
__kmem_cache_alloc_array() functions that
return 0 instead of using _HAVE_SLAB_ALLOCATOR_ARRAY_OPERATIONS at all.
> + /*
> + * 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]);
> +}
> +
> +#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
becomes simpler if you remove _HAVE_SLAB_ALLOCATOR_ARRAY_OPERATIONS
entirely and just have slab and slob do __kmem_cache_free_array()
behavior.
> #ifdef CONFIG_MEMCG_KMEM
> static int memcg_alloc_cache_params(struct mem_cgroup *memcg,
> struct kmem_cache *s, struct kmem_cache *root_cache)
> Index: linux/mm/slab.h
> ===================================================================
> --- linux.orig/mm/slab.h
> +++ linux/mm/slab.h
> @@ -69,6 +69,9 @@ extern struct kmem_cache *kmem_cache;
> unsigned long calculate_alignment(unsigned long flags,
> unsigned long align, unsigned long size);
>
> +/* Determine the number of objects per slab page */
> +unsigned objects_per_slab_page(struct kmem_cache *);
Seems like it should be in the next patch.
> +
> #ifndef CONFIG_SLOB
> /* Kmalloc array related functions */
> void create_kmalloc_caches(unsigned long);
> @@ -362,4 +365,12 @@ void *slab_next(struct seq_file *m, void
> void slab_stop(struct seq_file *m, void *p);
> int memcg_slab_show(struct seq_file *m, void *p);
>
> +void __kmem_cache_free_array(struct kmem_cache *s, int nr, void **p);
> +void __kmem_cache_alloc_array(struct kmem_cache *s, gfp_t flags, int nr, void **p);
Longer than 80 chars.
> +
> +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
> ===================================================================
> --- linux.orig/mm/slub.c
> +++ linux/mm/slub.c
> @@ -332,6 +332,11 @@ static inline int oo_objects(struct kmem
> return x.x & OO_MASK;
> }
>
> +unsigned objects_per_slab_page(struct kmem_cache *s)
> +{
> + return oo_objects(s->oo);
> +}
> +
> /*
> * Per slab locking using the pagelock
> */
On Tue, 10 Feb 2015, David Rientjes wrote:
> > +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
> > + /*
...
> > + 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().
The implementation is generic and can be used in the same way for SLAB.
SLOB does not have these types of object though.
> 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.
> > +#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.
On Wed, 11 Feb 2015, Christoph Lameter wrote:
> > 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.
>
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.
> > 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.
>
> > > +#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.
>
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.
On Wed, 11 Feb 2015, David Rientjes wrote:
> > >
> > > 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.
> >
>
> 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?
On Wed, 11 Feb 2015, Christoph Lameter wrote:
> > > > 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.
> > >
> >
> > 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?
>
No, my suggestion was for the same pattern as kmem_cache_alloc_array().
In other words, I think you should leave the definition of
kmem_cache_free_array() the way it is in your patch, remove the #ifndef
since _HAVE_SLAB_ALLOCATOR_ARRAY_OPERATIONS is going away, and then define
a __kmem_cache_free_array() for each allocator.
On Wed, Feb 11, 2015 at 12:18:07PM -0800, David Rientjes wrote:
> On Wed, 11 Feb 2015, Christoph Lameter wrote:
>
> > > 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.
> >
>
> 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.
Hello, Christoph.
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.
Thanks.
On Fri, 13 Feb 2015, Joonsoo Kim wrote:
>
> 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).
On Fri, 13 Feb 2015, Christoph Lameter wrote:
> > 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.
>
I think because we currently lack a non-fallback implementation for slab
that it may be premature to discuss what would be unified if such an
implementation were to exist. That unification can always happen later
if/when the slab implementation is proposed, but I don't think we should
be unifying an implementation that doesn't exist.
In other words, I think it would be much cleaner to do just define the
generic array alloc and array free functions in mm/slab_common.c along
with their EXPORT_SYMBOL()'s as simple callbacks to per-allocator
__kmem_cache_{alloc,free}_array() implementations. I think it's also
better from a source code perspective to avoid reading two different
functions and then realizing that nothing is actually unified between them
(and the absence of an unnecessary #ifdef is currently helpful).
On Fri, Feb 13, 2015 at 09:47:59AM -0600, Christoph Lameter wrote:
> On Fri, 13 Feb 2015, Joonsoo Kim wrote:
> >
> > 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).
Hello,
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.
This cannot be implemented by using kmem_cache_alloc_array() you
suggested and this is why I think just calling allocator-defined
__kmem_cache_alloc_array() is better approach.
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.
Thanks.
On Tue, 17 Feb 2015, Joonsoo Kim wrote:
> 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?
Well we are talking about a large number of objects. And going around
randomly in memory is going to cause a lot of TLB misses. Spatial locality
increases the effectiveness of the processing of these objects.
> 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.
SLUB will still have the per cpu objects in the per cpu page and te per
cpu slab pages.
> 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.
> 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.
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).
On Tue, 17 Feb 2015 10:03:51 -0600 (CST)
Christoph Lameter <[email protected]> wrote:
> On Tue, 17 Feb 2015, Joonsoo Kim wrote:
>
[...]
> > 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.
>
(My use-case is in area of 32-64 elems)
[...]
>
> 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.
--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Sr. Network Kernel Developer at Red Hat
Author of http://www.iptv-analyzer.org
LinkedIn: http://www.linkedin.com/in/brouer
On Wed, 18 Feb 2015, Jesper Dangaard Brouer wrote:
> (My use-case is in area of 32-64 elems)
Ok that is in the realm of a couple of pages from the page allocator?
> > 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.
The problem is that going for the cache hot objects involves dealing with
synchronization that you would not have to spend time on if going direct
to the page allocator or going to the partial lists and retrieving
multiple objects by taking a single lock.
Per cpu object (cache hot!) is already optimized to the hilt. There wont
be much of a benefit.