[RFC,PATCH] optimize fixed size kmalloc calls

[RFC,PATCH] optimize fixed size kmalloc calls

[Manfred Spraul]

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

Hi,

kmalloc(constant,GFP_KERNEL) spends a singificant amount of time in the 
initial loop that finds the correct cache. For constant allocations, the 
correct cache can be indentified at compile time.

What do you think about the attached patch? It's not pretty, but it 
should work will all gcc versions. Any other ideas?
Just FYI: The function that forced me to use use switch/case instead of 
if is interrupts_open in fs/proc/proc_misc.c.

--
    Manfred

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

// $Header$
// Kernel Version:
//  VERSION = 2
//  PATCHLEVEL = 5
//  SUBLEVEL = 70
//  EXTRAVERSION = -mm4
--- 2.5/include/linux/slab.h	2003-06-08 23:32:03.000000000 +0200
+++ build-2.5/include/linux/slab.h	2003-06-08 23:30:41.000000000 +0200
@@ -62,7 +62,52 @@
 extern void kmem_cache_free(kmem_cache_t *, void *);
 extern unsigned int kmem_cache_size(kmem_cache_t *);
 
-extern void *kmalloc(size_t, int);
+/* Size description struct for general caches. */
+struct cache_sizes {
+	size_t		 cs_size;
+	kmem_cache_t	*cs_cachep;
+	kmem_cache_t	*cs_dmacachep;
+};
+extern struct cache_sizes malloc_sizes[];
+extern void *__kmalloc(size_t, int);
+
+/*
+ * gcc's brain is lossy: is forgets that a number is known at compile
+ * time after a few accesses and produces bogus code if a sequence of
+ * if clauses is used. This is avoided by using select.
+ */
+static inline void * kmalloc(size_t size, int flags)
+{
+	if (__builtin_constant_p(size)) {
+extern void __you_cannot_kmalloc_that_much(void);
+		unsigned int i,j;
+		j = 0;
+		switch(size) {
+		case 0 ...
+#define CACHE(x) \
+			(x): j++; \
+		case (x+1) ...
+#define LCACHE(x) \
+			(x): j++; break;
+#include "kmalloc_sizes.h"
+#undef CACHE
+#undef LCACHE
+		default:
+				__you_cannot_kmalloc_that_much();
+		}
+		i = 0;
+#define CACHE(x) \
+		i++;
+#include "kmalloc_sizes.h"
+#undef CACHE
+		return kmem_cache_alloc( (flags & GFP_DMA)?
+					malloc_sizes[i-j].cs_dmacachep
+					: malloc_sizes[i-j].cs_cachep,
+					flags);
+	}
+	return __kmalloc(size,flags);
+}
+
 extern void kfree(const void *);
 extern unsigned int ksize(const void *);
 
--- 2.5/mm/slab.c	2003-06-08 23:32:06.000000000 +0200
+++ build-2.5/mm/slab.c	2003-06-07 21:57:59.000000000 +0200
@@ -388,11 +388,7 @@
 #define	GET_PAGE_SLAB(pg)     ((struct slab *)(pg)->list.prev)
 
 /* 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[] = {
+struct cache_sizes malloc_sizes[] = {
 #define CACHE(x) { .cs_size = (x) },
 #include <linux/kmalloc_sizes.h>
 	{ 0, }
@@ -2039,7 +2035,7 @@
  * platforms.  For example, on i386, it means that the memory must come
  * from the first 16MB.
  */
-void * kmalloc (size_t size, int flags)
+void * __kmalloc (size_t size, int flags)
 {
 	struct cache_sizes *csizep = malloc_sizes;
 
--- 2.5/kernel/ksyms.c	2003-06-08 23:32:04.000000000 +0200
+++ build-2.5/kernel/ksyms.c	2003-06-07 21:56:55.000000000 +0200
@@ -95,7 +95,8 @@
 EXPORT_SYMBOL(kmem_cache_size);
 EXPORT_SYMBOL(set_shrinker);
 EXPORT_SYMBOL(remove_shrinker);
-EXPORT_SYMBOL(kmalloc);
+EXPORT_SYMBOL(malloc_sizes);
+EXPORT_SYMBOL(__kmalloc);
 EXPORT_SYMBOL(kfree);
 #ifdef CONFIG_SMP
 EXPORT_SYMBOL(__alloc_percpu);
--- 2.5/include/linux/kmalloc_sizes.h	2003-06-05 19:01:42.000000000 +0200
+++ build-2.5/include/linux/kmalloc_sizes.h	2003-06-08 23:23:11.000000000 +0200
@@ -1,3 +1,14 @@
+/*
+ * kmalloc cache sizes.
+ * - CACHE(x) is called for every entry except the last
+ * - for the last entry, LCACHE is called. LCACHE defaults
+ *   to CACHE.
+ */
+#ifndef LCACHE
+#define LCACHE(x)	CACHE(x)
+#define __LCACHE_DEFINED
+#endif
+
 #if (PAGE_SIZE == 4096)
 	CACHE(32)
 #endif
@@ -18,16 +29,25 @@
 	CACHE(16384)
 	CACHE(32768)
 	CACHE(65536)
+#ifdef CONFIG_MMU
+	LCACHE(131072)
+#else
 	CACHE(131072)
-#ifndef CONFIG_MMU
 	CACHE(262144)
 	CACHE(524288)
+#ifndef CONFIG_LARGE_ALLOCS
+	LCACHE(1048576)
+#else
 	CACHE(1048576)
-#ifdef CONFIG_LARGE_ALLOCS
 	CACHE(2097152)
 	CACHE(4194304)
 	CACHE(8388608)
 	CACHE(16777216)
-	CACHE(33554432)
+	LCACHE(33554432)
 #endif /* CONFIG_LARGE_ALLOCS */
 #endif /* CONFIG_MMU */
+
+#ifdef __LCACHE_DEFINED
+#undef __LCACHE_DEFINIED
+#undef LCACHE
+#endif

Re: [RFC,PATCH] optimize fixed size kmalloc calls

[Brian Gerst]

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

Manfred Spraul wrote:
> Hi,
> 
> kmalloc(constant,GFP_KERNEL) spends a singificant amount of time in the 
> initial loop that finds the correct cache. For constant allocations, the 
> correct cache can be indentified at compile time.
> 
> What do you think about the attached patch? It's not pretty, but it 
> should work will all gcc versions. Any other ideas?
> Just FYI: The function that forced me to use use switch/case instead of 
> if is interrupts_open in fs/proc/proc_misc.c.

How about this?  GCC 3.2.2 is able to optimize it away properly from the 
tests that I've run.

--
				Brian Gerst

[-- Attachment #2: kmalloc-const-1 --]
[-- Type: text/plain, Size: 2498 bytes --]

diff -ur linux-2.5.70-bk/include/linux/slab.h linux/include/linux/slab.h
--- linux-2.5.70-bk/include/linux/slab.h	2003-05-26 22:27:29.000000000 -0400
+++ linux/include/linux/slab.h	2003-06-09 17:24:40.000000000 -0400
@@ -62,7 +62,36 @@
 extern void kmem_cache_free(kmem_cache_t *, void *);
 extern unsigned int kmem_cache_size(kmem_cache_t *);
 
-extern void *kmalloc(size_t, int);
+/* Size description struct for general caches. */
+struct cache_sizes {
+	size_t		 cs_size;
+	kmem_cache_t	*cs_cachep;
+	kmem_cache_t	*cs_dmacachep;
+};
+extern struct cache_sizes malloc_sizes[];
+extern void *__kmalloc(size_t, int);
+
+static inline void *kmalloc(size_t size, int flags)
+{
+	if (__builtin_constant_p(size)) {
+		int i = 0;
+#define CACHE(x) \
+		if (size <= x) \
+			goto found; \
+		else \
+			i++;
+#include "kmalloc_sizes.h"
+#undef CACHE
+		extern void __you_cannot_kmalloc_that_much(void);
+		__you_cannot_kmalloc_that_much();
+found:
+		return kmem_cache_alloc((flags & GFP_DMA) ?
+			malloc_sizes[i].cs_dmacachep :
+			malloc_sizes[i].cs_cachep, flags);
+	}
+	return __kmalloc(size, flags);
+}
+
 extern void kfree(const void *);
 extern unsigned int ksize(const void *);
 
diff -ur linux-2.5.70-bk/kernel/ksyms.c linux/kernel/ksyms.c
--- linux-2.5.70-bk/kernel/ksyms.c	2003-06-08 23:50:12.000000000 -0400
+++ linux/kernel/ksyms.c	2003-06-09 16:44:27.000000000 -0400
@@ -95,7 +95,8 @@
 EXPORT_SYMBOL(kmem_cache_size);
 EXPORT_SYMBOL(set_shrinker);
 EXPORT_SYMBOL(remove_shrinker);
-EXPORT_SYMBOL(kmalloc);
+EXPORT_SYMBOL(malloc_sizes);
+EXPORT_SYMBOL(__kmalloc);
 EXPORT_SYMBOL(kfree);
 #ifdef CONFIG_SMP
 EXPORT_SYMBOL(__alloc_percpu);
diff -ur linux-2.5.70-bk/mm/slab.c linux/mm/slab.c
--- linux-2.5.70-bk/mm/slab.c	2003-06-08 23:50:13.000000000 -0400
+++ linux/mm/slab.c	2003-06-09 16:43:55.000000000 -0400
@@ -385,11 +385,7 @@
 #define	GET_PAGE_SLAB(pg)     ((struct slab *)(pg)->list.prev)
 
 /* 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[] = {
+struct cache_sizes malloc_sizes[] = {
 #define CACHE(x) { .cs_size = (x) },
 #include <linux/kmalloc_sizes.h>
 	{ 0, }
@@ -1967,7 +1963,7 @@
  * platforms.  For example, on i386, it means that the memory must come
  * from the first 16MB.
  */
-void * kmalloc (size_t size, int flags)
+void * __kmalloc (size_t size, int flags)
 {
 	struct cache_sizes *csizep = malloc_sizes;
 

Re: [RFC,PATCH] optimize fixed size kmalloc calls

[Andrew Morton]

Brian Gerst <bgerst@didntduck.org> wrote:
>
> > What do you think about the attached patch? It's not pretty, but it 
> > should work will all gcc versions. Any other ideas?
> > Just FYI: The function that forced me to use use switch/case instead of 
> > if is interrupts_open in fs/proc/proc_misc.c.
> 
> How about this?  GCC 3.2.2 is able to optimize it away properly from the 
> tests that I've run.

It doesn't compile with older gcc's - see the `extern' decl in the middle
of the function.

The compiler should have been given a way of disabling this.  It'd going to
bite again and again.


I'll fix it up.


void *kmalloc(size_t size, int flags)
{
        if (__builtin_constant_p(size)) {
                int i = 0;





# 1 "include/linux/kmalloc_sizes.h" 1

        if (size <= 32) goto found; else i++;

        if (size <= 64) goto found; else i++;



        if (size <= 128) goto found; else i++;



        if (size <= 256) goto found; else i++;
        if (size <= 512) goto found; else i++;
        if (size <= 1024) goto found; else i++;
        if (size <= 2048) goto found; else i++;
        if (size <= 4096) goto found; else i++;
        if (size <= 8192) goto found; else i++;
        if (size <= 16384) goto found; else i++;
        if (size <= 32768) goto found; else i++;
        if (size <= 65536) goto found; else i++;
        if (size <= 131072) goto found; else i++;
# 84 "include/linux/slab.h" 2

                extern void __you_cannot_kmalloc_that_much(void);
                __you_cannot_kmalloc_that_much();
found:
                return kmem_cache_alloc((flags & 0x01) ?
                        malloc_sizes[i].cs_dmacachep :
                        malloc_sizes[i].cs_cachep, flags);
        }
        return __kmalloc(size, flags);
}