Re: slab: avoid linear search in kmalloc? (GCC Guru wanted :)

[Momchil Velikov <velco@fadata.bg>]

>>>>> "Bernd" == Bernd Eckenfels <ecki@lina.inka.de> writes:

Bernd> Hello,
Bernd> I noticed that kmalloc and kmem_find_general_cachep are doing a linear
Bernd> search in the cache_sizes array. Isnt it better to speed that up by doing a
Bernd> binary search or a b-tree if like the following patch?

Here is a patch using a gcc extension. gcc generates binary search for the case.  

Regards,
-velco

--- slab.c.orig	Wed Sep 19 00:16:26 2001
+++ slab.c	Wed Nov 21 11:11:09 2001
@@ -1533,15 +1533,9 @@ void * kmem_cache_alloc (kmem_cache_t *c
  */
 void * kmalloc (size_t size, int flags)
 {
-	cache_sizes_t *csizep = cache_sizes;
-
-	for (; csizep->cs_size; csizep++) {
-		if (size > csizep->cs_size)
-			continue;
-		return __kmem_cache_alloc(flags & GFP_DMA ?
-			 csizep->cs_dmacachep : csizep->cs_cachep, flags);
-	}
-	return NULL;
+	kmem_cache_t *cp = kmem_find_general_cachep (size, flags);
+	
+	return cp == NULL ? NULL : __kmem_cache_alloc(cp, flags);
 }
 
 /**
@@ -1589,18 +1583,66 @@ void kfree (const void *objp)
 
 kmem_cache_t * kmem_find_general_cachep (size_t size, int gfpflags)
 {
-	cache_sizes_t *csizep = cache_sizes;
+	int idx;
 
-	/* This function could be moved to the header file, and
-	 * made inline so consumers can quickly determine what
-	 * cache pointer they require.
-	 */
-	for ( ; csizep->cs_size; csizep++) {
-		if (size > csizep->cs_size)
-			continue;
+	switch (size) {
+#if PAGE_SIZE == 4096
+	case 0 ... 32: 
+		idx = 0;
+		break;
+	case 33 ... 64:
+		idx = 1;
+		break;
+#else
+	case 0 ... 64:
+		idx = 1;
+		break;
+#endif
+	case 65 ... 128:
+		idx = 2;
+		break;
+	case 129 ... 256:
+		idx = 3;
+		break;
+	case 257 ...512:
+		idx = 4;
+		break;
+	case 513 ... 1024:
+		idx = 5;
+		break;
+	case 1025 ... 2048:
+		idx = 6;
+		break;
+	case 2049 ... 4096:
+		idx = 7;
+		break;
+	case 4097 ... 8192:
+		idx = 8;
+		break;
+	case 8193 ... 16384:
+		idx = 9;
+		break;
+	case 16385 ... 32768:
+		idx = 10;
+		break;
+	case 32769 ... 65536:
+		idx = 11;
+		break;
+	case 65537 ... 131072:
+		idx = 12;
+		break;
+	default:
+		idx = -1;
 		break;
 	}
-	return (gfpflags & GFP_DMA) ? csizep->cs_dmacachep : csizep->cs_cachep;
+
+	if (idx == -1)
+		return NULL;
+
+#if PAGE_SIZE != 4096
+	idx = idx - 1;
+#endif
+	return (gfpflags & GFP_DMA) ? cache_sizes [idx].cs_dmacachep : cache_sizes [idx].cs_cachep;
 }
 
 #ifdef CONFIG_SMP