Saving the 'number of bits to shift' to get the array index rather than the 'level' saves the shift = level * 9 + 3 calculations. In addition a shift of zero only happens for an NULL pointer, so the 'indirect into a single page' check can be optimised for.
Signed-off-by: David Laight <[email protected]> --- lib/generic-radix-tree.c | 116 ++++++++++++++++++++------------------- 1 file changed, 59 insertions(+), 57 deletions(-) diff --git a/lib/generic-radix-tree.c b/lib/generic-radix-tree.c index 0df99ee428d8..363bcefae8aa 100644 --- a/lib/generic-radix-tree.c +++ b/lib/generic-radix-tree.c @@ -6,6 +6,7 @@ #define GENRADIX_ARY (PAGE_SIZE / sizeof(struct genradix_node *)) #define GENRADIX_ARY_SHIFT ilog2(GENRADIX_ARY) +#define GENRADIX_ROOT_SHIFT ilog2(sizeof(struct genradix_node *)) struct genradix_node { union { @@ -17,11 +18,6 @@ struct genradix_node { }; }; -static inline int genradix_depth_shift(unsigned depth) -{ - return PAGE_SHIFT + GENRADIX_ARY_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. @@ -29,17 +25,21 @@ static inline int genradix_depth_shift(unsigned depth) * 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). + * + * The 'depth' is saved as the shift to get the index into children[]. + * With 4k pages on a 64bit system the values are 3, 12, 21 etc. + * A 0 shift only ever happens when the pointer is NULL. */ -#define GENRADIX_DEPTH_MASK 0xff +#define GENRADIX_SHIFT_MASK 0xff -static inline unsigned genradix_root_to_depth(struct genradix_root *r) +static inline unsigned genradix_root_to_shift(struct genradix_root *r) { - return (unsigned long) r & GENRADIX_DEPTH_MASK; + return (unsigned long)r & GENRADIX_SHIFT_MASK; } static inline struct genradix_node *genradix_root_to_node(struct genradix_root *r) { - return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK); + return (void *)((unsigned long) r & ~GENRADIX_SHIFT_MASK); } /* @@ -50,16 +50,14 @@ 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 int shift = genradix_root_to_depth(r); + unsigned int shift = genradix_root_to_shift(r); unsigned int idx; - if (unlikely(!n)) - return NULL; - - if (!shift) + if (likely(shift == GENRADIX_ROOT_SHIFT)) return offset < PAGE_SIZE ? n->data + offset : NULL; - shift = genradix_depth_shift(shift) - GENRADIX_ARY_SHIFT; + if (unlikely(!shift)) + return NULL; idx = offset >> shift; if (unlikely(idx >= GENRADIX_ARY)) @@ -102,7 +100,7 @@ static inline void genradix_free_node(struct genradix_node *node) static noinline struct genradix_node * alloc_node(struct genradix_node **tgt, struct genradix_node *old, - struct genradix_node *child, unsigned int level, gfp_t gfp) + struct genradix_node *child, unsigned int shift, gfp_t gfp) { struct genradix_node *n = genradix_alloc_node(gfp); struct genradix_node *new_node, *check; @@ -111,8 +109,8 @@ alloc_node(struct genradix_node **tgt, struct genradix_node *old, return NULL; n->children[0] = child; - /* The 'root' address is 'overpunched' with the level */ - new_node = (void *)((unsigned long)n + level); + /* The 'root' address is 'overpunched' with the shift */ + new_node = (void *)((unsigned long)n + shift); check = cmpxchg_release(tgt, old, new_node); if (check == old) @@ -124,9 +122,9 @@ alloc_node(struct genradix_node **tgt, struct genradix_node *old, static struct genradix_root * alloc_root(struct genradix_root **tgt, struct genradix_root *old, - struct genradix_node *child, unsigned int level, gfp_t gfp) + struct genradix_node *child, unsigned int shift, gfp_t gfp) { - return (void *)alloc_node((void *)tgt, (void *)old, child, level, gfp); + return (void *)alloc_node((void *)tgt, (void *)old, child, shift, gfp); } /* @@ -137,43 +135,48 @@ void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset, gfp_t gfp) { struct genradix_node *n, *n1; struct genradix_root *r; - unsigned int level, shift; + unsigned int shift; unsigned int idx; r = READ_ONCE(radix->root); - level = genradix_root_to_depth(r); + shift = genradix_root_to_shift(r); + n = genradix_root_to_node(r); /* Optimise non-tree structures */ - if (likely(!level) && likely(offset < PAGE_SIZE)) { - n = genradix_root_to_node(r); - if (likely(n)) + if (likely(offset < PAGE_SIZE)) { + if (likely(shift == GENRADIX_ROOT_SHIFT)) return n->data + offset; - r = alloc_root(&radix->root, NULL, NULL, 0, gfp); - if (!r) - return NULL; - level = genradix_root_to_depth(r); - if (!level) { + + if (!shift) { + r = alloc_root(&radix->root, NULL, NULL, GENRADIX_ROOT_SHIFT, gfp); + if (!r) + return NULL; + shift = genradix_root_to_shift(r); n = genradix_root_to_node(r); - return n->data + offset; + if (shift == GENRADIX_ROOT_SHIFT) + return n->data + offset; + /* Someone else added multiple root levels */ } - } - - /* Ensure tree is deep enough */ - for (;;) { - n = genradix_root_to_node(r); - shift = genradix_depth_shift(level) - GENRADIX_ARY_SHIFT; - idx = offset >> shift; - - if (likely(idx < GENRADIX_ARY)) - break; - - /* Tree depth needs increasing */ - r = alloc_root(&radix->root, r, n, level + 1, gfp); - if (!r) - return NULL; + } else { + /* Ensure tree is deep enough */ + for (;;) { + idx = offset >> shift; + + if (likely(idx < GENRADIX_ARY)) + break; + + /* Tree depth needs increasing */ + if (!shift) + shift = GENRADIX_ROOT_SHIFT; + shift += GENRADIX_ARY_SHIFT; + r = alloc_root(&radix->root, r, n, shift, gfp); + if (!r) + return NULL; - /* Multiple levels could have been added by someone else. */ - level = genradix_root_to_depth(r); + /* Many levels could have been added by someone else. */ + shift = genradix_root_to_shift(r); + n = genradix_root_to_node(r); + } } /* Descend the tree */ @@ -201,15 +204,14 @@ void *__genradix_iter_peek(struct genradix_iter *iter, { struct genradix_root *r; struct genradix_node *n; - unsigned int shift, level, i; + unsigned int shift, i; restart: r = READ_ONCE(radix->root); if (!r) return NULL; n = genradix_root_to_node(r); - level = genradix_root_to_depth(r); - shift = genradix_depth_shift(level); + shift = genradix_root_to_shift(r); if (iter->offset >> shift) return NULL; @@ -221,8 +223,7 @@ void *__genradix_iter_peek(struct genradix_iter *iter, while (!n->children[i]) { i++; - iter->offset = round_down(iter->offset + - (1u << shift), + iter->offset = round_down(iter->offset + (1u << shift), 1u << shift); iter->pos = (iter->offset >> PAGE_SHIFT) * objs_per_page; @@ -237,14 +238,15 @@ void *__genradix_iter_peek(struct genradix_iter *iter, } EXPORT_SYMBOL(__genradix_iter_peek); -static void genradix_free_recurse(struct genradix_node *n, unsigned level) +static void genradix_free_recurse(struct genradix_node *n, unsigned shift) { - if (level) { + if (shift > GENRADIX_ARY_SHIFT) { unsigned i; + shift -= GENRADIX_ARY_SHIFT; for (i = 0; i < GENRADIX_ARY; i++) if (n->children[i]) - genradix_free_recurse(n->children[i], level - 1); + genradix_free_recurse(n->children[i], shift); } genradix_free_node(n); @@ -267,6 +269,6 @@ void __genradix_free(struct __genradix *radix) struct genradix_root *r = xchg(&radix->root, NULL); genradix_free_recurse(genradix_root_to_node(r), - genradix_root_to_depth(r)); + genradix_root_to_shift(r)); } EXPORT_SYMBOL(__genradix_free); -- 2.25.1 - Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
