linux-kernel - [PATCH] lib/radix-tree.c: use generic find_next

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:   Fri,  3 Jan 2020 20:24:08 -0800
From:   Yury Norov <yury.norov@...il.com>
To:     Richard Fontana <rfontana@...hat.com>,
        Allison Randal <allison@...utok.net>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        "Matthew Wilcox (Oracle)" <willy@...radead.org>,
        Armijn Hemel <armijn@...ldur.nl>,
        Yury Norov <yury.norov@...il.com>,
        Thomas Gleixner <tglx@...utronix.de>,
        linux-kernel@...r.kernel.org
Subject: [PATCH] lib/radix-tree.c: use generic find_next_bit()

lib/radix-tree.c has its own version of find_next_bit(). This patch
switches it to generic one.

Testing with tools/testing/radix-tree shows no significant difference.

Before:
$ time ./main
random seed 1578108797
running tests
XArray: 21151073 of 21151073 tests passed
vvv Ignore these warnings
assertion failed at idr.c:269
assertion failed at idr.c:206
^^^ Warnings over
IDA: 39122827 of 39122827 tests passed
tests completed

real	1m28.290s
user	2m29.610s
sys	0m32.256s
yury:radix-tree$ mutt
4440 kept, 0 deleted.

After:
$ time ./main
random seed 1578108654
running tests
XArray: 21151073 of 21151073 tests passed
qvvv Ignore these warnings
assertion failed at idr.c:269
assertion failed at idr.c:206
^^^ Warnings over
IDA: 40991309 of 40991309 tests passed
tests completed

real	1m29.035s
user	2m31.481s
sys	0m33.006s

Signed-off-by: Yury Norov <yury.norov@...il.com>
---
 lib/radix-tree.c | 19 +------------------
 1 file changed, 1 insertion(+), 18 deletions(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index c8fa1d2745302..23f86281133da 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -189,24 +189,7 @@ static __always_inline unsigned long
 radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag,
 			 unsigned long offset)
 {
-	const unsigned long *addr = node->tags[tag];
-
-	if (offset < RADIX_TREE_MAP_SIZE) {
-		unsigned long tmp;
-
-		addr += offset / BITS_PER_LONG;
-		tmp = *addr >> (offset % BITS_PER_LONG);
-		if (tmp)
-			return __ffs(tmp) + offset;
-		offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1);
-		while (offset < RADIX_TREE_MAP_SIZE) {
-			tmp = *++addr;
-			if (tmp)
-				return __ffs(tmp) + offset;
-			offset += BITS_PER_LONG;
-		}
-	}
-	return RADIX_TREE_MAP_SIZE;
+	return find_next_bit(node->tags[tag], RADIX_TREE_MAP_SIZE, offset);
 }
 
 static unsigned int iter_offset(const struct radix_tree_iter *iter)
-- 
2.20.1