LinuxLists.cc - [patch] SLQB slab allocator

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

Hi Nick,

On Wed, Jan 14, 2009 at 11:04 AM, Nick Piggin <[email protected]> wrote:
> This is the latest SLQB patch. Since last time, we have imported the sysfs
> framework from SLUB, and added specific event counters things for SLQB. I
> had initially been somewhat against this because it makes SLQB depend on
> another complex subsystem (which itself depends back on the slab allocator).
> But I guess it is not fundamentally different than /proc, and there needs to
> be some reporting somewhere. The individual per-slab counters really do make
> performance analysis much easier. There is a Documentation/vm/slqbinfo.c
> file, which is a parser adapted from slabinfo.c for SLUB.
>
> Fixed some bugs, including a nasty one that was causing remote objects to
> sneak onto local freelist, which would mean NUMA allocation was basically
> broken.
>
> The NUMA side of things is now much more complete. NUMA policies are obeyed.
> There is still a known bug where it won't run on a system with CPU-only
> nodes.
>
> CONFIG options are improved.
>
> Credit to some of the engineers at Intel for helping run tests, contributing
> ideas and patches to improve performance and fix bugs.
>
> I think it is getting to the point where it is stable and featureful. It
> really needs to be further proven in the performance area. We'd welcome
> any performance results or suggestions for tests to run.
>
> After this round of review/feedback, I plan to set about getting SLQB merged.

The code looks sane but I am still bit unhappy it's not a patchset on top of
SLUB. We've discussed this in the past and you mentioned that the design is
"completely different." Looking at it, I don't see any fundamental reason we
can't do a struct kmem_cache_list layer on top of SLUB which would make
merging of all this much less painful. I mean, at least in the past Linus hasn't
been too keen on adding yet another slab allocator to the kernel and I must
say judging from the SLAB -> SLUB experience, I'm not looking forward to it
either.

Also, to merge this, we need to see numbers. I assume SLQB fixes the
long-standing SLUB vs. SLAB regression reported by Intel and doesn't
introduce new performance regressions? Also, it would be nice for me to
be able to reproduce the numbers, especially for those tests where SLUB
performs worse.

One thing that puzzles me a bit is that in addition to the struct
kmem_cache_list caching, I also see things like cache coloring, avoiding
page allocator pass-through, and lots of prefetch hints in the code
which makes evaluating the performance differences quite difficult. If
these optimizations *are* a win, then why don't we add them to SLUB?

A completely different topic is memory efficiency of SLQB. The current
situation is that SLOB out-performs SLAB by huge margin whereas SLUB is
usually quite close. With the introduction of kmemtrace, I'm hopeful
that we will be able to fix up many of the badly fitting allocations in
the kernel to narrow the gap between SLUB and SLOB even more and I worry
SLQB will take us back to the SLAB numbers.

> +/*
> + * Primary per-cpu, per-kmem_cache structure.
> + */
> +struct kmem_cache_cpu {
> + struct kmem_cache_list list; /* List for node-local slabs. */
> +
> + unsigned int colour_next;

Do you see a performance improvement with cache coloring? IIRC,
Christoph has stated in the past that SLUB doesn't do it because newer
associative cache designs take care of the issue.

> +/*
> + * Constant size allocations use this path to find index into kmalloc caches
> + * arrays. get_slab() function is used for non-constant sizes.
> + */
> +static __always_inline int kmalloc_index(size_t size)
> +{
> + if (unlikely(!size))
> + return 0;
> + if (unlikely(size > 1UL << KMALLOC_SHIFT_SLQB_HIGH))
> + return 0;

SLUB doesn't have the above check. Does it fix an actual bug? Should we
add that to SLUB as well?

> +
> + if (unlikely(size <= KMALLOC_MIN_SIZE))
> + return KMALLOC_SHIFT_LOW;
> +
> +#if L1_CACHE_BYTES < 64
> + if (size > 64 && size <= 96)
> + return 1;
> +#endif
> +#if L1_CACHE_BYTES < 128
> + if (size > 128 && size <= 192)
> + return 2;
> +#endif
> + if (size <= 8) return 3;
> + if (size <= 16) return 4;
> + if (size <= 32) return 5;
> + if (size <= 64) return 6;
> + if (size <= 128) return 7;
> + if (size <= 256) return 8;
> + if (size <= 512) return 9;
> + if (size <= 1024) return 10;
> + if (size <= 2 * 1024) return 11;
> + if (size <= 4 * 1024) return 12;
> + if (size <= 8 * 1024) return 13;
> + if (size <= 16 * 1024) return 14;
> + if (size <= 32 * 1024) return 15;
> + if (size <= 64 * 1024) return 16;
> + if (size <= 128 * 1024) return 17;
> + if (size <= 256 * 1024) return 18;
> + if (size <= 512 * 1024) return 19;
> + if (size <= 1024 * 1024) return 20;
> + if (size <= 2 * 1024 * 1024) return 21;
> + return -1;

I suppose we could just make this one return zero and drop the above
check?

> +#define KMALLOC_HEADER (ARCH_KMALLOC_MINALIGN < sizeof(void *) ? sizeof(void *) : ARCH_KMALLOC_MINALIGN)
> +
> +static __always_inline void *kmalloc(size_t size, gfp_t flags)
> +{

So no page allocator pass-through, why is that? Looking at commit
aadb4bc4a1f9108c1d0fbd121827c936c2ed4217 ("SLUB: direct pass through of
page size or higher kmalloc requests"), I'd assume SQLB would get many
of the same benefits as well? It seems like a bad idea to hang on onto
large chuncks of pages in caches, no?

> + if (__builtin_constant_p(size)) {
> + struct kmem_cache *s;
> +
> + s = kmalloc_slab(size, flags);
> + if (unlikely(ZERO_OR_NULL_PTR(s)))
> + return s;
> +
> + return kmem_cache_alloc(s, flags);
> + }
> + return __kmalloc(size, flags);
> +}

> Index: linux-2.6/mm/slqb.c
> ===================================================================
> --- /dev/null
> +++ linux-2.6/mm/slqb.c
> @@ -0,0 +1,3368 @@
> +/*
> + * 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).
> + *
> + * Using ideas and code from mm/slab.c, mm/slob.c, and mm/slub.c.
> + */
> +
> +#include <linux/mm.h>
> +#include <linux/module.h>
> +#include <linux/bit_spinlock.h>
> +#include <linux/interrupt.h>
> +#include <linux/bitops.h>
> +#include <linux/slab.h>
> +#include <linux/seq_file.h>
> +#include <linux/cpu.h>
> +#include <linux/cpuset.h>
> +#include <linux/mempolicy.h>
> +#include <linux/ctype.h>
> +#include <linux/kallsyms.h>
> +#include <linux/memory.h>
> +
> +static inline int slab_hiwater(struct kmem_cache *s)
> +{
> + return s->hiwater;
> +}
> +
> +static inline int slab_freebatch(struct kmem_cache *s)
> +{
> + return s->freebatch;
> +}
> +
> +/*
> + * slqb_page overloads struct page, and is used to manage some slob allocation
> + * aspects, however to avoid the horrible mess in include/linux/mm_types.h,
> + * we'll just define our own struct slqb_page type variant here.
> + */

You say horrible mess, I say convenient. I think it's good that core vm
hackers who have no interest in the slab allocator can clearly see we're
overloading some of the struct page fields. But as SLOB does it like
this as well, I suppose we can keep it as-is.

> +struct slqb_page {
> + union {
> + struct {
> + unsigned long flags; /* mandatory */
> + atomic_t _count; /* mandatory */
> + unsigned int inuse; /* Nr of objects */
> + struct kmem_cache_list *list; /* Pointer to list */
> + void **freelist; /* freelist req. slab lock */
> + union {
> + struct list_head lru; /* misc. list */
> + struct rcu_head rcu_head; /* for rcu freeing */
> + };
> + };
> + struct page page;
> + };
> +};
> +static inline void struct_slqb_page_wrong_size(void)
> +{ BUILD_BUG_ON(sizeof(struct slqb_page) != sizeof(struct page)); }
> +
> +#define PG_SLQB_BIT (1 << PG_slab)
> +
> +static int kmem_size __read_mostly;
> +#ifdef CONFIG_NUMA
> +static int numa_platform __read_mostly;
> +#else
> +#define numa_platform 0
> +#endif

Hmm, why do we want to do this? If someone is running a CONFIG_NUMA
kernel on an UMA machine, let them suffer?

And if we *do* need to do this, can we move numa_platform() logic out of
the memory allocator?

> +#ifdef CONFIG_SMP
> +/*
> + * If enough objects have been remotely freed back to this list,
> + * remote_free_check will be set. In which case, we'll eventually come here
> + * to take those objects off our remote_free list and onto our LIFO freelist.
> + *
> + * Caller must be the owner CPU in the case of per-CPU list, or hold the node's
> + * list_lock in the case of per-node list.
> + */
> +static void claim_remote_free_list(struct kmem_cache *s, struct kmem_cache_list *l)
> +{
> + void **head, **tail;
> + int nr;
> +
> + VM_BUG_ON(!l->remote_free.list.head != !l->remote_free.list.tail);
> +
> + if (!l->remote_free.list.nr)
> + return;
> +
> + l->remote_free_check = 0;
> + head = l->remote_free.list.head;
> + prefetchw(head);

So this prefetchw() is for flush_free_list(), right? A comment would be
nice.

> +
> + spin_lock(&l->remote_free.lock);
> + l->remote_free.list.head = NULL;
> + tail = l->remote_free.list.tail;
> + l->remote_free.list.tail = NULL;
> + nr = l->remote_free.list.nr;
> + l->remote_free.list.nr = 0;
> + spin_unlock(&l->remote_free.lock);
> +
> + if (!l->freelist.nr)
> + l->freelist.head = head;
> + else
> + set_freepointer(s, l->freelist.tail, head);
> + l->freelist.tail = tail;
> +
> + l->freelist.nr += nr;
> +
> + slqb_stat_inc(l, CLAIM_REMOTE_LIST);
> + slqb_stat_add(l, CLAIM_REMOTE_LIST_OBJECTS, nr);
> +}
> +#endif
> +
> +/*
> + * Allocation fastpath. Get an object from the list's LIFO freelist, or
> + * return NULL if it is empty.
> + *
> + * Caller must be the owner CPU in the case of per-CPU list, or hold the node's
> + * list_lock in the case of per-node list.
> + */
> +static __always_inline void *__cache_list_get_object(struct kmem_cache *s, struct kmem_cache_list *l)
> +{
> + void *object;
> +
> + object = l->freelist.head;
> + if (likely(object)) {
> + void *next = get_freepointer(s, object);
> + VM_BUG_ON(!l->freelist.nr);
> + l->freelist.nr--;
> + l->freelist.head = next;
> + if (next)
> + prefetchw(next);

Why do we need this prefetchw() here?

> + return object;
> + }
> + VM_BUG_ON(l->freelist.nr);
> +
> +#ifdef CONFIG_SMP
> + if (unlikely(l->remote_free_check)) {
> + claim_remote_free_list(s, l);
> +
> + if (l->freelist.nr > slab_hiwater(s))
> + flush_free_list(s, l);
> +
> + /* repetition here helps gcc :( */
> + object = l->freelist.head;
> + if (likely(object)) {
> + void *next = get_freepointer(s, object);
> + VM_BUG_ON(!l->freelist.nr);
> + l->freelist.nr--;
> + l->freelist.head = next;
> + if (next)
> + prefetchw(next);

Or here?

> + return object;
> + }
> + VM_BUG_ON(l->freelist.nr);
> + }
> +#endif
> +
> + return NULL;
> +}
> +
> +/*
> + * Slow(er) path. Get a page from this list's existing pages. Will be a
> + * new empty page in the case that __slab_alloc_page has just been called
> + * (empty pages otherwise never get queued up on the lists), or a partial page
> + * already on the list.
> + *
> + * Caller must be the owner CPU in the case of per-CPU list, or hold the node's
> + * list_lock in the case of per-node list.
> + */
> +static noinline void *__cache_list_get_page(struct kmem_cache *s, struct kmem_cache_list *l)
> +{
> + struct slqb_page *page;
> + void *object;
> +
> + if (unlikely(!l->nr_partial))
> + return NULL;
> +
> + page = list_first_entry(&l->partial, struct slqb_page, lru);
> + VM_BUG_ON(page->inuse == s->objects);
> + if (page->inuse + 1 == s->objects) {
> + l->nr_partial--;
> + list_del(&page->lru);
> +/*XXX list_move(&page->lru, &l->full); */
> + }
> +
> + VM_BUG_ON(!page->freelist);
> +
> + page->inuse++;
> +
> +// VM_BUG_ON(node != -1 && node != slqb_page_to_nid(page));
> +
> + object = page->freelist;
> + page->freelist = get_freepointer(s, object);
> + if (page->freelist)
> + prefetchw(page->freelist);

I don't understand this prefetchw(). Who exactly is going to be updating
contents of page->freelist?

> +/*
> + * Perform some interrupts-on processing around the main allocation path
> + * (debug checking and memset()ing).
> + */
> +static __always_inline void *slab_alloc(struct kmem_cache *s,
> + gfp_t gfpflags, int node, void *addr)
> +{
> + void *object;
> + unsigned long flags;
> +
> +again:
> + local_irq_save(flags);
> + object = __slab_alloc(s, gfpflags, node);
> + local_irq_restore(flags);
> +

As a cleanup, you could just do:

if (unlikely(object == NULL))
return NULL;

here to avoid the double comparison. Maybe it even generates better asm.

> + if (unlikely(slab_debug(s)) && likely(object)) {
> + if (unlikely(!alloc_debug_processing(s, object, addr)))
> + goto again;
> + }
> +
> + if (unlikely(gfpflags & __GFP_ZERO) && likely(object))
> + memset(object, 0, s->objsize);
> +
> + return object;
> +}
> +
> +void *kmem_cache_alloc(struct kmem_cache *s, gfp_t gfpflags)
> +{
> + int node = -1;
> +#ifdef CONFIG_NUMA
> + if (unlikely(current->flags & (PF_SPREAD_SLAB | PF_MEMPOLICY)))
> + node = alternate_nid(s, gfpflags, node);
> +#endif
> + return slab_alloc(s, gfpflags, node, __builtin_return_address(0));

The return address is wrong when kmem_cache_alloc() is called through
__kmalloc().

As a side note, you can use the shorter _RET_IP_ instead of
builtin_return_address(0) everywhere.

Pekka

2009-01-14 11:47:24

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Wed, Jan 14, 2009 at 12:53:18PM +0200, Pekka Enberg wrote:
> Hi Nick,
>
> On Wed, Jan 14, 2009 at 11:04 AM, Nick Piggin <[email protected]> wrote:
> > This is the latest SLQB patch. Since last time, we have imported the sysfs
> > framework from SLUB, and added specific event counters things for SLQB. I
> > had initially been somewhat against this because it makes SLQB depend on
> > another complex subsystem (which itself depends back on the slab allocator).
> > But I guess it is not fundamentally different than /proc, and there needs to
> > be some reporting somewhere. The individual per-slab counters really do make
> > performance analysis much easier. There is a Documentation/vm/slqbinfo.c
> > file, which is a parser adapted from slabinfo.c for SLUB.
> >
> > Fixed some bugs, including a nasty one that was causing remote objects to
> > sneak onto local freelist, which would mean NUMA allocation was basically
> > broken.
> >
> > The NUMA side of things is now much more complete. NUMA policies are obeyed.
> > There is still a known bug where it won't run on a system with CPU-only
> > nodes.
> >
> > CONFIG options are improved.
> >
> > Credit to some of the engineers at Intel for helping run tests, contributing
> > ideas and patches to improve performance and fix bugs.
> >
> > I think it is getting to the point where it is stable and featureful. It
> > really needs to be further proven in the performance area. We'd welcome
> > any performance results or suggestions for tests to run.
> >
> > After this round of review/feedback, I plan to set about getting SLQB merged.
>
> The code looks sane but I am still bit unhappy it's not a patchset on top of
> SLUB. We've discussed this in the past and you mentioned that the design is
> "completely different." Looking at it, I don't see any fundamental reason we
> can't do a struct kmem_cache_list layer on top of SLUB which would make
> merging of all this much less painful. I mean, at least in the past Linus hasn't
> been too keen on adding yet another slab allocator to the kernel and I must
> say judging from the SLAB -> SLUB experience, I'm not looking forward to it
> either.

Well SLUB has all this stuff in it to attempt to make it "unqueued", or
semi unqueued. None of that is required with SLQB; after the object
queues go away, the rest of SLQB is little more than a per-CPU SLOB with
individual slabs. But also has important differences. It is per-cpu, obeys
NUMA policies strongly, frees unused pages immediately (after they drop
off the object lists done via periodic reaping). Another one of the major
things I specifically avoid for example is higher order allocations.

The core allocator algorithms are so completely different that it is
obviously as different from SLUB as SLUB is from SLAB (apart from peripheral
support code and code structure). So it may as well be a patch against
SLAB.

I will also prefer to maintain it myself because as I've said I don't
really agree with choices made in SLUB (and ergo SLUB developers don't
agree with SLQB).

Note that I'm not trying to be nasty here. Of course I raised objections
to things I don't like, and I don't think I'm right by default. Just IMO
SLUB has some problems. As do SLAB and SLQB of course. Nothing is
perfect.

Also, I don't want to propose replacing any of the other allocators yet,
until more performance data is gathered. People need to compare each one.
SLQB definitely is not a clear winner in all tests. At the moment I want
to see healthy competition and hopefully one day decide on just one of
the main 3.

> Also, to merge this, we need to see numbers. I assume SLQB fixes the
> long-standing SLUB vs. SLAB regression reported by Intel and doesn't
> introduce new performance regressions? Also, it would be nice for me to
> be able to reproduce the numbers, especially for those tests where SLUB
> performs worse.

It is comparable to SLAB on Intel's OLTP test. I don't know exactly
where SLUB lies, but I think it is several % below that.

No big obvious new regressions yet, but of course we won't know that
without a lot more testing. SLQB isn't outright winner in all cases.
For example, on machine A, tbench may be faster with SLAB, but on
machine B it turns out to be faster on SLQB. Another test might show
SLUB is better.

> One thing that puzzles me a bit is that in addition to the struct
> kmem_cache_list caching, I also see things like cache coloring, avoiding
> page allocator pass-through, and lots of prefetch hints in the code
> which makes evaluating the performance differences quite difficult. If
> these optimizations *are* a win, then why don't we add them to SLUB?

I don't know. I don't have enough time of day to work on SLQB enough,
let alone attempt to do all this for SLUB as well. Especially when I
think there are fundamental problems with the basic design of it.

None of those optimisations you mention really showed a noticable win
anywhere (except avoiding page allocator pass-through perhaps, simply
because that is not an optimisation, rather it would be a de-optimisation
to *add* page allocator pass-through for SLQB, so maybe it would aslow
down some loads).

Cache colouring was just brought over from SLAB. prefetching was done
by looking at cache misses generally, and attempting to reduce them.
But you end up barely making a significant difference or just pushing
the cost elsewhere really. Down to the level of prefetching it is
going to hugely depend on the exact behaviour of the workload and
the allocator.

> A completely different topic is memory efficiency of SLQB. The current
> situation is that SLOB out-performs SLAB by huge margin whereas SLUB is
> usually quite close. With the introduction of kmemtrace, I'm hopeful
> that we will be able to fix up many of the badly fitting allocations in
> the kernel to narrow the gap between SLUB and SLOB even more and I worry
> SLQB will take us back to the SLAB numbers.

Fundamentally it is more like SLOB and SLUB in that it uses object
pointers and can allocate down to very small sizes. It doesn't have
O(NR_CPUS^2) type behaviours or preallocated array caches like SLAB.
I didn't look closely at memory efficiency, but I have no reason to
think it would be a problem.

> > +/*
> > + * Primary per-cpu, per-kmem_cache structure.
> > + */
> > +struct kmem_cache_cpu {
> > + struct kmem_cache_list list; /* List for node-local slabs. */
> > +
> > + unsigned int colour_next;
>
> Do you see a performance improvement with cache coloring? IIRC,
> Christoph has stated in the past that SLUB doesn't do it because newer
> associative cache designs take care of the issue.

No I haven't seen an improvement.

> > +/*
> > + * Constant size allocations use this path to find index into kmalloc caches
> > + * arrays. get_slab() function is used for non-constant sizes.
> > + */
> > +static __always_inline int kmalloc_index(size_t size)
> > +{
> > + if (unlikely(!size))
> > + return 0;
> > + if (unlikely(size > 1UL << KMALLOC_SHIFT_SLQB_HIGH))
> > + return 0;
>
> SLUB doesn't have the above check. Does it fix an actual bug? Should we
> add that to SLUB as well?

I think it is OK because of page allocator passthrough.

> > + if (size <= 64) return 6;
> > + if (size <= 128) return 7;
> > + if (size <= 256) return 8;
> > + if (size <= 512) return 9;
> > + if (size <= 1024) return 10;
> > + if (size <= 2 * 1024) return 11;
> > + if (size <= 4 * 1024) return 12;
> > + if (size <= 8 * 1024) return 13;
> > + if (size <= 16 * 1024) return 14;
> > + if (size <= 32 * 1024) return 15;
> > + if (size <= 64 * 1024) return 16;
> > + if (size <= 128 * 1024) return 17;
> > + if (size <= 256 * 1024) return 18;
> > + if (size <= 512 * 1024) return 19;
> > + if (size <= 1024 * 1024) return 20;
> > + if (size <= 2 * 1024 * 1024) return 21;
> > + return -1;
>
> I suppose we could just make this one return zero and drop the above
> check?

I guess so... although this is for the constant folded path anyway,
so efficiency is not an issue.

> > +#define KMALLOC_HEADER (ARCH_KMALLOC_MINALIGN < sizeof(void *) ? sizeof(void *) : ARCH_KMALLOC_MINALIGN)
> > +
> > +static __always_inline void *kmalloc(size_t size, gfp_t flags)
> > +{
>
> So no page allocator pass-through, why is that? Looking at commit
> aadb4bc4a1f9108c1d0fbd121827c936c2ed4217 ("SLUB: direct pass through of
> page size or higher kmalloc requests"), I'd assume SQLB would get many
> of the same benefits as well? It seems like a bad idea to hang on onto
> large chuncks of pages in caches, no?

I don't think so. From that commit:

Advantages:
- Reduces memory overhead for kmalloc array

Fair point. But I'm attempting to compete primarily with SLAB than SLOB.

- Large kmalloc operations are faster since they do not
need to pass through the slab allocator to get to the
page allocator.

SLQB is faster than the page allocator.

- Performance increase of 10%-20% on alloc and 50% on free for
PAGE_SIZEd allocations.
SLUB must call page allocator for each alloc anyways since
the higher order pages which that allowed avoiding the page alloc calls
are not available in a reliable way anymore. So we are basically removing
useless slab allocator overhead.

SLQB is more like SLAB in this regard so it doesn't have this problme.

- Large kmallocs yields page aligned object which is what
SLAB did. Bad things like using page sized kmalloc allocations to
stand in for page allocate allocs can be transparently handled and are not
distinguishable from page allocator uses.

I don't understand this one. Definitely SLQB should give page aligned
objects for large kmallocs too.

- Checking for too large objects can be removed since
it is done by the page allocator.

But the check is made for size > PAGE_SIZE anyway, so I don't see the
win.

Drawbacks:
- No accounting for large kmalloc slab allocations anymore
- No debugging of large kmalloc slab allocations.

And doesn't suffer these drawbacks either of course.

> > +/*
> > + * slqb_page overloads struct page, and is used to manage some slob allocation
> > + * aspects, however to avoid the horrible mess in include/linux/mm_types.h,
> > + * we'll just define our own struct slqb_page type variant here.
> > + */
>
> You say horrible mess, I say convenient. I think it's good that core vm
> hackers who have no interest in the slab allocator can clearly see we're
> overloading some of the struct page fields.

Yeah, but you can't really. There are so many places that overload them
for different things and don't tell you about it right in that file. But
it mostly works because we have nice layering and compartmentalisation.

Anyway IIRC my initial patches to do some of these conversions actually
either put the definitions into mm_types.h or at least added references
to them in mm_types.h. It is the better way to go really because you get
better type checking and it is readable. You may say the horrible mess is
readable. Barely. Imagine how it would be if we put everything in there.

> But as SLOB does it like
> this as well, I suppose we can keep it as-is.

I added that ;)

> > +struct slqb_page {
> > + union {
> > + struct {
> > + unsigned long flags; /* mandatory */
> > + atomic_t _count; /* mandatory */
> > + unsigned int inuse; /* Nr of objects */
> > + struct kmem_cache_list *list; /* Pointer to list */
> > + void **freelist; /* freelist req. slab lock */
> > + union {
> > + struct list_head lru; /* misc. list */
> > + struct rcu_head rcu_head; /* for rcu freeing */
> > + };
> > + };
> > + struct page page;
> > + };
> > +};
> > +static inline void struct_slqb_page_wrong_size(void)
> > +{ BUILD_BUG_ON(sizeof(struct slqb_page) != sizeof(struct page)); }
> > +
> > +#define PG_SLQB_BIT (1 << PG_slab)
> > +
> > +static int kmem_size __read_mostly;
> > +#ifdef CONFIG_NUMA
> > +static int numa_platform __read_mostly;
> > +#else
> > +#define numa_platform 0
> > +#endif
>
> Hmm, why do we want to do this? If someone is running a CONFIG_NUMA
> kernel on an UMA machine, let them suffer?

Distros, mainly. SLAB does the same thing of course. There is a tiny
downside for the NUMA case (not measurable, but obviously another branch).
Not worth another config option, although I guess there could be a
config option to basically say "this config is exactly my machine; not
the maximum capabilities of a machine intended to run on this kernel".
That could be useful to everyone, including here.

> And if we *do* need to do this, can we move numa_platform() logic out of
> the memory allocator?

Possible. If it is moved out of SLAB it would make my life (slightly)
easier

> > +#ifdef CONFIG_SMP
> > +/*
> > + * If enough objects have been remotely freed back to this list,
> > + * remote_free_check will be set. In which case, we'll eventually come here
> > + * to take those objects off our remote_free list and onto our LIFO freelist.
> > + *
> > + * Caller must be the owner CPU in the case of per-CPU list, or hold the node's
> > + * list_lock in the case of per-node list.
> > + */
> > +static void claim_remote_free_list(struct kmem_cache *s, struct kmem_cache_list *l)
> > +{
> > + void **head, **tail;
> > + int nr;
> > +
> > + VM_BUG_ON(!l->remote_free.list.head != !l->remote_free.list.tail);
> > +
> > + if (!l->remote_free.list.nr)
> > + return;
> > +
> > + l->remote_free_check = 0;
> > + head = l->remote_free.list.head;
> > + prefetchw(head);
>
> So this prefetchw() is for flush_free_list(), right? A comment would be
> nice.

Either the flush or the next allocation, whichever comes first.

Added a comment.

> > +static __always_inline void *__cache_list_get_object(struct kmem_cache *s, struct kmem_cache_list *l)
> > +{
> > + void *object;
> > +
> > + object = l->freelist.head;
> > + if (likely(object)) {
> > + void *next = get_freepointer(s, object);
> > + VM_BUG_ON(!l->freelist.nr);
> > + l->freelist.nr--;
> > + l->freelist.head = next;
> > + if (next)
> > + prefetchw(next);
>
> Why do we need this prefetchw() here?

For the next allocation call. But TBH I have not seen a significant
difference in any test. I alternate from commenting it out and not.
I guess when in doubt there should be less code and complexity...

> > + if (next)
> > + prefetchw(next);
>
> Or here?

Ditto.

> > +
> > + object = page->freelist;
> > + page->freelist = get_freepointer(s, object);
> > + if (page->freelist)
> > + prefetchw(page->freelist);
>
> I don't understand this prefetchw(). Who exactly is going to be updating
> contents of page->freelist?

Again, it is for the next allocation. This was shown to reduce cache
misses here in IIRC tbench, but I'm not sure if that translated to a
significant performance improvement.

An alternate approach I have is a patch called "batchfeed", which
basically loads the entire page freelist in this path. But it cost
complexity and the last free word in struct page (which could be
gained back at the cost of yet more complexity). So I'm still on
the fence with this. I will have to take reports of regressions and
see if things like this help.

> > +/*
> > + * Perform some interrupts-on processing around the main allocation path
> > + * (debug checking and memset()ing).
> > + */
> > +static __always_inline void *slab_alloc(struct kmem_cache *s,
> > + gfp_t gfpflags, int node, void *addr)
> > +{
> > + void *object;
> > + unsigned long flags;
> > +
> > +again:
> > + local_irq_save(flags);
> > + object = __slab_alloc(s, gfpflags, node);
> > + local_irq_restore(flags);
> > +
>
> As a cleanup, you could just do:
>
> if (unlikely(object == NULL))
> return NULL;
>
> here to avoid the double comparison. Maybe it even generates better asm.

Sometimes the stupid compiler loads a new literal to return with code
like this. I'll see.

>
> > + if (unlikely(slab_debug(s)) && likely(object)) {
> > + if (unlikely(!alloc_debug_processing(s, object, addr)))
> > + goto again;
> > + }
> > +
> > + if (unlikely(gfpflags & __GFP_ZERO) && likely(object))
> > + memset(object, 0, s->objsize);
> > +
> > + return object;
> > +}
> > +
> > +void *kmem_cache_alloc(struct kmem_cache *s, gfp_t gfpflags)
> > +{
> > + int node = -1;
> > +#ifdef CONFIG_NUMA
> > + if (unlikely(current->flags & (PF_SPREAD_SLAB | PF_MEMPOLICY)))
> > + node = alternate_nid(s, gfpflags, node);
> > +#endif
> > + return slab_alloc(s, gfpflags, node, __builtin_return_address(0));
>
> The return address is wrong when kmem_cache_alloc() is called through
> __kmalloc().

Ah, good catch.

> As a side note, you can use the shorter _RET_IP_ instead of
> builtin_return_address(0) everywhere.

OK.

Thanks for the comments and discussion so far.

Nick

2009-01-14 13:44:57

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

Hi Nick,

On Wed, Jan 14, 2009 at 1:47 PM, Nick Piggin <[email protected]> wrote:
> The core allocator algorithms are so completely different that it is
> obviously as different from SLUB as SLUB is from SLAB (apart from peripheral
> support code and code structure). So it may as well be a patch against
> SLAB.
>
> I will also prefer to maintain it myself because as I've said I don't
> really agree with choices made in SLUB (and ergo SLUB developers don't
> agree with SLQB).

Just for the record, I am only interesting in getting rid of SLAB (and
SLOB if we can serve the embedded folks as well in the future, sorry
Matt). Now, if that means we have to replace SLUB with SLQB, I am fine
with that. Judging from the SLAB -> SLUB experience, though, I am not
so sure adding a completely separate allocator is the way to get
there.

On Wed, Jan 14, 2009 at 1:47 PM, Nick Piggin <[email protected]> wrote:
> Note that I'm not trying to be nasty here. Of course I raised objections
> to things I don't like, and I don't think I'm right by default. Just IMO
> SLUB has some problems. As do SLAB and SLQB of course. Nothing is
> perfect.
>
> Also, I don't want to propose replacing any of the other allocators yet,
> until more performance data is gathered. People need to compare each one.
> SLQB definitely is not a clear winner in all tests. At the moment I want
> to see healthy competition and hopefully one day decide on just one of
> the main 3.

OK, then it is really up to Andrew and Linus to decide whether they
want to merge it or not. I'm not violently against it, it's just that
there's some maintenance overhead for API changes and for external
code like kmemcheck, kmemtrace, and failslab, that need hooks in the
slab allocator.

On Wed, Jan 14, 2009 at 1:47 PM, Nick Piggin <[email protected]> wrote:
>> One thing that puzzles me a bit is that in addition to the struct
>> kmem_cache_list caching, I also see things like cache coloring, avoiding
>> page allocator pass-through, and lots of prefetch hints in the code
>> which makes evaluating the performance differences quite difficult. If
>> these optimizations *are* a win, then why don't we add them to SLUB?
>
> I don't know. I don't have enough time of day to work on SLQB enough,
> let alone attempt to do all this for SLUB as well. Especially when I
> think there are fundamental problems with the basic design of it.
>
> None of those optimisations you mention really showed a noticable win
> anywhere (except avoiding page allocator pass-through perhaps, simply
> because that is not an optimisation, rather it would be a de-optimisation
> to *add* page allocator pass-through for SLQB, so maybe it would aslow
> down some loads).
>
> Cache colouring was just brought over from SLAB. prefetching was done
> by looking at cache misses generally, and attempting to reduce them.
> But you end up barely making a significant difference or just pushing
> the cost elsewhere really. Down to the level of prefetching it is
> going to hugely depend on the exact behaviour of the workload and
> the allocator.

As far as I understood, the prefetch optimizations can produce
unexpected results on some systems (yes, bit of hand-waving here), so
I would consider ripping them out. Even if cache coloring isn't a huge
win on most systems, it's probably not going to hurt either.

On Wed, Jan 14, 2009 at 1:47 PM, Nick Piggin <[email protected]> wrote:
>> A completely different topic is memory efficiency of SLQB. The current
>> situation is that SLOB out-performs SLAB by huge margin whereas SLUB is
>> usually quite close. With the introduction of kmemtrace, I'm hopeful
>> that we will be able to fix up many of the badly fitting allocations in
>> the kernel to narrow the gap between SLUB and SLOB even more and I worry
>> SLQB will take us back to the SLAB numbers.
>
> Fundamentally it is more like SLOB and SLUB in that it uses object
> pointers and can allocate down to very small sizes. It doesn't have
> O(NR_CPUS^2) type behaviours or preallocated array caches like SLAB.
> I didn't look closely at memory efficiency, but I have no reason to
> think it would be a problem.

Right, that's nice to hear.

On Wed, Jan 14, 2009 at 1:47 PM, Nick Piggin <[email protected]> wrote:
>> > +/*
>> > + * slqb_page overloads struct page, and is used to manage some slob allocation
>> > + * aspects, however to avoid the horrible mess in include/linux/mm_types.h,
>> > + * we'll just define our own struct slqb_page type variant here.
>> > + */
>>
>> You say horrible mess, I say convenient. I think it's good that core vm
>> hackers who have no interest in the slab allocator can clearly see we're
>> overloading some of the struct page fields.
>
> Yeah, but you can't really. There are so many places that overload them
> for different things and don't tell you about it right in that file. But
> it mostly works because we have nice layering and compartmentalisation.
>
> Anyway IIRC my initial patches to do some of these conversions actually
> either put the definitions into mm_types.h or at least added references
> to them in mm_types.h. It is the better way to go really because you get
> better type checking and it is readable. You may say the horrible mess is
> readable. Barely. Imagine how it would be if we put everything in there.

Well, if we only had one slab allocator... But yeah, point taken.

On Wed, Jan 14, 2009 at 1:47 PM, Nick Piggin <[email protected]> wrote:
>> > + object = page->freelist;
>> > + page->freelist = get_freepointer(s, object);
>> > + if (page->freelist)
>> > + prefetchw(page->freelist);
>>
>> I don't understand this prefetchw(). Who exactly is going to be updating
>> contents of page->freelist?
>
> Again, it is for the next allocation. This was shown to reduce cache
> misses here in IIRC tbench, but I'm not sure if that translated to a
> significant performance improvement.

I'm not sure why you would want to optimize for the next allocation. I
mean, I'd expect us to optimize for the kmalloc() + do some work +
kfree() case where prefetching is likely to hurt more than help. Not
that I have any numbers on this.

Pekka

2009-01-14 14:22:34

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Wed, Jan 14, 2009 at 03:44:44PM +0200, Pekka Enberg wrote:
> Hi Nick,
>
> On Wed, Jan 14, 2009 at 1:47 PM, Nick Piggin <[email protected]> wrote:
> > The core allocator algorithms are so completely different that it is
> > obviously as different from SLUB as SLUB is from SLAB (apart from peripheral
> > support code and code structure). So it may as well be a patch against
> > SLAB.
> >
> > I will also prefer to maintain it myself because as I've said I don't
> > really agree with choices made in SLUB (and ergo SLUB developers don't
> > agree with SLQB).
>
> Just for the record, I am only interesting in getting rid of SLAB (and
> SLOB if we can serve the embedded folks as well in the future, sorry
> Matt). Now, if that means we have to replace SLUB with SLQB, I am fine
> with that. Judging from the SLAB -> SLUB experience, though, I am not
> so sure adding a completely separate allocator is the way to get
> there.

The problem is there was apparently no plan for resolving the SLAB vs SLUB
strategy. And then features and things were added to one or the other one.
But on the other hand, the SLUB experience was a success in a way because
there were a lot of performance regressions found and fixed after it was
merged, for example.

I'd love to be able to justify replacing SLAB and SLUB today, but actually
it is simply never going to be trivial to discover performance regressions.
So I don't think outright replacement is great either (consider if SLUB
had replaced SLAB completely).

> On Wed, Jan 14, 2009 at 1:47 PM, Nick Piggin <[email protected]> wrote:
> > Note that I'm not trying to be nasty here. Of course I raised objections
> > to things I don't like, and I don't think I'm right by default. Just IMO
> > SLUB has some problems. As do SLAB and SLQB of course. Nothing is
> > perfect.
> >
> > Also, I don't want to propose replacing any of the other allocators yet,
> > until more performance data is gathered. People need to compare each one.
> > SLQB definitely is not a clear winner in all tests. At the moment I want
> > to see healthy competition and hopefully one day decide on just one of
> > the main 3.
>
> OK, then it is really up to Andrew and Linus to decide whether they
> want to merge it or not. I'm not violently against it, it's just that
> there's some maintenance overhead for API changes and for external
> code like kmemcheck, kmemtrace, and failslab, that need hooks in the
> slab allocator.

Sure. On the slab side, I would be happy to do that work.

We split the user base, which is a big problem if it drags out for years
like SLAB/SLUB. But if it is a very deliberate use of testing resources
in order to make progress on the issue, then that can be a positive.

> On Wed, Jan 14, 2009 at 1:47 PM, Nick Piggin <[email protected]> wrote:
> > Cache colouring was just brought over from SLAB. prefetching was done
> > by looking at cache misses generally, and attempting to reduce them.
> > But you end up barely making a significant difference or just pushing
> > the cost elsewhere really. Down to the level of prefetching it is
> > going to hugely depend on the exact behaviour of the workload and
> > the allocator.
>
> As far as I understood, the prefetch optimizations can produce
> unexpected results on some systems (yes, bit of hand-waving here), so
> I would consider ripping them out. Even if cache coloring isn't a huge
> win on most systems, it's probably not going to hurt either.

I hit problems on some microbenchmark where I was prefetching a NULL pointer in
some cases, which must have been causing the CPU to trap internally and alloc
overhead suddenly got much higher ;)

Possibly sometimes if you prefetch too early or when various queues are
already full, then it ends up causing slowdowns too.

> On Wed, Jan 14, 2009 at 1:47 PM, Nick Piggin <[email protected]> wrote:
> >> > + object = page->freelist;
> >> > + page->freelist = get_freepointer(s, object);
> >> > + if (page->freelist)
> >> > + prefetchw(page->freelist);
> >>
> >> I don't understand this prefetchw(). Who exactly is going to be updating
> >> contents of page->freelist?
> >
> > Again, it is for the next allocation. This was shown to reduce cache
> > misses here in IIRC tbench, but I'm not sure if that translated to a
> > significant performance improvement.
>
> I'm not sure why you would want to optimize for the next allocation. I
> mean, I'd expect us to optimize for the kmalloc() + do some work +
> kfree() case where prefetching is likely to hurt more than help. Not
> that I have any numbers on this.

That's true, OTOH if the time between allocations is large, then an
extra prefetch is just a small cost. If the time between them is
short, it might be a bigger win.

2009-01-14 14:45:44

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

Hi Nick,

On Wed, Jan 14, 2009 at 4:22 PM, Nick Piggin <[email protected]> wrote:
> The problem is there was apparently no plan for resolving the SLAB vs SLUB
> strategy. And then features and things were added to one or the other one.
> But on the other hand, the SLUB experience was a success in a way because
> there were a lot of performance regressions found and fixed after it was
> merged, for example.

That's not completely true. I can't speak for Christoph, but the
biggest problem I have is that I have _no way_ of reproducing or
analyzing the regression. I've tried out various benchmarks I have
access to but I haven't been able to find anything.

The hypothesis is that SLUB regresses because of kmalloc()/kfree()
ping-pong between CPUs and as far as I understood, Christoph thinks we
can improve SLUB with the per-cpu alloc patches and the freelist
management rework.

Don't get me wrong, though. I am happy you are able to work with the
Intel engineers to fix the long standing issue (I want it fixed too!)
but I would be happier if the end-result was few simple patches
against mm/slub.c :-).

On Wed, Jan 14, 2009 at 4:22 PM, Nick Piggin <[email protected]> wrote:
> I'd love to be able to justify replacing SLAB and SLUB today, but actually
> it is simply never going to be trivial to discover performance regressions.
> So I don't think outright replacement is great either (consider if SLUB
> had replaced SLAB completely).

If you ask me, I wish we *had* removed SLAB so relevant people could
have made a huge stink out of it and the regression would have been
taken care quickly ;-).

Pekka

2009-01-14 15:09:19

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Wed, Jan 14, 2009 at 04:45:15PM +0200, Pekka Enberg wrote:
> Hi Nick,
>
> On Wed, Jan 14, 2009 at 4:22 PM, Nick Piggin <[email protected]> wrote:
> > The problem is there was apparently no plan for resolving the SLAB vs SLUB
> > strategy. And then features and things were added to one or the other one.
> > But on the other hand, the SLUB experience was a success in a way because
> > there were a lot of performance regressions found and fixed after it was
> > merged, for example.
>
> That's not completely true. I can't speak for Christoph, but the
> biggest problem I have is that I have _no way_ of reproducing or
> analyzing the regression. I've tried out various benchmarks I have
> access to but I haven't been able to find anything.
>
> The hypothesis is that SLUB regresses because of kmalloc()/kfree()
> ping-pong between CPUs and as far as I understood, Christoph thinks we
> can improve SLUB with the per-cpu alloc patches and the freelist
> management rework.
>
> Don't get me wrong, though. I am happy you are able to work with the
> Intel engineers to fix the long standing issue (I want it fixed too!)
> but I would be happier if the end-result was few simple patches
> against mm/slub.c :-).

Right, but that regression isn't my only problem with SLUB. I think
higher order allocations could be much more damaging for more a wider
class of users. It is less common to see higher order allocation failure
reports in places other than lkml, where people tend to have systems
stay up longer and/or do a wider range of things with them.

The idea of removing queues doesn't seem so good to me. Queues are good.
You amortize or avoid all sorts of things with queues. We have them
everywhere in the kernel ;)

> On Wed, Jan 14, 2009 at 4:22 PM, Nick Piggin <[email protected]> wrote:
> > I'd love to be able to justify replacing SLAB and SLUB today, but actually
> > it is simply never going to be trivial to discover performance regressions.
> > So I don't think outright replacement is great either (consider if SLUB
> > had replaced SLAB completely).
>
> If you ask me, I wish we *had* removed SLAB so relevant people could
> have made a huge stink out of it and the regression would have been
> taken care quickly ;-).

Well, presumably the stink was made because we've been stuck with SLAB
for 2 years for some reason. But it is not only that one but there were
other regressions too. Point simply is that it would have been much
harder for users to detect if there even is a regression, what with all
the other changes happening.

2009-01-14 15:22:23

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

Hit send a bit too early here.

On Wed, Jan 14, 2009 at 04:09:00PM +0100, Nick Piggin wrote:
> On Wed, Jan 14, 2009 at 04:45:15PM +0200, Pekka Enberg wrote:
> >
> > Don't get me wrong, though. I am happy you are able to work with the
> > Intel engineers to fix the long standing issue (I want it fixed too!)
> > but I would be happier if the end-result was few simple patches
> > against mm/slub.c :-).
>
> Right, but that regression isn't my only problem with SLUB. I think
> higher order allocations could be much more damaging for more a wider
> class of users. It is less common to see higher order allocation failure

Sorry, *more* common.

> reports in places other than lkml, where people tend to have systems
> stay up longer and/or do a wider range of things with them.
>
> The idea of removing queues doesn't seem so good to me. Queues are good.
> You amortize or avoid all sorts of things with queues. We have them
> everywhere in the kernel ;)
>
>
> > On Wed, Jan 14, 2009 at 4:22 PM, Nick Piggin <[email protected]> wrote:
> > > I'd love to be able to justify replacing SLAB and SLUB today, but actually
> > > it is simply never going to be trivial to discover performance regressions.
> > > So I don't think outright replacement is great either (consider if SLUB
> > > had replaced SLAB completely).
> >
> > If you ask me, I wish we *had* removed SLAB so relevant people could
> > have made a huge stink out of it and the regression would have been
> > taken care quickly ;-).
>
> Well, presumably the stink was made because we've been stuck with SLAB
> for 2 years for some reason. But it is not only that one but there were
> other regressions too. Point simply is that it would have been much
> harder for users to detect if there even is a regression, what with all
> the other changes happening.

It would have been harder to detect SLUB vs SLAB regressions if they
had been forced to bisect (which could lead eg. to CFS, or GSO), rather
than select between two allocators.

And... IIRC, the Intel guys did make a stink but it wasn't considered
so important or worthwhile to fix for some reason? Anyway, the fact is
that it hadn't been fixed in SLUB. Hmm, I guess it is a significant
failure of SLUB that it hasn't managed to replace SLAB by this point.

2009-01-14 15:31:01

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

Hi Nick,

On Wed, Jan 14, 2009 at 5:22 PM, Nick Piggin <[email protected]> wrote:
> And... IIRC, the Intel guys did make a stink but it wasn't considered
> so important or worthwhile to fix for some reason? Anyway, the fact is
> that it hadn't been fixed in SLUB. Hmm, I guess it is a significant
> failure of SLUB that it hasn't managed to replace SLAB by this point.

Again, not speaking for Christoph, but *I* do consider the regression
to be important and I do want it to be fixed. I have asked for a test
case to reproduce the regression and/or oprofile reports but have yet
to receive them. I did fix one regression I saw with the fio benchmark
but unfortunately it wasn't the same regression the Intel guys are
hitting. I suppose we're in limbo now because the people who are
affected by the regression can simply turn on CONFIG_SLAB.

In any case, I do agree that the inability to replace SLAB with SLUB
is a failure on the latter. I'm just not totally convinced that it's
because the SLUB code is unfixable ;).

Pekka

2009-01-14 15:59:47

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Wed, Jan 14, 2009 at 05:30:48PM +0200, Pekka Enberg wrote:
> Hi Nick,
>
> On Wed, Jan 14, 2009 at 5:22 PM, Nick Piggin <[email protected]> wrote:
> > And... IIRC, the Intel guys did make a stink but it wasn't considered
> > so important or worthwhile to fix for some reason? Anyway, the fact is
> > that it hadn't been fixed in SLUB. Hmm, I guess it is a significant
> > failure of SLUB that it hasn't managed to replace SLAB by this point.
>
> Again, not speaking for Christoph, but *I* do consider the regression
> to be important and I do want it to be fixed. I have asked for a test
> case to reproduce the regression and/or oprofile reports but have yet
> to receive them. I did fix one regression I saw with the fio benchmark
> but unfortunately it wasn't the same regression the Intel guys are
> hitting. I suppose we're in limbo now because the people who are
> affected by the regression can simply turn on CONFIG_SLAB.

Mmm. SLES11 will ship with CONFIG_SLAB, FWIW. No I actually didn't
make any input into the decision. And I have mixed feelings about
that because there are places where SLAB is better.

But I must say that SLAB seems to be a really good allocator, and
outside of some types of microbenchmarks where it would sometimes
be much slower than SLAB, SLAB was often my main performance competitor
and often very hard to match with SLQB, let alone beat. That's not
to say SLUB wasn't also often the faster of the two, but I was
surprised at how good SLAB is.

> In any case, I do agree that the inability to replace SLAB with SLUB
> is a failure on the latter. I'm just not totally convinced that it's
> because the SLUB code is unfixable ;).

Well if you would like to consider SLQB as a fix for SLUB, that's
fine by me ;) Actually I guess it is a valid way to look at the problem:
SLQB solves the OLTP regression, so the only question is "what is the
downside of it?".

2009-01-14 18:02:16

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Wed, 14 Jan 2009, Nick Piggin wrote:

> Right, but that regression isn't my only problem with SLUB. I think
> higher order allocations could be much more damaging for more a wider
> class of users. It is less common to see higher order allocation failure
> reports in places other than lkml, where people tend to have systems
> stay up longer and/or do a wider range of things with them.

The higher orders can fail and will then result in the allocator doing
order 0 allocs. It is not a failure condition. Higher orders are an
advantage because they localize variables of the same type and therefore
reduce TLB pressure.

> The idea of removing queues doesn't seem so good to me. Queues are good.
> You amortize or avoid all sorts of things with queues. We have them
> everywhere in the kernel ;)

Queues require maintenance which introduces variability because queue
cleaning has to be done periodically and the queues grow in number if NUMA
scenarios have to be handled effectively. This is a big problem for low
latency applications (like in HPC). Spending far too much time optimizing
queue cleaning in SLAB lead to the SLUB idea.

2009-01-14 18:41:19

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Wed, 14 Jan 2009, Nick Piggin wrote:

> Well if you would like to consider SLQB as a fix for SLUB, that's
> fine by me ;) Actually I guess it is a valid way to look at the problem:
> SLQB solves the OLTP regression, so the only question is "what is the
> downside of it?".

The downside is that it brings the SLAB stuff back that SLUB was
designed to avoid. Queue expiration. The use of timers to expire at
uncontrollable intervals for user space. Object dispersal
in the kernel address space. Memory policy handling in the slab
allocator. Even seems to include periodic moving of objects between
queues. The NUMA stuff is still a bit foggy to me since it seems to assume
a mapping between cpus and nodes. There are cpuless nodes as well as
memoryless cpus.

SLQB maybe a good cleanup for SLAB. Its good that it is based on the
cleaned up code in SLUB but the fundamental design is SLAB (or rather the
Solaris allocator from which we got the design for all the queuing stuff
in the first place). It preserves many of the drawbacks of that code.

If SLQB would replace SLAB then there would be a lot of shared code
(debugging for example). Having a generic slab allocator framework may
then be possible within which a variety of algorithms may be implemented.

2009-01-15 06:03:45

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Wed, Jan 14, 2009 at 12:01:32PM -0600, Christoph Lameter wrote:
> On Wed, 14 Jan 2009, Nick Piggin wrote:
>
> > Right, but that regression isn't my only problem with SLUB. I think
> > higher order allocations could be much more damaging for more a wider
> > class of users. It is less common to see higher order allocation failure
> > reports in places other than lkml, where people tend to have systems
> > stay up longer and/or do a wider range of things with them.
>
> The higher orders can fail and will then result in the allocator doing
> order 0 allocs. It is not a failure condition.

But they increase pressure on the resource and reduce availability to
other higher order allocations. They accelerate the breakdown of the
anti-frag heuristics, and they make slab internal fragmentation worse.
They also simply cost more to allocate and free and reclaim.

> Higher orders are an
> advantage because they localize variables of the same type and therefore
> reduce TLB pressure.

They are also a disadvantage. The disadvantages are very real. The
advantage is a bit theoretical (how much really is it going to help
going from 4K to 32K, if you still have hundreds or thousands of
slabs anyway?). Also, there is no reason why the other allocators
cannot use higher orer allocations, but their big advantage is that
they don't need to.

> > The idea of removing queues doesn't seem so good to me. Queues are good.
> > You amortize or avoid all sorts of things with queues. We have them
> > everywhere in the kernel ;)
>
> Queues require maintenance which introduces variability because queue
> cleaning has to be done periodically and the queues grow in number if NUMA
> scenarios have to be handled effectively. This is a big problem for low
> latency applications (like in HPC). Spending far too much time optimizing
> queue cleaning in SLAB lead to the SLUB idea.

I'd like to see any real numbers showing this is a problem. Queue
trimming in SLQB can easily be scaled or tweaked to change latency
characteristics. The fact is that it isn't a very critical or highly
tuned operation. It happens _very_ infrequently in the large scheme
of things, and could easily be changed if there is a problem.

What you have in SLUB IMO is not obviously better because it effectively
has sizeable queues in higher order partial and free pages and the
active page, which simply never get trimmed, AFAIKS. This can be harmful
for slab internal fragmentation as well in some situations.

2009-01-15 06:19:43

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Wed, Jan 14, 2009 at 12:40:12PM -0600, Christoph Lameter wrote:
> On Wed, 14 Jan 2009, Nick Piggin wrote:
>
> > Well if you would like to consider SLQB as a fix for SLUB, that's
> > fine by me ;) Actually I guess it is a valid way to look at the problem:
> > SLQB solves the OLTP regression, so the only question is "what is the
> > downside of it?".
>
> The downside is that it brings the SLAB stuff back that SLUB was
> designed to avoid. Queue expiration.

What's this mean? Something distinct from periodic timer?

> The use of timers to expire at
> uncontrollable intervals for user space.

I am not convinced this is a problem. I would like to see evidence
that it is a problem, but I have only seen assertions.

Definitely it is not uncontrollable. And not unchangeable. It is
about the least sensitive part of the allocator because in a serious
workload, the queues will continually be bounded by watermarks rather
than timer reaping.

> Object dispersal
> in the kernel address space.

You mean due to lower order allocations?
1. I have not seen any results showing this gives a practical performance
increase, let alone one that offsets the downsides of using higher
order allocations.
2. Increased internal fragmentation may also have the opposite effect and
result in worse packing.
3. There is no reason why SLQB can't use higher order allocations if this
is a significant win.

> Memory policy handling in the slab
> allocator.

I see no reason why this should be a problem. The SLUB merge just asserted
it would be a problem. But actually SLAB seems to handle it just fine, and
SLUB also doesn't always obey memory policies, so I consider that to be a
worse problem, at least until it is justified by performance numbers that
show otherwise.

> Even seems to include periodic moving of objects between
> queues.

The queues expire slowly. Same as SLAB's arrays. You are describing the
implementation, and not the problems it has.

> The NUMA stuff is still a bit foggy to me since it seems to assume
> a mapping between cpus and nodes. There are cpuless nodes as well as
> memoryless cpus.

That needs a little bit of work, but my primary focus is to come up
with a design that has competitive performance in the most important
cases.

There needs to be some fallback cases added to slowpaths to handle
these things, but I don't see why it would take much work.

> SLQB maybe a good cleanup for SLAB. Its good that it is based on the
> cleaned up code in SLUB but the fundamental design is SLAB (or rather the
> Solaris allocator from which we got the design for all the queuing stuff
> in the first place). It preserves many of the drawbacks of that code.

It is _like_ slab. It avoids the major drawbacks of large footprint of
array caches, and O(N^2) memory consumption behaviour, and corner cases
where scalability is poor. The queueing behaviour of SLAB IMO is not
a drawback and it is a big reaon why SLAB is so good.

> If SLQB would replace SLAB then there would be a lot of shared code
> (debugging for example). Having a generic slab allocator framework may
> then be possible within which a variety of algorithms may be implemented.

The goal is to replace SLAB and SLUB. Anything less would be a failure
on behalf of SLQB. Shared code is not a bad thing, but the major problem
is the actual core behaviour of the allocator because it affects almost
everywhere in the kernel and splitting userbase is not a good thing.

2009-01-15 20:57:36

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Thu, 15 Jan 2009, Nick Piggin wrote:

> > The higher orders can fail and will then result in the allocator doing
> > order 0 allocs. It is not a failure condition.
>
> But they increase pressure on the resource and reduce availability to
> other higher order allocations. They accelerate the breakdown of the
> anti-frag heuristics, and they make slab internal fragmentation worse.
> They also simply cost more to allocate and free and reclaim.

The costs are less since there is no need to have metadata for each of
the 4k sized pages. Instead there is one contiguous chunk that can be
tracked as a whole.

> > Higher orders are an
> > advantage because they localize variables of the same type and therefore
> > reduce TLB pressure.
>
> They are also a disadvantage. The disadvantages are very real. The
> advantage is a bit theoretical (how much really is it going to help
> going from 4K to 32K, if you still have hundreds or thousands of
> slabs anyway?). Also, there is no reason why the other allocators
> cannot use higher orer allocations, but their big advantage is that
> they don't need to.

The benefit of going from 4k to 32k is that 8 times as many objects may be
handled by the same 2M TLB covering a 32k page. If the 4k pages are
dispersed then you may need 8 2M tlbs (which covers already a quarter of
the available 2M TLBs on nehalem f.e.) for which the larger alloc just
needs a single one.

> > > The idea of removing queues doesn't seem so good to me. Queues are good.
> > > You amortize or avoid all sorts of things with queues. We have them
> > > everywhere in the kernel ;)
> >
> > Queues require maintenance which introduces variability because queue
> > cleaning has to be done periodically and the queues grow in number if NUMA
> > scenarios have to be handled effectively. This is a big problem for low
> > latency applications (like in HPC). Spending far too much time optimizing
> > queue cleaning in SLAB lead to the SLUB idea.
>
> I'd like to see any real numbers showing this is a problem. Queue
> trimming in SLQB can easily be scaled or tweaked to change latency
> characteristics. The fact is that it isn't a very critical or highly
> tuned operation. It happens _very_ infrequently in the large scheme
> of things, and could easily be changed if there is a problem.

Queue trimming can be configured in the same way in SLAB. But this means
that you are forever tuning these things as loads vary. Thats one of the
frustrations that led to the SLUB design. Also if the objects in queues
are not bound to particular page (as in slub) then traversal of the queues
can be very TLB fault intensive.

> What you have in SLUB IMO is not obviously better because it effectively
> has sizeable queues in higher order partial and free pages and the
> active page, which simply never get trimmed, AFAIKS. This can be harmful
> for slab internal fragmentation as well in some situations.

It has lists of free objects that are bound to a particular page. That
simplifies numa handling since all the objects in a "queue" (or page) have
the same NUMA characteristics. There is no moving between queues
(there is one exception but in general that is true) because the page list can
become the percpu list by just using the pointer to the head object.

Slab internal fragmentation is already a problem in SLAB. The solution
would be a targeted reclaim mechanism. Something like what I proposed in
with the slab defrag patches.

There is no need for trimming since there is no queue in the SLAB sense. A
page is assigned to a processor and then that processor takes objects off
the freelist and may free objects back to the freelist of that page that
was assigned to a processor. Memory wastage may only occur because
each processor needs to have a separate page from which to allocate. SLAB
like designs needs to put a large number of objects in queues which may
keep a number of pages in the allocated pages pool although all objects
are unused. That does not occur with slub.

2009-01-15 21:06:39

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Thu, 15 Jan 2009, Nick Piggin wrote:

> Definitely it is not uncontrollable. And not unchangeable. It is
> about the least sensitive part of the allocator because in a serious
> workload, the queues will continually be bounded by watermarks rather
> than timer reaping.

The application that is interrupted has no control over when SLQB runs its
expiration. The longer the queues the longer the holdoff. Look at the
changelogs for various queue expiration things in the kernel. I fixed up a
couple of those over the years for latency reasons.

> > Object dispersal
> > in the kernel address space.
>
> You mean due to lower order allocations?
> 1. I have not seen any results showing this gives a practical performance
> increase, let alone one that offsets the downsides of using higher
> order allocations.

Well yes with enterprise app you are likely not going to see it. Run HPC
and other low latency tests (Infiniband based and such).

> 2. Increased internal fragmentation may also have the opposite effect and
> result in worse packing.

Memory allocations in latency critical appls are generally done in
contexts where high latencies are tolerable (f.e. at startup).

> 3. There is no reason why SLQB can't use higher order allocations if this
> is a significant win.

It still will have to move objects between queues? Or does it adapt the
slub method of "queue" per page?

> > Memory policy handling in the slab
> > allocator.
>
> I see no reason why this should be a problem. The SLUB merge just asserted
> it would be a problem. But actually SLAB seems to handle it just fine, and
> SLUB also doesn't always obey memory policies, so I consider that to be a
> worse problem, at least until it is justified by performance numbers that
> show otherwise.

Well I wrote the code in SLAB that does this. And AFAICT this was a very
bad hack that I had to put in after all the original developers of the
NUMA slab stuff vanished and things began to segfault.

SLUB obeys memory policies. It just uses the page allocator for this by
doing an allocation *without* specifying the node that memory has to come
from. SLAB manages memory strictly per node. So it always has to ask for
memory from a particular node. Hence the need to implement memory policies
in the allocator.

> > Even seems to include periodic moving of objects between
> > queues.
>
> The queues expire slowly. Same as SLAB's arrays. You are describing the
> implementation, and not the problems it has.

Periodic movement again introduces processing spikes and pollution of the
cpu caches.

> There needs to be some fallback cases added to slowpaths to handle
> these things, but I don't see why it would take much work.

The need for that fallback comes from the SLAB methodology used....

> > SLQB maybe a good cleanup for SLAB. Its good that it is based on the
> > cleaned up code in SLUB but the fundamental design is SLAB (or rather the
> > Solaris allocator from which we got the design for all the queuing stuff
> > in the first place). It preserves many of the drawbacks of that code.
>
> It is _like_ slab. It avoids the major drawbacks of large footprint of
> array caches, and O(N^2) memory consumption behaviour, and corner cases
> where scalability is poor. The queueing behaviour of SLAB IMO is not
> a drawback and it is a big reaon why SLAB is so good.

Queuing and the explosions of the number of queues with the alien caches
resulted in the potential of portions of memory vanishing into these
queues. Queueing means unused objects are in those queues stemming from
pages that would otherwise (if the the free object would be "moved" back
to the page) be available for other kernel uses.

> > If SLQB would replace SLAB then there would be a lot of shared code
> > (debugging for example). Having a generic slab allocator framework may
> > then be possible within which a variety of algorithms may be implemented.
>
> The goal is to replace SLAB and SLUB. Anything less would be a failure
> on behalf of SLQB. Shared code is not a bad thing, but the major problem
> is the actual core behaviour of the allocator because it affects almost
> everywhere in the kernel and splitting userbase is not a good thing.

I still dont see the problem that SLQB is addressing (aside from code
cleanup of SLAB). Seems that you feel that the queueing behavior of SLAB
is okay.

2009-01-16 03:19:55

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Thu, Jan 15, 2009 at 02:05:55PM -0600, Christoph Lameter wrote:
> On Thu, 15 Jan 2009, Nick Piggin wrote:
>
> > > The higher orders can fail and will then result in the allocator doing
> > > order 0 allocs. It is not a failure condition.
> >
> > But they increase pressure on the resource and reduce availability to
> > other higher order allocations. They accelerate the breakdown of the
> > anti-frag heuristics, and they make slab internal fragmentation worse.
> > They also simply cost more to allocate and free and reclaim.
>
> The costs are less since there is no need to have metadata for each of
> the 4k sized pages. Instead there is one contiguous chunk that can be
> tracked as a whole.

In terms of memory footprint of metadata, SLQB and SLUB both use the
struct page for this, so no advantage. In terms of performance, well
it seems that SLUB is not faster with higher order allocations, but
slower with order-0 allocations. So this seems to just be an argument
for using higher order allocations in SLUB, rather than an argument
against using order-0 in SLQB or SLAB>

> > > Higher orders are an
> > > advantage because they localize variables of the same type and therefore
> > > reduce TLB pressure.
> >
> > They are also a disadvantage. The disadvantages are very real. The
> > advantage is a bit theoretical (how much really is it going to help
> > going from 4K to 32K, if you still have hundreds or thousands of
> > slabs anyway?). Also, there is no reason why the other allocators
> > cannot use higher orer allocations, but their big advantage is that
> > they don't need to.
>
> The benefit of going from 4k to 32k is that 8 times as many objects may be
> handled by the same 2M TLB covering a 32k page. If the 4k pages are
> dispersed then you may need 8 2M tlbs (which covers already a quarter of
> the available 2M TLBs on nehalem f.e.) for which the larger alloc just
> needs a single one.

Yes I know that. But it's pretty theoretical IMO (and I could equally
describe a theoretical situation where increased fragmentation in higher
order slabs will result in worse TLB coverage).

Has there been a demonstrated advantage of this? That outweighs the
costs of using higher order allocs? If so, then I could just add some
parameters to SLQB to allow higher order allocs as well.

> > I'd like to see any real numbers showing this is a problem. Queue
> > trimming in SLQB can easily be scaled or tweaked to change latency
> > characteristics. The fact is that it isn't a very critical or highly
> > tuned operation. It happens _very_ infrequently in the large scheme
> > of things, and could easily be changed if there is a problem.
>
> Queue trimming can be configured in the same way in SLAB. But this means
> that you are forever tuning these things as loads vary. Thats one of the

As I said, this is not my experience. Queue trimming is a third order
problem and barely makes any difference in a running workload. It just
serves to clean up unused memory when slabs stop being used. There is
basically no performance implication to it (watermarks are far more
important to queue management of a busy slab).

Tens of millions of objects can be allocated and freed between queue
trimming intervals.

> frustrations that led to the SLUB design. Also if the objects in queues
> are not bound to particular page (as in slub) then traversal of the queues
> can be very TLB fault intensive.

Yeah but it happens so infrequently it should be in the noise. I have
never seen any real problems caused by this. Have you?

> > What you have in SLUB IMO is not obviously better because it effectively
> > has sizeable queues in higher order partial and free pages and the
> > active page, which simply never get trimmed, AFAIKS. This can be harmful
> > for slab internal fragmentation as well in some situations.
>
> It has lists of free objects that are bound to a particular page. That
> simplifies numa handling since all the objects in a "queue" (or page) have
> the same NUMA characteristics.

The same can be said of SLQB and SLAB as well.

> There is no moving between queues
> (there is one exception but in general that is true) because the page list can
> become the percpu list by just using the pointer to the head object.

Exactly the same way SLQB can move a queue of remotely freed objects back
to the allocating processor. It just manipulates a head pointer. It doesn't
walk every object in the list.

> Slab internal fragmentation is already a problem in SLAB. The solution
> would be a targeted reclaim mechanism. Something like what I proposed in
> with the slab defrag patches.

It is still a much bigger problem with 16x larger pages. If you have targetted
reclaim and 32K slabs, then you will still have a bigger problem than
targetted reclaim and 4K slabs (and the targetted reclaim will be less
efficient because it will have to free more objects).

> There is no need for trimming since there is no queue in the SLAB sense. A
> page is assigned to a processor and then that processor takes objects off
> the freelist and may free objects back to the freelist of that page that
> was assigned to a processor. Memory wastage may only occur because
> each processor needs to have a separate page from which to allocate. SLAB
> like designs needs to put a large number of objects in queues which may
> keep a number of pages in the allocated pages pool although all objects
> are unused. That does not occur with slub.

That's wrong. SLUB keeps completely free pages on its partial lists, and
also IIRC can keep free pages pinned in the per-cpu page. I have actually
seen SLQB use less memory than SLUB in some situations for this reason.

2009-01-16 03:44:18

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Thu, Jan 15, 2009 at 02:47:02PM -0600, Christoph Lameter wrote:
> On Thu, 15 Jan 2009, Nick Piggin wrote:
>
> > Definitely it is not uncontrollable. And not unchangeable. It is
> > about the least sensitive part of the allocator because in a serious
> > workload, the queues will continually be bounded by watermarks rather
> > than timer reaping.
>
> The application that is interrupted has no control over when SLQB runs its
> expiration. The longer the queues the longer the holdoff. Look at the
> changelogs for various queue expiration things in the kernel. I fixed up a
> couple of those over the years for latency reasons.

Interrupts and timers etc. as well as preemption by kernel threads happen
everywhere in the kernel. I have not seen any reason why slab queue reaping
in particular is a problem.

Any slab allocator is going to have a whole lot of theoretical problems and
you simply won't be able to fix them all because some require an oracle or
others fundamentally conflict with another theoretical problem.

I concentrate on the main practical problems and the end result. If I see
evidence of some problem caused, then I will do my best to fix it.

> > > Object dispersal
> > > in the kernel address space.
> >
> > You mean due to lower order allocations?
> > 1. I have not seen any results showing this gives a practical performance
> > increase, let alone one that offsets the downsides of using higher
> > order allocations.
>
> Well yes with enterprise app you are likely not going to see it. Run HPC
> and other low latency tests (Infiniband based and such).

So do you have any results or not?

> > 2. Increased internal fragmentation may also have the opposite effect and
> > result in worse packing.
>
> Memory allocations in latency critical appls are generally done in
> contexts where high latencies are tolerable (f.e. at startup).
>
> > 3. There is no reason why SLQB can't use higher order allocations if this
> > is a significant win.
>
> It still will have to move objects between queues? Or does it adapt the
> slub method of "queue" per page?

It has several queues that objects can move between. You keep asserting
that this is a problem.

> > > Memory policy handling in the slab
> > > allocator.
> >
> > I see no reason why this should be a problem. The SLUB merge just asserted
> > it would be a problem. But actually SLAB seems to handle it just fine, and
> > SLUB also doesn't always obey memory policies, so I consider that to be a
> > worse problem, at least until it is justified by performance numbers that
> > show otherwise.
>
> Well I wrote the code in SLAB that does this. And AFAICT this was a very
> bad hack that I had to put in after all the original developers of the
> NUMA slab stuff vanished and things began to segfault.
>
> SLUB obeys memory policies. It just uses the page allocator for this by
> doing an allocation *without* specifying the node that memory has to come
> from. SLAB manages memory strictly per node. So it always has to ask for
> memory from a particular node. Hence the need to implement memory policies
> in the allocator.

You only go to the allocator when the percpu queue goes empty though, so
if memory policy changes (eg context switch or something), then subsequent
allocations will be of the wrong policy.

That is what I call a hack, which is made in order to solve a percieved
performance problem. The SLAB/SLQB method of checking policy is simple,
obviously correct, and until there is a *demonstrated* performance problem
with that, then I'm not going to change it.

> > > Even seems to include periodic moving of objects between
> > > queues.
> >
> > The queues expire slowly. Same as SLAB's arrays. You are describing the
> > implementation, and not the problems it has.
>
> Periodic movement again introduces processing spikes and pollution of the
> cpu caches.

I don't think this is a problem. Anyway, rt systems that care about such
tiny latencies can easily prioritise this. And ones that don't care so
much have many other sources of interrupts and background processing by
the kernel or hardware interrupts.

If this actually *is* a problem, I will allow an option to turn of periodic
trimming of queues, and allow objects to remain in queues (like the page
allocator does with its queues). And just provide hooks to reap them at
low memory time.

> > There needs to be some fallback cases added to slowpaths to handle
> > these things, but I don't see why it would take much work.
>
> The need for that fallback comes from the SLAB methodology used....

The fallback will probably be adapted from SLUB.

> > > SLQB maybe a good cleanup for SLAB. Its good that it is based on the
> > > cleaned up code in SLUB but the fundamental design is SLAB (or rather the
> > > Solaris allocator from which we got the design for all the queuing stuff
> > > in the first place). It preserves many of the drawbacks of that code.
> >
> > It is _like_ slab. It avoids the major drawbacks of large footprint of
> > array caches, and O(N^2) memory consumption behaviour, and corner cases
> > where scalability is poor. The queueing behaviour of SLAB IMO is not
> > a drawback and it is a big reaon why SLAB is so good.
>
> Queuing and the explosions of the number of queues with the alien caches
> resulted in the potential of portions of memory vanishing into these
> queues. Queueing means unused objects are in those queues stemming from
> pages that would otherwise (if the the free object would be "moved" back
> to the page) be available for other kernel uses.

It's strange. You percieve these theoretical problems with things that I
actually consider is a distinct *advantage* of SLAB/SLQB. order-0 allocations,
queueing, strictly obeying NUMA policies...

> > > If SLQB would replace SLAB then there would be a lot of shared code
> > > (debugging for example). Having a generic slab allocator framework may
> > > then be possible within which a variety of algorithms may be implemented.
> >
> > The goal is to replace SLAB and SLUB. Anything less would be a failure
> > on behalf of SLQB. Shared code is not a bad thing, but the major problem
> > is the actual core behaviour of the allocator because it affects almost
> > everywhere in the kernel and splitting userbase is not a good thing.
>
> I still dont see the problem that SLQB is addressing (aside from code
> cleanup of SLAB). Seems that you feel that the queueing behavior of SLAB
> is okay.

It addresses O(NR_CPUS^2) memory consumption of kmem caches, and large
constant consumption of array caches of SLAB. It addresses scalability
eg in situations with lots of cores per node. It allows resizeable
queues. It addresses the code complexity and bootstap hoops of SLAB.

It addresses performance and higher order allocation problems of SLUB.

2009-01-16 21:08:51

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Fri, 16 Jan 2009, Nick Piggin wrote:

> > handled by the same 2M TLB covering a 32k page. If the 4k pages are
> > dispersed then you may need 8 2M tlbs (which covers already a quarter of
> > the available 2M TLBs on nehalem f.e.) for which the larger alloc just
> > needs a single one.
>
> Yes I know that. But it's pretty theoretical IMO (and I could equally
> describe a theoretical situation where increased fragmentation in higher
> order slabs will result in worse TLB coverage).

Theoretical only for low sizes of memory. If you have terabytes of memory
then this becomes significant in a pretty fast way.

> > It has lists of free objects that are bound to a particular page. That
> > simplifies numa handling since all the objects in a "queue" (or page) have
> > the same NUMA characteristics.
>
> The same can be said of SLQB and SLAB as well.

Sorry not at all. SLAB and SLQB queue objects from different pages in the
same queue.

> > was assigned to a processor. Memory wastage may only occur because
> > each processor needs to have a separate page from which to allocate. SLAB
> > like designs needs to put a large number of objects in queues which may
> > keep a number of pages in the allocated pages pool although all objects
> > are unused. That does not occur with slub.
>
> That's wrong. SLUB keeps completely free pages on its partial lists, and
> also IIRC can keep free pages pinned in the per-cpu page. I have actually
> seen SLQB use less memory than SLUB in some situations for this reason.

As I sad it pins a single page in the per cpu page and uses that in a way
that you call a queue and I call a freelist.

SLUB keeps a few pages on the partial list right now because it tries to
avoid trips to the page allocator (which is quite slow). These could be
eliminated if the page allocator would work effectively. However that
number is a per node limit.

SLAB and SLUB can have large quantities of objects in their queues that
each can keep a single page out of circulation if its the last
object in that page. This is per queue thing and you have at least two
queues per cpu. SLAB has queues per cpu, per pair of cpu, per node and per
alien node for each node. That can pin quite a number of pages on large
systems. Note that SLAB has one per cpu whereas you have already 2 per
cpu? In SMP configurations this may mean that SLQB has more queues than
SLAB.

2009-01-16 21:26:16

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Fri, 16 Jan 2009, Nick Piggin wrote:

> > The application that is interrupted has no control over when SLQB runs its
> > expiration. The longer the queues the longer the holdoff. Look at the
> > changelogs for various queue expiration things in the kernel. I fixed up a
> > couple of those over the years for latency reasons.
>
> Interrupts and timers etc. as well as preemption by kernel threads happen
> everywhere in the kernel. I have not seen any reason why slab queue reaping
> in particular is a problem.

The slab queues are a particular problem since they are combined with
timers. So the latency insensitive phase of an HPC app completes and then
the latency critical part starts to run. SLAB will happily every 2 seconds
expire a certain amount of objects from all its various queues.

> Any slab allocator is going to have a whole lot of theoretical problems and
> you simply won't be able to fix them all because some require an oracle or
> others fundamentally conflict with another theoretical problem.

I agree there is no point in working on theoretical problems. We are
talking about practical problems.

> I concentrate on the main practical problems and the end result. If I see
> evidence of some problem caused, then I will do my best to fix it.

You concentrate on the problems that are given to you I guess...

> > Well yes with enterprise app you are likely not going to see it. Run HPC
> > and other low latency tests (Infiniband based and such).
>
> So do you have any results or not?

Of course. I need to repost them? I am no longer employed by the company I
did the work for. So the test data is no longer accessible to me. You have
to rely on the material that was posted in the past.

> > It still will have to move objects between queues? Or does it adapt the
> > slub method of "queue" per page?
>
> It has several queues that objects can move between. You keep asserting
> that this is a problem.

> > SLUB obeys memory policies. It just uses the page allocator for this by
> > doing an allocation *without* specifying the node that memory has to come
> > from. SLAB manages memory strictly per node. So it always has to ask for
> > memory from a particular node. Hence the need to implement memory policies
> > in the allocator.
>
> You only go to the allocator when the percpu queue goes empty though, so
> if memory policy changes (eg context switch or something), then subsequent
> allocations will be of the wrong policy.

The per cpu queue size in SLUB is limited by the queues only containing
objects from the same page. If you have large queues like SLAB/SLQB(?)
then this could be an issue.

> That is what I call a hack, which is made in order to solve a percieved
> performance problem. The SLAB/SLQB method of checking policy is simple,
> obviously correct, and until there is a *demonstrated* performance problem
> with that, then I'm not going to change it.

Well so far it seems that your tests never even exercise that part of the
allocators.

> I don't think this is a problem. Anyway, rt systems that care about such
> tiny latencies can easily prioritise this. And ones that don't care so
> much have many other sources of interrupts and background processing by
> the kernel or hardware interrupts.

How do they prioritize this?

> If this actually *is* a problem, I will allow an option to turn of periodic
> trimming of queues, and allow objects to remain in queues (like the page
> allocator does with its queues). And just provide hooks to reap them at
> low memory time.

That means large amounts of memory are going to be caught in these queues.
If its per cpu and one cpu does allocation and the other frees then the
first cpu will consume more and more memory from the page allocator
whereas the second will build up huge per cpu lists.

> It's strange. You percieve these theoretical problems with things that I
> actually consider is a distinct *advantage* of SLAB/SLQB. order-0 allocations,
> queueing, strictly obeying NUMA policies...

These are issues that we encountered in practice with large systems.
Pointer chasing performance on many apps is bounded by TLB faults etc.
Strictly obeying NUMA policies causes performance problems in SLAB. Try
MPOL_INTERLEAVE vs a cpu local allocations.

> > I still dont see the problem that SLQB is addressing (aside from code
> > cleanup of SLAB). Seems that you feel that the queueing behavior of SLAB
> > is okay.
>
> It addresses O(NR_CPUS^2) memory consumption of kmem caches, and large
> constant consumption of array caches of SLAB. It addresses scalability
> eg in situations with lots of cores per node. It allows resizeable
> queues. It addresses the code complexity and bootstap hoops of SLAB.
>
> It addresses performance and higher order allocation problems of SLUB.

It seems that on SMP systems SLQB will actually increase the number of
queues since it needs 2 queues per cpu instead of the 1 of SLAB. SLAB also
has resizable queues. Code simplification and bootstrap: Great work on
that. Again good cleanup of SLAB.

2009-01-19 05:47:43

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Fri, Jan 16, 2009 at 03:07:52PM -0600, Christoph Lameter wrote:
> On Fri, 16 Jan 2009, Nick Piggin wrote:
>
> > > handled by the same 2M TLB covering a 32k page. If the 4k pages are
> > > dispersed then you may need 8 2M tlbs (which covers already a quarter of
> > > the available 2M TLBs on nehalem f.e.) for which the larger alloc just
> > > needs a single one.
> >
> > Yes I know that. But it's pretty theoretical IMO (and I could equally
> > describe a theoretical situation where increased fragmentation in higher
> > order slabs will result in worse TLB coverage).
>
> Theoretical only for low sizes of memory. If you have terabytes of memory
> then this becomes significant in a pretty fast way.

I don't really buy that as a general statement with no other qualifiers.
If the huge system has a correspondingly increased number of slab
objects, then the potential win is much smaller as system sizes increases.
Say if you have a 1GB RAM system, with 128 2MB TLBs, and suppose you have
a slab that takes 25% of the RAM. Then if you optimally pack the slab for
TLB access of those objects in a random pattern, then you can get 100%
TLB hit for a given random access. And 25% in the case of random allocations.

In a 1TB RAM system, you have ~0.1% chance of TLB hit in the optimally packed
case and ~0.025% chance of hit in the random case. So in that case it is a
much smaller (negligable) possible gain from packing.

And note that we're talking about best possible packing scenario (ie. 2MB
pages vs 4K pages). The standard SLUB tune would not get anywhere near that.

The thing IMO you forget with all these doomsday scenarios about SGI's peta
scale systems is that no matter what you do, you can't avoid the fact that
computing is about locality. Even if you totally take the TLB out of the
equation, you still have the small detail of other caches. Code that jumps
all over that 1024 TB of memory with no locality is going to suck regardless
of what the kernel ever does, due to physical limitations of hardware.

Anyway, this is trivial for SLQB to tune this on those systems that really
care, giving SLUB no advantage. So we needn't really get sidetracked with
this in the context of SLQB.

> > > It has lists of free objects that are bound to a particular page. That
> > > simplifies numa handling since all the objects in a "queue" (or page) have
> > > the same NUMA characteristics.
> >
> > The same can be said of SLQB and SLAB as well.
>
> Sorry not at all. SLAB and SLQB queue objects from different pages in the
> same queue.

The last sentence is what I was replying to. Ie. "simplification of
numa handling" does not follow from the SLUB implementation of per-page
freelists.

> > > was assigned to a processor. Memory wastage may only occur because
> > > each processor needs to have a separate page from which to allocate. SLAB
> > > like designs needs to put a large number of objects in queues which may
> > > keep a number of pages in the allocated pages pool although all objects
> > > are unused. That does not occur with slub.
> >
> > That's wrong. SLUB keeps completely free pages on its partial lists, and
> > also IIRC can keep free pages pinned in the per-cpu page. I have actually
> > seen SLQB use less memory than SLUB in some situations for this reason.
>
> As I sad it pins a single page in the per cpu page and uses that in a way
> that you call a queue and I call a freelist.

And you found you have to increase the size of your pages because you
need bigger queues. (must we argue semantics? it is a list of free
objects)

> SLUB keeps a few pages on the partial list right now because it tries to
> avoid trips to the page allocator (which is quite slow). These could be
> eliminated if the page allocator would work effectively. However that
> number is a per node limit.

This is the practical vs theoretical I'm talking about.

> SLAB and SLUB can have large quantities of objects in their queues that
> each can keep a single page out of circulation if its the last
> object in that page. This is per queue thing and you have at least two

And if that were a problem, SLQB can easily be runtime tuned to keep no
objects in its object lists. But as I said, queueing is good, so why
would anybody want to get rid of it?

> queues per cpu. SLAB has queues per cpu, per pair of cpu, per node and per
> alien node for each node. That can pin quite a number of pages on large
> systems. Note that SLAB has one per cpu whereas you have already 2 per
> cpu? In SMP configurations this may mean that SLQB has more queues than
> SLAB.

Again, this doesn't really go anywhere while we disagree on the
fundamental goodliness of queueing. This is just describing the
implementation.

2009-01-19 06:19:18

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Fri, Jan 16, 2009 at 03:25:05PM -0600, Christoph Lameter wrote:
> On Fri, 16 Jan 2009, Nick Piggin wrote:
>
> > > The application that is interrupted has no control over when SLQB runs its
> > > expiration. The longer the queues the longer the holdoff. Look at the
> > > changelogs for various queue expiration things in the kernel. I fixed up a
> > > couple of those over the years for latency reasons.
> >
> > Interrupts and timers etc. as well as preemption by kernel threads happen
> > everywhere in the kernel. I have not seen any reason why slab queue reaping
> > in particular is a problem.
>
> The slab queues are a particular problem since they are combined with
> timers. So the latency insensitive phase of an HPC app completes and then
> the latency critical part starts to run. SLAB will happily every 2 seconds
> expire a certain amount of objects from all its various queues.

Didn't you just earlier say that HPC apps will do all their memory
allocations up front before the critical part of the run? Anyway,
I have not seen any particular problem of cache reaping every 2 seconds
that would be worse than hardware interrupts or other timers.

But as I said, if I do see evidence of that, I will tweak the queue
reaping. But I prefer to keep it simple and closer to SLAB behaviour
until that time.

> > Any slab allocator is going to have a whole lot of theoretical problems and
> > you simply won't be able to fix them all because some require an oracle or
> > others fundamentally conflict with another theoretical problem.
>
> I agree there is no point in working on theoretical problems. We are
> talking about practical problems.

You are not saying what the practical problem is, though. Ie. what
exactly is the workload where cache reaping is causing a problem and
what are the results of eliminating that reaping?

> > I concentrate on the main practical problems and the end result. If I see
> > evidence of some problem caused, then I will do my best to fix it.
>
> You concentrate on the problems that are given to you I guess...

Of course. That would include any problems SGI or you would give me, I would
try to fix them. But I not only concentrate on those, but also ones that
I seek out myself. Eg. the OLTP problem.

> > > Well yes with enterprise app you are likely not going to see it. Run HPC
> > > and other low latency tests (Infiniband based and such).
> >
> > So do you have any results or not?
>
> Of course. I need to repost them? I am no longer employed by the company I
> did the work for. So the test data is no longer accessible to me. You have
> to rely on the material that was posted in the past.

Just links are fine. I could find nothing concrete in the mm/slqb.c
changelogs.

> > > It still will have to move objects between queues? Or does it adapt the
> > > slub method of "queue" per page?
> >
> > It has several queues that objects can move between. You keep asserting
> > that this is a problem.
>
> > > SLUB obeys memory policies. It just uses the page allocator for this by
> > > doing an allocation *without* specifying the node that memory has to come
> > > from. SLAB manages memory strictly per node. So it always has to ask for
> > > memory from a particular node. Hence the need to implement memory policies
> > > in the allocator.
> >
> > You only go to the allocator when the percpu queue goes empty though, so
> > if memory policy changes (eg context switch or something), then subsequent
> > allocations will be of the wrong policy.
>
> The per cpu queue size in SLUB is limited by the queues only containing
> objects from the same page. If you have large queues like SLAB/SLQB(?)
> then this could be an issue.

And it could be a problem in SLUB too. Chances are that several allocations
will be wrong after every policy switch. I could describe situations in which
SLUB will allocate with the _wrong_ policy literally 100% of the time.

> > That is what I call a hack, which is made in order to solve a percieved
> > performance problem. The SLAB/SLQB method of checking policy is simple,
> > obviously correct, and until there is a *demonstrated* performance problem
> > with that, then I'm not going to change it.
>
> Well so far it seems that your tests never even exercise that part of the
> allocators.

It uses code and behaviour from SLAB, which I know that has been
extensively tested in enterprise distros and on just about every
serious production NUMA installation and every hardware vendor
including SGI.

That will satisfy me until somebody reports a problem. Again, I could
only find handwaving in the SLUB changelog, which I definitely have
looked at because I want to find and solve as many issues in this
subsystem as I can.

> > I don't think this is a problem. Anyway, rt systems that care about such
> > tiny latencies can easily prioritise this. And ones that don't care so
> > much have many other sources of interrupts and background processing by
> > the kernel or hardware interrupts.
>
> How do they prioritize this?

In -rt, by prioritising interrupts. As I said, in the mainline kernel
I am skeptical that this is a problem. If it was a problem, I have
never seen a report, or an obvious simple improvmeent of moving the
reaping into a workqueue which can be prioritised, like was done with
the multi-cpu scheduler when there were problems iwth it.

> > If this actually *is* a problem, I will allow an option to turn of periodic
> > trimming of queues, and allow objects to remain in queues (like the page
> > allocator does with its queues). And just provide hooks to reap them at
> > low memory time.
>
> That means large amounts of memory are going to be caught in these queues.
> If its per cpu and one cpu does allocation and the other frees then the
> first cpu will consume more and more memory from the page allocator
> whereas the second will build up huge per cpu lists.

Wrong. I said I would allow an option to turn off *periodic trimming*.
Or just modify the existing tunables or look at making the trimming
more fine grained etc etc. I won't know until I see a workload where it
hurts, and I will try to solve it then.

> > It's strange. You percieve these theoretical problems with things that I
> > actually consider is a distinct *advantage* of SLAB/SLQB. order-0 allocations,
> > queueing, strictly obeying NUMA policies...
>
> These are issues that we encountered in practice with large systems.
> Pointer chasing performance on many apps is bounded by TLB faults etc.

I would be surprised if SLUB somehow fixed such apps. Especially on
large systems, if you look at the maths.

But I don't dismiss the possibility, and SLQB as I keep repeating,
can do higher order allocations. The reason I bring it up is
because SLUB will get significantly slower for many workloads if
higher order allocations *are not* done. Which is the advantage of
SLAB and SLQB here. This cannot be turned into an advantage for
SLUB because of this TLB issue.

> Strictly obeying NUMA policies causes performance problems in SLAB. Try
> MPOL_INTERLEAVE vs a cpu local allocations.

I will try testing that. Note that I have of course been testing
NUMA things on our small Altix, but I just haven't found anything
interesting enough to post...

> > > I still dont see the problem that SLQB is addressing (aside from code
> > > cleanup of SLAB). Seems that you feel that the queueing behavior of SLAB
> > > is okay.
> >
> > It addresses O(NR_CPUS^2) memory consumption of kmem caches, and large
> > constant consumption of array caches of SLAB. It addresses scalability
> > eg in situations with lots of cores per node. It allows resizeable
> > queues. It addresses the code complexity and bootstap hoops of SLAB.
> >
> > It addresses performance and higher order allocation problems of SLUB.
>
> It seems that on SMP systems SLQB will actually increase the number of
> queues since it needs 2 queues per cpu instead of the 1 of SLAB.

I don't know what you mean when you say queues, but SLQB has more
than 2 queues per CPU. Great. I like them ;)

> SLAB also
> has resizable queues.

Not significantly because that would require large memory allocations for
large queues. And there is no code there to do runtime resizing.

> Code simplification and bootstrap: Great work on
> that. Again good cleanup of SLAB.

2009-01-22 00:31:35

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Mon, 19 Jan 2009, Nick Piggin wrote:

> > > You only go to the allocator when the percpu queue goes empty though, so
> > > if memory policy changes (eg context switch or something), then subsequent
> > > allocations will be of the wrong policy.
> >
> > The per cpu queue size in SLUB is limited by the queues only containing
> > objects from the same page. If you have large queues like SLAB/SLQB(?)
> > then this could be an issue.
>
> And it could be a problem in SLUB too. Chances are that several allocations
> will be wrong after every policy switch. I could describe situations in which
> SLUB will allocate with the _wrong_ policy literally 100% of the time.

No it cannot because in SLUB objects must come from the same page.
Multiple objects in a queue will only ever require a single page and not
multiple like in SLAB.

> > That means large amounts of memory are going to be caught in these queues.
> > If its per cpu and one cpu does allocation and the other frees then the
> > first cpu will consume more and more memory from the page allocator
> > whereas the second will build up huge per cpu lists.
>
> Wrong. I said I would allow an option to turn off *periodic trimming*.
> Or just modify the existing tunables or look at making the trimming
> more fine grained etc etc. I won't know until I see a workload where it
> hurts, and I will try to solve it then.

You are not responding to the issue. If you have queues that contain
objects from multiple pages then every object pointer in these queues can
pin a page although this actually is a free object.

> > It seems that on SMP systems SLQB will actually increase the number of
> > queues since it needs 2 queues per cpu instead of the 1 of SLAB.
>
> I don't know what you mean when you say queues, but SLQB has more
> than 2 queues per CPU. Great. I like them ;)

This gets better and better.

> > SLAB also
> > has resizable queues.
>
> Not significantly because that would require large memory allocations for
> large queues. And there is no code there to do runtime resizing.

Groan. Please have a look at do_tune_cpucache() in slab.c

2009-01-22 00:33:23

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Mon, 19 Jan 2009, Nick Piggin wrote:

> The thing IMO you forget with all these doomsday scenarios about SGI's peta
> scale systems is that no matter what you do, you can't avoid the fact that
> computing is about locality. Even if you totally take the TLB out of the
> equation, you still have the small detail of other caches. Code that jumps
> all over that 1024 TB of memory with no locality is going to suck regardless
> of what the kernel ever does, due to physical limitations of hardware.

Typically we traverse lists of objects that are in the same slab cache.

> > Sorry not at all. SLAB and SLQB queue objects from different pages in the
> > same queue.
>
> The last sentence is what I was replying to. Ie. "simplification of
> numa handling" does not follow from the SLUB implementation of per-page
> freelists.

If all objects are from the same page then you need not check
the NUMA locality of any object on that queue.

> > As I sad it pins a single page in the per cpu page and uses that in a way
> > that you call a queue and I call a freelist.
>
> And you found you have to increase the size of your pages because you
> need bigger queues. (must we argue semantics? it is a list of free
> objects)

Right. That may be the case and its a similar tuning to what SLAB does.

> > SLAB and SLUB can have large quantities of objects in their queues that
> > each can keep a single page out of circulation if its the last
> > object in that page. This is per queue thing and you have at least two
>
> And if that were a problem, SLQB can easily be runtime tuned to keep no
> objects in its object lists. But as I said, queueing is good, so why
> would anybody want to get rid of it?

Queing is sometimes good....

> Again, this doesn't really go anywhere while we disagree on the
> fundamental goodliness of queueing. This is just describing the
> implementation.

I am not sure that you understand the fine points of queuing in slub. I am
not a fundamentalist: Queues are good if used the right way and as you say
SLUB has "queues" designed in a particular fashion that solves issus that
we had with SLAB queues.

2009-01-22 09:27:22

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

Hi Christoph,

On Mon, 19 Jan 2009, Nick Piggin wrote:
> > > > You only go to the allocator when the percpu queue goes empty though, so
> > > > if memory policy changes (eg context switch or something), then subsequent
> > > > allocations will be of the wrong policy.
> > >
> > > The per cpu queue size in SLUB is limited by the queues only containing
> > > objects from the same page. If you have large queues like SLAB/SLQB(?)
> > > then this could be an issue.
> >
> > And it could be a problem in SLUB too. Chances are that several allocations
> > will be wrong after every policy switch. I could describe situations in which
> > SLUB will allocate with the _wrong_ policy literally 100% of the time.

On Wed, 2009-01-21 at 19:13 -0500, Christoph Lameter wrote:
> No it cannot because in SLUB objects must come from the same page.
> Multiple objects in a queue will only ever require a single page and not
> multiple like in SLAB.

There's one potential problem with "per-page queues", though. The bigger
the object, the smaller the "queue" (i.e. less objects per page). Also,
partial lists are less likely to help for big objects because they get
emptied so quickly and returned to the page allocator. Perhaps we should
do a small "full list" for caches with large objects?

Pekka

2009-01-22 09:30:58

by Yanmin Zhang

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Thu, 2009-01-22 at 11:27 +0200, Pekka Enberg wrote:
> Hi Christoph,
>
> On Mon, 19 Jan 2009, Nick Piggin wrote:
> > > > > You only go to the allocator when the percpu queue goes empty though, so
> > > > > if memory policy changes (eg context switch or something), then subsequent
> > > > > allocations will be of the wrong policy.
> > > >
> > > > The per cpu queue size in SLUB is limited by the queues only containing
> > > > objects from the same page. If you have large queues like SLAB/SLQB(?)
> > > > then this could be an issue.
> > >
> > > And it could be a problem in SLUB too. Chances are that several allocations
> > > will be wrong after every policy switch. I could describe situations in which
> > > SLUB will allocate with the _wrong_ policy literally 100% of the time.
>
> On Wed, 2009-01-21 at 19:13 -0500, Christoph Lameter wrote:
> > No it cannot because in SLUB objects must come from the same page.
> > Multiple objects in a queue will only ever require a single page and not
> > multiple like in SLAB.
>
> There's one potential problem with "per-page queues", though. The bigger
> the object, the smaller the "queue" (i.e. less objects per page). Also,
> partial lists are less likely to help for big objects because they get
> emptied so quickly and returned to the page allocator. Perhaps we should
> do a small "full list" for caches with large objects?
That helps definitely. We could use a batch to control the list size.

2009-01-22 09:33:23

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Thu, 2009-01-22 at 17:30 +0800, Zhang, Yanmin wrote:
> On Thu, 2009-01-22 at 11:27 +0200, Pekka Enberg wrote:
> > Hi Christoph,
> >
> > On Mon, 19 Jan 2009, Nick Piggin wrote:
> > > > > > You only go to the allocator when the percpu queue goes empty though, so
> > > > > > if memory policy changes (eg context switch or something), then subsequent
> > > > > > allocations will be of the wrong policy.
> > > > >
> > > > > The per cpu queue size in SLUB is limited by the queues only containing
> > > > > objects from the same page. If you have large queues like SLAB/SLQB(?)
> > > > > then this could be an issue.
> > > >
> > > > And it could be a problem in SLUB too. Chances are that several allocations
> > > > will be wrong after every policy switch. I could describe situations in which
> > > > SLUB will allocate with the _wrong_ policy literally 100% of the time.
> >
> > On Wed, 2009-01-21 at 19:13 -0500, Christoph Lameter wrote:
> > > No it cannot because in SLUB objects must come from the same page.
> > > Multiple objects in a queue will only ever require a single page and not
> > > multiple like in SLAB.
> >
> > There's one potential problem with "per-page queues", though. The bigger
> > the object, the smaller the "queue" (i.e. less objects per page). Also,
> > partial lists are less likely to help for big objects because they get
> > emptied so quickly and returned to the page allocator. Perhaps we should
> > do a small "full list" for caches with large objects?
> That helps definitely. We could use a batch to control the list size.

s/full list/empty list/g

That is, a list of pages that could be returned to the page allocator
but are pooled in SLUB to avoid the page allocator overhead. Note that
this will not help allocators that trigger page allocator pass-through.

Pekka

2009-01-23 04:09:24

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Wed, Jan 21, 2009 at 07:13:44PM -0500, Christoph Lameter wrote:
> On Mon, 19 Jan 2009, Nick Piggin wrote:
>
> > > The per cpu queue size in SLUB is limited by the queues only containing
> > > objects from the same page. If you have large queues like SLAB/SLQB(?)
> > > then this could be an issue.
> >
> > And it could be a problem in SLUB too. Chances are that several allocations
> > will be wrong after every policy switch. I could describe situations in which
> > SLUB will allocate with the _wrong_ policy literally 100% of the time.
>
> No it cannot because in SLUB objects must come from the same page.
> Multiple objects in a queue will only ever require a single page and not
> multiple like in SLAB.

I don't know how that solves the problem. Task with memory policy A
allocates an object, which allocates the "fast" page with policy A
and allocates an object. Then context switch to task with memory
policy B which allocates another object, which is taken from the page
allocated with policy A. Right?

(OK this doesn't give the wrong policy 100% of the time; I thought
there could have been a context switch race during page allocation
that would result in 100% incorrect, but anyway it could still be
significantly incorrect couldn't it?)

> > > That means large amounts of memory are going to be caught in these queues.
> > > If its per cpu and one cpu does allocation and the other frees then the
> > > first cpu will consume more and more memory from the page allocator
> > > whereas the second will build up huge per cpu lists.
> >
> > Wrong. I said I would allow an option to turn off *periodic trimming*.
> > Or just modify the existing tunables or look at making the trimming
> > more fine grained etc etc. I won't know until I see a workload where it
> > hurts, and I will try to solve it then.
>
> You are not responding to the issue. If you have queues that contain
> objects from multiple pages then every object pointer in these queues can
> pin a page although this actually is a free object.

I am trying to respond to what you raise. "The" issue I thought you
raised above was that SLQB would grow freelists unbounded

"the first cpu will consume more and more memory from the page allocator
whereas the second will build up huge per cpu lists"

And this is wrong. There is another possible issue where every single
object on the freelist might come from a different (and otherwise free)
page, and thus eg 100 8 byte objects might consume 400K.

That's not an invalid concern, but I think it will be quite rare, and
the periodic queue trimming should naturally help this because it will
cycle out those objects and if new allocations are needed, they will
come from new pages which can be packed more densely.

> > > It seems that on SMP systems SLQB will actually increase the number of
> > > queues since it needs 2 queues per cpu instead of the 1 of SLAB.
> >
> > I don't know what you mean when you say queues, but SLQB has more
> > than 2 queues per CPU. Great. I like them ;)
>
> This gets better and better.

So no response to my asking where the TLB improvement in SLUB helps,
or where queueing hurts? You complain about not being able to reproduce
Intel's OLTP problem, and yet you won't even _say_ what the problems
are for SLQB. Wheras Intel at least puts a lot of effort into running
tests and helping to analyse things.

> > > SLAB also
> > > has resizable queues.
> >
> > Not significantly because that would require large memory allocations for
> > large queues. And there is no code there to do runtime resizing.
>
> Groan. Please have a look at do_tune_cpucache() in slab.c

Cool, I didn't realise it had hooks to do runtime resizing. The more
important issue of course is the one of extra cache footprint and
metadata in SLAB's scheme.

2009-01-23 04:18:14

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Wed, Jan 21, 2009 at 07:19:08PM -0500, Christoph Lameter wrote:
> On Mon, 19 Jan 2009, Nick Piggin wrote:
>
> > The thing IMO you forget with all these doomsday scenarios about SGI's peta
> > scale systems is that no matter what you do, you can't avoid the fact that
> > computing is about locality. Even if you totally take the TLB out of the
> > equation, you still have the small detail of other caches. Code that jumps
> > all over that 1024 TB of memory with no locality is going to suck regardless
> > of what the kernel ever does, due to physical limitations of hardware.
>
> Typically we traverse lists of objects that are in the same slab cache.

Very often that is not the case. And the price you pay for that is that
you have to drain and switch freelists whenever you encounter an object
that is not on the same page.

This gives your freelists a chaotic and unpredictable behaviour IMO in
a running system where pages succumb to fragmentation so your freelist
maximum sizes are limited. It also means you can lose track of cache
hot objects when you switch to different "fast" pages. I don't consider
this to be "queueing done right".

> > > Sorry not at all. SLAB and SLQB queue objects from different pages in the
> > > same queue.
> >
> > The last sentence is what I was replying to. Ie. "simplification of
> > numa handling" does not follow from the SLUB implementation of per-page
> > freelists.
>
> If all objects are from the same page then you need not check
> the NUMA locality of any object on that queue.

In SLAB and SLQB, all objects on the freelist are on the same node. So
tell me how does same-page objects simplify numa handling?

> > > As I sad it pins a single page in the per cpu page and uses that in a way
> > > that you call a queue and I call a freelist.
> >
> > And you found you have to increase the size of your pages because you
> > need bigger queues. (must we argue semantics? it is a list of free
> > objects)
>
> Right. That may be the case and its a similar tuning to what SLAB does.

SLAB and SLQB doesn't need bigger pages to do that.

> > > SLAB and SLUB can have large quantities of objects in their queues that
> > > each can keep a single page out of circulation if its the last
> > > object in that page. This is per queue thing and you have at least two
> >
> > And if that were a problem, SLQB can easily be runtime tuned to keep no
> > objects in its object lists. But as I said, queueing is good, so why
> > would anybody want to get rid of it?
>
> Queing is sometimes good....
>
> > Again, this doesn't really go anywhere while we disagree on the
> > fundamental goodliness of queueing. This is just describing the
> > implementation.
>
> I am not sure that you understand the fine points of queuing in slub. I am
> not a fundamentalist: Queues are good if used the right way and as you say
> SLUB has "queues" designed in a particular fashion that solves issus that
> we had with SLAB queues.

OK, and I juts don't think they solved all the problems and they added
other worse ones. And if you would tell me what the problems are and
how to reproduce them (or point to someone who might be able to help
with reproducing them), then I'm confident that I can solve those problems
in SLQB, which has fewer downsides than SLUB. At least I will try my best.

So can you please give a better idea of the problems? "latency sensitive
HPC applications" is about as much help to me solving that as telling
you that "OLTP applications slow down" helps solve one of the problems in
SLUB.

2009-01-23 15:44:19

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Fri, 23 Jan 2009, Nick Piggin wrote:

> > No it cannot because in SLUB objects must come from the same page.
> > Multiple objects in a queue will only ever require a single page and not
> > multiple like in SLAB.
>
> I don't know how that solves the problem. Task with memory policy A
> allocates an object, which allocates the "fast" page with policy A
> and allocates an object. Then context switch to task with memory
> policy B which allocates another object, which is taken from the page
> allocated with policy A. Right?

Correct. But this is only an issue if you think about policies applying to
individual object allocations (like realized in SLAB). If policies only
apply to pages (which is sufficient for balancing IMHO) then this is okay.

> > (OK this doesn't give the wrong policy 100% of the time; I thought
> there could have been a context switch race during page allocation
> that would result in 100% incorrect, but anyway it could still be
> significantly incorrect couldn't it?)

Memory policies are applied in a fuzzy way anyways. A context switch can
result in page allocation action that changes the expected interleave
pattern. Page populations in an address space depend on the task policy.
So the exact policy applied to a page depends on the task. This isnt an
exact thing.

> "the first cpu will consume more and more memory from the page allocator
> whereas the second will build up huge per cpu lists"
>
> And this is wrong. There is another possible issue where every single
> object on the freelist might come from a different (and otherwise free)
> page, and thus eg 100 8 byte objects might consume 400K.
>
> That's not an invalid concern, but I think it will be quite rare, and
> the periodic queue trimming should naturally help this because it will
> cycle out those objects and if new allocations are needed, they will
> come from new pages which can be packed more densely.

Well but you said that you would defer the trimming (due to latency
concerns). The longer you defer the larger the lists will get.

2009-01-23 15:44:34

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Thu, 22 Jan 2009, Pekka Enberg wrote:

> That is, a list of pages that could be returned to the page allocator
> but are pooled in SLUB to avoid the page allocator overhead. Note that
> this will not help allocators that trigger page allocator pass-through.

We use the partial list for that.

2009-01-23 15:44:52

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Thu, 22 Jan 2009, Pekka Enberg wrote:

> On Wed, 2009-01-21 at 19:13 -0500, Christoph Lameter wrote:
> > No it cannot because in SLUB objects must come from the same page.
> > Multiple objects in a queue will only ever require a single page and not
> > multiple like in SLAB.
>
> There's one potential problem with "per-page queues", though. The bigger
> the object, the smaller the "queue" (i.e. less objects per page). Also,
> partial lists are less likely to help for big objects because they get
> emptied so quickly and returned to the page allocator. Perhaps we should
> do a small "full list" for caches with large objects?

Right thats why there is need for higher order allocs because that
increases the "queue" sizes. If the pages are larger then also the partial
lists will cover more ground. Much of the tuning in SLUB is the page size
setting (remember you can set the order for each slab in slub!). In
SLAB/SLQB the corresponding tuning is through the queue sizes.

2009-01-23 15:53:21

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Fri, Jan 23, 2009 at 10:41:15AM -0500, Christoph Lameter wrote:
> On Fri, 23 Jan 2009, Nick Piggin wrote:
>
> > > No it cannot because in SLUB objects must come from the same page.
> > > Multiple objects in a queue will only ever require a single page and not
> > > multiple like in SLAB.
> >
> > I don't know how that solves the problem. Task with memory policy A
> > allocates an object, which allocates the "fast" page with policy A
> > and allocates an object. Then context switch to task with memory
> > policy B which allocates another object, which is taken from the page
> > allocated with policy A. Right?
>
> Correct. But this is only an issue if you think about policies applying to
> individual object allocations (like realized in SLAB). If policies only
> apply to pages (which is sufficient for balancing IMHO) then this is okay.

According to memory policies, a task's memory policy is supposed to
apply to its slab allocations too.

> > > (OK this doesn't give the wrong policy 100% of the time; I thought
> > there could have been a context switch race during page allocation
> > that would result in 100% incorrect, but anyway it could still be
> > significantly incorrect couldn't it?)
>
> Memory policies are applied in a fuzzy way anyways. A context switch can
> result in page allocation action that changes the expected interleave
> pattern. Page populations in an address space depend on the task policy.
> So the exact policy applied to a page depends on the task. This isnt an
> exact thing.

There are other memory policies than just interleave though.

> > "the first cpu will consume more and more memory from the page allocator
> > whereas the second will build up huge per cpu lists"
> >
> > And this is wrong. There is another possible issue where every single
> > object on the freelist might come from a different (and otherwise free)
> > page, and thus eg 100 8 byte objects might consume 400K.
> >
> > That's not an invalid concern, but I think it will be quite rare, and
> > the periodic queue trimming should naturally help this because it will
> > cycle out those objects and if new allocations are needed, they will
> > come from new pages which can be packed more densely.
>
> Well but you said that you would defer the trimming (due to latency
> concerns). The longer you defer the larger the lists will get.

But that is wrong. The lists obviously have high water marks that
get trimmed down. Periodic trimming as I keep saying basically is
alrady so infrequent that it is irrelevant (millions of objects
per cpu can be allocated anyway between existing trimming interval)

2009-01-23 16:27:20

[permalink] [raw]

Subject: Re: [patch] SLQB slab allocator

On Fri, 23 Jan 2009, Nick Piggin wrote:

> > > The thing IMO you forget with all these doomsday scenarios about SGI's peta
> > > scale systems is that no matter what you do, you can't avoid the fact that
> > > computing is about locality. Even if you totally take the TLB out of the
> > > equation, you still have the small detail of other caches. Code that jumps
> > > all over that 1024 TB of memory with no locality is going to suck regardless
> > > of what the kernel ever does, due to physical limitations of hardware.
> >
> > Typically we traverse lists of objects that are in the same slab cache.
>
> Very often that is not the case. And the price you pay for that is that
> you have to drain and switch freelists whenever you encounter an object
> that is not on the same page.

SLUB can directly free an object to any slab page. "Queuing" on free via
the per cpu slab is only possible if the object came from that per cpu
slab. This is typically only the case for objects that were recently
allocated.

There is no switching of queues because they do not exist in that form in
SLUB. We always determine the page address and put the object into the
freelist of that page. Also results in nice parallelism since the lock is
not even cpu specific.

> This gives your freelists a chaotic and unpredictable behaviour IMO in
> a running system where pages succumb to fragmentation so your freelist
> maximum sizes are limited. It also means you can lose track of cache
> hot objects when you switch to different "fast" pages. I don't consider
> this to be "queueing done right".

Yes you can loose track of caching hot objects. That is one of the
concerns with the SLUB approach. On the other hand: Caching architectures
get more and more complex these days (especially in a NUMA system). The
SLAB approach is essentially trying to guess which objects are cache hot
and queue them. Sometimes the queueing is advantageous (may be a reason
that SLAB is better than SLUB in some cases). In other cases SLAB keeps
objects on queues but the object have become sale (context switch, slab
unused for awhile). Then its no advantage anymore.

> > If all objects are from the same page then you need not check
> > the NUMA locality of any object on that queue.
>
> In SLAB and SLQB, all objects on the freelist are on the same node. So
> tell me how does same-page objects simplify numa handling?

F.e. On free you need to determine the node to find the right queue in
SLAB. SLUB does not need to do that. It simply determines the page address
and does not care about the node when freeing the object. It is irrelevant
on which node the object sits.

Also on alloc: The per cpu slab can be from a foreign node. NUMA locality
does only matter if the caller wants memory from a particular node. So
cpus that have no local memory can still use the per cpu slabs to have
fast allocations etc etc.

> > > And you found you have to increase the size of your pages because you
> > > need bigger queues. (must we argue semantics? it is a list of free
> > > objects)
> >
> > Right. That may be the case and its a similar tuning to what SLAB does.
>
> SLAB and SLQB doesn't need bigger pages to do that.

But they require more metadata handling because they need to manage lists
of order-0 pages. metadata handling is reduced by orders of magnitude in
SLUB.

2009-01-26 17:31:40