Re: [PATCH] slab.c cleanup

Re: [PATCH] slab.c cleanup

[Arnd Bergmann]

Brian Gerst wrote:

> - Don't create caches that are not multiples of L1_CACHE_BYTES.

This sounds a bit drastic to me considering that the vast majority
of kmalloc allocations that I see are either in the <32 byte or
in the 64..128 byte range. Enlarging the minimum size to 256
byte would immediately waste over 1MB on my machine...

        Arnd <><

Re: [PATCH] slab.c cleanup

[Arnd Bergmann]

Brian Gerst wrote:

> Manfred Spraul wrote:
>>
>> No, the patch is a bad thing: It means that everyone who does 
>> kmalloc(32,) now allocates 128 bytes, i.e. 3/4 wasted. IMHO not acceptable.
> 
> Perhaps, but it currently is already allocating 128 bytes for smaller 
> caches, because the cache is created with SLAB_HWCACHE_ALIGN.  So we 
> ended up with redundantly sized caches.

Doesn't this code in kmem_cache_create() handle this already?

>        if (flags & SLAB_HWCACHE_ALIGN) {
>                /* Need to adjust size so that objs are cache aligned. */
>               /* Small obj size, can get at least two per cache line. */
>                while (size < align/2)
>                        align /= 2;
>                size = (size+align-1)&(~(align-1));
>        }

        Arnd <><

Re: [PATCH] slab.c cleanup

[Manfred Spraul]

[-- Attachment #1: Type: text/plain, Size: 851 bytes --]

Anton wrote:

>> - Don't create caches that are not multiples of L1_CACHE_BYTES.
>
>Nice idea, I often see the list walk (of the cache sizes) in kmalloc in kernel
>profiles. eg a bunch of kmalloc(2k) for network drivers.
>
>Since we have a 128byte cacheline on ppc64 this patch should reduce that.
>  
>
No, the patch is a bad thing: It means that everyone who does 
kmalloc(32,) now allocates 128 bytes, i.e. 3/4 wasted. IMHO not acceptable.

I agree that the list walk in kmalloc is a problem - but the right 
solution is a quicker lookup.
Perhaps something like the attached patch.
For networking: I bet that virtually all allocations have the same size 
- what about calling kmem_find_general_cachep, and caching the last 
request/result? Then the next calls can allocate directly from the 
appropriate cache, without any lookup.

--
    Manfred


[-- Attachment #2: patch-fast-kmalloc --]
[-- Type: text/plain, Size: 1223 bytes --]

--- 2.5/mm/slab.c	Sat Oct 26 21:13:33 2002
+++ build-2.5/mm/slab.c	Sun Oct 27 13:48:06 2002
@@ -424,6 +430,7 @@
 	CN("size-131072")
 }; 
 #undef CN
+static struct cache_sizes *malloc_hints[sizeof(size_t)*8];
 
 struct arraycache_init initarray_cache __initdata = { { 0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
 struct arraycache_init initarray_generic __initdata = { { 0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
@@ -587,6 +594,7 @@
 void __init kmem_cache_init(void)
 {
 	size_t left_over;
+	int i;
 
 	init_MUTEX(&cache_chain_sem);
 	INIT_LIST_HEAD(&cache_chain);
@@ -604,6 +612,18 @@
 	 * that initializes ac_data for all new cpus
 	 */
 	register_cpu_notifier(&cpucache_notifier);
+
+	for (i=0;i<sizeof(size_t)*8;i++) {
+		struct cache_sizes *csizep = malloc_sizes;
+		int size = (1<<i)+1;
+
+		for ( ; csizep->cs_size; csizep++) {
+			if (size > csizep->cs_size)
+				continue;
+			break;
+		}
+		malloc_hints[i] = csizep;
+	}
 }
 
 
@@ -1796,7 +1816,11 @@
  */
 void * kmalloc (size_t size, int flags)
 {
-	struct cache_sizes *csizep = malloc_sizes;
+	struct cache_sizes *csizep;
+
+	if (unlikely(size < 2))
+		size = 2;
+	csizep = malloc_hints[fls((size-1))-1];
 
 	for (; csizep->cs_size; csizep++) {
 		if (size > csizep->cs_size)

Re: [PATCH] slab.c cleanup

[Brian Gerst]

Manfred Spraul wrote:
> Anton wrote:
> 
>>> - Don't create caches that are not multiples of L1_CACHE_BYTES.
>>
>>
>> Nice idea, I often see the list walk (of the cache sizes) in kmalloc 
>> in kernel
>> profiles. eg a bunch of kmalloc(2k) for network drivers.
>>
>> Since we have a 128byte cacheline on ppc64 this patch should reduce that.
>>  
>>
> No, the patch is a bad thing: It means that everyone who does 
> kmalloc(32,) now allocates 128 bytes, i.e. 3/4 wasted. IMHO not acceptable.

Perhaps, but it currently is already allocating 128 bytes for smaller 
caches, because the cache is created with SLAB_HWCACHE_ALIGN.  So we 
ended up with redundantly sized caches.

--
				Brian Gerst

Re: [PATCH] slab.c cleanup

[Manfred Spraul]

Brian Gerst wrote:

>
> Perhaps, but it currently is already allocating 128 bytes for smaller 
> caches, because the cache is created with SLAB_HWCACHE_ALIGN.  So we 
> ended up with redundantly sized caches.
>

linux/mm/slab.c:

>	if (flags & SLAB_HWCACHE_ALIGN) {
>		/* Need to adjust size so that objs are cache aligned. */
>		/* Small obj size, can get at least two per cache line. */
>		while (size < align/2)
>			align /= 2;
>		size = (size+align-1)&(~(align-1));
>	}
>  
>
HWALIGN is just a hint, the implementation ignores it if it results in 
unreasonable wasting of memory.

--
    Manfred

Re: [PATCH] slab.c cleanup

[Brian Gerst]

Manfred Spraul wrote:
> Brian Gerst wrote:
> 
>>
>> Perhaps, but it currently is already allocating 128 bytes for smaller 
>> caches, because the cache is created with SLAB_HWCACHE_ALIGN.  So we 
>> ended up with redundantly sized caches.
>>
> 
> linux/mm/slab.c:
> 
>>     if (flags & SLAB_HWCACHE_ALIGN) {
>>         /* Need to adjust size so that objs are cache aligned. */
>>         /* Small obj size, can get at least two per cache line. */
>>         while (size < align/2)
>>             align /= 2;
>>         size = (size+align-1)&(~(align-1));
>>     }
>>  
>>
> HWALIGN is just a hint, the implementation ignores it if it results in 
> unreasonable wasting of memory.

I think I see what was causing be to believe it was always rounding up 
to the cache size.  The while test should be while (size <= align/2). 
On my machine (athlon, 64 byte cache), the size-32 cache was rounded up 
to 64 bytes because of this.

size-128            1416   1470    128   49   49    1 :  248  124
size-64              351    413     64    7    7    1 :  248  124
size-32              649    649     64   11   11    1 :  248  124
                                    ^^^^

--
				Brian Gerst

[PATCH] slab.c cleanup

[Brian Gerst]

[-- Attachment #1: Type: text/plain, Size: 201 bytes --]

- Reduce code duplication by putting the kmalloc cache sizes into a 
header file.
- Don't create caches that are not multiples of L1_CACHE_BYTES.
- Tidy up kmem_cache_sizes_init().

--
				Brian Gerst

[-- Attachment #2: kmalloc_sizes-1 --]
[-- Type: text/plain, Size: 5453 bytes --]

diff -urN linux-2.5.65-bk5/include/linux/kmalloc_sizes.h linux/include/linux/kmalloc_sizes.h
--- linux-2.5.65-bk5/include/linux/kmalloc_sizes.h	1969-12-31 19:00:00.000000000 -0500
+++ linux/include/linux/kmalloc_sizes.h	2003-03-23 10:39:23.000000000 -0500
@@ -0,0 +1,37 @@
+#if !(32 % L1_CACHE_BYTES) && (PAGE_SIZE == 4096)
+	CACHE(32)
+#endif
+#if !(64 % L1_CACHE_BYTES)
+	CACHE(64)
+#endif
+#if !(96 % L1_CACHE_BYTES)
+	CACHE(96)
+#endif
+#if !(128 % L1_CACHE_BYTES)
+	CACHE(128)
+#endif
+#if !(192 % L1_CACHE_BYTES)
+	CACHE(192)
+#endif
+	CACHE(256)
+	CACHE(512)
+	CACHE(1024)
+	CACHE(2048)
+	CACHE(4096)
+	CACHE(8192)
+	CACHE(16384)
+	CACHE(32768)
+	CACHE(65536)
+	CACHE(131072)
+#ifndef CONFIG_MMU
+	CACHE(262144)
+	CACHE(524288)
+	CACHE(1048576)
+#ifdef CONFIG_LARGE_ALLOCS
+	CACHE(2097152)
+	CACHE(4194304)
+	CACHE(8388608)
+	CACHE(16777216)
+	CACHE(33554432)
+#endif /* CONFIG_LARGE_ALLOCS */
+#endif /* CONFIG_MMU */
diff -urN linux-2.5.65-bk5/mm/slab.c linux/mm/slab.c
--- linux-2.5.65-bk5/mm/slab.c	2003-03-23 09:35:46.000000000 -0500
+++ linux/mm/slab.c	2003-03-23 13:03:12.000000000 -0500
@@ -375,91 +375,26 @@
 #define	SET_PAGE_SLAB(pg,x)   ((pg)->list.prev = (struct list_head *)(x))
 #define	GET_PAGE_SLAB(pg)     ((struct slab *)(pg)->list.prev)
 
-/* Size description struct for general caches. */
-struct cache_sizes {
+/* These are the default caches for kmalloc. Custom caches can have other sizes. */
+static struct cache_sizes {
 	size_t		 cs_size;
 	kmem_cache_t	*cs_cachep;
 	kmem_cache_t	*cs_dmacachep;
+} malloc_sizes[] = {
+#define CACHE(x) { .cs_size = (x) },
+#include <linux/kmalloc_sizes.h>
+#undef CACHE
 };
 
-/* These are the default caches for kmalloc. Custom caches can have other sizes. */
-static struct cache_sizes malloc_sizes[] = {
-#if PAGE_SIZE == 4096
-	{    32,	NULL, NULL},
-#endif
-	{    64,	NULL, NULL},
-#if L1_CACHE_BYTES < 64
-	{    96,	NULL, NULL},
-#endif
-	{   128,	NULL, NULL},
-#if L1_CACHE_BYTES < 128
-	{   192,	NULL, NULL},
-#endif
-	{   256,	NULL, NULL},
-	{   512,	NULL, NULL},
-	{  1024,	NULL, NULL},
-	{  2048,	NULL, NULL},
-	{  4096,	NULL, NULL},
-	{  8192,	NULL, NULL},
-	{ 16384,	NULL, NULL},
-	{ 32768,	NULL, NULL},
-	{ 65536,	NULL, NULL},
-	{131072,	NULL, NULL},
-#ifndef CONFIG_MMU
-	{262144,	NULL, NULL},
-	{524288,	NULL, NULL},
-	{1048576,	NULL, NULL},
-#ifdef CONFIG_LARGE_ALLOCS
-	{2097152,	NULL, NULL},
-	{4194304,	NULL, NULL},
-	{8388608,	NULL, NULL},
-	{16777216,	NULL, NULL},
-	{33554432,	NULL, NULL},
-#endif /* CONFIG_LARGE_ALLOCS */
-#endif /* CONFIG_MMU */
-	{     0,	NULL, NULL}
-};
 /* Must match cache_sizes above. Out of line to keep cache footprint low. */
-#define CN(x) { x, x "(DMA)" }
 static struct { 
 	char *name; 
 	char *name_dma;
 } cache_names[] = { 
-#if PAGE_SIZE == 4096
-	CN("size-32"),
-#endif
-	CN("size-64"),
-#if L1_CACHE_BYTES < 64
-	CN("size-96"),
-#endif
-	CN("size-128"),
-#if L1_CACHE_BYTES < 128
-	CN("size-192"),
-#endif
-	CN("size-256"),
-	CN("size-512"),
-	CN("size-1024"),
-	CN("size-2048"),
-	CN("size-4096"),
-	CN("size-8192"),
-	CN("size-16384"),
-	CN("size-32768"),
-	CN("size-65536"),
-	CN("size-131072"),
-#ifndef CONFIG_MMU
-	CN("size-262144"),
-	CN("size-524288"),
-	CN("size-1048576"),
-#ifdef CONFIG_LARGE_ALLOCS
-	CN("size-2097152"),
-	CN("size-4194304"),
-	CN("size-8388608"),
-	CN("size-16777216"),
-	CN("size-33554432"),
-#endif /* CONFIG_LARGE_ALLOCS */
-#endif /* CONFIG_MMU */
+#define CACHE(x) { .name = "size-" #x, .name_dma = "size-" #x "(DMA)" },
+#include <linux/kmalloc_sizes.h>
+#undef CACHE
 }; 
-#undef CN
 
 struct arraycache_init initarray_cache __initdata = { { 0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
 struct arraycache_init initarray_generic __initdata = { { 0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
@@ -660,39 +595,39 @@
  */
 void __init kmem_cache_sizes_init(void)
 {
-	struct cache_sizes *sizes = malloc_sizes;
+	int i;
 	/*
 	 * Fragmentation resistance on low memory - only use bigger
 	 * page orders on machines with more than 32MB of memory.
 	 */
 	if (num_physpages > (32 << 20) >> PAGE_SHIFT)
 		slab_break_gfp_order = BREAK_GFP_ORDER_HI;
-	do {
+
+	for (i = 0; i < ARRAY_SIZE(malloc_sizes); i++) {
+		struct cache_sizes *sizes = malloc_sizes + i;
 		/* For performance, all the general caches are L1 aligned.
 		 * This should be particularly beneficial on SMP boxes, as it
 		 * eliminates "false sharing".
 		 * Note for systems short on memory removing the alignment will
 		 * allow tighter packing of the smaller caches. */
-		if (!(sizes->cs_cachep =
-			kmem_cache_create(cache_names[sizes-malloc_sizes].name, 
-					  sizes->cs_size,
-					0, SLAB_HWCACHE_ALIGN, NULL, NULL))) {
+		sizes->cs_cachep = kmem_cache_create(
+			cache_names[i].name, sizes->cs_size,
+			0, SLAB_HWCACHE_ALIGN, NULL, NULL);
+		if (!sizes->cs_cachep)
 			BUG();
-		}
 
 		/* Inc off-slab bufctl limit until the ceiling is hit. */
 		if (!(OFF_SLAB(sizes->cs_cachep))) {
 			offslab_limit = sizes->cs_size-sizeof(struct slab);
 			offslab_limit /= sizeof(kmem_bufctl_t);
 		}
+
 		sizes->cs_dmacachep = kmem_cache_create(
-		    cache_names[sizes-malloc_sizes].name_dma, 
-			sizes->cs_size, 0,
-			SLAB_CACHE_DMA|SLAB_HWCACHE_ALIGN, NULL, NULL);
+			cache_names[i].name_dma, sizes->cs_size,
+			0, SLAB_CACHE_DMA|SLAB_HWCACHE_ALIGN, NULL, NULL);
 		if (!sizes->cs_dmacachep)
 			BUG();
-		sizes++;
-	} while (sizes->cs_size);
+	}
 	/*
 	 * The generic caches are running - time to kick out the
 	 * bootstrap cpucaches.

Re: [PATCH] slab.c cleanup

[Anton Blanchard]

> - Don't create caches that are not multiples of L1_CACHE_BYTES.

Nice idea, I often see the list walk (of the cache sizes) in kmalloc in kernel
profiles. eg a bunch of kmalloc(2k) for network drivers.

Since we have a 128byte cacheline on ppc64 this patch should reduce that.

Anton