SLQB slab allocator

RFC PATCH In review Nick Piggin 6 participants 21 messages Dec 12, 2008 – Dec 19, 2008

Subsystems (7)

Networking Memory management x86 Library code +3 more subsystems

lore

Share & tools

lore

Nick Piggin

author

2008-12-12 00:25 UTC #0 lore raw

RFC PATCH 1/1 SLQB slab allocator

(Re)introducing SLQB allocator. Q for queued, but in reality, SLAB and SLUB also have queues of things as well, so "Q" is just a meaningless differentiator :)

I've kept working on SLQB slab allocator because I don't agree with the design choices in SLUB, and I'm worried about the push to make it the one true allocator.

My primary goal in SLQB is performance, secondarily are order-0 page allocations, and memory consumption.

I have worked with the Linux guys at Intel to ensure that SLQB is comparable to SLAB in their OLTP performance benchmark. Recently that goal has been reached -- so SLQB performs comparably well to SLAB on that test (it's within the noise).

I've also been comparing SLQB with SLAB and SLUB in other benchmarks, and trying to ensure it is as good or better. I don't know if that's always the case, but nothing obvious has gone wrong (it's sometimes hard to find meaningful benchmarks that exercise slab in interesting ways).

Now it isn't exactly complete -- debugging, tracking, stats, etc. code is not always in the best shape, however I have been focusing on performance of the core allocator. No matter how good the rest is if the core code is poor... But it boots, works, is pretty stable.

SLQB, like SLUB and unlike SLAB, doesn't have greater than linear memory consumption growth with the number of CPUs or nodes.

SLQB tries to be very page-size agnostic. And it tries very hard to use order-0 pages. This is good for both page allocator fragmentation, and slab fragmentation. I don't like that SLUB performs significantly worse with order-0 pages in some workloads.

SLQB goes to some lengths to optimise remote-freeing cases (allocate on one CPU, free on another). It seems to work well, but there are a *lot* of possible ways this can be implemented especially when NUMA comes into play, so I'd like to know of workloads where remote freeing happens a lot, and perhaps look at alternative ways to do it.

SLQB initialistaion code attempts to be as simple and un-clever as possible. There are no multiple phases where different things come up. There is no weird self bootstrapping stuff. It just statically allocates the structures required to create the slabs that allocate other slab structures.

I'm going to continue working on this as I get time, and I plan to soon ask to have it merged. It would be great if people could comment or test it.

---
 arch/x86/include/asm/page.h |    1
 include/linux/mm.h          |    4
 include/linux/rcu_types.h   |   18
 include/linux/rcupdate.h    |   11
 include/linux/slab.h        |    6
 include/linux/slqb_def.h    |  258 ++++
 include/linux/vmstat.h      |   16
 init/Kconfig                |   10
 lib/Kconfig.debug           |   10
 mm/Makefile                 |    1
 mm/slqb.c                   | 2824 ++++++++++++++++++++++++++++++++++++++++++++
 mm/vmstat.c                 |   15
 12 files changed, 3161 insertions(+), 13 deletions(-)

include/linux/rcupdate.h +1 ~~-10~~

Index: linux-2.6/include/linux/rcupdate.h
===================================================================
@@ -33,6 +33,7 @@
 #ifndef __LINUX_RCUPDATE_H
 #define __LINUX_RCUPDATE_H
 
+#include <linux/rcu_types.h>
 #include <linux/cache.h>
 #include <linux/spinlock.h>
 #include <linux/threads.h>

@@ -42,16 +43,6 @@
 #include <linux/lockdep.h>
 #include <linux/completion.h>
 
-/**
- * struct rcu_head - callback structure for use with RCU
- * @next: next update requests in a list
- * @func: actual update function to call after the grace period.
- */
-struct rcu_head {
-	struct rcu_head *next;
-	void (*func)(struct rcu_head *head);
-};
-
 #ifdef CONFIG_CLASSIC_RCU
 #include <linux/rcuclassic.h>
 #else /* #ifdef CONFIG_CLASSIC_RCU */

include/linux/slqb_def.h new file +258 -0

258 lines not on this page · raw message

init/Kconfig +9 -1

Index: linux-2.6/init/Kconfig
===================================================================
@@ -760,6 +760,11 @@ config SLUB_DEBUG
 	  SLUB sysfs support. /sys/slab will not exist and there will be
 	  no support for cache validation etc.
 
+config SLQB_DEBUG
+	default y
+	bool "Enable SLQB debugging support"
+	depends on SLQB
+
 choice
 	prompt "Choose SLAB allocator"
 	default SLUB

@@ -783,6 +788,9 @@ config SLUB
 	   and has enhanced diagnostics. SLUB is the default choice for
 	   a slab allocator.
 
+config SLQB
+	bool "SLQB (Qeued allocator)"
+
 config SLOB
 	depends on EMBEDDED
 	bool "SLOB (Simple Allocator)"

@@ -823,7 +831,7 @@ config HAVE_GENERIC_DMA_COHERENT
 config SLABINFO
 	bool
 	depends on PROC_FS
-	depends on SLAB || SLUB_DEBUG
+	depends on SLAB || SLUB_DEBUG || SLQB
 	default y
 
 config RT_MUTEXES

lib/Kconfig.debug +10 -0

Index: linux-2.6/lib/Kconfig.debug
===================================================================
@@ -290,6 +290,16 @@ config SLUB_STATS
 	  out which slabs are relevant to a particular load.
 	  Try running: slabinfo -DA
 
+config SLQB_DEBUG_ON
+	bool "SLQB debugging on by default"
+	depends on SLQB_DEBUG
+	default n
+
+config SLQB_STATS2
+	default n
+	bool "Enable SLQB performance statistics"
+	depends on SLQB
+
 config DEBUG_PREEMPT
 	bool "Debug preemptible kernel"
 	depends on DEBUG_KERNEL && PREEMPT && (TRACE_IRQFLAGS_SUPPORT || PPC64)

mm/slqb.c new file +2824 -0

2,675 lines not on this page · raw message

include/linux/slab.h +4 -2

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

Lines of this file are not shown. View the raw message.

mm/Makefile +1 -0

Index: linux-2.6/mm/Makefile
===================================================================

Lines of this file are not shown. View the raw message.

include/linux/rcu_types.h new file +18 -0

Index: linux-2.6/include/linux/rcu_types.h
===================================================================

Lines of this file are not shown. View the raw message.

include/linux/vmstat.h +16 -0

Index: linux-2.6/include/linux/vmstat.h
===================================================================

Lines of this file are not shown. View the raw message.

mm/vmstat.c +15 -0

Index: linux-2.6/mm/vmstat.c
===================================================================

Lines of this file are not shown. View the raw message.

arch/x86/include/asm/page.h +1 -0

Index: linux-2.6/arch/x86/include/asm/page.h
===================================================================

Lines of this file are not shown. View the raw message.

include/linux/mm.h +4 -0

Index: linux-2.6/include/linux/mm.h
===================================================================

Lines of this file are not shown. View the raw message.

The rest of this diff is not shown. View the raw message.

Part of the diff is not shown here. View the raw message.

Nick Piggin

author

2008-12-12 00:31 UTC #1 lore raw

RFC PATCH 1/1 mm: kfree_size

Introduce kfree_size(). Some allocators can do a better job at kfree if the size of the freed object is known in advance. skb layer in the networking stack can use kfree intensively, and in that case, the size information should be hot in cache, so it should be a win to use kfree_size here.

Allocators which don't care so much could just define kfree_size to kfree.

Thoughts? Any other good candidate callers?

---
 include/linux/slqb_def.h |   15 +++++++++++++++
 mm/slqb.c                |   12 ++++++++++++
 net/core/skbuff.c        |    7 ++++++-
 3 files changed, 33 insertions(+), 1 deletion(-)

include/linux/slqb_def.h +15 -0

Index: linux-2.6/include/linux/slqb_def.h
===================================================================
@@ -222,6 +222,21 @@ void *__kmalloc(size_t size, gfp_t flags
 
 #define KMALLOC_HEADER (ARCH_KMALLOC_MINALIGN < sizeof(void *) ? sizeof(void *) : ARCH_KMALLOC_MINALIGN)
 
+void __kfree_size(const void *mem, size_t size);
+static __always_inline void kfree_size(void *mem, size_t size)
+{
+	if (__builtin_constant_p(size)) {
+		struct kmem_cache *s;
+
+		s = kmalloc_slab(size, 0);
+		if (unlikely(ZERO_OR_NULL_PTR(s)))
+			return;
+
+		kmem_cache_free(s, mem);
+	}
+	__kfree_size(mem, size);
+}
+
 static __always_inline void *kmalloc(size_t size, gfp_t flags)
 {
 	if (__builtin_constant_p(size)) {

mm/slqb.c +12 -0

Index: linux-2.6/mm/slqb.c
===================================================================
@@ -2118,6 +2118,18 @@ void *__kmalloc_node(size_t size, gfp_t
 EXPORT_SYMBOL(__kmalloc_node);
 #endif
 
+void __kfree_size(const void *mem, size_t size)
+{
+	struct kmem_cache *s;
+
+	s = get_slab(size, 0);
+
+	if (unlikely(ZERO_OR_NULL_PTR(s)))
+		return;
+
+	kmem_cache_free(s, mem);
+}
+
 size_t ksize(const void *object)
 {
 	struct slqb_page *page;

net/core/skbuff.c +6 -1

Index: linux-2.6/net/core/skbuff.c
===================================================================
@@ -336,6 +336,11 @@ static void skb_release_data(struct sk_b
 	if (!skb->cloned ||
 	    !atomic_sub_return(skb->nohdr ? (1 << SKB_DATAREF_SHIFT) + 1 : 1,
 			       &skb_shinfo(skb)->dataref)) {
+#ifdef NET_SKBUFF_DATA_USES_OFFSET
+		int size = skb->end;
+#else
+		int size = skb->end - skb->head;
+#endif
 		if (skb_shinfo(skb)->nr_frags) {
 			int i;
 			for (i = 0; i < skb_shinfo(skb)->nr_frags; i++)

@@ -345,7 +350,7 @@ static void skb_release_data(struct sk_b
 		if (skb_shinfo(skb)->frag_list)
 			skb_drop_fraglist(skb);
 
-		kfree(skb->head);
+		kfree_size(skb->head, size);
 	}
 }

Christoph Lameter

2008-12-13 02:36 UTC #2 lore raw

Re: [rfc][patch] mm: kfree_size

Quoted 3 lines · Nick Piggin

Allocators which don't care so much could just define kfree_size to kfree.
Thoughts? Any other good candidate callers?

Would be a good idea together with some sort of allocator skeleton. Not having to carry the size is especially important for alternate kmalloc array implementations.

Eric Dumazet

2008-12-12 05:38 UTC #3 lore raw

In reply to Nick Piggin

Quoted 40 lines · Nick Piggin

(Re)introducing SLQB allocator. Q for queued, but in reality, SLAB and SLUB also have queues of things as well, so "Q" is just a meaningless differentiator :)
I've kept working on SLQB slab allocator because I don't agree with the design choices in SLUB, and I'm worried about the push to make it the one true allocator.
My primary goal in SLQB is performance, secondarily are order-0 page allocations, and memory consumption.
I have worked with the Linux guys at Intel to ensure that SLQB is comparable to SLAB in their OLTP performance benchmark. Recently that goal has been reached -- so SLQB performs comparably well to SLAB on that test (it's within the noise).
I've also been comparing SLQB with SLAB and SLUB in other benchmarks, and trying to ensure it is as good or better. I don't know if that's always the case, but nothing obvious has gone wrong (it's sometimes hard to find meaningful benchmarks that exercise slab in interesting ways).
Now it isn't exactly complete -- debugging, tracking, stats, etc. code is not always in the best shape, however I have been focusing on performance of the core allocator. No matter how good the rest is if the core code is poor... But it boots, works, is pretty stable.
SLQB, like SLUB and unlike SLAB, doesn't have greater than linear memory consumption growth with the number of CPUs or nodes.
SLQB tries to be very page-size agnostic. And it tries very hard to use order-0 pages. This is good for both page allocator fragmentation, and slab fragmentation. I don't like that SLUB performs significantly worse with order-0 pages in some workloads.
SLQB goes to some lengths to optimise remote-freeing cases (allocate on one CPU, free on another). It seems to work well, but there are a *lot* of possible ways this can be implemented especially when NUMA comes into play, so I'd like to know of workloads where remote freeing happens a lot, and perhaps look at alternative ways to do it.

Quoted 8 lines

SLQB initialistaion code attempts to be as simple and un-clever as possible. There are no multiple phases where different things come up. There is no weird self bootstrapping stuff. It just statically allocates the structures required to create the slabs that allocate other slab structures.
I'm going to continue working on this as I get time, and I plan to soon ask to have it merged. It would be great if people could comment or test it.

It seems really good, but will need some hours to review :)

Minor nit : You spelled Qeued instead of Queued in init/Kconfig

+config SLQB
+ bool "SLQB (Qeued allocator)"

One of the problem I see with SLAB & SLUB is the irq masking stuff. Some (many ???) kmem_cache are only used in process context, I see no point of disabling irqs for them.

I tested your patch on my 8 ways HP BL460c G1, on top on my last patch serie. (linux-2.6, not net-next-2.6)

# time ./socketallocbench

real    0m1.300s
user    0m0.078s
sys     0m1.207s
# time ./socketallocbench -n 8

real    0m1.686s
user    0m0.614s
sys     0m12.737s

So no bad effect (same than SLUB).

For the record, SLAB is really really bad for this workload

PU: Core 2, speed 3000.1 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 100 000

samples  cum. samples  %        cum. %     symbol name
136537   136537        10.8300  10.8300    kmem_cache_alloc
129380   265917        10.2623  21.0924    tcp_close
79696    345613         6.3214  27.4138    tcp_v4_init_sock
73873    419486         5.8596  33.2733    tcp_v4_destroy_sock
63436    482922         5.0317  38.3050    sysenter_past_esp
62140    545062         4.9289  43.2339    inet_csk_destroy_sock
56565    601627         4.4867  47.7206    kmem_cache_free
40430    642057         3.2069  50.9275    __percpu_counter_add
35742    677799         2.8350  53.7626    init_timer
35611    713410         2.8246  56.5872    copy_from_user
21616    735026         1.7146  58.3018    d_alloc
20821    755847         1.6515  59.9533    alloc_inode
19645    775492         1.5582  61.5115    alloc_fd
18935    794427         1.5019  63.0134    __fput
18922    813349         1.5009  64.5143    inet_create
18919    832268         1.5006  66.0149    sys_close
16074    848342         1.2750  67.2899    release_sock
15337    863679         1.2165  68.5064    lock_sock_nested
15172    878851         1.2034  69.7099    sock_init_data
14196    893047         1.1260  70.8359    fd_install
13677    906724         1.0849  71.9207    drop_file_write_access
13195    919919         1.0466  72.9673    dput
12768    932687         1.0127  73.9801    inotify_d_instantiate
11404    944091         0.9046  74.8846    init_waitqueue_head
11228    955319         0.8906  75.7752    sysenter_do_call
11213    966532         0.8894  76.6647    local_bh_enable_ip
10948    977480         0.8684  77.5330    __sock_create
10912    988392         0.8655  78.3986    local_bh_enable
10665    999057         0.8459  79.2445    __new_inode
10579    1009636        0.8391  80.0836    inet_release
9665     1019301        0.7666  80.8503    iput_single
9545     1028846        0.7571  81.6074    fput
7950     1036796        0.6306  82.2379    sock_release
7236     1044032        0.5740  82.8119    local_bh_disable

We can see most of the time is taken by the memset() to clear object, then irq masking stuff...

c0281e10 <kmem_cache_alloc>: /* kmem_cache_alloc total: 140659 10.8277 */

  2414  0.1858 :c0281e10:       push   %ebp
     7 5.4e-04 :c0281e11:       mov    %esp,%ebp
               :c0281e13:       push   %edi
  1454  0.1119 :c0281e14:       push   %esi
   310  0.0239 :c0281e15:       mov    %eax,%esi
               :c0281e17:       push   %ebx
   368  0.0283 :c0281e18:       sub    $0x10,%esp
   949  0.0731 :c0281e1b:       mov    %edx,-0x18(%ebp)
   383  0.0295 :c0281e1e:       mov    0x4(%ebp),%eax
  1189  0.0915 :c0281e21:       mov    %eax,-0x14(%ebp)
  1240  0.0955 :c0281e24:       jmp    c0281e6e <kmem_cache_alloc+0x5e>
               :c0281e26:       lea    0x0(%esi),%esi
               :c0281e29:       lea    0x0(%edi,%eiz,1),%edi
  1188  0.0915 :c0281e30:       mov    0x10(%esi),%eax
               :c0281e33:       mov    (%edx,%eax,1),%eax
  1483  0.1142 :c0281e36:       decl   (%ebx)
   898  0.0691 :c0281e38:       mov    %eax,0x4(%ebx)
   586  0.0451 :c0281e3b:       mov    %edx,-0x1c(%ebp)
     1 7.7e-05 :c0281e3e:       pushl  -0x10(%ebp)
  1226  0.0944 :c0281e41:       popf
 26385  2.0311 :c0281e42:       testl  $0x210d00,(%esi)
  1188  0.0915 :c0281e48:       je     c0281ef8 <kmem_cache_alloc+0xe8>
               :c0281e4e:       mov    -0x1c(%ebp),%eax
               :c0281e51:       test   %eax,%eax
               :c0281e53:       je     c0281ef8 <kmem_cache_alloc+0xe8>
               :c0281e59:       mov    -0x14(%ebp),%ecx
               :c0281e5c:       mov    -0x1c(%ebp),%edx
               :c0281e5f:       mov    %esi,%eax
               :c0281e61:       call   c0280d60 <alloc_debug_processing>
               :c0281e66:       test   %eax,%eax
               :c0281e68:       jne    c0281ef8 <kmem_cache_alloc+0xe8>
  1205  0.0928 :c0281e6e:       pushf
  4888  0.3763 :c0281e6f:       popl   -0x10(%ebp)
   319  0.0246 :c0281e72:       cli
  5975  0.4599 :c0281e73:       nop
               :c0281e74:       lea    0x0(%esi,%eiz,1),%esi
               :c0281e78:       mov    %fs:0xc068d004,%eax
  1166  0.0898 :c0281e7e:       mov    0x38(%esi,%eax,4),%ebx
    26  0.0020 :c0281e82:       mov    0x4(%ebx),%edx
   662  0.0510 :c0281e85:       test   %edx,%edx
               :c0281e87:       jne    c0281e30 <kmem_cache_alloc+0x20>
               :c0281e89:       mov    0xc(%ebx),%eax
               :c0281e8c:       test   %eax,%eax
               :c0281e8e:       jne    c0281ec8 <kmem_cache_alloc+0xb8>
               :c0281e90:       mov    %ebx,%edx
               :c0281e92:       mov    %esi,%eax
               :c0281e94:       call   c0280010 <__cache_list_get_page>
               :c0281e99:       mov    %eax,%edx
               :c0281e9b:       test   %eax,%eax
               :c0281e9d:       jne    c0281f31 <kmem_cache_alloc+0x121>
               :c0281ea3:       mov    $0xffffffff,%ecx
     1 7.7e-05 :c0281ea8:       mov    -0x18(%ebp),%edx
               :c0281eab:       mov    %esi,%eax
               :c0281ead:       call   c02815a0 <__slab_alloc_page>
               :c0281eb2:       test   %eax,%eax
               :c0281eb4:       jne    c0281e78 <kmem_cache_alloc+0x68>
               :c0281eb6:       movl   $0x0,-0x1c(%ebp)
               :c0281ebd:       jmp    c0281e3e <kmem_cache_alloc+0x2e>
               :c0281ec2:       lea    0x0(%esi),%esi
               :c0281ec8:       mov    %esi,%eax
               :c0281eca:       mov    %ebx,%edx
               :c0281ecc:       call   c0280240 <claim_remote_free_list>
               :c0281ed1:       mov    0x4(%esi),%eax
               :c0281ed4:       shl    $0x2,%eax
               :c0281ed7:       cmp    %eax,(%ebx)
               :c0281ed9:       ja     c0281f48 <kmem_cache_alloc+0x138>
               :c0281edb:       mov    0x4(%ebx),%edx
               :c0281ede:       mov    %edx,-0x1c(%ebp)
               :c0281ee1:       test   %edx,%edx
               :c0281ee3:       je     c0281e90 <kmem_cache_alloc+0x80>
               :c0281ee5:       mov    0x10(%esi),%eax
               :c0281ee8:       mov    (%edx,%eax,1),%eax
               :c0281eeb:       decl   (%ebx)
               :c0281eed:       mov    %eax,0x4(%ebx)
               :c0281ef0:       jmp    c0281e3e <kmem_cache_alloc+0x2e>

               :c0281ef5:       lea    0x0(%esi),%esi
  1261  0.0971 :c0281ef8:       cmpw   $0x0,-0x18(%ebp)
   957  0.0737 :c0281efd:       jns    c0281f26 <kmem_cache_alloc+0x116>
   627  0.0483 :c0281eff:       mov    -0x1c(%ebp),%eax
               :c0281f02:       test   %eax,%eax
               :c0281f04:       je     c0281f26 <kmem_cache_alloc+0x116>
    82  0.0063 :c0281f06:       mov    0xc(%esi),%esi
     2 1.5e-04 :c0281f09:       mov    -0x1c(%ebp),%ebx
   527  0.0406 :c0281f0c:       mov    %esi,%ecx
               :c0281f0e:       mov    %ebx,%edi
    86  0.0066 :c0281f10:       shr    $0x2,%ecx
   602  0.0463 :c0281f13:       xor    %eax,%eax
     1 7.7e-05 :c0281f15:       mov    %esi,%edx
 74845  5.7614 :c0281f17:       rep stos %eax,%es:(%edi)
  1170  0.0901 :c0281f19:       test   $0x2,%dl
     2 1.5e-04 :c0281f1c:       je     c0281f20 <kmem_cache_alloc+0x110>
               :c0281f1e:       stos   %ax,%es:(%edi)
   600  0.0462 :c0281f20:       test   $0x1,%dl
               :c0281f23:       je     c0281f26 <kmem_cache_alloc+0x116>
               :c0281f25:       stos   %al,%es:(%edi)
  1171  0.0901 :c0281f26:       mov    -0x1c(%ebp),%eax
   199  0.0153 :c0281f29:       add    $0x10,%esp
               :c0281f2c:       pop    %ebx
     2 1.5e-04 :c0281f2d:       pop    %esi
  1215  0.0935 :c0281f2e:       pop    %edi
   548  0.0422 :c0281f2f:       leave
  1251  0.0963 :c0281f30:       ret
               :c0281f31:       mov    0x10(%edx),%ecx
               :c0281f34:       mov    %ecx,-0x1c(%ebp)
               :c0281f37:       mov    0x10(%esi),%eax
               :c0281f3a:       mov    (%ecx,%eax,1),%eax
               :c0281f3d:       mov    %eax,0x10(%edx)
               :c0281f40:       jmp    c0281e3e <kmem_cache_alloc+0x2e>
               :c0281f45:       lea    0x0(%esi),%esi
               :c0281f48:       mov    %ebx,%edx
               :c0281f4a:       mov    %esi,%eax
               :c0281f4c:       call   c02811d0 <flush_free_list>
               :c0281f51:       jmp    c0281edb <kmem_cache_alloc+0xcb>
               :c0281f53:       lea    0x0(%esi),%esi

Nick Piggin

author

2008-12-12 05:50 UTC #4 lore raw

init/Kconfig config SLUB · line 792

Quoted 11 lines · Eric Dumazet

Quoted 3 lines · Nick Piggin
I'm going to continue working on this as I get time, and I plan to soon ask to have it merged. It would be great if people could comment or test it.
It seems really good, but will need some hours to review :)
Minor nit : You spelled Qeued instead of Queued in init/Kconfig
init/Kconfig +2 -0
+config SLQB
+	bool "SLQB (Qeued allocator)"

OK, thanks.

Quoted 3 lines

One of the problem I see with SLAB & SLUB is the irq masking stuff. Some (many ???) kmem_cache are only used in process context, I see no point of disabling irqs for them.

That's a very good point actually, and something I want to look at...

I'm thinking it will make most sense to provide a kmem_cache_alloc/free_irqsafe for callers who either don't do any interrupt context allocations, or already have irqs off (another slab flag will just add another branch in the fastpaths).

And then also a kmalloc/kfree_irqsoff for code which already has irqs off.

That's something which benefit all slab allocators roughly equally, so at the moment I'm concentrating on the core code. But it's a very good idea.

Quoted 10 lines

I tested your patch on my 8 ways HP BL460c G1, on top on my last patch serie. (linux-2.6, not net-next-2.6)
# time ./socketallocbench
real    0m1.300s
user    0m0.078s
sys     0m1.207s
# time ./socketallocbench -n 8

Quoted 5 lines

real    0m1.686s
user    0m0.614s
sys     0m12.737s
So no bad effect (same than SLUB).

Cool, thanks.

Quoted 42 lines

For the record, SLAB is really really bad for this workload

PU: Core 2, speed 3000.1 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 100 000

samples  cum. samples  %        cum. %     symbol name
136537   136537        10.8300  10.8300    kmem_cache_alloc
129380   265917        10.2623  21.0924    tcp_close
79696    345613         6.3214  27.4138    tcp_v4_init_sock
73873    419486         5.8596  33.2733    tcp_v4_destroy_sock
63436    482922         5.0317  38.3050    sysenter_past_esp
62140    545062         4.9289  43.2339    inet_csk_destroy_sock
56565    601627         4.4867  47.7206    kmem_cache_free
40430    642057         3.2069  50.9275    __percpu_counter_add
35742    677799         2.8350  53.7626    init_timer
35611    713410         2.8246  56.5872    copy_from_user
21616    735026         1.7146  58.3018    d_alloc
20821    755847         1.6515  59.9533    alloc_inode
19645    775492         1.5582  61.5115    alloc_fd
18935    794427         1.5019  63.0134    __fput
18922    813349         1.5009  64.5143    inet_create
18919    832268         1.5006  66.0149    sys_close
16074    848342         1.2750  67.2899    release_sock
15337    863679         1.2165  68.5064    lock_sock_nested
15172    878851         1.2034  69.7099    sock_init_data
14196    893047         1.1260  70.8359    fd_install
13677    906724         1.0849  71.9207    drop_file_write_access
13195    919919         1.0466  72.9673    dput
12768    932687         1.0127  73.9801    inotify_d_instantiate
11404    944091         0.9046  74.8846    init_waitqueue_head
11228    955319         0.8906  75.7752    sysenter_do_call
11213    966532         0.8894  76.6647    local_bh_enable_ip
10948    977480         0.8684  77.5330    __sock_create
10912    988392         0.8655  78.3986    local_bh_enable
10665    999057         0.8459  79.2445    __new_inode
10579    1009636        0.8391  80.0836    inet_release
9665     1019301        0.7666  80.8503    iput_single
9545     1028846        0.7571  81.6074    fput
7950     1036796        0.6306  82.2379    sock_release
7236     1044032        0.5740  82.8119    local_bh_disable

Quoted 2 lines

We can see most of the time is taken by the memset() to clear object, then irq masking stuff...

Yep, it's difficult to make the local alloc/free fastpath much more optimal as-is.

Is SLAB still bad at the test with the slab-rcu patch in place? SLAB has a pretty optimal fastpath as well, although if its queues start overflowing, it can run into contention quite easily.

Quoted 2 lines

c0281e10 <kmem_cache_alloc>: /* kmem_cache_alloc total: 140659 10.8277 */

I guess you're compiling with -Os? I find gcc can pack the fastpath much better with -O2, and actually decrease the effective icache footprint size even if the total text size increases...

Quoted 115 lines

  2414  0.1858 :c0281e10:       push   %ebp
     7 5.4e-04 :c0281e11:       mov    %esp,%ebp
               :c0281e13:       push   %edi
  1454  0.1119 :c0281e14:       push   %esi
   310  0.0239 :c0281e15:       mov    %eax,%esi
               :c0281e17:       push   %ebx
   368  0.0283 :c0281e18:       sub    $0x10,%esp
   949  0.0731 :c0281e1b:       mov    %edx,-0x18(%ebp)
   383  0.0295 :c0281e1e:       mov    0x4(%ebp),%eax
  1189  0.0915 :c0281e21:       mov    %eax,-0x14(%ebp)
  1240  0.0955 :c0281e24:       jmp    c0281e6e <kmem_cache_alloc+0x5e>
               :c0281e26:       lea    0x0(%esi),%esi
               :c0281e29:       lea    0x0(%edi,%eiz,1),%edi
  1188  0.0915 :c0281e30:       mov    0x10(%esi),%eax
               :c0281e33:       mov    (%edx,%eax,1),%eax
  1483  0.1142 :c0281e36:       decl   (%ebx)
   898  0.0691 :c0281e38:       mov    %eax,0x4(%ebx)
   586  0.0451 :c0281e3b:       mov    %edx,-0x1c(%ebp)
     1 7.7e-05 :c0281e3e:       pushl  -0x10(%ebp)
  1226  0.0944 :c0281e41:       popf
 26385  2.0311 :c0281e42:       testl  $0x210d00,(%esi)
  1188  0.0915 :c0281e48:       je     c0281ef8 <kmem_cache_alloc+0xe8>
               :c0281e4e:       mov    -0x1c(%ebp),%eax
               :c0281e51:       test   %eax,%eax
               :c0281e53:       je     c0281ef8 <kmem_cache_alloc+0xe8>
               :c0281e59:       mov    -0x14(%ebp),%ecx
               :c0281e5c:       mov    -0x1c(%ebp),%edx
               :c0281e5f:       mov    %esi,%eax
               :c0281e61:       call   c0280d60 <alloc_debug_processing>
               :c0281e66:       test   %eax,%eax
               :c0281e68:       jne    c0281ef8 <kmem_cache_alloc+0xe8>
  1205  0.0928 :c0281e6e:       pushf
  4888  0.3763 :c0281e6f:       popl   -0x10(%ebp)
   319  0.0246 :c0281e72:       cli
  5975  0.4599 :c0281e73:       nop
               :c0281e74:       lea    0x0(%esi,%eiz,1),%esi
               :c0281e78:       mov    %fs:0xc068d004,%eax
  1166  0.0898 :c0281e7e:       mov    0x38(%esi,%eax,4),%ebx
    26  0.0020 :c0281e82:       mov    0x4(%ebx),%edx
   662  0.0510 :c0281e85:       test   %edx,%edx
               :c0281e87:       jne    c0281e30 <kmem_cache_alloc+0x20>
               :c0281e89:       mov    0xc(%ebx),%eax
               :c0281e8c:       test   %eax,%eax
               :c0281e8e:       jne    c0281ec8 <kmem_cache_alloc+0xb8>
               :c0281e90:       mov    %ebx,%edx
               :c0281e92:       mov    %esi,%eax
               :c0281e94:       call   c0280010 <__cache_list_get_page>
               :c0281e99:       mov    %eax,%edx
               :c0281e9b:       test   %eax,%eax
               :c0281e9d:       jne    c0281f31 <kmem_cache_alloc+0x121>
               :c0281ea3:       mov    $0xffffffff,%ecx
     1 7.7e-05 :c0281ea8:       mov    -0x18(%ebp),%edx
               :c0281eab:       mov    %esi,%eax
               :c0281ead:       call   c02815a0 <__slab_alloc_page>
               :c0281eb2:       test   %eax,%eax
               :c0281eb4:       jne    c0281e78 <kmem_cache_alloc+0x68>
               :c0281eb6:       movl   $0x0,-0x1c(%ebp)
               :c0281ebd:       jmp    c0281e3e <kmem_cache_alloc+0x2e>
               :c0281ec2:       lea    0x0(%esi),%esi
               :c0281ec8:       mov    %esi,%eax
               :c0281eca:       mov    %ebx,%edx
               :c0281ecc:       call   c0280240 <claim_remote_free_list>
               :c0281ed1:       mov    0x4(%esi),%eax
               :c0281ed4:       shl    $0x2,%eax
               :c0281ed7:       cmp    %eax,(%ebx)
               :c0281ed9:       ja     c0281f48 <kmem_cache_alloc+0x138>
               :c0281edb:       mov    0x4(%ebx),%edx
               :c0281ede:       mov    %edx,-0x1c(%ebp)
               :c0281ee1:       test   %edx,%edx
               :c0281ee3:       je     c0281e90 <kmem_cache_alloc+0x80>
               :c0281ee5:       mov    0x10(%esi),%eax
               :c0281ee8:       mov    (%edx,%eax,1),%eax
               :c0281eeb:       decl   (%ebx)
               :c0281eed:       mov    %eax,0x4(%ebx)
               :c0281ef0:       jmp    c0281e3e <kmem_cache_alloc+0x2e>

               :c0281ef5:       lea    0x0(%esi),%esi
  1261  0.0971 :c0281ef8:       cmpw   $0x0,-0x18(%ebp)
   957  0.0737 :c0281efd:       jns    c0281f26 <kmem_cache_alloc+0x116>
   627  0.0483 :c0281eff:       mov    -0x1c(%ebp),%eax
               :c0281f02:       test   %eax,%eax
               :c0281f04:       je     c0281f26 <kmem_cache_alloc+0x116>
    82  0.0063 :c0281f06:       mov    0xc(%esi),%esi
     2 1.5e-04 :c0281f09:       mov    -0x1c(%ebp),%ebx
   527  0.0406 :c0281f0c:       mov    %esi,%ecx
               :c0281f0e:       mov    %ebx,%edi
    86  0.0066 :c0281f10:       shr    $0x2,%ecx
   602  0.0463 :c0281f13:       xor    %eax,%eax
     1 7.7e-05 :c0281f15:       mov    %esi,%edx
 74845  5.7614 :c0281f17:       rep stos %eax,%es:(%edi)
  1170  0.0901 :c0281f19:       test   $0x2,%dl
     2 1.5e-04 :c0281f1c:       je     c0281f20 <kmem_cache_alloc+0x110>
               :c0281f1e:       stos   %ax,%es:(%edi)
   600  0.0462 :c0281f20:       test   $0x1,%dl
               :c0281f23:       je     c0281f26 <kmem_cache_alloc+0x116>
               :c0281f25:       stos   %al,%es:(%edi)
  1171  0.0901 :c0281f26:       mov    -0x1c(%ebp),%eax
   199  0.0153 :c0281f29:       add    $0x10,%esp
               :c0281f2c:       pop    %ebx
     2 1.5e-04 :c0281f2d:       pop    %esi
  1215  0.0935 :c0281f2e:       pop    %edi
   548  0.0422 :c0281f2f:       leave
  1251  0.0963 :c0281f30:       ret
               :c0281f31:       mov    0x10(%edx),%ecx
               :c0281f34:       mov    %ecx,-0x1c(%ebp)
               :c0281f37:       mov    0x10(%esi),%eax
               :c0281f3a:       mov    (%ecx,%eax,1),%eax
               :c0281f3d:       mov    %eax,0x10(%edx)
               :c0281f40:       jmp    c0281e3e <kmem_cache_alloc+0x2e>
               :c0281f45:       lea    0x0(%esi),%esi
               :c0281f48:       mov    %ebx,%edx
               :c0281f4a:       mov    %esi,%eax
               :c0281f4c:       call   c02811d0 <flush_free_list>
               :c0281f51:       jmp    c0281edb <kmem_cache_alloc+0xcb>
               :c0281f53:       lea    0x0(%esi),%esi

Eric Dumazet

2008-12-12 07:07 UTC #5 lore raw

Quoted 98 lines · Nick Piggin

init/Kconfig config SLUB · line 792
Quoted 10 lines · Eric Dumazet
Quoted 3 lines · Nick Piggin
I'm going to continue working on this as I get time, and I plan to soon ask to have it merged. It would be great if people could comment or test it.
It seems really good, but will need some hours to review :)
Minor nit : You spelled Qeued instead of Queued in init/Kconfig
init/Kconfig +2 -0
+config SLQB
+	bool "SLQB (Qeued allocator)"
OK, thanks.
Quoted 3 lines
One of the problem I see with SLAB & SLUB is the irq masking stuff. Some (many ???) kmem_cache are only used in process context, I see no point of disabling irqs for them.
That's a very good point actually, and something I want to look at...
I'm thinking it will make most sense to provide a kmem_cache_alloc/free_irqsafe for callers who either don't do any interrupt context allocations, or already have irqs off (another slab flag will just add another branch in the fastpaths).
And then also a kmalloc/kfree_irqsoff for code which already has irqs off.
That's something which benefit all slab allocators roughly equally, so at the moment I'm concentrating on the core code. But it's a very good idea.
Quoted 10 lines
I tested your patch on my 8 ways HP BL460c G1, on top on my last patch serie. (linux-2.6, not net-next-2.6)
# time ./socketallocbench
real    0m1.300s
user    0m0.078s
sys     0m1.207s
# time ./socketallocbench -n 8
Quoted 5 lines
real    0m1.686s
user    0m0.614s
sys     0m12.737s
So no bad effect (same than SLUB).
Cool, thanks.
Quoted 42 lines
For the record, SLAB is really really bad for this workload
PU: Core 2, speed 3000.1 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (Unhalted core cycles) count 100 000
samples  cum. samples  %        cum. %     symbol name
136537   136537        10.8300  10.8300    kmem_cache_alloc
129380   265917        10.2623  21.0924    tcp_close
79696    345613         6.3214  27.4138    tcp_v4_init_sock
73873    419486         5.8596  33.2733    tcp_v4_destroy_sock
63436    482922         5.0317  38.3050    sysenter_past_esp
62140    545062         4.9289  43.2339    inet_csk_destroy_sock
56565    601627         4.4867  47.7206    kmem_cache_free
40430    642057         3.2069  50.9275    __percpu_counter_add
35742    677799         2.8350  53.7626    init_timer
35611    713410         2.8246  56.5872    copy_from_user
21616    735026         1.7146  58.3018    d_alloc
20821    755847         1.6515  59.9533    alloc_inode
19645    775492         1.5582  61.5115    alloc_fd
18935    794427         1.5019  63.0134    __fput
18922    813349         1.5009  64.5143    inet_create
18919    832268         1.5006  66.0149    sys_close
16074    848342         1.2750  67.2899    release_sock
15337    863679         1.2165  68.5064    lock_sock_nested
15172    878851         1.2034  69.7099    sock_init_data
14196    893047         1.1260  70.8359    fd_install
13677    906724         1.0849  71.9207    drop_file_write_access
13195    919919         1.0466  72.9673    dput
12768    932687         1.0127  73.9801    inotify_d_instantiate
11404    944091         0.9046  74.8846    init_waitqueue_head
11228    955319         0.8906  75.7752    sysenter_do_call
11213    966532         0.8894  76.6647    local_bh_enable_ip
10948    977480         0.8684  77.5330    __sock_create
10912    988392         0.8655  78.3986    local_bh_enable
10665    999057         0.8459  79.2445    __new_inode
10579    1009636        0.8391  80.0836    inet_release
9665     1019301        0.7666  80.8503    iput_single
9545     1028846        0.7571  81.6074    fput
7950     1036796        0.6306  82.2379    sock_release
7236     1044032        0.5740  82.8119    local_bh_disable
Quoted 2 lines
We can see most of the time is taken by the memset() to clear object, then irq masking stuff...

Quoted 6 lines

Yep, it's difficult to make the local alloc/free fastpath much more optimal as-is.
Is SLAB still bad at the test with the slab-rcu patch in place? SLAB has a pretty optimal fastpath as well, although if its queues start overflowing, it can run into contention quite easily.

Yes, I forgot I applied Christoph patch (SLAB_DESTROY_BY_RCU for struct file) in the meantime, silly me, this was with the v2 of my serie, with only 5 patches.

With SLAB, results are quite good !

# time ./socketallocbench

real    0m1.201s
user    0m0.071s
sys     0m1.122s
# time ./socketallocbench -n8

real    0m1.616s
user    0m0.578s
sys     0m12.220s

Quoted 6 lines

Quoted 2 lines
c0281e10 <kmem_cache_alloc>: /* kmem_cache_alloc total: 140659 10.8277 */
I guess you're compiling with -Os? I find gcc can pack the fastpath much better with -O2, and actually decrease the effective icache footprint size even if the total text size increases...

No, I dont use -Os, unless something got wrong

# CONFIG_CC_OPTIMIZE_FOR_SIZE is not set
# CONFIG_OPTIMIZE_INLINING is not set

Nick Piggin

author

2008-12-12 07:23 UTC #6 lore raw

Quoted 12 lines · Eric Dumazet

Quoted 3 lines · Nick Piggin
Is SLAB still bad at the test with the slab-rcu patch in place? SLAB has a pretty optimal fastpath as well, although if its queues start overflowing, it can run into contention quite easily.
Yes, I forgot I applied Christoph patch (SLAB_DESTROY_BY_RCU for struct file) in the meantime, silly me, this was with the v2 of my serie, with only 5 patches.
With SLAB, results are quite good !
# time ./socketallocbench

Quoted 8 lines

real    0m1.201s
user    0m0.071s
sys     0m1.122s
# time ./socketallocbench -n8

real    0m1.616s
user    0m0.578s
sys     0m12.220s

Yeah, SLAB is actually very hard to beat, much of the time.

Quoted 10 lines

Quoted 5 lines
Quoted 1 line
c0281e10 <kmem_cache_alloc>: /* kmem_cache_alloc total: 140659 10.8277 */
I guess you're compiling with -Os? I find gcc can pack the fastpath much better with -O2, and actually decrease the effective icache footprint size even if the total text size increases...
No, I dont use -Os, unless something got wrong
# CONFIG_CC_OPTIMIZE_FOR_SIZE is not set
# CONFIG_OPTIMIZE_INLINING is not set

Oh OK. Hmm, you do have SLQB debugging compiled in by the looks. I haven't really been looking at code generation in that case. I don't expect that would cause a significant difference in your case, though.

Anyway, I'll see if I can work out why SLQB is slower. Do you have socketallocbench online?

Eric Dumazet

2008-12-12 08:05 UTC #7 lore raw

Quoted 30 lines · Nick Piggin

Quoted 11 lines · Eric Dumazet
Quoted 3 lines · Nick Piggin
Is SLAB still bad at the test with the slab-rcu patch in place? SLAB has a pretty optimal fastpath as well, although if its queues start overflowing, it can run into contention quite easily.
Yes, I forgot I applied Christoph patch (SLAB_DESTROY_BY_RCU for struct file) in the meantime, silly me, this was with the v2 of my serie, with only 5 patches.
With SLAB, results are quite good !
# time ./socketallocbench
Quoted 8 lines
real    0m1.201s
user    0m0.071s
sys     0m1.122s
# time ./socketallocbench -n8
real    0m1.616s
user    0m0.578s
sys     0m12.220s
Yeah, SLAB is actually very hard to beat, much of the time.
Quoted 6 lines
Quoted 4 lines
Quoted 1 line
c0281e10 <kmem_cache_alloc>: /* kmem_cache_alloc total: 140659 10.8277 */
I guess you're compiling with -Os? I find gcc can pack the fastpath much better with -O2, and actually decrease the effective icache footprint size even if the total text size increases...
No, I dont use -Os, unless something got wrong

Quoted 8 lines

Quoted 2 lines
# CONFIG_CC_OPTIMIZE_FOR_SIZE is not set
# CONFIG_OPTIMIZE_INLINING is not set
Oh OK. Hmm, you do have SLQB debugging compiled in by the looks. I haven't really been looking at code generation in that case. I don't expect that would cause a significant difference in your case, though.

One thing that might give a difference is to not use kmem_cache_zalloc() in get_empty_filp(), because on 32bits, sizeof(struct file)=132

So kmem_cache_zalloc() clears 192 bytes, while if done by a memset() inside get_empty_filp(), we would clear 132 bytes exactly.

OK, I tried without SLQB debugging and got :

# time ./socketallocbench

real    0m1.261s
user    0m0.078s
sys     0m1.183s
# time ./socketallocbench -n 8

real    0m1.640s
user    0m0.638s
sys     0m12.346s

Quoted 2 lines

Anyway, I'll see if I can work out why SLQB is slower. Do you have socketallocbench online?

Well, it's so trivial, you probably can code it in perl or whatever in 4 lines :)

its a basic

	for (i = 0; i < 1000000; i++)
		close(socket(AF_INET, SOCK_STREAM, 0));

and -n 8 starts 8 processes doing this same loop in //

Nick Piggin

author

2008-12-12 09:43 UTC #8 lore raw

In reply to Nick Piggin

Quoted 2 lines · Nick Piggin

Anyway, I'll see if I can work out why SLQB is slower. Do you have socketallocbench online?

Hmph, it seems to be in the noise (I'm testing with an AMD system though). Some boots SLAB is faster, other boots, SLQB is. Could be a matter of luck in cacheline placement maybe?

I think this benchmark (after the slab rcu patch) will be pretty trivial for any slab allocator because it will basically be each CPU allocating then freeing an object.

Christoph Lameter

2008-12-13 02:34 UTC #9 lore raw

In reply to Nick Piggin

Quoted 3 lines · Nick Piggin

+ * SLQB : A slab allocator with object queues.
+ *
+ * (C) 2008 Nick Piggin <[email protected]>

My copyright notice is missing. Most of this is directly copied from SLUB. And I am not CCed? What should I be thinking?

Quoted 5 lines

+/*
+ * SLQB: A slab allocator that focuses on per-CPU scaling, and good performance
+ * with order-0 allocations. Fastpaths emphasis is placed on local allocaiton
+ * and freeing, but with a secondary goal of good remote freeing (freeing on
+ * another CPU from that which allocated).

Good idea. I like new ideas based on SLUB.

Quoted 2 lines

+ *
+ * Using ideas and code from mm/slab.c, mm/slob.c, and mm/slub.c.

Thats not right. The code was copied from mm/slub.c and then modified.

It seems that the SLUB skeleton is very useful. Maybe we could abstract the common code out in order to make more creative variants possible in the future?

Quoted 7 lines

+/*
+ * Issues still to be resolved:
+ *
+ * - Support PAGE_ALLOC_DEBUG. Should be easy to do.
+ *
+ * - Variable sizing of the per node arrays
+ */

These are outdated SLUB comments....

mm/slqb.c line 1196

Quoted 2 lines

mm/slqb.c new file +2 -0

+	/* XXX: might disobey node parameter here */
+	if (!NUMA_BUILD || likely(slqb_page_to_nid(page) == numa_node_id())) {

You can only decide not to obey if __GFP_THISNODE is not set.

Quoted 6 lines

mm/slqb.c new file +6 -0

+static __always_inline void *__slab_alloc(struct kmem_cache *s,
+		gfp_t gfpflags, int node)
+{
+	void *object;
+	struct kmem_cache_cpu *c;
+	struct kmem_cache_list *l;

mm/slqb.c line 1284

Quoted 10 lines

mm/slqb.c new file +10 -0

+
+again:
+#ifdef CONFIG_NUMA
+	if (unlikely(node != -1) && unlikely(node != numa_node_id())) {
+		object = __remote_slab_alloc(s, node);
+		if (unlikely(!object))
+			goto alloc_new;
+		return object;
+	}
+#endif

Does this mean that SLQB is less efficient than SLUB for off node allocations? SLUB can do off node allocations from the per cpu objects. It does not need to make the distinction for allocation.

mm/slqb.c line 1287

Quoted 2 lines

mm/slqb.c new file +2 -0

+	c = get_cpu_slab(s, smp_processor_id());
+	VM_BUG_ON(!c);

if c = NULL then the deref will fail anyways with a NULL deref error. No need to have a VM_BUG_ON here.

Review

Quoted 2 lines

(quoted diff) +2 -0

+	l = &c->list;
+	object = __cache_list_get_object(s, l);

Hmmm... __cache_list_get_object() is quite a bunch of heavy processing. This is all inline?

mm/slqb.c line 1424

Quoted 13 lines

mm/slqb.c new file +13 -0

+static __always_inline void __slab_free(struct kmem_cache *s, struct slqb_page *page, void *object)
+{
+	struct kmem_cache_cpu *c;
+	struct kmem_cache_list *l;
+	int thiscpu = smp_processor_id();
+
+	__count_slqb_event(SLQB_FREE);
+
+	c = get_cpu_slab(s, thiscpu);
+	l = &c->list;
+
+	if (!NUMA_BUILD || !numa_platform ||
+			likely(slqb_page_to_nid(page) == numa_node_id())) {

SLUB does not need a node check. The page struct pointer comparison is enough.

This also means that SLQB cannot do fast frees to remote node objects that were just allocated. per cpu queue is bound to the local numa node which is quite bad for memoryless nodes. In that case you always need to do remote allocs.

In general I am a bit concerned that you kept the linked object list. You may be able to do much better by creating arrays of object pointers. That way you can allocate and free multiple objects by only accessing the cacheline that contains the object pointers. Only works if the objects are not immediately writen to before and after free.

AFAICT this is the special case that matters in terms of the database test you are trying to improve. The case there is likely the result of bad cache unfriendly programming. You may actually improve the benchmark more if the cachelines would be kept hot there in the right way.

Pekka Enberg

2008-12-13 09:03 UTC #10 lore raw

Quoted 5 lines · Christoph Lameter

AFAICT this is the special case that matters in terms of the database test you are trying to improve. The case there is likely the result of bad cache unfriendly programming. You may actually improve the benchmark more if the cachelines would be kept hot there in the right way.

Lets not forget the order-0 page thing, which is nice from page allocator fragmentation point of view. But I suppose SLUB can use them as well if we get around fixing the page allocator fastpaths?

Christoph Lameter

2008-12-15 01:51 UTC #11 lore raw

Quoted 3 lines · Pekka Enberg

Lets not forget the order-0 page thing, which is nice from page allocator fragmentation point of view. But I suppose SLUB can use them as well if we get around fixing the page allocator fastpaths?

If the fastpath of the page allocator would be comparable in performance to the slab allocators then page sized allocations could simply be forwarded to the page allocator etc. IMHO this is how it should be .... Right now slab allocators must buffer PAGE_SIZEd allocs due to page allocator slowness.

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

Nick Piggin

author

2008-12-14 23:04 UTC #12 lore raw

In reply to Christoph Lameter

Quoted 7 lines · Christoph Lameter

Quoted 3 lines · Nick Piggin
+ * SLQB : A slab allocator with object queues.
+ *
+ * (C) 2008 Nick Piggin <[email protected]>
My copyright notice is missing. Most of this is directly copied from SLUB.

I did definitely attribute sources.... ah, you noticed further down.

Quoted 1 line

And I am not CCed? What should I be thinking?

Linux-mm is cc'ed and you're subscribed, right? linux-mm has good S/N, so I get lazy with cc lists if my audience is subscribed there ;) No ill intention.

Quoted 7 lines

Quoted 5 lines
+/*
+ * SLQB: A slab allocator that focuses on per-CPU scaling, and good performance
+ * with order-0 allocations. Fastpaths emphasis is placed on local allocaiton
+ * and freeing, but with a secondary goal of good remote freeing (freeing on
+ * another CPU from that which allocated).
Good idea. I like new ideas based on SLUB.

Well, thanks. The core allocator is more based on SLAB, but with linked list of objects from SLOB, rather than arrays. But whatever; it is what it is.

Actually, the boot-time debugging idea is from SLUB, which is useful.

Quoted 4 lines

Quoted 2 lines
+ *
+ * Using ideas and code from mm/slab.c, mm/slob.c, and mm/slub.c.
Thats not right. The code was copied from mm/slub.c and then modified.

I definitely took ideas and code from mm/slab.c, and ideas if not code from mm/slob.c too so I need to attribute them as well.

Quoted 3 lines

It seems that the SLUB skeleton is very useful. Maybe we could abstract the common code out in order to make more creative variants possible in the future?

I think it wasn't hard to take the code and change it.

Quoted 9 lines

Quoted 7 lines
+/*
+ * Issues still to be resolved:
+ *
+ * - Support PAGE_ALLOC_DEBUG. Should be easy to do.
+ *
+ * - Variable sizing of the per node arrays
+ */
These are outdated SLUB comments....

Thanks, probably quite a bit of SLUB cruft left ;)

Quoted 4 lines

mm/slqb.c line 1196
Quoted 2 lines
mm/slqb.c new file +2 -0
+	/* XXX: might disobey node parameter here */
+	if (!NUMA_BUILD || likely(slqb_page_to_nid(page) == numa_node_id())) {
You can only decide not to obey if __GFP_THISNODE is not set.

I think that's outdated. Basically I think I was previously caching numa_node_id across the allocation. The code used to be structured differently...

Quoted 12 lines

mm/slqb.c new file +12 -0

+static __always_inline void *__slab_alloc(struct kmem_cache *s,
+		gfp_t gfpflags, int node)
+{
+	void *object;
+	struct kmem_cache_cpu *c;
+	struct kmem_cache_list *l;
+
+again:
+#ifdef CONFIG_NUMA
+	if (unlikely(node != -1) && unlikely(node != numa_node_id())) {
+		object = __remote_slab_alloc(s, node);
+		if (unlikely(!object))

Quoted 8 lines

mm/slqb.c line 1284
Quoted 4 lines
mm/slqb.c new file +4 -0
+			goto alloc_new;
+		return object;
+	}
+#endif
Does this mean that SLQB is less efficient than SLUB for off node allocations? SLUB can do off node allocations from the per cpu objects. It does not need to make the distinction for allocation.

I haven't measured them, but that could be the case. However I haven't found a workload that does a lot of off-node allocations (short lived allocations are better on-node, and long lived ones are not going to be so numerous).

It's easy to suck up several objects at a time and put them onto a remote-node list on the per-cpu structure, but I don't want to prematurely optimise.

Quoted 5 lines

Review
Quoted 2 lines
(quoted diff) +2 -0
+	l = &c->list;
+	object = __cache_list_get_object(s, l);
Hmmm... __cache_list_get_object() is quite a bunch of heavy processing. This is all inline?

Yes. I've looked at the fastpath assembly and it's pretty good. gcc can reorder things so the effective icache footprint is pretty small. That becomes harder if things are out of line.

Quoted 17 lines

mm/slqb.c line 1424

Quoted 13 lines

mm/slqb.c new file +13 -0

+static __always_inline void __slab_free(struct kmem_cache *s, struct slqb_page *page, void *object)
+{
+	struct kmem_cache_cpu *c;
+	struct kmem_cache_list *l;
+	int thiscpu = smp_processor_id();
+
+	__count_slqb_event(SLQB_FREE);
+
+	c = get_cpu_slab(s, thiscpu);
+	l = &c->list;
+
+	if (!NUMA_BUILD || !numa_platform ||
+			likely(slqb_page_to_nid(page) == numa_node_id())) {

SLUB does not need a node check. The page struct pointer comparison is enough.

Quoted 4 lines

This also means that SLQB cannot do fast frees to remote node objects that were just allocated. per cpu queue is bound to the local numa node which is quite bad for memoryless nodes. In that case you always need to do remote allocs.

I'm not very worried about that case yet. As I said, it's not hard to add something for it, but I don't know if it is worthwhile yet.

Quoted 5 lines

In general I am a bit concerned that you kept the linked object list. You may be able to do much better by creating arrays of object pointers. That way you can allocate and free multiple objects by only accessing the cacheline that contains the object pointers. Only works if the objects are not immediately writen to before and after free.

That's more complexity, though. Given that objects are often hot when they are freed, and need to be touched after they are allocated anyway, the simple queue seems to be reasonable.

Quoted 5 lines

AFAICT this is the special case that matters in terms of the database test you are trying to improve. The case there is likely the result of bad cache unfriendly programming. You may actually improve the benchmark more if the cachelines would be kept hot there in the right way.

This case does improve the database score by around 1.5-2%, yes. I don't know what you mean exactly, though. What case, and what do you mean by bad cache unfriendly programming? I would be very interested in improving that benchmark of course, but I don't know what you suggest by keeping cachelines hot in the right way?

Thanks,
Nick

Christoph Lameter

2008-12-15 14:02 UTC #13 lore raw

Quoted 8 lines · Nick Piggin

Quoted 3 lines
Does this mean that SLQB is less efficient than SLUB for off node allocations? SLUB can do off node allocations from the per cpu objects. It does not need to make the distinction for allocation.
I haven't measured them, but that could be the case. However I haven't found a workload that does a lot of off-node allocations (short lived allocations are better on-node, and long lived ones are not going to be so numerous).

A memoryless node is a case where all allocations will be like that.

Quoted 3 lines

That's more complexity, though. Given that objects are often hot when they are freed, and need to be touched after they are allocated anyway, the simple queue seems to be reasonable.

Yup.

Quoted 5 lines

This case does improve the database score by around 1.5-2%, yes. I don't know what you mean exactly, though. What case, and what do you mean by bad cache unfriendly programming? I would be very interested in improving that benchmark of course, but I don't know what you suggest by keeping cachelines hot in the right way?

What I was told about the database test is that it collects lists of objects from various processors that are then freed on a different processor. This means all objects are cache cold.

Nick Piggin

author

2008-12-15 14:16 UTC #14 lore raw

Quoted 6 lines · Christoph Lameter

Quoted 4 lines · Nick Piggin
Quoted 3 lines
Does this mean that SLQB is less efficient than SLUB for off node allocations? SLUB can do off node allocations from the per cpu objects. It does not need to make the distinction for allocation.

Quoted 6 lines

Quoted 4 lines
I haven't measured them, but that could be the case. However I haven't found a workload that does a lot of off-node allocations (short lived allocations are better on-node, and long lived ones are not going to be so numerous).
A memoryless node is a case where all allocations will be like that.

Yes. Can the memoryless node revert to a default (closest) memory node?

Quoted 12 lines

Quoted 3 lines
That's more complexity, though. Given that objects are often hot when they are freed, and need to be touched after they are allocated anyway, the simple queue seems to be reasonable.
Yup.
Quoted 5 lines
This case does improve the database score by around 1.5-2%, yes. I don't know what you mean exactly, though. What case, and what do you mean by bad cache unfriendly programming? I would be very interested in improving that benchmark of course, but I don't know what you suggest by keeping cachelines hot in the right way?

Quoted 3 lines

What I was told about the database test is that it collects lists of objects from various processors that are then freed on a different processor. This means all objects are cache cold.

Well it's running an unmodified kernel... the database itself I guess is just submitting direct-IO requests from multiple processes to multiple disks. The objects should be pretty warm on the freeing CPU, but yes it would take a cacheline transfer at some level I guess.

Christoph Lameter

2008-12-15 15:03 UTC #15 lore raw

Quoted 3 lines · Nick Piggin

Quoted 1 line
A memoryless node is a case where all allocations will be like that.
Yes. Can the memoryless node revert to a default (closest) memory node?

It should do that but the node we allocat from will still be not the local node. The local_node will only have processors. No memory.

MinChan Kim

2008-12-15 23:40 UTC #16 lore raw

In reply to Nick Piggin

Hi, Nick.
I am interested in SLQB.
So I tested slqb, slub, slab by kernel compile time.

make all -j 8

slqb and slub not DEBUG.
my test environment is as follows.

cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz
stepping : 11
cpu MHz : 1600.000
cache size : 4096 KB

Below is average for ten time test.

slab :
user : 2376.484, system : 192.616 elapsed : 12:22.0 slub :
user : 2378.439, system : 194.989 elapsed : 12:22.4 slqb :
user : 2380.556, system : 194.801 elapsed : 12:23.0

so, slqb is rather slow although it is a big difference. Interestingly, slqb consumes less time than slub in system.

And I found some trivial bug. :)

<snip>

Quoted 5 lines

mm/slqb.c new file +5 -0

+static struct slqb_page *new_slab_page(struct kmem_cache *s, gfp_t flags, int node)
+{
+       struct slqb_page *page;
+       void *start;
+       void *last;

mm/slqb.c line 942

Quoted 10 lines

mm/slqb.c new file +10 -0

+       void *p;
+
+       BUG_ON(flags & GFP_SLAB_BUG_MASK);
+
+       page = allocate_slab(s,
+               flags & (GFP_RECLAIM_MASK | GFP_CONSTRAINT_MASK), node);
+       if (!page)
+               goto out;
+
+       page->flags |= 1 << PG_slab;

PG_slab set is redundant.
It's already set in alloc_slqb_pags_node.

Quoted 4 lines

mm/slqb.c new file +4 -0

+       start = page_address(&page->page);
+
+       if (unlikely(slab_poison(s)))
+               memset(start, POISON_INUSE, PAGE_SIZE << s->order);

<snip>

Quoted 19 lines

mm/slqb.c new file +19 -0

+void kfree(const void *object)
+{
+       struct kmem_cache *s;
+       struct page *p;
+       struct slqb_page *page;
+       unsigned long flags;
+
+       if (unlikely(ZERO_OR_NULL_PTR(object)))
+               return;
+
+       p = virt_to_page(object);
+       prefetch(p);
+       prefetchw(object);
+
+#ifdef CONFIG_SLQB_DEBUG
+       page = (struct slqb_page *)compound_head(p);
+       s = page->list->cache;
+       debug_check_no_locks_freed(object, s->objsize);
+       if (likely(object) && unlikely(slab_debug(s))) {

mm/slqb.c line 2185

Quoted 10 lines

mm/slqb.c new file +10 -0

+               if (unlikely(!free_debug_processing(s, object, __builtin_return_address(0))))
+                       return;
+       }
+#endif
+
+       local_irq_save(flags);
+#ifndef CONFIG_SLQB_DEBUG
+       page = (struct slqb_page *)compound_head(p);
+       s = page->list->cache;
+#endif

If it is not defined CONFIG_SLQB_DEBUG, page is garbage.

Quoted 5 lines

mm/slqb.c new file +5 -0

+       __slab_free(s, page, object);
+       local_irq_restore(flags);
+}
+EXPORT_SYMBOL(kfree);
+

Signature · 7 lines

Kinds regards,
MinChan Kim
--
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>

Nick Piggin

author

2008-12-17 06:41 UTC #17 lore raw

Quoted 25 lines · MinChan Kim

Hi, Nick.
I am interested in SLQB.
So I tested slqb, slub, slab by kernel compile time.
make all -j 8
slqb and slub not DEBUG.
my test environment is as follows.
cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz
stepping : 11
cpu MHz : 1600.000
cache size : 4096 KB
Below is average for ten time test.
slab :
user : 2376.484, system : 192.616 elapsed : 12:22.0 slub :
user : 2378.439, system : 194.989 elapsed : 12:22.4 slqb :
user : 2380.556, system : 194.801 elapsed : 12:23.0

Quoted 2 lines

so, slqb is rather slow although it is a big difference. Interestingly, slqb consumes less time than slub in system.

Thanks, interesting test. kbuild is not very slab allocator intensive, so I hadn't thought of trying it. Possibly the object cacheline layout of longer lived allocations changes the behaviour (increased user time could indicate that).

I've been making a few changes to that, and hopefully slqb is slightly improved now (the margin is much closer, seems within the noise with SLUB on my NUMA opteron now, although that's a very different system).

The biggest bug I fixed was that the NUMA path wasn't being taken in kmem_cache_free on NUMA systems (oops), but that wouldn't change your result. But I did make some other changes too, eg in prefetching.

Quoted 14 lines

And I found some trivial bug. :)

<snip>

Quoted 10 lines

(quoted diff) +10 -0

+static struct slqb_page *new_slab_page(struct kmem_cache *s, gfp_t flags, int node)
+{
+       struct slqb_page *page;
+       void *start;
+       void *last;
+       void *p;
+
+       BUG_ON(flags & GFP_SLAB_BUG_MASK);
+
+       page = allocate_slab(s,

Quoted 8 lines

Review
Quoted 5 lines
(quoted diff) +5 -0
+               flags & (GFP_RECLAIM_MASK | GFP_CONSTRAINT_MASK), node);
+       if (!page)
+               goto out;
+
+       page->flags |= 1 << PG_slab;
PG_slab set is redundant.
It's already set in alloc_slqb_pags_node.

Thanks, fixed.

Quoted 30 lines

Quoted 4 lines

(quoted diff) +4 -0

+       start = page_address(&page->page);
+
+       if (unlikely(slab_poison(s)))
+               memset(start, POISON_INUSE, PAGE_SIZE << s->order);

<snip>

Quoted 23 lines

(quoted diff) +23 -0

+void kfree(const void *object)
+{
+       struct kmem_cache *s;
+       struct page *p;
+       struct slqb_page *page;
+       unsigned long flags;
+
+       if (unlikely(ZERO_OR_NULL_PTR(object)))
+               return;
+
+       p = virt_to_page(object);
+       prefetch(p);
+       prefetchw(object);
+
+#ifdef CONFIG_SLQB_DEBUG
+       page = (struct slqb_page *)compound_head(p);
+       s = page->list->cache;
+       debug_check_no_locks_freed(object, s->objsize);
+       if (likely(object) && unlikely(slab_debug(s))) {
+               if (unlikely(!free_debug_processing(s, object, __builtin_return_address(0))))
+                       return;
+       }
+#endif

Quoted 8 lines

Review
Quoted 6 lines
(quoted diff) +6 -0
+
+       local_irq_save(flags);
+#ifndef CONFIG_SLQB_DEBUG
+       page = (struct slqb_page *)compound_head(p);
+       s = page->list->cache;
+#endif
If it is not defined CONFIG_SLQB_DEBUG, page is garbage.

Thanks... I've cleaned up that path significantly.

---

include/linux/rcupdate.h +1 ~~-10~~

Index: linux-2.6/include/linux/rcupdate.h
===================================================================
@@ -33,6 +33,7 @@
 #ifndef __LINUX_RCUPDATE_H
 #define __LINUX_RCUPDATE_H
 
+#include <linux/rcu_types.h>
 #include <linux/cache.h>
 #include <linux/spinlock.h>
 #include <linux/threads.h>

@@ -42,16 +43,6 @@
 #include <linux/lockdep.h>
 #include <linux/completion.h>
 
-/**
- * struct rcu_head - callback structure for use with RCU
- * @next: next update requests in a list
- * @func: actual update function to call after the grace period.
- */
-struct rcu_head {
-	struct rcu_head *next;
-	void (*func)(struct rcu_head *head);
-};
-
 #ifdef CONFIG_CLASSIC_RCU
 #include <linux/rcuclassic.h>
 #else /* #ifdef CONFIG_CLASSIC_RCU */

include/linux/slqb_def.h new file +274 -0

274 lines not on this page · raw message

init/Kconfig +9 -1

Index: linux-2.6/init/Kconfig
===================================================================
@@ -760,6 +760,11 @@ config SLUB_DEBUG
 	  SLUB sysfs support. /sys/slab will not exist and there will be
 	  no support for cache validation etc.
 
+config SLQB_DEBUG
+	default y
+	bool "Enable SLQB debugging support"
+	depends on SLQB
+
 choice
 	prompt "Choose SLAB allocator"
 	default SLUB

@@ -783,6 +788,9 @@ config SLUB
 	   and has enhanced diagnostics. SLUB is the default choice for
 	   a slab allocator.
 
+config SLQB
+	bool "SLQB (Qeued allocator)"
+
 config SLOB
 	depends on EMBEDDED
 	bool "SLOB (Simple Allocator)"

@@ -823,7 +831,7 @@ config HAVE_GENERIC_DMA_COHERENT
 config SLABINFO
 	bool
 	depends on PROC_FS
-	depends on SLAB || SLUB_DEBUG
+	depends on SLAB || SLUB_DEBUG || SLQB
 	default y
 
 config RT_MUTEXES

lib/Kconfig.debug +10 -0

Index: linux-2.6/lib/Kconfig.debug
===================================================================
@@ -290,6 +290,16 @@ config SLUB_STATS
 	  out which slabs are relevant to a particular load.
 	  Try running: slabinfo -DA
 
+config SLQB_DEBUG_ON
+	bool "SLQB debugging on by default"
+	depends on SLQB_DEBUG
+	default n
+
+config SLQB_STATS2
+	default n
+	bool "Enable SLQB performance statistics"
+	depends on SLQB
+
 config DEBUG_PREEMPT
 	bool "Debug preemptible kernel"
 	depends on DEBUG_KERNEL && PREEMPT && (TRACE_IRQFLAGS_SUPPORT || PPC64)

mm/slqb.c new file +2897 -0

2,611 lines not on this page · raw message

include/linux/slab.h +4 -2

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

Lines of this file are not shown. View the raw message.

mm/Makefile +1 -0

Index: linux-2.6/mm/Makefile
===================================================================

Lines of this file are not shown. View the raw message.

include/linux/rcu_types.h new file +18 -0

Index: linux-2.6/include/linux/rcu_types.h
===================================================================

Lines of this file are not shown. View the raw message.

include/linux/vmstat.h +16 -0

Index: linux-2.6/include/linux/vmstat.h
===================================================================

Lines of this file are not shown. View the raw message.

mm/vmstat.c +15 -0

Index: linux-2.6/mm/vmstat.c
===================================================================

Lines of this file are not shown. View the raw message.

arch/x86/include/asm/page.h +1 -0

Index: linux-2.6/arch/x86/include/asm/page.h
===================================================================

Lines of this file are not shown. View the raw message.

include/linux/mm.h +4 -0

Index: linux-2.6/include/linux/mm.h
===================================================================

Lines of this file are not shown. View the raw message.

The rest of this diff is not shown. View the raw message.

Part of the diff is not shown here. View the raw message.

MinChan Kim

2008-12-17 06:59 UTC #18 lore raw

Quoted 26 lines · Nick Piggin

Quoted 25 lines · MinChan Kim
Hi, Nick.
I am interested in SLQB.
So I tested slqb, slub, slab by kernel compile time.
make all -j 8
slqb and slub not DEBUG.
my test environment is as follows.
cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz
stepping : 11
cpu MHz : 1600.000
cache size : 4096 KB
Below is average for ten time test.
slab :
user : 2376.484, system : 192.616 elapsed : 12:22.0 slub :
user : 2378.439, system : 194.989 elapsed : 12:22.4 slqb :
user : 2380.556, system : 194.801 elapsed : 12:23.0

Quoted 4 lines

Quoted 2 lines
so, slqb is rather slow although it is a big difference. Interestingly, slqb consumes less time than slub in system.
Thanks, interesting test. kbuild is not very slab allocator intensive,

Let me know what is popular benchmark program in slab allocator. I will try with it. :)

Quoted 3 lines

so I hadn't thought of trying it. Possibly the object cacheline layout of longer lived allocations changes the behaviour (increased user time could indicate that).

What mean "object cacheline layout of loger lived allocations" ?

Quoted 7 lines

I've been making a few changes to that, and hopefully slqb is slightly improved now (the margin is much closer, seems within the noise with SLUB on my NUMA opteron now, although that's a very different system).
The biggest bug I fixed was that the NUMA path wasn't being taken in kmem_cache_free on NUMA systems (oops), but that wouldn't change your result. But I did make some other changes too, eg in prefetching.

OK. I will review and test your new patch in my machine.

Signature · 7 lines

Kinds regards,
MinChan Kim
--
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>

Nick Piggin

author

2008-12-17 07:08 UTC #19 lore raw

Quoted 10 lines · MinChan Kim

Quoted 9 lines · Nick Piggin
Quoted 9 lines
Below is average for ten time test.
slab :
user : 2376.484, system : 192.616 elapsed : 12:22.0 slub :
user : 2378.439, system : 194.989 elapsed : 12:22.4 slqb :
user : 2380.556, system : 194.801 elapsed : 12:23.0

Quoted 7 lines

Quoted 4 lines
Quoted 2 lines
so, slqb is rather slow although it is a big difference. Interestingly, slqb consumes less time than slub in system.
Thanks, interesting test. kbuild is not very slab allocator intensive,
Let me know what is popular benchmark program in slab allocator. I will try with it. :)

That's not to say it is a bad benchmark :) If it shows up a difference and is a useful workload like kbuild, then it is a good benchmark.

Allocator changes tend to show up more when there is a lot of network or disk IO happening. But it is good to see other tets too, so any numbers you get are welcome.

Quoted 5 lines

Quoted 3 lines
so I hadn't thought of trying it. Possibly the object cacheline layout of longer lived allocations changes the behaviour (increased user time could indicate that).
What mean "object cacheline layout of loger lived allocations" ?

For example, different allocation schemes will alter the chances of getting different ways (colours), or false sharing. SLUB and SLQB for example allow as fine as 8 byte allocation granularity wheras SLAB goes down to 32 bytes, so small objects *could* be more prone to false sharing. I don't know for sure at this stage, just guessing ;)

The difference doesn't show up significantly on my system, so profiling doesn't reveal anything (I guess even on your system it would be difficult to profile because it is not a huge difference).

Quoted 9 lines

Quoted 7 lines
I've been making a few changes to that, and hopefully slqb is slightly improved now (the margin is much closer, seems within the noise with SLUB on my NUMA opteron now, although that's a very different system).
The biggest bug I fixed was that the NUMA path wasn't being taken in kmem_cache_free on NUMA systems (oops), but that wouldn't change your result. But I did make some other changes too, eg in prefetching.
OK. I will review and test your new patch in my machine.

Thanks! Code style and comments should be improved quite a bit now.

Zhang, Yanmin

2008-12-19 07:46 UTC #20 lore raw

In reply to Nick Piggin

Quoted 40 lines · Nick Piggin

(Re)introducing SLQB allocator. Q for queued, but in reality, SLAB and SLUB also have queues of things as well, so "Q" is just a meaningless differentiator :)
I've kept working on SLQB slab allocator because I don't agree with the design choices in SLUB, and I'm worried about the push to make it the one true allocator.
My primary goal in SLQB is performance, secondarily are order-0 page allocations, and memory consumption.
I have worked with the Linux guys at Intel to ensure that SLQB is comparable to SLAB in their OLTP performance benchmark. Recently that goal has been reached -- so SLQB performs comparably well to SLAB on that test (it's within the noise).
I've also been comparing SLQB with SLAB and SLUB in other benchmarks, and trying to ensure it is as good or better. I don't know if that's always the case, but nothing obvious has gone wrong (it's sometimes hard to find meaningful benchmarks that exercise slab in interesting ways).
Now it isn't exactly complete -- debugging, tracking, stats, etc. code is not always in the best shape, however I have been focusing on performance of the core allocator. No matter how good the rest is if the core code is poor... But it boots, works, is pretty stable.
SLQB, like SLUB and unlike SLAB, doesn't have greater than linear memory consumption growth with the number of CPUs or nodes.
SLQB tries to be very page-size agnostic. And it tries very hard to use order-0 pages. This is good for both page allocator fragmentation, and slab fragmentation. I don't like that SLUB performs significantly worse with order-0 pages in some workloads.
SLQB goes to some lengths to optimise remote-freeing cases (allocate on one CPU, free on another). It seems to work well, but there are a *lot* of possible ways this can be implemented especially when NUMA comes into play, so I'd like to know of workloads where remote freeing happens a lot, and perhaps look at alternative ways to do it.

Quoted 7 lines

SLQB initialistaion code attempts to be as simple and un-clever as possible. There are no multiple phases where different things come up. There is no weird self bootstrapping stuff. It just statically allocates the structures required to create the slabs that allocate other slab structures.
I'm going to continue working on this as I get time, and I plan to soon ask to have it merged. It would be great if people could comment or test it.

Nick,

I tested your patch on a couple of x86-64 machines with kernel 2.6.28-rc8, mostly comparing with SLUB. I used many benchmarks, such like specjbb/cpu2k/aim7/hackbench/tbench/netperf /dbench/volanoMark/kbuild/oltp(mysql+sysbench) and so on. The result has no big difference from the one of SLUB, except:

1) kbuild: On my 8-core stoakley machine, I see about 20% improvement with SLQB. But on 16-core tigerton,there is about 6% regression. I reran the testing with CONFIG_SLUB=y and 'slabinfo -AD' showed kmalloc4096 is proactive.

2) netperf UDP loopback testing: I bind the server process and client process on different physical cpu.

	UDP-U-4k: 20% improvement than the one of SLUB;
	UDP-U-1k: less than 2% improvement;
	UDP-RR-1: 3% improvement;
	UDP-RR-512: 2% improvement;
	The improvement on 8-core stoakley is close to the one on 16-core tigerton.
	TCP testing has no such improvement/regression although there might be about 1%~2%

variation.

3) Real network netperf testing: start 64 client processes on 1 machine and 64 servers on another machine. UDP-RR-1 has about 5% improvement. Others are not so clear.

4) hackbench: On 16-core tigerton, I see about 5% improvement, for example,

	the result(running time) of 'hackbench 100 process 2000' is 24.6(SLUB) versus 23(SLQB).
	But on 8-core stoakley, SLUB result is better than the one of SLQB, less than 5%.

5) volanoMark: The result with the default chatroom number (10) has no big difference, but if I use CPU_NUM*2 as the chatroom number, there is about 5%~12% improvement with SLQB.

SLUB has a good tool, slabinfo, to show lots of useful information, including alloc/free statistics. SLQB has no such tool, even no such data.

yanmin