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