Skip to contentSkip to conversation

mm, slob: Rewrite SLOB using segregated free list

RFC PATCH In review Hyeonggon Yoo 5 participants 6 messages Oct 20, 2021 – Oct 25, 2021

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

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 kB

Slab: 668 kB

After:

    MemTotal:          29668 kB
    MemFree:           19420 kB
    MemAvailable:      18452 kB

Slab: 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

After:
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
index 7f8ee09c711f..465bb00327a5 100644
@@ -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
index 083f3ce550bc..cca90f289cc3 100644
@@ -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
index 58c01a34e5b8..19c02568b6fb 100644
@@ -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
index ec2bb0beed75..09f9d18ce091 100644
@@ -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
#1 lore raw
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.

#2 lore raw
In reply to Hyeonggon Yoo
[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

#3 lore raw
In reply to Hyeonggon Yoo
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_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 kB

Slab: 668 kB

After:

    MemTotal:          29668 kB
    MemFree:           19420 kB
    MemAvailable:      18452 kB

Slab: 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

---

#4 lore raw

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_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 kB

Slab: 668 kB

After:

    MemTotal:          29668 kB
    MemFree:           19420 kB
    MemAvailable:      18452 kB

Slab: 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

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

---

#5 lore raw
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.