summaryrefslogtreecommitdiff
path: root/lib/test_xarray.c
diff options
context:
space:
mode:
authorMatthew Wilcox <willy@infradead.org>2018-11-06 14:13:35 -0500
committerMatthew Wilcox <willy@infradead.org>2019-02-06 13:32:25 -0500
commit2fa044e51a1f35d7b04cbde07ec513b0ba195e38 (patch)
treeca7f9f39820ca4f8241caf7a6eef8f044db5d38a /lib/test_xarray.c
parenta3e4d3f97ec844de005a679585c04c5c03dfbdb6 (diff)
downloadlwn-2fa044e51a1f35d7b04cbde07ec513b0ba195e38.tar.gz
lwn-2fa044e51a1f35d7b04cbde07ec513b0ba195e38.zip
XArray: Add cyclic allocation
This differs slightly from the IDR equivalent in five ways. 1. It can allocate up to UINT_MAX instead of being limited to INT_MAX, like xa_alloc(). Also like xa_alloc(), it will write to the 'id' pointer before placing the entry in the XArray. 2. The 'next' cursor is allocated separately from the XArray instead of being part of the IDR. This saves memory for all the users which do not use the cyclic allocation API and suits some users better. 3. It returns -EBUSY instead of -ENOSPC. 4. It will attempt to wrap back to the minimum value on memory allocation failure as well as on an -EBUSY error, assuming that a user would rather allocate a small ID than suffer an ID allocation failure. 5. It reports whether it has wrapped, which is important to some users. Signed-off-by: Matthew Wilcox <willy@infradead.org>
Diffstat (limited to 'lib/test_xarray.c')
-rw-r--r--lib/test_xarray.c53
1 files changed, 53 insertions, 0 deletions
diff --git a/lib/test_xarray.c b/lib/test_xarray.c
index b5a6b981454d..eaf53f742c72 100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -715,6 +715,57 @@ static noinline void check_xa_alloc_2(struct xarray *xa, unsigned int base)
xa_destroy(xa);
}
+static noinline void check_xa_alloc_3(struct xarray *xa, unsigned int base)
+{
+ struct xa_limit limit = XA_LIMIT(1, 0x3fff);
+ u32 next = 0;
+ unsigned int i, id;
+ unsigned long index;
+ void *entry;
+
+ XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(1), limit,
+ &next, GFP_KERNEL) != 0);
+ XA_BUG_ON(xa, id != 1);
+
+ next = 0x3ffd;
+ XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(0x3ffd), limit,
+ &next, GFP_KERNEL) != 0);
+ XA_BUG_ON(xa, id != 0x3ffd);
+ xa_erase_index(xa, 0x3ffd);
+ xa_erase_index(xa, 1);
+ XA_BUG_ON(xa, !xa_empty(xa));
+
+ for (i = 0x3ffe; i < 0x4003; i++) {
+ if (i < 0x4000)
+ entry = xa_mk_index(i);
+ else
+ entry = xa_mk_index(i - 0x3fff);
+ XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, entry, limit,
+ &next, GFP_KERNEL) != (id == 1));
+ XA_BUG_ON(xa, xa_mk_index(id) != entry);
+ }
+
+ /* Check wrap-around is handled correctly */
+ if (base != 0)
+ xa_erase_index(xa, base);
+ xa_erase_index(xa, base + 1);
+ next = UINT_MAX;
+ XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(UINT_MAX),
+ xa_limit_32b, &next, GFP_KERNEL) != 0);
+ XA_BUG_ON(xa, id != UINT_MAX);
+ XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base),
+ xa_limit_32b, &next, GFP_KERNEL) != 1);
+ XA_BUG_ON(xa, id != base);
+ XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base + 1),
+ xa_limit_32b, &next, GFP_KERNEL) != 0);
+ XA_BUG_ON(xa, id != base + 1);
+
+ xa_for_each(xa, index, entry)
+ xa_erase_index(xa, index);
+
+ XA_BUG_ON(xa, !xa_empty(xa));
+}
+
static DEFINE_XARRAY_ALLOC(xa0);
static DEFINE_XARRAY_ALLOC1(xa1);
@@ -724,6 +775,8 @@ static noinline void check_xa_alloc(void)
check_xa_alloc_1(&xa1, 1);
check_xa_alloc_2(&xa0, 0);
check_xa_alloc_2(&xa1, 1);
+ check_xa_alloc_3(&xa0, 0);
+ check_xa_alloc_3(&xa1, 1);
}
static noinline void __check_store_iter(struct xarray *xa, unsigned long start,