linux-kernel - [PATCH 03/13] lib/generic-radix-tree: Always use low 8 bits of 'root' for depth.

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <c91557f439854e4997e807a5215d4763@AcuMS.aculab.com>
Date:   Tue, 25 Aug 2020 14:53:04 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "'linux-sctp@...r.kernel.org'" <linux-sctp@...r.kernel.org>,
        Eric Biggers <ebiggers@...nel.org>,
        'Marcelo Ricardo Leitner' <marcelo.leitner@...il.com>,
        'Catalin Marinas' <catalin.marinas@....com>,
        "'kent.overstreet@...il.com'" <kent.overstreet@...il.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        "'Neil Horman'" <nhorman@...driver.com>
Subject: [PATCH 03/13] lib/generic-radix-tree: Always use low 8 bits of 'root'
 for depth.

There is no need to calculate the minimum number of bits needed for the
depth (stored in the low bits of the pointer to the root).
Since the root is PAGE_SIZE aligned and we can't need more than 64bits
just use the low 8 bits for the depth.
This (probably) generates better code on x86 then using (say) 6 bits.

Signed-off-by: David Laight <david.laight@...lab.com>
---
 lib/generic-radix-tree.c | 15 +++++++++------
 1 file changed, 9 insertions(+), 6 deletions(-)

diff --git a/lib/generic-radix-tree.c b/lib/generic-radix-tree.c
index d5e97b51308d..12dcaf891af9 100644
--- a/lib/generic-radix-tree.c
+++ b/lib/generic-radix-tree.c
@@ -30,12 +30,15 @@ static inline size_t genradix_depth_size(unsigned depth)
 	return 1UL << genradix_depth_shift(depth);
 }
 
-/* depth that's needed for a genradix that can address up to ULONG_MAX: */
-#define GENRADIX_MAX_DEPTH	\
-	DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT)
-
-#define GENRADIX_DEPTH_MASK				\
-	((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1))
+/*
+ * The 'depth' of the tree is held in the low bits of the 'root'.
+ * Since all the buffers are allocated as pages lots of low bits are zero.
+ * To support a genradix that can address up to ULONG_MAX items the
+ * maximum depth/shift we can possibly need is 64.
+ * However using the low 8 bits for the depth may give better code
+ * on some archectures (eg x86).
+ */
+#define GENRADIX_DEPTH_MASK 0xff
 
 static inline unsigned genradix_root_to_depth(struct genradix_root *r)
 {
-- 
2.25.1

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)