Merge pull request #16 from koverstreet/master

[bcachefs-tools-debian] / linux / generic-radix-tree.c

diff --git a/linux/generic-radix-tree.c b/linux/generic-radix-tree.c
index 5c4a275ea3f57fcd295b9b0fab306780efc28d91..7857017c1d48a11c6ceab7e4069af4908b46a415 100644 (file)
--- a/linux/generic-radix-tree.c
+++ b/linux/generic-radix-tree.c
@@ -1,4 +1,5 @@
 
+#include <linux/atomic.h>
 #include <linux/export.h>
 #include <linux/generic-radix-tree.h>
 #include <linux/gfp.h>
@@ -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;
+               n       = genradix_root_to_node(r);
+               level   = genradix_root_to_depth(r);
 
-               new_root->children[0] = radix->root;
-               radix->root = new_root;
-               radix->depth++;
-       }
-
-       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,23 @@ 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;
+       unsigned level, i;
 
-       if (!radix->root)
+       if (iter->offset == SIZE_MAX)
                return NULL;
+
 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--;
@@ -127,10 +169,17 @@ restart:
                        (GENRADIX_ARY - 1);
 
                while (!n->children[i]) {
+                       size_t objs_per_ptr = genradix_depth_size(level);
+
+                       if (iter->offset + objs_per_ptr < iter->offset) {
+                               iter->offset    = SIZE_MAX;
+                               iter->pos       = SIZE_MAX;
+                               return NULL;
+                       }
+
                        i++;
-                       iter->offset = round_down(iter->offset +
-                                          genradix_depth_size(level),
-                                          genradix_depth_size(level));
+                       iter->offset = round_down(iter->offset + objs_per_ptr,
+                                                 objs_per_ptr);
                        iter->pos = (iter->offset >> PAGE_SHIFT) *
                                objs_per_page;
                        if (i == GENRADIX_ARY)
@@ -157,11 +206,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);