2003-06-09 19:25:19

by Manfred Spraul

[permalink] [raw]
Subject: [RFC,PATCH] optimize fixed size kmalloc calls

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


Attachments:
patch-kmalloc-fixed (3.68 kB)

2003-06-10 01:03:53

by Brian Gerst

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

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;


Attachments:
kmalloc-const-1 (2.44 kB)

2003-06-10 22:50:58

by Andrew Morton

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

Brian Gerst <[email protected]> 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);
}