[PATCH 0/2] Introducing the eXtensible Array (xarray)

[PATCH 0/2] Introducing the eXtensible Array (xarray)

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

I wrote the xarray to replace the radix tree with a better API based
on observing how programmers are currently using the radix tree, and
on how (and why) they aren't.  Conceptually, an xarray is an array of
2^BITS_PER_LONG pointers which is initially full of NULL pointers.

This is the result of about two weeks worth of hacking.  There is much
more to do; I think the most important thing remaining is to start
working on converting the page cache from the radix tree to the xarray.
That will tell me where the API could be better.  I'm sending it out
now for feedback; I know there are bugs and some half-finished code,
but I'm interested in comments on the design direction.

Improvements the xarray has over the radix tree:

 - The radix tree provides operations like other trees do; 'insert' and
   'delete'.  But what users really want is an automatically resizing
   array, and so it makes more sense to give users an API that is like
   an array -- 'load' and 'store'.
 - Locking is part of the API.  This simplifies a lot of users who
   formerly had to manage their own locking just for the radix tree.
   It also improves code generation as we can now tell RCU that we're
   holding a lock and it doesn't need to generate as much fencing code.
   The other advantage is that tree nodes can be moved (not yet
   implemented).
 - GFP flags are now parameters to calls which may need to allocate
   memory.  The radix tree forced users to decide what the allocation
   flags would be at creation time.  It's much clearer to specify them
   at allocation time.  I know the MM people disapprove of the radix
   tree using the top bits of the GFP flags for its own purpose, so
   they'll like this aspect.
 - Memory is not preloaded; we don't tie up dozens of pages on the
   off chance that the slab allocator fails.  Instead, we drop the lock,
   allocate a new node and retry the operation.
 - The xarray provides a conditional-replace operation.  The radix tree
   forces users to roll their own (and at least four have).
 - Iterators now take a 'max' parameter.  That simplifies many users and
   will reduce the amount of iteration done.
 - Iteration can proceed backwards.  We only have one user for this, but
   since it's called as part of the pagefault readahead algorithm, that
   seemed worth mentioning.  Not fully implemented.
 - RCU-protected pointers are not exposed as part of the API.  There are
   some fun bugs where the page cache forgets to use rcu_dereference()
   in the current codebase.
 - Any function which wants it can now call the update_node() callback.
   There were a few places missing that I noticed as part of this rewrite.
 - Help the page cache to keep nrexceptional and nrpages up to date.
 - Exceptional entries may now be BITS_PER_LONG-1 in size, rather than the
   BITS_PER_LONG-2 that they had in the radix tree.  That gives us the
   extra bit we need to put huge page swap entries in the page cache.

The API comes in two parts, normal and advanced.  The normal API takes
care of the locking and memory allocation for you.  You can get the
value of a pointer by calling xa_load() and set the value of a pointer by
calling xa_store().  You can conditionally update the value of a pointer
by calling xa_replace().  Each pointer which isn't NULL can be tagged
with up to 3 bits of extra information, accessed through xa_get_tag(),
xa_set_tag() and xa_clear_tag().  You can copy batches of pointers out
of the array by calling xa_get_entries() or xa_get_tagged().  You can
iterate over pointers in the array by calling xa_find(), xa_next()
or xa_for_each().

The advanced API allows users to build their own operations.  You have
to take care of your own locking and handle memory allocation failures.
Most of the advanced operations are based around the xa_state which
keeps state between sub-operations.  Read the xarray.h header file for
more information on the advanced API, and see the implementation of the
normal API for examples of how to use the advanced API.

Those familiar with the radix tree may notice certain similarities between
the implementation of the xarray and the radix tree.  That's entirely
intentional, but the implementation will certainly adapt in the future.
For example, one of the impediments I see to using xarrays instead of
kvmalloced arrays is memory consumption, so I have a couple of ideas to
reduce memory usage for smaller arrays.

I have already reimplementated the IDR and the IDA based on the xarray.
They are roughly the same complexity as they were when implemented on
top of the radix tree (although much less intertwined).

When converting code from the radix tree to the xarray, the biggest thing
to bear in mind is that 'store' overwrites anything which happens to be
in the xarray.  Just like the assignment operator.  The equivalent to
the insert operation is to replace NULL with the new value.

A quick reference guide to help when converting radix tree code.
Functions which start 'xas' are XA_ADVANCED functions.

radix_tree_empty			xa_empty
__radix_tree_create			xas_create
__radix_tree_insert			xas_store
radix_tree_insert(x)			xa_replace(NULL, x)
__radix_tree_lookup			xas_load
radix_tree_lookup			xa_load
radix_tree_lookup_slot			xas_load
__radix_tree_replace			xas_store
radix_tree_iter_replace			xas_store
radix_tree_replace_slot			xas_store
__radix_tree_delete_node		xas_delete_node
radix_tree_delete_item			xa_replace
radix_tree_delete			xa_store(NULL)
radix_tree_clear_tags			xas_clear_tags
radix_tree_gang_lookup			xa_get_entries
radix_tree_gang_lookup_slot		xas_find (*1)
radix_tree_preload			(*3)
radix_tree_maybe_preload		(*3)
radix_tree_tag_set			xa_set_tag
radix_tree_tag_clear			xa_clear_tag
radix_tree_tag_get			xa_get_tag
radix_tree_iter_tag_set			xas_set_tag
radix_tree_gang_lookup_tag		xa_get_tagged
radix_tree_gang_lookup_tag_slot		xas_load (*2)
radix_tree_tagged			xa_tagged
radix_tree_preload_end			xas_preload_end
radix_tree_split_preload		(*3)
radix_tree_split			xas_split (*4)
radix_tree_join				xa_replace

(*1) All three users of radix_tree_gang_lookup_slot() are using it to
ensure that there are no entries in a given range.  
(*2) The one radix_tree_gang_lookup_tag_slot user should be using a
radix_tree_iter loop.  It can use an xas_for_each() loop, or even an
xa_for_each() loop.
(*3) I don't think we're going to need a preallocation API.  If we do
end up needing one, I have a plan that doesn't involve per-cpu
preallocation pools.
(*4) Not yet implemented


Matthew Wilcox (2):
  Add XArray
  XArray: Convert IDR and add test suite

 include/linux/idr.h                            |  136 +--
 include/linux/xarray.h                         |  764 ++++++++++++++
 lib/Makefile                                   |    3 +-
 lib/idr.c                                      |  503 +++++----
 lib/radix-tree.c                               |  169 +--
 lib/xarray.c                                   | 1305 ++++++++++++++++++++++++
 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 +++++
 19 files changed, 2783 insertions(+), 542 deletions(-)
 create mode 100644 include/linux/xarray.h
 create mode 100644 lib/xarray.c
 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

-- 
2.11.0

[PATCH 1/2] Add XArray

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

The xarray is an array of 2^BITS_PER_LONG pointers which handles its own
locking and memory allocation.  It is intended to replace the radix tree.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/xarray.h |  764 ++++++++++++++++++++++++++++
 lib/Makefile           |    3 +-
 lib/xarray.c           | 1305 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 2071 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/xarray.h
 create mode 100644 lib/xarray.c

diff --git a/include/linux/xarray.h b/include/linux/xarray.h
new file mode 100644
index 000000000000..646ff84b4444
--- /dev/null
+++ b/include/linux/xarray.h
@@ -0,0 +1,764 @@
+#ifndef _LINUX_XARRAY_H
+#define _LINUX_XARRAY_H
+/*
+ * eXtensible Arrays
+ * Copyright (c) 2017 Microsoft Corporation
+ * Author: Matthew Wilcox <mawilcox@microsoft.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ */
+
+/**
+ * An eXtensible Array is an array of pointers indexed by an unsigned
+ * long.  The xarray takes care of its own locking, using an irqsafe
+ * spinlock for operations that modify the array and RCU for operations
+ * which only read from the array.
+ *
+ * The xarray can store exceptional entries as well as pointers.
+ * Exceptional entries have a value between 0 and 2^(BITS_PER_LONG - 1).
+ * You cannot store arbitrary unsigned longs in the xarray as some
+ * values are reserved for internal use.  It is better to avoid storing
+ * IS_ERR() pointers in the array as it is hard to distinguish between
+ * xa_store() having failed to allocate memory, and a previously successful
+ * store of the entry ERR_PTR(-ENOMEM) in the array.
+ *
+ * A freshly initialised xarray is full of NULL pointers.  You can set
+ * the entry at any index by calling xa_store(), and get the value by
+ * calling xa_load().  There is no difference between an entry which has
+ * never been stored to and an entry which has most recently had NULL stored
+ * to it.  You can conditionally update the value of an entry by calling
+ * xa_replace().  Each entry which isn't NULL can be tagged with up to three
+ * bits of extra information, accessed through xa_get_tag(), xa_set_tag() and
+ * xa_clear_tag().  You can copy batches of entries out of the array by
+ * calling xa_get_entries() or xa_get_tagged().  You can iterate over present
+ * entries in the array by calling xa_find(), xa_next() or xa_for_each().
+ *
+ * There are two levels of API provided.  Normal and Advanced.  Define
+ * XA_ADVANCED before including this file to get access to the extra API.
+ * The advanced API has sharp edges and you can easily corrupt an xarray.
+ */
+
+#include <linux/bug.h>
+#include <linux/compiler.h>
+#include <linux/kernel.h>
+#include <linux/rcupdate.h>
+#include <linux/spinlock.h>
+
+/**
+ * struct xarray - The anchor of the XArray
+ * @xa_lock: Lock protecting writes to the array.
+ * @xa_flags: Internal XArray flags.
+ * @xa_head: The first pointer in the array.
+ *
+ * If all of the pointers in the array are NULL, @xa_head is a NULL pointer.
+ * If the only non-NULL pointer in the array is at index 0, @xa_head is that
+ * pointer.  If any other pointer in the array is non-NULL, @xa_head points
+ * to an @xa_node.
+ */
+struct xarray {
+	spinlock_t xa_lock;
+	unsigned int xa_flags;
+	void __rcu *xa_head;
+};
+
+#define __XARRAY_INIT(name, flags) {				\
+	.xa_lock = __SPIN_LOCK_UNLOCKED(name.xa_lock),		\
+	.xa_flags = flags,					\
+	.xa_head = NULL,					\
+}
+
+#define XARRAY_INIT(name) __XARRAY_INIT(name, 0)
+#define XARRAY_FREE_INIT(name) __XARRAY_INIT(name, XA_FLAG_TRACK_FREE | 1)
+
+#define DEFINE_XARRAY(name) struct xarray name = XARRAY_INIT(name)
+
+/*
+ * The low three bits of the flag field are used for storing the tags.
+ *
+ * The TRACK_FREE flag indicates that the XA_FREE_TAG tag is used to track
+ * free entries in the xarray.  If you set this flag, only tags 1 & 2
+ * are available for you to use.
+ */
+#define XA_FLAG_TRACK_FREE	(1 << 3)
+
+void *xa_load(const struct xarray *, unsigned long index);
+void *xa_store(struct xarray *, unsigned long index, void *entry, gfp_t);
+void *xa_replace(struct xarray *, unsigned long index,
+		void *entry, void *old, gfp_t);
+
+typedef unsigned __bitwise xa_tag_t;
+#define XA_TAG_0	((__force xa_tag_t)0U)
+#define XA_TAG_1	((__force xa_tag_t)1U)
+#define XA_TAG_2	((__force xa_tag_t)2U)
+
+#define XA_TAG_MAX	XA_TAG_2
+#define XA_FREE_TAG	XA_TAG_0
+
+/*
+ * The vast majority of users have a constant tag, so the compiler can
+ * optimise this away.
+ */
+static inline bool xa_bad_tag(xa_tag_t tag)
+{
+	return (WARN_ON_ONCE((__force unsigned)tag >
+				(__force unsigned)XA_TAG_MAX));
+}
+
+/**
+ * xa_tagged() - Inquire whether any entry in this array has a tag set
+ * @xa: Array
+ * @tag: Tag value
+ *
+ * Return: True if any entry has this tag set, false if no entry does.
+ */
+static inline bool xa_tagged(const struct xarray *xa, xa_tag_t tag)
+{
+	if (xa_bad_tag(tag))
+		return false;
+	return xa->xa_flags & (1 << (__force unsigned)tag);
+}
+
+bool __xa_get_tag(const struct xarray *, unsigned long index, xa_tag_t);
+void *__xa_set_tag(struct xarray *, unsigned long index, xa_tag_t);
+void *__xa_clear_tag(struct xarray *, unsigned long index, xa_tag_t);
+
+#define xa_get_tag(xa, index, tag) \
+	(!xa_bad_tag(tag) && __xa_get_tag(xa, index, tag))
+#define xa_set_tag(xa, index, tag) \
+	(xa_bad_tag(tag) ? ERR_PTR(-EINVAL) : __xa_set_tag(xa, index, tag))
+#define xa_clear_tag(xa, index, tag) \
+	(xa_bad_tag(tag) ? ERR_PTR(-EINVAL) : __xa_clear_tag(xa, index, tag))
+
+int xa_get_entries(const struct xarray *, unsigned long start, void **dst,
+		unsigned int n);
+int xa_get_tagged(const struct xarray *, unsigned long start, void **dst,
+		unsigned int n, xa_tag_t);
+
+/**
+ * xa_empty() - Determine if an array has any present entries
+ * @xa: Array
+ *
+ * Return: True if the array has no entries in it.
+ */
+static inline bool xa_empty(const struct xarray *xa)
+{
+	return xa->xa_head == NULL;
+}
+
+void *xa_find(const struct xarray *xa, unsigned long *index, unsigned long max);
+void *xa_next(const struct xarray *xa, unsigned long *index, unsigned long max);
+
+/**
+ * xa_for_each() - Iterate over a portion of an array
+ * @xa: Array
+ * @entry: Pointer retrieved from array
+ * @index: Index of pointer retrieved from the array
+ * @max: Maximum index to retrieve from array
+ *
+ * Initialise @index to the minimum index you want to retrieve from
+ * the array.  During the iteration, @entry will have the value of the
+ * pointer stored in @xa at @index.  The iteration will skip all NULL
+ * pointers in the array.  You may modify @index during the
+ * iteration if you want to skip indices.  It is safe to modify the
+ * array during the iteration.  At the end of the iteration, @entry will
+ * be set to NULL and @index will have a value less than or equal to max.
+ *
+ * xa_for_each() is O(n.log(n)) while xas_for_each() is O(n).  You have
+ * to handle your own locking with xas_for_each(), and if you have to unlock
+ * after each iteration, it will also end up being O(n.log(n)).
+ */
+#define xa_for_each(xa, entry, index, max) \
+	for (entry = xa_find(xa, &index, max); entry; \
+	     entry = xa_next(xa, &index, max))
+
+/**
+ * xa_mk_exceptional() - Create an exceptional entry
+ * @v: value to store in exceptional entry
+ */
+static inline void *xa_mk_exceptional(unsigned long v)
+{
+	WARN_ON(v > LONG_MAX);
+	return (void *)((v << 1) | 1);
+}
+
+/**
+ * xa_exceptional_value() - Get value stored in an exceptional entry
+ * @entry: Value stored in xarray
+ */
+static inline unsigned long xa_exceptional_value(void *entry)
+{
+	return (unsigned long)entry >> 1;
+}
+
+/**
+ * xa_is_exceptional() - Determine if an entry is exceptional
+ * @entry: Value stored in xarray
+ *
+ * Return: True if the entry is exceptional
+ */
+static inline bool xa_is_exceptional(void *entry)
+{
+	return (unsigned long)entry & 1;
+}
+
+#ifdef XA_ADVANCED
+
+#ifdef XA_DEBUG
+#define XA_BUG_ON(x) BUG_ON(x)
+#else
+#define XA_BUG_ON(x)
+#endif
+
+/* XXX: unused */
+typedef unsigned __bitwise xa_tags_t;
+
+#define xa_trylock(xa)		spin_trylock(&(xa)->xa_lock);
+#define xa_lock(xa)		spin_lock(&(xa)->xa_lock)
+#define xa_unlock(xa)		spin_unlock(&(xa)->xa_lock)
+#define xa_lock_irq(xa)		spin_lock_irq(&(xa)->xa_lock)
+#define xa_unlock_irq(xa)	spin_unlock_irq(&(xa)->xa_lock)
+#define xa_lock_irqsave(xa, flags) \
+				spin_lock_irqsave(&(xa)->xa_lock, flags)
+#define xa_unlock_irqrestore(xa, flags) \
+				spin_unlock_irqrestore(&(xa)->xa_lock, flags)
+
+/*
+ * The xarray is constructed out of a set of 'chunks' of pointers.  Choosing
+ * the best chunk size requires some tradeoffs.  A power of two recommends
+ * itself so that we can arrange the chunks into a tree and navigate based
+ * purely on shifts and masks.  Generally, the larger the better; as the
+ * number of slots per level of the tree increases, the less tall the tree
+ * needs to be.  But that needs to be balanced against the memory consumption
+ * of each node.  On a 64-bit system, xa_node is currently 576 bytes, and we
+ * get 7 of them per 4kB page.  If we doubled the number of slots per node,
+ * we'd get only 3 nodes per 4kB page.
+ */
+#define XA_CHUNK_SHIFT		6
+#define XA_CHUNK_SIZE		(1 << XA_CHUNK_SHIFT)
+#define XA_CHUNK_MASK		(XA_CHUNK_SIZE - 1)
+#define XA_MAX_TAGS		3
+#define XA_TAG_LONGS 		(XA_CHUNK_SIZE / BITS_PER_LONG)
+#define XA_PREALLOC_COUNT	((BITS_PER_LONG / XA_CHUNK_SHIFT) * 2 + 1)
+
+struct xa_node {
+	union {
+		unsigned char offset;
+		unsigned char max;
+	};
+	unsigned char shift;
+	unsigned char count;
+	unsigned char exceptional;
+	struct xa_node __rcu *parent;
+	struct xarray *array;
+	union {
+		struct list_head private_list;
+		struct rcu_head rcu_head;
+	};
+	unsigned long tags[XA_MAX_TAGS][XA_TAG_LONGS];
+	void __rcu *slots[XA_CHUNK_SIZE];
+};
+
+/*
+ * Entries in the xarray have three possible types:
+ * 1. Kernel pointers.  These have the bottom two bits clear.
+ * 2. Exceptional entries.  These have the bottom bit set.
+ * 3. Internal entries.  These have the bottom two bits equal to 10b.
+ *
+ * Internal entries can only be observed if you're using the advanced
+ * API; the normal API will not expose them to the user.
+ *
+ * There are six subtypes of internal entries:
+ * 3a. Node entry.  This entry points to a node closer to the edge.
+ * 3b. Retry entry.  This indicates that the entry you're looking for is
+ *     in the array, but it's been moved to a different node.  Retry your
+ *     lookup from the head of the array.
+ * 3c. Sibling entry.  This indicates that the entry you're looking for
+ *     is stored in a different slot in the same node.
+ * 3d. Cousin entry.  This indicates that the entry you're looking for
+ *     is stored in a slot in a different node.
+ * 3e. IDR NULL entry.  The IDR distinguishes between allocated NULL pointers
+ *     and free entries.  The easiest way to support this in the xarray is to
+ *     substitute an internal entry for the NULL pointer.
+ * 3f. Walk End entry.  This entry is never found in the array.  It is
+ *     returned by iteration functions to signal that the iteration has
+ *     finished.
+ *
+ * The head of the array never contains a retry, sibling or cousin entry;
+ * these entries can only be found in array nodes.
+ */
+
+static inline void *xa_mk_internal(unsigned long v)
+{
+	return (void *)((v << 2) | 2);
+}
+
+static inline unsigned long xa_internal_value(void *entry)
+{
+	return (unsigned long)entry >> 2;
+}
+
+static inline bool xa_is_internal(void *entry)
+{
+	return ((unsigned long)entry & 3) == 2;
+}
+
+static inline void *xa_mk_node(struct xa_node *node)
+{
+	return (void *)((unsigned long)node | 2);
+}
+
+static inline struct xa_node *xa_node(void *entry)
+{
+	return (struct xa_node *)((unsigned long)entry & ~3UL);
+}
+
+static inline bool xa_is_node(void *entry)
+{
+	return xa_is_internal(entry) && (unsigned long)entry > 4096;
+}
+
+static inline void *xa_mk_sibling(unsigned int offset)
+{
+	return xa_mk_internal(offset);
+}
+
+static inline unsigned long xa_sibling_offset(void *entry)
+{
+	return xa_internal_value(entry);
+}
+
+static inline bool xa_is_sibling(void *entry)
+{
+	return xa_is_internal(entry) && xa_sibling_offset(entry) < 256;
+}
+
+static inline void *xa_mk_cousin(unsigned long offset)
+{
+	return xa_mk_internal(offset + 256);
+}
+
+static inline unsigned long xa_cousin_offset(void *entry)
+{
+	return xa_internal_value(entry) - 256;
+}
+
+static inline bool xa_is_cousin(void *entry)
+{
+	return xa_is_internal(entry) && xa_cousin_offset(entry) < 256;
+}
+
+static inline bool xa_is_relative(void *entry)
+{
+	return xa_is_internal(entry) && xa_internal_value(entry) < 512;
+}
+
+/*
+ * Values 0-255 are reserved for sibling entries (0-62 actually used)
+ * Values 256-511 are reserved for cousin entries (0-62, 64 actually used)
+ * 515-1023 are available for use before we start packing siblings & cousins
+ * closer together.
+ */
+#define XA_IDR_NULL		xa_mk_internal(512)
+#define XA_RETRY_ENTRY		xa_mk_internal(513)
+#define XA_WALK_END		xa_mk_internal(514)
+
+/*
+ * These are not array entries.  They are found only in xas->xa_node and
+ * mean that the lookup should be restarted from the top.  They must be
+ * distinct from NULL, any valid node pointer and the IS_ERR() range.
+ * Making them small means we can test for them cheaply.
+ */
+#define XA_WALK_RESTART		((struct xa_node *)1)
+#define XA_RESTART_FIND		((struct xa_node *)1)
+#define XA_RESTART_NEXT		((struct xa_node *)2)
+
+static inline bool xa_is_retry(void *entry)
+{
+	return unlikely(entry == XA_RETRY_ENTRY);
+}
+
+static inline bool xa_is_idr_null(void *entry)
+{
+	return entry == XA_IDR_NULL;
+}
+
+static inline bool xa_track_free(struct xarray *xa)
+{
+	return xa->xa_flags & XA_FLAG_TRACK_FREE;
+}
+
+static inline void *xa_head(const struct xarray *xa)
+{
+	return rcu_dereference_check(xa->xa_head,
+					lockdep_is_held(&xa->xa_lock));
+}
+
+static inline void *xa_head_locked(const struct xarray *xa)
+{
+	return rcu_dereference_protected(xa->xa_head,
+					lockdep_is_held(&xa->xa_lock));
+}
+
+static inline void *xa_entry(const struct xarray *xa,
+		const struct xa_node *node, unsigned int offset)
+{
+	XA_BUG_ON(offset >= XA_CHUNK_SIZE);
+	return rcu_dereference_check(node->slots[offset],
+					lockdep_is_held(&xa->xa_lock));
+}
+
+static inline void *xa_entry_locked(const struct xarray *xa,
+		const struct xa_node *node, unsigned int offset)
+{
+	XA_BUG_ON(offset >= XA_CHUNK_SIZE);
+	return rcu_dereference_protected(node->slots[offset],
+					lockdep_is_held(&xa->xa_lock));
+}
+
+static inline void *xa_parent(const struct xarray *xa,
+		const struct xa_node *node)
+{
+	return rcu_dereference_check(node->parent,
+					lockdep_is_held(&xa->xa_lock));
+}
+
+static inline void *xa_parent_locked(const struct xarray *xa,
+		const struct xa_node *node)
+{
+	return rcu_dereference_protected(node->parent,
+					lockdep_is_held(&xa->xa_lock));
+}
+
+static inline void *xa_deref_locked(struct xarray *xa, void __rcu **slot)
+{
+	return rcu_dereference_protected(*slot, lockdep_is_held(&xa->xa_lock));
+}
+
+typedef void (*xa_update_node_t)(struct xa_node *);
+
+/**
+ * xa_state - XArray operation state
+ * @xa_index: The index which this operation is currently about.
+ * @xa_shift: The shift of the node containing the entry we're interested in.
+ * @xa_slots: The number of slots occupied by that entry in that node.
+ * @xa_flags: Flags, see below
+ * @xa_offset: This entry's offset within the chunk of slots.
+ * @xa_node: The node containing this entry, or NULL if the entry is at
+ *	     xa_head, or XA_WALK_RESTART to start walking through the array
+ *	     from the head, or an IS_ERR pointer if an error occurred.
+ * @xa_alloc: One preallocated node.
+ * @xa_count: Number of entries added/deleted so far during this operation.
+ * @xa_exceptional: Number of exceptional entries added/deleted.
+ * @xa_update: Callback when updating a node.
+ *
+ * Some of this state may seem redundant, but some of it is input state and
+ * some is output state.  For example, xa_shift is not equal to xa_node->shift
+ * until we have walked through the array to the correct xa_node.
+ */
+struct xa_state {
+	unsigned long xa_index;
+	unsigned char xa_shift;
+	unsigned char xa_slots;
+	unsigned char xa_offset;
+	unsigned char xa_flags;
+	struct xa_node *xa_node;
+	struct xa_node *xa_alloc;
+	long xa_count;
+	long xa_exceptional;
+	xa_update_node_t xa_update;
+};
+
+/*
+ * XAS_FLAG_LOOKUP - Find this index.  If clear, it means we're searching for
+ * the next index.  This only makes a difference if we see a multislot entry;
+ * if set, we move backwards to return the entry.  If clear, we move forwards
+ * and find the next entry.
+ */
+#define XAS_FLAG_LOOKUP	1
+
+static inline int xas_error(const struct xa_state *xas)
+{
+	return IS_ERR(xas->xa_node) ? PTR_ERR(xas->xa_node) : 0;
+}
+
+static inline void xas_set_err(struct xa_state *xas, int err)
+{
+	XA_BUG_ON(err > 0);
+	xas->xa_node = ERR_PTR(err);
+}
+
+static inline bool xas_restart(const struct xa_state *xas)
+{
+	return unlikely(xas->xa_node == XA_WALK_RESTART);
+}
+
+static inline void xas_retry(struct xa_state *xas)
+{
+	xas->xa_flags |= XAS_FLAG_LOOKUP;
+	xas->xa_node = XA_WALK_RESTART;
+}
+
+static inline void xas_pause(struct xa_state *xas)
+{
+	xas->xa_node = XA_WALK_RESTART;
+}
+
+static inline void xas_jump(struct xa_state *xas, unsigned long index)
+{
+	xas->xa_index = index;
+	xas->xa_node = XA_WALK_RESTART;
+}
+
+void xas_init_range(struct xa_state *, unsigned long index,
+		unsigned char shift, unsigned char slots);
+void xas_destroy(struct xa_state *);
+bool xas_nomem(struct xa_state *, gfp_t);
+
+void *xas_load(const struct xarray *, struct xa_state *);
+void *xas_store(struct xarray *, struct xa_state *, void *entry);
+void *xas_create(struct xarray *, struct xa_state *);
+int xas_split(struct xarray *, struct xa_state *, unsigned int order);
+
+bool xas_get_tag(const struct xarray *, const struct xa_state *, xa_tag_t);
+void xas_set_tag(struct xarray *, const struct xa_state *, xa_tag_t);
+void xas_clear_tag(struct xarray *, const struct xa_state *, xa_tag_t);
+void xas_init_tags(struct xarray *, const struct xa_state *);
+void *xas_find_tag(const struct xarray *, struct xa_state *, unsigned long max,
+		xa_tag_t);
+
+void *xas_next_entry(const struct xarray *, struct xa_state *,
+		unsigned long max);
+void *__xas_prev_slot(const struct xarray *, struct xa_state *,
+		unsigned long min);
+
+/*
+ * xas_init() - Set up xarray operation state
+ * @xas: Array operation state.
+ * @index: Target of the operation.
+ */
+static inline void xas_init(struct xa_state *xas, unsigned long index)
+{
+	xas_init_range(xas, index, 0, 1);
+}
+
+/**
+ * xas_init_order() - Set up xarray operation state for a multislot entry
+ * @xas: Array operation state.
+ * @index: Target of the operation.
+ * @order: Entry occupies 2^@order indices.
+ */
+static inline void xas_init_order(struct xa_state *xas, unsigned long index,
+		unsigned int order)
+{
+	unsigned char shift = order - (order % XA_CHUNK_SHIFT);
+	unsigned char slots = 1 << (order % XA_CHUNK_SHIFT);
+
+	index = ((index >> shift) & ~(slots - 1UL)) << shift;
+	xas_init_range(xas, index, shift, slots);
+}
+
+static inline void *xas_next(const struct xarray *xa, struct xa_state *xas,
+		unsigned long max)
+{
+	struct xa_node *node = xas->xa_node;
+	void *entry;
+
+	if (unlikely(!node) || IS_ERR(node))
+		return XA_WALK_END;
+	if (unlikely(node == XA_WALK_RESTART))
+		return xas_next_entry(xa, xas, max);
+
+	do {
+		xas->xa_index = (xas->xa_index |
+					((1UL << node->shift) - 1)) + 1;
+		if (unlikely(xas->xa_index > max))
+			return XA_WALK_END;
+
+		if (unlikely(++xas->xa_offset == XA_CHUNK_SIZE))
+			return xas_next_entry(xa, xas, max);
+		entry = xa_entry(xa, node, xas->xa_offset);
+		if (unlikely(xa_is_internal(entry)))
+			return xas_next_entry(xa, xas, max);
+	} while (!entry);
+
+	return entry;
+}
+
+static inline unsigned int xas_chunk_tag(const struct xa_state *xas,
+		xa_tag_t tag)
+{
+	unsigned long *addr = xas->xa_node->tags[(__force unsigned)tag];
+
+	return find_next_bit(addr, XA_CHUNK_SIZE, xas->xa_offset);
+}
+
+static inline void *xas_next_tag(const struct xarray *xa, struct xa_state *xas,
+		unsigned long max, xa_tag_t tag)
+{
+	struct xa_node *node = xas->xa_node;
+	unsigned int offset;
+
+	if (unlikely(!node) || IS_ERR(node))
+		return XA_WALK_END;
+	if (unlikely(node == XA_WALK_RESTART))
+		return xas_find_tag(xa, xas, max, tag);
+
+	xas->xa_offset++;
+	xas->xa_index = (xas->xa_index | ((1UL << node->shift) - 1)) + 1;
+	if (unlikely(xas->xa_index > max))
+		return XA_WALK_END;
+	offset = xas_chunk_tag(xas, tag);
+	if (offset == XA_CHUNK_SIZE)
+		return xas_find_tag(xa, xas, max, tag);
+	if (offset != xas->xa_offset) {
+		xas->xa_index += (offset - xas->xa_offset) << node->shift;
+		xas->xa_offset = offset;
+		if (unlikely(xas->xa_index > max))
+			return XA_WALK_END;
+	}
+
+	return xa_entry(xa, node, offset);
+}
+
+static inline void *xas_prev_slot(const struct xarray *xa,
+		struct xa_state *xas, unsigned long min)
+{
+	struct xa_node *node = xas->xa_node;
+	void *entry;
+
+	if (xas->xa_index <= min || !node)
+		return XA_WALK_END;
+	if (unlikely(node == XA_WALK_RESTART ||
+				++xas->xa_offset == XA_CHUNK_SIZE))
+		return __xas_prev_slot(xa, xas, min);
+	entry = xa_entry(xa, node, xas->xa_offset);
+	if (unlikely(xa_is_internal(entry)))
+		return __xas_prev_slot(xa, xas, min);
+	xas->xa_index -= 1UL << node->shift;
+	return entry;
+}
+
+/**
+ * xas_for_each() - Iterate over all present entries in this range
+ * @xa: Array
+ * @xas: Array operation state
+ * @entry: Pointer to use for iteration
+ * @max: Highest index to return
+ *
+ * The loop body will be invoked for each entry present in the xarray
+ * between the current xas position and @max.  @entry will be set to
+ * the entry retrieved from the xarray.  It is safe to delete entries
+ * from the array in the loop body.
+ */
+#define xas_for_each(xa, xas, entry, max) \
+	for (entry = xas_next(xa, xas, max); \
+	     entry != XA_WALK_END; \
+	     entry = xas_next(xa, xas, max))
+
+/**
+ * xas_for_each_slot() - Iterate over all slots in this range
+ * @xa: Array
+ * @xas: Array operation state
+ * @entry: Pointer to use for iteration
+ * @max: Highest index to return
+ *
+ * The loop body will be executed for each allocated slot in the xarray
+ * between the current xas position and @max.  @entry will be set to
+ * the entry retrieved from the xarray.  It is safe to delete entries
+ * from the array in the loop body.
+ */
+#define xas_for_each_slot(xa, xas, entry, max) \
+	for (entry = xas_next_slot(xa, xas); \
+	     entry != XA_WALK_END; \
+	     entry = xas_next_slot(xa, xas, max))
+
+/**
+ * xas_for_each_tag() - Iterate over all tagged entries in this range
+ * @xa: Array
+ * @xas: Array operation state
+ * @entry: Pointer to use for iteration
+ * @max: Highest index to return
+ *
+ * The loop body will be executed for each tagged entry in the xarray
+ * between the current xas position and @max.  @entry will be set to
+ * the entry retrieved from the xarray.  It is safe to delete entries
+ * from the array in the loop body.
+ */
+#define xas_for_each_tag(xa, xas, entry, max) \
+	for (entry = xas_next_tag(xa, xas, max, tag); \
+	     entry != XA_WALK_END; \
+	     entry = xas_next_tag(xa, xas, max, tag))
+
+/**
+ * xas_for_each_slot_rev() - Iterate over all slots in this range backwards
+ * @xa: Array
+ * @xas: Array operation state
+ * @entry: Pointer to use for iteration
+ * @min: Lowest index to return
+ *
+ * The loop body will be executed for each allocated slot in the xarray
+ * between the current xas position and @min.  @entry will be set to
+ * the entry retrieved from the xarray.  It is safe to delete entries
+ * from the array in the loop body.
+ */
+#define xas_for_each_slot_rev(xa, xas, entry, min) \
+	for (entry = xas_prev_slot(xa, xas); \
+	     entry != XA_WALK_END; \
+	     entry = xas_prev_slot(xa, xas, max))
+
+/**
+ * xas_store_for_each() - Iterate over all entries, then replace them
+ * @xa: Array
+ * @xas: Array operation state
+ * @entry: Pointer to use for iteration
+ * @index: Index to store new entry at
+ * @order: Order of new entry
+ * @new: New entry
+ *
+ * The loop body will be executed for each entry present in the range
+ * specified by @index and @order.  After all entries have been processed,
+ * the @new entry will be atomically stored in the xarray.
+ * RCU readers may temporarily see retry entries.  If you break out of the
+ * loop, no modifications will have been made to the xarray.
+ */
+#define xas_store_for_each(xa, xas, entry, index, order, new)		\
+	for (entry = xas_store_begin(xa, xas, index, order);		\
+	     entry = xas_store_finish(xa, xas, index, order, new); )
+
+/**
+ * xas_split_for_each() - Create new entries to replace a multislot entry
+ * @xa: Array
+ * @xas: Array operation state
+ * @entry: Pointer to use for iteration
+ * @index: Index of entry to split
+ * @order: Order of new entries to create
+ *
+ * The loop body will be executed for each new entry present in the range
+ * specified by @index and @order.  The loop will see the index of the new
+ * entry in @xas->xa_index.  It should call xas_store() to set up each new
+ * entry.  After the loop has successfully terminated, the new entries will
+ * be atomically stored in the xarray.  RCU readers may temporarily see
+ * retry entries.  If you break out of the loop, no modifications will have
+ * been made to the xarray and the temporary memory allocation will be freed
+ * by xas_destroy().
+ */
+#define xas_split_for_each(xa, xas, entry, index, order)                \
+	for (entry = xas_split_begin(xa, xas, index, order);            \
+	     entry = xas_split_finish(xa, xas, index, order); )
+
+/* Really advanced. */
+extern struct kmem_cache *xa_node_cache;
+void xas_delete_node(struct xarray *, struct xa_state *);
+
+#endif /* XA_ADVANCED */
+
+extern void xarray_init(void);
+#endif /* _LINUX_XARRAY_H */
diff --git a/lib/Makefile b/lib/Makefile
index 43a80ec3bd10..d8744c25ab29 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -17,7 +17,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 dump_stack.o timerqueue.o\
+	 xarray.o rbtree.o radix-tree.o dump_stack.o timerqueue.o\
 	 idr.o int_sqrt.o extable.o \
 	 sha1.o chacha20.o md5.o irq_regs.o argv_split.o \
 	 flex_proportions.o ratelimit.o show_mem.o \
@@ -26,6 +26,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 
 CFLAGS_radix-tree.o += -DCONFIG_SPARSE_RCU_POINTER
 CFLAGS_idr.o += -DCONFIG_SPARSE_RCU_POINTER
+CFLAGS_xarray.o += -DCONFIG_SPARSE_RCU_POINTER
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/xarray.c b/lib/xarray.c
new file mode 100644
index 000000000000..fd33b5b91013
--- /dev/null
+++ b/lib/xarray.c
@@ -0,0 +1,1305 @@
+#define XA_ADVANCED
+
+#include <linux/bitmap.h>
+#include <linux/bitops.h>
+#include <linux/export.h>
+#include <linux/gfp.h>
+#include <linux/init.h>
+#include <linux/kernel.h>
+#include <linux/list.h>
+#include <linux/rcupdate.h>
+#include <linux/slab.h>
+#include <linux/xarray.h>
+
+#ifdef XA_DEBUG
+#define XA_BUG_ON(x) BUG_ON(x)
+#else
+#define XA_BUG_ON(x)
+#endif
+
+#define inc_tag(tag) do { \
+	tag = (__force xa_tag_t)((__force unsigned)(tag) + 1); \
+} while (0)
+
+static inline void xa_tag_set(struct xarray *xa, xa_tag_t tag)
+{
+	if (!(xa->xa_flags & (1 << (__force unsigned)tag)))
+		xa->xa_flags |= (1 << (__force unsigned)tag);
+}
+
+static inline void xa_tag_clear(struct xarray *xa, xa_tag_t tag)
+{
+	if (xa->xa_flags & (1 << (__force unsigned)tag))
+		xa->xa_flags &= ~(1 << (__force unsigned)tag);
+}
+
+static inline bool tag_get(const struct xa_node *node, unsigned int offset,
+		xa_tag_t tag)
+{
+	return test_bit(offset, node->tags[(__force unsigned)tag]);
+}
+
+static inline void tag_set(struct xa_node *node, unsigned int offset,
+		xa_tag_t tag)
+{
+	__set_bit(offset, node->tags[(__force unsigned)tag]);
+}
+
+static inline void tag_clear(struct xa_node *node, unsigned int offset,
+		xa_tag_t tag)
+{
+	__clear_bit(offset, node->tags[(__force unsigned)tag]);
+}
+
+static inline void tag_set_all(struct xa_node *node, xa_tag_t tag)
+{
+	bitmap_fill(node->tags[(__force unsigned)tag], XA_CHUNK_SIZE);
+}
+
+static inline bool tag_any_set(struct xa_node *node, xa_tag_t tag)
+{
+	return !bitmap_empty(node->tags[(__force unsigned)tag], XA_CHUNK_SIZE);
+}
+
+/*
+ * Use this to calculate the maximum index that will need to be created
+ * in order to add the entry described by @xas.  Because we cannot store a
+ * multiple-slot entry at index 0, the calculation is a little more complex
+ * than you might expect.
+ */
+static unsigned long xas_max(struct xa_state *xas)
+{
+	unsigned long mask, max = xas->xa_index;
+
+	if (xas->xa_shift || xas->xa_slots > 1) {
+		mask = ((xas->xa_slots << xas->xa_shift) - 1);
+		max |= mask;
+		if (mask == max)
+			max++;
+	}
+	return max;
+}
+
+static unsigned long set_index(struct xa_node *node, unsigned int offset,
+		unsigned long index)
+{
+	unsigned long mask = ((unsigned long)XA_CHUNK_SIZE << node->shift) - 1;
+
+	return (index & ~mask) + ((unsigned long)offset << node->shift);
+}
+
+/* XXX: kill? */
+static unsigned int node_offset(struct xa_node *node, unsigned long index)
+{
+	return (index >> node->shift) & XA_CHUNK_MASK;
+}
+
+static unsigned long xas_offset(struct xa_state *xas)
+{
+	return (xas->xa_index >> xas->xa_node->shift) & XA_CHUNK_MASK;
+}
+
+/* Returns true if 'entry' can contain 'index' */
+static bool xa_bounds(unsigned long index, void *entry)
+{
+	struct xa_node *node;
+	unsigned int max;
+
+	if (!xa_is_node(entry))
+		return index == 0;
+	node = xa_node(entry);
+	max = node->max;
+	if (max == 0)
+		max = 63;
+	return (index >> node->shift) <= max;
+}
+
+static void *xas_start(const struct xarray *xa, struct xa_state *xas)
+{
+	struct xa_node *node = xas->xa_node;
+	void *entry;
+	unsigned long offset;
+
+	if (!xas_restart(xas)) {
+		if (node)
+			return xa_entry(xa, xas->xa_node, xas->xa_offset);
+		else
+			return xa_head(xa);
+	}
+
+	entry = xa_head(xa);
+	if (!xa_is_node(entry)) {
+		if (xas->xa_index)
+			return XA_WALK_END;
+		xas->xa_node = NULL;
+		return entry;
+	}
+
+	node = xa_node(entry);
+	if (xas->xa_shift > node->shift) {
+		xas->xa_node = NULL;
+		return entry;
+	}
+
+	offset = xas->xa_index >> node->shift;
+	if (offset > XA_CHUNK_MASK)
+		return XA_WALK_END;
+
+	xas->xa_node = node;
+	xas->xa_offset = offset;
+	return entry;
+}
+
+/**
+ * xas_init_range() - Initialise xarray operation state for a multislot entry
+ * @xas: Array operation state.
+ * @index: Eventual target of the operation.
+ * @shift: Shift of the node this will occupy
+ * @slots: Number of slots in that node to occupy
+ */
+void xas_init_range(struct xa_state *xas, unsigned long index,
+		unsigned char shift, unsigned char slots)
+{
+	xas->xa_index = index;
+	xas->xa_shift = shift;
+	xas->xa_slots = slots;
+	xas->xa_offset = 0;
+	xas->xa_flags = XAS_FLAG_LOOKUP;
+	xas->xa_node = XA_WALK_RESTART;
+	xas->xa_alloc = NULL;
+	xas->xa_count = 0;
+	xas->xa_exceptional = 0;
+	xas->xa_update = NULL;
+}
+EXPORT_SYMBOL_GPL(xas_init_range);
+
+struct kmem_cache *xa_node_cache;
+
+static void xa_node_ctor(void *p)
+{
+	struct xa_node *node = p;
+
+	memset(&node->tags, 0, sizeof(node->tags));
+	memset(&node->slots, 0, sizeof(node->slots));
+	INIT_LIST_HEAD(&node->private_list);
+}
+
+static void xa_node_rcu_free(struct rcu_head *head)
+{
+	struct xa_node *node = container_of(head, struct xa_node, rcu_head);
+
+	xa_node_ctor(node);
+	kmem_cache_free(xa_node_cache, node);
+}
+
+static void xa_node_free(struct xa_node *node)
+{
+	call_rcu(&node->rcu_head, xa_node_rcu_free);
+}
+
+/**
+ * xas_destroy() - Dispose of any resources used during the xarray operation
+ * @xas: Array operation state.
+ *
+ * If the operation only involved read accesses to the XArray or modifying
+ * existing data in the XArray, there is no need to call this function
+ * (eg xa_set_tag()).  However, if you may have allocated memory (for
+ * example by calling xas_nomem()), then call this function.
+ *
+ * This function does not reinitialise the state, so you may continue to
+ * call xas_error(), and you would want to call xas_init() before reusing
+ * this structure.  It only releases any resources.
+ */
+void xas_destroy(struct xa_state *xas)
+{
+	struct xa_node *node = xas->xa_alloc;
+
+	if (!node)
+		return;
+#if 0
+	while (node->count)
+		kmem_cache_free(xa_node_cache, node->slots[node->count - 1]);
+#endif
+	kmem_cache_free(xa_node_cache, node);
+	xas->xa_alloc = NULL;
+}
+EXPORT_SYMBOL_GPL(xas_destroy);
+
+/**
+ * xas_nomem() - Allocate memory if needed
+ * @xas: Array operation state
+ * @gfp: Memory allocation flags
+ *
+ * If we need to add new nodes to the xarray, we try to allocate memory
+ * with GFP_NOWAIT while holding the lock, which will usually succeed.
+ * If it fails, @xas is flagged as needing memory to continue.  The caller
+ * should drop the lock and call xas_nomem().  If xas_nomem() succeeds,
+ * the caller should retry the operation.
+ *
+ * Forward progress is guaranteed as one node is allocated here and is
+ * available to the memory allocators.
+ *
+ * Return: true if memory was needed, and was successfully allocated.
+ */
+bool xas_nomem(struct xa_state *xas, gfp_t gfp)
+{
+	if (xas->xa_node != ERR_PTR(-ENOMEM))
+		return false;
+	xas->xa_alloc = kmem_cache_alloc(xa_node_cache, gfp);
+	if (!xas->xa_alloc)
+		return false;
+	xas->xa_node = XA_WALK_RESTART;
+	return true;
+}
+EXPORT_SYMBOL_GPL(xas_nomem);
+
+static void *xas_alloc(struct xarray *xa, struct xa_state *xas,
+		unsigned int shift)
+{
+	struct xa_node *parent = xas->xa_node;
+	struct xa_node *node = xas->xa_alloc;
+
+	if (IS_ERR(parent))
+		return NULL;
+
+	if (node) {
+		xas->xa_alloc = NULL;
+	} else {
+		node = kmem_cache_alloc(xa_node_cache,
+					GFP_NOWAIT | __GFP_NOWARN);
+		if (!node) {
+			xas->xa_node = ERR_PTR(-ENOMEM);
+			return NULL;
+		}
+	}
+
+	if (xas->xa_node) {
+		node->offset = xas->xa_offset;
+		parent->count++;
+		XA_BUG_ON(parent->count > XA_CHUNK_SIZE);
+	} else {
+		node->max = XA_CHUNK_MASK;
+	}
+	XA_BUG_ON(shift > BITS_PER_LONG);
+	node->shift = shift;
+	node->count = 0;
+	node->exceptional = 0;
+	RCU_INIT_POINTER(node->parent, xas->xa_node);
+	node->array = xa;
+
+	return node;
+}
+
+#if 0
+static void *xas_find_cousin(const struct xarray *xa, struct xa_state *xas)
+{
+	struct xa_node *node = xas->xa_node;
+	unsigned int offset = xas->xa_offset;
+	void *entry;
+
+	while (offset == 0) {
+		offset = node->offset;
+		node = xa_parent(xa, node);
+		XA_BUG_ON(!node);
+	}
+
+	offset--;
+
+	for (;;) {
+		entry = xa_entry(xa, node, offset);
+
+		if (xa_is_sibling(entry)) {
+			offset = xa_sibling_offset(entry);
+			entry = xa_entry(xa, node, offset);
+		}
+
+		if (!xa_is_node(entry))
+			break;
+		node = xa_node(entry);
+		offset = XA_CHUNK_SIZE - 1;
+	}
+
+	xas->xa_node = node;
+	xas->xa_offset = offset;
+	return entry;
+}
+	} else if (unlikely(xa_cousin_entry(entry))) {
+		return xas_find_cousin(xa, xas);
+#endif
+
+static void *xas_descend(const struct xarray *xa, struct xa_state *xas,
+		struct xa_node *node)
+{
+	unsigned int offset = node_offset(node, xas->xa_index);
+	void *entry = xa_entry(xa, node, offset);
+
+	if (xa_is_sibling(entry)) {
+		offset = xa_sibling_offset(entry);
+		entry = xa_entry(xa, node, offset);
+	}
+
+	xas->xa_node = node;
+	xas->xa_offset = offset;
+	return entry;
+}
+
+/**
+ * xas_get_tag() - Returns the state of this tag
+ * @xa: Array
+ * @xas: Array operation state
+ * @tag: Tag value
+ *
+ * Return: true if the tag is set, false if the tag is clear.
+ */
+bool xas_get_tag(const struct xarray *xa, const struct xa_state *xas,
+		xa_tag_t tag)
+{
+	if (xas_restart(xas) || xas_error(xas))
+		return false;
+	if (!xas->xa_node)
+		return xa_tagged(xa, tag);
+	return tag_get(xas->xa_node, xas->xa_offset, tag);
+}
+EXPORT_SYMBOL_GPL(xas_get_tag);
+
+/**
+ * xas_set_tag() - Sets the tag on this entry and its parents
+ * @xa: Array
+ * @xas: Array operation state
+ * @tag: Tag value
+ *
+ * Sets the specified tag on this entry, and walks up the tree setting it
+ * on all the ancestor entries.
+ */
+void xas_set_tag(struct xarray *xa, const struct xa_state *xas, xa_tag_t tag)
+{
+	struct xa_node *node = xas->xa_node;
+	unsigned int offset = xas->xa_offset;
+
+	if (IS_ERR(node))
+		return;
+
+	while (node) {
+		if (tag_get(node, offset, tag))
+			return;
+		tag_set(node, offset, tag);
+		offset = node->offset;
+		node = xa_parent(xa, node);
+	}
+
+	if (!xa_tagged(xa, tag))
+		xa_tag_set(xa, tag);
+}
+EXPORT_SYMBOL_GPL(xas_set_tag);
+
+/**
+ * xas_clear_tag() - Clears the tag on this entry and its parents
+ * @xa: Array
+ * @xas: Array operation state
+ * @tag: Tag value
+ *
+ * Clears the specified tag on this entry, and walks up the tree
+ * attempting to clear it on all the ancestor entries.  A tag may
+ * only be cleared on an ancestor entry if none of its children
+ * have that tag set.
+ */
+void xas_clear_tag(struct xarray *xa, const struct xa_state *xas, xa_tag_t tag)
+{
+	struct xa_node *node = xas->xa_node;
+	unsigned int offset = xas->xa_offset;
+
+	if (IS_ERR(node))
+		return;
+
+	while (node) {
+		if (!tag_get(node, offset, tag))
+			return;
+		tag_clear(node, offset, tag);
+		if (tag_any_set(node, tag))
+			return;
+
+		offset = node->offset;
+		node = xa_parent(xa, node);
+	}
+
+	if (xa_tagged(xa, tag))
+		xa_tag_clear(xa, tag);
+}
+EXPORT_SYMBOL_GPL(xas_clear_tag);
+
+/**
+ * xas_init_tags() - Initialise all tags for the entry
+ * @xa: Array
+ * @xas: Array operations state.
+ *
+ * Initialise all tags for the entry specified by @xas.  If we're tracking
+ * free entries with a tag, we need to set it on all entries.  All other
+ * tags are cleared.
+ *
+ * This implementation is not as efficient as it could be; we may walk
+ * up the tree multiple times.
+ */
+void xas_init_tags(struct xarray *xa, const struct xa_state *xas)
+{
+	xa_tag_t tag = 0;
+
+	if (xa_track_free(xa)) {
+		xas_set_tag(xa, xas, XA_FREE_TAG);
+		inc_tag(tag);
+	}
+	for (;;) {
+		xas_clear_tag(xa, xas, tag);
+		if (tag == XA_TAG_MAX)
+			break;
+		inc_tag(tag);
+	}
+}
+EXPORT_SYMBOL_GPL(xas_init_tags);
+
+/**
+ * xas_load() - Find the entry for the index
+ * @xa: Array.
+ * @xas: Array operation state.
+ *
+ * If the @xas is in an error state, returns the error in the state.
+ * If it is in the RESTART_WALK state, will return XA_WALK_END if the
+ * xa_index cannot be contained in the current xarray without expanding it.
+ * If there is no entry for the index, the walk may stop at a level in the
+ * tree higher than the entry, or even at the root.
+ *
+ * Return: An entry in the tree that is not a sibling or node entry.  May be
+ * a NULL pointer, a user pointer, exceptional entry, retry entry, or an
+ * IDR_NULL.
+ */
+void *xas_load(const struct xarray *xa, struct xa_state *xas)
+{
+	void *entry;
+
+	if (xas_error(xas))
+		return xas->xa_node;
+
+	entry = xas_start(xa, xas);
+	while (xa_is_node(entry)) {
+		struct xa_node *node = xa_node(entry);
+
+		if (xas->xa_shift > node->shift)
+			break;
+		entry = xas_descend(xa, xas, node);
+	}
+	return entry;
+}
+EXPORT_SYMBOL_GPL(xas_load);
+
+static void xas_shrink(struct xarray *xa, const struct xa_state *xas)
+{
+	struct xa_node *node = xas->xa_node;
+
+	for (;;) {
+		void *entry;
+
+		XA_BUG_ON(node->count > XA_CHUNK_SIZE);
+		if (node->count != 1)
+			break;
+		entry = xa_entry_locked(xa, node, 0);
+		if (!entry)
+			break;
+		if (!xa_is_node(entry) && node->shift)
+			break;
+
+		RCU_INIT_POINTER(xa->xa_head, entry);
+		if (xa_track_free(xa) && !tag_get(node, 0, XA_FREE_TAG))
+			xa_tag_clear(xa, XA_FREE_TAG);
+
+		node->count = 0;
+		node->exceptional = 0;
+		if (xa_is_node(entry))
+			RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);
+		VM_WARN_ON_ONCE(!list_empty(&node->private_list));
+		xa_node_free(node);
+		if (!xa_is_node(entry))
+			break;
+		node = xa_node(entry);
+		if (xas->xa_update)
+			xas->xa_update(node);
+	}
+}
+
+void xas_delete_node(struct xarray *xa, struct xa_state *xas)
+{
+	struct xa_node *node = xas->xa_node;
+
+	for (;;) {
+		struct xa_node *parent;
+
+		XA_BUG_ON(node->count > XA_CHUNK_SIZE);
+		if (node->count)
+			break;
+
+		parent = xa_parent_locked(xa, node);
+		VM_WARN_ON_ONCE(!list_empty(&node->private_list));
+		xas->xa_node = parent;
+		xas->xa_offset = node->offset;
+		xa_node_free(node);
+
+		if (!parent) {
+			xa->xa_head = NULL;
+			xas->xa_node = XA_WALK_RESTART;
+			return;
+		}
+
+		parent->slots[xas->xa_offset] = NULL;
+		parent->count--;
+		XA_BUG_ON(parent->count > XA_CHUNK_SIZE);
+		node = parent;
+		if (xas->xa_update)
+			xas->xa_update(node);
+	}
+
+	if (!node->parent)
+		xas_shrink(xa, xas);
+}
+
+/**
+ * xas_free_nodes() - Free this node and all nodes that it references
+ * @xa: Array
+ * @xas: Array operation state
+ * @top: Node to free
+ *
+ * This node has been removed from the tree.  We must now free it and all
+ * of its subnodes.  There may be RCU walkers with references into the tree,
+ * so we must replace all entries with retry markers.
+ */
+static void xas_free_nodes(const struct xarray *xa, struct xa_state *xas,
+		struct xa_node *top)
+{
+	unsigned int offset = 0;
+	struct xa_node *node = top;
+
+	for (;;) {
+		void *entry = xa_entry_locked(xa, node, offset);
+
+		if (xa_is_node(entry)) {
+			node = xa_node(entry);
+			offset = 0;
+			continue;
+		}
+		if (entry) {
+			RCU_INIT_POINTER(node->slots[offset], XA_RETRY_ENTRY);
+			if (xa_is_exceptional(entry))
+				xas->xa_exceptional--;
+			xas->xa_count--;
+		}
+		offset++;
+		while (offset == XA_CHUNK_SIZE) {
+			struct xa_node *parent = xa_parent_locked(xa, node);
+
+			offset = node->offset + 1;
+			node->count = 0;
+			node->exceptional = 0;
+			if (xas->xa_update)
+				xas->xa_update(node);
+			VM_WARN_ON_ONCE(!list_empty(&node->private_list));
+			xa_node_free(node);
+			if (node == top)
+				return;
+			node = parent;
+		}
+	}
+}
+
+/*
+ * xas_expand adds nodes to the head of the tree until it has reached
+ * sufficient height to be able to contain index
+ */
+static int xas_expand(struct xarray *xa, struct xa_state *xas, void *entry)
+{
+	struct xa_node *node = NULL;
+	unsigned int shift = 0;
+	unsigned long max = xas_max(xas);
+
+	if (!entry) {
+		if (max == 0)
+			return 0;
+		while ((max >> shift) >= XA_CHUNK_SIZE)
+			shift += XA_CHUNK_SHIFT;
+		return shift + XA_CHUNK_SHIFT;
+	} else if (xa_is_node(entry)) {
+		node = xa_node(entry);
+		shift = node->shift + XA_CHUNK_SHIFT;
+	}
+	xas->xa_node = NULL;
+
+	while (!xa_bounds(max, entry)) {
+		xa_tag_t tag = 0;
+
+		XA_BUG_ON(shift > BITS_PER_LONG);
+		node = xas_alloc(xa, xas, shift);
+		if (!node)
+			return -ENOMEM;
+
+		node->count = 1;
+		if (xa_is_exceptional(entry))
+			node->exceptional = 1;
+		RCU_INIT_POINTER(node->slots[0], entry);
+
+		/* Propagate the aggregated tag info to the new child */
+		if (xa_track_free(xa)) {
+			tag_set_all(node, XA_FREE_TAG);
+			if (!xa_tagged(xa, XA_FREE_TAG)) {
+				tag_clear(node, 0, XA_FREE_TAG);
+				xa_tag_set(xa, XA_FREE_TAG);
+			}
+			inc_tag(tag);
+		}
+		for (;;) {
+			if (xa_tagged(xa, tag))
+				tag_set(node, 0, tag);
+			if (tag == XA_TAG_MAX)
+				break;
+			inc_tag(tag);
+		}
+
+		/*
+		 * Now that the new node is fully initialised, we can add
+		 * it to the tree
+		 */
+		if (xa_is_node(entry)) {
+			xa_node(entry)->offset = 0;
+			rcu_assign_pointer(xa_node(entry)->parent, node);
+		}
+		entry = xa_mk_node(node);
+		rcu_assign_pointer(xa->xa_head, entry);
+
+		shift += XA_CHUNK_SHIFT;
+	}
+
+	xas->xa_node = node;
+	return shift;
+}
+
+void *xas_create(struct xarray *xa, struct xa_state *xas)
+{
+	void *entry;
+	void __rcu **slot;
+	struct xa_node *node = xas->xa_node;
+	int shift;
+	unsigned int order = xas->xa_shift;
+
+	if (node == XA_WALK_RESTART) {
+		entry = xa_head_locked(xa);
+		xas->xa_node = NULL;
+		shift = xas_expand(xa, xas, entry);
+		if (shift < 0)
+			goto err;
+		entry = xa_head_locked(xa);
+		slot = &xa->xa_head;
+	} else if (IS_ERR(node)) {
+		return node;
+	} else if (node) {
+		unsigned int offset = xas->xa_offset;
+
+		shift = node->shift;
+		entry = xa_entry_locked(xa, node, offset);
+		slot = &node->slots[offset];
+	} else {
+		shift = 0;
+		entry = xa_head_locked(xa);
+		slot = &xa->xa_head;
+	}
+
+	while (shift > order) {
+		shift -= XA_CHUNK_SHIFT;
+		if (!entry) {
+			node = xas_alloc(xa, xas, shift);
+			if (!node)
+				break;
+			if (xa_track_free(xa))
+				tag_set_all(node, XA_FREE_TAG);
+			rcu_assign_pointer(*slot, xa_mk_node(node));
+		} else if (xa_is_node(entry)) {
+			node = xa_node(entry);
+		} else {
+			break;
+		}
+		entry = xas_descend(xa, xas, node);
+		slot = &node->slots[xas->xa_offset];
+	}
+
+	return entry;
+err:
+	xas_set_err(xas, -ENOMEM);
+	return xas->xa_node;
+}
+EXPORT_SYMBOL_GPL(xas_create);
+
+/* XXX: mishandles counts if you have something like
+ * exceptional, sibling, NULL, normal and store something
+ * over the top of all four.  write a testcase for it, then fix it.
+ */
+static void handle_sibling_slots(const struct xarray *xa, struct xa_state *xas,
+		void *entry, int *countp, int *exceptionalp)
+{
+	struct xa_node *node = xas->xa_node;
+	unsigned int offset = xas->xa_offset;
+	unsigned int slots = xas->xa_slots;
+	void *sibling = entry ? xa_mk_sibling(offset) : NULL;
+
+	while (++offset < XA_CHUNK_SIZE) {
+		void *next = xa_entry(xa, node, offset);
+
+		if (--slots)
+			RCU_INIT_POINTER(node->slots[offset], sibling);
+		else if (!xa_is_sibling(next))
+			break;
+
+		if (xa_is_node(next))
+			xas_free_nodes(xa, xas, xa_node(next));
+		*countp += !next - !entry;
+		*exceptionalp += !xa_is_exceptional(next) -
+				 !xa_is_exceptional(entry);
+	}
+}
+
+/**
+ * xas_store() - Store this entry in the array
+ * @xa: Array
+ * @xas: State
+ * @entry: New entry
+ *
+ * Return: The old value at this index or ERR_PTR() if an error happened
+ */
+void *xas_store(struct xarray *xa, struct xa_state *xas, void *entry)
+{
+	struct xa_node *node;
+	int count, exceptional;
+	void *curr;
+
+	if (entry)
+		curr = xas_create(xa, xas);
+	else
+		curr = xas_load(xa, xas);
+	if (xas_restart(xas))
+		return NULL;
+
+	node = xas->xa_node;
+	if (IS_ERR(node))
+		return node;
+	if (node)
+		rcu_assign_pointer(node->slots[xas->xa_offset], entry);
+	else
+		rcu_assign_pointer(xa->xa_head, entry);
+	if (!entry)
+		xas_init_tags(xa, xas);
+	else if (xa_track_free(xa))
+		xas_clear_tag(xa, xas, XA_FREE_TAG);
+
+	exceptional = !xa_is_exceptional(curr) - !xa_is_exceptional(entry);
+	count = !curr - !entry;
+	if (xa_is_node(curr))
+		xas_free_nodes(xa, xas, xa_node(curr));
+	if (node)
+		handle_sibling_slots(xa, xas, entry, &count, &exceptional);
+
+	if (!xa_is_internal(entry)) {
+		xas->xa_count += count;
+		xas->xa_exceptional += exceptional;
+	}
+	if (node) {
+		node->count += count;
+		XA_BUG_ON(node->count > XA_CHUNK_SIZE);
+		node->exceptional += exceptional;
+		XA_BUG_ON(node->exceptional > XA_CHUNK_SIZE);
+		if ((count || exceptional) && xas->xa_update)
+			xas->xa_update(node);
+		if (count < 0)
+			xas_delete_node(xa, xas);
+	}
+
+	return curr;
+}
+EXPORT_SYMBOL_GPL(xas_store);
+
+static bool xas_is_sibling(const struct xa_state *xas, void *entry)
+{
+	return (xas->xa_flags & XAS_FLAG_LOOKUP) && xa_is_sibling(entry);
+}
+
+/*
+ * xas_next_entry() - Helper for other tree walking functions
+ *
+ * As a helper, this function has a lot of rough edges.  On entry,
+ * xas->xa_index may not lay within xas->xa_node (which is why we
+ * start by walking back up the tree if it isn't).  xas->xa_index
+ * is assumed to have been rounded to point to the head of the next entry,
+ * even if the previous iteration hit in the middle of a multislot entry.
+ */
+void *xas_next_entry(const struct xarray *xa, struct xa_state *xas,
+		unsigned long max)
+{
+	XA_BUG_ON(xas_error(xas));
+
+	while (xas->xa_node) {
+		void *entry;
+
+		if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
+			xas->xa_offset = xas->xa_node->offset + 1;
+			xas->xa_node = xa_parent(xa, xas->xa_node);
+			continue;
+		}
+		entry = xas_load(xa, xas);
+
+		if (xa_is_node(entry)) {
+			xas->xa_node = xa_node(entry);
+			xas->xa_offset = xas_offset(xas);
+			continue;
+		} else if (xas_is_sibling(xas, entry)) {
+			xas->xa_offset = xa_sibling_offset(entry);
+			entry = xa_entry(xa, xas->xa_node, xas->xa_offset);
+			xas->xa_flags &= ~XAS_FLAG_LOOKUP;
+			return entry;
+		} else if (entry && !xa_is_internal(entry))
+			return entry;
+
+		if (xas->xa_node <= XA_WALK_RESTART)
+			break;
+		xas->xa_offset++;
+		xas->xa_index += 1UL << xas->xa_node->shift;
+		if (xas->xa_index > max)
+			break;
+	}
+
+	return XA_WALK_END;
+}
+EXPORT_SYMBOL_GPL(xas_next_entry);
+
+/**
+ * xas_find_tag() - Search the xarray for a tagged entry
+ * @xa: Array
+ * @xas: Array operation state
+ * @max: Maximum value to return
+ * @tag: Tag number to search for
+ *
+ * Finds the first tagged entry at or after the index in @xas
+ * tag set and is less than or equal to @max.
+ *
+ * Return: The entry, if found, otherwise XA_WALK_END.
+ */
+void *xas_find_tag(const struct xarray *xa, struct xa_state *xas,
+		unsigned long max, xa_tag_t tag)
+{
+	void *entry = XA_WALK_END;
+	int offset;
+
+	XA_BUG_ON(xas_error(xas));
+
+	if (xas->xa_index > max)
+		return entry;
+
+	if (xas_restart(xas)) {
+		struct xa_node *node;
+		unsigned long offset;
+
+		entry = xa_head(xa);
+		if (!xa_tagged(xa, tag)) {
+			if (xa_is_node(entry))
+				xas->xa_index = XA_CHUNK_SIZE <<
+						xa_node(entry)->shift;
+			else if (xas->xa_index < 1)
+				xas->xa_index = 1;
+			return XA_WALK_END;
+		}
+		if (!xa_is_node(entry)) {
+			if (xas->xa_index)
+				return XA_WALK_END;
+			xas->xa_node = NULL;
+			return entry;
+		}
+		node = xa_node(entry);
+		offset = xas->xa_index >> node->shift;
+		if (offset > XA_CHUNK_MASK)
+			return XA_WALK_END;
+		xas->xa_node = node;
+		xas->xa_offset = offset;
+		entry = XA_WALK_END;
+	}
+
+	while (xas->xa_node) {
+		offset = xas_chunk_tag(xas, tag);
+		if (offset != xas->xa_offset) {
+			unsigned long index = set_index(xas->xa_node, offset,
+								xas->xa_index);
+			if (!index || index > max) {
+				xas->xa_index = max + 1;
+				break;
+			}
+			xas->xa_index = index;
+			xas->xa_offset = offset;
+		}
+
+		if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
+			xas->xa_offset = xas->xa_node->offset + 1;
+			xas->xa_node = xa_parent(xa, xas->xa_node);
+			continue;
+		}
+
+		entry = xa_entry(xa, xas->xa_node, offset);
+		if (!xa_is_node(entry))
+			break;
+		xas->xa_node = xa_node(entry);
+		xas->xa_offset = xas_offset(xas);
+		entry = XA_WALK_END;
+	}
+
+	if (entry == XA_WALK_END)
+		xas->xa_node = XA_WALK_RESTART;
+	return entry;
+}
+EXPORT_SYMBOL_GPL(xas_find_tag);
+
+/**
+ * xa_load() - Load the entry from the array
+ * @xa: Array
+ * @index: index in array
+ *
+ * Return: The entry at @index in @xa.
+ */
+void *xa_load(const struct xarray *xa, unsigned long index)
+{
+	struct xa_state xas;
+	void *entry;
+
+	xas_init(&xas, index);
+	rcu_read_lock();
+	entry = xas_start(xa, &xas);
+	while (xa_is_node(entry)) {
+		entry = xas_descend(xa, &xas, xa_node(entry));
+		if (xa_is_retry(entry))
+			entry = xas_start(xa, &xas);
+	}
+	rcu_read_unlock();
+
+	if (entry == XA_WALK_END)
+		entry = NULL;
+	return entry;
+}
+EXPORT_SYMBOL(xa_load);
+
+/**
+ * xa_store() - Store this entry in the array
+ * @xa: Array
+ * @index: index in array
+ * @entry: New entry
+ * @gfp: Allocation flags
+ *
+ * Stores almost always succeed.  The notable exceptions:
+ *  - Attempted to store a reserved pointer value (-EINVAL)
+ *  - Ran out of memory trying to allocate new nodes (-ENOMEM)
+ *
+ * Storing into an existing multientry updates the value of every index.
+ *
+ * Return: The old value at this index or ERR_PTR() if an error happened
+ */
+void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
+{
+	struct xa_state xas;
+	unsigned long flags;
+	void *curr;
+
+	if (WARN_ON_ONCE(xa_is_internal(entry)))
+		return ERR_PTR(-EINVAL);
+
+	xas_init(&xas, index);
+	do {
+		xa_lock_irqsave(xa, flags);
+		curr = xas_store(xa, &xas, entry);
+		xa_unlock_irqrestore(xa, flags);
+	} while (xas_nomem(&xas, gfp));
+	xas_destroy(&xas);
+
+	if (xas_error(&xas))
+		curr = xas.xa_node;
+	return curr;
+}
+EXPORT_SYMBOL(xa_store);
+
+/**
+ * xa_replace() - Conditionally replace this entry in the array
+ * @xa: Array
+ * @index: index in array
+ * @entry: New value to place in array
+ * @old: Old value to test against
+ * @gfp: Allocation flags
+ *
+ * If the entry at @index is the same as @old, replace it with @entry.
+ * If the return value is equal to @old, then the exchange was successful.
+ *
+ * Return: The old value at this index or ERR_PTR() if an error happened
+ */
+void *xa_replace(struct xarray *xa, unsigned long index,
+		void *entry, void *old, gfp_t gfp)
+{
+	struct xa_state xas;
+	unsigned long flags;
+	void *curr;
+
+	if (WARN_ON_ONCE(xa_is_internal(entry)))
+		return ERR_PTR(-EINVAL);
+
+	xas_init(&xas, index);
+	do {
+		xa_lock_irqsave(xa, flags);
+		curr = xas_create(xa, &xas);
+		if (curr == old)
+			xas_store(xa, &xas, entry);
+		xa_unlock_irqrestore(xa, flags);
+	} while (xas_nomem(&xas, gfp));
+	xas_destroy(&xas);
+
+	if (xas_error(&xas))
+		curr = xas.xa_node;
+	return curr;
+}
+EXPORT_SYMBOL(xa_replace);
+
+/**
+ * xa_get_tag() - Inquire whether this tag is set on this entry
+ * @xa: Array
+ * @index: Index of entry
+ * @tag: Tag value
+ *
+ * This function is protected by the RCU read lock, so the result may be
+ * out of date by the time it returns.  If you need the result to be stable,
+ * use a lock.
+ *
+ * Return: True if the entry at @index has this tag set, false if it doesn't.
+ */
+bool __xa_get_tag(const struct xarray *xa, unsigned long index, xa_tag_t tag)
+{
+	struct xa_state xas;
+	void *entry;
+
+	xas_init(&xas, index);
+	rcu_read_lock();
+	entry = xas_start(xa, &xas);
+	while (xas_get_tag(xa, &xas, tag)) {
+		if (!xa_is_node(entry))
+			goto found;
+		entry = xas_descend(xa, &xas, xa_node(entry));
+	}
+	rcu_read_unlock();
+	return false;
+found:
+	rcu_read_unlock();
+	return true;
+}
+EXPORT_SYMBOL(__xa_get_tag);
+
+/**
+ * xa_set_tag() - Set this tag on this entry.
+ * @xa: Array
+ * @index: Index of entry
+ * @tag: Tag value
+ *
+ * Attempting to set a tag on a NULL entry does not succeed.
+ *
+ * Return: The entry at this index or ERR_PTR() if an error occurs.
+ */
+void *__xa_set_tag(struct xarray *xa, unsigned long index, xa_tag_t tag)
+{
+	struct xa_state xas;
+	unsigned long flags;
+	void *entry;
+
+	xas_init(&xas, index);
+	xa_lock_irqsave(xa, flags);
+	entry = xas_load(xa, &xas);
+	if (entry == XA_WALK_END)
+		entry = NULL;
+	if (entry)
+		xas_set_tag(xa, &xas, tag);
+	xa_unlock_irqrestore(xa, flags);
+
+	return entry;
+}
+EXPORT_SYMBOL(__xa_set_tag);
+
+/**
+ * xa_clear_tag() - Clear this tag on this entry.
+ * @xa: Array
+ * @index: Index of entry
+ * @tag: Tag value
+ *
+ * Clearing a tag on an entry which doesn't exist always succeeds
+ *
+ * Return: The entry at this index or ERR_PTR() if an error occurs.
+ */
+void *__xa_clear_tag(struct xarray *xa, unsigned long index, xa_tag_t tag)
+{
+	struct xa_state xas;
+	unsigned long flags;
+	void *entry;
+
+	xas_init(&xas, index);
+	xa_lock_irqsave(xa, flags);
+	entry = xas_load(xa, &xas);
+	if (entry == XA_WALK_END)
+		entry = NULL;
+	if (entry)
+		xas_clear_tag(xa, &xas, tag);
+	xa_unlock_irqrestore(xa, flags);
+
+	return entry;
+}
+EXPORT_SYMBOL(__xa_clear_tag);
+
+/**
+ * xa_find() - Search the xarray for a present entry
+ * @xa: Array
+ * @indexp: Pointer to an index
+ * @max: Maximum value to return
+ *
+ * Finds the entry in the xarray with the lowest index that is between
+ * *@indexp and max, inclusive.  If an entry is found, updates @indexp to
+ * be the index of the pointer.  This function is protected by the RCU read
+ * lock, so it may not find all entries if called in a loop.
+ *
+ * Return: The pointer, if found, otherwise NULL.
+ */
+void *xa_find(const struct xarray *xa, unsigned long *indexp, unsigned long max)
+{
+	struct xa_state xas;
+	void *entry;
+
+	xas_init(&xas, *indexp);
+
+	rcu_read_lock();
+	do {
+		entry = xas_next(xa, &xas, max);
+		if (xa_is_retry(entry))
+			xas_retry(&xas);
+		if (entry == XA_WALK_END)
+			entry = NULL;
+	} while (xa_is_internal(entry));
+	rcu_read_unlock();
+
+	if (entry)
+		*indexp = xas.xa_index;
+	return entry;
+}
+EXPORT_SYMBOL(xa_find);
+
+/**
+ * xa_next() - Search the xarray for the next present entry
+ * @xa: Array
+ * @indexp: Pointer to an index
+ * @max: Maximum value to return
+ *
+ * Finds the entry in the xarray with the lowest index that is above
+ * *@indexp and not greater than max.  If an entry is found, updates
+ * @indexp to be the index of the pointer.
+ *
+ * Return: The pointer, if found, otherwise NULL.
+ */
+void *xa_next(const struct xarray *xa, unsigned long *indexp, unsigned long max)
+{
+	struct xa_state xas;
+	void *entry;
+
+	xas_init(&xas, *indexp + 1);
+	xas.xa_flags &= ~XAS_FLAG_LOOKUP;
+
+	rcu_read_lock();
+	do {
+		entry = xas_next(xa, &xas, max);
+		if (xa_is_retry(entry))
+			xas_retry(&xas);
+		if (entry == XA_WALK_END)
+			entry = NULL;
+	} while (xa_is_internal(entry));
+	rcu_read_unlock();
+
+	if (entry)
+		*indexp = xas.xa_index;
+	return entry;
+}
+EXPORT_SYMBOL(xa_next);
+
+/**
+ * xa_get_entries() - Copy entries from the xarray into a normal array
+ * @xa: The source XArray to copy from
+ * @dst: The buffer to copy pointers into
+ * @start: The first index in the XArray eligible to be copied from
+ * @n: The maximum number of entries to copy
+ *
+ * Return: The number of entries copied.
+ */
+int xa_get_entries(const struct xarray *xa, unsigned long start, void **dst,
+		unsigned int n)
+{
+	struct xa_state xas;
+	void *entry;
+	unsigned int i = 0;
+
+	if (!n)
+		return 0;
+
+	xas_init(&xas, start);
+	rcu_read_lock();
+	xas_for_each(xa, &xas, entry, ~0UL) {
+		if (xa_is_retry(entry)) {
+			xas_retry(&xas);
+			continue;
+		}
+		dst[i++] = entry;
+		if (i == n)
+			break;
+	}
+	rcu_read_unlock();
+
+	return i;
+}
+EXPORT_SYMBOL(xa_get_entries);
+
+/**
+ * xa_get_tagged() - Copy tagged entries from the xarray into a normal array
+ * @xa: The source XArray to copy from
+ * @dst: The buffer to copy pointers into
+ * @start: The first index in the XArray eligible to be copied from
+ * @n: The maximum number of entries to copy
+ *
+ * Return: The number of entries copied.
+ */
+int xa_get_tagged(const struct xarray *xa, unsigned long start, void **dst,
+		unsigned int n, xa_tag_t tag)
+{
+	struct xa_state xas;
+	void *entry;
+	unsigned int i = 0;
+
+	if (!n)
+		return 0;
+
+	xas_init(&xas, start);
+	rcu_read_lock();
+	xas_for_each_tag(xa, &xas, entry, ~0UL) {
+		if (xa_is_retry(entry)) {
+			xas_retry(&xas);
+			continue;
+		}
+		dst[i++] = entry;
+		if (i == n)
+			break;
+	}
+	rcu_read_unlock();
+
+	return i;
+}
+EXPORT_SYMBOL(xa_get_tagged);
+
+void __init xarray_init(void)
+{
+	xa_node_cache = kmem_cache_create("xarray node",
+				sizeof(struct xa_node), 0,
+				SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
+				xa_node_ctor);
+}
-- 
2.11.0

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

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

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@microsoft.com>
---
 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

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

[kbuild test robot]

Hi Matthew,

[auto build test WARNING on linus/master]
[also build test WARNING on next-20170302]
[cannot apply to v4.10]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]

url:    https://github.com/0day-ci/linux/commits/Matthew-Wilcox/Add-XArray/20170302-092723
reproduce:
        # apt-get install sparse
        make ARCH=x86_64 allmodconfig
        make C=1 CF=-D__CHECK_ENDIAN__


sparse warnings: (new ones prefixed by >>)

   include/linux/compiler.h:264:8: sparse: attribute 'no_sanitize_address': unknown attribute
   drivers/gpu/drm/drm_mode_config.c:369:9: sparse: Expected ; at end of statement
   drivers/gpu/drm/drm_mode_config.c:369:9: sparse: got {
   drivers/gpu/drm/drm_mode_config.c:370:9: sparse: Expected ; at end of statement
   drivers/gpu/drm/drm_mode_config.c:370:9: sparse: got {
>> drivers/gpu/drm/drm_mode_config.c:384:1: sparse: expected 'while' after 'do'
   drivers/gpu/drm/drm_mode_config.c:384:1: sparse: Expected ( after 'do-while'
   drivers/gpu/drm/drm_mode_config.c:384:1: sparse: got extern
   builtin:0:0: sparse: Expected } at end of compound statement
   builtin:0:0: sparse: got end-of-input
   builtin:0:0: sparse: expected 'while' after 'do'
   builtin:0:0: sparse: Expected } at end of function
   builtin:0:0: sparse: got end-of-input
   drivers/gpu/drm/drm_mode_config.c:371:9: sparse: undefined identifier 'ida_init'
   In file included from include/linux/kernfs.h:14:0,
                    from include/linux/sysfs.h:15,
                    from include/linux/kobject.h:21,
                    from include/linux/device.h:17,
                    from include/linux/i2c.h:30,
                    from include/drm/drm_crtc.h:28,
                    from include/drm/drm_encoder.h:28,
                    from drivers/gpu/drm/drm_mode_config.c:23:
   drivers/gpu/drm/drm_mode_config.c: In function 'drm_mode_config_init':
   include/linux/idr.h:25:1: error: expected expression before '{' token
    {       \
    ^
   include/linux/idr.h:30:11: note: in expansion of macro 'IDR_INIT'
     *(idr) = IDR_INIT(#idr)    \
              ^~~~~~~~
   drivers/gpu/drm/drm_mode_config.c:369:2: note: in expansion of macro 'idr_init'
     idr_init(&dev->mode_config.crtc_idr);
     ^~~~~~~~
   include/linux/idr.h:25:1: error: expected expression before '{' token
    {       \
    ^
   include/linux/idr.h:30:11: note: in expansion of macro 'IDR_INIT'
     *(idr) = IDR_INIT(#idr)    \
              ^~~~~~~~
   drivers/gpu/drm/drm_mode_config.c:370:2: note: in expansion of macro 'idr_init'
     idr_init(&dev->mode_config.tile_idr);
     ^~~~~~~~
   drivers/gpu/drm/drm_mode_config.c:371:2: error: implicit declaration of function 'ida_init' [-Werror=implicit-function-declaration]
     ida_init(&dev->mode_config.connector_ida);
     ^~~~~~~~
   cc1: some warnings being treated as errors
--
   include/linux/compiler.h:264:8: sparse: attribute 'no_sanitize_address': unknown attribute
   drivers/net/wireless/ath/ath10k/htt_tx.c:407:9: sparse: Expected ; at end of statement
   drivers/net/wireless/ath/ath10k/htt_tx.c:407:9: sparse: got {
>> drivers/net/wireless/ath/ath10k/htt_tx.c:426:1: sparse: expected 'while' after 'do'
   drivers/net/wireless/ath/ath10k/htt_tx.c:426:1: sparse: Expected ( after 'do-while'
   drivers/net/wireless/ath/ath10k/htt_tx.c:426:1: sparse: got static
   drivers/net/wireless/ath/ath10k/htt_tx.c:432:71: sparse: undefined identifier 'msdu_id'
   drivers/net/wireless/ath/ath10k/htt_tx.c:434:27: sparse: undefined identifier 'msdu_id'
   drivers/net/wireless/ath/ath10k/htt_tx.c:456:40: sparse: undefined identifier 'ath10k_htt_tx_clean_up_pending'
   In file included from include/linux/cgroup-defs.h:12:0,
                    from include/linux/sched.h:60,
                    from include/linux/kasan.h:4,
                    from include/linux/slab.h:118,
                    from include/linux/textsearch.h:8,
                    from include/linux/skbuff.h:30,
                    from include/linux/if_ether.h:23,
                    from include/linux/etherdevice.h:25,
                    from drivers/net/wireless/ath/ath10k/htt_tx.c:18:
   drivers/net/wireless/ath/ath10k/htt_tx.c: In function 'ath10k_htt_tx_start':
   include/linux/idr.h:25:1: error: expected expression before '{' token
    {       \
    ^
   include/linux/idr.h:30:11: note: in expansion of macro 'IDR_INIT'
     *(idr) = IDR_INIT(#idr)    \
              ^~~~~~~~
   drivers/net/wireless/ath/ath10k/htt_tx.c:407:2: note: in expansion of macro 'idr_init'
     idr_init(&htt->pending_tx);
     ^~~~~~~~
--
   include/linux/compiler.h:264:8: sparse: attribute 'no_sanitize_address': unknown attribute
   drivers/net/wireless/marvell/mwifiex/init.c:495:17: sparse: Expected ; at end of statement
   drivers/net/wireless/marvell/mwifiex/init.c:495:17: sparse: got {
>> drivers/net/wireless/marvell/mwifiex/init.c:498:9: sparse: expected 'while' after 'do'
   drivers/net/wireless/marvell/mwifiex/init.c:498:9: sparse: Expected ( after 'do-while'
   drivers/net/wireless/marvell/mwifiex/init.c:498:9: sparse: got return
   builtin:0:0: sparse: Expected } at end of function
   builtin:0:0: sparse: got end-of-input
   In file included from include/linux/cgroup-defs.h:12:0,
                    from include/linux/sched.h:60,
                    from include/linux/kasan.h:4,
                    from include/linux/slab.h:118,
                    from include/linux/textsearch.h:8,
                    from include/linux/skbuff.h:30,
                    from include/linux/if_ether.h:23,
                    from include/linux/ieee80211.h:21,
                    from drivers/net/wireless/marvell/mwifiex/decl.h:28,
                    from drivers/net/wireless/marvell/mwifiex/init.c:20:
   drivers/net/wireless/marvell/mwifiex/init.c: In function 'mwifiex_init_lock_list':
   include/linux/idr.h:25:1: error: expected expression before '{' token
    {       \
    ^
   include/linux/idr.h:30:11: note: in expansion of macro 'IDR_INIT'
     *(idr) = IDR_INIT(#idr)    \
              ^~~~~~~~
   drivers/net/wireless/marvell/mwifiex/init.c:495:3: note: in expansion of macro 'idr_init'
      idr_init(&priv->ack_status_frames);
      ^~~~~~~~
--
   include/linux/compiler.h:264:8: sparse: attribute 'no_sanitize_address': unknown attribute
   drivers/staging/unisys/visorhba/visorhba_main.c:1111:9: sparse: Expected ; at end of statement
   drivers/staging/unisys/visorhba/visorhba_main.c:1111:9: sparse: got {
>> drivers/staging/unisys/visorhba/visorhba_main.c:1142:1: sparse: expected 'while' after 'do'
   drivers/staging/unisys/visorhba/visorhba_main.c:1142:1: sparse: Expected ( after 'do-while'
   drivers/staging/unisys/visorhba/visorhba_main.c:1142:1: sparse: got static
   drivers/staging/unisys/visorhba/visorhba_main.c:1148:17: sparse: return with no return value
   drivers/staging/unisys/visorhba/visorhba_main.c:1171:19: sparse: undefined identifier 'visorhba_remove'
   In file included from include/linux/cgroup-defs.h:12:0,
                    from include/linux/sched.h:60,
                    from include/linux/kasan.h:4,
                    from include/linux/slab.h:118,
                    from include/linux/textsearch.h:8,
                    from include/linux/skbuff.h:30,
                    from drivers/staging/unisys/visorhba/visorhba_main.c:17:
   drivers/staging/unisys/visorhba/visorhba_main.c: In function 'visorhba_probe':
   include/linux/idr.h:25:1: error: expected expression before '{' token
    {       \
    ^
   include/linux/idr.h:30:11: note: in expansion of macro 'IDR_INIT'
     *(idr) = IDR_INIT(#idr)    \
              ^~~~~~~~
   drivers/staging/unisys/visorhba/visorhba_main.c:1111:2: note: in expansion of macro 'idr_init'
     idr_init(&devdata->idr);
     ^~~~~~~~

vim +384 drivers/gpu/drm/drm_mode_config.c

28575f16 Daniel Vetter 2016-11-14  363  	INIT_LIST_HEAD(&dev->mode_config.crtc_list);
28575f16 Daniel Vetter 2016-11-14  364  	INIT_LIST_HEAD(&dev->mode_config.connector_list);
28575f16 Daniel Vetter 2016-11-14  365  	INIT_LIST_HEAD(&dev->mode_config.encoder_list);
28575f16 Daniel Vetter 2016-11-14  366  	INIT_LIST_HEAD(&dev->mode_config.property_list);
28575f16 Daniel Vetter 2016-11-14  367  	INIT_LIST_HEAD(&dev->mode_config.property_blob_list);
28575f16 Daniel Vetter 2016-11-14  368  	INIT_LIST_HEAD(&dev->mode_config.plane_list);
28575f16 Daniel Vetter 2016-11-14 @369  	idr_init(&dev->mode_config.crtc_idr);
28575f16 Daniel Vetter 2016-11-14  370  	idr_init(&dev->mode_config.tile_idr);
28575f16 Daniel Vetter 2016-11-14  371  	ida_init(&dev->mode_config.connector_ida);
613051da Daniel Vetter 2016-12-14  372  	spin_lock_init(&dev->mode_config.connector_list_lock);
28575f16 Daniel Vetter 2016-11-14  373  
28575f16 Daniel Vetter 2016-11-14  374  	drm_mode_create_standard_properties(dev);
28575f16 Daniel Vetter 2016-11-14  375  
28575f16 Daniel Vetter 2016-11-14  376  	/* Just to be sure */
28575f16 Daniel Vetter 2016-11-14  377  	dev->mode_config.num_fb = 0;
28575f16 Daniel Vetter 2016-11-14  378  	dev->mode_config.num_connector = 0;
28575f16 Daniel Vetter 2016-11-14  379  	dev->mode_config.num_crtc = 0;
28575f16 Daniel Vetter 2016-11-14  380  	dev->mode_config.num_encoder = 0;
28575f16 Daniel Vetter 2016-11-14  381  	dev->mode_config.num_overlay_plane = 0;
28575f16 Daniel Vetter 2016-11-14  382  	dev->mode_config.num_total_plane = 0;
28575f16 Daniel Vetter 2016-11-14  383  }
28575f16 Daniel Vetter 2016-11-14 @384  EXPORT_SYMBOL(drm_mode_config_init);
28575f16 Daniel Vetter 2016-11-14  385  
28575f16 Daniel Vetter 2016-11-14  386  /**
28575f16 Daniel Vetter 2016-11-14  387   * drm_mode_config_cleanup - free up DRM mode_config info

:::::: The code at line 384 was first introduced by commit
:::::: 28575f165d36051310d7ea2350e2011f8095b6fb drm: Extract drm_mode_config.[hc]

:::::: TO: Daniel Vetter <daniel.vetter@ffwll.ch>
:::::: CC: Daniel Vetter <daniel.vetter@ffwll.ch>

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation