Update bcachefs sources to 99750eab4d bcachefs: Persist stripe blocks_used

1 files changed, 89 insertions, 38 deletions

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