From 35fca2f044d375b1590f499cfd34bef38ca0f8f1 Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Wed, 23 Jan 2019 15:49:44 -0500 Subject: Update bcachefs sources to 99750eab4d bcachefs: Persist stripe blocks_used --- linux/generic-radix-tree.c | 127 +++++++++++++++++++++++++++++++-------------- 1 file changed, 89 insertions(+), 38 deletions(-) (limited to 'linux') diff --git a/linux/generic-radix-tree.c b/linux/generic-radix-tree.c index 5c4a275e..4f43d0bb 100644 --- a/linux/generic-radix-tree.c +++ b/linux/generic-radix-tree.c @@ -1,4 +1,5 @@ +#include #include #include #include @@ -16,7 +17,7 @@ struct genradix_node { }; }; -static inline unsigned genradix_depth_shift(unsigned depth) +static inline int genradix_depth_shift(unsigned depth) { return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth; } @@ -29,16 +30,34 @@ static inline size_t genradix_depth_size(unsigned depth) return 1UL << genradix_depth_shift(depth); } +/* depth that's needed for a genradix that can address up to ULONG_MAX: */ +#define GENRADIX_MAX_DEPTH \ + DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT) + +#define GENRADIX_DEPTH_MASK \ + ((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1)) + +unsigned genradix_root_to_depth(struct genradix_root *r) +{ + return (unsigned long) r & GENRADIX_DEPTH_MASK; +} + +struct genradix_node *genradix_root_to_node(struct genradix_root *r) +{ + return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK); +} + /* * Returns pointer to the specified byte @offset within @radix, or NULL if not * allocated */ void *__genradix_ptr(struct __genradix *radix, size_t offset) { - size_t level = radix->depth; - struct genradix_node *n = radix->root; + struct genradix_root *r = READ_ONCE(radix->root); + struct genradix_node *n = genradix_root_to_node(r); + unsigned level = genradix_root_to_depth(r); - if (offset >= genradix_depth_size(radix->depth)) + if (ilog2(offset) >= genradix_depth_shift(level)) return NULL; while (1) { @@ -64,43 +83,60 @@ EXPORT_SYMBOL(__genradix_ptr); void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset, gfp_t gfp_mask) { - struct genradix_node **n; - size_t level; + struct genradix_root *v = READ_ONCE(radix->root); + struct genradix_node *n, *new_node = NULL; + unsigned level; /* Increase tree depth if necessary: */ + while (1) { + struct genradix_root *r = v, *new_root; - while (offset >= genradix_depth_size(radix->depth)) { - struct genradix_node *new_root = - (void *) __get_free_page(gfp_mask|__GFP_ZERO); - - if (!new_root) - return NULL; - - new_root->children[0] = radix->root; - radix->root = new_root; - radix->depth++; - } + n = genradix_root_to_node(r); + level = genradix_root_to_depth(r); - n = &radix->root; - level = radix->depth; + if (n && ilog2(offset) < genradix_depth_shift(level)) + break; - while (1) { - if (!*n) { - *n = (void *) __get_free_page(gfp_mask|__GFP_ZERO); - if (!*n) + if (!new_node) { + new_node = (void *) + __get_free_page(gfp_mask|__GFP_ZERO); + if (!new_node) return NULL; } - if (!level) - break; + new_node->children[0] = n; + new_root = ((struct genradix_root *) + ((unsigned long) new_node | (n ? level + 1 : 0))); - level--; + if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) { + v = new_root; + new_node = NULL; + } + } - n = &(*n)->children[offset >> genradix_depth_shift(level)]; + while (level--) { + struct genradix_node **p = + &n->children[offset >> genradix_depth_shift(level)]; offset &= genradix_depth_size(level) - 1; + + n = READ_ONCE(*p); + if (!n) { + if (!new_node) { + new_node = (void *) + __get_free_page(gfp_mask|__GFP_ZERO); + if (!new_node) + return NULL; + } + + if (!(n = cmpxchg_release(p, NULL, new_node))) + swap(n, new_node); + } } - return &(*n)->data[offset]; + if (new_node) + free_page((unsigned long) new_node); + + return &n->data[offset]; } EXPORT_SYMBOL(__genradix_ptr_alloc); @@ -108,17 +144,19 @@ void *__genradix_iter_peek(struct genradix_iter *iter, struct __genradix *radix, size_t objs_per_page) { + struct genradix_root *r; struct genradix_node *n; - size_t level, i; - - if (!radix->root) - return NULL; + unsigned level, i; restart: - if (iter->offset >= genradix_depth_size(radix->depth)) + r = READ_ONCE(radix->root); + if (!r) return NULL; - n = radix->root; - level = radix->depth; + n = genradix_root_to_node(r); + level = genradix_root_to_depth(r); + + if (ilog2(iter->offset) >= genradix_depth_shift(level)) + return NULL; while (level) { level--; @@ -157,11 +195,24 @@ static void genradix_free_recurse(struct genradix_node *n, unsigned level) free_page((unsigned long) n); } +int __genradix_prealloc(struct __genradix *radix, size_t size, + gfp_t gfp_mask) +{ + size_t offset; + + for (offset = 0; offset < size; offset += PAGE_SIZE) + if (!__genradix_ptr_alloc(radix, offset, gfp_mask)) + return -ENOMEM; + + return 0; +} +EXPORT_SYMBOL(__genradix_prealloc); + void __genradix_free(struct __genradix *radix) { - genradix_free_recurse(radix->root, radix->depth); + struct genradix_root *r = xchg(&radix->root, NULL); - radix->root = NULL; - radix->depth = 0; + genradix_free_recurse(genradix_root_to_node(r), + genradix_root_to_depth(r)); } EXPORT_SYMBOL(__genradix_free); -- cgit v1.2.3