Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0+
0002 /*
0003  * test_xarray.c: Test the XArray API
0004  * Copyright (c) 2017-2018 Microsoft Corporation
0005  * Copyright (c) 2019-2020 Oracle
0006  * Author: Matthew Wilcox <willy@infradead.org>
0007  */
0008 
0009 #include <linux/xarray.h>
0010 #include <linux/module.h>
0011 
0012 static unsigned int tests_run;
0013 static unsigned int tests_passed;
0014 
0015 static const unsigned int order_limit =
0016         IS_ENABLED(CONFIG_XARRAY_MULTI) ? BITS_PER_LONG : 1;
0017 
0018 #ifndef XA_DEBUG
0019 # ifdef __KERNEL__
0020 void xa_dump(const struct xarray *xa) { }
0021 # endif
0022 #undef XA_BUG_ON
0023 #define XA_BUG_ON(xa, x) do {                   \
0024     tests_run++;                        \
0025     if (x) {                        \
0026         printk("BUG at %s:%d\n", __func__, __LINE__);   \
0027         xa_dump(xa);                    \
0028         dump_stack();                   \
0029     } else {                        \
0030         tests_passed++;                 \
0031     }                           \
0032 } while (0)
0033 #endif
0034 
0035 static void *xa_mk_index(unsigned long index)
0036 {
0037     return xa_mk_value(index & LONG_MAX);
0038 }
0039 
0040 static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp)
0041 {
0042     return xa_store(xa, index, xa_mk_index(index), gfp);
0043 }
0044 
0045 static void xa_insert_index(struct xarray *xa, unsigned long index)
0046 {
0047     XA_BUG_ON(xa, xa_insert(xa, index, xa_mk_index(index),
0048                 GFP_KERNEL) != 0);
0049 }
0050 
0051 static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp)
0052 {
0053     u32 id;
0054 
0055     XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(index), xa_limit_32b,
0056                 gfp) != 0);
0057     XA_BUG_ON(xa, id != index);
0058 }
0059 
0060 static void xa_erase_index(struct xarray *xa, unsigned long index)
0061 {
0062     XA_BUG_ON(xa, xa_erase(xa, index) != xa_mk_index(index));
0063     XA_BUG_ON(xa, xa_load(xa, index) != NULL);
0064 }
0065 
0066 /*
0067  * If anyone needs this, please move it to xarray.c.  We have no current
0068  * users outside the test suite because all current multislot users want
0069  * to use the advanced API.
0070  */
0071 static void *xa_store_order(struct xarray *xa, unsigned long index,
0072         unsigned order, void *entry, gfp_t gfp)
0073 {
0074     XA_STATE_ORDER(xas, xa, index, order);
0075     void *curr;
0076 
0077     do {
0078         xas_lock(&xas);
0079         curr = xas_store(&xas, entry);
0080         xas_unlock(&xas);
0081     } while (xas_nomem(&xas, gfp));
0082 
0083     return curr;
0084 }
0085 
0086 static noinline void check_xa_err(struct xarray *xa)
0087 {
0088     XA_BUG_ON(xa, xa_err(xa_store_index(xa, 0, GFP_NOWAIT)) != 0);
0089     XA_BUG_ON(xa, xa_err(xa_erase(xa, 0)) != 0);
0090 #ifndef __KERNEL__
0091     /* The kernel does not fail GFP_NOWAIT allocations */
0092     XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
0093     XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
0094 #endif
0095     XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_KERNEL)) != 0);
0096     XA_BUG_ON(xa, xa_err(xa_store(xa, 1, xa_mk_value(0), GFP_KERNEL)) != 0);
0097     XA_BUG_ON(xa, xa_err(xa_erase(xa, 1)) != 0);
0098 // kills the test-suite :-(
0099 //  XA_BUG_ON(xa, xa_err(xa_store(xa, 0, xa_mk_internal(0), 0)) != -EINVAL);
0100 }
0101 
0102 static noinline void check_xas_retry(struct xarray *xa)
0103 {
0104     XA_STATE(xas, xa, 0);
0105     void *entry;
0106 
0107     xa_store_index(xa, 0, GFP_KERNEL);
0108     xa_store_index(xa, 1, GFP_KERNEL);
0109 
0110     rcu_read_lock();
0111     XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_value(0));
0112     xa_erase_index(xa, 1);
0113     XA_BUG_ON(xa, !xa_is_retry(xas_reload(&xas)));
0114     XA_BUG_ON(xa, xas_retry(&xas, NULL));
0115     XA_BUG_ON(xa, xas_retry(&xas, xa_mk_value(0)));
0116     xas_reset(&xas);
0117     XA_BUG_ON(xa, xas.xa_node != XAS_RESTART);
0118     XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
0119     XA_BUG_ON(xa, xas.xa_node != NULL);
0120     rcu_read_unlock();
0121 
0122     XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
0123 
0124     rcu_read_lock();
0125     XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas)));
0126     xas.xa_node = XAS_RESTART;
0127     XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
0128     rcu_read_unlock();
0129 
0130     /* Make sure we can iterate through retry entries */
0131     xas_lock(&xas);
0132     xas_set(&xas, 0);
0133     xas_store(&xas, XA_RETRY_ENTRY);
0134     xas_set(&xas, 1);
0135     xas_store(&xas, XA_RETRY_ENTRY);
0136 
0137     xas_set(&xas, 0);
0138     xas_for_each(&xas, entry, ULONG_MAX) {
0139         xas_store(&xas, xa_mk_index(xas.xa_index));
0140     }
0141     xas_unlock(&xas);
0142 
0143     xa_erase_index(xa, 0);
0144     xa_erase_index(xa, 1);
0145 }
0146 
0147 static noinline void check_xa_load(struct xarray *xa)
0148 {
0149     unsigned long i, j;
0150 
0151     for (i = 0; i < 1024; i++) {
0152         for (j = 0; j < 1024; j++) {
0153             void *entry = xa_load(xa, j);
0154             if (j < i)
0155                 XA_BUG_ON(xa, xa_to_value(entry) != j);
0156             else
0157                 XA_BUG_ON(xa, entry);
0158         }
0159         XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
0160     }
0161 
0162     for (i = 0; i < 1024; i++) {
0163         for (j = 0; j < 1024; j++) {
0164             void *entry = xa_load(xa, j);
0165             if (j >= i)
0166                 XA_BUG_ON(xa, xa_to_value(entry) != j);
0167             else
0168                 XA_BUG_ON(xa, entry);
0169         }
0170         xa_erase_index(xa, i);
0171     }
0172     XA_BUG_ON(xa, !xa_empty(xa));
0173 }
0174 
0175 static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index)
0176 {
0177     unsigned int order;
0178     unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 8 : 1;
0179 
0180     /* NULL elements have no marks set */
0181     XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
0182     xa_set_mark(xa, index, XA_MARK_0);
0183     XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
0184 
0185     /* Storing a pointer will not make a mark appear */
0186     XA_BUG_ON(xa, xa_store_index(xa, index, GFP_KERNEL) != NULL);
0187     XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
0188     xa_set_mark(xa, index, XA_MARK_0);
0189     XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
0190 
0191     /* Setting one mark will not set another mark */
0192     XA_BUG_ON(xa, xa_get_mark(xa, index + 1, XA_MARK_0));
0193     XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_1));
0194 
0195     /* Storing NULL clears marks, and they can't be set again */
0196     xa_erase_index(xa, index);
0197     XA_BUG_ON(xa, !xa_empty(xa));
0198     XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
0199     xa_set_mark(xa, index, XA_MARK_0);
0200     XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
0201 
0202     /*
0203      * Storing a multi-index entry over entries with marks gives the
0204      * entire entry the union of the marks
0205      */
0206     BUG_ON((index % 4) != 0);
0207     for (order = 2; order < max_order; order++) {
0208         unsigned long base = round_down(index, 1UL << order);
0209         unsigned long next = base + (1UL << order);
0210         unsigned long i;
0211 
0212         XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL));
0213         xa_set_mark(xa, index + 1, XA_MARK_0);
0214         XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL));
0215         xa_set_mark(xa, index + 2, XA_MARK_2);
0216         XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL));
0217         xa_store_order(xa, index, order, xa_mk_index(index),
0218                 GFP_KERNEL);
0219         for (i = base; i < next; i++) {
0220             XA_STATE(xas, xa, i);
0221             unsigned int seen = 0;
0222             void *entry;
0223 
0224             XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
0225             XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_1));
0226             XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_2));
0227 
0228             /* We should see two elements in the array */
0229             rcu_read_lock();
0230             xas_for_each(&xas, entry, ULONG_MAX)
0231                 seen++;
0232             rcu_read_unlock();
0233             XA_BUG_ON(xa, seen != 2);
0234 
0235             /* One of which is marked */
0236             xas_set(&xas, 0);
0237             seen = 0;
0238             rcu_read_lock();
0239             xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
0240                 seen++;
0241             rcu_read_unlock();
0242             XA_BUG_ON(xa, seen != 1);
0243         }
0244         XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0));
0245         XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_1));
0246         XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_2));
0247         xa_erase_index(xa, index);
0248         xa_erase_index(xa, next);
0249         XA_BUG_ON(xa, !xa_empty(xa));
0250     }
0251     XA_BUG_ON(xa, !xa_empty(xa));
0252 }
0253 
0254 static noinline void check_xa_mark_2(struct xarray *xa)
0255 {
0256     XA_STATE(xas, xa, 0);
0257     unsigned long index;
0258     unsigned int count = 0;
0259     void *entry;
0260 
0261     xa_store_index(xa, 0, GFP_KERNEL);
0262     xa_set_mark(xa, 0, XA_MARK_0);
0263     xas_lock(&xas);
0264     xas_load(&xas);
0265     xas_init_marks(&xas);
0266     xas_unlock(&xas);
0267     XA_BUG_ON(xa, !xa_get_mark(xa, 0, XA_MARK_0) == 0);
0268 
0269     for (index = 3500; index < 4500; index++) {
0270         xa_store_index(xa, index, GFP_KERNEL);
0271         xa_set_mark(xa, index, XA_MARK_0);
0272     }
0273 
0274     xas_reset(&xas);
0275     rcu_read_lock();
0276     xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
0277         count++;
0278     rcu_read_unlock();
0279     XA_BUG_ON(xa, count != 1000);
0280 
0281     xas_lock(&xas);
0282     xas_for_each(&xas, entry, ULONG_MAX) {
0283         xas_init_marks(&xas);
0284         XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0));
0285         XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0));
0286     }
0287     xas_unlock(&xas);
0288 
0289     xa_destroy(xa);
0290 }
0291 
0292 static noinline void check_xa_mark_3(struct xarray *xa)
0293 {
0294 #ifdef CONFIG_XARRAY_MULTI
0295     XA_STATE(xas, xa, 0x41);
0296     void *entry;
0297     int count = 0;
0298 
0299     xa_store_order(xa, 0x40, 2, xa_mk_index(0x40), GFP_KERNEL);
0300     xa_set_mark(xa, 0x41, XA_MARK_0);
0301 
0302     rcu_read_lock();
0303     xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) {
0304         count++;
0305         XA_BUG_ON(xa, entry != xa_mk_index(0x40));
0306     }
0307     XA_BUG_ON(xa, count != 1);
0308     rcu_read_unlock();
0309     xa_destroy(xa);
0310 #endif
0311 }
0312 
0313 static noinline void check_xa_mark(struct xarray *xa)
0314 {
0315     unsigned long index;
0316 
0317     for (index = 0; index < 16384; index += 4)
0318         check_xa_mark_1(xa, index);
0319 
0320     check_xa_mark_2(xa);
0321     check_xa_mark_3(xa);
0322 }
0323 
0324 static noinline void check_xa_shrink(struct xarray *xa)
0325 {
0326     XA_STATE(xas, xa, 1);
0327     struct xa_node *node;
0328     unsigned int order;
0329     unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 15 : 1;
0330 
0331     XA_BUG_ON(xa, !xa_empty(xa));
0332     XA_BUG_ON(xa, xa_store_index(xa, 0, GFP_KERNEL) != NULL);
0333     XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
0334 
0335     /*
0336      * Check that erasing the entry at 1 shrinks the tree and properly
0337      * marks the node as being deleted.
0338      */
0339     xas_lock(&xas);
0340     XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1));
0341     node = xas.xa_node;
0342     XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != xa_mk_value(0));
0343     XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
0344     XA_BUG_ON(xa, xa_load(xa, 1) != NULL);
0345     XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS);
0346     XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != XA_RETRY_ENTRY);
0347     XA_BUG_ON(xa, xas_load(&xas) != NULL);
0348     xas_unlock(&xas);
0349     XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
0350     xa_erase_index(xa, 0);
0351     XA_BUG_ON(xa, !xa_empty(xa));
0352 
0353     for (order = 0; order < max_order; order++) {
0354         unsigned long max = (1UL << order) - 1;
0355         xa_store_order(xa, 0, order, xa_mk_value(0), GFP_KERNEL);
0356         XA_BUG_ON(xa, xa_load(xa, max) != xa_mk_value(0));
0357         XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
0358         rcu_read_lock();
0359         node = xa_head(xa);
0360         rcu_read_unlock();
0361         XA_BUG_ON(xa, xa_store_index(xa, ULONG_MAX, GFP_KERNEL) !=
0362                 NULL);
0363         rcu_read_lock();
0364         XA_BUG_ON(xa, xa_head(xa) == node);
0365         rcu_read_unlock();
0366         XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
0367         xa_erase_index(xa, ULONG_MAX);
0368         XA_BUG_ON(xa, xa->xa_head != node);
0369         xa_erase_index(xa, 0);
0370     }
0371 }
0372 
0373 static noinline void check_insert(struct xarray *xa)
0374 {
0375     unsigned long i;
0376 
0377     for (i = 0; i < 1024; i++) {
0378         xa_insert_index(xa, i);
0379         XA_BUG_ON(xa, xa_load(xa, i - 1) != NULL);
0380         XA_BUG_ON(xa, xa_load(xa, i + 1) != NULL);
0381         xa_erase_index(xa, i);
0382     }
0383 
0384     for (i = 10; i < BITS_PER_LONG; i++) {
0385         xa_insert_index(xa, 1UL << i);
0386         XA_BUG_ON(xa, xa_load(xa, (1UL << i) - 1) != NULL);
0387         XA_BUG_ON(xa, xa_load(xa, (1UL << i) + 1) != NULL);
0388         xa_erase_index(xa, 1UL << i);
0389 
0390         xa_insert_index(xa, (1UL << i) - 1);
0391         XA_BUG_ON(xa, xa_load(xa, (1UL << i) - 2) != NULL);
0392         XA_BUG_ON(xa, xa_load(xa, 1UL << i) != NULL);
0393         xa_erase_index(xa, (1UL << i) - 1);
0394     }
0395 
0396     xa_insert_index(xa, ~0UL);
0397     XA_BUG_ON(xa, xa_load(xa, 0UL) != NULL);
0398     XA_BUG_ON(xa, xa_load(xa, ~1UL) != NULL);
0399     xa_erase_index(xa, ~0UL);
0400 
0401     XA_BUG_ON(xa, !xa_empty(xa));
0402 }
0403 
0404 static noinline void check_cmpxchg(struct xarray *xa)
0405 {
0406     void *FIVE = xa_mk_value(5);
0407     void *SIX = xa_mk_value(6);
0408     void *LOTS = xa_mk_value(12345678);
0409 
0410     XA_BUG_ON(xa, !xa_empty(xa));
0411     XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL);
0412     XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EBUSY);
0413     XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS);
0414     XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS);
0415     XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE);
0416     XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL);
0417     XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL);
0418     XA_BUG_ON(xa, xa_insert(xa, 5, FIVE, GFP_KERNEL) != -EBUSY);
0419     XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != FIVE);
0420     XA_BUG_ON(xa, xa_insert(xa, 5, FIVE, GFP_KERNEL) == -EBUSY);
0421     xa_erase_index(xa, 12345678);
0422     xa_erase_index(xa, 5);
0423     XA_BUG_ON(xa, !xa_empty(xa));
0424 }
0425 
0426 static noinline void check_reserve(struct xarray *xa)
0427 {
0428     void *entry;
0429     unsigned long index;
0430     int count;
0431 
0432     /* An array with a reserved entry is not empty */
0433     XA_BUG_ON(xa, !xa_empty(xa));
0434     XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
0435     XA_BUG_ON(xa, xa_empty(xa));
0436     XA_BUG_ON(xa, xa_load(xa, 12345678));
0437     xa_release(xa, 12345678);
0438     XA_BUG_ON(xa, !xa_empty(xa));
0439 
0440     /* Releasing a used entry does nothing */
0441     XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
0442     XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL);
0443     xa_release(xa, 12345678);
0444     xa_erase_index(xa, 12345678);
0445     XA_BUG_ON(xa, !xa_empty(xa));
0446 
0447     /* cmpxchg sees a reserved entry as ZERO */
0448     XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
0449     XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, XA_ZERO_ENTRY,
0450                 xa_mk_value(12345678), GFP_NOWAIT) != NULL);
0451     xa_release(xa, 12345678);
0452     xa_erase_index(xa, 12345678);
0453     XA_BUG_ON(xa, !xa_empty(xa));
0454 
0455     /* xa_insert treats it as busy */
0456     XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
0457     XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) !=
0458             -EBUSY);
0459     XA_BUG_ON(xa, xa_empty(xa));
0460     XA_BUG_ON(xa, xa_erase(xa, 12345678) != NULL);
0461     XA_BUG_ON(xa, !xa_empty(xa));
0462 
0463     /* Can iterate through a reserved entry */
0464     xa_store_index(xa, 5, GFP_KERNEL);
0465     XA_BUG_ON(xa, xa_reserve(xa, 6, GFP_KERNEL) != 0);
0466     xa_store_index(xa, 7, GFP_KERNEL);
0467 
0468     count = 0;
0469     xa_for_each(xa, index, entry) {
0470         XA_BUG_ON(xa, index != 5 && index != 7);
0471         count++;
0472     }
0473     XA_BUG_ON(xa, count != 2);
0474 
0475     /* If we free a reserved entry, we should be able to allocate it */
0476     if (xa->xa_flags & XA_FLAGS_ALLOC) {
0477         u32 id;
0478 
0479         XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(8),
0480                     XA_LIMIT(5, 10), GFP_KERNEL) != 0);
0481         XA_BUG_ON(xa, id != 8);
0482 
0483         xa_release(xa, 6);
0484         XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(6),
0485                     XA_LIMIT(5, 10), GFP_KERNEL) != 0);
0486         XA_BUG_ON(xa, id != 6);
0487     }
0488 
0489     xa_destroy(xa);
0490 }
0491 
0492 static noinline void check_xas_erase(struct xarray *xa)
0493 {
0494     XA_STATE(xas, xa, 0);
0495     void *entry;
0496     unsigned long i, j;
0497 
0498     for (i = 0; i < 200; i++) {
0499         for (j = i; j < 2 * i + 17; j++) {
0500             xas_set(&xas, j);
0501             do {
0502                 xas_lock(&xas);
0503                 xas_store(&xas, xa_mk_index(j));
0504                 xas_unlock(&xas);
0505             } while (xas_nomem(&xas, GFP_KERNEL));
0506         }
0507 
0508         xas_set(&xas, ULONG_MAX);
0509         do {
0510             xas_lock(&xas);
0511             xas_store(&xas, xa_mk_value(0));
0512             xas_unlock(&xas);
0513         } while (xas_nomem(&xas, GFP_KERNEL));
0514 
0515         xas_lock(&xas);
0516         xas_store(&xas, NULL);
0517 
0518         xas_set(&xas, 0);
0519         j = i;
0520         xas_for_each(&xas, entry, ULONG_MAX) {
0521             XA_BUG_ON(xa, entry != xa_mk_index(j));
0522             xas_store(&xas, NULL);
0523             j++;
0524         }
0525         xas_unlock(&xas);
0526         XA_BUG_ON(xa, !xa_empty(xa));
0527     }
0528 }
0529 
0530 #ifdef CONFIG_XARRAY_MULTI
0531 static noinline void check_multi_store_1(struct xarray *xa, unsigned long index,
0532         unsigned int order)
0533 {
0534     XA_STATE(xas, xa, index);
0535     unsigned long min = index & ~((1UL << order) - 1);
0536     unsigned long max = min + (1UL << order);
0537 
0538     xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
0539     XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(index));
0540     XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(index));
0541     XA_BUG_ON(xa, xa_load(xa, max) != NULL);
0542     XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
0543 
0544     xas_lock(&xas);
0545     XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(min)) != xa_mk_index(index));
0546     xas_unlock(&xas);
0547     XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(min));
0548     XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(min));
0549     XA_BUG_ON(xa, xa_load(xa, max) != NULL);
0550     XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
0551 
0552     xa_erase_index(xa, min);
0553     XA_BUG_ON(xa, !xa_empty(xa));
0554 }
0555 
0556 static noinline void check_multi_store_2(struct xarray *xa, unsigned long index,
0557         unsigned int order)
0558 {
0559     XA_STATE(xas, xa, index);
0560     xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL);
0561 
0562     xas_lock(&xas);
0563     XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0));
0564     XA_BUG_ON(xa, xas.xa_index != index);
0565     XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
0566     xas_unlock(&xas);
0567     XA_BUG_ON(xa, !xa_empty(xa));
0568 }
0569 
0570 static noinline void check_multi_store_3(struct xarray *xa, unsigned long index,
0571         unsigned int order)
0572 {
0573     XA_STATE(xas, xa, 0);
0574     void *entry;
0575     int n = 0;
0576 
0577     xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
0578 
0579     xas_lock(&xas);
0580     xas_for_each(&xas, entry, ULONG_MAX) {
0581         XA_BUG_ON(xa, entry != xa_mk_index(index));
0582         n++;
0583     }
0584     XA_BUG_ON(xa, n != 1);
0585     xas_set(&xas, index + 1);
0586     xas_for_each(&xas, entry, ULONG_MAX) {
0587         XA_BUG_ON(xa, entry != xa_mk_index(index));
0588         n++;
0589     }
0590     XA_BUG_ON(xa, n != 2);
0591     xas_unlock(&xas);
0592 
0593     xa_destroy(xa);
0594 }
0595 #endif
0596 
0597 static noinline void check_multi_store(struct xarray *xa)
0598 {
0599 #ifdef CONFIG_XARRAY_MULTI
0600     unsigned long i, j, k;
0601     unsigned int max_order = (sizeof(long) == 4) ? 30 : 60;
0602 
0603     /* Loading from any position returns the same value */
0604     xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL);
0605     XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
0606     XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
0607     XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
0608     rcu_read_lock();
0609     XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2);
0610     XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
0611     rcu_read_unlock();
0612 
0613     /* Storing adjacent to the value does not alter the value */
0614     xa_store(xa, 3, xa, GFP_KERNEL);
0615     XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
0616     XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
0617     XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
0618     rcu_read_lock();
0619     XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3);
0620     XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
0621     rcu_read_unlock();
0622 
0623     /* Overwriting multiple indexes works */
0624     xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL);
0625     XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1));
0626     XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1));
0627     XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1));
0628     XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1));
0629     XA_BUG_ON(xa, xa_load(xa, 4) != NULL);
0630     rcu_read_lock();
0631     XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4);
0632     XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4);
0633     rcu_read_unlock();
0634 
0635     /* We can erase multiple values with a single store */
0636     xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL);
0637     XA_BUG_ON(xa, !xa_empty(xa));
0638 
0639     /* Even when the first slot is empty but the others aren't */
0640     xa_store_index(xa, 1, GFP_KERNEL);
0641     xa_store_index(xa, 2, GFP_KERNEL);
0642     xa_store_order(xa, 0, 2, NULL, GFP_KERNEL);
0643     XA_BUG_ON(xa, !xa_empty(xa));
0644 
0645     for (i = 0; i < max_order; i++) {
0646         for (j = 0; j < max_order; j++) {
0647             xa_store_order(xa, 0, i, xa_mk_index(i), GFP_KERNEL);
0648             xa_store_order(xa, 0, j, xa_mk_index(j), GFP_KERNEL);
0649 
0650             for (k = 0; k < max_order; k++) {
0651                 void *entry = xa_load(xa, (1UL << k) - 1);
0652                 if ((i < k) && (j < k))
0653                     XA_BUG_ON(xa, entry != NULL);
0654                 else
0655                     XA_BUG_ON(xa, entry != xa_mk_index(j));
0656             }
0657 
0658             xa_erase(xa, 0);
0659             XA_BUG_ON(xa, !xa_empty(xa));
0660         }
0661     }
0662 
0663     for (i = 0; i < 20; i++) {
0664         check_multi_store_1(xa, 200, i);
0665         check_multi_store_1(xa, 0, i);
0666         check_multi_store_1(xa, (1UL << i) + 1, i);
0667     }
0668     check_multi_store_2(xa, 4095, 9);
0669 
0670     for (i = 1; i < 20; i++) {
0671         check_multi_store_3(xa, 0, i);
0672         check_multi_store_3(xa, 1UL << i, i);
0673     }
0674 #endif
0675 }
0676 
0677 static noinline void check_xa_alloc_1(struct xarray *xa, unsigned int base)
0678 {
0679     int i;
0680     u32 id;
0681 
0682     XA_BUG_ON(xa, !xa_empty(xa));
0683     /* An empty array should assign %base to the first alloc */
0684     xa_alloc_index(xa, base, GFP_KERNEL);
0685 
0686     /* Erasing it should make the array empty again */
0687     xa_erase_index(xa, base);
0688     XA_BUG_ON(xa, !xa_empty(xa));
0689 
0690     /* And it should assign %base again */
0691     xa_alloc_index(xa, base, GFP_KERNEL);
0692 
0693     /* Allocating and then erasing a lot should not lose base */
0694     for (i = base + 1; i < 2 * XA_CHUNK_SIZE; i++)
0695         xa_alloc_index(xa, i, GFP_KERNEL);
0696     for (i = base; i < 2 * XA_CHUNK_SIZE; i++)
0697         xa_erase_index(xa, i);
0698     xa_alloc_index(xa, base, GFP_KERNEL);
0699 
0700     /* Destroying the array should do the same as erasing */
0701     xa_destroy(xa);
0702 
0703     /* And it should assign %base again */
0704     xa_alloc_index(xa, base, GFP_KERNEL);
0705 
0706     /* The next assigned ID should be base+1 */
0707     xa_alloc_index(xa, base + 1, GFP_KERNEL);
0708     xa_erase_index(xa, base + 1);
0709 
0710     /* Storing a value should mark it used */
0711     xa_store_index(xa, base + 1, GFP_KERNEL);
0712     xa_alloc_index(xa, base + 2, GFP_KERNEL);
0713 
0714     /* If we then erase base, it should be free */
0715     xa_erase_index(xa, base);
0716     xa_alloc_index(xa, base, GFP_KERNEL);
0717 
0718     xa_erase_index(xa, base + 1);
0719     xa_erase_index(xa, base + 2);
0720 
0721     for (i = 1; i < 5000; i++) {
0722         xa_alloc_index(xa, base + i, GFP_KERNEL);
0723     }
0724 
0725     xa_destroy(xa);
0726 
0727     /* Check that we fail properly at the limit of allocation */
0728     XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX - 1),
0729                 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
0730                 GFP_KERNEL) != 0);
0731     XA_BUG_ON(xa, id != 0xfffffffeU);
0732     XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX),
0733                 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
0734                 GFP_KERNEL) != 0);
0735     XA_BUG_ON(xa, id != 0xffffffffU);
0736     id = 3;
0737     XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(0),
0738                 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
0739                 GFP_KERNEL) != -EBUSY);
0740     XA_BUG_ON(xa, id != 3);
0741     xa_destroy(xa);
0742 
0743     XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
0744                 GFP_KERNEL) != -EBUSY);
0745     XA_BUG_ON(xa, xa_store_index(xa, 3, GFP_KERNEL) != 0);
0746     XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
0747                 GFP_KERNEL) != -EBUSY);
0748     xa_erase_index(xa, 3);
0749     XA_BUG_ON(xa, !xa_empty(xa));
0750 }
0751 
0752 static noinline void check_xa_alloc_2(struct xarray *xa, unsigned int base)
0753 {
0754     unsigned int i, id;
0755     unsigned long index;
0756     void *entry;
0757 
0758     /* Allocate and free a NULL and check xa_empty() behaves */
0759     XA_BUG_ON(xa, !xa_empty(xa));
0760     XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
0761     XA_BUG_ON(xa, id != base);
0762     XA_BUG_ON(xa, xa_empty(xa));
0763     XA_BUG_ON(xa, xa_erase(xa, id) != NULL);
0764     XA_BUG_ON(xa, !xa_empty(xa));
0765 
0766     /* Ditto, but check destroy instead of erase */
0767     XA_BUG_ON(xa, !xa_empty(xa));
0768     XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
0769     XA_BUG_ON(xa, id != base);
0770     XA_BUG_ON(xa, xa_empty(xa));
0771     xa_destroy(xa);
0772     XA_BUG_ON(xa, !xa_empty(xa));
0773 
0774     for (i = base; i < base + 10; i++) {
0775         XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b,
0776                     GFP_KERNEL) != 0);
0777         XA_BUG_ON(xa, id != i);
0778     }
0779 
0780     XA_BUG_ON(xa, xa_store(xa, 3, xa_mk_index(3), GFP_KERNEL) != NULL);
0781     XA_BUG_ON(xa, xa_store(xa, 4, xa_mk_index(4), GFP_KERNEL) != NULL);
0782     XA_BUG_ON(xa, xa_store(xa, 4, NULL, GFP_KERNEL) != xa_mk_index(4));
0783     XA_BUG_ON(xa, xa_erase(xa, 5) != NULL);
0784     XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
0785     XA_BUG_ON(xa, id != 5);
0786 
0787     xa_for_each(xa, index, entry) {
0788         xa_erase_index(xa, index);
0789     }
0790 
0791     for (i = base; i < base + 9; i++) {
0792         XA_BUG_ON(xa, xa_erase(xa, i) != NULL);
0793         XA_BUG_ON(xa, xa_empty(xa));
0794     }
0795     XA_BUG_ON(xa, xa_erase(xa, 8) != NULL);
0796     XA_BUG_ON(xa, xa_empty(xa));
0797     XA_BUG_ON(xa, xa_erase(xa, base + 9) != NULL);
0798     XA_BUG_ON(xa, !xa_empty(xa));
0799 
0800     xa_destroy(xa);
0801 }
0802 
0803 static noinline void check_xa_alloc_3(struct xarray *xa, unsigned int base)
0804 {
0805     struct xa_limit limit = XA_LIMIT(1, 0x3fff);
0806     u32 next = 0;
0807     unsigned int i, id;
0808     unsigned long index;
0809     void *entry;
0810 
0811     XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(1), limit,
0812                 &next, GFP_KERNEL) != 0);
0813     XA_BUG_ON(xa, id != 1);
0814 
0815     next = 0x3ffd;
0816     XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(0x3ffd), limit,
0817                 &next, GFP_KERNEL) != 0);
0818     XA_BUG_ON(xa, id != 0x3ffd);
0819     xa_erase_index(xa, 0x3ffd);
0820     xa_erase_index(xa, 1);
0821     XA_BUG_ON(xa, !xa_empty(xa));
0822 
0823     for (i = 0x3ffe; i < 0x4003; i++) {
0824         if (i < 0x4000)
0825             entry = xa_mk_index(i);
0826         else
0827             entry = xa_mk_index(i - 0x3fff);
0828         XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, entry, limit,
0829                     &next, GFP_KERNEL) != (id == 1));
0830         XA_BUG_ON(xa, xa_mk_index(id) != entry);
0831     }
0832 
0833     /* Check wrap-around is handled correctly */
0834     if (base != 0)
0835         xa_erase_index(xa, base);
0836     xa_erase_index(xa, base + 1);
0837     next = UINT_MAX;
0838     XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(UINT_MAX),
0839                 xa_limit_32b, &next, GFP_KERNEL) != 0);
0840     XA_BUG_ON(xa, id != UINT_MAX);
0841     XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base),
0842                 xa_limit_32b, &next, GFP_KERNEL) != 1);
0843     XA_BUG_ON(xa, id != base);
0844     XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base + 1),
0845                 xa_limit_32b, &next, GFP_KERNEL) != 0);
0846     XA_BUG_ON(xa, id != base + 1);
0847 
0848     xa_for_each(xa, index, entry)
0849         xa_erase_index(xa, index);
0850 
0851     XA_BUG_ON(xa, !xa_empty(xa));
0852 }
0853 
0854 static DEFINE_XARRAY_ALLOC(xa0);
0855 static DEFINE_XARRAY_ALLOC1(xa1);
0856 
0857 static noinline void check_xa_alloc(void)
0858 {
0859     check_xa_alloc_1(&xa0, 0);
0860     check_xa_alloc_1(&xa1, 1);
0861     check_xa_alloc_2(&xa0, 0);
0862     check_xa_alloc_2(&xa1, 1);
0863     check_xa_alloc_3(&xa0, 0);
0864     check_xa_alloc_3(&xa1, 1);
0865 }
0866 
0867 static noinline void __check_store_iter(struct xarray *xa, unsigned long start,
0868             unsigned int order, unsigned int present)
0869 {
0870     XA_STATE_ORDER(xas, xa, start, order);
0871     void *entry;
0872     unsigned int count = 0;
0873 
0874 retry:
0875     xas_lock(&xas);
0876     xas_for_each_conflict(&xas, entry) {
0877         XA_BUG_ON(xa, !xa_is_value(entry));
0878         XA_BUG_ON(xa, entry < xa_mk_index(start));
0879         XA_BUG_ON(xa, entry > xa_mk_index(start + (1UL << order) - 1));
0880         count++;
0881     }
0882     xas_store(&xas, xa_mk_index(start));
0883     xas_unlock(&xas);
0884     if (xas_nomem(&xas, GFP_KERNEL)) {
0885         count = 0;
0886         goto retry;
0887     }
0888     XA_BUG_ON(xa, xas_error(&xas));
0889     XA_BUG_ON(xa, count != present);
0890     XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_index(start));
0891     XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=
0892             xa_mk_index(start));
0893     xa_erase_index(xa, start);
0894 }
0895 
0896 static noinline void check_store_iter(struct xarray *xa)
0897 {
0898     unsigned int i, j;
0899     unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
0900 
0901     for (i = 0; i < max_order; i++) {
0902         unsigned int min = 1 << i;
0903         unsigned int max = (2 << i) - 1;
0904         __check_store_iter(xa, 0, i, 0);
0905         XA_BUG_ON(xa, !xa_empty(xa));
0906         __check_store_iter(xa, min, i, 0);
0907         XA_BUG_ON(xa, !xa_empty(xa));
0908 
0909         xa_store_index(xa, min, GFP_KERNEL);
0910         __check_store_iter(xa, min, i, 1);
0911         XA_BUG_ON(xa, !xa_empty(xa));
0912         xa_store_index(xa, max, GFP_KERNEL);
0913         __check_store_iter(xa, min, i, 1);
0914         XA_BUG_ON(xa, !xa_empty(xa));
0915 
0916         for (j = 0; j < min; j++)
0917             xa_store_index(xa, j, GFP_KERNEL);
0918         __check_store_iter(xa, 0, i, min);
0919         XA_BUG_ON(xa, !xa_empty(xa));
0920         for (j = 0; j < min; j++)
0921             xa_store_index(xa, min + j, GFP_KERNEL);
0922         __check_store_iter(xa, min, i, min);
0923         XA_BUG_ON(xa, !xa_empty(xa));
0924     }
0925 #ifdef CONFIG_XARRAY_MULTI
0926     xa_store_index(xa, 63, GFP_KERNEL);
0927     xa_store_index(xa, 65, GFP_KERNEL);
0928     __check_store_iter(xa, 64, 2, 1);
0929     xa_erase_index(xa, 63);
0930 #endif
0931     XA_BUG_ON(xa, !xa_empty(xa));
0932 }
0933 
0934 static noinline void check_multi_find_1(struct xarray *xa, unsigned order)
0935 {
0936 #ifdef CONFIG_XARRAY_MULTI
0937     unsigned long multi = 3 << order;
0938     unsigned long next = 4 << order;
0939     unsigned long index;
0940 
0941     xa_store_order(xa, multi, order, xa_mk_value(multi), GFP_KERNEL);
0942     XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL) != NULL);
0943     XA_BUG_ON(xa, xa_store_index(xa, next + 1, GFP_KERNEL) != NULL);
0944 
0945     index = 0;
0946     XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
0947             xa_mk_value(multi));
0948     XA_BUG_ON(xa, index != multi);
0949     index = multi + 1;
0950     XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
0951             xa_mk_value(multi));
0952     XA_BUG_ON(xa, (index < multi) || (index >= next));
0953     XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) !=
0954             xa_mk_value(next));
0955     XA_BUG_ON(xa, index != next);
0956     XA_BUG_ON(xa, xa_find_after(xa, &index, next, XA_PRESENT) != NULL);
0957     XA_BUG_ON(xa, index != next);
0958 
0959     xa_erase_index(xa, multi);
0960     xa_erase_index(xa, next);
0961     xa_erase_index(xa, next + 1);
0962     XA_BUG_ON(xa, !xa_empty(xa));
0963 #endif
0964 }
0965 
0966 static noinline void check_multi_find_2(struct xarray *xa)
0967 {
0968     unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1;
0969     unsigned int i, j;
0970     void *entry;
0971 
0972     for (i = 0; i < max_order; i++) {
0973         unsigned long index = 1UL << i;
0974         for (j = 0; j < index; j++) {
0975             XA_STATE(xas, xa, j + index);
0976             xa_store_index(xa, index - 1, GFP_KERNEL);
0977             xa_store_order(xa, index, i, xa_mk_index(index),
0978                     GFP_KERNEL);
0979             rcu_read_lock();
0980             xas_for_each(&xas, entry, ULONG_MAX) {
0981                 xa_erase_index(xa, index);
0982             }
0983             rcu_read_unlock();
0984             xa_erase_index(xa, index - 1);
0985             XA_BUG_ON(xa, !xa_empty(xa));
0986         }
0987     }
0988 }
0989 
0990 static noinline void check_multi_find_3(struct xarray *xa)
0991 {
0992     unsigned int order;
0993 
0994     for (order = 5; order < order_limit; order++) {
0995         unsigned long index = 1UL << (order - 5);
0996 
0997         XA_BUG_ON(xa, !xa_empty(xa));
0998         xa_store_order(xa, 0, order - 4, xa_mk_index(0), GFP_KERNEL);
0999         XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT));
1000         xa_erase_index(xa, 0);
1001     }
1002 }
1003 
1004 static noinline void check_find_1(struct xarray *xa)
1005 {
1006     unsigned long i, j, k;
1007 
1008     XA_BUG_ON(xa, !xa_empty(xa));
1009 
1010     /*
1011      * Check xa_find with all pairs between 0 and 99 inclusive,
1012      * starting at every index between 0 and 99
1013      */
1014     for (i = 0; i < 100; i++) {
1015         XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
1016         xa_set_mark(xa, i, XA_MARK_0);
1017         for (j = 0; j < i; j++) {
1018             XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) !=
1019                     NULL);
1020             xa_set_mark(xa, j, XA_MARK_0);
1021             for (k = 0; k < 100; k++) {
1022                 unsigned long index = k;
1023                 void *entry = xa_find(xa, &index, ULONG_MAX,
1024                                 XA_PRESENT);
1025                 if (k <= j)
1026                     XA_BUG_ON(xa, index != j);
1027                 else if (k <= i)
1028                     XA_BUG_ON(xa, index != i);
1029                 else
1030                     XA_BUG_ON(xa, entry != NULL);
1031 
1032                 index = k;
1033                 entry = xa_find(xa, &index, ULONG_MAX,
1034                                 XA_MARK_0);
1035                 if (k <= j)
1036                     XA_BUG_ON(xa, index != j);
1037                 else if (k <= i)
1038                     XA_BUG_ON(xa, index != i);
1039                 else
1040                     XA_BUG_ON(xa, entry != NULL);
1041             }
1042             xa_erase_index(xa, j);
1043             XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0));
1044             XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
1045         }
1046         xa_erase_index(xa, i);
1047         XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0));
1048     }
1049     XA_BUG_ON(xa, !xa_empty(xa));
1050 }
1051 
1052 static noinline void check_find_2(struct xarray *xa)
1053 {
1054     void *entry;
1055     unsigned long i, j, index;
1056 
1057     xa_for_each(xa, index, entry) {
1058         XA_BUG_ON(xa, true);
1059     }
1060 
1061     for (i = 0; i < 1024; i++) {
1062         xa_store_index(xa, index, GFP_KERNEL);
1063         j = 0;
1064         xa_for_each(xa, index, entry) {
1065             XA_BUG_ON(xa, xa_mk_index(index) != entry);
1066             XA_BUG_ON(xa, index != j++);
1067         }
1068     }
1069 
1070     xa_destroy(xa);
1071 }
1072 
1073 static noinline void check_find_3(struct xarray *xa)
1074 {
1075     XA_STATE(xas, xa, 0);
1076     unsigned long i, j, k;
1077     void *entry;
1078 
1079     for (i = 0; i < 100; i++) {
1080         for (j = 0; j < 100; j++) {
1081             rcu_read_lock();
1082             for (k = 0; k < 100; k++) {
1083                 xas_set(&xas, j);
1084                 xas_for_each_marked(&xas, entry, k, XA_MARK_0)
1085                     ;
1086                 if (j > k)
1087                     XA_BUG_ON(xa,
1088                         xas.xa_node != XAS_RESTART);
1089             }
1090             rcu_read_unlock();
1091         }
1092         xa_store_index(xa, i, GFP_KERNEL);
1093         xa_set_mark(xa, i, XA_MARK_0);
1094     }
1095     xa_destroy(xa);
1096 }
1097 
1098 static noinline void check_find_4(struct xarray *xa)
1099 {
1100     unsigned long index = 0;
1101     void *entry;
1102 
1103     xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1104 
1105     entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);
1106     XA_BUG_ON(xa, entry != xa_mk_index(ULONG_MAX));
1107 
1108     entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);
1109     XA_BUG_ON(xa, entry);
1110 
1111     xa_erase_index(xa, ULONG_MAX);
1112 }
1113 
1114 static noinline void check_find(struct xarray *xa)
1115 {
1116     unsigned i;
1117 
1118     check_find_1(xa);
1119     check_find_2(xa);
1120     check_find_3(xa);
1121     check_find_4(xa);
1122 
1123     for (i = 2; i < 10; i++)
1124         check_multi_find_1(xa, i);
1125     check_multi_find_2(xa);
1126     check_multi_find_3(xa);
1127 }
1128 
1129 /* See find_swap_entry() in mm/shmem.c */
1130 static noinline unsigned long xa_find_entry(struct xarray *xa, void *item)
1131 {
1132     XA_STATE(xas, xa, 0);
1133     unsigned int checked = 0;
1134     void *entry;
1135 
1136     rcu_read_lock();
1137     xas_for_each(&xas, entry, ULONG_MAX) {
1138         if (xas_retry(&xas, entry))
1139             continue;
1140         if (entry == item)
1141             break;
1142         checked++;
1143         if ((checked % 4) != 0)
1144             continue;
1145         xas_pause(&xas);
1146     }
1147     rcu_read_unlock();
1148 
1149     return entry ? xas.xa_index : -1;
1150 }
1151 
1152 static noinline void check_find_entry(struct xarray *xa)
1153 {
1154 #ifdef CONFIG_XARRAY_MULTI
1155     unsigned int order;
1156     unsigned long offset, index;
1157 
1158     for (order = 0; order < 20; order++) {
1159         for (offset = 0; offset < (1UL << (order + 3));
1160              offset += (1UL << order)) {
1161             for (index = 0; index < (1UL << (order + 5));
1162                  index += (1UL << order)) {
1163                 xa_store_order(xa, index, order,
1164                         xa_mk_index(index), GFP_KERNEL);
1165                 XA_BUG_ON(xa, xa_load(xa, index) !=
1166                         xa_mk_index(index));
1167                 XA_BUG_ON(xa, xa_find_entry(xa,
1168                         xa_mk_index(index)) != index);
1169             }
1170             XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1171             xa_destroy(xa);
1172         }
1173     }
1174 #endif
1175 
1176     XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1177     xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1178     XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1179     XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_index(ULONG_MAX)) != -1);
1180     xa_erase_index(xa, ULONG_MAX);
1181     XA_BUG_ON(xa, !xa_empty(xa));
1182 }
1183 
1184 static noinline void check_pause(struct xarray *xa)
1185 {
1186     XA_STATE(xas, xa, 0);
1187     void *entry;
1188     unsigned int order;
1189     unsigned long index = 1;
1190     unsigned int count = 0;
1191 
1192     for (order = 0; order < order_limit; order++) {
1193         XA_BUG_ON(xa, xa_store_order(xa, index, order,
1194                     xa_mk_index(index), GFP_KERNEL));
1195         index += 1UL << order;
1196     }
1197 
1198     rcu_read_lock();
1199     xas_for_each(&xas, entry, ULONG_MAX) {
1200         XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));
1201         count++;
1202     }
1203     rcu_read_unlock();
1204     XA_BUG_ON(xa, count != order_limit);
1205 
1206     count = 0;
1207     xas_set(&xas, 0);
1208     rcu_read_lock();
1209     xas_for_each(&xas, entry, ULONG_MAX) {
1210         XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));
1211         count++;
1212         xas_pause(&xas);
1213     }
1214     rcu_read_unlock();
1215     XA_BUG_ON(xa, count != order_limit);
1216 
1217     xa_destroy(xa);
1218 }
1219 
1220 static noinline void check_move_tiny(struct xarray *xa)
1221 {
1222     XA_STATE(xas, xa, 0);
1223 
1224     XA_BUG_ON(xa, !xa_empty(xa));
1225     rcu_read_lock();
1226     XA_BUG_ON(xa, xas_next(&xas) != NULL);
1227     XA_BUG_ON(xa, xas_next(&xas) != NULL);
1228     rcu_read_unlock();
1229     xa_store_index(xa, 0, GFP_KERNEL);
1230     rcu_read_lock();
1231     xas_set(&xas, 0);
1232     XA_BUG_ON(xa, xas_next(&xas) != xa_mk_index(0));
1233     XA_BUG_ON(xa, xas_next(&xas) != NULL);
1234     xas_set(&xas, 0);
1235     XA_BUG_ON(xa, xas_prev(&xas) != xa_mk_index(0));
1236     XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1237     rcu_read_unlock();
1238     xa_erase_index(xa, 0);
1239     XA_BUG_ON(xa, !xa_empty(xa));
1240 }
1241 
1242 static noinline void check_move_max(struct xarray *xa)
1243 {
1244     XA_STATE(xas, xa, 0);
1245 
1246     xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1247     rcu_read_lock();
1248     XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));
1249     XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);
1250     rcu_read_unlock();
1251 
1252     xas_set(&xas, 0);
1253     rcu_read_lock();
1254     XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));
1255     xas_pause(&xas);
1256     XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);
1257     rcu_read_unlock();
1258 
1259     xa_erase_index(xa, ULONG_MAX);
1260     XA_BUG_ON(xa, !xa_empty(xa));
1261 }
1262 
1263 static noinline void check_move_small(struct xarray *xa, unsigned long idx)
1264 {
1265     XA_STATE(xas, xa, 0);
1266     unsigned long i;
1267 
1268     xa_store_index(xa, 0, GFP_KERNEL);
1269     xa_store_index(xa, idx, GFP_KERNEL);
1270 
1271     rcu_read_lock();
1272     for (i = 0; i < idx * 4; i++) {
1273         void *entry = xas_next(&xas);
1274         if (i <= idx)
1275             XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
1276         XA_BUG_ON(xa, xas.xa_index != i);
1277         if (i == 0 || i == idx)
1278             XA_BUG_ON(xa, entry != xa_mk_index(i));
1279         else
1280             XA_BUG_ON(xa, entry != NULL);
1281     }
1282     xas_next(&xas);
1283     XA_BUG_ON(xa, xas.xa_index != i);
1284 
1285     do {
1286         void *entry = xas_prev(&xas);
1287         i--;
1288         if (i <= idx)
1289             XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
1290         XA_BUG_ON(xa, xas.xa_index != i);
1291         if (i == 0 || i == idx)
1292             XA_BUG_ON(xa, entry != xa_mk_index(i));
1293         else
1294             XA_BUG_ON(xa, entry != NULL);
1295     } while (i > 0);
1296 
1297     xas_set(&xas, ULONG_MAX);
1298     XA_BUG_ON(xa, xas_next(&xas) != NULL);
1299     XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1300     XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));
1301     XA_BUG_ON(xa, xas.xa_index != 0);
1302     XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1303     XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1304     rcu_read_unlock();
1305 
1306     xa_erase_index(xa, 0);
1307     xa_erase_index(xa, idx);
1308     XA_BUG_ON(xa, !xa_empty(xa));
1309 }
1310 
1311 static noinline void check_move(struct xarray *xa)
1312 {
1313     XA_STATE(xas, xa, (1 << 16) - 1);
1314     unsigned long i;
1315 
1316     for (i = 0; i < (1 << 16); i++)
1317         XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
1318 
1319     rcu_read_lock();
1320     do {
1321         void *entry = xas_prev(&xas);
1322         i--;
1323         XA_BUG_ON(xa, entry != xa_mk_index(i));
1324         XA_BUG_ON(xa, i != xas.xa_index);
1325     } while (i != 0);
1326 
1327     XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1328     XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1329 
1330     do {
1331         void *entry = xas_next(&xas);
1332         XA_BUG_ON(xa, entry != xa_mk_index(i));
1333         XA_BUG_ON(xa, i != xas.xa_index);
1334         i++;
1335     } while (i < (1 << 16));
1336     rcu_read_unlock();
1337 
1338     for (i = (1 << 8); i < (1 << 15); i++)
1339         xa_erase_index(xa, i);
1340 
1341     i = xas.xa_index;
1342 
1343     rcu_read_lock();
1344     do {
1345         void *entry = xas_prev(&xas);
1346         i--;
1347         if ((i < (1 << 8)) || (i >= (1 << 15)))
1348             XA_BUG_ON(xa, entry != xa_mk_index(i));
1349         else
1350             XA_BUG_ON(xa, entry != NULL);
1351         XA_BUG_ON(xa, i != xas.xa_index);
1352     } while (i != 0);
1353 
1354     XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1355     XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1356 
1357     do {
1358         void *entry = xas_next(&xas);
1359         if ((i < (1 << 8)) || (i >= (1 << 15)))
1360             XA_BUG_ON(xa, entry != xa_mk_index(i));
1361         else
1362             XA_BUG_ON(xa, entry != NULL);
1363         XA_BUG_ON(xa, i != xas.xa_index);
1364         i++;
1365     } while (i < (1 << 16));
1366     rcu_read_unlock();
1367 
1368     xa_destroy(xa);
1369 
1370     check_move_tiny(xa);
1371     check_move_max(xa);
1372 
1373     for (i = 0; i < 16; i++)
1374         check_move_small(xa, 1UL << i);
1375 
1376     for (i = 2; i < 16; i++)
1377         check_move_small(xa, (1UL << i) - 1);
1378 }
1379 
1380 static noinline void xa_store_many_order(struct xarray *xa,
1381         unsigned long index, unsigned order)
1382 {
1383     XA_STATE_ORDER(xas, xa, index, order);
1384     unsigned int i = 0;
1385 
1386     do {
1387         xas_lock(&xas);
1388         XA_BUG_ON(xa, xas_find_conflict(&xas));
1389         xas_create_range(&xas);
1390         if (xas_error(&xas))
1391             goto unlock;
1392         for (i = 0; i < (1U << order); i++) {
1393             XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i)));
1394             xas_next(&xas);
1395         }
1396 unlock:
1397         xas_unlock(&xas);
1398     } while (xas_nomem(&xas, GFP_KERNEL));
1399 
1400     XA_BUG_ON(xa, xas_error(&xas));
1401 }
1402 
1403 static noinline void check_create_range_1(struct xarray *xa,
1404         unsigned long index, unsigned order)
1405 {
1406     unsigned long i;
1407 
1408     xa_store_many_order(xa, index, order);
1409     for (i = index; i < index + (1UL << order); i++)
1410         xa_erase_index(xa, i);
1411     XA_BUG_ON(xa, !xa_empty(xa));
1412 }
1413 
1414 static noinline void check_create_range_2(struct xarray *xa, unsigned order)
1415 {
1416     unsigned long i;
1417     unsigned long nr = 1UL << order;
1418 
1419     for (i = 0; i < nr * nr; i += nr)
1420         xa_store_many_order(xa, i, order);
1421     for (i = 0; i < nr * nr; i++)
1422         xa_erase_index(xa, i);
1423     XA_BUG_ON(xa, !xa_empty(xa));
1424 }
1425 
1426 static noinline void check_create_range_3(void)
1427 {
1428     XA_STATE(xas, NULL, 0);
1429     xas_set_err(&xas, -EEXIST);
1430     xas_create_range(&xas);
1431     XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);
1432 }
1433 
1434 static noinline void check_create_range_4(struct xarray *xa,
1435         unsigned long index, unsigned order)
1436 {
1437     XA_STATE_ORDER(xas, xa, index, order);
1438     unsigned long base = xas.xa_index;
1439     unsigned long i = 0;
1440 
1441     xa_store_index(xa, index, GFP_KERNEL);
1442     do {
1443         xas_lock(&xas);
1444         xas_create_range(&xas);
1445         if (xas_error(&xas))
1446             goto unlock;
1447         for (i = 0; i < (1UL << order); i++) {
1448             void *old = xas_store(&xas, xa_mk_index(base + i));
1449             if (xas.xa_index == index)
1450                 XA_BUG_ON(xa, old != xa_mk_index(base + i));
1451             else
1452                 XA_BUG_ON(xa, old != NULL);
1453             xas_next(&xas);
1454         }
1455 unlock:
1456         xas_unlock(&xas);
1457     } while (xas_nomem(&xas, GFP_KERNEL));
1458 
1459     XA_BUG_ON(xa, xas_error(&xas));
1460 
1461     for (i = base; i < base + (1UL << order); i++)
1462         xa_erase_index(xa, i);
1463     XA_BUG_ON(xa, !xa_empty(xa));
1464 }
1465 
1466 static noinline void check_create_range_5(struct xarray *xa,
1467         unsigned long index, unsigned int order)
1468 {
1469     XA_STATE_ORDER(xas, xa, index, order);
1470     unsigned int i;
1471 
1472     xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
1473 
1474     for (i = 0; i < order + 10; i++) {
1475         do {
1476             xas_lock(&xas);
1477             xas_create_range(&xas);
1478             xas_unlock(&xas);
1479         } while (xas_nomem(&xas, GFP_KERNEL));
1480     }
1481 
1482     xa_destroy(xa);
1483 }
1484 
1485 static noinline void check_create_range(struct xarray *xa)
1486 {
1487     unsigned int order;
1488     unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1;
1489 
1490     for (order = 0; order < max_order; order++) {
1491         check_create_range_1(xa, 0, order);
1492         check_create_range_1(xa, 1U << order, order);
1493         check_create_range_1(xa, 2U << order, order);
1494         check_create_range_1(xa, 3U << order, order);
1495         check_create_range_1(xa, 1U << 24, order);
1496         if (order < 10)
1497             check_create_range_2(xa, order);
1498 
1499         check_create_range_4(xa, 0, order);
1500         check_create_range_4(xa, 1U << order, order);
1501         check_create_range_4(xa, 2U << order, order);
1502         check_create_range_4(xa, 3U << order, order);
1503         check_create_range_4(xa, 1U << 24, order);
1504 
1505         check_create_range_4(xa, 1, order);
1506         check_create_range_4(xa, (1U << order) + 1, order);
1507         check_create_range_4(xa, (2U << order) + 1, order);
1508         check_create_range_4(xa, (2U << order) - 1, order);
1509         check_create_range_4(xa, (3U << order) + 1, order);
1510         check_create_range_4(xa, (3U << order) - 1, order);
1511         check_create_range_4(xa, (1U << 24) + 1, order);
1512 
1513         check_create_range_5(xa, 0, order);
1514         check_create_range_5(xa, (1U << order), order);
1515     }
1516 
1517     check_create_range_3();
1518 }
1519 
1520 static noinline void __check_store_range(struct xarray *xa, unsigned long first,
1521         unsigned long last)
1522 {
1523 #ifdef CONFIG_XARRAY_MULTI
1524     xa_store_range(xa, first, last, xa_mk_index(first), GFP_KERNEL);
1525 
1526     XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_index(first));
1527     XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_index(first));
1528     XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL);
1529     XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL);
1530 
1531     xa_store_range(xa, first, last, NULL, GFP_KERNEL);
1532 #endif
1533 
1534     XA_BUG_ON(xa, !xa_empty(xa));
1535 }
1536 
1537 static noinline void check_store_range(struct xarray *xa)
1538 {
1539     unsigned long i, j;
1540 
1541     for (i = 0; i < 128; i++) {
1542         for (j = i; j < 128; j++) {
1543             __check_store_range(xa, i, j);
1544             __check_store_range(xa, 128 + i, 128 + j);
1545             __check_store_range(xa, 4095 + i, 4095 + j);
1546             __check_store_range(xa, 4096 + i, 4096 + j);
1547             __check_store_range(xa, 123456 + i, 123456 + j);
1548             __check_store_range(xa, (1 << 24) + i, (1 << 24) + j);
1549         }
1550     }
1551 }
1552 
1553 #ifdef CONFIG_XARRAY_MULTI
1554 static void check_split_1(struct xarray *xa, unsigned long index,
1555                 unsigned int order, unsigned int new_order)
1556 {
1557     XA_STATE_ORDER(xas, xa, index, new_order);
1558     unsigned int i;
1559 
1560     xa_store_order(xa, index, order, xa, GFP_KERNEL);
1561 
1562     xas_split_alloc(&xas, xa, order, GFP_KERNEL);
1563     xas_lock(&xas);
1564     xas_split(&xas, xa, order);
1565     for (i = 0; i < (1 << order); i += (1 << new_order))
1566         __xa_store(xa, index + i, xa_mk_index(index + i), 0);
1567     xas_unlock(&xas);
1568 
1569     for (i = 0; i < (1 << order); i++) {
1570         unsigned int val = index + (i & ~((1 << new_order) - 1));
1571         XA_BUG_ON(xa, xa_load(xa, index + i) != xa_mk_index(val));
1572     }
1573 
1574     xa_set_mark(xa, index, XA_MARK_0);
1575     XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
1576 
1577     xa_destroy(xa);
1578 }
1579 
1580 static noinline void check_split(struct xarray *xa)
1581 {
1582     unsigned int order, new_order;
1583 
1584     XA_BUG_ON(xa, !xa_empty(xa));
1585 
1586     for (order = 1; order < 2 * XA_CHUNK_SHIFT; order++) {
1587         for (new_order = 0; new_order < order; new_order++) {
1588             check_split_1(xa, 0, order, new_order);
1589             check_split_1(xa, 1UL << order, order, new_order);
1590             check_split_1(xa, 3UL << order, order, new_order);
1591         }
1592     }
1593 }
1594 #else
1595 static void check_split(struct xarray *xa) { }
1596 #endif
1597 
1598 static void check_align_1(struct xarray *xa, char *name)
1599 {
1600     int i;
1601     unsigned int id;
1602     unsigned long index;
1603     void *entry;
1604 
1605     for (i = 0; i < 8; i++) {
1606         XA_BUG_ON(xa, xa_alloc(xa, &id, name + i, xa_limit_32b,
1607                     GFP_KERNEL) != 0);
1608         XA_BUG_ON(xa, id != i);
1609     }
1610     xa_for_each(xa, index, entry)
1611         XA_BUG_ON(xa, xa_is_err(entry));
1612     xa_destroy(xa);
1613 }
1614 
1615 /*
1616  * We should always be able to store without allocating memory after
1617  * reserving a slot.
1618  */
1619 static void check_align_2(struct xarray *xa, char *name)
1620 {
1621     int i;
1622 
1623     XA_BUG_ON(xa, !xa_empty(xa));
1624 
1625     for (i = 0; i < 8; i++) {
1626         XA_BUG_ON(xa, xa_store(xa, 0, name + i, GFP_KERNEL) != NULL);
1627         xa_erase(xa, 0);
1628     }
1629 
1630     for (i = 0; i < 8; i++) {
1631         XA_BUG_ON(xa, xa_reserve(xa, 0, GFP_KERNEL) != 0);
1632         XA_BUG_ON(xa, xa_store(xa, 0, name + i, 0) != NULL);
1633         xa_erase(xa, 0);
1634     }
1635 
1636     XA_BUG_ON(xa, !xa_empty(xa));
1637 }
1638 
1639 static noinline void check_align(struct xarray *xa)
1640 {
1641     char name[] = "Motorola 68000";
1642 
1643     check_align_1(xa, name);
1644     check_align_1(xa, name + 1);
1645     check_align_1(xa, name + 2);
1646     check_align_1(xa, name + 3);
1647     check_align_2(xa, name);
1648 }
1649 
1650 static LIST_HEAD(shadow_nodes);
1651 
1652 static void test_update_node(struct xa_node *node)
1653 {
1654     if (node->count && node->count == node->nr_values) {
1655         if (list_empty(&node->private_list))
1656             list_add(&shadow_nodes, &node->private_list);
1657     } else {
1658         if (!list_empty(&node->private_list))
1659             list_del_init(&node->private_list);
1660     }
1661 }
1662 
1663 static noinline void shadow_remove(struct xarray *xa)
1664 {
1665     struct xa_node *node;
1666 
1667     xa_lock(xa);
1668     while ((node = list_first_entry_or_null(&shadow_nodes,
1669                     struct xa_node, private_list))) {
1670         XA_BUG_ON(xa, node->array != xa);
1671         list_del_init(&node->private_list);
1672         xa_delete_node(node, test_update_node);
1673     }
1674     xa_unlock(xa);
1675 }
1676 
1677 static noinline void check_workingset(struct xarray *xa, unsigned long index)
1678 {
1679     XA_STATE(xas, xa, index);
1680     xas_set_update(&xas, test_update_node);
1681 
1682     do {
1683         xas_lock(&xas);
1684         xas_store(&xas, xa_mk_value(0));
1685         xas_next(&xas);
1686         xas_store(&xas, xa_mk_value(1));
1687         xas_unlock(&xas);
1688     } while (xas_nomem(&xas, GFP_KERNEL));
1689 
1690     XA_BUG_ON(xa, list_empty(&shadow_nodes));
1691 
1692     xas_lock(&xas);
1693     xas_next(&xas);
1694     xas_store(&xas, &xas);
1695     XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1696 
1697     xas_store(&xas, xa_mk_value(2));
1698     xas_unlock(&xas);
1699     XA_BUG_ON(xa, list_empty(&shadow_nodes));
1700 
1701     shadow_remove(xa);
1702     XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1703     XA_BUG_ON(xa, !xa_empty(xa));
1704 }
1705 
1706 /*
1707  * Check that the pointer / value / sibling entries are accounted the
1708  * way we expect them to be.
1709  */
1710 static noinline void check_account(struct xarray *xa)
1711 {
1712 #ifdef CONFIG_XARRAY_MULTI
1713     unsigned int order;
1714 
1715     for (order = 1; order < 12; order++) {
1716         XA_STATE(xas, xa, 1 << order);
1717 
1718         xa_store_order(xa, 0, order, xa, GFP_KERNEL);
1719         rcu_read_lock();
1720         xas_load(&xas);
1721         XA_BUG_ON(xa, xas.xa_node->count == 0);
1722         XA_BUG_ON(xa, xas.xa_node->count > (1 << order));
1723         XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1724         rcu_read_unlock();
1725 
1726         xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order),
1727                 GFP_KERNEL);
1728         XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2);
1729 
1730         xa_erase(xa, 1 << order);
1731         XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1732 
1733         xa_erase(xa, 0);
1734         XA_BUG_ON(xa, !xa_empty(xa));
1735     }
1736 #endif
1737 }
1738 
1739 static noinline void check_get_order(struct xarray *xa)
1740 {
1741     unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
1742     unsigned int order;
1743     unsigned long i, j;
1744 
1745     for (i = 0; i < 3; i++)
1746         XA_BUG_ON(xa, xa_get_order(xa, i) != 0);
1747 
1748     for (order = 0; order < max_order; order++) {
1749         for (i = 0; i < 10; i++) {
1750             xa_store_order(xa, i << order, order,
1751                     xa_mk_index(i << order), GFP_KERNEL);
1752             for (j = i << order; j < (i + 1) << order; j++)
1753                 XA_BUG_ON(xa, xa_get_order(xa, j) != order);
1754             xa_erase(xa, i << order);
1755         }
1756     }
1757 }
1758 
1759 static noinline void check_destroy(struct xarray *xa)
1760 {
1761     unsigned long index;
1762 
1763     XA_BUG_ON(xa, !xa_empty(xa));
1764 
1765     /* Destroying an empty array is a no-op */
1766     xa_destroy(xa);
1767     XA_BUG_ON(xa, !xa_empty(xa));
1768 
1769     /* Destroying an array with a single entry */
1770     for (index = 0; index < 1000; index++) {
1771         xa_store_index(xa, index, GFP_KERNEL);
1772         XA_BUG_ON(xa, xa_empty(xa));
1773         xa_destroy(xa);
1774         XA_BUG_ON(xa, !xa_empty(xa));
1775     }
1776 
1777     /* Destroying an array with a single entry at ULONG_MAX */
1778     xa_store(xa, ULONG_MAX, xa, GFP_KERNEL);
1779     XA_BUG_ON(xa, xa_empty(xa));
1780     xa_destroy(xa);
1781     XA_BUG_ON(xa, !xa_empty(xa));
1782 
1783 #ifdef CONFIG_XARRAY_MULTI
1784     /* Destroying an array with a multi-index entry */
1785     xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL);
1786     XA_BUG_ON(xa, xa_empty(xa));
1787     xa_destroy(xa);
1788     XA_BUG_ON(xa, !xa_empty(xa));
1789 #endif
1790 }
1791 
1792 static DEFINE_XARRAY(array);
1793 
1794 static int xarray_checks(void)
1795 {
1796     check_xa_err(&array);
1797     check_xas_retry(&array);
1798     check_xa_load(&array);
1799     check_xa_mark(&array);
1800     check_xa_shrink(&array);
1801     check_xas_erase(&array);
1802     check_insert(&array);
1803     check_cmpxchg(&array);
1804     check_reserve(&array);
1805     check_reserve(&xa0);
1806     check_multi_store(&array);
1807     check_get_order(&array);
1808     check_xa_alloc();
1809     check_find(&array);
1810     check_find_entry(&array);
1811     check_pause(&array);
1812     check_account(&array);
1813     check_destroy(&array);
1814     check_move(&array);
1815     check_create_range(&array);
1816     check_store_range(&array);
1817     check_store_iter(&array);
1818     check_align(&xa0);
1819     check_split(&array);
1820 
1821     check_workingset(&array, 0);
1822     check_workingset(&array, 64);
1823     check_workingset(&array, 4096);
1824 
1825     printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);
1826     return (tests_run == tests_passed) ? 0 : -EINVAL;
1827 }
1828 
1829 static void xarray_exit(void)
1830 {
1831 }
1832 
1833 module_init(xarray_checks);
1834 module_exit(xarray_exit);
1835 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
1836 MODULE_LICENSE("GPL");
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!