XArray: Add support for 1s-based allocation
authorMatthew Wilcox <willy@infradead.org>
Fri, 26 Oct 2018 18:43:22 +0000 (14:43 -0400)
committerMatthew Wilcox <willy@infradead.org>
Wed, 6 Feb 2019 18:13:24 +0000 (13:13 -0500)
commit3ccaf57a6a63ad171a951dcaddffc453b2414c7b
treefc2202432a5b50ee5507a2e240b439b2993c2c3f
parentfd9dc93e36231fb6d520e0edd467058fad4fd12d
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>
Documentation/core-api/xarray.rst
include/linux/xarray.h
lib/test_xarray.c
lib/xarray.c