mm, slob: Rewrite SLOB using segregated free list
Subsystems (3)
RFC PATCH 1/1 mm, slob: Rewrite SLOB using segregated free list
Hello linux-mm, I rewrote SLOB using segregated free list, to understand SLOB and SLUB more. It uses more kilobytes of memory (48kB on 32bit tinyconfig) and became 9~10x faster.
But after rewriting, I thought I need to discuss what SLOB is for. According to Matthew, SLOB is for small machines whose memory is 1~16 MB.
I wonder adding 48kB on SLOB memory for speed/lower latency is worth or harmful.
So.. questions in my head now:
- Who is users of SLOB?
- Is it harmful to add some kilobytes of memory into SLOB?
- Is it really possible to run linux under 10MB of RAM? (I failed with tinyconfig.)
- What is the boundary to make decision between SLOB and SLUB?
Anyway, below is my work.
Any comments/opinions will be appreciated!
SLOB uses sequential fit method. the advantages of this method is the fact that it is simple and does not have complex metadata.
But big downside of sequential fit method is its high latency in allocation/deallocation and fast fragmentation.
High latency comes from iterating pages and also iterating objects in the page to find suitable free object. And fragmentation easily happens because objects of difference size is allocated in same page.
This patch tries to minimize both its latency and fragmentation by re-implmenting SLOB using segregated free list method and adding support for slab merging. it looks like lightweight SLUB but more compact than SLUB.
One notable difference is after this patch SLOB uses kmalloc_caches like SL[AU]B.
Below is performance impacts of this patch.
Memory usage was measured on 32 bit + tinyconfig + slab merging.
Before:
MemTotal: 29668 kB
MemFree: 19364 kB
MemAvailable: 18396 kBSlab: 668 kB
After:
MemTotal: 29668 kB
MemFree: 19420 kB
MemAvailable: 18452 kBSlab: 716 kB
This patch adds about 48 kB after boot.
hackbench was measured on 64 bit typical buildroot configuration. After this patch it's 9~10x faster than before.
Before:
memory usage:
after boot:
Slab: 7908 kB
after hackbench:
Slab: 8544 kB
Time: 189.947
Performance counter stats for 'hackbench -g 4 -l 10000':
379413.20 msec cpu-clock # 1.997 CPUs utilized
8818226 context-switches # 23.242 K/sec
375186 cpu-migrations # 988.859 /sec
3954 page-faults # 10.421 /sec
269923095290 cycles # 0.711 GHz
212341582012 instructions # 0.79 insn per cycle
2361087153 branch-misses
58222839688 cache-references # 153.455 M/sec
6786521959 cache-misses # 11.656 % of all cache refs
190.002062273 seconds time elapsed
3.486150000 seconds user
375.599495000 seconds sysAfter:
memory usage:
after boot:
Slab: 7560 kB
after hackbench:
Slab: 7836 kB
hackbench:
Time: 20.780
Performance counter stats for 'hackbench -g 4 -l 10000':
41509.79 msec cpu-clock # 1.996 CPUs utilized
630032 context-switches # 15.178 K/sec
8287 cpu-migrations # 199.640 /sec
4036 page-faults # 97.230 /sec
57477161020 cycles # 1.385 GHz
62775453932 instructions # 1.09 insn per cycle
164902523 branch-misses
22559952993 cache-references # 543.485 M/sec
832404011 cache-misses # 3.690 % of all cache refs
20.791893590 seconds time elapsed
1.423282000 seconds user
40.072449000 seconds sys--- include/linux/mm_types.h | 4 +- include/linux/slab.h | 8 +- mm/slab.h | 24 +- mm/slab_common.c | 2 - mm/slob.c | 608 ++++++++++++++++----------------------- 5 files changed, 263 insertions(+), 383 deletions(-)
include/linux/mm_types.h +2 -2
@@ -131,7 +131,7 @@ struct page {#endif }; }; -struct kmem_cache *slab_cache;/* not slob */ +struct kmem_cache *slab_cache;/* Double-word boundary */ void *freelist;/* first free object */ union {
@@ -209,7 +209,7 @@ struct page {unsigned int page_type;unsigned int active;/* SLAB */ -int units;/* SLOB */ +int units;/* zsmalloc */ };/* Usage count. *DO NOT USE DIRECTLY*. See page_ref.h */
include/linux/slab.h +2 -6
@@ -327,7 +327,6 @@ enum kmalloc_cache_type { NR_KMALLOC_TYPES }; -#ifndef CONFIG_SLOB extern struct kmem_cache * kmalloc_caches[NR_KMALLOC_TYPES ][KMALLOC_SHIFT_HIGH +1 ];
@@ -423,7 +422,6 @@ static __always_inline unsigned int __kmalloc_index(size_t size,return -1 ; }#define kmalloc_index (s) __kmalloc_index(s, true) -#endif /* !CONFIG_SLOB */ void *__kmalloc (size_t size,gfp_t flags) __assume_kmalloc_alignment __malloc;void *kmem_cache_alloc (struct kmem_cache *,gfp_t flags) __assume_slab_alignment __malloc;
@@ -577,12 +575,11 @@ static __always_inline void *kmalloc_large(size_t size, gfp_t flags) static __always_inline void *kmalloc(size_t size, gfp_t flags) {if (__builtin_constant_p (size)) { -#ifndef CONFIG_SLOB unsigned int index; -#endif +if (size >KMALLOC_MAX_CACHE_SIZE )return kmalloc_large (size, flags); -#ifndef CONFIG_SLOB + index =kmalloc_index (size);if (!index)
@@ -591,7 +588,6 @@ static __always_inline void *kmalloc(size_t size, gfp_t flags)return kmem_cache_alloc_trace ( kmalloc_caches[kmalloc_type (flags)][index], flags, size); -#endif }return __kmalloc (size, flags); }
mm/slab.h +8 -16
@@ -6,6 +6,13 @@*/ #ifdef CONFIG_SLOB + +struct slob { +size_t size; +spinlock_t lock; +struct list_head head[MAX_NUMNODES ]; +}; +/* * Common fields provided in kmem_cache by all slab allocators * This struct is either used directly by the allocator (SLOB)
@@ -28,6 +35,7 @@ struct kmem_cache {int refcount;/* Use counter */ void (*ctor)(void *);/* Called on object slot creation */ struct list_head list;/* List of all slab caches on the system */ + struct slob slob; };#endif /* CONFIG_SLOB */
@@ -80,14 +88,12 @@ extern const struct kmalloc_info_struct {unsigned int size; } kmalloc_info[]; -#ifndef CONFIG_SLOB /* Kmalloc array related functions */ void setup_kmalloc_cache_index_table (void );void create_kmalloc_caches (slab_flags_t );/* Find the kmalloc slab corresponding for a certain size */ struct kmem_cache *kmalloc_slab (size_t ,gfp_t ); -#endif gfp_t kmalloc_fix_flags (gfp_t flags);
@@ -104,26 +110,12 @@ extern void create_boot_cache(struct kmem_cache *, const char *name,int slab_unmergeable (struct kmem_cache *s);struct kmem_cache *find_mergeable (unsigned size,unsigned align,slab_flags_t flags,const char *name,void (*ctor)(void *)); -#ifndef CONFIG_SLOB struct kmem_cache *__kmem_cache_alias (const char *name,unsigned int size,unsigned int align,slab_flags_t flags,void (*ctor)(void *));slab_flags_t kmem_cache_flags (unsigned int object_size,slab_flags_t flags,const char *name); -#else -static inline struct kmem_cache * -__kmem_cache_alias (const char *name,unsigned int size,unsigned int align, -slab_flags_t flags,void (*ctor)(void *)) -{return NULL ; } - -static inline slab_flags_t kmem_cache_flags (unsigned int object_size, -slab_flags_t flags,const char *name) -{ -return flags; -} -#endif -/* Legal flag mask for kmem_cache_create(), for various configurations */ #define SLAB_CORE_FLAGS (SLAB_HWCACHE_ALIGN | SLAB_CACHE_DMA | \
mm/slab_common.c +0 -2
@@ -636,7 +636,6 @@ void kmem_dump_obj(void *object)EXPORT_SYMBOL_GPL (kmem_dump_obj);#endif -#ifndef CONFIG_SLOB /* Create a cache during boot when no slab services are available yet */ void __init create_boot_cache(struct kmem_cache *s, const char *name, unsigned int size, slab_flags_t flags,
@@ -926,7 +925,6 @@ void __init create_kmalloc_caches(slab_flags_t flags) }#endif } -#endif /* !CONFIG_SLOB */ gfp_t kmalloc_fix_flags (gfp_t flags) {
mm/slob.c +251 -357
820 lines not on this page · raw message
Signature · 1 line
2.27.0
Quoted 11 lines · Hyeonggon Yoo
Hello linux-mm, I rewrote SLOB using segregated free list, to understand SLOB and SLUB more. It uses more kilobytes of memory (48kB on 32bit tinyconfig) and became 9~10x faster.
But after rewriting, I thought I need to discuss what SLOB is for. According to Matthew, SLOB is for small machines whose memory is 1~16 MB.
I wonder adding 48kB on SLOB memory for speed/lower latency is worth or harmful.
Quoted 6 lines
So.. questions in my head now:
- Who is users of SLOB?
- Is it harmful to add some kilobytes of memory into SLOB?
- Is it really possible to run linux under 10MB of RAM? (I failed with tinyconfig.)
- What is the boundary to make decision between SLOB and SLUB?
There certainly are people running Linux on such small machines. Nicolas Pitre talked about what it takes to do it in a series of four articles:
https://lwn.net/Articles/746780/
It's been a couple of decades since I was last paid to work on such a system. Dave Taht (cc'd) may be able to help you find people who care about these use cases. And maybe they can tell you whether 9-10x faster for 48kB extra memory consumption is a good tradeoff for them.
kernel test robot
build bot[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in https://git-scm.com/docs/git-format-patch]
Hi Hyeonggon,
[FYI, it's a private test report for your RFC patch.]
[auto build test ERROR on linux/master]
[also build test ERROR on linus/master v5.15-rc6 next-20211020] [cannot apply to hnaz-mm/master]
[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]
url: https://github.com/0day-ci/linux/commits/Hyeonggon-Yoo/mm-slob-Rewrite-SLOB-using-segregated-free-list/20211020-215705 base: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git ec681c53f8d2d0ee362ff67f5b98dd8263c15002 config: i386-randconfig-r003-20211019 (attached as .config) compiler: clang version 14.0.0 (https://github.com/llvm/llvm-project 9660563950aaed54020bfdf0be07e7096a9553e4)
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# https://github.com/0day-ci/linux/commit/e2ba7ee42ed802d48dd0ea4ff0fe07096d115c11
git remote add linux-review https://github.com/0day-ci/linux
git fetch --no-tags linux-review Hyeonggon-Yoo/mm-slob-Rewrite-SLOB-using-segregated-free-list/20211020-215705 git checkout e2ba7ee42ed802d48dd0ea4ff0fe07096d115c11
# save the attached .config to linux build tree
mkdir build_dir
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=i386 SHELL=/bin/bash
If you fix the issue, kindly add following tag as appropriate
All errors (new ones prefixed by >>):
>> mm/slob.c:603:16: error: use of undeclared identifier '_RET_IP'; did you mean 'NET_IPX'?
trace_kmalloc(_RET_IP, ret, size, s->size, gfp);
^~~~~~~
NET_IPX
include/uapi/linux/sysctl.h:210:2: note: 'NET_IPX' declared here
NET_IPX=6,
^
>> mm/slob.c:604:12: error: expected ';' after return statement
return ret
^
;2 errors generated.
vim +603 mm/slob.c
597
598 #ifdef CONFIG_TRACING
599 void *kmem_cache_alloc_trace(struct kmem_cache *s, gfp_t gfp, size_t size)
600 {
601 void *ret = slob_alloc_node(s, gfp, NUMA_NO_NODE);
602
> 603 trace_kmalloc(_RET_IP, ret, size, s->size, gfp); > 604 return ret
605 }
606
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org
Quoted 27 lines · Hyeonggon Yoo
Hello linux-mm, I rewrote SLOB using segregated free list, to understand SLOB and SLUB more. It uses more kilobytes of memory (48kB on 32bit tinyconfig) and became 9~10x faster.
But after rewriting, I thought I need to discuss what SLOB is for. According to Matthew, SLOB is for small machines whose memory is 1~16 MB.
I wonder adding 48kB on SLOB memory for speed/lower latency is worth or harmful.
So.. questions in my head now:
- Who is users of SLOB?
- Is it harmful to add some kilobytes of memory into SLOB?
- Is it really possible to run linux under 10MB of RAM? (I failed with tinyconfig.)
- What is the boundary to make decision between SLOB and SLUB?Anyway, below is my work.
Any comments/opinions will be appreciated!SLOB uses sequential fit method. the advantages of this method is the fact that it is simple and does not have complex metadata.
But big downside of sequential fit method is its high latency in allocation/deallocation and fast fragmentation.
Quoted 8 lines
High latency comes from iterating pages and also iterating objects in the page to find suitable free object. And fragmentation easily happens because objects of difference size is allocated in same page.
This patch tries to minimize both its latency and fragmentation by re-implmenting SLOB using segregated free list method and adding support for slab merging. it looks like lightweight SLUB but more compact than SLUB.
My immediate reaction is that we probably don't want to turn SLOB into lightweight SLUB. SLOB choses the tradeoff of low memory usage over speed and shifting it towards more speed kinda defeats this purpose. Also it's a major rewrite, so without a very clear motivation there will be resistance to that.
SLUB itself could be probably tuned to less memory overhead if needed. Most of the debug options effectively disable percpu slabs, we could add a mode that disables them without the rest of the debugging overhead. Allocation order can be lowered (although some object sizes might benefit from less fragmentation with a higher order).
Quoted 48 lines
One notable difference is after this patch SLOB uses
kmalloc_cacheslike SL[AU]B.Below is performance impacts of this patch.
Memory usage was measured on 32 bit + tinyconfig + slab merging.
Before:
MemTotal: 29668 kB MemFree: 19364 kB MemAvailable: 18396 kBSlab: 668 kB
After:
MemTotal: 29668 kB MemFree: 19420 kB MemAvailable: 18452 kBSlab: 716 kB
This patch adds about 48 kB after boot.
hackbench was measured on 64 bit typical buildroot configuration. After this patch it's 9~10x faster than before.
Before:
memory usage: after boot: Slab: 7908 kB after hackbench: Slab: 8544 kB Time: 189.947 Performance counter stats for 'hackbench -g 4 -l 10000': 379413.20 msec cpu-clock # 1.997 CPUs utilized 8818226 context-switches # 23.242 K/sec 375186 cpu-migrations # 988.859 /sec 3954 page-faults # 10.421 /sec 269923095290 cycles # 0.711 GHz 212341582012 instructions # 0.79 insn per cycle 2361087153 branch-misses 58222839688 cache-references # 153.455 M/sec 6786521959 cache-misses # 11.656 % of all cache refs 190.002062273 seconds time elapsed 3.486150000 seconds user 375.599495000 seconds sys
Quoted 6 lines
After:
memory usage:
after boot:
Slab: 7560 kB
after hackbench:
Slab: 7836 kB
Interesting that the memory usage in this test is actually lower with your patch.
Quoted 17 lines
hackbench:
Time: 20.780 Performance counter stats for 'hackbench -g 4 -l 10000': 41509.79 msec cpu-clock # 1.996 CPUs utilized 630032 context-switches # 15.178 K/sec 8287 cpu-migrations # 199.640 /sec 4036 page-faults # 97.230 /sec 57477161020 cycles # 1.385 GHz 62775453932 instructions # 1.09 insn per cycle 164902523 branch-misses 22559952993 cache-references # 543.485 M/sec 832404011 cache-misses # 3.690 % of all cache refs 20.791893590 seconds time elapsed 1.423282000 seconds user 40.072449000 seconds sys
That's significant, but also hackbench is kind of worst case test, so in practice the benefit won't be that prominent.
Quoted 2 lines
Signed-off-by Hyeonggon Yoo <[email protected]>---
Hmm.. I think I need to clarify my intention.
I'm not saying this should be merged or we should put effort to make SLOB into lightweight SLOB. I just rewrote it just for fun. I wanted to know how small a segregated free list allocator can be.
And when I rewrote it, I wondered who is users of SLOB and where SLOB should be used.
I think SLOB was useful when there was only SLAB and there was no SLUB, but I wonder where SLOB should be used now.
When I compared SLOB and SLUB without cpu partials, That made 300kB of difference in Slab memory.
Then Is SLOB used where 300kB of difference is so important? But I think we need at least 16MB of RAM to run linux.
So I'm not saying we need to turn SLOB into lightweight SLUB, but wanted to talk about the questions:
Quoted 13 lines
Quoted 13 lines
But after rewriting, I thought I need to discuss what SLOB is for. According to Matthew, SLOB is for small machines whose memory is 1~16 MB.
I wonder adding 48kB on SLOB memory for speed/lower latency is worth or harmful.
So.. questions in my head now:
- Who is users of SLOB?
- Is it harmful to add some kilobytes of memory into SLOB?
- Is it really possible to run linux under 10MB of RAM? (I failed with tinyconfig.)
- What is the boundary to make decision between SLOB and SLUB?
Quoted 37 lines · Vlastimil Babka
Quoted 27 lines · Hyeonggon Yoo
Hello linux-mm, I rewrote SLOB using segregated free list, to understand SLOB and SLUB more. It uses more kilobytes of memory (48kB on 32bit tinyconfig) and became 9~10x faster.
But after rewriting, I thought I need to discuss what SLOB is for. According to Matthew, SLOB is for small machines whose memory is 1~16 MB.
I wonder adding 48kB on SLOB memory for speed/lower latency is worth or harmful.
So.. questions in my head now:
- Who is users of SLOB?
- Is it harmful to add some kilobytes of memory into SLOB?
- Is it really possible to run linux under 10MB of RAM? (I failed with tinyconfig.)
- What is the boundary to make decision between SLOB and SLUB?Anyway, below is my work.
Any comments/opinions will be appreciated!SLOB uses sequential fit method. the advantages of this method is the fact that it is simple and does not have complex metadata.
But big downside of sequential fit method is its high latency in allocation/deallocation and fast fragmentation.
Quoted 8 lines
High latency comes from iterating pages and also iterating objects in the page to find suitable free object. And fragmentation easily happens because objects of difference size is allocated in same page.
This patch tries to minimize both its latency and fragmentation by re-implmenting SLOB using segregated free list method and adding support for slab merging. it looks like lightweight SLUB but more compact than SLUB.
Quoted 6 lines
My immediate reaction is that we probably don't want to turn SLOB into lightweight SLUB. SLOB choses the tradeoff of low memory usage over speed and shifting it towards more speed kinda defeats this purpose. Also it's a major rewrite, so without a very clear motivation there will be resistance to that.
Yes, I agree that SLOB is for memory efficiency, not a performance.
Quoted 2 lines · That's why I
Quoted 2 lines
I wonder adding 48kB on SLOB memory for speed/lower latency is worth or harmful.
But on the contrary, I wonder when SLOB is useful than SLUB. is it for really tiny linux systems that has under 1M of RAM? But can linux be that small?
Quoted 5 lines
SLUB itself could be probably tuned to less memory overhead if needed. Most of the debug options effectively disable percpu slabs, we could add a mode that disables them without the rest of the debugging overhead. Allocation order can be lowered (although some object sizes might benefit from less fragmentation with a higher order).
Yes, that's what I was curious about. As SLUB is not that big, I wonder where SLOB is useful.
Quoted 55 lines
Quoted 48 lines
One notable difference is after this patch SLOB uses
kmalloc_cacheslike SL[AU]B.Below is performance impacts of this patch.
Memory usage was measured on 32 bit + tinyconfig + slab merging.
Before:
MemTotal: 29668 kB MemFree: 19364 kB MemAvailable: 18396 kBSlab: 668 kB
After:
MemTotal: 29668 kB MemFree: 19420 kB MemAvailable: 18452 kBSlab: 716 kB
This patch adds about 48 kB after boot.
hackbench was measured on 64 bit typical buildroot configuration. After this patch it's 9~10x faster than before.
Before:
memory usage: after boot: Slab: 7908 kB after hackbench: Slab: 8544 kB Time: 189.947 Performance counter stats for 'hackbench -g 4 -l 10000': 379413.20 msec cpu-clock # 1.997 CPUs utilized 8818226 context-switches # 23.242 K/sec 375186 cpu-migrations # 988.859 /sec 3954 page-faults # 10.421 /sec 269923095290 cycles # 0.711 GHz 212341582012 instructions # 0.79 insn per cycle 2361087153 branch-misses 58222839688 cache-references # 153.455 M/sec 6786521959 cache-misses # 11.656 % of all cache refs 190.002062273 seconds time elapsed 3.486150000 seconds user 375.599495000 seconds sysQuoted 6 lines
After:
memory usage:
after boot:
Slab: 7560 kB
after hackbench:
Slab: 7836 kB
Quoted 2 lines
Interesting that the memory usage in this test is actually lower with your patch.
I didn't mention that because if we have enough memory, I think we have no reason to use SLOB. (why not use SLUB?) I thought memory usage on small machine is important.
Quoted 25 lines
Quoted 18 lines
hackbench:
Time: 20.780 Performance counter stats for 'hackbench -g 4 -l 10000': 41509.79 msec cpu-clock # 1.996 CPUs utilized 630032 context-switches # 15.178 K/sec 8287 cpu-migrations # 199.640 /sec 4036 page-faults # 97.230 /sec 57477161020 cycles # 1.385 GHz 62775453932 instructions # 1.09 insn per cycle 164902523 branch-misses 22559952993 cache-references # 543.485 M/sec 832404011 cache-misses # 3.690 % of all cache refs 20.791893590 seconds time elapsed 1.423282000 seconds user 40.072449000 seconds sysThat's significant, but also hackbench is kind of worst case test, so in practice the benefit won't be that prominent.
Quoted 2 lines
Signed-off-by Hyeonggon Yoo <[email protected]>---
Quoted 3 lines · Hyeonggon Yoo
But on the contrary, I wonder when SLOB is useful than SLUB. is it for really tiny linux systems that has under 1M of RAM? But can linux be that small?
SLOB I think is mainly a nice intro into how slab allocators work. It is a simple architecture and the code is to read and therefore easily understood. I heard of some use cases from others but I have only ever been able to run a kernel boot in KVM with SLOB.