summaryrefslogtreecommitdiff
path: root/lib/xarray.c
diff options
context:
space:
mode:
authorMatthew Wilcox <willy@infradead.org>2018-10-26 21:43:22 +0300
committerMatthew Wilcox <willy@infradead.org>2019-02-06 21:13:24 +0300
commit3ccaf57a6a63ad171a951dcaddffc453b2414c7b (patch)
treefc2202432a5b50ee5507a2e240b439b2993c2c3f /lib/xarray.c
parentfd9dc93e36231fb6d520e0edd467058fad4fd12d (diff)
downloadlinux-3ccaf57a6a63ad171a951dcaddffc453b2414c7b.tar.xz
XArray: Add support for 1s-based allocation
A lot of places want to allocate IDs starting at 1 instead of 0. While the xa_alloc() API supports this, it's not very efficient if lots of IDs are allocated, due to having to walk down to the bottom of the tree to see if ID 1 is available, then all the way over to the next non-allocated ID. This method marks ID 0 as being occupied which wastes one slot in the XArray, but preserves xa_empty() as working. Signed-off-by: Matthew Wilcox <willy@infradead.org>
Diffstat (limited to 'lib/xarray.c')
-rw-r--r--lib/xarray.c11
1 files changed, 11 insertions, 0 deletions
diff --git a/lib/xarray.c b/lib/xarray.c
index 1b97ca58bd15..468fb7b7963f 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -57,6 +57,11 @@ static inline bool xa_track_free(const struct xarray *xa)
return xa->xa_flags & XA_FLAGS_TRACK_FREE;
}
+static inline bool xa_zero_busy(const struct xarray *xa)
+{
+ return xa->xa_flags & XA_FLAGS_ZERO_BUSY;
+}
+
static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark)
{
if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))
@@ -432,6 +437,8 @@ static void xas_shrink(struct xa_state *xas)
break;
if (!xa_is_node(entry) && node->shift)
break;
+ if (xa_is_zero(entry) && xa_zero_busy(xa))
+ entry = NULL;
xas->xa_node = XAS_BOUNDS;
RCU_INIT_POINTER(xa->xa_head, entry);
@@ -628,6 +635,8 @@ static void *xas_create(struct xa_state *xas, bool allow_root)
if (xas_top(node)) {
entry = xa_head_locked(xa);
xas->xa_node = NULL;
+ if (!entry && xa_zero_busy(xa))
+ entry = XA_ZERO_ENTRY;
shift = xas_expand(xas, entry);
if (shift < 0)
return NULL;
@@ -1942,6 +1951,8 @@ void xa_destroy(struct xarray *xa)
entry = xa_head_locked(xa);
RCU_INIT_POINTER(xa->xa_head, NULL);
xas_init_marks(&xas);
+ if (xa_zero_busy(xa))
+ xa_mark_clear(xa, XA_FREE_MARK);
/* lockdep checks we're still holding the lock in xas_free_nodes() */
if (xa_is_node(entry))
xas_free_nodes(&xas, xa_to_node(entry));