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]
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)

Powered by blists - more mailing lists