[PATCH 2/2] XArray: Convert IDR and add test suite

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



From: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>

The test suite for the xarray is still quite modest, but converting
the IDR and the IDA to use the xarray lets me use the IDR & IDA test
suites to test the xarray.  They have been very helpful in finding bugs
(and poor design decisions).

Signed-off-by: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>
---
 include/linux/idr.h                            | 136 ++-----
 lib/idr.c                                      | 503 +++++++++++++++----------
 lib/radix-tree.c                               | 169 +--------
 tools/include/asm/bug.h                        |   4 +
 tools/include/linux/kernel.h                   |   1 +
 tools/include/linux/spinlock.h                 |   7 +-
 tools/testing/radix-tree/.gitignore            |   4 +-
 tools/testing/radix-tree/Makefile              |  34 +-
 tools/testing/radix-tree/{idr-test.c => idr.c} |  37 +-
 tools/testing/radix-tree/linux.c               |   2 +-
 tools/testing/radix-tree/linux/radix-tree.h    |   5 -
 tools/testing/radix-tree/linux/rcupdate.h      |   2 +
 tools/testing/radix-tree/linux/xarray.h        |   1 +
 tools/testing/radix-tree/test.c                |  59 +--
 tools/testing/radix-tree/test.h                |  48 ++-
 tools/testing/radix-tree/xarray.c              | 241 ++++++++++++
 16 files changed, 712 insertions(+), 541 deletions(-)
 rename tools/testing/radix-tree/{idr-test.c => idr.c} (91%)
 create mode 100644 tools/testing/radix-tree/linux/xarray.h
 create mode 100644 tools/testing/radix-tree/xarray.c

diff --git a/include/linux/idr.h b/include/linux/idr.h
index bf70b3ef0a07..681cc6e7591f 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -9,100 +9,58 @@
  * tables.
  */
 
-#ifndef __IDR_H__
-#define __IDR_H__
+#ifndef _LINUX_IDR_H
+#define _LINUX_IDR_H
 
-#include <linux/radix-tree.h>
+#include <linux/xarray.h>
 #include <linux/gfp.h>
 #include <linux/percpu.h>
+#include <linux/preempt.h>
 
 struct idr {
-	struct radix_tree_root	idr_rt;
-	unsigned int		idr_next;
+	struct xarray	idxa;
 };
 
-/*
- * The IDR API does not expose the tagging functionality of the radix tree
- * to users.  Use tag 0 to track whether a node has free space below it.
- */
-#define IDR_FREE	0
-
-/* Set the IDR flag and the IDR_FREE tag */
-#define IDR_RT_MARKER		((__force gfp_t)(3 << __GFP_BITS_SHIFT))
-
-#define IDR_INIT							\
-{									\
-	.idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER)			\
-}
-#define DEFINE_IDR(name)	struct idr name = IDR_INIT
-
-/**
- * idr_get_cursor - Return the current position of the cyclic allocator
- * @idr: idr handle
- *
- * The value returned is the value that will be next returned from
- * idr_alloc_cyclic() if it is free (otherwise the search will start from
- * this position).
- */
-static inline unsigned int idr_get_cursor(const struct idr *idr)
-{
-	return READ_ONCE(idr->idr_next);
-}
-
-/**
- * idr_set_cursor - Set the current position of the cyclic allocator
- * @idr: idr handle
- * @val: new position
- *
- * The next call to idr_alloc_cyclic() will return @val if it is free
- * (otherwise the search will start from this position).
- */
-static inline void idr_set_cursor(struct idr *idr, unsigned int val)
-{
-	WRITE_ONCE(idr->idr_next, val);
+#define IDR_INIT(name)					\
+{							\
+	.idxa = XARRAY_FREE_INIT(name.idxa)		\
 }
+#define DEFINE_IDR(name)	struct idr name = IDR_INIT(name)
+#define idr_init(idr) do {				\
+	*(idr) = IDR_INIT(#idr)				\
+} while (0)
 
 /**
  * DOC: idr sync
- * idr synchronization (stolen from radix-tree.h)
+ * idr synchronization
  *
- * idr_find() is able to be called locklessly, using RCU. The caller must
- * ensure calls to this function are made within rcu_read_lock() regions.
- * Other readers (lock-free or otherwise) and modifications may be running
- * concurrently.
+ * The IDR manages its own locking, using irqsafe spinlocks for operations
+ * which modify the IDR and RCU for operations which do not.  The user of
+ * the IDR may choose to wrap accesses to it in another lock if it needs
+ * to guarantee the IDR does not change during a read access.
  *
- * It is still required that the caller manage the synchronization and
- * lifetimes of the items. So if RCU lock-free lookups are used, typically
- * this would mean that the items have their own locks, or are amenable to
- * lock-free access; and that the items are freed by RCU (or only freed after
- * having been deleted from the idr tree *and* a synchronize_rcu() grace
- * period).
+ * The caller must still manage the synchronization and lifetimes of the
+ * items.  So if RCU lock-free lookups are used, typically this would mean
+ * that the items have their own locks, or are amenable to lock-free access;
+ * and that the items are freed by RCU (or only freed after having been
+ * deleted from the IDR *and* a synchronize_rcu() grace period).
  */
 
-void idr_preload(gfp_t gfp_mask);
+void idr_preload(gfp_t);
 int idr_alloc(struct idr *, void *entry, int start, int end, gfp_t);
-int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t);
+int idr_alloc_cyclic(struct idr *, int *cursor, void *entry,
+		int start, int end, gfp_t);
+void *idr_find(const struct idr *, int id);
 int idr_for_each(const struct idr *,
 		 int (*fn)(int id, void *p, void *data), void *data);
-void *idr_get_next(struct idr *, int *nextid);
+void *idr_get_next(const struct idr *, int *nextid);
 void *idr_replace(struct idr *, void *, int id);
+void *idr_remove(struct idr *, int id);
 void idr_destroy(struct idr *);
 
-static inline void *idr_remove(struct idr *idr, int id)
-{
-	return radix_tree_delete_item(&idr->idr_rt, id, NULL);
-}
-
-static inline void idr_init(struct idr *idr)
-{
-	INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
-	idr->idr_next = 0;
-}
-
 static inline bool idr_is_empty(const struct idr *idr)
 {
-	return radix_tree_empty(&idr->idr_rt) &&
-		radix_tree_tagged(&idr->idr_rt, IDR_FREE);
+	return xa_empty(&idr->idxa);
 }
 
 /**
@@ -117,23 +75,6 @@ static inline void idr_preload_end(void)
 }
 
 /**
- * idr_find - return pointer for given id
- * @idr: idr handle
- * @id: lookup key
- *
- * Return the pointer given the id it has been registered with.  A %NULL
- * return indicates that @id is not valid or you passed %NULL in
- * idr_get_new().
- *
- * This function can be called under rcu_read_lock(), given that the leaf
- * pointers lifetimes are correctly managed.
- */
-static inline void *idr_find(const struct idr *idr, int id)
-{
-	return radix_tree_lookup(&idr->idr_rt, id);
-}
-
-/**
  * idr_for_each_entry - iterate over an idr's elements of a given type
  * @idr:     idr handle
  * @entry:   the type * to use as cursor
@@ -175,13 +116,13 @@ struct ida_bitmap {
 DECLARE_PER_CPU(struct ida_bitmap *, ida_bitmap);
 
 struct ida {
-	struct radix_tree_root	ida_rt;
+	struct xarray idxa;
 };
 
-#define IDA_INIT	{						\
-	.ida_rt = RADIX_TREE_INIT(IDR_RT_MARKER | GFP_NOWAIT),		\
+#define IDA_INIT(name)	{				\
+	.idxa = XARRAY_FREE_INIT(name.idxa)		\
 }
-#define DEFINE_IDA(name)	struct ida name = IDA_INIT
+#define DEFINE_IDA(name)	struct ida name = IDA_INIT(name)
 
 int ida_pre_get(struct ida *ida, gfp_t gfp_mask);
 int ida_get_new_above(struct ida *ida, int starting_id, int *p_id);
@@ -190,12 +131,7 @@ void ida_destroy(struct ida *ida);
 
 int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 		   gfp_t gfp_mask);
-void ida_simple_remove(struct ida *ida, unsigned int id);
-
-static inline void ida_init(struct ida *ida)
-{
-	INIT_RADIX_TREE(&ida->ida_rt, IDR_RT_MARKER | GFP_NOWAIT);
-}
+#define ida_simple_remove(ida, id) ida_remove(ida, id);
 
 /**
  * ida_get_new - allocate new ID
@@ -211,6 +147,6 @@ static inline int ida_get_new(struct ida *ida, int *p_id)
 
 static inline bool ida_is_empty(const struct ida *ida)
 {
-	return radix_tree_empty(&ida->ida_rt);
+	return xa_empty(&ida->idxa);
 }
-#endif /* __IDR_H__ */
+#endif /* __LINUX_IDR_H */
diff --git a/lib/idr.c b/lib/idr.c
index b13682bb0a1c..c280f0ee9440 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -1,14 +1,94 @@
+#define XA_ADVANCED
+
 #include <linux/bitmap.h>
+#include <linux/err.h>
 #include <linux/export.h>
 #include <linux/idr.h>
+#include <linux/percpu.h>
+#include <linux/preempt.h>
+#include <linux/radix-tree.h>
 #include <linux/slab.h>
 #include <linux/spinlock.h>
+#include <linux/xarray.h>
 
 DEFINE_PER_CPU(struct ida_bitmap *, ida_bitmap);
-static DEFINE_SPINLOCK(simple_ida_lock);
+
+static inline void *idr_null(void *entry)
+{
+	return entry == XA_IDR_NULL ? NULL : entry;
+}
+
+/* Until we get the IDR preload API fixed */
+struct radix_tree_preload {
+	unsigned nr;
+	struct radix_tree_node *nodes;
+};
+DECLARE_PER_CPU(struct radix_tree_preload, radix_tree_preloads);
+
+static bool idr_nomem(struct xa_state *xas, gfp_t gfp)
+{
+	struct radix_tree_preload *rtp;
+
+	BUILD_BUG_ON(sizeof(struct radix_tree_node) != sizeof(struct xa_node));
+	if (xas->xa_node != ERR_PTR(-ENOMEM))
+		return false;
+	xas->xa_alloc = kmem_cache_alloc(xa_node_cache, gfp | __GFP_NOWARN);
+	if (xas->xa_alloc)
+		goto alloc;
+
+	rtp = this_cpu_ptr(&radix_tree_preloads);
+	if (!rtp->nr)
+		return false;
+	xas->xa_alloc = (struct xa_node *)rtp->nodes;
+	rtp->nodes = (struct radix_tree_node *)xas->xa_alloc->parent;
+	rtp->nr--;
+
+alloc:
+	xas->xa_node = XA_WALK_RESTART;
+	return true;
+}
+
+static int __idr_alloc(struct idr *idr, void *ptr, int start, int min,
+		int end, gfp_t gfp)
+{
+	struct xa_state xas;
+	unsigned long flags;
+	void *entry;
+	int id;
+	unsigned long max = (end > 0) ? end - 1 : INT_MAX;
+
+	if (WARN_ON_ONCE(xa_is_internal(ptr)))
+		return -EINVAL;
+	if (!ptr)
+		ptr = XA_IDR_NULL;
+
+	xas_init(&xas, start);
+	do {
+		xa_lock_irqsave(&idr->idxa, flags);
+		entry = xas_find_tag(&idr->idxa, &xas, max, XA_FREE_TAG);
+		if (entry == XA_WALK_END) {
+			if ((xas.xa_index > max) && (min < start)) {
+				xas_jump(&xas, min);
+				entry = xas_find_tag(&idr->idxa, &xas, max,
+							XA_FREE_TAG);
+			}
+			if (xas.xa_index > max)
+				xas_set_err(&xas, -ENOSPC);
+		}
+		xas_store(&idr->idxa, &xas, ptr);
+		xa_unlock_irqrestore(&idr->idxa, flags);
+	} while (idr_nomem(&xas, gfp));
+
+	id = xas.xa_index;
+	if (IS_ERR(xas.xa_node))
+		id = PTR_ERR(xas.xa_node);
+	xas_destroy(&xas);
+
+	return id;
+}
 
 /**
- * idr_alloc - allocate an id
+ * idr_alloc() - allocate an id
  * @idr: idr handle
  * @ptr: pointer to be associated with the new id
  * @start: the minimum id (inclusive)
@@ -21,34 +101,16 @@ static DEFINE_SPINLOCK(simple_ida_lock);
  * Note that @end is treated as max when <= 0.  This is to always allow
  * using @start + N as @end as long as N is inside integer range.
  *
- * Simultaneous modifications to the @idr are not allowed and should be
- * prevented by the user, usually with a lock.  idr_alloc() may be called
- * concurrently with read-only accesses to the @idr, such as idr_find() and
- * idr_for_each_entry().
+ * Protected by the irqsafe spinlock
  */
 int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
 {
-	void __rcu **slot;
-	struct radix_tree_iter iter;
-
-	if (WARN_ON_ONCE(start < 0))
-		return -EINVAL;
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
-		return -EINVAL;
-
-	radix_tree_iter_init(&iter, start);
-	slot = idr_get_free(&idr->idr_rt, &iter, gfp, end);
-	if (IS_ERR(slot))
-		return PTR_ERR(slot);
-
-	radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
-	radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);
-	return iter.index;
+	return __idr_alloc(idr, ptr, start, start, end, gfp);
 }
 EXPORT_SYMBOL_GPL(idr_alloc);
 
 /**
- * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion
+ * idr_alloc_cyclic() - allocate new idr entry in a cyclical fashion
  * @idr: idr handle
  * @ptr: pointer to be associated with the new id
  * @start: the minimum id (inclusive)
@@ -58,27 +120,43 @@ EXPORT_SYMBOL_GPL(idr_alloc);
  * Allocates an ID larger than the last ID allocated if one is available.
  * If not, it will attempt to allocate the smallest ID that is larger or
  * equal to @start.
+ *
+ * Protected by the irqsafe spinlock
  */
-int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
+int idr_alloc_cyclic(struct idr *idr, int *cursor, void *ptr,
+		int start, int end, gfp_t gfp)
 {
-	int id, curr = idr->idr_next;
+	int curr = *cursor;
+	int id;
 
 	if (curr < start)
 		curr = start;
-
-	id = idr_alloc(idr, ptr, curr, end, gfp);
-	if ((id == -ENOSPC) && (curr > start))
-		id = idr_alloc(idr, ptr, start, curr, gfp);
+	id = __idr_alloc(idr, ptr, curr, start, end, gfp);
 
 	if (id >= 0)
-		idr->idr_next = id + 1U;
-
+		*cursor = id + 1U;
 	return id;
 }
-EXPORT_SYMBOL(idr_alloc_cyclic);
 
 /**
- * idr_for_each - iterate through all stored pointers
+ * idr_find() - return pointer for given id
+ * @idr: idr handle
+ * @id: lookup key
+ *
+ * Return the pointer given the id it has been registered with.  A %NULL
+ * return indicates that @id is not valid or you passed %NULL in
+ * idr_get_new().
+ *
+ * This function is protected by the RCU read lock.
+ */
+void *idr_find(const struct idr *idr, int id)
+{
+	return idr_null(xa_load(&idr->idxa, id));
+}
+EXPORT_SYMBOL(idr_find);
+
+/**
+ * idr_for_each() - iterate through all stored pointers
  * @idr: idr handle
  * @fn: function to be called for each pointer
  * @data: data passed to callback function
@@ -89,19 +167,19 @@ EXPORT_SYMBOL(idr_alloc_cyclic);
  * If @fn returns anything other than %0, the iteration stops and that
  * value is returned from this function.
  *
- * idr_for_each() can be called concurrently with idr_alloc() and
- * idr_remove() if protected by RCU.  Newly added entries may not be
- * seen and deleted entries may be seen, but adding and removing entries
- * will not cause other entries to be skipped, nor spurious ones to be seen.
+ * This iteration is protected by the RCU lock.  That means that the
+ * callback function may not sleep.  If your callback function must sleep,
+ * then you will have to use a mutex to prevent allocation / removal from
+ * modifying the IDR while the callback function is sleeping.
  */
 int idr_for_each(const struct idr *idr,
-		int (*fn)(int id, void *p, void *data), void *data)
+		int (*fn)(int id, void *ptr, void *data), void *data)
 {
-	struct radix_tree_iter iter;
-	void __rcu **slot;
+	unsigned long i = 0;
+	void *p;
 
-	radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) {
-		int ret = fn(iter.index, rcu_dereference_raw(*slot), data);
+	xa_for_each(&idr->idxa, p, i, INT_MAX) {
+		int ret = fn(i, p, data);
 		if (ret)
 			return ret;
 	}
@@ -111,7 +189,7 @@ int idr_for_each(const struct idr *idr,
 EXPORT_SYMBOL(idr_for_each);
 
 /**
- * idr_get_next - Find next populated entry
+ * idr_get_next() - Find next populated entry
  * @idr: idr handle
  * @nextid: Pointer to lowest possible ID to return
  *
@@ -119,55 +197,88 @@ EXPORT_SYMBOL(idr_for_each);
  * or equal to the value pointed to by @nextid.  On exit, @nextid is updated
  * to the ID of the found value.  To use in a loop, the value pointed to by
  * nextid must be incremented by the user.
+ *
+ * Protects itself with the irqsafe spinlock.
  */
-void *idr_get_next(struct idr *idr, int *nextid)
+void *idr_get_next(const struct idr *idr, int *id)
 {
-	struct radix_tree_iter iter;
-	void __rcu **slot;
-
-	slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid);
-	if (!slot)
-		return NULL;
+	unsigned long index = *id;
+	void *entry = xa_find(&idr->idxa, &index, INT_MAX);
 
-	*nextid = iter.index;
-	return rcu_dereference_raw(*slot);
+	*id = index;
+	return entry;
 }
 EXPORT_SYMBOL(idr_get_next);
 
 /**
- * idr_replace - replace pointer for given id
+ * idr_replace() - replace pointer for given id
  * @idr: idr handle
  * @ptr: New pointer to associate with the ID
  * @id: Lookup key
  *
  * Replace the pointer registered with an ID and return the old value.
- * This function can be called under the RCU read lock concurrently with
- * idr_alloc() and idr_remove() (as long as the ID being removed is not
- * the one being replaced!).
+ * This function takes the irqsafe spinlock.
  *
- * Returns: 0 on success.  %-ENOENT indicates that @id was not found.
+ * Return: 0 on success.  %-ENOENT indicates that @id was not found.
  * %-EINVAL indicates that @id or @ptr were not valid.
  */
 void *idr_replace(struct idr *idr, void *ptr, int id)
 {
-	struct radix_tree_node *node;
-	void __rcu **slot = NULL;
-	void *entry;
+	struct xa_state xas;
+	unsigned long flags;
+	void *curr;
 
-	if (WARN_ON_ONCE(id < 0))
-		return ERR_PTR(-EINVAL);
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
+	if (WARN_ON_ONCE(xa_is_internal(ptr)))
 		return ERR_PTR(-EINVAL);
+	if (!ptr)
+		ptr = XA_IDR_NULL;
+
+	xas_init(&xas, id);
+	xa_lock_irqsave(&idr->idxa, flags);
+	curr = xas_load(&idr->idxa, &xas);
+	if (curr && curr != XA_WALK_END)
+		curr = idr_null(xas_store(&idr->idxa, &xas, ptr));
+	else
+		curr = ERR_PTR(-ENOENT);
+	xa_unlock_irqrestore(&idr->idxa, flags);
+
+	return curr;
+}
+EXPORT_SYMBOL(idr_replace);
+
+/**
+ * idr_remove() - Free an allocated ID
+ * @idr: idr handle
+ * @id: Lookup key
+ *
+ * This function protects itself with the irqsafe spinlock.
+ *
+ * Return: The previous pointer associated with this ID.
+ */
+void *idr_remove(struct idr *idr, int id)
+{
+	return idr_null(xa_store(&idr->idxa, id, NULL, GFP_NOWAIT));
+}
+EXPORT_SYMBOL(idr_remove);
+
+/* Move to xarray.c? */
+static void xa_destroy(struct xarray *xa)
+{
+	struct xa_state xas;
+	unsigned long flags;
 
-	entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
-	if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))
-		return ERR_PTR(-ENOENT);
+	xas_init_order(&xas, 0, BITS_PER_LONG);
 
-	__radix_tree_replace(&idr->idr_rt, node, slot, ptr, NULL, NULL);
+	xa_lock_irqsave(xa, flags);
+	xas_store(xa, &xas, NULL);
+	xa_unlock_irqrestore(xa, flags);
+}
 
-	return entry;
+void idr_destroy(struct idr *idr)
+{
+	xa_destroy(&idr->idxa);
 }
-EXPORT_SYMBOL(idr_replace);
+EXPORT_SYMBOL(idr_destroy);
 
 /**
  * DOC: IDA description
@@ -181,9 +292,7 @@ EXPORT_SYMBOL(idr_replace);
  *
  * If you have more complex locking requirements, use a loop around
  * ida_pre_get() and ida_get_new() to allocate a new ID.  Then use
- * ida_remove() to free an ID.  You must make sure that ida_get_new() and
- * ida_remove() cannot be called at the same time as each other for the
- * same IDA.
+ * ida_remove() to free an ID.
  *
  * You can also use ida_get_new_above() if you need an ID to be allocated
  * above a particular number.  ida_destroy() can be used to dispose of an
@@ -197,28 +306,20 @@ EXPORT_SYMBOL(idr_replace);
 /*
  * Developer's notes:
  *
- * The IDA uses the functionality provided by the IDR & radix tree to store
- * bitmaps in each entry.  The IDR_FREE tag means there is at least one bit
+ * The IDA uses the functionality provided by the xarray to store bitmaps
+ * in each entry.  The XA_FREE_TAG tag means there is at least one bit
  * free, unlike the IDR where it means at least one entry is free.
  *
- * I considered telling the radix tree that each slot is an order-10 node
- * and storing the bit numbers in the radix tree, but the radix tree can't
+ * I considered telling the xarray that each slot is an order-10 node
+ * and storing the bit numbers in the xarray, but the xarray can't
  * allow a single multiorder entry at index 0, which would significantly
  * increase memory consumption for the IDA.  So instead we divide the index
- * by the number of bits in the leaf bitmap before doing a radix tree lookup.
+ * by the number of bits in the leaf bitmap before doing an xarray load.
  *
  * As an optimisation, if there are only a few low bits set in any given
- * leaf, instead of allocating a 128-byte bitmap, we use the 'exceptional
- * entry' functionality of the radix tree to store BITS_PER_LONG - 2 bits
- * directly in the entry.  By being really tricksy, we could store
- * BITS_PER_LONG - 1 bits, but there're diminishing returns after optimising
- * for 0-3 allocated IDs.
- *
- * We allow the radix tree 'exceptional' count to get out of date.  Nothing
- * in the IDA nor the radix tree code checks it.  If it becomes important
- * to maintain an accurate exceptional count, switch the rcu_assign_pointer()
- * calls to radix_tree_iter_replace() which will correct the exceptional
- * count.
+ * entry, instead of allocating a 128-byte bitmap, we use the 'exceptional
+ * entry' functionality of the xarray to store BITS_PER_LONG - 1 bits
+ * directly in the entry.
  *
  * The IDA always requires a lock to alloc/free.  If we add a 'test_bit'
  * equivalent, it will still need locking.  Going to RCU lookup would require
@@ -230,7 +331,7 @@ EXPORT_SYMBOL(idr_replace);
 #define IDA_MAX (0x80000000U / IDA_BITMAP_BITS)
 
 /**
- * ida_get_new_above - allocate new ID above or equal to a start id
+ * ida_get_new_above() - allocate new ID above or equal to a start id
  * @ida: ida handle
  * @start: id to start search at
  * @id: pointer to the allocated handle
@@ -249,52 +350,55 @@ EXPORT_SYMBOL(idr_replace);
  */
 int ida_get_new_above(struct ida *ida, int start, int *id)
 {
-	struct radix_tree_root *root = &ida->ida_rt;
-	void __rcu **slot;
-	struct radix_tree_iter iter;
+	struct xarray *xa = &ida->idxa;
+	struct xa_state xas;
+	unsigned long flags;
 	struct ida_bitmap *bitmap;
 	unsigned long index;
 	unsigned bit, ebit;
 	int new;
+	bool retry;
 
 	index = start / IDA_BITMAP_BITS;
 	bit = start % IDA_BITMAP_BITS;
-	ebit = bit + RADIX_TREE_EXCEPTIONAL_SHIFT;
-
-	slot = radix_tree_iter_init(&iter, index);
-	for (;;) {
-		if (slot)
-			slot = radix_tree_next_slot(slot, &iter,
-						RADIX_TREE_ITER_TAGGED);
-		if (!slot) {
-			slot = idr_get_free(root, &iter, GFP_NOWAIT, IDA_MAX);
-			if (IS_ERR(slot)) {
-				if (slot == ERR_PTR(-ENOMEM))
-					return -EAGAIN;
-				return PTR_ERR(slot);
-			}
-		}
-		if (iter.index > index) {
+	ebit = bit + 1;
+
+	xas_init(&xas, index);
+	xa_lock_irqsave(xa, flags);
+	do {
+		retry = false;
+		bitmap = xas_find_tag(xa, &xas, IDA_MAX, XA_FREE_TAG);
+		if (xas.xa_index > IDA_MAX)
+			goto nospc;
+		if (xas.xa_index > index) {
 			bit = 0;
-			ebit = RADIX_TREE_EXCEPTIONAL_SHIFT;
+			ebit = 1;
 		}
-		new = iter.index * IDA_BITMAP_BITS;
-		bitmap = rcu_dereference_raw(*slot);
-		if (radix_tree_exception(bitmap)) {
+		new = xas.xa_index * IDA_BITMAP_BITS;
+		if (bitmap == XA_WALK_END) {
+			bitmap = NULL;
+		} else if (xa_is_exceptional(bitmap)) {
 			unsigned long tmp = (unsigned long)bitmap;
 			ebit = find_next_zero_bit(&tmp, BITS_PER_LONG, ebit);
 			if (ebit < BITS_PER_LONG) {
 				tmp |= 1UL << ebit;
-				rcu_assign_pointer(*slot, (void *)tmp);
-				*id = new + ebit - RADIX_TREE_EXCEPTIONAL_SHIFT;
-				return 0;
+				xas_store(xa, &xas, (void *)tmp);
+				xas_set_tag(xa, &xas, XA_FREE_TAG); /* Hmm */
+				bit = ebit - 1;
+				new += bit;
+				continue;
 			}
 			bitmap = this_cpu_xchg(ida_bitmap, NULL);
-			if (!bitmap)
-				return -EAGAIN;
+			if (!bitmap) {
+				bitmap = ERR_PTR(-EAGAIN);
+				break;
+			}
 			memset(bitmap, 0, sizeof(*bitmap));
-			bitmap->bitmap[0] = tmp >> RADIX_TREE_EXCEPTIONAL_SHIFT;
-			rcu_assign_pointer(*slot, bitmap);
+			bitmap->bitmap[0] = tmp >> 1;
+			xas_store(xa, &xas, bitmap);
+			if (xas_error(&xas))
+				bitmap = this_cpu_xchg(ida_bitmap, bitmap);
+			xas_set_tag(xa, &xas, XA_FREE_TAG); /* Hmm */
 		}
 
 		if (bitmap) {
@@ -302,113 +406,133 @@ int ida_get_new_above(struct ida *ida, int start, int *id)
 							IDA_BITMAP_BITS, bit);
 			new += bit;
 			if (new < 0)
-				return -ENOSPC;
-			if (bit == IDA_BITMAP_BITS)
+				goto nospc;
+			if (bit == IDA_BITMAP_BITS) {
+				retry = true;
+				xas_jump(&xas, xas.xa_index + 1);
 				continue;
+			}
 
 			__set_bit(bit, bitmap->bitmap);
 			if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))
-				radix_tree_iter_tag_clear(root, &iter,
-								IDR_FREE);
+				xas_clear_tag(xa, &xas, XA_FREE_TAG);
+			break;
 		} else {
 			new += bit;
 			if (new < 0)
-				return -ENOSPC;
+				goto nospc;
 			if (ebit < BITS_PER_LONG) {
-				bitmap = (void *)((1UL << ebit) |
-						RADIX_TREE_EXCEPTIONAL_ENTRY);
-				radix_tree_iter_replace(root, &iter, slot,
-						bitmap);
-				*id = new;
-				return 0;
+				bitmap = xa_mk_exceptional(1UL << bit);
+				xas_store(xa, &xas, bitmap);
+				xas_set_tag(xa, &xas, XA_FREE_TAG); /* Hmm */
+				continue;
 			}
 			bitmap = this_cpu_xchg(ida_bitmap, NULL);
-			if (!bitmap)
-				return -EAGAIN;
+			if (!bitmap) {
+				bitmap = ERR_PTR(-EAGAIN);
+				break;
+			}
 			memset(bitmap, 0, sizeof(*bitmap));
 			__set_bit(bit, bitmap->bitmap);
-			radix_tree_iter_replace(root, &iter, slot, bitmap);
+			xas_store(xa, &xas, bitmap);
+			if (xas_error(&xas))
+				bitmap = this_cpu_xchg(ida_bitmap, bitmap);
+			xas_set_tag(xa, &xas, XA_FREE_TAG); /* Hmm */
 		}
-
-		*id = new;
-		return 0;
-	}
+	} while (retry || idr_nomem(&xas, GFP_NOWAIT));
+	xa_unlock_irqrestore(xa, flags);
+
+	if (IS_ERR(bitmap))
+		return PTR_ERR(bitmap);
+	if (xas_error(&xas) == -ENOMEM)
+		return -EAGAIN;
+	*id = new;
+	return 0;
+nospc:
+	xa_unlock_irqrestore(xa, flags);
+	return -ENOSPC;
 }
 EXPORT_SYMBOL(ida_get_new_above);
 
 /**
- * ida_remove - Free the given ID
+ * ida_remove() - Free the given ID
  * @ida: ida handle
  * @id: ID to free
  *
- * This function should not be called at the same time as ida_get_new_above().
+ * This function is protected by the irqsafe spinlock.
  */
 void ida_remove(struct ida *ida, int id)
 {
-	unsigned long index = id / IDA_BITMAP_BITS;
-	unsigned offset = id % IDA_BITMAP_BITS;
+	struct xarray *xa = &ida->idxa;
+	struct xa_state xas;
+	unsigned long flags;
 	struct ida_bitmap *bitmap;
+	unsigned long index = id / IDA_BITMAP_BITS;
+	unsigned bit = id % IDA_BITMAP_BITS;
 	unsigned long *btmp;
-	struct radix_tree_iter iter;
-	void __rcu **slot;
 
-	slot = radix_tree_iter_lookup(&ida->ida_rt, &iter, index);
-	if (!slot)
+	xas_init(&xas, index);
+	xa_lock_irqsave(xa, flags);
+	bitmap = xas_load(xa, &xas);
+	if (bitmap == XA_WALK_END)
 		goto err;
-
-	bitmap = rcu_dereference_raw(*slot);
-	if (radix_tree_exception(bitmap)) {
-		btmp = (unsigned long *)slot;
-		offset += RADIX_TREE_EXCEPTIONAL_SHIFT;
-		if (offset >= BITS_PER_LONG)
+	if (xa_is_exceptional(bitmap)) {
+		btmp = (unsigned long *)&bitmap;
+		bit++;
+		if (bit >= BITS_PER_LONG)
 			goto err;
 	} else {
 		btmp = bitmap->bitmap;
 	}
-	if (!test_bit(offset, btmp))
-		goto err;
 
-	__clear_bit(offset, btmp);
-	radix_tree_iter_tag_set(&ida->ida_rt, &iter, IDR_FREE);
-	if (radix_tree_exception(bitmap)) {
-		if (rcu_dereference_raw(*slot) ==
-					(void *)RADIX_TREE_EXCEPTIONAL_ENTRY)
-			radix_tree_iter_delete(&ida->ida_rt, &iter, slot);
+	if (!test_bit(bit, btmp))
+		goto err;
+	__clear_bit(bit, btmp);
+	if (xa_is_exceptional(bitmap)) {
+		if (xa_exceptional_value(bitmap) == 0)
+			bitmap = NULL;
+		xas_store(xa, &xas, bitmap);
+		xas_set_tag(xa, &xas, XA_FREE_TAG); /* Hmm */
 	} else if (bitmap_empty(btmp, IDA_BITMAP_BITS)) {
 		kfree(bitmap);
-		radix_tree_iter_delete(&ida->ida_rt, &iter, slot);
+		xas_store(xa, &xas, NULL);
+	} else {
+		xas_set_tag(xa, &xas, XA_FREE_TAG);
 	}
+	xa_unlock_irqrestore(xa, flags);
 	return;
  err:
+	xa_unlock_irqrestore(xa, flags);
 	WARN(1, "ida_remove called for id=%d which is not allocated.\n", id);
 }
 EXPORT_SYMBOL(ida_remove);
 
 /**
- * ida_destroy - Free the contents of an ida
+ * ida_destroy() - Free the contents of an ida
  * @ida: ida handle
  *
  * Calling this function releases all resources associated with an IDA.  When
- * this call returns, the IDA is empty and can be reused or freed.  The caller
- * should not allow ida_remove() or ida_get_new_above() to be called at the
- * same time.
+ * this call returns, the IDA is empty and can be reused or freed.
  */
 void ida_destroy(struct ida *ida)
 {
-	struct radix_tree_iter iter;
-	void __rcu **slot;
+	struct xa_state xas;
+	unsigned long flags;
+	struct ida_bitmap *bitmap;
 
-	radix_tree_for_each_slot(slot, &ida->ida_rt, &iter, 0) {
-		struct ida_bitmap *bitmap = rcu_dereference_raw(*slot);
-		if (!radix_tree_exception(bitmap))
+	xas_init(&xas, 0);
+	xa_lock_irqsave(&ida->idxa, flags);
+	xas_for_each(&ida->idxa, &xas, bitmap, ~0UL) {
+		if (!xa_is_exceptional(bitmap))
 			kfree(bitmap);
-		radix_tree_iter_delete(&ida->ida_rt, &iter, slot);
+		xas_store(&ida->idxa, &xas, NULL);
 	}
+	xa_unlock_irqrestore(&ida->idxa, flags);
 }
 EXPORT_SYMBOL(ida_destroy);
 
 /**
- * ida_simple_get - get a new id.
+ * ida_simple_get() - get a new id.
  * @ida: the (initialized) ida.
  * @start: the minimum id (inclusive, < 0x8000000)
  * @end: the maximum id (exclusive, < 0x8000000 or 0)
@@ -416,18 +540,12 @@ EXPORT_SYMBOL(ida_destroy);
  *
  * Allocates an id in the range start <= id < end, or returns -ENOSPC.
  * On memory allocation failure, returns -ENOMEM.
- *
- * Compared to ida_get_new_above() this function does its own locking, and
- * should be used unless there are special requirements.
- *
- * Use ida_simple_remove() to get rid of an id.
  */
 int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 		   gfp_t gfp_mask)
 {
 	int ret, id;
 	unsigned int max;
-	unsigned long flags;
 
 	BUG_ON((int)start < 0);
 	BUG_ON((int)end < 0);
@@ -440,10 +558,6 @@ int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 	}
 
 again:
-	if (!ida_pre_get(ida, gfp_mask))
-		return -ENOMEM;
-
-	spin_lock_irqsave(&simple_ida_lock, flags);
 	ret = ida_get_new_above(ida, start, &id);
 	if (!ret) {
 		if (id > max) {
@@ -453,32 +567,13 @@ int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 			ret = id;
 		}
 	}
-	spin_unlock_irqrestore(&simple_ida_lock, flags);
 
-	if (unlikely(ret == -EAGAIN))
+	if (unlikely(ret == -EAGAIN)) {
+		if (!ida_pre_get(ida, gfp_mask))
+			return -ENOMEM;
 		goto again;
+	}
 
 	return ret;
 }
 EXPORT_SYMBOL(ida_simple_get);
-
-/**
- * ida_simple_remove - remove an allocated id.
- * @ida: the (initialized) ida.
- * @id: the id returned by ida_simple_get.
- *
- * Use to release an id allocated with ida_simple_get().
- *
- * Compared to ida_remove() this function does its own locking, and should be
- * used unless there are special requirements.
- */
-void ida_simple_remove(struct ida *ida, unsigned int id)
-{
-	unsigned long flags;
-
-	BUG_ON((int)id < 0);
-	spin_lock_irqsave(&simple_ida_lock, flags);
-	ida_remove(ida, id);
-	spin_unlock_irqrestore(&simple_ida_lock, flags);
-}
-EXPORT_SYMBOL(ida_simple_remove);
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 9c0fa4df736b..8d2563097133 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -269,13 +269,6 @@ static inline unsigned long node_maxindex(const struct radix_tree_node *node)
 	return shift_maxindex(node->shift);
 }
 
-static unsigned long next_index(unsigned long index,
-				const struct radix_tree_node *node,
-				unsigned long offset)
-{
-	return (index & ~node_maxindex(node)) + (offset << node->shift);
-}
-
 #ifndef __KERNEL__
 static void dump_node(struct radix_tree_node *node, unsigned long index)
 {
@@ -319,54 +312,6 @@ static void radix_tree_dump(struct radix_tree_root *root)
 		return;
 	dump_node(entry_to_node(root->rnode), 0);
 }
-
-static void dump_ida_node(void *entry, unsigned long index)
-{
-	unsigned long i;
-
-	if (!entry)
-		return;
-
-	if (radix_tree_is_internal_node(entry)) {
-		struct radix_tree_node *node = entry_to_node(entry);
-
-		pr_debug("ida node: %p offset %d indices %lu-%lu parent %p free %lx shift %d count %d\n",
-			node, node->offset, index * IDA_BITMAP_BITS,
-			((index | node_maxindex(node)) + 1) *
-				IDA_BITMAP_BITS - 1,
-			node->parent, node->tags[0][0], node->shift,
-			node->count);
-		for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
-			dump_ida_node(node->slots[i],
-					index | (i << node->shift));
-	} else if (radix_tree_exceptional_entry(entry)) {
-		pr_debug("ida excp: %p offset %d indices %lu-%lu data %lx\n",
-				entry, (int)(index & RADIX_TREE_MAP_MASK),
-				index * IDA_BITMAP_BITS,
-				index * IDA_BITMAP_BITS + BITS_PER_LONG -
-					RADIX_TREE_EXCEPTIONAL_SHIFT,
-				(unsigned long)entry >>
-					RADIX_TREE_EXCEPTIONAL_SHIFT);
-	} else {
-		struct ida_bitmap *bitmap = entry;
-
-		pr_debug("ida btmp: %p offset %d indices %lu-%lu data", bitmap,
-				(int)(index & RADIX_TREE_MAP_MASK),
-				index * IDA_BITMAP_BITS,
-				(index + 1) * IDA_BITMAP_BITS - 1);
-		for (i = 0; i < IDA_BITMAP_LONGS; i++)
-			pr_cont(" %lx", bitmap->bitmap[i]);
-		pr_cont("\n");
-	}
-}
-
-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);
-}
 #endif
 
 /*
@@ -629,7 +574,7 @@ static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
 		maxshift += RADIX_TREE_MAP_SHIFT;
 
 	entry = rcu_dereference_raw(root->rnode);
-	if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE)))
+	if (!entry && (!is_idr(root) || root_tag_get(root, XA_FREE_TAG)))
 		goto out;
 
 	do {
@@ -639,10 +584,10 @@ static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
 			return -ENOMEM;
 
 		if (is_idr(root)) {
-			all_tag_set(node, IDR_FREE);
-			if (!root_tag_get(root, IDR_FREE)) {
-				tag_clear(node, IDR_FREE, 0);
-				root_tag_set(root, IDR_FREE);
+			all_tag_set(node, XA_FREE_TAG);
+			if (!root_tag_get(root, XA_FREE_TAG)) {
+				tag_clear(node, XA_FREE_TAG, 0);
+				root_tag_set(root, XA_FREE_TAG);
 			}
 		} else {
 			/* Propagate the aggregated tag info to the new child */
@@ -714,8 +659,8 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root,
 		 * one (root->rnode) as far as dependent read barriers go.
 		 */
 		root->rnode = (void __rcu *)child;
-		if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
-			root_tag_clear(root, IDR_FREE);
+		if (is_idr(root) && !tag_get(node, XA_FREE_TAG, 0))
+			root_tag_clear(root, XA_FREE_TAG);
 
 		/*
 		 * We have a dilemma here. The node's slot[0] must not be
@@ -1147,7 +1092,7 @@ static bool node_tag_get(const struct radix_tree_root *root,
 /*
  * IDR users want to be able to store NULL in the tree, so if the slot isn't
  * free, don't adjust the count, even if it's transitioning between NULL and
- * non-NULL.  For the IDA, we mark slots as being IDR_FREE while they still
+ * non-NULL.  For the IDA, we mark slots as being XA_FREE_TAG while they still
  * have empty bits, but it only stores NULL in slots when they're being
  * deleted.
  */
@@ -1157,7 +1102,7 @@ static int calculate_count(struct radix_tree_root *root,
 {
 	if (is_idr(root)) {
 		unsigned offset = get_slot_offset(node, slot);
-		bool free = node_tag_get(root, node, IDR_FREE, offset);
+		bool free = node_tag_get(root, node, XA_FREE_TAG, offset);
 		if (!free)
 			return 0;
 		if (!old)
@@ -1994,7 +1939,7 @@ static bool __radix_tree_delete(struct radix_tree_root *root,
 	int tag;
 
 	if (is_idr(root))
-		node_tag_set(root, node, IDR_FREE, offset);
+		node_tag_set(root, node, XA_FREE_TAG, offset);
 	else
 		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
 			node_tag_clear(root, node, tag, offset);
@@ -2041,7 +1986,7 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
 	void *entry;
 
 	entry = __radix_tree_lookup(root, index, &node, &slot);
-	if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
+	if (!entry && (!is_idr(root) || node_tag_get(root, node, XA_FREE_TAG,
 						get_slot_offset(node, slot))))
 		return NULL;
 
@@ -2136,98 +2081,6 @@ int ida_pre_get(struct ida *ida, gfp_t gfp)
 }
 EXPORT_SYMBOL(ida_pre_get);
 
-void __rcu **idr_get_free(struct radix_tree_root *root,
-			struct radix_tree_iter *iter, gfp_t gfp, int end)
-{
-	struct radix_tree_node *node = NULL, *child;
-	void __rcu **slot = (void __rcu **)&root->rnode;
-	unsigned long maxindex, start = iter->next_index;
-	unsigned long max = end > 0 ? end - 1 : INT_MAX;
-	unsigned int shift, offset = 0;
-
- grow:
-	shift = radix_tree_load_root(root, &child, &maxindex);
-	if (!radix_tree_tagged(root, IDR_FREE))
-		start = max(start, maxindex + 1);
-	if (start > max)
-		return ERR_PTR(-ENOSPC);
-
-	if (start > maxindex) {
-		int error = radix_tree_extend(root, gfp, start, shift);
-		if (error < 0)
-			return ERR_PTR(error);
-		shift = error;
-		child = rcu_dereference_raw(root->rnode);
-	}
-
-	while (shift) {
-		shift -= RADIX_TREE_MAP_SHIFT;
-		if (child == NULL) {
-			/* Have to add a child node.  */
-			child = radix_tree_node_alloc(gfp, node, root, shift,
-							offset, 0, 0);
-			if (!child)
-				return ERR_PTR(-ENOMEM);
-			all_tag_set(child, IDR_FREE);
-			rcu_assign_pointer(*slot, node_to_entry(child));
-			if (node)
-				node->count++;
-		} else if (!radix_tree_is_internal_node(child))
-			break;
-
-		node = entry_to_node(child);
-		offset = radix_tree_descend(node, &child, start);
-		if (!tag_get(node, IDR_FREE, offset)) {
-			offset = radix_tree_find_next_bit(node, IDR_FREE,
-							offset + 1);
-			start = next_index(start, node, offset);
-			if (start > max)
-				return ERR_PTR(-ENOSPC);
-			while (offset == RADIX_TREE_MAP_SIZE) {
-				offset = node->offset + 1;
-				node = node->parent;
-				if (!node)
-					goto grow;
-				shift = node->shift;
-			}
-			child = rcu_dereference_raw(node->slots[offset]);
-		}
-		slot = &node->slots[offset];
-	}
-
-	iter->index = start;
-	if (node)
-		iter->next_index = 1 + min(max, (start | node_maxindex(node)));
-	else
-		iter->next_index = 1;
-	iter->node = node;
-	__set_iter_shift(iter, shift);
-	set_iter_tags(iter, node, offset, IDR_FREE);
-
-	return slot;
-}
-
-/**
- * idr_destroy - release all internal memory from an IDR
- * @idr: idr handle
- *
- * After this function is called, the IDR is empty, and may be reused or
- * the data structure containing it may be freed.
- *
- * A typical clean-up sequence for objects stored in an idr tree will use
- * idr_for_each() to free all objects, if necessary, then idr_destroy() to
- * free the memory used to keep track of those objects.
- */
-void idr_destroy(struct idr *idr)
-{
-	struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.rnode);
-	if (radix_tree_is_internal_node(node))
-		radix_tree_free_nodes(node);
-	idr->idr_rt.rnode = NULL;
-	root_tag_set(&idr->idr_rt, IDR_FREE);
-}
-EXPORT_SYMBOL(idr_destroy);
-
 static void
 radix_tree_node_ctor(void *arg)
 {
diff --git a/tools/include/asm/bug.h b/tools/include/asm/bug.h
index 4790f047a89c..4eabf5597682 100644
--- a/tools/include/asm/bug.h
+++ b/tools/include/asm/bug.h
@@ -41,4 +41,8 @@
 	unlikely(__ret_warn_once);		\
 })
 
+#define VM_WARN_ON_ONCE WARN_ON_ONCE
+
+#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
+
 #endif /* _TOOLS_ASM_BUG_H */
diff --git a/tools/include/linux/kernel.h b/tools/include/linux/kernel.h
index 28607db02bd3..b2e4918f2b14 100644
--- a/tools/include/linux/kernel.h
+++ b/tools/include/linux/kernel.h
@@ -4,6 +4,7 @@
 #include <stdarg.h>
 #include <stddef.h>
 #include <assert.h>
+#include <limits.h>
 
 #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
 
diff --git a/tools/include/linux/spinlock.h b/tools/include/linux/spinlock.h
index 58397dcb19d6..703859ddadb4 100644
--- a/tools/include/linux/spinlock.h
+++ b/tools/include/linux/spinlock.h
@@ -1,5 +1,10 @@
 #define spinlock_t		pthread_mutex_t
-#define DEFINE_SPINLOCK(x)	pthread_mutex_t x = PTHREAD_MUTEX_INITIALIZER;
+#define DEFINE_SPINLOCK(x)	pthread_mutex_t x = PTHREAD_MUTEX_INITIALIZER
+#define __SPIN_LOCK_UNLOCKED(x)	PTHREAD_MUTEX_INITIALIZER
 
+#define spin_lock(x)			pthread_mutex_lock(x)
+#define spin_unlock(x)			pthread_mutex_unlock(x)
+#define spin_lock_irq(x)		pthread_mutex_lock(x)
+#define spin_unlock_irqr(x)		pthread_mutex_unlock(x)
 #define spin_lock_irqsave(x, f)		(void)f, pthread_mutex_lock(x)
 #define spin_unlock_irqrestore(x, f)	(void)f, pthread_mutex_unlock(x)
diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore
index d4706c0ffceb..7db5861132b5 100644
--- a/tools/testing/radix-tree/.gitignore
+++ b/tools/testing/radix-tree/.gitignore
@@ -1,6 +1,6 @@
 generated/map-shift.h
-idr.c
-idr-test
+idr
 main
 multiorder
 radix-tree.c
+xarray
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index f11315bedefc..4d9ce949dc93 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -1,10 +1,10 @@
 
-CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address
+CFLAGS += -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address
 LDFLAGS += -lpthread -lurcu
-TARGETS = main idr-test multiorder
-CORE_OFILES := radix-tree.o idr.o linux.o test.o find_bit.o
+TARGETS = main idr-test multiorder xarray
+CORE_OFILES := radix-tree.o idr.o xarray.o linux.o test.o find_bit.o
 OFILES = main.o $(CORE_OFILES) regression1.o regression2.o regression3.o \
-	 tag_check.o multiorder.o idr-test.o iteration_check.o benchmark.o
+	 tag_check.o multiorder.o iteration_check.o benchmark.o
 
 ifndef SHIFT
 	SHIFT=3
@@ -15,14 +15,22 @@ targets: mapshift $(TARGETS)
 main:	$(OFILES)
 	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o main
 
-idr-test: idr-test.o $(CORE_OFILES)
-	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o idr-test
+idr: $(CORE_OFILES)
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@
+idr.o: idr.c ../../../lib/idr.c
 
 multiorder: multiorder.o $(CORE_OFILES)
 	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o multiorder
 
+xarray: xarray.o linux.o test.o find_bit.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@
+xarray.o: ../../../lib/xarray.c
+
+xarray-idr: xarray.o idr-test.o linux.o idr-xarray.o test.o find_bit.o
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o $@
+
 clean:
-	$(RM) $(TARGETS) *.o radix-tree.c idr.c generated/map-shift.h
+	$(RM) $(TARGETS) *.o radix-tree.c generated/map-shift.h
 
 vpath %.c ../../lib
 
@@ -30,18 +38,18 @@ $(OFILES): *.h */*.h generated/map-shift.h \
 	../../include/linux/*.h \
 	../../include/asm/*.h \
 	../../../include/linux/radix-tree.h \
-	../../../include/linux/idr.h
+	../../../include/linux/idr.h \
+	../../../include/linux/xarray.h
 
 radix-tree.c: ../../../lib/radix-tree.c
 	sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
 
-idr.c: ../../../lib/idr.c
-	sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
-
 .PHONY: mapshift
 
-mapshift:
-	@if ! grep -qw $(SHIFT) generated/map-shift.h; then		\
+mapshift: generated/map-shift.h
+
+generated/map-shift.h:
+	@if ! grep -sqw $(SHIFT) generated/map-shift.h; then		\
 		echo "#define RADIX_TREE_MAP_SHIFT $(SHIFT)" >		\
 				generated/map-shift.h;			\
 	fi
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr.c
similarity index 91%
rename from tools/testing/radix-tree/idr-test.c
rename to tools/testing/radix-tree/idr.c
index a26098c6123d..8965217f689c 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr.c
@@ -11,15 +11,19 @@
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  * more details.
  */
+#include "../../../lib/idr.c"
+
 #include <linux/bitmap.h>
 #include <linux/idr.h>
 #include <linux/slab.h>
 #include <linux/kernel.h>
 #include <linux/errno.h>
 
+#define _TEST_H_NO_DEFINE_PRELOAD
 #include "test.h"
 
-#define DUMMY_PTR	((void *)0x12)
+//#define DUMMY_PTR	((void *)0x12)
+#define DUMMY_PTR	xa_mk_exceptional(10)
 
 int item_idr_free(int id, void *p, void *data)
 {
@@ -42,9 +46,10 @@ void idr_alloc_test(void)
 {
 	unsigned long i;
 	DEFINE_IDR(idr);
+	int cursor = 0;
 
-	assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0, 0x4000, GFP_KERNEL) == 0);
-	assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0x3ffd, 0x4000, GFP_KERNEL) == 0x3ffd);
+	assert(idr_alloc_cyclic(&idr, &cursor, DUMMY_PTR, 0, 0x4000, GFP_KERNEL) == 0);
+	assert(idr_alloc_cyclic(&idr, &cursor, DUMMY_PTR, 0x3ffd, 0x4000, GFP_KERNEL) == 0x3ffd);
 	idr_remove(&idr, 0x3ffd);
 	idr_remove(&idr, 0);
 
@@ -57,7 +62,7 @@ void idr_alloc_test(void)
 		else
 			item = item_create(i - 0x3fff, 0);
 
-		id = idr_alloc_cyclic(&idr, item, 1, 0x4000, GFP_KERNEL);
+		id = idr_alloc_cyclic(&idr, &cursor, item, 1, 0x4000, GFP_KERNEL);
 		assert(id == item->index);
 	}
 
@@ -83,8 +88,10 @@ void idr_replace_test(void)
  */
 void idr_null_test(void)
 {
-	int i;
 	DEFINE_IDR(idr);
+	void *entry;
+	unsigned long bits = 0;
+	int i;
 
 	assert(idr_is_empty(&idr));
 
@@ -95,6 +102,8 @@ void idr_null_test(void)
 
 	assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
 	assert(!idr_is_empty(&idr));
+	assert(idr_find(&idr, 0) == NULL);
+	assert(idr_find(&idr, 1) == NULL);
 	idr_destroy(&idr);
 	assert(idr_is_empty(&idr));
 
@@ -110,6 +119,10 @@ void idr_null_test(void)
 	assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 5);
 	idr_remove(&idr, 5);
 
+	idr_for_each_entry(&idr, entry, i)
+		bits |= (1UL << i);
+	assert(bits == 0x8);
+
 	for (i = 0; i < 9; i++) {
 		idr_remove(&idr, i);
 		assert(!idr_is_empty(&idr));
@@ -163,7 +176,7 @@ void idr_checks(void)
 		assert(idr_alloc(&idr, item, 0, 20000, GFP_KERNEL) == i);
 	}
 
-	assert(idr_alloc(&idr, DUMMY_PTR, 5, 30, GFP_KERNEL) < 0);
+	assert(idr_alloc(&idr, DUMMY_PTR, 5, 30, GFP_KERNEL) == -ENOSPC);
 
 	for (i = 0; i < 5000; i++)
 		item_idr_remove(&idr, i);
@@ -172,7 +185,6 @@ void idr_checks(void)
 
 	idr_for_each(&idr, item_idr_free, &idr);
 	idr_destroy(&idr);
-
 	assert(idr_is_empty(&idr));
 
 	idr_remove(&idr, 3);
@@ -295,16 +307,17 @@ void ida_check_conv(void)
 	for (i = 0; i < 1000000; i++) {
 		int err = ida_get_new(&ida, &id);
 		if (err == -EAGAIN) {
-			assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 2));
+			assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 1));
 			assert(ida_pre_get(&ida, GFP_KERNEL));
 			err = ida_get_new(&ida, &id);
 		} else {
-			assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 2));
+			assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 1));
 		}
 		assert(!err);
 		assert(id == i);
 	}
 	ida_destroy(&ida);
+	assert(ida_is_empty(&ida));
 }
 
 /*
@@ -432,13 +445,17 @@ void ida_checks(void)
 	radix_tree_cpu_dead(1);
 }
 
-int __weak main(void)
+int main(void)
 {
+	test_verbose = 2;
+	rcu_init();
+	xarray_init();
 	radix_tree_init();
 	idr_checks();
 	ida_checks();
 	rcu_barrier();
 	if (nr_allocated)
 		printf("nr_allocated = %d\n", nr_allocated);
+	fflush(stdout);
 	return 0;
 }
diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c
index cf48c8473f48..e7ecff9cfa10 100644
--- a/tools/testing/radix-tree/linux.c
+++ b/tools/testing/radix-tree/linux.c
@@ -28,7 +28,7 @@ void *kmem_cache_alloc(struct kmem_cache *cachep, int flags)
 {
 	struct radix_tree_node *node;
 
-	if (flags & __GFP_NOWARN)
+	if (!(flags & __GFP_DIRECT_RECLAIM))
 		return NULL;
 
 	pthread_mutex_lock(&cachep->lock);
diff --git a/tools/testing/radix-tree/linux/radix-tree.h b/tools/testing/radix-tree/linux/radix-tree.h
index bf1bb231f9b5..e9f1b859f45e 100644
--- a/tools/testing/radix-tree/linux/radix-tree.h
+++ b/tools/testing/radix-tree/linux/radix-tree.h
@@ -5,7 +5,6 @@
 #include "../../../../include/linux/radix-tree.h"
 
 extern int kmalloc_verbose;
-extern int test_verbose;
 
 static inline void trace_call_rcu(struct rcu_head *head,
 		void (*func)(struct rcu_head *head))
@@ -16,10 +15,6 @@ static inline void trace_call_rcu(struct rcu_head *head,
 	call_rcu(head, func);
 }
 
-#define printv(verbosity_level, fmt, ...) \
-	if(test_verbose >= verbosity_level) \
-		printf(fmt, ##__VA_ARGS__)
-
 #undef call_rcu
 #define call_rcu(x, y) trace_call_rcu(x, y)
 
diff --git a/tools/testing/radix-tree/linux/rcupdate.h b/tools/testing/radix-tree/linux/rcupdate.h
index f7129ea2a899..733952ddb01b 100644
--- a/tools/testing/radix-tree/linux/rcupdate.h
+++ b/tools/testing/radix-tree/linux/rcupdate.h
@@ -5,5 +5,7 @@
 
 #define rcu_dereference_raw(p) rcu_dereference(p)
 #define rcu_dereference_protected(p, cond) rcu_dereference(p)
+#define rcu_dereference_check(p, cond) rcu_dereference(p)
+#define RCU_INIT_POINTER(p, v)	p = v
 
 #endif
diff --git a/tools/testing/radix-tree/linux/xarray.h b/tools/testing/radix-tree/linux/xarray.h
new file mode 100644
index 000000000000..6b4a24916434
--- /dev/null
+++ b/tools/testing/radix-tree/linux/xarray.h
@@ -0,0 +1 @@
+#include "../../../include/linux/xarray.h"
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index 1a257d738a1e..293d59e130e1 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -8,25 +8,26 @@
 #include "test.h"
 
 struct item *
-item_tag_set(struct radix_tree_root *root, unsigned long index, int tag)
+item_tag_set(struct xarray *xa, unsigned long index, int tag)
 {
-	return radix_tree_tag_set(root, index, tag);
+	return xa_set_tag(xa, index, tag);
 }
 
 struct item *
-item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag)
+item_tag_clear(struct xarray *xa, unsigned long index, int tag)
 {
-	return radix_tree_tag_clear(root, index, tag);
+	return xa_clear_tag(xa, index, tag);
 }
 
-int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)
+int item_tag_get(struct xarray *xa, unsigned long index, int tag)
 {
-	return radix_tree_tag_get(root, index, tag);
+	return xa_get_tag(xa, index, tag);
 }
 
-int __item_insert(struct radix_tree_root *root, struct item *item)
+int __item_insert(struct xarray *xa, struct item *item)
 {
-	return __radix_tree_insert(root, item->index, item->order, item);
+	assert(!item->order);
+	return xa_replace(xa, item->index, item, NULL, GFP_KERNEL) == NULL;
 }
 
 struct item *item_create(unsigned long index, unsigned int order)
@@ -38,33 +39,33 @@ struct item *item_create(unsigned long index, unsigned int order)
 	return ret;
 }
 
-int item_insert_order(struct radix_tree_root *root, unsigned long index,
+int item_insert_order(struct xarray *xa, unsigned long index,
 			unsigned order)
 {
 	struct item *item = item_create(index, order);
-	int err = __item_insert(root, item);
+	int err = __item_insert(xa, item);
 	if (err)
 		free(item);
 	return err;
 }
 
-int item_insert(struct radix_tree_root *root, unsigned long index)
+int item_insert(struct xarray *xa, unsigned long index)
 {
-	return item_insert_order(root, index, 0);
+	return item_insert_order(xa, index, 0);
 }
 
 void item_sanity(struct item *item, unsigned long index)
 {
 	unsigned long mask;
-	assert(!radix_tree_is_internal_node(item));
+	assert(!xa_is_internal(item));
 	assert(item->order < BITS_PER_LONG);
 	mask = (1UL << item->order) - 1;
 	assert((item->index | mask) == (index | mask));
 }
 
-int item_delete(struct radix_tree_root *root, unsigned long index)
+int item_delete(struct xarray *xa, unsigned long index)
 {
-	struct item *item = radix_tree_delete(root, index);
+	struct item *item = xa_store(xa, index, NULL, GFP_NOWAIT);
 
 	if (item) {
 		item_sanity(item, index);
@@ -74,32 +75,33 @@ int item_delete(struct radix_tree_root *root, unsigned long index)
 	return 0;
 }
 
-void item_check_present(struct radix_tree_root *root, unsigned long index)
+void item_check_present(struct xarray *xa, unsigned long index)
 {
 	struct item *item;
 
-	item = radix_tree_lookup(root, index);
+	item = xa_load(xa, index);
 	assert(item != NULL);
 	item_sanity(item, index);
 }
 
-struct item *item_lookup(struct radix_tree_root *root, unsigned long index)
+struct item *item_lookup(struct xarray *xa, unsigned long index)
 {
-	return radix_tree_lookup(root, index);
+	return xa_load(xa, index);
 }
 
-void item_check_absent(struct radix_tree_root *root, unsigned long index)
+void item_check_absent(struct xarray *xa, unsigned long index)
 {
 	struct item *item;
 
-	item = radix_tree_lookup(root, index);
+	item = xa_load(xa, index);
 	assert(item == NULL);
 }
 
+#if 0
 /*
  * Scan only the passed (start, start+nr] for present items
  */
-void item_gang_check_present(struct radix_tree_root *root,
+void item_gang_check_present(struct xarray *xa,
 			unsigned long start, unsigned long nr,
 			int chunk, int hop)
 {
@@ -126,7 +128,7 @@ void item_gang_check_present(struct radix_tree_root *root,
 /*
  * Scan the entire tree, only expecting present items (start, start+nr]
  */
-void item_full_scan(struct radix_tree_root *root, unsigned long start,
+void item_full_scan(struct xarray *xa, unsigned long start,
 			unsigned long nr, int chunk)
 {
 	struct item *items[chunk];
@@ -156,7 +158,7 @@ void item_full_scan(struct radix_tree_root *root, unsigned long start,
 }
 
 /* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */
-int tag_tagged_items(struct radix_tree_root *root, pthread_mutex_t *lock,
+int tag_tagged_items(struct xarray *xa, pthread_mutex_t *lock,
 			unsigned long start, unsigned long end, unsigned batch,
 			unsigned iftag, unsigned thentag)
 {
@@ -190,7 +192,7 @@ int tag_tagged_items(struct radix_tree_root *root, pthread_mutex_t *lock,
 }
 
 /* Use the same pattern as find_swap_entry() in mm/shmem.c */
-unsigned long find_item(struct radix_tree_root *root, void *item)
+unsigned long find_item(struct xarray *xa, void *item)
 {
 	struct radix_tree_iter iter;
 	void **slot;
@@ -259,7 +261,7 @@ static int verify_node(struct radix_tree_node *slot, unsigned int tag,
 	return 0;
 }
 
-void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
+void verify_tag_consistency(struct xarray *xa, unsigned int tag)
 {
 	struct radix_tree_node *node = root->rnode;
 	if (!radix_tree_is_internal_node(node))
@@ -267,7 +269,7 @@ void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
 	verify_node(node, tag, !!root_tag_get(root, tag));
 }
 
-void item_kill_tree(struct radix_tree_root *root)
+void item_kill_tree(struct xarray *xa)
 {
 	struct radix_tree_iter iter;
 	void **slot;
@@ -294,7 +296,7 @@ void item_kill_tree(struct radix_tree_root *root)
 	assert(root->rnode == NULL);
 }
 
-void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
+void tree_verify_min_height(struct xarray *xa, int maxindex)
 {
 	unsigned shift;
 	struct radix_tree_node *node = root->rnode;
@@ -312,3 +314,4 @@ void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
 	else
 		assert(maxindex > 0);
 }
+#endif
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index b30e11d9d271..fa9d95086215 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -1,3 +1,6 @@
+#define XA_ADVANCED
+
+#include <linux/xarray.h>
 #include <linux/gfp.h>
 #include <linux/types.h>
 #include <linux/radix-tree.h>
@@ -9,26 +12,26 @@ struct item {
 };
 
 struct item *item_create(unsigned long index, unsigned int order);
-int __item_insert(struct radix_tree_root *root, struct item *item);
-int item_insert(struct radix_tree_root *root, unsigned long index);
-int item_insert_order(struct radix_tree_root *root, unsigned long index,
+int __item_insert(struct xarray *root, struct item *item);
+int item_insert(struct xarray *root, unsigned long index);
+int item_insert_order(struct xarray *root, unsigned long index,
 			unsigned order);
-int item_delete(struct radix_tree_root *root, unsigned long index);
-struct item *item_lookup(struct radix_tree_root *root, unsigned long index);
+int item_delete(struct xarray *root, unsigned long index);
+struct item *item_lookup(struct xarray *root, unsigned long index);
 
-void item_check_present(struct radix_tree_root *root, unsigned long index);
-void item_check_absent(struct radix_tree_root *root, unsigned long index);
-void item_gang_check_present(struct radix_tree_root *root,
+void item_check_present(struct xarray *root, unsigned long index);
+void item_check_absent(struct xarray *root, unsigned long index);
+void item_gang_check_present(struct xarray *root,
 			unsigned long start, unsigned long nr,
 			int chunk, int hop);
-void item_full_scan(struct radix_tree_root *root, unsigned long start,
+void item_full_scan(struct xarray *root, unsigned long start,
 			unsigned long nr, int chunk);
-void item_kill_tree(struct radix_tree_root *root);
+void item_kill_tree(struct xarray *root);
 
-int tag_tagged_items(struct radix_tree_root *, pthread_mutex_t *,
+int tag_tagged_items(struct xarray *, pthread_mutex_t *,
 			unsigned long start, unsigned long end, unsigned batch,
 			unsigned iftag, unsigned thentag);
-unsigned long find_item(struct radix_tree_root *, void *item);
+unsigned long find_item(struct xarray *, void *item);
 
 void tag_check(void);
 void multiorder_checks(void);
@@ -38,24 +41,31 @@ void idr_checks(void);
 void ida_checks(void);
 
 struct item *
-item_tag_set(struct radix_tree_root *root, unsigned long index, int tag);
+item_tag_set(struct xarray *root, unsigned long index, int tag);
 struct item *
-item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag);
-int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag);
-void tree_verify_min_height(struct radix_tree_root *root, int maxindex);
-void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag);
+item_tag_clear(struct xarray *root, unsigned long index, int tag);
+int item_tag_get(struct xarray *root, unsigned long index, int tag);
+void tree_verify_min_height(struct xarray *root, int maxindex);
+void verify_tag_consistency(struct xarray *root, unsigned int tag);
 
 extern int nr_allocated;
+extern int test_verbose;
+
+#define printv(verbosity_level, fmt, ...) \
+	if (test_verbose >= verbosity_level) \
+		printf(fmt, ##__VA_ARGS__)
 
 /* Normally private parts of lib/radix-tree.c */
 struct radix_tree_node *entry_to_node(void *ptr);
-void radix_tree_dump(struct radix_tree_root *root);
-int root_tag_get(struct radix_tree_root *root, unsigned int tag);
+void radix_tree_dump(struct xarray *root);
+int root_tag_get(struct xarray *root, unsigned int tag);
 unsigned long node_maxindex(struct radix_tree_node *);
 unsigned long shift_maxindex(unsigned int shift);
 int radix_tree_cpu_dead(unsigned int cpu);
+#ifndef _TEST_H_NO_DEFINE_PRELOAD
 struct radix_tree_preload {
 	unsigned nr;
 	struct radix_tree_node *nodes;
 };
 extern struct radix_tree_preload radix_tree_preloads;
+#endif
diff --git a/tools/testing/radix-tree/xarray.c b/tools/testing/radix-tree/xarray.c
new file mode 100644
index 000000000000..9a9156840d1d
--- /dev/null
+++ b/tools/testing/radix-tree/xarray.c
@@ -0,0 +1,241 @@
+#include <assert.h>
+#include <stdio.h>
+
+#define XA_DEBUG
+#include "../../../lib/xarray.c"
+
+#include "test.h"
+
+void xa_dump_entry(void *entry, unsigned long index)
+{
+	if (!entry)
+		return;
+
+	if (xa_is_exceptional(entry))
+		printf("%lu: exceptional %#lx\n", index,
+				xa_exceptional_value(entry));
+	else if (!xa_is_internal(entry))
+		printf("%lu: %p\n", index, entry);
+	else if (xa_is_node(entry)) {
+		unsigned long i;
+		struct xa_node *node = xa_node(entry);
+		printf("node %p %s %d parent %p shift %d count %d "
+			"exceptional %d tags %lx %lx %lx indices %lu-%lu\n",
+			node, node->parent ? "offset" : "max", node->offset,
+			node->parent, node->shift, node->count,
+			node->exceptional,
+			node->tags[0][0], node->tags[1][0], node->tags[2][0],
+			index, index |
+			(((unsigned long)XA_CHUNK_SIZE << node->shift) - 1));
+		for (i = 0; i < XA_CHUNK_SIZE; i++)
+			xa_dump_entry(node->slots[i],
+					index + (i << node->shift));
+	} else if (xa_is_retry(entry))
+		printf("%lu: retry (%ld)\n", index, xa_internal_value(entry));
+	else if (xa_is_sibling(entry))
+		printf("%lu: sibling (%ld)\n", index, xa_sibling_offset(entry));
+	else if (xa_is_cousin(entry))
+		printf("%lu: cousin (%ld)\n", index, xa_cousin_offset(entry));
+	else if (xa_is_idr_null(entry))
+		printf("%lu: IDR NULL (%ld)\n", index,
+						xa_internal_value(entry));
+	else
+		printf("%lu: UNKNOWN ENTRY (%p)\n", index, entry);
+}
+
+void xa_dump(struct xarray *xa)
+{
+	printf("xarray: %p %x %p\n", xa, xa->xa_flags, xa->xa_head);
+	xa_dump_entry(xa->xa_head, 0);
+}
+
+#define FOUR	(void *)4
+#define EIGHT	(void *)8
+
+void xas_walk_test(struct xarray *xa)
+{
+	struct xa_state xas;
+
+	xas_init(&xas, 0);
+//	assert(xas_load(xa, &xas) == NULL);
+}
+
+void xas_store_test(struct xarray *xa, unsigned long index)
+{
+	struct xa_state xas;
+	int err;
+	void *curr;
+
+	xas_init(&xas, index);
+	assert(!err);
+	do {
+		xa_lock(xa);
+		curr = xas_create(xa, &xas);
+		xa_unlock(xa);
+	} while (xas_nomem(&xas, GFP_KERNEL));
+	assert(curr == NULL);
+	curr = xas_store(xa, &xas, FOUR);
+	assert(curr == NULL);
+	if (index == 0)
+		assert(xa->xa_head == FOUR);
+	curr = xas_store(xa, &xas, NULL);
+	assert(curr == FOUR);
+	xas_destroy(&xas);
+	assert(xa_empty(xa));
+}
+
+static void multiorder_check(struct xarray *xa, unsigned long index, int order)
+{
+	struct xa_state xas;
+	unsigned long i;
+	unsigned long min = index & ~((1UL << order) - 1);
+	unsigned long max = min + (1UL << order);
+	void *curr, *entry = xa_mk_exceptional(index);
+
+	printv(2, "Multiorder index %ld, order %d\n", index, order);
+
+	xas_init_order(&xas, index, order);
+	do {
+		xa_lock(xa);
+		curr = xas_store(xa, &xas, entry);
+		xa_unlock(xa);
+	} while (xas_nomem(&xas, GFP_KERNEL));
+
+	assert(curr == NULL);
+	xas_destroy(&xas);
+
+	for (i = 0; i < min; i++)
+		assert(xa_load(xa, i) == NULL);
+	for (i = min; i < max; i++)
+		assert(xa_load(xa, i) == entry);
+	for (i = max; i < 2 * max; i++)
+		assert(xa_load(xa, i) == NULL);
+
+	xa_lock(xa);
+	assert(xas_store(xa, &xas, NULL) == entry);
+	xa_unlock(xa);
+
+	assert(xa_empty(xa));
+}
+
+void xas_tests(struct xarray *xa)
+{
+	int i;
+
+	assert(xa_empty(xa));
+	xas_walk_test(xa);
+	xas_store_test(xa, 0);
+	xas_store_test(xa, 1);
+
+	for (i = 0; i < 20; i++) {
+		multiorder_check(xa, 200, i);
+		multiorder_check(xa, 0, i);
+		multiorder_check(xa, (1UL << i) + 1, i);
+	}
+}
+
+void xa_get_test(struct xarray *xa)
+{
+	struct item *buf[10];
+	int i;
+
+	xa_store(xa, 0, item_create(0, 0), GFP_KERNEL);
+	xa_store(xa, 1, item_create(1, 0), GFP_KERNEL);
+	xa_store(xa, 7, item_create(7, 0), GFP_KERNEL);
+	xa_store(xa, 1UL << 63, item_create(1UL << 63, 0), GFP_KERNEL);
+
+	assert(xa_get_entries(xa, 0, (void **)buf, 10) == 4);
+	assert(buf[0]->index == 0);
+	assert(buf[1]->index == 1);
+	assert(buf[2]->index == 7);
+	assert(buf[3]->index == 1UL << 63);
+
+	for (i = 0; i < 4; i++)
+		kfree(xa_store(xa, buf[i]->index, NULL, GFP_KERNEL));
+	assert(xa_empty(xa));
+}
+
+void xa_tag_test(struct xarray *xa)
+{
+	struct item *buf[10];
+	int i;
+
+	assert(xa_store(xa, 0, item_create(0, 0), GFP_KERNEL) == NULL);
+	buf[9] = xa_set_tag(xa, 0, XA_TAG_2);
+	assert(buf[9]->index == 0);
+	assert(xa_get_tag(xa, 0, XA_TAG_2));
+	assert(xa_set_tag(xa, 1, XA_TAG_2) == NULL);
+	assert(!xa_get_tag(xa, 1, XA_TAG_2));
+	assert(!xa_get_tag(xa, 64, XA_TAG_2));
+	assert(!xa_get_tag(xa, 0, XA_TAG_1));
+
+	assert(xa_store(xa, 1, item_create(1, 0), GFP_KERNEL) == NULL);
+	assert(xa_store(xa, 7, item_create(7, 0), GFP_KERNEL) == NULL);
+	assert(xa_store(xa, 1UL << 63, item_create(1UL << 63, 0), GFP_KERNEL)
+			== NULL);
+	buf[9] = xa_set_tag(xa, 1, XA_TAG_1);
+	assert(buf[9]->index == 1);
+	buf[9] = xa_set_tag(xa, 7, XA_TAG_1);
+	assert(buf[9]->index == 7);
+
+	assert(xa_get_tagged(xa, 0, (void **)buf, 10, XA_TAG_1) == 2);
+	assert(buf[0]->index == 1);
+	assert(buf[1]->index == 7);
+
+	assert(!xa_get_tag(xa, 0, XA_TAG_1));
+	assert(xa_get_tag(xa, 7, XA_TAG_1));
+	assert(xa_set_tag(xa, 6, XA_TAG_1) == NULL);
+	printf("The next line should be a warning\n");
+	assert(xa_set_tag(xa, 7, 5) == ERR_PTR(-EINVAL));
+	assert(xa_clear_tag(xa, 7, 5) == ERR_PTR(-EINVAL));
+	assert(!xa_get_tag(xa, 7, 5));
+	printf("If there was no warning before this line, that is a bug\n");
+	assert(!xa_get_tag(xa, 7, XA_TAG_0));
+	assert(xa_clear_tag(xa, 7, XA_TAG_1) == buf[1]);
+	assert(!xa_get_tag(xa, 7, XA_TAG_1));
+	assert(!xa_get_tag(xa, 7, 5));
+
+	for (i = 0; i < 2; i++)
+		kfree(xa_store(xa, buf[i]->index, NULL, GFP_KERNEL));
+	assert(xa_get_entries(xa, 0, (void **)buf, 10) == 2);
+	for (i = 0; i < 2; i++)
+		kfree(xa_store(xa, buf[i]->index, NULL, GFP_KERNEL));
+	assert(xa_empty(xa));
+}
+
+void xa_tests(struct xarray *xa)
+{
+	assert(xa_load(xa, 0) == NULL);
+	assert(xa_load(xa, 1) == NULL);
+	assert(xa_load(xa, 2) == NULL);
+	assert(xa_load(xa, ~0) == NULL);
+	assert(xa_store(xa, 0, FOUR, GFP_KERNEL) == NULL);
+	assert(xa_store(xa, 0, EIGHT, GFP_KERNEL) == FOUR);
+	assert(xa_replace(xa, 0, NULL, FOUR, GFP_KERNEL) == EIGHT);
+	assert(xa_replace(xa, 0, NULL, FOUR, GFP_KERNEL) == EIGHT);
+	assert(xa_replace(xa, 0, NULL, EIGHT, GFP_KERNEL) == EIGHT);
+	assert(xa_load(xa, 0) == NULL);
+	assert(xa_load(xa, 1) == NULL);
+	assert(xa_store(xa, 1, FOUR, GFP_KERNEL) == NULL);
+	assert(xa_store(xa, 1, EIGHT, GFP_KERNEL) == FOUR);
+	assert(xa_store(xa, 1, NULL, GFP_KERNEL) == EIGHT);
+	assert(xa_empty(xa));
+
+	xa_get_test(xa);
+	xa_tag_test(xa);
+}
+
+int __weak main(int argc, char **argv)
+{
+	DEFINE_XARRAY(array);
+	test_verbose = 2;
+
+	rcu_init();
+	xarray_init();
+
+	xas_tests(&array);
+	xa_tests(&array);
+
+	rcu_barrier();
+	return 0;
+}
-- 
2.11.0





[Index of Archives]     [Linux Ext4 Filesystem]     [Union Filesystem]     [Filesystem Testing]     [Ceph Users]     [Ecryptfs]     [AutoFS]     [Kernel Newbies]     [Share Photos]     [Security]     [Netfilter]     [Bugtraq]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux Cachefs]     [Reiser Filesystem]     [Linux RAID]     [Samba]     [Device Mapper]     [CEPH Development]
  Powered by Linux