Re: [rfc][patch] SLQB slab allocator

[Eric Dumazet <dada1@cosmosbay.com>]

Nick Piggin a écrit :
> (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.
> 

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