xarray: Add definition of struct xarray

This is a direct replacement for struct radix_tree_root.  Some of the
struct members have changed name; convert those, and use a #define so
that radix_tree users continue to work without change.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
Reviewed-by: Josef Bacik <jbacik@fb.com>

4 files changed, 84 insertions, 41 deletions

diff --git a/lib/Makefile b/lib/Makefile
index ca3f7ebb900d..057385f1f145 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -18,7 +18,7 @@ KCOV_INSTRUMENT_debugobjects.o := n
 KCOV_INSTRUMENT_dynamic_debug.o := n
 
 lib-y := ctype.o string.o vsprintf.o cmdline.o \
-         rbtree.o radix-tree.o timerqueue.o\
+         rbtree.o radix-tree.o timerqueue.o xarray.o \
          idr.o int_sqrt.o extable.o \
          sha1.o chacha20.o irq_regs.o argv_split.o \
          flex_proportions.o ratelimit.o show_mem.o \
diff --git a/lib/idr.c b/lib/idr.c
index 88419fbc5737..9a366b5be2c2 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -39,8 +39,8 @@ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
         unsigned int base = idr->idr_base;
         unsigned int id = *nextid;
 
-        if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR)))
-                idr->idr_rt.gfp_mask |= IDR_RT_MARKER;
+        if (WARN_ON_ONCE(!(idr->idr_rt.xa_flags & ROOT_IS_IDR)))
+                idr->idr_rt.xa_flags |= IDR_RT_MARKER;
 
         id = (id < base) ? 0 : id - base;
         radix_tree_iter_init(&iter, id);
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 59b28111eabc..299d4bdba109 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -124,7 +124,7 @@ static unsigned int radix_tree_descend(const struct radix_tree_node *parent,
 
 static inline gfp_t root_gfp_mask(const struct radix_tree_root *root)
 {
-        return root->gfp_mask & (__GFP_BITS_MASK & ~GFP_ZONEMASK);
+        return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK);
 }
 
 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
@@ -147,32 +147,32 @@ static inline int tag_get(const struct radix_tree_node *node, unsigned int tag,
 
 static inline void root_tag_set(struct radix_tree_root *root, unsigned tag)
 {
-        root->gfp_mask |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));
+        root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));
 }
 
 static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
 {
-        root->gfp_mask &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));
+        root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));
 }
 
 static inline void root_tag_clear_all(struct radix_tree_root *root)
 {
-        root->gfp_mask &= (1 << ROOT_TAG_SHIFT) - 1;
+        root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1);
 }
 
 static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag)
 {
-        return (__force int)root->gfp_mask & (1 << (tag + ROOT_TAG_SHIFT));
+        return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT));
 }
 
 static inline unsigned root_tags_get(const struct radix_tree_root *root)
 {
-        return (__force unsigned)root->gfp_mask >> ROOT_TAG_SHIFT;
+        return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT;
 }
 
 static inline bool is_idr(const struct radix_tree_root *root)
 {
-        return !!(root->gfp_mask & ROOT_IS_IDR);
+        return !!(root->xa_flags & ROOT_IS_IDR);
 }
 
 /*
@@ -291,12 +291,12 @@ static void dump_node(struct radix_tree_node *node, unsigned long index)
 /* For debug */
 static void radix_tree_dump(struct radix_tree_root *root)
 {
-        pr_debug("radix root: %p rnode %p tags %x\n",
-                        root, root->rnode,
-                        root->gfp_mask >> ROOT_TAG_SHIFT);
-        if (!radix_tree_is_internal_node(root->rnode))
+        pr_debug("radix root: %p xa_head %p tags %x\n",
+                        root, root->xa_head,
+                        root->xa_flags >> ROOT_TAG_SHIFT);
+        if (!radix_tree_is_internal_node(root->xa_head))
                 return;
-        dump_node(entry_to_node(root->rnode), 0);
+        dump_node(entry_to_node(root->xa_head), 0);
 }
 
 static void dump_ida_node(void *entry, unsigned long index)
@@ -340,9 +340,9 @@ static void dump_ida_node(void *entry, unsigned long index)
 static void ida_dump(struct ida *ida)
 {
         struct radix_tree_root *root = &ida->ida_rt;
-        pr_debug("ida: %p node %p free %d\n", ida, root->rnode,
-                                root->gfp_mask >> ROOT_TAG_SHIFT);
-        dump_ida_node(root->rnode, 0);
+        pr_debug("ida: %p node %p free %d\n", ida, root->xa_head,
+                                root->xa_flags >> ROOT_TAG_SHIFT);
+        dump_ida_node(root->xa_head, 0);
 }
 #endif
 
@@ -576,7 +576,7 @@ int radix_tree_maybe_preload_order(gfp_t gfp_mask, int order)
 static unsigned radix_tree_load_root(const struct radix_tree_root *root,
                 struct radix_tree_node **nodep, unsigned long *maxindex)
 {
-        struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
+        struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
 
         *nodep = node;
 
@@ -605,7 +605,7 @@ static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
         while (index > shift_maxindex(maxshift))
                 maxshift += RADIX_TREE_MAP_SHIFT;
 
-        entry = rcu_dereference_raw(root->rnode);
+        entry = rcu_dereference_raw(root->xa_head);
         if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE)))
                 goto out;
 
@@ -633,7 +633,7 @@ static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
                 if (radix_tree_is_internal_node(entry)) {
                         entry_to_node(entry)->parent = node;
                 } else if (xa_is_value(entry)) {
-                        /* Moving an exceptional root->rnode to a node */
+                        /* Moving an exceptional root->xa_head to a node */
                         node->exceptional = 1;
                 }
                 /*
@@ -642,7 +642,7 @@ static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
                  */
                 node->slots[0] = (void __rcu *)entry;
                 entry = node_to_entry(node);
-                rcu_assign_pointer(root->rnode, entry);
+                rcu_assign_pointer(root->xa_head, entry);
                 shift += RADIX_TREE_MAP_SHIFT;
         } while (shift <= maxshift);
 out:
@@ -659,7 +659,7 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root,
         bool shrunk = false;
 
         for (;;) {
-                struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
+                struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
                 struct radix_tree_node *child;
 
                 if (!radix_tree_is_internal_node(node))
@@ -695,9 +695,9 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root,
                  * moving the node from one part of the tree to another: if it
                  * was safe to dereference the old pointer to it
                  * (node->slots[0]), it will be safe to dereference the new
-                 * one (root->rnode) as far as dependent read barriers go.
+                 * one (root->xa_head) as far as dependent read barriers go.
                  */
-                root->rnode = (void __rcu *)child;
+                root->xa_head = (void __rcu *)child;
                 if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
                         root_tag_clear(root, IDR_FREE);
 
@@ -745,9 +745,8 @@ static bool delete_node(struct radix_tree_root *root,
 
                 if (node->count) {
                         if (node_to_entry(node) ==
-                                        rcu_dereference_raw(root->rnode))
-                                deleted |= radix_tree_shrink(root,
-                                                                update_node);
+                                        rcu_dereference_raw(root->xa_head))
+                                deleted |= radix_tree_shrink(root, update_node);
                         return deleted;
                 }
 
@@ -762,7 +761,7 @@ static bool delete_node(struct radix_tree_root *root,
                          */
                         if (!is_idr(root))
                                 root_tag_clear_all(root);
-                        root->rnode = NULL;
+                        root->xa_head = NULL;
                 }
 
                 WARN_ON_ONCE(!list_empty(&node->private_list));
@@ -787,7 +786,7 @@ static bool delete_node(struct radix_tree_root *root,
  *      at position @index in the radix tree @root.
  *
  *      Until there is more than one item in the tree, no nodes are
- *      allocated and @root->rnode is used as a direct slot instead of
+ *      allocated and @root->xa_head is used as a direct slot instead of
  *      pointing to a node, in which case *@nodep will be NULL.
  *
  *      Returns -ENOMEM, or 0 for success.
@@ -797,7 +796,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
                         void __rcu ***slotp)
 {
         struct radix_tree_node *node = NULL, *child;
-        void __rcu **slot = (void __rcu **)&root->rnode;
+        void __rcu **slot = (void __rcu **)&root->xa_head;
         unsigned long maxindex;
         unsigned int shift, offset = 0;
         unsigned long max = index | ((1UL << order) - 1);
@@ -813,7 +812,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
                 if (error < 0)
                         return error;
                 shift = error;
-                child = rcu_dereference_raw(root->rnode);
+                child = rcu_dereference_raw(root->xa_head);
         }
 
         while (shift > order) {
@@ -1004,7 +1003,7 @@ EXPORT_SYMBOL(__radix_tree_insert);
  *      tree @root.
  *
  *      Until there is more than one item in the tree, no nodes are
- *      allocated and @root->rnode is used as a direct slot instead of
+ *      allocated and @root->xa_head is used as a direct slot instead of
  *      pointing to a node, in which case *@nodep will be NULL.
  */
 void *__radix_tree_lookup(const struct radix_tree_root *root,
@@ -1017,7 +1016,7 @@ void *__radix_tree_lookup(const struct radix_tree_root *root,
 
  restart:
         parent = NULL;
-        slot = (void __rcu **)&root->rnode;
+        slot = (void __rcu **)&root->xa_head;
         radix_tree_load_root(root, &node, &maxindex);
         if (index > maxindex)
                 return NULL;
@@ -1168,9 +1167,9 @@ void __radix_tree_replace(struct radix_tree_root *root,
         /*
          * This function supports replacing exceptional entries and
          * deleting entries, but that needs accounting against the
-         * node unless the slot is root->rnode.
+         * node unless the slot is root->xa_head.
          */
-        WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->rnode) &&
+        WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) &&
                         (count || exceptional));
         replace_slot(slot, item, node, count, exceptional);
 
@@ -1722,7 +1721,7 @@ void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
                 iter->tags = 1;
                 iter->node = NULL;
                 __set_iter_shift(iter, 0);
-                return (void __rcu **)&root->rnode;
+                return (void __rcu **)&root->xa_head;
         }
 
         do {
@@ -2109,7 +2108,7 @@ void __rcu **idr_get_free(struct radix_tree_root *root,
                               unsigned long max)
 {
         struct radix_tree_node *node = NULL, *child;
-        void __rcu **slot = (void __rcu **)&root->rnode;
+        void __rcu **slot = (void __rcu **)&root->xa_head;
         unsigned long maxindex, start = iter->next_index;
         unsigned int shift, offset = 0;
 
@@ -2125,7 +2124,7 @@ void __rcu **idr_get_free(struct radix_tree_root *root,
                 if (error < 0)
                         return ERR_PTR(error);
                 shift = error;
-                child = rcu_dereference_raw(root->rnode);
+                child = rcu_dereference_raw(root->xa_head);
         }
         if (start == 0 && shift == 0)
                 shift = RADIX_TREE_MAP_SHIFT;
@@ -2190,10 +2189,10 @@ void __rcu **idr_get_free(struct radix_tree_root *root,
  */
 void idr_destroy(struct idr *idr)
 {
-        struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.rnode);
+        struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.xa_head);
         if (radix_tree_is_internal_node(node))
                 radix_tree_free_nodes(node);
-        idr->idr_rt.rnode = NULL;
+        idr->idr_rt.xa_head = NULL;
         root_tag_set(&idr->idr_rt, IDR_FREE);
 }
 EXPORT_SYMBOL(idr_destroy);
diff --git a/lib/xarray.c b/lib/xarray.c
new file mode 100644
index 000000000000..862f4c64c754
--- /dev/null
+++ b/lib/xarray.c
@@ -0,0 +1,44 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * XArray implementation
+ * Copyright (c) 2017 Microsoft Corporation
+ * Author: Matthew Wilcox <willy@infradead.org>
+ */
+
+#include <linux/export.h>
+#include <linux/xarray.h>
+
+/*
+ * Coding conventions in this file:
+ *
+ * @xa is used to refer to the entire xarray.
+ * @xas is the 'xarray operation state'.  It may be either a pointer to
+ * an xa_state, or an xa_state stored on the stack.  This is an unfortunate
+ * ambiguity.
+ * @index is the index of the entry being operated on
+ * @mark is an xa_mark_t; a small number indicating one of the mark bits.
+ * @node refers to an xa_node; usually the primary one being operated on by
+ * this function.
+ * @offset is the index into the slots array inside an xa_node.
+ * @parent refers to the @xa_node closer to the head than @node.
+ * @entry refers to something stored in a slot in the xarray
+ */
+
+/**
+ * xa_init_flags() - Initialise an empty XArray with flags.
+ * @xa: XArray.
+ * @flags: XA_FLAG values.
+ *
+ * If you need to initialise an XArray with special flags (eg you need
+ * to take the lock from interrupt context), use this function instead
+ * of xa_init().
+ *
+ * Context: Any context.
+ */
+void xa_init_flags(struct xarray *xa, gfp_t flags)
+{
+        spin_lock_init(&xa->xa_lock);
+        xa->xa_flags = flags;
+        xa->xa_head = NULL;
+}
+EXPORT_SYMBOL(xa_init_flags);