Skip to contentSkip to conversation

Introducing lockless cache built on top of slab allocator

RFC PATCH In review Hyeonggon Yoo 4 participants 11 messages Sep 19, 2021 – Sep 20, 2021 Memory management

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 Introducing lockless cache built on top of slab allocator

It is just simple proof of concept, and not ready for submission yet. There can be wrong code (like wrong gfp flags, or wrong error handling, etc) it is just simple proof of concept. I want comment from you.

Recently block layer implemented percpu, lockless cache on the top of slab allocator. It can be used for IO polling, because IO polling disables interrupt.

it gained some IOPS increase after this. (Note that Jens used SLUB on performance measurement)

this is generalization of what have been done in block layer, built on top of slab allocator.

lockless cache uses simple queuing to be more cache friendly. and when the percpu freelist gets too big, it returns some objects back to slab allocator.

it seems lockless cache can be used network layer's IO Polling (NAPI) too.

Any ideas/opinions on this?

---
 include/linux/lockless_cache.h |  31 ++++++++
 init/main.c                    |   2 +
 mm/Makefile                    |   2 +-
 mm/lockless_cache.c            | 132 +++++++++++++++++++++++++++++++++
 4 files changed, 166 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/lockless_cache.h
 create mode 100644 mm/lockless_cache.c
include/linux/lockless_cache.h new file +31 -0
new file mode 100644
index 000000000000..e64b85e869f3
@@ -0,0 +1,31 @@
+#include <linux/gfp.h>
+
+struct object_list {
+	void *object;
+	struct list_head list;
+};
+
+struct freelist {
+	struct object_list *head;
+	int size;
+};
+
+struct lockless_cache {
+	struct kmem_cache *cache;
+	struct freelist __percpu *freelist;
+
+	int total_size;
+	unsigned int max; /* maximum size for each percpu freelist */
+	unsigned int slack; /* number of objects returning to slab when freelist is too big (> max) */
+};
+
+void lockless_cache_init(void);
+struct lockless_cache
+*lockless_cache_create(const char *name, unsigned int size, unsigned int align,
+		slab_flags_t flags, void (*ctor)(void *), unsigned int max,
+		unsigned int slack);
+
+void lockless_cache_destroy(struct lockless_cache *cache);
+void *lockless_cache_alloc(struct lockless_cache *cache, gfp_t flags);
+void lockless_cache_free(struct lockless_cache *cache, void *object);
+
init/main.c +2 -0
index 3f7216934441..c18d6421cb65 100644
@@ -79,6 +79,7 @@
 #include <linux/async.h>
 #include <linux/shmem_fs.h>
 #include <linux/slab.h>
+#include <linux/lockless_cache.h>
 #include <linux/perf_event.h>
 #include <linux/ptrace.h>
 #include <linux/pti.h>
@@ -848,6 +849,7 @@ static void __init mm_init(void)
 	/* page_owner must be initialized after buddy is ready */
 	page_ext_init_flatmem_late();
 	kmem_cache_init();
+	lockless_cache_init();
 	kmemleak_init();
 	pgtable_init();
 	debug_objects_mem_init();
mm/Makefile +1 -1
index fc60a40ce954..d6c3a89ed548 100644
@@ -52,7 +52,7 @@ obj-y			:= filemap.o mempool.o oom_kill.o fadvise.o \
 			   mm_init.o percpu.o slab_common.o \
 			   compaction.o vmacache.o \
 			   interval_tree.o list_lru.o workingset.o \
-			   debug.o gup.o mmap_lock.o $(mmu-y)
+			   debug.o gup.o mmap_lock.o lockless_cache.o $(mmu-y)
 
 # Give 'page_alloc' its own module-parameter namespace
 page-alloc-y := page_alloc.o
mm/lockless_cache.c new file +132 -0

132 lines not on this page · raw message

Signature · 1 line
2.27.0
#1 lore raw
Quoted 3 lines · Hyeonggon Yoo

It is just simple proof of concept, and not ready for submission yet. There can be wrong code (like wrong gfp flags, or wrong error handling, etc) it is just simple proof of concept. I want comment from you.

Have you read:

https://www.usenix.org/legacy/event/usenix01/full_papers/bonwick/bonwick_html/

The relevant part of that paper is section 3, magazines. We should have low and high water marks for number of objects, and we should allocate from / free to the slab allocator in batches. Slab has bulk alloc/free APIs already.

I'd rather see this be part of the slab allocator than a separate API.

#2 lore raw

Hello Matthew, Thanks to give me a comment! I appreciate it.

Quoted 10 lines · Matthew Wilcox
Quoted 3 lines · Hyeonggon Yoo

It is just simple proof of concept, and not ready for submission yet. There can be wrong code (like wrong gfp flags, or wrong error handling, etc) it is just simple proof of concept. I want comment from you.

Have you read:

https://www.usenix.org/legacy/event/usenix01/full_papers/bonwick/bonwick_html/
The relevant part of that paper is section 3, magazines. We should have low and high water marks for number of objects

I haven't read that before, but after reading it seems not different from SLAB's percpu queuing.

Quoted 4 lines

and we should allocate
from / free to the slab allocator in batches. Slab has bulk alloc/free APIs already.

There's kmem_cache_alloc_{bulk,free} functions for bulk allocation. But it's designed for large number of allocation to reduce locking cost, not for percpu lockless allocation.

Yeah, we can implement lockless cache using kmem_cache_alloc_{bulk, free} but kmem_cache_alloc_{free,bulk} is not enough.

Quoted 1 line

I'd rather see this be part of the slab allocator than a separate API.

And I disagree on this. for because most of situation, we cannot allocate without lock, it is special case for IO polling.

To make it as part of slab allocator, we need to modify existing data structure. But making it part of slab allocator will be waste of memory because most of them are not using this.

#3 lore raw
Quoted 17 lines · Hyeonggon Yoo

Hello Matthew, Thanks to give me a comment! I appreciate it.

Quoted 10 lines · Matthew Wilcox
Quoted 3 lines · Hyeonggon Yoo

It is just simple proof of concept, and not ready for submission yet. There can be wrong code (like wrong gfp flags, or wrong error handling, etc) it is just simple proof of concept. I want comment from you.

Have you read:

https://www.usenix.org/legacy/event/usenix01/full_papers/bonwick/bonwick_html/
The relevant part of that paper is section 3, magazines. We should have low and high water marks for number of objects

I haven't read that before, but after reading it seems not different from SLAB's percpu queuing.

Quoted 8 lines
Quoted 4 lines

and we should allocate
from / free to the slab allocator in batches. Slab has bulk alloc/free APIs already.

There's kmem_cache_alloc_{bulk,free} functions for bulk allocation. But it's designed for large number of allocation to reduce locking cost, not for percpu lockless allocation.

What I'm saying is that rather than a linked list of objects, we should have an array of, say, 15 pointers per CPU (and a count of how many allocations we have). If we are trying to allocate and have no objects, call kmem_cache_alloc_bulk() for 8 objects. If we are trying to free and have 15 objects already, call kmem_cache_free_bulk() for the last 8 objects and set the number of allocated objects to 7.

(maybe 8 and 15 are the wrong numbers. this is just an example)

Quoted 11 lines

Yeah, we can implement lockless cache using kmem_cache_alloc_{bulk, free} but kmem_cache_alloc_{free,bulk} is not enough.

Quoted 1 line

I'd rather see this be part of the slab allocator than a separate API.

And I disagree on this. for because most of situation, we cannot allocate without lock, it is special case for IO polling.

To make it as part of slab allocator, we need to modify existing data structure. But making it part of slab allocator will be waste of memory because most of them are not using this.

Oh, it would have to be an option. Maybe as a new slab_flags_t flag. Or maybe a kmem_cache_alloc_percpu_lockless().

#4 lore raw
Quoted 27 lines · Matthew Wilcox
Quoted 17 lines · Hyeonggon Yoo

Hello Matthew, Thanks to give me a comment! I appreciate it.

Quoted 10 lines · Matthew Wilcox
Quoted 3 lines · Hyeonggon Yoo

It is just simple proof of concept, and not ready for submission yet. There can be wrong code (like wrong gfp flags, or wrong error handling, etc) it is just simple proof of concept. I want comment from you.

Have you read:

https://www.usenix.org/legacy/event/usenix01/full_papers/bonwick/bonwick_html/
The relevant part of that paper is section 3, magazines. We should have low and high water marks for number of objects

I haven't read that before, but after reading it seems not different from SLAB's percpu queuing.

Quoted 8 lines
Quoted 4 lines

and we should allocate
from / free to the slab allocator in batches. Slab has bulk alloc/free APIs already.

There's kmem_cache_alloc_{bulk,free} functions for bulk allocation. But it's designed for large number of allocation to reduce locking cost, not for percpu lockless allocation.

Quoted 9 lines

What I'm saying is that rather than a linked list of objects, we should have an array of, say, 15 pointers per CPU (and a count of how many allocations we have). If we are trying to allocate and have no objects, call kmem_cache_alloc_bulk() for 8 objects. If we are trying to free and have 15 objects already, call kmem_cache_free_bulk() for the last 8 objects and set the number of allocated objects to 7.

(maybe 8 and 15 are the wrong numbers. this is just an example)

Ah, Okay. it seems better to use array. Using cache for list is unnecessary cost. array is simpler.

Quoted 8 lines
Quoted 8 lines

Yeah, we can implement lockless cache using kmem_cache_alloc_{bulk, free} but kmem_cache_alloc_{free,bulk} is not enough.

Quoted 1 line

I'd rather see this be part of the slab allocator than a separate API.

And I disagree on this. for because most of situation, we cannot allocate without lock, it is special case for IO polling.

Quoted 6 lines
Quoted 3 lines

To make it as part of slab allocator, we need to modify existing data structure. But making it part of slab allocator will be waste of memory because most of them are not using this.

Oh, it would have to be an option. Maybe as a new slab_flags_t flag. Or maybe a kmem_cache_alloc_percpu_lockless().

Oh, Now I got what you mean. That is a good improvement!

For example,
there is a slab_flags_t flag like SLAB_LOCKLESS.
and a cache created with SLAB_LOCKLESS flag can allocate
using both kmem_cache_alloc, or kmem_cache_alloc_percpu_lockless depending on situation? (I suggest kmem_cache_alloc_lockless is better name)

it seems MUCH better. (because it prevents duplicating a cache)

I'll send RFC v2 soon.
Thank you so much Matthew.

If there's misunderstanding from me, please let me know.

Thanks,
Hyeonggon Yoo

#5 lore raw
In reply to Matthew Wilcox
Quoted 10 lines · Matthew Wilcox
Quoted 9 lines · Hyeonggon Yoo

Hello Matthew, Thanks to give me a comment! I appreciate it. Yeah, we can implement lockless cache using kmem_cache_alloc_{bulk, free} but kmem_cache_alloc_{free,bulk} is not enough.

Quoted 1 line

I'd rather see this be part of the slab allocator than a separate API.

And I disagree on this. for because most of situation, we cannot allocate without lock, it is special case for IO polling.

Quoted 6 lines
Quoted 3 lines

To make it as part of slab allocator, we need to modify existing data structure. But making it part of slab allocator will be waste of memory because most of them are not using this.

Oh, it would have to be an option. Maybe as a new slab_flags_t flag. Or maybe a kmem_cache_alloc_percpu_lockless().

I've recently found out that similar attempts (introduce queueing to SLUB) have been done around 2010. See e.g. [1] but there will be other threads to search at lore too. Haven't checked yet while it wasn't ultimately merged, I guess Christoph and David could remember (this was before my time).

I guess making it opt-in only for caches where performance improvement was measured would make it easier to add, as for some caches it would mean no improvement, but increased memory usage. But of course it makes the API more harder to use.

I'd be careful about the name "lockless", as that's ambiguous. Is it "mostly lockless" therefore fast, but if the cache is empty, it will still take locks as part of refill? Or is it lockless always, therefore useful in contexts that can take no locks, but then the caller has to have fallbacks in case the cache is empty and nothing is allocated?

[1] https://lore.kernel.org/linux-mm/[email protected]/T/#u

#6 lore raw
Quoted 15 lines · Vlastimil Babka
Quoted 14 lines · Matthew Wilcox
Quoted 12 lines · Hyeonggon Yoo

Hello Matthew, Thanks to give me a comment! I appreciate it. Yeah, we can implement lockless cache using kmem_cache_alloc_{bulk, free} but kmem_cache_alloc_{free,bulk} is not enough.

Quoted 1 line

I'd rather see this be part of the slab allocator than a separate API.

And I disagree on this. for because most of situation, we cannot allocate without lock, it is special case for IO polling.

To make it as part of slab allocator, we need to modify existing data structure. But making it part of slab allocator will be waste of memory because most of them are not using this.

Quoted 7 lines
Quoted 2 lines

Oh, it would have to be an option. Maybe as a new slab_flags_t flag. Or maybe a kmem_cache_alloc_percpu_lockless().

I've recently found out that similar attempts (introduce queueing to SLUB) have been done around 2010. See e.g. [1] but there will be other threads to search at lore too. Haven't checked yet while it wasn't ultimately merged, I guess Christoph and David could remember (this was before my time).

There was attempt on SLUB with queueing as you said. I searched a bit and found [2] and [3].

- SLUB with queueing (V2) beats SLAB netperf TCP_RR, 2010-07
[2] https://lore.kernel.org/lkml/[email protected]/T/#m5a31c7caa28b93a00de3af6d547b79273449f5ba

- The Unified slab allocator (V4), 2010-10
[3] https://linux-mm.kvack.narkive.com/e595iCuz/unifiedv4-00-16-the-unified-slab-allocator-v4#post47

Looking at [3], There was still some regression comparing "SLUB with queueing" with SLAB. And I couldn't find patch series after [3] yet. I'll add link if I find.

Quoted 4 lines

I guess making it opt-in only for caches where performance improvement was measured would make it easier to add, as for some caches it would mean no improvement, but increased memory usage. But of course it makes the API more harder to use.

Do you mean "lockless cache" it should be separate from slab because some caches doesn't benefit at all?

Quoted 3 lines

I'd be careful about the name "lockless", as that's ambiguous. Is it "mostly lockless" therefore fast, but if the cache is empty, it will still take locks as part of refill?

It is actually "mostly lockless" so it is ambiguous. Can you suggest a name? like try_lockless or anything?

Quoted 5 lines

Or is it lockless always, therefore useful in
contexts that can take no locks, but then the caller has to have fallbacks in case the cache is empty and nothing is allocated?

[1] https://lore.kernel.org/linux-mm/[email protected]/T/#u

#7 lore raw
Quoted 8 lines · Hyeonggon Yoo
Quoted 4 lines · Vlastimil Babka

I guess making it opt-in only for caches where performance improvement was measured would make it easier to add, as for some caches it would mean no improvement, but increased memory usage. But of course it makes the API more harder to use.

Do you mean "lockless cache" it should be separate from slab because some caches doesn't benefit at all?

I meant it seems to be a valid approach to have a special kmem_cache flag and allocation function variants, as you discussed. That covers the "some caches don't benefit at all" while being an integral part of the allocator, so others don't have to build ad-hoc solutions on top of it, and possibly it can be also more optimized given access to the SLUB internals.

Quoted 6 lines
Quoted 3 lines

I'd be careful about the name "lockless", as that's ambiguous. Is it "mostly lockless" therefore fast, but if the cache is empty, it will still take locks as part of refill?

It is actually "mostly lockless" so it is ambiguous. Can you suggest a name? like try_lockless or anything?

"cached" instead of "lockless" ?

Quoted 6 lines
Quoted 5 lines

Or is it lockless always, therefore useful in
contexts that can take no locks, but then the caller has to have fallbacks in case the cache is empty and nothing is allocated?

[1] https://lore.kernel.org/linux-mm/[email protected]/T/#u

#8 lore raw
Quoted 7 lines · Vlastimil Babka
Quoted 6 lines · Hyeonggon Yoo
Quoted 4 lines · Vlastimil Babka

I guess making it opt-in only for caches where performance improvement was measured would make it easier to add, as for some caches it would mean no improvement, but increased memory usage. But of course it makes the API more harder to use.

Quoted 8 lines
Quoted 2 lines

Do you mean "lockless cache" it should be separate from slab because some caches doesn't benefit at all?

I meant it seems to be a valid approach to have a special kmem_cache flag and allocation function variants, as you discussed. That covers the "some caches don't benefit at all" while being an integral part of the allocator, so others don't have to build ad-hoc solutions on top of it, and possibly it can be also more optimized given access to the SLUB internals.

Okay! I sent RFC v2. please check if how does look like to you:

	https://lore.kernel.org/linux-mm/[email protected]/T/#u
Quoted 9 lines
Quoted 6 lines
Quoted 3 lines

I'd be careful about the name "lockless", as that's ambiguous. Is it "mostly lockless" therefore fast, but if the cache is empty, it will still take locks as part of refill?

It is actually "mostly lockless" so it is ambiguous. Can you suggest a name? like try_lockless or anything?

"cached" instead of "lockless" ?

added kmem_cache_alloc_cached, kmem_cache_free_cached in v2.

Thanks for your opinion Vlastimil,
Hyeonggon.

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

Or is it lockless always, therefore useful in
contexts that can take no locks, but then the caller has to have fallbacks in case the cache is empty and nothing is allocated?

[1] https://lore.kernel.org/linux-mm/[email protected]/T/#u

#9 lore raw
In reply to Matthew Wilcox
Quoted 9 lines · Matthew Wilcox
Quoted 8 lines · Hyeonggon Yoo

Hello Matthew, Thanks to give me a comment! I appreciate it.

Quoted 5 lines · Matthew Wilcox
Quoted 3 lines · Hyeonggon Yoo

It is just simple proof of concept, and not ready for submission yet. There can be wrong code (like wrong gfp flags, or wrong error handling, etc) it is just simple proof of concept. I want comment from you.

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

Have you read:

https://www.usenix.org/legacy/event/usenix01/full_papers/bonwick/bonwick_html/
The relevant part of that paper is section 3, magazines. We should have low and high water marks for number of objects

In case unknown, jfyi there is an implementation of this in drivers/iommu/iova.c

Thanks,
John

Quoted 7 lines
Quoted 7 lines

I haven't read that before, but after reading it seems not different from SLAB's percpu queuing.

Quoted 4 lines

and we should allocate
from / free to the slab allocator in batches. Slab has bulk alloc/free APIs already.

#10 lore raw
Quoted 12 lines · John Garry
Quoted 11 lines · Matthew Wilcox
Quoted 10 lines · Hyeonggon Yoo

Hello Matthew, Thanks to give me a comment! I appreciate it.

Quoted 7 lines · Matthew Wilcox
Quoted 3 lines · Hyeonggon Yoo

It is just simple proof of concept, and not ready for submission yet. There can be wrong code (like wrong gfp flags, or wrong error handling, etc) it is just simple proof of concept. I want comment from you.

Have you read:

Quoted 7 lines
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines

https://www.usenix.org/legacy/event/usenix01/full_papers/bonwick/bonwick_html/
The relevant part of that paper is section 3, magazines. We should have low and high water marks for number of objects

In case unknown, jfyi there is an implementation of this in drivers/iommu/iova.c

Thanks for good information. I'll take a look at it!

Thanks,
Hyeonggon

Quoted 9 lines

Thanks,
John

Quoted 6 lines
Quoted 6 lines

I haven't read that before, but after reading it seems not different from SLAB's percpu queuing.

Quoted 4 lines

and we should allocate
from / free to the slab allocator in batches. Slab has bulk alloc/free APIs already.