Skip to contentSkip to conversation

optimize fixed size kmalloc calls

RFC PATCH In review Manfred Spraul 3 participants 3 messages Jun 9, 2003 – Jun 10, 2003

Subsystems (2)
Memory management Slab allocator
lore
Share & tools
lore

Manfred Spraul

author
#0 lore raw

RFC PATCH 1/1 optimize fixed size kmalloc calls

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

// $Header$
// Kernel Version:

//  VERSION = 2
//  PATCHLEVEL = 5
//  SUBLEVEL = 70
//  EXTRAVERSION = -mm4
include/linux/slab.h +46 -1
@@ -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 *);
mm/slab.c +2 -6
@@ -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;
kernel/ksyms.c +2 -1
@@ -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);
include/linux/kmalloc_sizes.h +23 -3
@@ -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
#1 lore raw
Quoted 6 lines · Manfred Spraul

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

include/linux/slab.h +30 -1
diff -ur linux-2.5.70-bk/include/linux/slab.h linux/include/linux/slab.h
@@ -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 *);
kernel/ksyms.c +2 -1
diff -ur linux-2.5.70-bk/kernel/ksyms.c linux/kernel/ksyms.c
@@ -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);
mm/slab.c +2 -6
diff -ur linux-2.5.70-bk/mm/slab.c linux/mm/slab.c
@@ -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;
#2 lore raw
Quoted 8 lines · Brian Gerst
Quoted 5 lines

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);
}