Skip to content

Commit f8d5d0c

Browse files
author
Matthew Wilcox
committed
xarray: Add definition of struct xarray
This is a direct replacement for struct radix_tree_root. Some of the struct members have changed name; convert those, and use a #define so that radix_tree users continue to work without change. Signed-off-by: Matthew Wilcox <willy@infradead.org> Reviewed-by: Josef Bacik <jbacik@fb.com>
1 parent 02c02bf commit f8d5d0c

File tree

12 files changed

+181
-68
lines changed

12 files changed

+181
-68
lines changed

‎include/linux/radix-tree.h

Lines changed: 8 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,9 @@
3030
#include <linux/types.h>
3131
#include <linux/xarray.h>
3232

33+
/* Keep unconverted code working */
34+
#define radix_tree_root xarray
35+
3336
/*
3437
* The bottom two bits of the slot determine how the remaining bits in the
3538
* slot are interpreted:
@@ -92,36 +95,21 @@ struct radix_tree_node {
9295
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
9396
};
9497

95-
/* The IDR tag is stored in the low bits of the GFP flags */
98+
/* The IDR tag is stored in the low bits of xa_flags */
9699
#define ROOT_IS_IDR ((__force gfp_t)4)
97-
/* The top bits of gfp_mask are used to store the root tags */
100+
/* The top bits of xa_flags are used to store the root tags */
98101
#define ROOT_TAG_SHIFT (__GFP_BITS_SHIFT)
99102

100-
struct radix_tree_root {
101-
spinlock_t xa_lock;
102-
gfp_t gfp_mask;
103-
struct radix_tree_node __rcu *rnode;
104-
};
105-
106-
#define RADIX_TREE_INIT(name, mask) { \
107-
.xa_lock = __SPIN_LOCK_UNLOCKED(name.xa_lock), \
108-
.gfp_mask = (mask), \
109-
.rnode = NULL, \
110-
}
103+
#define RADIX_TREE_INIT(name, mask) XARRAY_INIT(name, mask)
111104

112105
#define RADIX_TREE(name, mask) \
113106
struct radix_tree_root name = RADIX_TREE_INIT(name, mask)
114107

115-
#define INIT_RADIX_TREE(root, mask) \
116-
do { \
117-
spin_lock_init(&(root)->xa_lock); \
118-
(root)->gfp_mask = (mask); \
119-
(root)->rnode = NULL; \
120-
} while (0)
108+
#define INIT_RADIX_TREE(root, mask) xa_init_flags(root, mask)
121109

122110
static inline bool radix_tree_empty(const struct radix_tree_root *root)
123111
{
124-
return root->rnode == NULL;
112+
return root->xa_head == NULL;
125113
}
126114

127115
/**

‎include/linux/xarray.h

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,8 @@
1010
*/
1111

1212
#include <linux/bug.h>
13+
#include <linux/compiler.h>
14+
#include <linux/kconfig.h>
1315
#include <linux/spinlock.h>
1416
#include <linux/types.h>
1517

@@ -153,6 +155,74 @@ static inline bool xa_is_internal(const void *entry)
153155
return ((unsigned long)entry & 3) == 2;
154156
}
155157

158+
/**
159+
* struct xarray - The anchor of the XArray.
160+
* @xa_lock: Lock that protects the contents of the XArray.
161+
*
162+
* To use the xarray, define it statically or embed it in your data structure.
163+
* It is a very small data structure, so it does not usually make sense to
164+
* allocate it separately and keep a pointer to it in your data structure.
165+
*
166+
* You may use the xa_lock to protect your own data structures as well.
167+
*/
168+
/*
169+
* If all of the entries in the array are NULL, @xa_head is a NULL pointer.
170+
* If the only non-NULL entry in the array is at index 0, @xa_head is that
171+
* entry. If any other entry in the array is non-NULL, @xa_head points
172+
* to an @xa_node.
173+
*/
174+
struct xarray {
175+
spinlock_t xa_lock;
176+
/* private: The rest of the data structure is not to be used directly. */
177+
gfp_t xa_flags;
178+
void __rcu * xa_head;
179+
};
180+
181+
#define XARRAY_INIT(name, flags) { \
182+
.xa_lock = __SPIN_LOCK_UNLOCKED(name.xa_lock), \
183+
.xa_flags = flags, \
184+
.xa_head = NULL, \
185+
}
186+
187+
/**
188+
* DEFINE_XARRAY_FLAGS() - Define an XArray with custom flags.
189+
* @name: A string that names your XArray.
190+
* @flags: XA_FLAG values.
191+
*
192+
* This is intended for file scope definitions of XArrays. It declares
193+
* and initialises an empty XArray with the chosen name and flags. It is
194+
* equivalent to calling xa_init_flags() on the array, but it does the
195+
* initialisation at compiletime instead of runtime.
196+
*/
197+
#define DEFINE_XARRAY_FLAGS(name, flags) \
198+
struct xarray name = XARRAY_INIT(name, flags)
199+
200+
/**
201+
* DEFINE_XARRAY() - Define an XArray.
202+
* @name: A string that names your XArray.
203+
*
204+
* This is intended for file scope definitions of XArrays. It declares
205+
* and initialises an empty XArray with the chosen name. It is equivalent
206+
* to calling xa_init() on the array, but it does the initialisation at
207+
* compiletime instead of runtime.
208+
*/
209+
#define DEFINE_XARRAY(name) DEFINE_XARRAY_FLAGS(name, 0)
210+
211+
void xa_init_flags(struct xarray *, gfp_t flags);
212+
213+
/**
214+
* xa_init() - Initialise an empty XArray.
215+
* @xa: XArray.
216+
*
217+
* An empty XArray is full of NULL entries.
218+
*
219+
* Context: Any context.
220+
*/
221+
static inline void xa_init(struct xarray *xa)
222+
{
223+
xa_init_flags(xa, 0);
224+
}
225+
156226
#define xa_trylock(xa) spin_trylock(&(xa)->xa_lock)
157227
#define xa_lock(xa) spin_lock(&(xa)->xa_lock)
158228
#define xa_unlock(xa) spin_unlock(&(xa)->xa_lock)

‎lib/Makefile

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@ KCOV_INSTRUMENT_debugobjects.o := n
1818
KCOV_INSTRUMENT_dynamic_debug.o := n
1919

2020
lib-y := ctype.o string.o vsprintf.o cmdline.o \
21-
rbtree.o radix-tree.o timerqueue.o\
21+
rbtree.o radix-tree.o timerqueue.o xarray.o \
2222
idr.o int_sqrt.o extable.o \
2323
sha1.o chacha20.o irq_regs.o argv_split.o \
2424
flex_proportions.o ratelimit.o show_mem.o \

‎lib/idr.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -39,8 +39,8 @@ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
3939
unsigned int base = idr->idr_base;
4040
unsigned int id = *nextid;
4141

42-
if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR)))
43-
idr->idr_rt.gfp_mask |= IDR_RT_MARKER;
42+
if (WARN_ON_ONCE(!(idr->idr_rt.xa_flags & ROOT_IS_IDR)))
43+
idr->idr_rt.xa_flags |= IDR_RT_MARKER;
4444

4545
id = (id < base) ? 0 : id - base;
4646
radix_tree_iter_init(&iter, id);

0 commit comments

Comments
 (0)