linux-kernel - [PATCH 07/13] lib/generic-radix-tree: Optimise __genradix_iter

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: <d606b3e29ec3407f98d4deb20bc29662@AcuMS.aculab.com>
Date:   Tue, 25 Aug 2020 14:52:35 +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 07/13] lib/generic-radix-tree: Optimise __genradix_iter_peek()

Use the the 'shift' rather than the 'level'.
NB There are exactly zero users of this code.

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

diff --git a/lib/generic-radix-tree.c b/lib/generic-radix-tree.c
index 219b43250a06..0df99ee428d8 100644
--- a/lib/generic-radix-tree.c
+++ b/lib/generic-radix-tree.c
@@ -22,14 +22,6 @@ static inline int genradix_depth_shift(unsigned depth)
 	return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth;
 }
 
-/*
- * Returns size (of data, in bytes) that a tree of a given depth holds:
- */
-static inline size_t genradix_depth_size(unsigned depth)
-{
-	return 1UL << genradix_depth_shift(depth);
-}
-
 /*
  * 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.
@@ -209,7 +201,7 @@ void *__genradix_iter_peek(struct genradix_iter *iter,
 {
 	struct genradix_root *r;
 	struct genradix_node *n;
-	unsigned level, i;
+	unsigned int shift, level, i;
 restart:
 	r = READ_ONCE(radix->root);
 	if (!r)
@@ -217,21 +209,21 @@ void *__genradix_iter_peek(struct genradix_iter *iter,
 
 	n	= genradix_root_to_node(r);
 	level	= genradix_root_to_depth(r);
+	shift = genradix_depth_shift(level);
 
-	if (iter->offset >> genradix_depth_shift(level))
+	if (iter->offset >> shift)
 		return NULL;
 
-	while (level) {
-		level--;
+	while (shift > GENRADIX_ARY_SHIFT) {
+		shift -= GENRADIX_ARY_SHIFT;
 
-		i = (iter->offset >> genradix_depth_shift(level)) &
-			(GENRADIX_ARY - 1);
+		i = (iter->offset >> shift) % GENRADIX_ARY;
 
 		while (!n->children[i]) {
 			i++;
 			iter->offset = round_down(iter->offset +
-					   genradix_depth_size(level),
-					   genradix_depth_size(level));
+					   (1u << shift),
+					   1u << shift);
 			iter->pos = (iter->offset >> PAGE_SHIFT) *
 				objs_per_page;
 			if (i == GENRADIX_ARY)
-- 
2.25.1

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