faster kmalloc lookup

@@ -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)/2+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))];
 
 	for (; csizep->cs_size; csizep++) {
 		if (size > csizep->cs_size)

@@ -414,11 +414,22 @@
 	return word;
 }
 
-/*
+/**
  * fls: find last bit set.
+ * @x: The word to search
+ *
  */
 
-#define fls(x) generic_fls(x)
+static inline int fls(int x)
+{
+	int r;
+
+	__asm__("bsrl %1,%0\n\t"
+		"jnz 1f\n\t"
+		"movl $-1,%0\n"
+		"1:" : "=r" (r) : "g" (x));
+	return r+1;
+}
 
 #ifdef __KERNEL__
 

@@ -58,8 +58,91 @@
 extern void kmem_cache_free(kmem_cache_t *, void *);
 extern unsigned int kmem_cache_size(kmem_cache_t *);
 
-extern void *kmalloc(size_t, int);
 extern void kfree(const void *);
+extern void * __kmalloc (int i, size_t size, int flags);
+
+/**
+ * kmalloc - allocate memory
+ * @size: how many bytes of memory are required.
+ * @flags: the type of memory to allocate.
+ *
+ * kmalloc is the normal method of allocating memory
+ * in the kernel.
+ *
+ * The @flags argument may be one of:
+ *
+ * %GFP_USER - Allocate memory on behalf of user.  May sleep.
+ *
+ * %GFP_KERNEL - Allocate normal kernel ram.  May sleep.
+ *
+ * %GFP_ATOMIC - Allocation will not sleep.  Use inside interrupt handlers.
+ *
+ * Additionally, the %GFP_DMA flag may be set to indicate the memory
+ * must be suitable for DMA.  This can mean different things on different
+ * platforms.  For example, on i386, it means that the memory must come
+ * from the first 16MB.
+ */
+static inline void * kmalloc (size_t size, int flags)
+{
+	int i;
+
+	switch(size) {
+#if PAGE_SIZE == 4096
+	case 0 ... 32:
+		i = 0;
+		break;
+	case 33 ... 64:
+#else
+	case 0 ... 64:
+#endif
+		i = 1;
+		break;
+	case 65 ... 96:
+		i = 2;
+		break;
+	case 97 ... 128:
+		i = 3;
+		break;
+	case 129 ... 192:
+		i = 4;
+		break;
+	case 193 ... 256:
+		i = 5;
+		break;
+	case 257 ... 512:
+		i = 6;
+		break;
+	case 513 ... 1024:
+		i = 7;
+		break;
+	case 1025 ... 2048:
+		i = 8;
+		break;
+	case 2049 ... 4096:
+		i = 9;
+		break;
+	case 4097 ... 8192:
+		i = 10;
+		break;
+	case 8193 ... 16384:
+		i = 11;
+		break;
+	case 16385 ... 32768:
+		i = 12;
+		break;
+	case 32769 ... 65536:
+		i = 13;
+		break;
+	case 65537 ... 131072:
+		i = 14;
+		break;
+	default:
+		return NULL;
+	}
+
+	return __kmalloc(i, size, flags);
+}
+
 
 extern int FASTCALL(kmem_cache_reap(int));
 

59 lines not on this page · raw message

@@ -58,7 +58,80 @@
 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 __you_cannot_kmalloc_more_than_128_kilo_bytes(void);
+
+enum malloc_numbers
+{
+#if PAGE_SIZE == 4096
+	kmalloc_size_32 = 0,
+#endif
+	kmalloc_size_64,
+#if L1_CACHE_BYTES < 64
+	kmalloc_size_96,
+#endif
+	kmalloc_size_128,
+#if L1_CACHE_BYTES < 128
+	kmalloc_size_192,
+#endif
+	kmalloc_size_256,
+	kmalloc_size_512,
+	kmalloc_size_1024,
+	kmalloc_size_2048,
+	kmalloc_size_4096,
+	kmalloc_size_8192,
+	kmalloc_size_16384,
+	kmalloc_size_32768,
+	kmalloc_size_65536,
+	kmalloc_size_131072
+};
+
+static inline void* __constant_kmalloc(size_t size, int flags)
+{
+#define FIXED_ALLOC(len) \
+	if(size <= len) \
+		return kmem_cache_alloc( (flags & GFP_DMA)? \
+				malloc_sizes[kmalloc_size_##len].cs_dmacachep \
+				: malloc_sizes[kmalloc_size_##len].cs_cachep, \
+				flags)
+#if PAGE_SIZE == 4096
+	FIXED_ALLOC(32);
+#endif
+	FIXED_ALLOC(64);
+#if L1_CACHE_BYTES < 64
+	FIXED_ALLOC(96);
+#endif
+	FIXED_ALLOC(128);
+#if L1_CACHE_BYTES < 128
+	FIXED_ALLOC(192);
+#endif
+	FIXED_ALLOC(256);
+	FIXED_ALLOC(512);
+	FIXED_ALLOC(1024);
+	FIXED_ALLOC(2048);
+	FIXED_ALLOC(4096);
+	FIXED_ALLOC(8192);
+	FIXED_ALLOC(16384);
+	FIXED_ALLOC(32768);
+	FIXED_ALLOC(65536);
+	FIXED_ALLOC(131072);
+#undef FIXED_ALLOC
+	__you_cannot_kmalloc_more_than_128_kilo_bytes();
+	return NULL;
+}
+extern void *__kmalloc(size_t, int);
+
+#define kmalloc(size, flags)				\
+	(__builtin_constant_p(size) ?			\
+	 __constant_kmalloc((size),(flags)) :		\
+	 __kmalloc(size,flags))
+
 extern void kfree(const void *);
 
 extern int FASTCALL(kmem_cache_reap(int));

@@ -369,15 +369,8 @@
 #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 {
-	size_t		 cs_size;
-	kmem_cache_t	*cs_cachep;
-	kmem_cache_t	*cs_dmacachep;
-};
-
 /* These are the default caches for kmalloc. Custom caches can have other sizes. */
-static struct cache_sizes malloc_sizes[] = {
+struct cache_sizes malloc_sizes[] = {
 #if PAGE_SIZE == 4096
 	{    32,	NULL, NULL},
 #endif

@@ -1804,7 +1797,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;
 

@@ -102,7 +102,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);
 EXPORT_SYMBOL(vfree);
 EXPORT_SYMBOL(__vmalloc);