Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1427147 > unrolled thread

[PATCH] mm: slab.h: use ilog2() in kmalloc_index()

Back to article view | Back to linux.kernel

Contents

  [PATCH] mm: slab.h: use ilog2() in kmalloc_index() Yury Norov <yury.norov@gmail.com> - 2016-06-21 01:50 +0200
    Re: [PATCH] mm: slab.h: use ilog2() in kmalloc_index() Andrew Morton <akpm@linux-foundation.org> - 2016-06-22 00:10 +0200
      Re: [PATCH] mm: slab.h: use ilog2() in kmalloc_index() Christoph Lameter <cl@linux.com> - 2016-06-22 15:30 +0200

#1427147 — [PATCH] mm: slab.h: use ilog2() in kmalloc_index()

kmalloc_index() uses simple straightforward way to calculate
bit position of nearest or equal upper power of 2.
This effectively results in generation of 24 episodes of
compare-branch instructions in assembler.

There is shorter way to calculate this: fls(size - 1).

The patch removes hard-coded calculation of kmalloc slab and
uses ilog2() instead that works on top of fls(). ilog2 is used
with intention that compiler also might optimize constant case
during compile time if it detects that.

BUG() is moved to the beginning of function. We left it here to
provide identical behaviour to previous version. It may be removed
if there's no requirement in it anymore.

While we're at this, fix comment that describes return value.

Reported-by: Alexey Klimov <klimov.linux@gmail.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Alexey Klimov <klimov.linux@gmail.com>
---
 include/linux/slab.h | 41 +++++++++--------------------------------
 1 file changed, 9 insertions(+), 32 deletions(-)

diff --git a/include/linux/slab.h b/include/linux/slab.h
index aeb3e6d..294ef52 100644
--- a/include/linux/slab.h
+++ b/include/linux/slab.h
@@ -267,13 +267,16 @@ extern struct kmem_cache *kmalloc_dma_caches[KMALLOC_SHIFT_HIGH + 1];
 /*
  * Figure out which kmalloc slab an allocation of a certain size
  * belongs to.
- * 0 = zero alloc
- * 1 =  65 .. 96 bytes
- * 2 = 129 .. 192 bytes
- * n = 2^(n-1)+1 .. 2^n
+ * 0 if zero alloc, or
+ * 1 if size is 65 .. 96 bytes, or
+ * 2 if size is 129 .. 192 bytes, or
+ * n if 2^(n - 1) < size <= 2^n
  */
 static __always_inline int kmalloc_index(size_t size)
 {
+	/* Bigger size is a bug */
+	BUG_ON(size > (1 << 26));
+
 	if (!size)
 		return 0;
 
@@ -284,34 +287,8 @@ static __always_inline int kmalloc_index(size_t size)
 		return 1;
 	if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)
 		return 2;
-	if (size <=          8) return 3;
-	if (size <=         16) return 4;
-	if (size <=         32) return 5;
-	if (size <=         64) return 6;
-	if (size <=        128) return 7;
-	if (size <=        256) return 8;
-	if (size <=        512) return 9;
-	if (size <=       1024) return 10;
-	if (size <=   2 * 1024) return 11;
-	if (size <=   4 * 1024) return 12;
-	if (size <=   8 * 1024) return 13;
-	if (size <=  16 * 1024) return 14;
-	if (size <=  32 * 1024) return 15;
-	if (size <=  64 * 1024) return 16;
-	if (size <= 128 * 1024) return 17;
-	if (size <= 256 * 1024) return 18;
-	if (size <= 512 * 1024) return 19;
-	if (size <= 1024 * 1024) return 20;
-	if (size <=  2 * 1024 * 1024) return 21;
-	if (size <=  4 * 1024 * 1024) return 22;
-	if (size <=  8 * 1024 * 1024) return 23;
-	if (size <=  16 * 1024 * 1024) return 24;
-	if (size <=  32 * 1024 * 1024) return 25;
-	if (size <=  64 * 1024 * 1024) return 26;
-	BUG();
-
-	/* Will never be reached. Needed because the compiler may complain */
-	return -1;
+
+	return ilog2(size - 1) + 1;
 }
 #endif /* !CONFIG_SLOB */
 
-- 
2.7.4

[toc] | [next] | [standalone]

#1428223

On Tue, 21 Jun 2016 02:33:06 +0300 Yury Norov <yury.norov@gmail.com> wrote:

> kmalloc_index() uses simple straightforward way to calculate
> bit position of nearest or equal upper power of 2.
> This effectively results in generation of 24 episodes of
> compare-branch instructions in assembler.
> 
> There is shorter way to calculate this: fls(size - 1).
> 
> The patch removes hard-coded calculation of kmalloc slab and
> uses ilog2() instead that works on top of fls(). ilog2 is used
> with intention that compiler also might optimize constant case
> during compile time if it detects that.
> 
> BUG() is moved to the beginning of function. We left it here to
> provide identical behaviour to previous version. It may be removed
> if there's no requirement in it anymore.
> 
> While we're at this, fix comment that describes return value.

kmalloc_index() is always called with a constant-valued `size' (see
__builtin_constant_p() tests) so the compiler will evaluate the switch
statement at compile-time.  This will be more efficient than calling
fls() at runtime.

[toc] | [prev] | [next] | [standalone]

#1428788

On Wed, 22 Jun 2016, Yury Norov wrote:

>
> There will be no fls() for constant at runtime because ilog2() calculates
> constant values at compile-time as well. From this point of view,
> this patch removes code duplication, as we already have compile-time
> log() calculation in kernel, and should re-use it whenever possible.\

The reason not to use ilog there was that the constant folding did not
work correctly with one or the other architectures/compilers. If you want
to do this then please verify that all arches reliably do produce a
constant there.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web