Skip to contentSkip to conversation

slub: bulk alloc and free for slub allocator

PATCH Superseded Jesper Dangaard Brouer 6 participants 35 messages Jun 15, 2015 – Jun 17, 2015

Subsystems (4)
Networking Network drivers Memory management Slab allocator

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Jesper Dangaard Brouer

author
#0 lore raw

cover slub: bulk alloc and free for slub allocator

With this patchset SLUB allocator now both have bulk alloc and free implemented.

(This patchset is based on DaveM's net-next tree on-top of commit c3eee1fb1d308. Tested patchset applied on-top of volatile linux-next commit aa036f86e1bf ("slub bulk alloc: extract objects from the per cpu slab"))

This mostly optimizes the "fastpath" where objects are available on the per CPU fastpath page. This mostly amortize the less-heavy none-locked cmpxchg_double used on fastpath.

The "fallback bulking" (e.g __kmem_cache_free_bulk) provides a good basis for comparison, but to avoid counting the overhead of the function call in benchmarking[1] I've used an inlined versions of these.

Tested on (very fast) CPU i7-4790K @ 4.00GHz, thus look at cycles count (as nanosec measurements are very low given the clock rate).

Baseline normal fastpath (alloc+free cost): 43 cycles(tsc) 10.814 ns

Bulk - Fallback bulking           - fastpath-bulking
   1 -  47 cycles(tsc) 11.921 ns  -  45 cycles(tsc) 11.461 ns   improved  4.3%
   2 -  46 cycles(tsc) 11.649 ns  -  28 cycles(tsc)  7.023 ns   improved 39.1%
   3 -  46 cycles(tsc) 11.550 ns  -  22 cycles(tsc)  5.671 ns   improved 52.2%
   4 -  45 cycles(tsc) 11.398 ns  -  19 cycles(tsc)  4.967 ns   improved 57.8%
   8 -  45 cycles(tsc) 11.303 ns  -  17 cycles(tsc)  4.298 ns   improved 62.2%
  16 -  44 cycles(tsc) 11.221 ns  -  17 cycles(tsc)  4.423 ns   improved 61.4%
  30 -  75 cycles(tsc) 18.894 ns  -  57 cycles(tsc) 14.497 ns   improved 24.0%
  32 -  73 cycles(tsc) 18.491 ns  -  56 cycles(tsc) 14.227 ns   improved 23.3%
  34 -  75 cycles(tsc) 18.962 ns  -  58 cycles(tsc) 14.638 ns   improved 22.7%
  48 -  80 cycles(tsc) 20.049 ns  -  64 cycles(tsc) 16.247 ns   improved 20.0%
  64 -  87 cycles(tsc) 21.929 ns  -  74 cycles(tsc) 18.598 ns   improved 14.9%
 128 -  98 cycles(tsc) 24.511 ns  -  89 cycles(tsc) 22.295 ns   improved  9.2%
 158 - 101 cycles(tsc) 25.389 ns  -  93 cycles(tsc) 23.390 ns   improved  7.9%
 250 - 104 cycles(tsc) 26.170 ns  - 100 cycles(tsc) 25.112 ns   improved  3.8%

Benchmarking shows impressive improvements in the "fastpath" with a small number of objects in the working set. Once the working set increases, resulting in activating the "slowpath" (that contains the heavier locked cmpxchg_double) the improvement decreases.

I'm currently working on also optimizing the "slowpath" (as network stack use-case hits this), but this patchset should provide a good foundation for further improvements.

Rest of my patch queue in this area needs some more work, but preliminary results are good. I'm attending Netfilter Workshop[2] next week, and I'll hopefully return working on further improvements in this area.

[1] https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/mm/slab_bulk_test01.c
[2] http://workshop.netfilter.org/2015/
---

Christoph Lameter (2):
slab: infrastructure for bulk object allocation and freeing slub bulk alloc: extract objects from the per cpu slab

Jesper Dangaard Brouer (5):
slub: reduce indention level in kmem_cache_alloc_bulk()
slub: fix error path bug in kmem_cache_alloc_bulk
slub: kmem_cache_alloc_bulk() move clearing outside IRQ disabled section
slub: improve bulk alloc strategy
slub: initial bulk free implementation

 include/linux/slab.h |   10 +++++
 mm/slab.c            |   13 +++++++
 mm/slab.h            |    9 +++++
 mm/slab_common.c     |   23 ++++++++++++
 mm/slob.c            |   13 +++++++
 mm/slub.c            |   93 ++++++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 161 insertions(+)

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

author
#1 lore raw

PATCH 1/7 slab: infrastructure for bulk object allocation and freeing

From: Christoph Lameter <[email protected]>

[NOTICE: Already in AKPM's quilt-queue]

Add the basic infrastructure for alloc/free operations on pointer arrays. It includes a generic function in the common slab code that is used in this infrastructure patch to create the unoptimized functionality for slab bulk operations.

Allocators can then provide optimized allocation functions for situations in which large numbers of objects are needed. These optimization may avoid taking locks repeatedly and bypass metadata creation if all objects in slab pages can be used to provide the objects required.

Allocators can extend the skeletons provided and add their own code to the bulk alloc and free functions. They can keep the generic allocation and freeing and just fall back to those if optimizations would not work (like for example when debugging is on).

Signed-off-by Christoph Lameter <[email protected]>
Cc Jesper Dangaard Brouer <[email protected]>
Cc Pekka Enberg <[email protected]>
Cc David Rientjes <[email protected]>
Cc Joonsoo Kim <[email protected]>
Signed-off-by Andrew Morton <[email protected]>
---
 include/linux/slab.h |   10 ++++++++++
 mm/slab.c            |   13 +++++++++++++
 mm/slab.h            |    9 +++++++++
 mm/slab_common.c     |   23 +++++++++++++++++++++++
 mm/slob.c            |   13 +++++++++++++
 mm/slub.c            |   14 ++++++++++++++
 6 files changed, 82 insertions(+)
include/linux/slab.h +10 -0
index ffd24c830151..5db59c950ef7 100644
@@ -290,6 +290,16 @@ void *__kmalloc(size_t size, gfp_t flags);
 void *kmem_cache_alloc(struct kmem_cache *, gfp_t flags);
 void kmem_cache_free(struct kmem_cache *, void *);
 
+/*
+ * Bulk allocation and freeing operations. These are accellerated in an
+ * allocator specific way to avoid taking locks repeatedly or building
+ * metadata structures unnecessarily.
+ *
+ * Note that interrupts must be enabled when calling these functions.
+ */
+void kmem_cache_free_bulk(struct kmem_cache *, size_t, void **);
+bool kmem_cache_alloc_bulk(struct kmem_cache *, gfp_t, size_t, void **);
+
 #ifdef CONFIG_NUMA
 void *__kmalloc_node(size_t size, gfp_t flags, int node);
 void *kmem_cache_alloc_node(struct kmem_cache *, gfp_t flags, int node);
mm/slab.c +13 -0
index 7eb38dd1cefa..c799d7ed0e18 100644
@@ -3415,6 +3415,19 @@ void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)
 }
 EXPORT_SYMBOL(kmem_cache_alloc);
 
+void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
+{
+	__kmem_cache_free_bulk(s, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_free_bulk);
+
+bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
+								void **p)
+{
+	return kmem_cache_alloc_bulk(s, flags, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_alloc_bulk);
+
 #ifdef CONFIG_TRACING
 void *
 kmem_cache_alloc_trace(struct kmem_cache *cachep, gfp_t flags, size_t size)
mm/slab.h +9 -0
index 4c3ac12dd644..6a427a74cca5 100644
@@ -162,6 +162,15 @@ void slabinfo_show_stats(struct seq_file *m, struct kmem_cache *s);
 ssize_t slabinfo_write(struct file *file, const char __user *buffer,
 		       size_t count, loff_t *ppos);
 
+/*
+ * Generic implementation of bulk operations
+ * These are useful for situations in which the allocator cannot
+ * perform optimizations. In that case segments of the objecct listed
+ * may be allocated or freed using these operations.
+ */
+void __kmem_cache_free_bulk(struct kmem_cache *, size_t, void **);
+bool __kmem_cache_alloc_bulk(struct kmem_cache *, gfp_t, size_t, void **);
+
 #ifdef CONFIG_MEMCG_KMEM
 /*
  * Iterate over all memcg caches of the given root cache. The caller must hold
mm/slab_common.c +23 -0
index 999bb3424d44..f8acc2bdb88b 100644
@@ -105,6 +105,29 @@ static inline int kmem_cache_sanity_check(const char *name, size_t size)
 }
 #endif
 
+void __kmem_cache_free_bulk(struct kmem_cache *s, size_t nr, void **p)
+{
+	size_t i;
+
+	for (i = 0; i < nr; i++)
+		kmem_cache_free(s, p[i]);
+}
+
+bool __kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t nr,
+								void **p)
+{
+	size_t i;
+
+	for (i = 0; i < nr; i++) {
+		void *x = p[i] = kmem_cache_alloc(s, flags);
+		if (!x) {
+			__kmem_cache_free_bulk(s, i, p);
+			return false;
+		}
+	}
+	return true;
+}
+
 #ifdef CONFIG_MEMCG_KMEM
 void slab_init_memcg_params(struct kmem_cache *s)
 {
mm/slob.c +13 -0
index 4765f65019c7..495df8e006ec 100644
@@ -611,6 +611,19 @@ void kmem_cache_free(struct kmem_cache *c, void *b)
 }
 EXPORT_SYMBOL(kmem_cache_free);
 
+void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
+{
+	__kmem_cache_free_bulk(s, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_free_bulk);
+
+bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
+								void **p)
+{
+	return kmem_cache_alloc_bulk(s, flags, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_alloc_bulk);
+
 int __kmem_cache_shutdown(struct kmem_cache *c)
 {
 	/* No way to check for remaining objects */
mm/slub.c +14 -0
index 54c0876b43d5..80f17403e503 100644
@@ -2750,6 +2750,20 @@ void kmem_cache_free(struct kmem_cache *s, void *x)
 }
 EXPORT_SYMBOL(kmem_cache_free);
 
+void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
+{
+	__kmem_cache_free_bulk(s, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_free_bulk);
+
+bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
+								void **p)
+{
+	return kmem_cache_alloc_bulk(s, flags, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_alloc_bulk);
+
+
 /*
  * Object placement in a slab is made very easy because we always start at
  * offset 0. If we tune the size of the object to the alignment then we can
#2 lore raw

Re: [PATCH 1/7] slab: infrastructure for bulk object allocation and freeing

Quoted 25 lines · Jesper Dangaard Brouer

From: Christoph Lameter <[email protected]>

[NOTICE: Already in AKPM's quilt-queue]

Add the basic infrastructure for alloc/free operations on pointer arrays. It includes a generic function in the common slab code that is used in this infrastructure patch to create the unoptimized functionality for slab bulk operations.

Allocators can then provide optimized allocation functions for situations in which large numbers of objects are needed. These optimization may avoid taking locks repeatedly and bypass metadata creation if all objects in slab pages can be used to provide the objects required.

Allocators can extend the skeletons provided and add their own code to the bulk alloc and free functions. They can keep the generic allocation and freeing and just fall back to those if optimizations would not work (like for example when debugging is on).

Signed-off-by Christoph Lameter <[email protected]>
Cc Jesper Dangaard Brouer <[email protected]>
Cc Pekka Enberg <[email protected]>
Cc David Rientjes <[email protected]>
Cc Joonsoo Kim <[email protected]>
Signed-off-by Andrew Morton <[email protected]>
Quoted 8 lines
---
  include/linux/slab.h |   10 ++++++++++
  mm/slab.c            |   13 +++++++++++++
  mm/slab.h            |    9 +++++++++
  mm/slab_common.c     |   23 +++++++++++++++++++++++
  mm/slob.c            |   13 +++++++++++++
  mm/slub.c            |   14 ++++++++++++++
  6 files changed, 82 insertions(+)

So I can see the motivation behind bulk allocation, but I cannot see the motivation behind bulk freeing. In the case of freeing the likelihood of the memory regions all belonging to the same page just isn't as high.

Quoted 11 lines
include/linux/slab.h +3 -0
index ffd24c830151..5db59c950ef7 100644
@@ -290,6 +290,16 @@ void *__kmalloc(size_t size, gfp_t flags);
  void *kmem_cache_alloc(struct kmem_cache *, gfp_t flags);
  void kmem_cache_free(struct kmem_cache *, void *);
 
+/*
+ * Bulk allocation and freeing operations. These are accellerated in an
+ * allocator specific way to avoid taking locks repeatedly or building

include/linux/slab.h void *__kmalloc(size_t size, gfp_t flags); · line 305

Quoted 10 lines
include/linux/slab.h +7 -0
+ * metadata structures unnecessarily.
+ *
+ * Note that interrupts must be enabled when calling these functions.
+ */
+void kmem_cache_free_bulk(struct kmem_cache *, size_t, void **);
+bool kmem_cache_alloc_bulk(struct kmem_cache *, gfp_t, size_t, void **);
+
  #ifdef CONFIG_NUMA
  void *__kmalloc_node(size_t size, gfp_t flags, int node);
  void *kmem_cache_alloc_node(struct kmem_cache *, gfp_t flags, int node);

Instead of having the bulk allocation return true, why not just return the number of entries you were able to obtain beyond the first and cut out most of the complexity. For example if you want to allocate 4 entries, and you succeeded in allocating 4 entries you would return 3. If you wanted 1 entry and succeeded you would return zero, else you just return a negative value indicating you failed.

The general idea is to do a best effort allocation. So if you only have 3 entries available in the percpu freelist and you want 4 then maybe you should only grab 3 entries instead of trying to force more entries out then what is there by grabbing from multiple SLUB/SLAB caches.

Also I wouldn't use a size_t to track the number of entities requested. An int should be enough. The size_t is confusing as that is normally what you would use to specify the size of the memory region, not the number of copies of it to request.

Quoted 68 lines
mm/slab.c +13 -0
index 7eb38dd1cefa..c799d7ed0e18 100644
@@ -3415,6 +3415,19 @@ void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)
  }
  EXPORT_SYMBOL(kmem_cache_alloc);
 
+void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
+{
+	__kmem_cache_free_bulk(s, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_free_bulk);
+
+bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
+								void **p)
+{
+	return kmem_cache_alloc_bulk(s, flags, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_alloc_bulk);
+
  #ifdef CONFIG_TRACING
  void *
  kmem_cache_alloc_trace(struct kmem_cache *cachep, gfp_t flags, size_t size)
mm/slab.h +9 -0
index 4c3ac12dd644..6a427a74cca5 100644
@@ -162,6 +162,15 @@ void slabinfo_show_stats(struct seq_file *m, struct kmem_cache *s);
  ssize_t slabinfo_write(struct file *file, const char __user *buffer,
  		       size_t count, loff_t *ppos);
 
+/*
+ * Generic implementation of bulk operations
+ * These are useful for situations in which the allocator cannot
+ * perform optimizations. In that case segments of the objecct listed
+ * may be allocated or freed using these operations.
+ */
+void __kmem_cache_free_bulk(struct kmem_cache *, size_t, void **);
+bool __kmem_cache_alloc_bulk(struct kmem_cache *, gfp_t, size_t, void **);
+
  #ifdef CONFIG_MEMCG_KMEM
  /*
   * Iterate over all memcg caches of the given root cache. The caller must hold
mm/slab_common.c +16 -0
index 999bb3424d44..f8acc2bdb88b 100644
@@ -105,6 +105,29 @@ static inline int kmem_cache_sanity_check(const char *name, size_t size)
  }
  #endif
 
+void __kmem_cache_free_bulk(struct kmem_cache *s, size_t nr, void **p)
+{
+	size_t i;
+
+	for (i = 0; i < nr; i++)
+		kmem_cache_free(s, p[i]);
+}
+
+bool __kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t nr,
+								void **p)
+{
+	size_t i;
+
+	for (i = 0; i < nr; i++) {
+		void *x = p[i] = kmem_cache_alloc(s, flags);
+		if (!x) {

mm/slab_common.c static inline int kmem_cache_sanity_check(const char *name, size_t size) · line 133

Quoted 10 lines
mm/slab_common.c +7 -0
+			__kmem_cache_free_bulk(s, i, p);
+			return false;
+		}
+	}
+	return true;
+}
+
  #ifdef CONFIG_MEMCG_KMEM
  void slab_init_memcg_params(struct kmem_cache *s)
  {

I don't really see the reason why you should be populating arrays. SLUB uses a linked list and I don't see this implemented for SLOB or SLAB so maybe you should look at making this into a linked list. Also as I stated in the other comment maybe you should not do bulk allocation if you don't support it in SLAB/SLOB and instead change this so that you return a count indicating that only 1 value was allocated in this pass.

Quoted 40 lines
mm/slob.c +13 -0
index 4765f65019c7..495df8e006ec 100644
@@ -611,6 +611,19 @@ void kmem_cache_free(struct kmem_cache *c, void *b)
  }
  EXPORT_SYMBOL(kmem_cache_free);
 
+void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
+{
+	__kmem_cache_free_bulk(s, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_free_bulk);
+
+bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
+								void **p)
+{
+	return kmem_cache_alloc_bulk(s, flags, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_alloc_bulk);
+
  int __kmem_cache_shutdown(struct kmem_cache *c)
  {
  	/* No way to check for remaining objects */
mm/slub.c +7 -0
index 54c0876b43d5..80f17403e503 100644
@@ -2750,6 +2750,20 @@ void kmem_cache_free(struct kmem_cache *s, void *x)
  }
  EXPORT_SYMBOL(kmem_cache_free);
 
+void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
+{
+	__kmem_cache_free_bulk(s, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_free_bulk);
+
+bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,

mm/slub.c void kmem_cache_free(struct kmem_cache *s, void *x) · line 2769

Quoted 10 lines
mm/slub.c +7 -0
+								void **p)
+{
+	return kmem_cache_alloc_bulk(s, flags, size, p);
+}
+EXPORT_SYMBOL(kmem_cache_alloc_bulk);
+
+
  /*
   * Object placement in a slab is made very easy because we always start at
   * offset 0. If we tune the size of the object to the alignment then we can

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#3 lore raw

Re: [PATCH 1/7] slab: infrastructure for bulk object allocation and freeing

Quoted 3 lines · Alexander Duyck

So I can see the motivation behind bulk allocation, but I cannot see the motivation behind bulk freeing. In the case of freeing the likelihood of the memory regions all belonging to the same page just isn't as high.

The likelyhood is high if the object are allocated in batch as well. In that case SLUB ensures that all objects from the same page are first allocated.

Quoted 6 lines

I don't really see the reason why you should be populating arrays. SLUB uses a linked list and I don't see this implemented for SLOB or SLAB so maybe you should look at making this into a linked list. Also as I stated in the other comment maybe you should not do bulk allocation if you don't support it in SLAB/SLOB and instead change this so that you return a count indicating that only 1 value was allocated in this pass.

It is extremely easy to just take the linked list off a page or a per cpu structure. Basically we would have constant cycle count for taking N objects available in a slab page.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

maintainer
#4 lore raw

Re: [PATCH 1/7] slab: infrastructure for bulk object allocation and freeing

In reply to Jesper Dangaard Brouer

Review

Quoted 5 lines · On Mon, 15 Jun 2015 17:51:56 +0200 Jesper Dangaard Brouer <[email protected]>…
(quoted diff) +5 -0
+bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
+								void **p)
+{
+	return kmem_cache_alloc_bulk(s, flags, size, p);
+}

hm, any call to this function is going to be nasty, brutal and short.

mm/slab.c renamed from mm/slab.c~slab-infrastructure-for-bulk-object-allocation-and-freeing-v3-fix +1 -1
@@ -3425,7 +3425,7 @@ EXPORT_SYMBOL(kmem_cache_free_bulk);
 bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 								void **p)
 {
-	return kmem_cache_alloc_bulk(s, flags, size, p);
+	return __kmem_cache_alloc_bulk(s, flags, size, p);
 }
 EXPORT_SYMBOL(kmem_cache_alloc_bulk);

_

author
#5 lore raw

PATCH 2/7 slub bulk alloc: extract objects from the per cpu slab

In reply to Jesper Dangaard Brouer

From: Christoph Lameter <[email protected]>

[NOTICE: Already in AKPM's quilt-queue]

First piece: acceleration of retrieval of per cpu objects

If we are allocating lots of objects then it is advantageous to disable interrupts and avoid the this_cpu_cmpxchg() operation to get these objects faster.

Note that we cannot do the fast operation if debugging is enabled, because we would have to add extra code to do all the debugging checks. And it would not be fast anyway.

Note also that the requirement of having interrupts disabled avoids having to do processor flag operations.

Allocate as many objects as possible in the fast way and then fall back to the generic implementation for the rest of the objects.

Signed-off-by Christoph Lameter <[email protected]>
Cc Jesper Dangaard Brouer <[email protected]>
Cc Pekka Enberg <[email protected]>
Cc David Rientjes <[email protected]>
Cc Joonsoo Kim <[email protected]>
Signed-off-by Andrew Morton <[email protected]>
---
 mm/slub.c |   27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)
mm/slub.c +26 -1
index 80f17403e503..d18f8e195ac4 100644
@@ -2759,7 +2759,32 @@ EXPORT_SYMBOL(kmem_cache_free_bulk);
 bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 								void **p)
 {
-	return kmem_cache_alloc_bulk(s, flags, size, p);
+	if (!kmem_cache_debug(s)) {
+		struct kmem_cache_cpu *c;
+
+		/* Drain objects in the per cpu slab */
+		local_irq_disable();
+		c = this_cpu_ptr(s->cpu_slab);
+
+		while (size) {
+			void *object = c->freelist;
+
+			if (!object)
+				break;
+
+			c->freelist = get_freepointer(s, object);
+			*p++ = object;
+			size--;
+
+			if (unlikely(flags & __GFP_ZERO))
+				memset(object, 0, s->object_size);
+		}
+		c->tid = next_tid(c->tid);
+
+		local_irq_enable();
+	}
+
+	return __kmem_cache_alloc_bulk(s, flags, size, p);
 }
 EXPORT_SYMBOL(kmem_cache_alloc_bulk);
#6 lore raw

Re: [PATCH 2/7] slub bulk alloc: extract objects from the per cpu slab

Quoted 57 lines · Jesper Dangaard Brouer

From: Christoph Lameter <[email protected]>

[NOTICE: Already in AKPM's quilt-queue]

First piece: acceleration of retrieval of per cpu objects

If we are allocating lots of objects then it is advantageous to disable interrupts and avoid the this_cpu_cmpxchg() operation to get these objects faster.

Note that we cannot do the fast operation if debugging is enabled, because we would have to add extra code to do all the debugging checks. And it would not be fast anyway.

Note also that the requirement of having interrupts disabled avoids having to do processor flag operations.

Allocate as many objects as possible in the fast way and then fall back to the generic implementation for the rest of the objects.

Signed-off-by Christoph Lameter <[email protected]>
Cc Jesper Dangaard Brouer <[email protected]>
Cc Pekka Enberg <[email protected]>
Cc David Rientjes <[email protected]>
Cc Joonsoo Kim <[email protected]>
Signed-off-by Andrew Morton <[email protected]>
---
 mm/slub.c |   27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)
mm/slub.c +18 -1
index 80f17403e503..d18f8e195ac4 100644
@@ -2759,7 +2759,32 @@ EXPORT_SYMBOL(kmem_cache_free_bulk);
 bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 								void **p)
 {
-	return kmem_cache_alloc_bulk(s, flags, size, p);
+	if (!kmem_cache_debug(s)) {
+		struct kmem_cache_cpu *c;
+
+		/* Drain objects in the per cpu slab */
+		local_irq_disable();
+		c = this_cpu_ptr(s->cpu_slab);
+
+		while (size) {
+			void *object = c->freelist;
+
+			if (!object)
+				break;
+
+			c->freelist = get_freepointer(s, object);
+			*p++ = object;
+			size--;
+
+			if (unlikely(flags & __GFP_ZERO))

mm/slub.c EXPORT_SYMBOL(kmem_cache_free_bulk); · line 2789

Quoted 10 lines
mm/slub.c +8 -0
+				memset(object, 0, s->object_size);
+		}
+		c->tid = next_tid(c->tid);
+
+		local_irq_enable();
+	}
+
+	return __kmem_cache_alloc_bulk(s, flags, size, p);
 }
 EXPORT_SYMBOL(kmem_cache_alloc_bulk);

Now I found that we need to call slab_pre_alloc_hook() before any operation on kmem_cache to support kmemcg accounting. And, we need to call slab_post_alloc_hook() on every allocated objects to support many debugging features like as kasan and kmemleak

Thanks.

#7 lore raw

Re: [PATCH 2/7] slub bulk alloc: extract objects from the per cpu slab

Quoted 4 lines · Joonsoo Kim

Now I found that we need to call slab_pre_alloc_hook() before any operation on kmem_cache to support kmemcg accounting. And, we need to call slab_post_alloc_hook() on every allocated objects to support many debugging features like as kasan and kmemleak

Use the fallback function for any debugging avoids that. This needs to be fast. If the performance is not wanted (debugging etc active) then the fallback should be fine.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

maintainer
#8 lore raw

Re: [PATCH 2/7] slub bulk alloc: extract objects from the per cpu slab

In reply to Jesper Dangaard Brouer
Quoted 42 lines · On Mon, 15 Jun 2015 17:52:07 +0200 Jesper Dangaard Brouer <[email protected]>…

From: Christoph Lameter <[email protected]>

[NOTICE: Already in AKPM's quilt-queue]

First piece: acceleration of retrieval of per cpu objects

If we are allocating lots of objects then it is advantageous to disable interrupts and avoid the this_cpu_cmpxchg() operation to get these objects faster.

Note that we cannot do the fast operation if debugging is enabled, because we would have to add extra code to do all the debugging checks. And it would not be fast anyway.

Note also that the requirement of having interrupts disabled avoids having to do processor flag operations.

Allocate as many objects as possible in the fast way and then fall back to the generic implementation for the rest of the objects.

...

mm/slub.c +13 -1
@@ -2759,7 +2759,32 @@ EXPORT_SYMBOL(kmem_cache_free_bulk);
 bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 								void **p)
 {
-	return kmem_cache_alloc_bulk(s, flags, size, p);
+	if (!kmem_cache_debug(s)) {
+		struct kmem_cache_cpu *c;
+
+		/* Drain objects in the per cpu slab */
+		local_irq_disable();
+		c = this_cpu_ptr(s->cpu_slab);
+
+		while (size) {
+			void *object = c->freelist;
+
+			if (!object)
+				break;
+

mm/slub.c EXPORT_SYMBOL(kmem_cache_free_bulk); · line 2784

Quoted 10 lines
mm/slub.c +10 -0
+			c->freelist = get_freepointer(s, object);
+			*p++ = object;
+			size--;
+
+			if (unlikely(flags & __GFP_ZERO))
+				memset(object, 0, s->object_size);
+		}
+		c->tid = next_tid(c->tid);
+
+		local_irq_enable();

It might be worth adding

		if (!size)
			return true;

here. To avoid the pointless call to __kmem_cache_alloc_bulk().

It depends on the typical success rate of this allocation loop. Do you know what this is?

Quoted 5 lines
mm/slub.c +3 -0
+	}
+
+	return __kmem_cache_alloc_bulk(s, flags, size, p);
 }
 EXPORT_SYMBOL(kmem_cache_alloc_bulk);
author
#9 lore raw

Re: [PATCH 2/7] slub bulk alloc: extract objects from the per cpu slab

Quoted 57 lines · On Tue, 16 Jun 2015 14:48:40 -0700 Andrew Morton <[email protected]>…
Quoted 42 lines · On Mon, 15 Jun 2015 17:52:07 +0200 Jesper Dangaard Brouer <[email protected]>…

From: Christoph Lameter <[email protected]>

[NOTICE: Already in AKPM's quilt-queue]

First piece: acceleration of retrieval of per cpu objects

If we are allocating lots of objects then it is advantageous to disable interrupts and avoid the this_cpu_cmpxchg() operation to get these objects faster.

Note that we cannot do the fast operation if debugging is enabled, because we would have to add extra code to do all the debugging checks. And it would not be fast anyway.

Note also that the requirement of having interrupts disabled avoids having to do processor flag operations.

Allocate as many objects as possible in the fast way and then fall back to the generic implementation for the rest of the objects.

...

mm/slub.c +13 -1
@@ -2759,7 +2759,32 @@ EXPORT_SYMBOL(kmem_cache_free_bulk);
 bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 								void **p)
 {
-	return kmem_cache_alloc_bulk(s, flags, size, p);
+	if (!kmem_cache_debug(s)) {
+		struct kmem_cache_cpu *c;
+
+		/* Drain objects in the per cpu slab */
+		local_irq_disable();
+		c = this_cpu_ptr(s->cpu_slab);
+
+		while (size) {
+			void *object = c->freelist;
+
+			if (!object)
+				break;
+

mm/slub.c EXPORT_SYMBOL(kmem_cache_free_bulk); · line 2784

Quoted 10 lines
mm/slub.c +10 -0
+			c->freelist = get_freepointer(s, object);
+			*p++ = object;
+			size--;
+
+			if (unlikely(flags & __GFP_ZERO))
+				memset(object, 0, s->object_size);
+		}
+		c->tid = next_tid(c->tid);
+
+		local_irq_enable();

It might be worth adding

Quoted 4 lines
		if (!size)
			return true;

here. To avoid the pointless call to __kmem_cache_alloc_bulk().

The pointless call did present a measurable performance hit (2ns), and I've removed it in the next patches, which fixes the error/exit path.

Signature · 11 lines
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

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
author
#10 lore raw

PATCH 3/7 slub: reduce indention level in kmem_cache_alloc_bulk()

In reply to Jesper Dangaard Brouer

Use kernel early return style to reduce indention level, by testing for kmem_cache_debug() and fallback to none-optimized bulking via __kmem_cache_alloc_bulk().

This also make it easier to fix a bug in the current implementation, in the next patch.

Signed-off-by Jesper Dangaard Brouer <[email protected]>
---
 mm/slub.c |   37 +++++++++++++++++++------------------
 1 file changed, 19 insertions(+), 18 deletions(-)
mm/slub.c +19 -18
index d18f8e195ac4..753f88bd8b40 100644
@@ -2757,32 +2757,33 @@ void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
 EXPORT_SYMBOL(kmem_cache_free_bulk);
 
 bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
-								void **p)
+			   void **p)
 {
-	if (!kmem_cache_debug(s)) {
-		struct kmem_cache_cpu *c;
+	struct kmem_cache_cpu *c;
 
-		/* Drain objects in the per cpu slab */
-		local_irq_disable();
-		c = this_cpu_ptr(s->cpu_slab);
+	/* Debugging fallback to generic bulk */
+	if (kmem_cache_debug(s))
+		return __kmem_cache_alloc_bulk(s, flags, size, p);
 
-		while (size) {
-			void *object = c->freelist;
+	/* Drain objects in the per cpu slab */
+	local_irq_disable();
+	c = this_cpu_ptr(s->cpu_slab);
 
-			if (!object)
-				break;
+	while (size) {
+		void *object = c->freelist;
 
-			c->freelist = get_freepointer(s, object);
-			*p++ = object;
-			size--;
+		if (!object)
+			break;
 
-			if (unlikely(flags & __GFP_ZERO))
-				memset(object, 0, s->object_size);
-		}
-		c->tid = next_tid(c->tid);
+		c->freelist = get_freepointer(s, object);
+		*p++ = object;
+		size--;
 
-		local_irq_enable();
+		if (unlikely(flags & __GFP_ZERO))
+			memset(object, 0, s->object_size);
 	}
+	c->tid = next_tid(c->tid);
+	local_irq_enable();
 
 	return __kmem_cache_alloc_bulk(s, flags, size, p);
 }
author
#11 lore raw

PATCH 4/7 slub: fix error path bug in kmem_cache_alloc_bulk

In reply to Jesper Dangaard Brouer

The current kmem_cache/SLAB bulking API need to release all objects in case the layer cannot satisfy the full request.

If __kmem_cache_alloc_bulk() fails, all allocated objects in array should be freed, but, __kmem_cache_alloc_bulk() can't know about objects allocated by this slub specific kmem_cache_alloc_bulk() function.

Signed-off-by Jesper Dangaard Brouer <[email protected]>
---
 mm/slub.c |   21 ++++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)
mm/slub.c +16 -5
index 753f88bd8b40..d10de5a33c03 100644
@@ -2760,24 +2760,27 @@ bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 			   void **p)
 {
 	struct kmem_cache_cpu *c;
+	int i;
 
 	/* Debugging fallback to generic bulk */
 	if (kmem_cache_debug(s))
 		return __kmem_cache_alloc_bulk(s, flags, size, p);
 
-	/* Drain objects in the per cpu slab */
+	/* Drain objects in the per cpu slab, while disabling local
+	 * IRQs, which protects against PREEMPT and interrupts
+	 * handlers invoking normal fastpath.
+	 */
 	local_irq_disable();
 	c = this_cpu_ptr(s->cpu_slab);
 
-	while (size) {
+	for (i = 0; i < size; i++) {
 		void *object = c->freelist;
 
 		if (!object)
 			break;
 
 		c->freelist = get_freepointer(s, object);
-		*p++ = object;
-		size--;
+		p[i] = object;
 
 		if (unlikely(flags & __GFP_ZERO))
 			memset(object, 0, s->object_size);

@@ -2785,7 +2788,15 @@ bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 	c->tid = next_tid(c->tid);
 	local_irq_enable();
 
-	return __kmem_cache_alloc_bulk(s, flags, size, p);
+	/* Fallback to single elem alloc */
+	for (; i < size; i++) {
+		void *x = p[i] = kmem_cache_alloc(s, flags);
+		if (unlikely(!x)) {
+			__kmem_cache_free_bulk(s, i, p);
+			return false;
+		}
+	}
+	return true;
 }
 EXPORT_SYMBOL(kmem_cache_alloc_bulk);
maintainer
#12 lore raw

Re: [PATCH 4/7] slub: fix error path bug in kmem_cache_alloc_bulk

Quoted 7 lines · On Mon, 15 Jun 2015 17:52:26 +0200 Jesper Dangaard Brouer <[email protected]>…

The current kmem_cache/SLAB bulking API need to release all objects in case the layer cannot satisfy the full request.

If __kmem_cache_alloc_bulk() fails, all allocated objects in array should be freed, but, __kmem_cache_alloc_bulk() can't know about objects allocated by this slub specific kmem_cache_alloc_bulk() function.

Can we fold patches 2, 3 and 4 into a single patch?

And maybe patch 5 as well. I don't think we need all these development-time increments in the permanent record.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

author
#13 lore raw

Re: [PATCH 4/7] slub: fix error path bug in kmem_cache_alloc_bulk

Quoted 10 lines · On Tue, 16 Jun 2015 14:51:09 -0700 Andrew Morton <[email protected]>…
Quoted 7 lines · On Mon, 15 Jun 2015 17:52:26 +0200 Jesper Dangaard Brouer <[email protected]>…

The current kmem_cache/SLAB bulking API need to release all objects in case the layer cannot satisfy the full request.

If __kmem_cache_alloc_bulk() fails, all allocated objects in array should be freed, but, __kmem_cache_alloc_bulk() can't know about objects allocated by this slub specific kmem_cache_alloc_bulk() function.

Quoted 4 lines

Can we fold patches 2, 3 and 4 into a single patch?

And maybe patch 5 as well. I don't think we need all these development-time increments in the permanent record.

I agree. I'll fold them when submitting V2

Signature · 11 lines
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

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
author
#14 lore raw

PATCH 5/7 slub: kmem_cache_alloc_bulk() move clearing outside IRQ disabled section

In reply to Jesper Dangaard Brouer

Move clearing of objects outside IRQ disabled section, to minimize time spend with local IRQs off.

Signed-off-by Jesper Dangaard Brouer <[email protected]>
---
 mm/slub.c |   11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)
mm/slub.c +8 -3
index d10de5a33c03..26f64005a347 100644
@@ -2781,13 +2781,18 @@ bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 
 		c->freelist = get_freepointer(s, object);
 		p[i] = object;
-
-		if (unlikely(flags & __GFP_ZERO))
-			memset(object, 0, s->object_size);
 	}
 	c->tid = next_tid(c->tid);
 	local_irq_enable();
 
+	/* Clear memory outside IRQ disabled fastpath loop */
+	if (unlikely(flags & __GFP_ZERO)) {
+		int j;
+
+		for (j = 0; j < i; j++)
+			memset(p[j], 0, s->object_size);
+	}
+
 	/* Fallback to single elem alloc */
 	for (; i < size; i++) {
 		void *x = p[i] = kmem_cache_alloc(s, flags);
author
#15 lore raw

PATCH 6/7 slub: improve bulk alloc strategy

In reply to Jesper Dangaard Brouer

Call slowpath __slab_alloc() from within the bulk loop, as the side-effect of this call likely repopulates c->freelist.

Choose to reenable local IRQs while calling slowpath.

Saving some optimizations for later. E.g. it is possible to extract parts of __slab_alloc() and avoid the unnecessary and expensive (37 cycles) local_irq_{save,restore}. For now, be happy calling __slab_alloc() this lower icache impact of this func and I don't have to worry about correctness.

Signed-off-by Jesper Dangaard Brouer <[email protected]>
---
 mm/slub.c |   27 +++++++++++++++++----------
 1 file changed, 17 insertions(+), 10 deletions(-)
mm/slub.c +17 -10
index 26f64005a347..98d0e6f73ec1 100644
@@ -2776,8 +2776,23 @@ bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 	for (i = 0; i < size; i++) {
 		void *object = c->freelist;
 
-		if (!object)
-			break;
+		if (unlikely(!object)) {
+			c->tid = next_tid(c->tid);
+			local_irq_enable();
+
+			/* Invoke slow path one time, then retry fastpath
+			 * as side-effect have updated c->freelist
+			 */
+			p[i] = __slab_alloc(s, flags, NUMA_NO_NODE,
+					    _RET_IP_, c);
+			if (unlikely(!p[i])) {
+				__kmem_cache_free_bulk(s, i, p);
+				return false;
+			}
+			local_irq_disable();
+			c = this_cpu_ptr(s->cpu_slab);
+			continue; /* goto for-loop */
+		}
 
 		c->freelist = get_freepointer(s, object);
 		p[i] = object;

@@ -2793,14 +2808,6 @@ bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 			memset(p[j], 0, s->object_size);
 	}
 
-	/* Fallback to single elem alloc */
-	for (; i < size; i++) {
-		void *x = p[i] = kmem_cache_alloc(s, flags);
-		if (unlikely(!x)) {
-			__kmem_cache_free_bulk(s, i, p);
-			return false;
-		}
-	}
 	return true;
 }
 EXPORT_SYMBOL(kmem_cache_alloc_bulk);
#16 lore raw

Re: [PATCH 6/7] slub: improve bulk alloc strategy

mm/slub.c bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 2780

Quoted 3 lines · Jesper Dangaard Brouer
mm/slub.c +2 -1
-			break;
+		if (unlikely(!object)) {
+			c->tid = next_tid(c->tid);

tid increment is not needed here since the per cpu information is not modified.

mm/slub.c bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 2788

Quoted 8 lines
mm/slub.c +8 -0
+			local_irq_enable();
+
+			/* Invoke slow path one time, then retry fastpath
+			 * as side-effect have updated c->freelist
+			 */
+			p[i] = __slab_alloc(s, flags, NUMA_NO_NODE,
+					    _RET_IP_, c);
+			if (unlikely(!p[i])) {

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

maintainer
#17 lore raw

Re: [PATCH 6/7] slub: improve bulk alloc strategy

In reply to Jesper Dangaard Brouer
Quoted 18 lines · On Mon, 15 Jun 2015 17:52:46 +0200 Jesper Dangaard Brouer <[email protected]>…

Call slowpath __slab_alloc() from within the bulk loop, as the side-effect of this call likely repopulates c->freelist.

Choose to reenable local IRQs while calling slowpath.

Saving some optimizations for later. E.g. it is possible to extract parts of __slab_alloc() and avoid the unnecessary and expensive (37 cycles) local_irq_{save,restore}. For now, be happy calling __slab_alloc() this lower icache impact of this func and I don't have to worry about correctness.

...

mm/slub.c +0 -0
@@ -2776,8 +2776,23 @@ bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 	for (i = 0; i < size; i++) {
 		void *object = c->freelist;

mm/slub.c bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 2785

Quoted 10 lines
mm/slub.c +7 -2
 
-		if (!object)
-			break;
+		if (unlikely(!object)) {
+			c->tid = next_tid(c->tid);
+			local_irq_enable();
+
+			/* Invoke slow path one time, then retry fastpath
+			 * as side-effect have updated c->freelist
+			 */

That isn't very grammatical.

Block comments are formatted

	/*
	 * like this
	 */

please.

mm/slub.c bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 2796

Quoted 11 lines
mm/slub.c +10 -0
+			p[i] = __slab_alloc(s, flags, NUMA_NO_NODE,
+					    _RET_IP_, c);
+			if (unlikely(!p[i])) {
+				__kmem_cache_free_bulk(s, i, p);
+				return false;
+			}
+			local_irq_disable();
+			c = this_cpu_ptr(s->cpu_slab);
+			continue; /* goto for-loop */
+		}

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

author
#18 lore raw

Re: [PATCH 6/7] slub: improve bulk alloc strategy

Quoted 2 lines · On Tue, 16 Jun 2015 14:53:36 -0700 Andrew Morton <[email protected]>…

On Mon, 15 Jun 2015 17:52:46 +0200 Jesper Dangaard Brouer <[email protected]> wrote:

[...]

Quoted 6 lines

mm/slub.c bool kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 2785

Quoted 3 lines
mm/slub.c +3 -0
+			/* Invoke slow path one time, then retry fastpath
+			 * as side-effect have updated c->freelist
+			 */

That isn't very grammatical.

Quoted 7 lines

Block comments are formatted

	/*
	 * like this
	 */

please.

Sure, old habit, this comment style is just that we use in net/ tree.

Signature · 5 lines
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
author
#19 lore raw

PATCH 7/7 slub: initial bulk free implementation

In reply to Jesper Dangaard Brouer

This implements SLUB specific kmem_cache_free_bulk(). SLUB allocator now both have bulk alloc and free implemented.

Play nice and reenable local IRQs while calling slowpath.

Signed-off-by Jesper Dangaard Brouer <[email protected]>
---
 mm/slub.c |   32 +++++++++++++++++++++++++++++++-
 1 file changed, 31 insertions(+), 1 deletion(-)
mm/slub.c +31 -1
index 98d0e6f73ec1..cc4f870677bb 100644
@@ -2752,7 +2752,37 @@ EXPORT_SYMBOL(kmem_cache_free);
 
 void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
 {
-	__kmem_cache_free_bulk(s, size, p);
+	struct kmem_cache_cpu *c;
+	struct page *page;
+	int i;
+
+	local_irq_disable();
+	c = this_cpu_ptr(s->cpu_slab);
+
+	for (i = 0; i < size; i++) {
+		void *object = p[i];
+
+		if (unlikely(!object))
+			continue; // HOW ABOUT BUG_ON()???
+
+		page = virt_to_head_page(object);
+		BUG_ON(s != page->slab_cache); /* Check if valid slab page */
+
+		if (c->page == page) {
+			/* Fastpath: local CPU free */
+			set_freepointer(s, object, c->freelist);
+			c->freelist = object;
+		} else {
+			c->tid = next_tid(c->tid);
+			local_irq_enable();
+			/* Slowpath: overhead locked cmpxchg_double_slab */
+			__slab_free(s, page, object, _RET_IP_);
+			local_irq_disable();
+			c = this_cpu_ptr(s->cpu_slab);
+		}
+	}
+	c->tid = next_tid(c->tid);
+	local_irq_enable();
 }
 EXPORT_SYMBOL(kmem_cache_free_bulk);
#20 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2766

Quoted 5 lines · Jesper Dangaard Brouer
mm/slub.c +5 -0
+	for (i = 0; i < size; i++) {
+		void *object = p[i];
+
+		if (unlikely(!object))
+			continue; // HOW ABOUT BUG_ON()???

Sure BUG_ON would be fitting here.

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2769

Quoted 3 lines
mm/slub.c +3 -0
+
+		page = virt_to_head_page(object);
+		BUG_ON(s != page->slab_cache); /* Check if valid slab page */

This is the check if the slab page belongs to the slab cache we are interested in.

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2776

Quoted 7 lines
mm/slub.c +7 -0
+
+		if (c->page == page) {
+			/* Fastpath: local CPU free */
+			set_freepointer(s, object, c->freelist);
+			c->freelist = object;
+		} else {
+			c->tid = next_tid(c->tid);

tids are only useful for the fastpath. No need to fiddle around with them for the slowpath.

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2778

Quoted 2 lines
mm/slub.c +2 -0
+			local_irq_enable();
+			/* Slowpath: overhead locked cmpxchg_double_slab */

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

author
#21 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

Quoted 9 lines · On Mon, 15 Jun 2015 11:34:44 -0500 (CDT) Christoph Lameter <[email protected]> wrote:

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2766

Quoted 5 lines · Jesper Dangaard Brouer
mm/slub.c +5 -0
+	for (i = 0; i < size; i++) {
+		void *object = p[i];
+
+		if (unlikely(!object))
+			continue; // HOW ABOUT BUG_ON()???

Sure BUG_ON would be fitting here.

Okay, will do in V2.

Quoted 6 lines

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2769

Quoted 3 lines
mm/slub.c +3 -0
+
+		page = virt_to_head_page(object);
+		BUG_ON(s != page->slab_cache); /* Check if valid slab page */

This is the check if the slab page belongs to the slab cache we are interested in.

Is this appropriate to keep on this fastpath? (I copied the check from one of your earlier patches)

Quoted 10 lines

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2776

Quoted 7 lines
mm/slub.c +7 -0
+
+		if (c->page == page) {
+			/* Fastpath: local CPU free */
+			set_freepointer(s, object, c->freelist);
+			c->freelist = object;
+		} else {
+			c->tid = next_tid(c->tid);

tids are only useful for the fastpath. No need to fiddle around with them for the slowpath.

Okay, understood.

Quoted 2 lines
Quoted 2 lines
mm/slub.c +2 -0
+			local_irq_enable();
+			/* Slowpath: overhead locked cmpxchg_double_slab */
Signature · 11 lines
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

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#22 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

In reply to Jesper Dangaard Brouer
Quoted 42 lines · Jesper Dangaard Brouer

This implements SLUB specific kmem_cache_free_bulk(). SLUB allocator now both have bulk alloc and free implemented.

Play nice and reenable local IRQs while calling slowpath.

Signed-off-by Jesper Dangaard Brouer <[email protected]>
---
  mm/slub.c |   32 +++++++++++++++++++++++++++++++-
  1 file changed, 31 insertions(+), 1 deletion(-)
mm/slub.c +23 -1
index 98d0e6f73ec1..cc4f870677bb 100644
@@ -2752,7 +2752,37 @@ EXPORT_SYMBOL(kmem_cache_free);
 
  void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
  {
-	__kmem_cache_free_bulk(s, size, p);
+	struct kmem_cache_cpu *c;
+	struct page *page;
+	int i;
+
+	local_irq_disable();
+	c = this_cpu_ptr(s->cpu_slab);
+
+	for (i = 0; i < size; i++) {
+		void *object = p[i];
+
+		if (unlikely(!object))
+			continue; // HOW ABOUT BUG_ON()???
+
+		page = virt_to_head_page(object);
+		BUG_ON(s != page->slab_cache); /* Check if valid slab page */
+
+		if (c->page == page) {
+			/* Fastpath: local CPU free */
+			set_freepointer(s, object, c->freelist);
+			c->freelist = object;
+		} else {
+			c->tid = next_tid(c->tid);
+			local_irq_enable();

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2787

Quoted 10 lines
mm/slub.c +8 -0
+			/* Slowpath: overhead locked cmpxchg_double_slab */
+			__slab_free(s, page, object, _RET_IP_);
+			local_irq_disable();
+			c = this_cpu_ptr(s->cpu_slab);
+		}
+	}
+	c->tid = next_tid(c->tid);
+	local_irq_enable();
  }
  EXPORT_SYMBOL(kmem_cache_free_bulk);

So if the idea is to batch the freeing maybe you should look at doing the freeing in two passes. The first would be to free all those buffers that share their page with the percpu slab. Then you could just free everything else in the second pass after you have re-enabled IRQs.

- Alex

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#23 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

In reply to Jesper Dangaard Brouer
Quoted 24 lines · Jesper Dangaard Brouer

This implements SLUB specific kmem_cache_free_bulk(). SLUB allocator now both have bulk alloc and free implemented.

Play nice and reenable local IRQs while calling slowpath.

Signed-off-by Jesper Dangaard Brouer <[email protected]>
---
 mm/slub.c |   32 +++++++++++++++++++++++++++++++-
 1 file changed, 31 insertions(+), 1 deletion(-)
mm/slub.c +5 -1
index 98d0e6f73ec1..cc4f870677bb 100644
@@ -2752,7 +2752,37 @@ EXPORT_SYMBOL(kmem_cache_free);
 
 void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
 {
-	__kmem_cache_free_bulk(s, size, p);
+	struct kmem_cache_cpu *c;
+	struct page *page;
+	int i;
+
+	local_irq_disable();

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2769

Quoted 10 lines
mm/slub.c +10 -0
+	c = this_cpu_ptr(s->cpu_slab);
+
+	for (i = 0; i < size; i++) {
+		void *object = p[i];
+
+		if (unlikely(!object))
+			continue; // HOW ABOUT BUG_ON()???
+
+		page = virt_to_head_page(object);
+		BUG_ON(s != page->slab_cache); /* Check if valid slab page */

You need to use cache_from_objt() to support kmemcg accounting. And, slab_free_hook() should be called before free.

Thanks.

author
#24 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

Quoted 30 lines · On Tue, 16 Jun 2015 16:23:28 +0900 Joonsoo Kim <[email protected]> wrote:
Quoted 29 lines · Jesper Dangaard Brouer

This implements SLUB specific kmem_cache_free_bulk(). SLUB allocator now both have bulk alloc and free implemented.

Play nice and reenable local IRQs while calling slowpath.

Signed-off-by Jesper Dangaard Brouer <[email protected]>
---
 mm/slub.c |   32 +++++++++++++++++++++++++++++++-
 1 file changed, 31 insertions(+), 1 deletion(-)
mm/slub.c +10 -1
index 98d0e6f73ec1..cc4f870677bb 100644
@@ -2752,7 +2752,37 @@ EXPORT_SYMBOL(kmem_cache_free);
 
 void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
 {
-	__kmem_cache_free_bulk(s, size, p);
+	struct kmem_cache_cpu *c;
+	struct page *page;
+	int i;
+
+	local_irq_disable();
+	c = this_cpu_ptr(s->cpu_slab);
+
+	for (i = 0; i < size; i++) {
+		void *object = p[i];
+
Quoted 8 lines

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2769

Quoted 5 lines
mm/slub.c +5 -0
+		if (unlikely(!object))
+			continue; // HOW ABOUT BUG_ON()???
+
+		page = virt_to_head_page(object);
+		BUG_ON(s != page->slab_cache); /* Check if valid slab page */

You need to use cache_from_objt() to support kmemcg accounting. And, slab_free_hook() should be called before free.

Okay, but Christoph choose to not support kmem_cache_debug() in patch2/7.

Should we/I try to add kmem cache debugging support?

If adding these, then I would also need to add those on alloc path...

Signature · 11 lines
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

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#25 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

2015-06-16 18:20 GMT+09:00 Jesper Dangaard Brouer <[email protected]>:

Quoted 42 lines
Quoted 30 lines · On Tue, 16 Jun 2015 16:23:28 +0900 Joonsoo Kim <[email protected]> wrote:
Quoted 29 lines · Jesper Dangaard Brouer

This implements SLUB specific kmem_cache_free_bulk(). SLUB allocator now both have bulk alloc and free implemented.

Play nice and reenable local IRQs while calling slowpath.

Signed-off-by Jesper Dangaard Brouer <[email protected]>
---
 mm/slub.c |   32 +++++++++++++++++++++++++++++++-
 1 file changed, 31 insertions(+), 1 deletion(-)
mm/slub.c +10 -1
index 98d0e6f73ec1..cc4f870677bb 100644
@@ -2752,7 +2752,37 @@ EXPORT_SYMBOL(kmem_cache_free);
 
 void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
 {
-   __kmem_cache_free_bulk(s, size, p);
+   struct kmem_cache_cpu *c;
+   struct page *page;
+   int i;
+
+   local_irq_disable();
+   c = this_cpu_ptr(s->cpu_slab);
+
+   for (i = 0; i < size; i++) {
+           void *object = p[i];
+
Quoted 8 lines

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2769

Quoted 5 lines
mm/slub.c +5 -0
+           if (unlikely(!object))
+                   continue; // HOW ABOUT BUG_ON()???
+
+           page = virt_to_head_page(object);
+           BUG_ON(s != page->slab_cache); /* Check if valid slab page */

You need to use cache_from_objt() to support kmemcg accounting. And, slab_free_hook() should be called before free.

Quoted 3 lines

Okay, but Christoph choose to not support kmem_cache_debug() in patch2/7.

Should we/I try to add kmem cache debugging support?

kmem_cache_debug() is the check for slab internal debugging feature. slab_free_hook() and others mentioned from me are also related to external debugging features like as kasan and kmemleak. So, even if debugged kmem_cache isn't supported by bulk API, external debugging feature should be supported.

Quoted 1 line

If adding these, then I would also need to add those on alloc path...

Yes, please.

Thanks.

author
#26 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

Quoted 10 lines · On Tue, 16 Jun 2015 21:00:39 +0900 Joonsoo Kim <[email protected]> wrote:
Quoted 3 lines

Okay, but Christoph choose to not support kmem_cache_debug() in patch2/7.

Should we/I try to add kmem cache debugging support?

kmem_cache_debug() is the check for slab internal debugging feature. slab_free_hook() and others mentioned from me are also related to external debugging features like as kasan and kmemleak. So, even if debugged kmem_cache isn't supported by bulk API, external debugging feature should be supported.

Quoted 3 lines
Quoted 1 line

If adding these, then I would also need to add those on alloc path...

Yes, please.

I've added a patch 8 to my queue, that (tries to) implement this. Currently trying to figure out how to "use" these debugging features, so I activate that code path.

Signature · 11 lines
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

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#27 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

In reply to Joonsoo Kim
Quoted 3 lines · Joonsoo Kim
Quoted 1 line

If adding these, then I would also need to add those on alloc path...

Yes, please.

Lets fall back to the generic implementation for any of these things. We need to focus on maximum performance in these functions. The more special cases we have to handle the more all of this gets compromised.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#28 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

In reply to Jesper Dangaard Brouer
Quoted 36 lines · Jesper Dangaard Brouer

This implements SLUB specific kmem_cache_free_bulk(). SLUB allocator now both have bulk alloc and free implemented.

Play nice and reenable local IRQs while calling slowpath.

Signed-off-by Jesper Dangaard Brouer <[email protected]>
---
 mm/slub.c |   32 +++++++++++++++++++++++++++++++-
 1 file changed, 31 insertions(+), 1 deletion(-)
mm/slub.c +17 -1
index 98d0e6f73ec1..cc4f870677bb 100644
@@ -2752,7 +2752,37 @@ EXPORT_SYMBOL(kmem_cache_free);
 
 void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
 {
-	__kmem_cache_free_bulk(s, size, p);
+	struct kmem_cache_cpu *c;
+	struct page *page;
+	int i;
+
+	local_irq_disable();
+	c = this_cpu_ptr(s->cpu_slab);
+
+	for (i = 0; i < size; i++) {
+		void *object = p[i];
+
+		if (unlikely(!object))
+			continue; // HOW ABOUT BUG_ON()???
+
+		page = virt_to_head_page(object);
+		BUG_ON(s != page->slab_cache); /* Check if valid slab page */
+
+		if (c->page == page) {

mm/slub.c EXPORT_SYMBOL(kmem_cache_free); · line 2781

Quoted 10 lines
mm/slub.c +10 -0
+			/* Fastpath: local CPU free */
+			set_freepointer(s, object, c->freelist);
+			c->freelist = object;
+		} else {
+			c->tid = next_tid(c->tid);
+			local_irq_enable();
+			/* Slowpath: overhead locked cmpxchg_double_slab */
+			__slab_free(s, page, object, _RET_IP_);
+			local_irq_disable();
+			c = this_cpu_ptr(s->cpu_slab);

SLUB free path doesn't need to irq management in many cases although it uses cmpxchg_doule_slab. Is this really better than just calling __kmem_cache_free_bulk()?

Thanks.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

author
#29 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

Quoted 1 line · On Tue, 16 Jun 2015 16:28:06 +0900 Joonsoo Kim <[email protected]> wrote:

Is this really better than just calling __kmem_cache_free_bulk()?

Yes, as can be seen by cover-letter, but my cover-letter does not seem to have reached mm-list.

Measurements for the entire patchset:

Bulk - Fallback bulking           - fastpath-bulking
   1 -  47 cycles(tsc) 11.921 ns  -  45 cycles(tsc) 11.461 ns   improved  4.3%
   2 -  46 cycles(tsc) 11.649 ns  -  28 cycles(tsc)  7.023 ns   improved 39.1%
   3 -  46 cycles(tsc) 11.550 ns  -  22 cycles(tsc)  5.671 ns   improved 52.2%
   4 -  45 cycles(tsc) 11.398 ns  -  19 cycles(tsc)  4.967 ns   improved 57.8%
   8 -  45 cycles(tsc) 11.303 ns  -  17 cycles(tsc)  4.298 ns   improved 62.2%
  16 -  44 cycles(tsc) 11.221 ns  -  17 cycles(tsc)  4.423 ns   improved 61.4%
  30 -  75 cycles(tsc) 18.894 ns  -  57 cycles(tsc) 14.497 ns   improved 24.0%
  32 -  73 cycles(tsc) 18.491 ns  -  56 cycles(tsc) 14.227 ns   improved 23.3%
  34 -  75 cycles(tsc) 18.962 ns  -  58 cycles(tsc) 14.638 ns   improved 22.7%
  48 -  80 cycles(tsc) 20.049 ns  -  64 cycles(tsc) 16.247 ns   improved 20.0%
  64 -  87 cycles(tsc) 21.929 ns  -  74 cycles(tsc) 18.598 ns   improved 14.9%
 128 -  98 cycles(tsc) 24.511 ns  -  89 cycles(tsc) 22.295 ns   improved  9.2%
 158 - 101 cycles(tsc) 25.389 ns  -  93 cycles(tsc) 23.390 ns   improved  7.9%
 250 - 104 cycles(tsc) 26.170 ns  - 100 cycles(tsc) 25.112 ns   improved  3.8%

I'll do a compare against the previous patch, and post the results.

Signature · 5 lines
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
author
#30 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

Quoted 26 lines · On Tue, 16 Jun 2015 10:21:10 +0200 Jesper Dangaard Brouer <[email protected]>…
Quoted 1 line · On Tue, 16 Jun 2015 16:28:06 +0900 Joonsoo Kim <[email protected]> wrote:

Is this really better than just calling __kmem_cache_free_bulk()?

Yes, as can be seen by cover-letter, but my cover-letter does not seem to have reached mm-list.

Measurements for the entire patchset:

Bulk - Fallback bulking           - fastpath-bulking
   1 -  47 cycles(tsc) 11.921 ns  -  45 cycles(tsc) 11.461 ns   improved  4.3%
   2 -  46 cycles(tsc) 11.649 ns  -  28 cycles(tsc)  7.023 ns   improved 39.1%
   3 -  46 cycles(tsc) 11.550 ns  -  22 cycles(tsc)  5.671 ns   improved 52.2%
   4 -  45 cycles(tsc) 11.398 ns  -  19 cycles(tsc)  4.967 ns   improved 57.8%
   8 -  45 cycles(tsc) 11.303 ns  -  17 cycles(tsc)  4.298 ns   improved 62.2%
  16 -  44 cycles(tsc) 11.221 ns  -  17 cycles(tsc)  4.423 ns   improved 61.4%
  30 -  75 cycles(tsc) 18.894 ns  -  57 cycles(tsc) 14.497 ns   improved 24.0%
  32 -  73 cycles(tsc) 18.491 ns  -  56 cycles(tsc) 14.227 ns   improved 23.3%
  34 -  75 cycles(tsc) 18.962 ns  -  58 cycles(tsc) 14.638 ns   improved 22.7%
  48 -  80 cycles(tsc) 20.049 ns  -  64 cycles(tsc) 16.247 ns   improved 20.0%
  64 -  87 cycles(tsc) 21.929 ns  -  74 cycles(tsc) 18.598 ns   improved 14.9%
 128 -  98 cycles(tsc) 24.511 ns  -  89 cycles(tsc) 22.295 ns   improved  9.2%
 158 - 101 cycles(tsc) 25.389 ns  -  93 cycles(tsc) 23.390 ns   improved  7.9%
 250 - 104 cycles(tsc) 26.170 ns  - 100 cycles(tsc) 25.112 ns   improved  3.8%
Quoted 1 line

I'll do a compare against the previous patch, and post the results.

Compare against previous patch:

Run: previous-patch - this patch

  1 -   49 cycles(tsc) 12.378 ns -  43 cycles(tsc) 10.775 ns  improved 12.2%
  2 -   37 cycles(tsc)  9.297 ns -  26 cycles(tsc)  6.652 ns  improved 29.7%
  3 -   33 cycles(tsc)  8.348 ns -  21 cycles(tsc)  5.347 ns  improved 36.4%
  4 -   31 cycles(tsc)  7.930 ns -  18 cycles(tsc)  4.669 ns  improved 41.9%
  8 -   30 cycles(tsc)  7.693 ns -  17 cycles(tsc)  4.404 ns  improved 43.3%
 16 -   32 cycles(tsc)  8.059 ns -  17 cycles(tsc)  4.493 ns  improved 46.9%
 30 -   65 cycles(tsc) 16.345 ns -  59 cycles(tsc) 14.858 ns  improved  9.2%
 32 -   64 cycles(tsc) 16.170 ns -  56 cycles(tsc) 14.074 ns  improved 12.5%
 34 -   66 cycles(tsc) 16.645 ns -  55 cycles(tsc) 13.882 ns  improved 16.7%
 48 -   78 cycles(tsc) 19.581 ns -  65 cycles(tsc) 16.266 ns  improved 16.7%
 64 -   81 cycles(tsc) 20.428 ns -  77 cycles(tsc) 19.432 ns  improved  4.9%
128 -   92 cycles(tsc) 23.030 ns -  78 cycles(tsc) 19.650 ns  improved 15.2%
158 -   94 cycles(tsc) 23.581 ns -  83 cycles(tsc) 20.953 ns  improved 11.7%
250 -   96 cycles(tsc) 24.175 ns -  93 cycles(tsc) 23.444 ns  improved  3.1%

This mostly amortize the less-heavy none-locked cmpxchg_double used on fastpath. As I demonstrated earlier this fastpath cmpxchg is approx 38% of the fastpath cost.

Thus, yes, doing bulk free this way is faster ;-)

Signature · 11 lines
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

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#31 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

2015-06-16 17:57 GMT+09:00 Jesper Dangaard Brouer <[email protected]>:

Quoted 33 lines
Quoted 26 lines · On Tue, 16 Jun 2015 10:21:10 +0200 Jesper Dangaard Brouer <[email protected]>…
Quoted 1 line · On Tue, 16 Jun 2015 16:28:06 +0900 Joonsoo Kim <[email protected]> wrote:

Is this really better than just calling __kmem_cache_free_bulk()?

Yes, as can be seen by cover-letter, but my cover-letter does not seem to have reached mm-list.

Measurements for the entire patchset:

Bulk - Fallback bulking           - fastpath-bulking
   1 -  47 cycles(tsc) 11.921 ns  -  45 cycles(tsc) 11.461 ns   improved  4.3%
   2 -  46 cycles(tsc) 11.649 ns  -  28 cycles(tsc)  7.023 ns   improved 39.1%
   3 -  46 cycles(tsc) 11.550 ns  -  22 cycles(tsc)  5.671 ns   improved 52.2%
   4 -  45 cycles(tsc) 11.398 ns  -  19 cycles(tsc)  4.967 ns   improved 57.8%
   8 -  45 cycles(tsc) 11.303 ns  -  17 cycles(tsc)  4.298 ns   improved 62.2%
  16 -  44 cycles(tsc) 11.221 ns  -  17 cycles(tsc)  4.423 ns   improved 61.4%
  30 -  75 cycles(tsc) 18.894 ns  -  57 cycles(tsc) 14.497 ns   improved 24.0%
  32 -  73 cycles(tsc) 18.491 ns  -  56 cycles(tsc) 14.227 ns   improved 23.3%
  34 -  75 cycles(tsc) 18.962 ns  -  58 cycles(tsc) 14.638 ns   improved 22.7%
  48 -  80 cycles(tsc) 20.049 ns  -  64 cycles(tsc) 16.247 ns   improved 20.0%
  64 -  87 cycles(tsc) 21.929 ns  -  74 cycles(tsc) 18.598 ns   improved 14.9%
 128 -  98 cycles(tsc) 24.511 ns  -  89 cycles(tsc) 22.295 ns   improved  9.2%
 158 - 101 cycles(tsc) 25.389 ns  -  93 cycles(tsc) 23.390 ns   improved  7.9%
 250 - 104 cycles(tsc) 26.170 ns  - 100 cycles(tsc) 25.112 ns   improved  3.8%
Quoted 1 line

I'll do a compare against the previous patch, and post the results.

Compare against previous patch:

Quoted 7 lines

Run: previous-patch - this patch

  1 -   49 cycles(tsc) 12.378 ns -  43 cycles(tsc) 10.775 ns  improved 12.2%
  2 -   37 cycles(tsc)  9.297 ns -  26 cycles(tsc)  6.652 ns  improved 29.7%
  3 -   33 cycles(tsc)  8.348 ns -  21 cycles(tsc)  5.347 ns  improved 36.4%
  4 -   31 cycles(tsc)  7.930 ns -  18 cycles(tsc)  4.669 ns  improved 41.9%
  8 -   30 cycles(tsc)  7.693 ns -  17 cycles(tsc)  4.404 ns  improved 43.3%
 16 -   32 cycles(tsc)  8.059 ns -  17 cycles(tsc)  4.493 ns  improved 46.9%

So, in your test, most of objects may come from one or two slabs and your algorithm is well optimized for this case. But, is this workload normal case? If most of objects comes from many different slabs, bulk free API does enabling/disabling interrupt very much so I guess it work worse than just calling __kmem_cache_free_bulk(). Could you test this case?

Thanks.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#32 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

Quoted 2 lines · Joonsoo Kim

So, in your test, most of objects may come from one or two slabs and your algorithm is well optimized for this case. But, is this workload normal case?

It is normal if the objects were bulk allocated because SLUB ensures that all objects are first allocated from one page before moving to another.

Quoted 3 lines

If most of objects comes from many different slabs, bulk free API does enabling/disabling interrupt very much so I guess it work worse than just calling __kmem_cache_free_bulk(). Could you test this case?

In case of SLAB this would be an issue since the queueing mechanism destroys spatial locality. This is much less an issue for SLUB.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

author
#33 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

Quoted 7 lines · On Tue, 16 Jun 2015 10:10:25 -0500 (CDT) Christoph Lameter <[email protected]> wrote:
Quoted 2 lines · Joonsoo Kim

So, in your test, most of objects may come from one or two slabs and your algorithm is well optimized for this case. But, is this workload normal case?

It is normal if the objects were bulk allocated because SLUB ensures that all objects are first allocated from one page before moving to another.

Yes, exactly. Maybe SLAB is different? If so, then we can handle that in the SLAB specific bulk implementation.

Quoted 6 lines
Quoted 3 lines

If most of objects comes from many different slabs, bulk free API does enabling/disabling interrupt very much so I guess it work worse than just calling __kmem_cache_free_bulk(). Could you test this case?

In case of SLAB this would be an issue since the queueing mechanism destroys spatial locality. This is much less an issue for SLUB.

I think Kim is worried about the cost of the enable/disable calls, when the slowpath gets called. But it is not a problem because the cost of local_irq_{disable,enable} is very low (total cost 7 cycles).

It is very important that everybody realizes that the save+restore variant is very expensive, this is key:

CPU: i7-4790K CPU @ 4.00GHz
* local_irq_{disable,enable}: 7 cycles(tsc) - 1.821 ns
* local_irq_{save,restore} : 37 cycles(tsc) - 9.443 ns

Even if EVERY object need to call slowpath/__slab_free() it will be faster than calling the fallback. Because I've demonstrated the call this_cpu_cmpxchg_double() costs 9 cycles.

Signature · 10 lines
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

p.s. for comparison[1] a function call cost is 5-6 cycles, and a function
pointer call cost is 6-10 cycles, depending on CPU.

[1] https://github.com/netoptimizer/prototype-kernel/blob/master/kernel/lib/time_bench_sample.c
#34 lore raw

Re: [PATCH 7/7] slub: initial bulk free implementation

Quoted 10 lines · Jesper Dangaard Brouer

It is very important that everybody realizes that the save+restore variant is very expensive, this is key:

CPU: i7-4790K CPU @ 4.00GHz
* local_irq_{disable,enable}: 7 cycles(tsc) - 1.821 ns
* local_irq_{save,restore} : 37 cycles(tsc) - 9.443 ns

Even if EVERY object need to call slowpath/__slab_free() it will be faster than calling the fallback. Because I've demonstrated the call this_cpu_cmpxchg_double() costs 9 cycles.

But the cmpxchg also stores a value. You need to add the cost of the store to the cycles.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>