SLQB slab allocator

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.

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

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

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

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

mm/slqb.c new file +28 -0

@@ -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;
+}
+

mm/slqb.c new file +17 -0

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

mm/slqb.c new file +12 -0

+#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;

mm/slqb.c new file +31 -0

+
+	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)
+{

mm/slqb.c new file +10 -0

+		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);

mm/slqb.c new file +34 -0

+			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); */
+	}
+

mm/slqb.c new file +5 -0

+/*
+ * 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,

mm/slqb.c new file +9 -0

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

Hi Nick,

Quoted 19 lines · Nick Piggin

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.

Quoted 8 lines

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.

include/linux/slqb_def.h line 92

Quoted 7 lines

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

+/*
+ * 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.

Quoted 5 lines

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

+/*
+ * 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)

include/linux/slqb_def.h line 178

Quoted 5 lines

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

+{
+	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?

Quoted 12 lines

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

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

include/linux/slqb_def.h line 210

Quoted 5 lines

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

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

include/linux/slqb_def.h line 251

Quoted 4 lines

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

+#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?

Quoted 5 lines

+/*
+ * 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.

Quoted 22 lines

mm/slqb.c new file +22 -0

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

mm/slqb.c line 65

Quoted 5 lines

mm/slqb.c new file +5 -0

+#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?

Quoted 17 lines

mm/slqb.c new file +17 -0

+#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)

mm/slqb.c line 1114

Quoted 5 lines

mm/slqb.c new file +5 -0

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

Quoted 6 lines

mm/slqb.c new file +6 -0

+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)) {

mm/slqb.c line 1155

Quoted 6 lines

mm/slqb.c new file +6 -0

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

Review

Quoted 2 lines

(quoted diff) +2 -0

+			if (next)
+				prefetchw(next);

Or here?

mm/slqb.c line 1219

Quoted 5 lines

mm/slqb.c new file +5 -0

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

Quoted 5 lines

mm/slqb.c new file +5 -0

+/*
+ * 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,

mm/slqb.c line 1401

Quoted 10 lines

mm/slqb.c new file +10 -0

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

Quoted 15 lines

mm/slqb.c new file +14 -0

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

mm/slqb.c line 1420

Quoted 5 lines

mm/slqb.c new file +5 -0

+#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.

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.

Quoted 5 lines

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.

Quoted 6 lines

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.

Quoted 9 lines

Quoted 5 lines

+/*
+ * 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.

Quoted 7 lines

mm/slqb.c line 1219

Quoted 4 lines

mm/slqb.c new file +4 -0

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

Hi Nick,

Quoted 8 lines · Nick Piggin

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.

Quoted 10 lines

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.

Quoted 6 lines

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.

Quoted 8 lines

Quoted 7 lines

mm/slqb.c line 1219

Quoted 4 lines

mm/slqb.c new file +4 -0

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

Quoted 3 lines

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.

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

Hi Nick,

Quoted 5 lines · Nick Piggin

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 :-).

Quoted 4 lines

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 ;-).

Quoted 5 lines · Pekka Enberg

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

Quoted 9 lines · Nick Piggin

Quoted 4 lines

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.

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.

Hi Nick,

Quoted 4 lines · Nick Piggin

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 ;).

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?".

Quoted 4 lines · Nick Piggin

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.

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.

Quoted 2 lines

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.

Quoted 2 lines

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.

Quoted 2 lines

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.

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.

Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 4 lines · Nick Piggin

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.

Quoted 7 lines

Quoted 2 lines

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

Quoted 2 lines

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

Quoted 2 lines

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?

Quoted 8 lines

Quoted 2 lines

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.

Quoted 5 lines

Quoted 2 lines

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.

Quoted 2 lines

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

Quoted 9 lines

Quoted 4 lines

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.

Quoted 4 lines

Quoted 3 lines

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.

Quoted 4 lines

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.

Quoted 4 lines

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.

Quoted 2 lines

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?

Quoted 2 lines

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.

Quoted 5 lines

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.

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.

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

Quoted 3 lines

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.

Quoted 5 lines · Nick Piggin

Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 2 lines

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

Quoted 4 lines

Quoted 2 lines

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.

Quoted 12 lines

Quoted 2 lines

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.

Quoted 5 lines

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.

Quoted 3 lines

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.

Quoted 4 lines

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.

Quoted 4 lines

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?

Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 9 lines

Quoted 3 lines

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.

Quoted 1 line

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.

Quoted 7 lines

Quoted 3 lines

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.

Quoted 4 lines

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.

Quoted 2 lines

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

Quoted 2 lines

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.

Quoted 11 lines

Quoted 7 lines

Quoted 3 lines

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.

Hi Christoph,

Quoted 11 lines · Nick Piggin

Quoted 11 lines

Quoted 7 lines

Quoted 3 lines

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.

Quoted 3 lines · Christoph Lameter

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?

Quoted 20 lines · Pekka Enberg

Hi Christoph,

Quoted 11 lines · Nick Piggin

Quoted 11 lines

Quoted 7 lines

Quoted 3 lines

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.

Quoted 3 lines · Christoph Lameter

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.

Quoted 5 lines

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.

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.

Quoted 3 lines

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.

Quoted 3 lines · Pekka Enberg

Quoted 3 lines

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.

Quoted 1 line · Christoph Lameter

We use the partial list for that.

Even if the slab is totally empty?

Quoted 3 lines · Christoph Lameter

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?

Quoted 4 lines · Nick Piggin

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 5 lines

Quoted 4 lines

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.

Quoted 4 lines

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.

Quoted 5 lines

Quoted 2 lines

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.

Quoted 5 lines

Quoted 2 lines

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

Quoted 3 lines

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?

Quoted 1 line

(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?)

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

Quoted 9 lines · Nick Piggin

Quoted 3 lines

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.

Quoted 4 lines

Quoted 1 line

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

Quoted 7 lines

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

Quoted 4 lines

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.

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

Quoted 5 lines

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.

Quoted 12 lines

Quoted 11 lines

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

Quoted 2 lines

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)

Quoted 2 lines · Nick Piggin

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

It does apply to slab allocations. The question is whether it has to apply to every object allocation or to every page allocation of the slab allocators.

Quoted 7 lines

Quoted 5 lines

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.

Which have similar issues since memory policy application is depending on a task policy and on memory migration that has been applied to an address range.

Quoted 4 lines

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)

Trimming through water marks and allocating memory from the page allocator is going to be very frequent if you continually allocate on one processor and free on another.

Quite obviously it should. Behaviour of a slab allocation on behalf of some task constrained within a given node should not depend on the task which has previously run on this CPU and made some allocations. Surely you can see this behaviour is not nice.

Quoted 3 lines

Which have similar issues since memory policy application is depending on a task policy and on memory migration that has been applied to an address range.

What similar issues? If a task ask to have slab allocations constrained to node 0, then SLUB hands out objects from other nodes, then that's bad.

Quoted 5 lines

Quoted 4 lines

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)

Quoted 3 lines

Trimming through water marks and allocating memory from the page allocator is going to be very frequent if you continually allocate on one processor and free on another.

Um yes, that's the point. But you previously claimed that it would just grow unconstrained. Which is obviously wrong. So I don't understand what your point is.

Quoted 7 lines

Quoted 3 lines

Trimming through water marks and allocating memory from the page allocator is going to be very frequent if you continually allocate on one processor and free on another.

Um yes, that's the point. But you previously claimed that it would just grow unconstrained. Which is obviously wrong. So I don't understand what your point is.

It will grow unconstrained if you elect to defer queue processing. That was what we discussed.

Quoted 2 lines

It will grow unconstrained if you elect to defer queue processing. That was what we discussed.

Well, the slab_hiwater() check in __slab_free() of mm/slqb.c will cap the size of the queue. But we do the same thing in SLAB with alien->limit in cache_free_alien() and ac->limit in __cache_free(). So I'm not sure what you mean when you say that the queues will "grow unconstrained" (in either of the allocators). Hmm?

Quoted 8 lines · Pekka Enberg

Quoted 2 lines

It will grow unconstrained if you elect to defer queue processing. That was what we discussed.

Well, the slab_hiwater() check in __slab_free() of mm/slqb.c will cap the size of the queue. But we do the same thing in SLAB with alien->limit in cache_free_alien() and ac->limit in __cache_free(). So I'm not sure what you mean when you say that the queues will "grow unconstrained" (in either of the allocators). Hmm?

That said, I can imagine a worst-case scenario where a queue with N objects is pinning N mostly empty slabs. As soon as we hit the periodical flush, we might need to do tons of work. That's pretty hard to control with watermarks as well as the scenario is solely dependent on allocation/free patterns.

That's very true, and we touched on this earlier. It is I guess you can say a downside of queueing. But an analogous situation in SLUB would be that lots of pages on the partial list with very few free objects, or freeing objects to pages with few objects in them. Basically SLUB will have to do the extra work in the fastpath.

Quoted 6 lines · Nick Piggin

That's very true, and we touched on this earlier. It is I guess you can say a downside of queueing. But an analogous situation in SLUB would be that lots of pages on the partial list with very few free objects, or freeing objects to pages with few objects in them. Basically SLUB will have to do the extra work in the fastpath.

But these are pages with mostly allocated objects and just a few objects free. The SLAB case is far worse: You have N objects on a queue and they are keeping possibly N pages away from the page allocator and in those pages *nothing* is used.

Well, the slab_hiwater() check in __slab_free() of mm/slqb.c will cap the size of the queue. But we do the same thing in SLAB with alien->limit in cache_free_alien() and ac->limit in __cache_free(). So I'm not sure what you mean when you say that the queues will "grow unconstrained" (in either of the allocators). Hmm?

Quoted 5 lines · Pekka Enberg

Well, the slab_hiwater() check in __slab_free() of mm/slqb.c will cap the size of the queue. But we do the same thing in SLAB with alien->limit in cache_free_alien() and ac->limit in __cache_free(). So I'm not sure what you mean when you say that the queues will "grow unconstrained" (in either of the allocators). Hmm?

Nick said he wanted to defer queue processing. If the water marks are checked and queue processing run then of course queue processing is not deferred and the queue does not build up further.

Quoted 4 lines · Nick Piggin

Quite obviously it should. Behaviour of a slab allocation on behalf of some task constrained within a given node should not depend on the task which has previously run on this CPU and made some allocations. Surely you can see this behaviour is not nice.

If you want cache hot objects then its better to use what a prior task has used. This opportunistic use is only done if the task is not asking for memory from a specifc node. There is another tradeoff here.

SLABs method there is to ignore all caching advantages even if the task did not ask for memory from a specific node. So it gets cache cold objects and if the node to allow from is remote then it always must use the slow path.

Quoted 6 lines

Quoted 3 lines

Which have similar issues since memory policy application is depending on a task policy and on memory migration that has been applied to an address range.

What similar issues? If a task ask to have slab allocations constrained to node 0, then SLUB hands out objects from other nodes, then that's bad.

Of course. A task can ask to have allocations from node 0 and it will get the object from node 0. But if the task does not care to ask for data from a specific node then it can be satisfied from the cpu slab which contains cache hot objects.

Quoted 9 lines

Quoted 8 lines

Quoted 4 lines

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)

Trimming through water marks and allocating memory from the page allocator is going to be very frequent if you continually allocate on one processor and free on another.

Quoted 3 lines

Um yes, that's the point. But you previously claimed that it would just grow unconstrained. Which is obviously wrong. So I don't understand what your point is.

It will grow unconstrained if you elect to defer queue processing. That was what we discussed.

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

Quoted 5 lines · Nick Piggin

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.

Quoted 3 lines

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.

Quoted 2 lines

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.

Quoted 3 lines

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.

Quoted 9 lines

Quoted 3 lines

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.

Quoted 3 lines · Nick Piggin

Quoted 2 lines

The higher orders can fail and will then result in the allocator doing order 0 allocs. It is not a failure condition.

Quoted 4 lines

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.

Quoted 10 lines

Quoted 3 lines

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.

Quoted 5 lines

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.

Quoted 4 lines

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.

Quoted 4 lines

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

Quoted 3 lines

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.

Quoted 5 lines

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.

Quoted 5 lines · Nick Piggin

Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 5 lines

Quoted 3 lines

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.

Quoted 6 lines

Quoted 5 lines

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.

Quoted 3 lines

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.

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.

Quoted 2 lines

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.

Quoted 2 lines

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)

Quoted 3 lines

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?

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

Quoted 6 lines · Nick Piggin

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.

Quoted 6 lines

Quoted 2 lines

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.

Quoted 6 lines

Quoted 2 lines

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.

Quoted 7 lines

Quoted 3 lines

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

Quoted 3 lines

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.

Quoted 7 lines

Quoted 6 lines

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.

Quoted 1 line

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

Quoted 2 lines

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?

Quoted 5 lines

Quoted 3 lines

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.

Quoted 2 lines · Nick Piggin

Quoted 1 line

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

Quoted 3 lines

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.

Quoted 5 lines

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.

Quoted 5 lines

Quoted 2 lines

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.

Quoted 7 lines

Quoted 5 lines

Quoted 3 lines

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.

Quoted 8 lines · Christoph Lameter

Quoted 6 lines · Nick Piggin

Quoted 2 lines

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.

Quoted 4 lines

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.

Ah yes ok that's right. But then you don't get LIFO allocation behaviour for those cases.

Quoted 5 lines

Quoted 4 lines

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.

Quoted 2 lines

Ah yes ok that's right. But then you don't get LIFO allocation behaviour for those cases.

And actually really this all just stems from conceptually in fact you _do_ switch to a different queue (from the one being allocated from) to free the object if it is on a different page. Because you have a set of queues (a queue per-page). So freeing to a different queue is where you lose LIFO property.

Quoted 5 lines · Nick Piggin

Quoted 5 lines

Quoted 4 lines

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.

Quoted 8 lines

Quoted 2 lines

Ah yes ok that's right. But then you don't get LIFO allocation behaviour for those cases.

And actually really this all just stems from conceptually in fact you _do_ switch to a different queue (from the one being allocated from) to free the object if it is on a different page. Because you have a set of queues (a queue per-page). So freeing to a different queue is where you lose LIFO property.

Yes you basically go for locality instead of LIFO if the free does not hit the per cpu slab. If the object is not in the per cpu slab then it is likely that it had a long lifetime and thus LIFOness does not matter too much. It is likely that many objects from that slab are going to be freed at the same time. So the first free warms up the "queue" of the page you are freeing to.

This is an increasingly important feature since memory chips prefer allocations next to each other. Same page accesses are faster in recent memory subsystems than random accesses across memory.

LIFO used
to be better but we are increasingly getting into locality of access being very important for access.

Especially with the NUMA characteristics of the
existing AMD and upcoming Nehalem processors this will become much more important.

Quoted 4 lines

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.

Ah yes ok that's right. But then you don't get LIFO allocation behaviour for those cases.

Quoted 6 lines

Quoted 2 lines

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

Because it is more important to get good cache behaviour.

So I think it is wrong to say it requires more metadata handling. SLUB will have to switch pages more often or free objects to pages other than the "fast" page (what do you call it?), so quite often I think you'll find SLUB has just as much if not more metadata handling.

Quoted 7 lines · Nick Piggin

Quoted 4 lines

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.

Ah yes ok that's right. But then you don't get LIFO allocation behaviour for those cases.

But you get more TLB local allocations.

Quoted 6 lines

Quoted 4 lines

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

Because it is more important to get good cache behaviour.

Its going to be quite difficult to realize algorithm that guestimate what information the processor keeps in its caches. The situation is quite complex in NUMA systems.

Quoted 4 lines

So I think it is wrong to say it requires more metadata handling. SLUB will have to switch pages more often or free objects to pages other than the "fast" page (what do you call it?), so quite often I think you'll find SLUB has just as much if not more metadata handling.

Its the per cpu slab. SLUB does not switch pages often but frees objects not from the per cpu slab directly with minimal overhead compared to a per cpu slab free. The overhead is much less than the SLAB slowpath which has to be taken for alien caches etc.