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:02 +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 04/13] lib/generic-radix-tree: Optimise __genradix_ptr()

While gcc managed to convert the 'level' loop into one that changed the
'shift' it couldn't convert '(offset & mask) >> n' to '(offset >> n) & 511'
so avoiding body of genradix_depth_size().
Perform both optimisations in the source.

Also optimise for the common (given the only users of this code) case of
the entire radix-tree fitting in one page.

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

diff --git a/lib/generic-radix-tree.c b/lib/generic-radix-tree.c
index 12dcaf891af9..212e04cf171a 100644
--- a/lib/generic-radix-tree.c
+++ b/lib/generic-radix-tree.c
@@ -58,24 +58,32 @@ void *__genradix_ptr(struct __genradix *radix, size_t offset)
 {
 	struct genradix_root *r = READ_ONCE(radix->root);
 	struct genradix_node *n = genradix_root_to_node(r);
-	unsigned level		= genradix_root_to_depth(r);
+	unsigned int shift = genradix_root_to_depth(r);
+	unsigned int idx;
 
-	if (offset >> genradix_depth_shift(level))
+	if (unlikely(!n))
 		return NULL;
 
-	while (1) {
-		if (!n)
+	if (!shift)
+		return offset < PAGE_SIZE ? n->data + offset : NULL;
+
+	shift = genradix_depth_shift(shift) - GENRADIX_ARY_SHIFT;
+
+	idx = offset >> shift;
+	if (unlikely(idx >= GENRADIX_ARY))
+		return NULL;
+
+	for (;;) {
+		n = READ_ONCE(n->children[idx]);
+		if (unlikely(!n))
 			return NULL;
-		if (!level)
-			break;
 
-		level--;
+		if (shift == PAGE_SHIFT)
+			return n->data + (offset % PAGE_SIZE);
 
-		n = n->children[offset >> genradix_depth_shift(level)];
-		offset &= genradix_depth_size(level) - 1;
+		shift -= GENRADIX_ARY_SHIFT;
+		idx = (offset >> shift) % GENRADIX_ARY;
 	}
-
-	return &n->data[offset];
 }
 EXPORT_SYMBOL(__genradix_ptr);
 
-- 
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