test_xarray.c 47 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * test_xarray.c: Test the XArray API
  4. * Copyright (c) 2017-2018 Microsoft Corporation
  5. * Copyright (c) 2019-2020 Oracle
  6. * Author: Matthew Wilcox <willy@infradead.org>
  7. */
  8. #include <linux/xarray.h>
  9. #include <linux/module.h>
  10. static unsigned int tests_run;
  11. static unsigned int tests_passed;
  12. static const unsigned int order_limit =
  13. IS_ENABLED(CONFIG_XARRAY_MULTI) ? BITS_PER_LONG : 1;
  14. #ifndef XA_DEBUG
  15. # ifdef __KERNEL__
  16. void xa_dump(const struct xarray *xa) { }
  17. # endif
  18. #undef XA_BUG_ON
  19. #define XA_BUG_ON(xa, x) do { \
  20. tests_run++; \
  21. if (x) { \
  22. printk("BUG at %s:%d\n", __func__, __LINE__); \
  23. xa_dump(xa); \
  24. dump_stack(); \
  25. } else { \
  26. tests_passed++; \
  27. } \
  28. } while (0)
  29. #endif
  30. static void *xa_mk_index(unsigned long index)
  31. {
  32. return xa_mk_value(index & LONG_MAX);
  33. }
  34. static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp)
  35. {
  36. return xa_store(xa, index, xa_mk_index(index), gfp);
  37. }
  38. static void xa_insert_index(struct xarray *xa, unsigned long index)
  39. {
  40. XA_BUG_ON(xa, xa_insert(xa, index, xa_mk_index(index),
  41. GFP_KERNEL) != 0);
  42. }
  43. static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp)
  44. {
  45. u32 id;
  46. XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(index), xa_limit_32b,
  47. gfp) != 0);
  48. XA_BUG_ON(xa, id != index);
  49. }
  50. static void xa_erase_index(struct xarray *xa, unsigned long index)
  51. {
  52. XA_BUG_ON(xa, xa_erase(xa, index) != xa_mk_index(index));
  53. XA_BUG_ON(xa, xa_load(xa, index) != NULL);
  54. }
  55. /*
  56. * If anyone needs this, please move it to xarray.c. We have no current
  57. * users outside the test suite because all current multislot users want
  58. * to use the advanced API.
  59. */
  60. static void *xa_store_order(struct xarray *xa, unsigned long index,
  61. unsigned order, void *entry, gfp_t gfp)
  62. {
  63. XA_STATE_ORDER(xas, xa, index, order);
  64. void *curr;
  65. do {
  66. xas_lock(&xas);
  67. curr = xas_store(&xas, entry);
  68. xas_unlock(&xas);
  69. } while (xas_nomem(&xas, gfp));
  70. return curr;
  71. }
  72. static noinline void check_xa_err(struct xarray *xa)
  73. {
  74. XA_BUG_ON(xa, xa_err(xa_store_index(xa, 0, GFP_NOWAIT)) != 0);
  75. XA_BUG_ON(xa, xa_err(xa_erase(xa, 0)) != 0);
  76. #ifndef __KERNEL__
  77. /* The kernel does not fail GFP_NOWAIT allocations */
  78. XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
  79. XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
  80. #endif
  81. XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_KERNEL)) != 0);
  82. XA_BUG_ON(xa, xa_err(xa_store(xa, 1, xa_mk_value(0), GFP_KERNEL)) != 0);
  83. XA_BUG_ON(xa, xa_err(xa_erase(xa, 1)) != 0);
  84. // kills the test-suite :-(
  85. // XA_BUG_ON(xa, xa_err(xa_store(xa, 0, xa_mk_internal(0), 0)) != -EINVAL);
  86. }
  87. static noinline void check_xas_retry(struct xarray *xa)
  88. {
  89. XA_STATE(xas, xa, 0);
  90. void *entry;
  91. xa_store_index(xa, 0, GFP_KERNEL);
  92. xa_store_index(xa, 1, GFP_KERNEL);
  93. rcu_read_lock();
  94. XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_value(0));
  95. xa_erase_index(xa, 1);
  96. XA_BUG_ON(xa, !xa_is_retry(xas_reload(&xas)));
  97. XA_BUG_ON(xa, xas_retry(&xas, NULL));
  98. XA_BUG_ON(xa, xas_retry(&xas, xa_mk_value(0)));
  99. xas_reset(&xas);
  100. XA_BUG_ON(xa, xas.xa_node != XAS_RESTART);
  101. XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
  102. XA_BUG_ON(xa, xas.xa_node != NULL);
  103. rcu_read_unlock();
  104. XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
  105. rcu_read_lock();
  106. XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas)));
  107. xas.xa_node = XAS_RESTART;
  108. XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
  109. rcu_read_unlock();
  110. /* Make sure we can iterate through retry entries */
  111. xas_lock(&xas);
  112. xas_set(&xas, 0);
  113. xas_store(&xas, XA_RETRY_ENTRY);
  114. xas_set(&xas, 1);
  115. xas_store(&xas, XA_RETRY_ENTRY);
  116. xas_set(&xas, 0);
  117. xas_for_each(&xas, entry, ULONG_MAX) {
  118. xas_store(&xas, xa_mk_index(xas.xa_index));
  119. }
  120. xas_unlock(&xas);
  121. xa_erase_index(xa, 0);
  122. xa_erase_index(xa, 1);
  123. }
  124. static noinline void check_xa_load(struct xarray *xa)
  125. {
  126. unsigned long i, j;
  127. for (i = 0; i < 1024; i++) {
  128. for (j = 0; j < 1024; j++) {
  129. void *entry = xa_load(xa, j);
  130. if (j < i)
  131. XA_BUG_ON(xa, xa_to_value(entry) != j);
  132. else
  133. XA_BUG_ON(xa, entry);
  134. }
  135. XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
  136. }
  137. for (i = 0; i < 1024; i++) {
  138. for (j = 0; j < 1024; j++) {
  139. void *entry = xa_load(xa, j);
  140. if (j >= i)
  141. XA_BUG_ON(xa, xa_to_value(entry) != j);
  142. else
  143. XA_BUG_ON(xa, entry);
  144. }
  145. xa_erase_index(xa, i);
  146. }
  147. XA_BUG_ON(xa, !xa_empty(xa));
  148. }
  149. static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index)
  150. {
  151. unsigned int order;
  152. unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 8 : 1;
  153. /* NULL elements have no marks set */
  154. XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
  155. xa_set_mark(xa, index, XA_MARK_0);
  156. XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
  157. /* Storing a pointer will not make a mark appear */
  158. XA_BUG_ON(xa, xa_store_index(xa, index, GFP_KERNEL) != NULL);
  159. XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
  160. xa_set_mark(xa, index, XA_MARK_0);
  161. XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
  162. /* Setting one mark will not set another mark */
  163. XA_BUG_ON(xa, xa_get_mark(xa, index + 1, XA_MARK_0));
  164. XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_1));
  165. /* Storing NULL clears marks, and they can't be set again */
  166. xa_erase_index(xa, index);
  167. XA_BUG_ON(xa, !xa_empty(xa));
  168. XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
  169. xa_set_mark(xa, index, XA_MARK_0);
  170. XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
  171. /*
  172. * Storing a multi-index entry over entries with marks gives the
  173. * entire entry the union of the marks
  174. */
  175. BUG_ON((index % 4) != 0);
  176. for (order = 2; order < max_order; order++) {
  177. unsigned long base = round_down(index, 1UL << order);
  178. unsigned long next = base + (1UL << order);
  179. unsigned long i;
  180. XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL));
  181. xa_set_mark(xa, index + 1, XA_MARK_0);
  182. XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL));
  183. xa_set_mark(xa, index + 2, XA_MARK_2);
  184. XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL));
  185. xa_store_order(xa, index, order, xa_mk_index(index),
  186. GFP_KERNEL);
  187. for (i = base; i < next; i++) {
  188. XA_STATE(xas, xa, i);
  189. unsigned int seen = 0;
  190. void *entry;
  191. XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
  192. XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_1));
  193. XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_2));
  194. /* We should see two elements in the array */
  195. rcu_read_lock();
  196. xas_for_each(&xas, entry, ULONG_MAX)
  197. seen++;
  198. rcu_read_unlock();
  199. XA_BUG_ON(xa, seen != 2);
  200. /* One of which is marked */
  201. xas_set(&xas, 0);
  202. seen = 0;
  203. rcu_read_lock();
  204. xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
  205. seen++;
  206. rcu_read_unlock();
  207. XA_BUG_ON(xa, seen != 1);
  208. }
  209. XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0));
  210. XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_1));
  211. XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_2));
  212. xa_erase_index(xa, index);
  213. xa_erase_index(xa, next);
  214. XA_BUG_ON(xa, !xa_empty(xa));
  215. }
  216. XA_BUG_ON(xa, !xa_empty(xa));
  217. }
  218. static noinline void check_xa_mark_2(struct xarray *xa)
  219. {
  220. XA_STATE(xas, xa, 0);
  221. unsigned long index;
  222. unsigned int count = 0;
  223. void *entry;
  224. xa_store_index(xa, 0, GFP_KERNEL);
  225. xa_set_mark(xa, 0, XA_MARK_0);
  226. xas_lock(&xas);
  227. xas_load(&xas);
  228. xas_init_marks(&xas);
  229. xas_unlock(&xas);
  230. XA_BUG_ON(xa, !xa_get_mark(xa, 0, XA_MARK_0) == 0);
  231. for (index = 3500; index < 4500; index++) {
  232. xa_store_index(xa, index, GFP_KERNEL);
  233. xa_set_mark(xa, index, XA_MARK_0);
  234. }
  235. xas_reset(&xas);
  236. rcu_read_lock();
  237. xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
  238. count++;
  239. rcu_read_unlock();
  240. XA_BUG_ON(xa, count != 1000);
  241. xas_lock(&xas);
  242. xas_for_each(&xas, entry, ULONG_MAX) {
  243. xas_init_marks(&xas);
  244. XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0));
  245. XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0));
  246. }
  247. xas_unlock(&xas);
  248. xa_destroy(xa);
  249. }
  250. static noinline void check_xa_mark_3(struct xarray *xa)
  251. {
  252. #ifdef CONFIG_XARRAY_MULTI
  253. XA_STATE(xas, xa, 0x41);
  254. void *entry;
  255. int count = 0;
  256. xa_store_order(xa, 0x40, 2, xa_mk_index(0x40), GFP_KERNEL);
  257. xa_set_mark(xa, 0x41, XA_MARK_0);
  258. rcu_read_lock();
  259. xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) {
  260. count++;
  261. XA_BUG_ON(xa, entry != xa_mk_index(0x40));
  262. }
  263. XA_BUG_ON(xa, count != 1);
  264. rcu_read_unlock();
  265. xa_destroy(xa);
  266. #endif
  267. }
  268. static noinline void check_xa_mark(struct xarray *xa)
  269. {
  270. unsigned long index;
  271. for (index = 0; index < 16384; index += 4)
  272. check_xa_mark_1(xa, index);
  273. check_xa_mark_2(xa);
  274. check_xa_mark_3(xa);
  275. }
  276. static noinline void check_xa_shrink(struct xarray *xa)
  277. {
  278. XA_STATE(xas, xa, 1);
  279. struct xa_node *node;
  280. unsigned int order;
  281. unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 15 : 1;
  282. XA_BUG_ON(xa, !xa_empty(xa));
  283. XA_BUG_ON(xa, xa_store_index(xa, 0, GFP_KERNEL) != NULL);
  284. XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
  285. /*
  286. * Check that erasing the entry at 1 shrinks the tree and properly
  287. * marks the node as being deleted.
  288. */
  289. xas_lock(&xas);
  290. XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1));
  291. node = xas.xa_node;
  292. XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != xa_mk_value(0));
  293. XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
  294. XA_BUG_ON(xa, xa_load(xa, 1) != NULL);
  295. XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS);
  296. XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != XA_RETRY_ENTRY);
  297. XA_BUG_ON(xa, xas_load(&xas) != NULL);
  298. xas_unlock(&xas);
  299. XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
  300. xa_erase_index(xa, 0);
  301. XA_BUG_ON(xa, !xa_empty(xa));
  302. for (order = 0; order < max_order; order++) {
  303. unsigned long max = (1UL << order) - 1;
  304. xa_store_order(xa, 0, order, xa_mk_value(0), GFP_KERNEL);
  305. XA_BUG_ON(xa, xa_load(xa, max) != xa_mk_value(0));
  306. XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
  307. rcu_read_lock();
  308. node = xa_head(xa);
  309. rcu_read_unlock();
  310. XA_BUG_ON(xa, xa_store_index(xa, ULONG_MAX, GFP_KERNEL) !=
  311. NULL);
  312. rcu_read_lock();
  313. XA_BUG_ON(xa, xa_head(xa) == node);
  314. rcu_read_unlock();
  315. XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
  316. xa_erase_index(xa, ULONG_MAX);
  317. XA_BUG_ON(xa, xa->xa_head != node);
  318. xa_erase_index(xa, 0);
  319. }
  320. }
  321. static noinline void check_insert(struct xarray *xa)
  322. {
  323. unsigned long i;
  324. for (i = 0; i < 1024; i++) {
  325. xa_insert_index(xa, i);
  326. XA_BUG_ON(xa, xa_load(xa, i - 1) != NULL);
  327. XA_BUG_ON(xa, xa_load(xa, i + 1) != NULL);
  328. xa_erase_index(xa, i);
  329. }
  330. for (i = 10; i < BITS_PER_LONG; i++) {
  331. xa_insert_index(xa, 1UL << i);
  332. XA_BUG_ON(xa, xa_load(xa, (1UL << i) - 1) != NULL);
  333. XA_BUG_ON(xa, xa_load(xa, (1UL << i) + 1) != NULL);
  334. xa_erase_index(xa, 1UL << i);
  335. xa_insert_index(xa, (1UL << i) - 1);
  336. XA_BUG_ON(xa, xa_load(xa, (1UL << i) - 2) != NULL);
  337. XA_BUG_ON(xa, xa_load(xa, 1UL << i) != NULL);
  338. xa_erase_index(xa, (1UL << i) - 1);
  339. }
  340. xa_insert_index(xa, ~0UL);
  341. XA_BUG_ON(xa, xa_load(xa, 0UL) != NULL);
  342. XA_BUG_ON(xa, xa_load(xa, ~1UL) != NULL);
  343. xa_erase_index(xa, ~0UL);
  344. XA_BUG_ON(xa, !xa_empty(xa));
  345. }
  346. static noinline void check_cmpxchg(struct xarray *xa)
  347. {
  348. void *FIVE = xa_mk_value(5);
  349. void *SIX = xa_mk_value(6);
  350. void *LOTS = xa_mk_value(12345678);
  351. XA_BUG_ON(xa, !xa_empty(xa));
  352. XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL);
  353. XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EBUSY);
  354. XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS);
  355. XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS);
  356. XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE);
  357. XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL);
  358. XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL);
  359. XA_BUG_ON(xa, xa_insert(xa, 5, FIVE, GFP_KERNEL) != -EBUSY);
  360. XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != FIVE);
  361. XA_BUG_ON(xa, xa_insert(xa, 5, FIVE, GFP_KERNEL) == -EBUSY);
  362. xa_erase_index(xa, 12345678);
  363. xa_erase_index(xa, 5);
  364. XA_BUG_ON(xa, !xa_empty(xa));
  365. }
  366. static noinline void check_reserve(struct xarray *xa)
  367. {
  368. void *entry;
  369. unsigned long index;
  370. int count;
  371. /* An array with a reserved entry is not empty */
  372. XA_BUG_ON(xa, !xa_empty(xa));
  373. XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
  374. XA_BUG_ON(xa, xa_empty(xa));
  375. XA_BUG_ON(xa, xa_load(xa, 12345678));
  376. xa_release(xa, 12345678);
  377. XA_BUG_ON(xa, !xa_empty(xa));
  378. /* Releasing a used entry does nothing */
  379. XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
  380. XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL);
  381. xa_release(xa, 12345678);
  382. xa_erase_index(xa, 12345678);
  383. XA_BUG_ON(xa, !xa_empty(xa));
  384. /* cmpxchg sees a reserved entry as ZERO */
  385. XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
  386. XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, XA_ZERO_ENTRY,
  387. xa_mk_value(12345678), GFP_NOWAIT) != NULL);
  388. xa_release(xa, 12345678);
  389. xa_erase_index(xa, 12345678);
  390. XA_BUG_ON(xa, !xa_empty(xa));
  391. /* xa_insert treats it as busy */
  392. XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
  393. XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) !=
  394. -EBUSY);
  395. XA_BUG_ON(xa, xa_empty(xa));
  396. XA_BUG_ON(xa, xa_erase(xa, 12345678) != NULL);
  397. XA_BUG_ON(xa, !xa_empty(xa));
  398. /* Can iterate through a reserved entry */
  399. xa_store_index(xa, 5, GFP_KERNEL);
  400. XA_BUG_ON(xa, xa_reserve(xa, 6, GFP_KERNEL) != 0);
  401. xa_store_index(xa, 7, GFP_KERNEL);
  402. count = 0;
  403. xa_for_each(xa, index, entry) {
  404. XA_BUG_ON(xa, index != 5 && index != 7);
  405. count++;
  406. }
  407. XA_BUG_ON(xa, count != 2);
  408. /* If we free a reserved entry, we should be able to allocate it */
  409. if (xa->xa_flags & XA_FLAGS_ALLOC) {
  410. u32 id;
  411. XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(8),
  412. XA_LIMIT(5, 10), GFP_KERNEL) != 0);
  413. XA_BUG_ON(xa, id != 8);
  414. xa_release(xa, 6);
  415. XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(6),
  416. XA_LIMIT(5, 10), GFP_KERNEL) != 0);
  417. XA_BUG_ON(xa, id != 6);
  418. }
  419. xa_destroy(xa);
  420. }
  421. static noinline void check_xas_erase(struct xarray *xa)
  422. {
  423. XA_STATE(xas, xa, 0);
  424. void *entry;
  425. unsigned long i, j;
  426. for (i = 0; i < 200; i++) {
  427. for (j = i; j < 2 * i + 17; j++) {
  428. xas_set(&xas, j);
  429. do {
  430. xas_lock(&xas);
  431. xas_store(&xas, xa_mk_index(j));
  432. xas_unlock(&xas);
  433. } while (xas_nomem(&xas, GFP_KERNEL));
  434. }
  435. xas_set(&xas, ULONG_MAX);
  436. do {
  437. xas_lock(&xas);
  438. xas_store(&xas, xa_mk_value(0));
  439. xas_unlock(&xas);
  440. } while (xas_nomem(&xas, GFP_KERNEL));
  441. xas_lock(&xas);
  442. xas_store(&xas, NULL);
  443. xas_set(&xas, 0);
  444. j = i;
  445. xas_for_each(&xas, entry, ULONG_MAX) {
  446. XA_BUG_ON(xa, entry != xa_mk_index(j));
  447. xas_store(&xas, NULL);
  448. j++;
  449. }
  450. xas_unlock(&xas);
  451. XA_BUG_ON(xa, !xa_empty(xa));
  452. }
  453. }
  454. #ifdef CONFIG_XARRAY_MULTI
  455. static noinline void check_multi_store_1(struct xarray *xa, unsigned long index,
  456. unsigned int order)
  457. {
  458. XA_STATE(xas, xa, index);
  459. unsigned long min = index & ~((1UL << order) - 1);
  460. unsigned long max = min + (1UL << order);
  461. xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
  462. XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(index));
  463. XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(index));
  464. XA_BUG_ON(xa, xa_load(xa, max) != NULL);
  465. XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
  466. xas_lock(&xas);
  467. XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(min)) != xa_mk_index(index));
  468. xas_unlock(&xas);
  469. XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(min));
  470. XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(min));
  471. XA_BUG_ON(xa, xa_load(xa, max) != NULL);
  472. XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
  473. xa_erase_index(xa, min);
  474. XA_BUG_ON(xa, !xa_empty(xa));
  475. }
  476. static noinline void check_multi_store_2(struct xarray *xa, unsigned long index,
  477. unsigned int order)
  478. {
  479. XA_STATE(xas, xa, index);
  480. xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL);
  481. xas_lock(&xas);
  482. XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0));
  483. XA_BUG_ON(xa, xas.xa_index != index);
  484. XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
  485. xas_unlock(&xas);
  486. XA_BUG_ON(xa, !xa_empty(xa));
  487. }
  488. static noinline void check_multi_store_3(struct xarray *xa, unsigned long index,
  489. unsigned int order)
  490. {
  491. XA_STATE(xas, xa, 0);
  492. void *entry;
  493. int n = 0;
  494. xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
  495. xas_lock(&xas);
  496. xas_for_each(&xas, entry, ULONG_MAX) {
  497. XA_BUG_ON(xa, entry != xa_mk_index(index));
  498. n++;
  499. }
  500. XA_BUG_ON(xa, n != 1);
  501. xas_set(&xas, index + 1);
  502. xas_for_each(&xas, entry, ULONG_MAX) {
  503. XA_BUG_ON(xa, entry != xa_mk_index(index));
  504. n++;
  505. }
  506. XA_BUG_ON(xa, n != 2);
  507. xas_unlock(&xas);
  508. xa_destroy(xa);
  509. }
  510. #endif
  511. static noinline void check_multi_store(struct xarray *xa)
  512. {
  513. #ifdef CONFIG_XARRAY_MULTI
  514. unsigned long i, j, k;
  515. unsigned int max_order = (sizeof(long) == 4) ? 30 : 60;
  516. /* Loading from any position returns the same value */
  517. xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL);
  518. XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
  519. XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
  520. XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
  521. rcu_read_lock();
  522. XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2);
  523. XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
  524. rcu_read_unlock();
  525. /* Storing adjacent to the value does not alter the value */
  526. xa_store(xa, 3, xa, GFP_KERNEL);
  527. XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
  528. XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
  529. XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
  530. rcu_read_lock();
  531. XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3);
  532. XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
  533. rcu_read_unlock();
  534. /* Overwriting multiple indexes works */
  535. xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL);
  536. XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1));
  537. XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1));
  538. XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1));
  539. XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1));
  540. XA_BUG_ON(xa, xa_load(xa, 4) != NULL);
  541. rcu_read_lock();
  542. XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4);
  543. XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4);
  544. rcu_read_unlock();
  545. /* We can erase multiple values with a single store */
  546. xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL);
  547. XA_BUG_ON(xa, !xa_empty(xa));
  548. /* Even when the first slot is empty but the others aren't */
  549. xa_store_index(xa, 1, GFP_KERNEL);
  550. xa_store_index(xa, 2, GFP_KERNEL);
  551. xa_store_order(xa, 0, 2, NULL, GFP_KERNEL);
  552. XA_BUG_ON(xa, !xa_empty(xa));
  553. for (i = 0; i < max_order; i++) {
  554. for (j = 0; j < max_order; j++) {
  555. xa_store_order(xa, 0, i, xa_mk_index(i), GFP_KERNEL);
  556. xa_store_order(xa, 0, j, xa_mk_index(j), GFP_KERNEL);
  557. for (k = 0; k < max_order; k++) {
  558. void *entry = xa_load(xa, (1UL << k) - 1);
  559. if ((i < k) && (j < k))
  560. XA_BUG_ON(xa, entry != NULL);
  561. else
  562. XA_BUG_ON(xa, entry != xa_mk_index(j));
  563. }
  564. xa_erase(xa, 0);
  565. XA_BUG_ON(xa, !xa_empty(xa));
  566. }
  567. }
  568. for (i = 0; i < 20; i++) {
  569. check_multi_store_1(xa, 200, i);
  570. check_multi_store_1(xa, 0, i);
  571. check_multi_store_1(xa, (1UL << i) + 1, i);
  572. }
  573. check_multi_store_2(xa, 4095, 9);
  574. for (i = 1; i < 20; i++) {
  575. check_multi_store_3(xa, 0, i);
  576. check_multi_store_3(xa, 1UL << i, i);
  577. }
  578. #endif
  579. }
  580. static noinline void check_xa_alloc_1(struct xarray *xa, unsigned int base)
  581. {
  582. int i;
  583. u32 id;
  584. XA_BUG_ON(xa, !xa_empty(xa));
  585. /* An empty array should assign %base to the first alloc */
  586. xa_alloc_index(xa, base, GFP_KERNEL);
  587. /* Erasing it should make the array empty again */
  588. xa_erase_index(xa, base);
  589. XA_BUG_ON(xa, !xa_empty(xa));
  590. /* And it should assign %base again */
  591. xa_alloc_index(xa, base, GFP_KERNEL);
  592. /* Allocating and then erasing a lot should not lose base */
  593. for (i = base + 1; i < 2 * XA_CHUNK_SIZE; i++)
  594. xa_alloc_index(xa, i, GFP_KERNEL);
  595. for (i = base; i < 2 * XA_CHUNK_SIZE; i++)
  596. xa_erase_index(xa, i);
  597. xa_alloc_index(xa, base, GFP_KERNEL);
  598. /* Destroying the array should do the same as erasing */
  599. xa_destroy(xa);
  600. /* And it should assign %base again */
  601. xa_alloc_index(xa, base, GFP_KERNEL);
  602. /* The next assigned ID should be base+1 */
  603. xa_alloc_index(xa, base + 1, GFP_KERNEL);
  604. xa_erase_index(xa, base + 1);
  605. /* Storing a value should mark it used */
  606. xa_store_index(xa, base + 1, GFP_KERNEL);
  607. xa_alloc_index(xa, base + 2, GFP_KERNEL);
  608. /* If we then erase base, it should be free */
  609. xa_erase_index(xa, base);
  610. xa_alloc_index(xa, base, GFP_KERNEL);
  611. xa_erase_index(xa, base + 1);
  612. xa_erase_index(xa, base + 2);
  613. for (i = 1; i < 5000; i++) {
  614. xa_alloc_index(xa, base + i, GFP_KERNEL);
  615. }
  616. xa_destroy(xa);
  617. /* Check that we fail properly at the limit of allocation */
  618. XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX - 1),
  619. XA_LIMIT(UINT_MAX - 1, UINT_MAX),
  620. GFP_KERNEL) != 0);
  621. XA_BUG_ON(xa, id != 0xfffffffeU);
  622. XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX),
  623. XA_LIMIT(UINT_MAX - 1, UINT_MAX),
  624. GFP_KERNEL) != 0);
  625. XA_BUG_ON(xa, id != 0xffffffffU);
  626. id = 3;
  627. XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(0),
  628. XA_LIMIT(UINT_MAX - 1, UINT_MAX),
  629. GFP_KERNEL) != -EBUSY);
  630. XA_BUG_ON(xa, id != 3);
  631. xa_destroy(xa);
  632. XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
  633. GFP_KERNEL) != -EBUSY);
  634. XA_BUG_ON(xa, xa_store_index(xa, 3, GFP_KERNEL) != 0);
  635. XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
  636. GFP_KERNEL) != -EBUSY);
  637. xa_erase_index(xa, 3);
  638. XA_BUG_ON(xa, !xa_empty(xa));
  639. }
  640. static noinline void check_xa_alloc_2(struct xarray *xa, unsigned int base)
  641. {
  642. unsigned int i, id;
  643. unsigned long index;
  644. void *entry;
  645. /* Allocate and free a NULL and check xa_empty() behaves */
  646. XA_BUG_ON(xa, !xa_empty(xa));
  647. XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
  648. XA_BUG_ON(xa, id != base);
  649. XA_BUG_ON(xa, xa_empty(xa));
  650. XA_BUG_ON(xa, xa_erase(xa, id) != NULL);
  651. XA_BUG_ON(xa, !xa_empty(xa));
  652. /* Ditto, but check destroy instead of erase */
  653. XA_BUG_ON(xa, !xa_empty(xa));
  654. XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
  655. XA_BUG_ON(xa, id != base);
  656. XA_BUG_ON(xa, xa_empty(xa));
  657. xa_destroy(xa);
  658. XA_BUG_ON(xa, !xa_empty(xa));
  659. for (i = base; i < base + 10; i++) {
  660. XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b,
  661. GFP_KERNEL) != 0);
  662. XA_BUG_ON(xa, id != i);
  663. }
  664. XA_BUG_ON(xa, xa_store(xa, 3, xa_mk_index(3), GFP_KERNEL) != NULL);
  665. XA_BUG_ON(xa, xa_store(xa, 4, xa_mk_index(4), GFP_KERNEL) != NULL);
  666. XA_BUG_ON(xa, xa_store(xa, 4, NULL, GFP_KERNEL) != xa_mk_index(4));
  667. XA_BUG_ON(xa, xa_erase(xa, 5) != NULL);
  668. XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
  669. XA_BUG_ON(xa, id != 5);
  670. xa_for_each(xa, index, entry) {
  671. xa_erase_index(xa, index);
  672. }
  673. for (i = base; i < base + 9; i++) {
  674. XA_BUG_ON(xa, xa_erase(xa, i) != NULL);
  675. XA_BUG_ON(xa, xa_empty(xa));
  676. }
  677. XA_BUG_ON(xa, xa_erase(xa, 8) != NULL);
  678. XA_BUG_ON(xa, xa_empty(xa));
  679. XA_BUG_ON(xa, xa_erase(xa, base + 9) != NULL);
  680. XA_BUG_ON(xa, !xa_empty(xa));
  681. xa_destroy(xa);
  682. }
  683. static noinline void check_xa_alloc_3(struct xarray *xa, unsigned int base)
  684. {
  685. struct xa_limit limit = XA_LIMIT(1, 0x3fff);
  686. u32 next = 0;
  687. unsigned int i, id;
  688. unsigned long index;
  689. void *entry;
  690. XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(1), limit,
  691. &next, GFP_KERNEL) != 0);
  692. XA_BUG_ON(xa, id != 1);
  693. next = 0x3ffd;
  694. XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(0x3ffd), limit,
  695. &next, GFP_KERNEL) != 0);
  696. XA_BUG_ON(xa, id != 0x3ffd);
  697. xa_erase_index(xa, 0x3ffd);
  698. xa_erase_index(xa, 1);
  699. XA_BUG_ON(xa, !xa_empty(xa));
  700. for (i = 0x3ffe; i < 0x4003; i++) {
  701. if (i < 0x4000)
  702. entry = xa_mk_index(i);
  703. else
  704. entry = xa_mk_index(i - 0x3fff);
  705. XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, entry, limit,
  706. &next, GFP_KERNEL) != (id == 1));
  707. XA_BUG_ON(xa, xa_mk_index(id) != entry);
  708. }
  709. /* Check wrap-around is handled correctly */
  710. if (base != 0)
  711. xa_erase_index(xa, base);
  712. xa_erase_index(xa, base + 1);
  713. next = UINT_MAX;
  714. XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(UINT_MAX),
  715. xa_limit_32b, &next, GFP_KERNEL) != 0);
  716. XA_BUG_ON(xa, id != UINT_MAX);
  717. XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base),
  718. xa_limit_32b, &next, GFP_KERNEL) != 1);
  719. XA_BUG_ON(xa, id != base);
  720. XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base + 1),
  721. xa_limit_32b, &next, GFP_KERNEL) != 0);
  722. XA_BUG_ON(xa, id != base + 1);
  723. xa_for_each(xa, index, entry)
  724. xa_erase_index(xa, index);
  725. XA_BUG_ON(xa, !xa_empty(xa));
  726. }
  727. static DEFINE_XARRAY_ALLOC(xa0);
  728. static DEFINE_XARRAY_ALLOC1(xa1);
  729. static noinline void check_xa_alloc(void)
  730. {
  731. check_xa_alloc_1(&xa0, 0);
  732. check_xa_alloc_1(&xa1, 1);
  733. check_xa_alloc_2(&xa0, 0);
  734. check_xa_alloc_2(&xa1, 1);
  735. check_xa_alloc_3(&xa0, 0);
  736. check_xa_alloc_3(&xa1, 1);
  737. }
  738. static noinline void __check_store_iter(struct xarray *xa, unsigned long start,
  739. unsigned int order, unsigned int present)
  740. {
  741. XA_STATE_ORDER(xas, xa, start, order);
  742. void *entry;
  743. unsigned int count = 0;
  744. retry:
  745. xas_lock(&xas);
  746. xas_for_each_conflict(&xas, entry) {
  747. XA_BUG_ON(xa, !xa_is_value(entry));
  748. XA_BUG_ON(xa, entry < xa_mk_index(start));
  749. XA_BUG_ON(xa, entry > xa_mk_index(start + (1UL << order) - 1));
  750. count++;
  751. }
  752. xas_store(&xas, xa_mk_index(start));
  753. xas_unlock(&xas);
  754. if (xas_nomem(&xas, GFP_KERNEL)) {
  755. count = 0;
  756. goto retry;
  757. }
  758. XA_BUG_ON(xa, xas_error(&xas));
  759. XA_BUG_ON(xa, count != present);
  760. XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_index(start));
  761. XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=
  762. xa_mk_index(start));
  763. xa_erase_index(xa, start);
  764. }
  765. static noinline void check_store_iter(struct xarray *xa)
  766. {
  767. unsigned int i, j;
  768. unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
  769. for (i = 0; i < max_order; i++) {
  770. unsigned int min = 1 << i;
  771. unsigned int max = (2 << i) - 1;
  772. __check_store_iter(xa, 0, i, 0);
  773. XA_BUG_ON(xa, !xa_empty(xa));
  774. __check_store_iter(xa, min, i, 0);
  775. XA_BUG_ON(xa, !xa_empty(xa));
  776. xa_store_index(xa, min, GFP_KERNEL);
  777. __check_store_iter(xa, min, i, 1);
  778. XA_BUG_ON(xa, !xa_empty(xa));
  779. xa_store_index(xa, max, GFP_KERNEL);
  780. __check_store_iter(xa, min, i, 1);
  781. XA_BUG_ON(xa, !xa_empty(xa));
  782. for (j = 0; j < min; j++)
  783. xa_store_index(xa, j, GFP_KERNEL);
  784. __check_store_iter(xa, 0, i, min);
  785. XA_BUG_ON(xa, !xa_empty(xa));
  786. for (j = 0; j < min; j++)
  787. xa_store_index(xa, min + j, GFP_KERNEL);
  788. __check_store_iter(xa, min, i, min);
  789. XA_BUG_ON(xa, !xa_empty(xa));
  790. }
  791. #ifdef CONFIG_XARRAY_MULTI
  792. xa_store_index(xa, 63, GFP_KERNEL);
  793. xa_store_index(xa, 65, GFP_KERNEL);
  794. __check_store_iter(xa, 64, 2, 1);
  795. xa_erase_index(xa, 63);
  796. #endif
  797. XA_BUG_ON(xa, !xa_empty(xa));
  798. }
  799. static noinline void check_multi_find_1(struct xarray *xa, unsigned order)
  800. {
  801. #ifdef CONFIG_XARRAY_MULTI
  802. unsigned long multi = 3 << order;
  803. unsigned long next = 4 << order;
  804. unsigned long index;
  805. xa_store_order(xa, multi, order, xa_mk_value(multi), GFP_KERNEL);
  806. XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL) != NULL);
  807. XA_BUG_ON(xa, xa_store_index(xa, next + 1, GFP_KERNEL) != NULL);
  808. index = 0;
  809. XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
  810. xa_mk_value(multi));
  811. XA_BUG_ON(xa, index != multi);
  812. index = multi + 1;
  813. XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
  814. xa_mk_value(multi));
  815. XA_BUG_ON(xa, (index < multi) || (index >= next));
  816. XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) !=
  817. xa_mk_value(next));
  818. XA_BUG_ON(xa, index != next);
  819. XA_BUG_ON(xa, xa_find_after(xa, &index, next, XA_PRESENT) != NULL);
  820. XA_BUG_ON(xa, index != next);
  821. xa_erase_index(xa, multi);
  822. xa_erase_index(xa, next);
  823. xa_erase_index(xa, next + 1);
  824. XA_BUG_ON(xa, !xa_empty(xa));
  825. #endif
  826. }
  827. static noinline void check_multi_find_2(struct xarray *xa)
  828. {
  829. unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1;
  830. unsigned int i, j;
  831. void *entry;
  832. for (i = 0; i < max_order; i++) {
  833. unsigned long index = 1UL << i;
  834. for (j = 0; j < index; j++) {
  835. XA_STATE(xas, xa, j + index);
  836. xa_store_index(xa, index - 1, GFP_KERNEL);
  837. xa_store_order(xa, index, i, xa_mk_index(index),
  838. GFP_KERNEL);
  839. rcu_read_lock();
  840. xas_for_each(&xas, entry, ULONG_MAX) {
  841. xa_erase_index(xa, index);
  842. }
  843. rcu_read_unlock();
  844. xa_erase_index(xa, index - 1);
  845. XA_BUG_ON(xa, !xa_empty(xa));
  846. }
  847. }
  848. }
  849. static noinline void check_multi_find_3(struct xarray *xa)
  850. {
  851. unsigned int order;
  852. for (order = 5; order < order_limit; order++) {
  853. unsigned long index = 1UL << (order - 5);
  854. XA_BUG_ON(xa, !xa_empty(xa));
  855. xa_store_order(xa, 0, order - 4, xa_mk_index(0), GFP_KERNEL);
  856. XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT));
  857. xa_erase_index(xa, 0);
  858. }
  859. }
  860. static noinline void check_find_1(struct xarray *xa)
  861. {
  862. unsigned long i, j, k;
  863. XA_BUG_ON(xa, !xa_empty(xa));
  864. /*
  865. * Check xa_find with all pairs between 0 and 99 inclusive,
  866. * starting at every index between 0 and 99
  867. */
  868. for (i = 0; i < 100; i++) {
  869. XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
  870. xa_set_mark(xa, i, XA_MARK_0);
  871. for (j = 0; j < i; j++) {
  872. XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) !=
  873. NULL);
  874. xa_set_mark(xa, j, XA_MARK_0);
  875. for (k = 0; k < 100; k++) {
  876. unsigned long index = k;
  877. void *entry = xa_find(xa, &index, ULONG_MAX,
  878. XA_PRESENT);
  879. if (k <= j)
  880. XA_BUG_ON(xa, index != j);
  881. else if (k <= i)
  882. XA_BUG_ON(xa, index != i);
  883. else
  884. XA_BUG_ON(xa, entry != NULL);
  885. index = k;
  886. entry = xa_find(xa, &index, ULONG_MAX,
  887. XA_MARK_0);
  888. if (k <= j)
  889. XA_BUG_ON(xa, index != j);
  890. else if (k <= i)
  891. XA_BUG_ON(xa, index != i);
  892. else
  893. XA_BUG_ON(xa, entry != NULL);
  894. }
  895. xa_erase_index(xa, j);
  896. XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0));
  897. XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
  898. }
  899. xa_erase_index(xa, i);
  900. XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0));
  901. }
  902. XA_BUG_ON(xa, !xa_empty(xa));
  903. }
  904. static noinline void check_find_2(struct xarray *xa)
  905. {
  906. void *entry;
  907. unsigned long i, j, index;
  908. xa_for_each(xa, index, entry) {
  909. XA_BUG_ON(xa, true);
  910. }
  911. for (i = 0; i < 1024; i++) {
  912. xa_store_index(xa, index, GFP_KERNEL);
  913. j = 0;
  914. xa_for_each(xa, index, entry) {
  915. XA_BUG_ON(xa, xa_mk_index(index) != entry);
  916. XA_BUG_ON(xa, index != j++);
  917. }
  918. }
  919. xa_destroy(xa);
  920. }
  921. static noinline void check_find_3(struct xarray *xa)
  922. {
  923. XA_STATE(xas, xa, 0);
  924. unsigned long i, j, k;
  925. void *entry;
  926. for (i = 0; i < 100; i++) {
  927. for (j = 0; j < 100; j++) {
  928. rcu_read_lock();
  929. for (k = 0; k < 100; k++) {
  930. xas_set(&xas, j);
  931. xas_for_each_marked(&xas, entry, k, XA_MARK_0)
  932. ;
  933. if (j > k)
  934. XA_BUG_ON(xa,
  935. xas.xa_node != XAS_RESTART);
  936. }
  937. rcu_read_unlock();
  938. }
  939. xa_store_index(xa, i, GFP_KERNEL);
  940. xa_set_mark(xa, i, XA_MARK_0);
  941. }
  942. xa_destroy(xa);
  943. }
  944. static noinline void check_find_4(struct xarray *xa)
  945. {
  946. unsigned long index = 0;
  947. void *entry;
  948. xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
  949. entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);
  950. XA_BUG_ON(xa, entry != xa_mk_index(ULONG_MAX));
  951. entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);
  952. XA_BUG_ON(xa, entry);
  953. xa_erase_index(xa, ULONG_MAX);
  954. }
  955. static noinline void check_find(struct xarray *xa)
  956. {
  957. unsigned i;
  958. check_find_1(xa);
  959. check_find_2(xa);
  960. check_find_3(xa);
  961. check_find_4(xa);
  962. for (i = 2; i < 10; i++)
  963. check_multi_find_1(xa, i);
  964. check_multi_find_2(xa);
  965. check_multi_find_3(xa);
  966. }
  967. /* See find_swap_entry() in mm/shmem.c */
  968. static noinline unsigned long xa_find_entry(struct xarray *xa, void *item)
  969. {
  970. XA_STATE(xas, xa, 0);
  971. unsigned int checked = 0;
  972. void *entry;
  973. rcu_read_lock();
  974. xas_for_each(&xas, entry, ULONG_MAX) {
  975. if (xas_retry(&xas, entry))
  976. continue;
  977. if (entry == item)
  978. break;
  979. checked++;
  980. if ((checked % 4) != 0)
  981. continue;
  982. xas_pause(&xas);
  983. }
  984. rcu_read_unlock();
  985. return entry ? xas.xa_index : -1;
  986. }
  987. static noinline void check_find_entry(struct xarray *xa)
  988. {
  989. #ifdef CONFIG_XARRAY_MULTI
  990. unsigned int order;
  991. unsigned long offset, index;
  992. for (order = 0; order < 20; order++) {
  993. for (offset = 0; offset < (1UL << (order + 3));
  994. offset += (1UL << order)) {
  995. for (index = 0; index < (1UL << (order + 5));
  996. index += (1UL << order)) {
  997. xa_store_order(xa, index, order,
  998. xa_mk_index(index), GFP_KERNEL);
  999. XA_BUG_ON(xa, xa_load(xa, index) !=
  1000. xa_mk_index(index));
  1001. XA_BUG_ON(xa, xa_find_entry(xa,
  1002. xa_mk_index(index)) != index);
  1003. }
  1004. XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
  1005. xa_destroy(xa);
  1006. }
  1007. }
  1008. #endif
  1009. XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
  1010. xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
  1011. XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
  1012. XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_index(ULONG_MAX)) != -1);
  1013. xa_erase_index(xa, ULONG_MAX);
  1014. XA_BUG_ON(xa, !xa_empty(xa));
  1015. }
  1016. static noinline void check_pause(struct xarray *xa)
  1017. {
  1018. XA_STATE(xas, xa, 0);
  1019. void *entry;
  1020. unsigned int order;
  1021. unsigned long index = 1;
  1022. unsigned int count = 0;
  1023. for (order = 0; order < order_limit; order++) {
  1024. XA_BUG_ON(xa, xa_store_order(xa, index, order,
  1025. xa_mk_index(index), GFP_KERNEL));
  1026. index += 1UL << order;
  1027. }
  1028. rcu_read_lock();
  1029. xas_for_each(&xas, entry, ULONG_MAX) {
  1030. XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));
  1031. count++;
  1032. }
  1033. rcu_read_unlock();
  1034. XA_BUG_ON(xa, count != order_limit);
  1035. count = 0;
  1036. xas_set(&xas, 0);
  1037. rcu_read_lock();
  1038. xas_for_each(&xas, entry, ULONG_MAX) {
  1039. XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));
  1040. count++;
  1041. xas_pause(&xas);
  1042. }
  1043. rcu_read_unlock();
  1044. XA_BUG_ON(xa, count != order_limit);
  1045. xa_destroy(xa);
  1046. }
  1047. static noinline void check_move_tiny(struct xarray *xa)
  1048. {
  1049. XA_STATE(xas, xa, 0);
  1050. XA_BUG_ON(xa, !xa_empty(xa));
  1051. rcu_read_lock();
  1052. XA_BUG_ON(xa, xas_next(&xas) != NULL);
  1053. XA_BUG_ON(xa, xas_next(&xas) != NULL);
  1054. rcu_read_unlock();
  1055. xa_store_index(xa, 0, GFP_KERNEL);
  1056. rcu_read_lock();
  1057. xas_set(&xas, 0);
  1058. XA_BUG_ON(xa, xas_next(&xas) != xa_mk_index(0));
  1059. XA_BUG_ON(xa, xas_next(&xas) != NULL);
  1060. xas_set(&xas, 0);
  1061. XA_BUG_ON(xa, xas_prev(&xas) != xa_mk_index(0));
  1062. XA_BUG_ON(xa, xas_prev(&xas) != NULL);
  1063. rcu_read_unlock();
  1064. xa_erase_index(xa, 0);
  1065. XA_BUG_ON(xa, !xa_empty(xa));
  1066. }
  1067. static noinline void check_move_max(struct xarray *xa)
  1068. {
  1069. XA_STATE(xas, xa, 0);
  1070. xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
  1071. rcu_read_lock();
  1072. XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));
  1073. XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);
  1074. rcu_read_unlock();
  1075. xas_set(&xas, 0);
  1076. rcu_read_lock();
  1077. XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));
  1078. xas_pause(&xas);
  1079. XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);
  1080. rcu_read_unlock();
  1081. xa_erase_index(xa, ULONG_MAX);
  1082. XA_BUG_ON(xa, !xa_empty(xa));
  1083. }
  1084. static noinline void check_move_small(struct xarray *xa, unsigned long idx)
  1085. {
  1086. XA_STATE(xas, xa, 0);
  1087. unsigned long i;
  1088. xa_store_index(xa, 0, GFP_KERNEL);
  1089. xa_store_index(xa, idx, GFP_KERNEL);
  1090. rcu_read_lock();
  1091. for (i = 0; i < idx * 4; i++) {
  1092. void *entry = xas_next(&xas);
  1093. if (i <= idx)
  1094. XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
  1095. XA_BUG_ON(xa, xas.xa_index != i);
  1096. if (i == 0 || i == idx)
  1097. XA_BUG_ON(xa, entry != xa_mk_index(i));
  1098. else
  1099. XA_BUG_ON(xa, entry != NULL);
  1100. }
  1101. xas_next(&xas);
  1102. XA_BUG_ON(xa, xas.xa_index != i);
  1103. do {
  1104. void *entry = xas_prev(&xas);
  1105. i--;
  1106. if (i <= idx)
  1107. XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
  1108. XA_BUG_ON(xa, xas.xa_index != i);
  1109. if (i == 0 || i == idx)
  1110. XA_BUG_ON(xa, entry != xa_mk_index(i));
  1111. else
  1112. XA_BUG_ON(xa, entry != NULL);
  1113. } while (i > 0);
  1114. xas_set(&xas, ULONG_MAX);
  1115. XA_BUG_ON(xa, xas_next(&xas) != NULL);
  1116. XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
  1117. XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));
  1118. XA_BUG_ON(xa, xas.xa_index != 0);
  1119. XA_BUG_ON(xa, xas_prev(&xas) != NULL);
  1120. XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
  1121. rcu_read_unlock();
  1122. xa_erase_index(xa, 0);
  1123. xa_erase_index(xa, idx);
  1124. XA_BUG_ON(xa, !xa_empty(xa));
  1125. }
  1126. static noinline void check_move(struct xarray *xa)
  1127. {
  1128. XA_STATE(xas, xa, (1 << 16) - 1);
  1129. unsigned long i;
  1130. for (i = 0; i < (1 << 16); i++)
  1131. XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
  1132. rcu_read_lock();
  1133. do {
  1134. void *entry = xas_prev(&xas);
  1135. i--;
  1136. XA_BUG_ON(xa, entry != xa_mk_index(i));
  1137. XA_BUG_ON(xa, i != xas.xa_index);
  1138. } while (i != 0);
  1139. XA_BUG_ON(xa, xas_prev(&xas) != NULL);
  1140. XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
  1141. do {
  1142. void *entry = xas_next(&xas);
  1143. XA_BUG_ON(xa, entry != xa_mk_index(i));
  1144. XA_BUG_ON(xa, i != xas.xa_index);
  1145. i++;
  1146. } while (i < (1 << 16));
  1147. rcu_read_unlock();
  1148. for (i = (1 << 8); i < (1 << 15); i++)
  1149. xa_erase_index(xa, i);
  1150. i = xas.xa_index;
  1151. rcu_read_lock();
  1152. do {
  1153. void *entry = xas_prev(&xas);
  1154. i--;
  1155. if ((i < (1 << 8)) || (i >= (1 << 15)))
  1156. XA_BUG_ON(xa, entry != xa_mk_index(i));
  1157. else
  1158. XA_BUG_ON(xa, entry != NULL);
  1159. XA_BUG_ON(xa, i != xas.xa_index);
  1160. } while (i != 0);
  1161. XA_BUG_ON(xa, xas_prev(&xas) != NULL);
  1162. XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
  1163. do {
  1164. void *entry = xas_next(&xas);
  1165. if ((i < (1 << 8)) || (i >= (1 << 15)))
  1166. XA_BUG_ON(xa, entry != xa_mk_index(i));
  1167. else
  1168. XA_BUG_ON(xa, entry != NULL);
  1169. XA_BUG_ON(xa, i != xas.xa_index);
  1170. i++;
  1171. } while (i < (1 << 16));
  1172. rcu_read_unlock();
  1173. xa_destroy(xa);
  1174. check_move_tiny(xa);
  1175. check_move_max(xa);
  1176. for (i = 0; i < 16; i++)
  1177. check_move_small(xa, 1UL << i);
  1178. for (i = 2; i < 16; i++)
  1179. check_move_small(xa, (1UL << i) - 1);
  1180. }
  1181. static noinline void xa_store_many_order(struct xarray *xa,
  1182. unsigned long index, unsigned order)
  1183. {
  1184. XA_STATE_ORDER(xas, xa, index, order);
  1185. unsigned int i = 0;
  1186. do {
  1187. xas_lock(&xas);
  1188. XA_BUG_ON(xa, xas_find_conflict(&xas));
  1189. xas_create_range(&xas);
  1190. if (xas_error(&xas))
  1191. goto unlock;
  1192. for (i = 0; i < (1U << order); i++) {
  1193. XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i)));
  1194. xas_next(&xas);
  1195. }
  1196. unlock:
  1197. xas_unlock(&xas);
  1198. } while (xas_nomem(&xas, GFP_KERNEL));
  1199. XA_BUG_ON(xa, xas_error(&xas));
  1200. }
  1201. static noinline void check_create_range_1(struct xarray *xa,
  1202. unsigned long index, unsigned order)
  1203. {
  1204. unsigned long i;
  1205. xa_store_many_order(xa, index, order);
  1206. for (i = index; i < index + (1UL << order); i++)
  1207. xa_erase_index(xa, i);
  1208. XA_BUG_ON(xa, !xa_empty(xa));
  1209. }
  1210. static noinline void check_create_range_2(struct xarray *xa, unsigned order)
  1211. {
  1212. unsigned long i;
  1213. unsigned long nr = 1UL << order;
  1214. for (i = 0; i < nr * nr; i += nr)
  1215. xa_store_many_order(xa, i, order);
  1216. for (i = 0; i < nr * nr; i++)
  1217. xa_erase_index(xa, i);
  1218. XA_BUG_ON(xa, !xa_empty(xa));
  1219. }
  1220. static noinline void check_create_range_3(void)
  1221. {
  1222. XA_STATE(xas, NULL, 0);
  1223. xas_set_err(&xas, -EEXIST);
  1224. xas_create_range(&xas);
  1225. XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);
  1226. }
  1227. static noinline void check_create_range_4(struct xarray *xa,
  1228. unsigned long index, unsigned order)
  1229. {
  1230. XA_STATE_ORDER(xas, xa, index, order);
  1231. unsigned long base = xas.xa_index;
  1232. unsigned long i = 0;
  1233. xa_store_index(xa, index, GFP_KERNEL);
  1234. do {
  1235. xas_lock(&xas);
  1236. xas_create_range(&xas);
  1237. if (xas_error(&xas))
  1238. goto unlock;
  1239. for (i = 0; i < (1UL << order); i++) {
  1240. void *old = xas_store(&xas, xa_mk_index(base + i));
  1241. if (xas.xa_index == index)
  1242. XA_BUG_ON(xa, old != xa_mk_index(base + i));
  1243. else
  1244. XA_BUG_ON(xa, old != NULL);
  1245. xas_next(&xas);
  1246. }
  1247. unlock:
  1248. xas_unlock(&xas);
  1249. } while (xas_nomem(&xas, GFP_KERNEL));
  1250. XA_BUG_ON(xa, xas_error(&xas));
  1251. for (i = base; i < base + (1UL << order); i++)
  1252. xa_erase_index(xa, i);
  1253. XA_BUG_ON(xa, !xa_empty(xa));
  1254. }
  1255. static noinline void check_create_range_5(struct xarray *xa,
  1256. unsigned long index, unsigned int order)
  1257. {
  1258. XA_STATE_ORDER(xas, xa, index, order);
  1259. unsigned int i;
  1260. xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
  1261. for (i = 0; i < order + 10; i++) {
  1262. do {
  1263. xas_lock(&xas);
  1264. xas_create_range(&xas);
  1265. xas_unlock(&xas);
  1266. } while (xas_nomem(&xas, GFP_KERNEL));
  1267. }
  1268. xa_destroy(xa);
  1269. }
  1270. static noinline void check_create_range(struct xarray *xa)
  1271. {
  1272. unsigned int order;
  1273. unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1;
  1274. for (order = 0; order < max_order; order++) {
  1275. check_create_range_1(xa, 0, order);
  1276. check_create_range_1(xa, 1U << order, order);
  1277. check_create_range_1(xa, 2U << order, order);
  1278. check_create_range_1(xa, 3U << order, order);
  1279. check_create_range_1(xa, 1U << 24, order);
  1280. if (order < 10)
  1281. check_create_range_2(xa, order);
  1282. check_create_range_4(xa, 0, order);
  1283. check_create_range_4(xa, 1U << order, order);
  1284. check_create_range_4(xa, 2U << order, order);
  1285. check_create_range_4(xa, 3U << order, order);
  1286. check_create_range_4(xa, 1U << 24, order);
  1287. check_create_range_4(xa, 1, order);
  1288. check_create_range_4(xa, (1U << order) + 1, order);
  1289. check_create_range_4(xa, (2U << order) + 1, order);
  1290. check_create_range_4(xa, (2U << order) - 1, order);
  1291. check_create_range_4(xa, (3U << order) + 1, order);
  1292. check_create_range_4(xa, (3U << order) - 1, order);
  1293. check_create_range_4(xa, (1U << 24) + 1, order);
  1294. check_create_range_5(xa, 0, order);
  1295. check_create_range_5(xa, (1U << order), order);
  1296. }
  1297. check_create_range_3();
  1298. }
  1299. static noinline void __check_store_range(struct xarray *xa, unsigned long first,
  1300. unsigned long last)
  1301. {
  1302. #ifdef CONFIG_XARRAY_MULTI
  1303. xa_store_range(xa, first, last, xa_mk_index(first), GFP_KERNEL);
  1304. XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_index(first));
  1305. XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_index(first));
  1306. XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL);
  1307. XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL);
  1308. xa_store_range(xa, first, last, NULL, GFP_KERNEL);
  1309. #endif
  1310. XA_BUG_ON(xa, !xa_empty(xa));
  1311. }
  1312. static noinline void check_store_range(struct xarray *xa)
  1313. {
  1314. unsigned long i, j;
  1315. for (i = 0; i < 128; i++) {
  1316. for (j = i; j < 128; j++) {
  1317. __check_store_range(xa, i, j);
  1318. __check_store_range(xa, 128 + i, 128 + j);
  1319. __check_store_range(xa, 4095 + i, 4095 + j);
  1320. __check_store_range(xa, 4096 + i, 4096 + j);
  1321. __check_store_range(xa, 123456 + i, 123456 + j);
  1322. __check_store_range(xa, (1 << 24) + i, (1 << 24) + j);
  1323. }
  1324. }
  1325. }
  1326. #ifdef CONFIG_XARRAY_MULTI
  1327. static void check_split_1(struct xarray *xa, unsigned long index,
  1328. unsigned int order, unsigned int new_order)
  1329. {
  1330. XA_STATE_ORDER(xas, xa, index, new_order);
  1331. unsigned int i;
  1332. xa_store_order(xa, index, order, xa, GFP_KERNEL);
  1333. xas_split_alloc(&xas, xa, order, GFP_KERNEL);
  1334. xas_lock(&xas);
  1335. xas_split(&xas, xa, order);
  1336. for (i = 0; i < (1 << order); i += (1 << new_order))
  1337. __xa_store(xa, index + i, xa_mk_index(index + i), 0);
  1338. xas_unlock(&xas);
  1339. for (i = 0; i < (1 << order); i++) {
  1340. unsigned int val = index + (i & ~((1 << new_order) - 1));
  1341. XA_BUG_ON(xa, xa_load(xa, index + i) != xa_mk_index(val));
  1342. }
  1343. xa_set_mark(xa, index, XA_MARK_0);
  1344. XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
  1345. xa_destroy(xa);
  1346. }
  1347. static noinline void check_split(struct xarray *xa)
  1348. {
  1349. unsigned int order, new_order;
  1350. XA_BUG_ON(xa, !xa_empty(xa));
  1351. for (order = 1; order < 2 * XA_CHUNK_SHIFT; order++) {
  1352. for (new_order = 0; new_order < order; new_order++) {
  1353. check_split_1(xa, 0, order, new_order);
  1354. check_split_1(xa, 1UL << order, order, new_order);
  1355. check_split_1(xa, 3UL << order, order, new_order);
  1356. }
  1357. }
  1358. }
  1359. #else
  1360. static void check_split(struct xarray *xa) { }
  1361. #endif
  1362. static void check_align_1(struct xarray *xa, char *name)
  1363. {
  1364. int i;
  1365. unsigned int id;
  1366. unsigned long index;
  1367. void *entry;
  1368. for (i = 0; i < 8; i++) {
  1369. XA_BUG_ON(xa, xa_alloc(xa, &id, name + i, xa_limit_32b,
  1370. GFP_KERNEL) != 0);
  1371. XA_BUG_ON(xa, id != i);
  1372. }
  1373. xa_for_each(xa, index, entry)
  1374. XA_BUG_ON(xa, xa_is_err(entry));
  1375. xa_destroy(xa);
  1376. }
  1377. /*
  1378. * We should always be able to store without allocating memory after
  1379. * reserving a slot.
  1380. */
  1381. static void check_align_2(struct xarray *xa, char *name)
  1382. {
  1383. int i;
  1384. XA_BUG_ON(xa, !xa_empty(xa));
  1385. for (i = 0; i < 8; i++) {
  1386. XA_BUG_ON(xa, xa_store(xa, 0, name + i, GFP_KERNEL) != NULL);
  1387. xa_erase(xa, 0);
  1388. }
  1389. for (i = 0; i < 8; i++) {
  1390. XA_BUG_ON(xa, xa_reserve(xa, 0, GFP_KERNEL) != 0);
  1391. XA_BUG_ON(xa, xa_store(xa, 0, name + i, 0) != NULL);
  1392. xa_erase(xa, 0);
  1393. }
  1394. XA_BUG_ON(xa, !xa_empty(xa));
  1395. }
  1396. static noinline void check_align(struct xarray *xa)
  1397. {
  1398. char name[] = "Motorola 68000";
  1399. check_align_1(xa, name);
  1400. check_align_1(xa, name + 1);
  1401. check_align_1(xa, name + 2);
  1402. check_align_1(xa, name + 3);
  1403. check_align_2(xa, name);
  1404. }
  1405. static LIST_HEAD(shadow_nodes);
  1406. static void test_update_node(struct xa_node *node)
  1407. {
  1408. if (node->count && node->count == node->nr_values) {
  1409. if (list_empty(&node->private_list))
  1410. list_add(&shadow_nodes, &node->private_list);
  1411. } else {
  1412. if (!list_empty(&node->private_list))
  1413. list_del_init(&node->private_list);
  1414. }
  1415. }
  1416. static noinline void shadow_remove(struct xarray *xa)
  1417. {
  1418. struct xa_node *node;
  1419. xa_lock(xa);
  1420. while ((node = list_first_entry_or_null(&shadow_nodes,
  1421. struct xa_node, private_list))) {
  1422. XA_BUG_ON(xa, node->array != xa);
  1423. list_del_init(&node->private_list);
  1424. xa_delete_node(node, test_update_node);
  1425. }
  1426. xa_unlock(xa);
  1427. }
  1428. static noinline void check_workingset(struct xarray *xa, unsigned long index)
  1429. {
  1430. XA_STATE(xas, xa, index);
  1431. xas_set_update(&xas, test_update_node);
  1432. do {
  1433. xas_lock(&xas);
  1434. xas_store(&xas, xa_mk_value(0));
  1435. xas_next(&xas);
  1436. xas_store(&xas, xa_mk_value(1));
  1437. xas_unlock(&xas);
  1438. } while (xas_nomem(&xas, GFP_KERNEL));
  1439. XA_BUG_ON(xa, list_empty(&shadow_nodes));
  1440. xas_lock(&xas);
  1441. xas_next(&xas);
  1442. xas_store(&xas, &xas);
  1443. XA_BUG_ON(xa, !list_empty(&shadow_nodes));
  1444. xas_store(&xas, xa_mk_value(2));
  1445. xas_unlock(&xas);
  1446. XA_BUG_ON(xa, list_empty(&shadow_nodes));
  1447. shadow_remove(xa);
  1448. XA_BUG_ON(xa, !list_empty(&shadow_nodes));
  1449. XA_BUG_ON(xa, !xa_empty(xa));
  1450. }
  1451. /*
  1452. * Check that the pointer / value / sibling entries are accounted the
  1453. * way we expect them to be.
  1454. */
  1455. static noinline void check_account(struct xarray *xa)
  1456. {
  1457. #ifdef CONFIG_XARRAY_MULTI
  1458. unsigned int order;
  1459. for (order = 1; order < 12; order++) {
  1460. XA_STATE(xas, xa, 1 << order);
  1461. xa_store_order(xa, 0, order, xa, GFP_KERNEL);
  1462. rcu_read_lock();
  1463. xas_load(&xas);
  1464. XA_BUG_ON(xa, xas.xa_node->count == 0);
  1465. XA_BUG_ON(xa, xas.xa_node->count > (1 << order));
  1466. XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
  1467. rcu_read_unlock();
  1468. xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order),
  1469. GFP_KERNEL);
  1470. XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2);
  1471. xa_erase(xa, 1 << order);
  1472. XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
  1473. xa_erase(xa, 0);
  1474. XA_BUG_ON(xa, !xa_empty(xa));
  1475. }
  1476. #endif
  1477. }
  1478. static noinline void check_get_order(struct xarray *xa)
  1479. {
  1480. unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
  1481. unsigned int order;
  1482. unsigned long i, j;
  1483. for (i = 0; i < 3; i++)
  1484. XA_BUG_ON(xa, xa_get_order(xa, i) != 0);
  1485. for (order = 0; order < max_order; order++) {
  1486. for (i = 0; i < 10; i++) {
  1487. xa_store_order(xa, i << order, order,
  1488. xa_mk_index(i << order), GFP_KERNEL);
  1489. for (j = i << order; j < (i + 1) << order; j++)
  1490. XA_BUG_ON(xa, xa_get_order(xa, j) != order);
  1491. xa_erase(xa, i << order);
  1492. }
  1493. }
  1494. }
  1495. static noinline void check_destroy(struct xarray *xa)
  1496. {
  1497. unsigned long index;
  1498. XA_BUG_ON(xa, !xa_empty(xa));
  1499. /* Destroying an empty array is a no-op */
  1500. xa_destroy(xa);
  1501. XA_BUG_ON(xa, !xa_empty(xa));
  1502. /* Destroying an array with a single entry */
  1503. for (index = 0; index < 1000; index++) {
  1504. xa_store_index(xa, index, GFP_KERNEL);
  1505. XA_BUG_ON(xa, xa_empty(xa));
  1506. xa_destroy(xa);
  1507. XA_BUG_ON(xa, !xa_empty(xa));
  1508. }
  1509. /* Destroying an array with a single entry at ULONG_MAX */
  1510. xa_store(xa, ULONG_MAX, xa, GFP_KERNEL);
  1511. XA_BUG_ON(xa, xa_empty(xa));
  1512. xa_destroy(xa);
  1513. XA_BUG_ON(xa, !xa_empty(xa));
  1514. #ifdef CONFIG_XARRAY_MULTI
  1515. /* Destroying an array with a multi-index entry */
  1516. xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL);
  1517. XA_BUG_ON(xa, xa_empty(xa));
  1518. xa_destroy(xa);
  1519. XA_BUG_ON(xa, !xa_empty(xa));
  1520. #endif
  1521. }
  1522. static DEFINE_XARRAY(array);
  1523. static int xarray_checks(void)
  1524. {
  1525. check_xa_err(&array);
  1526. check_xas_retry(&array);
  1527. check_xa_load(&array);
  1528. check_xa_mark(&array);
  1529. check_xa_shrink(&array);
  1530. check_xas_erase(&array);
  1531. check_insert(&array);
  1532. check_cmpxchg(&array);
  1533. check_reserve(&array);
  1534. check_reserve(&xa0);
  1535. check_multi_store(&array);
  1536. check_get_order(&array);
  1537. check_xa_alloc();
  1538. check_find(&array);
  1539. check_find_entry(&array);
  1540. check_pause(&array);
  1541. check_account(&array);
  1542. check_destroy(&array);
  1543. check_move(&array);
  1544. check_create_range(&array);
  1545. check_store_range(&array);
  1546. check_store_iter(&array);
  1547. check_align(&xa0);
  1548. check_split(&array);
  1549. check_workingset(&array, 0);
  1550. check_workingset(&array, 64);
  1551. check_workingset(&array, 4096);
  1552. printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);
  1553. return (tests_run == tests_passed) ? 0 : -EINVAL;
  1554. }
  1555. static void xarray_exit(void)
  1556. {
  1557. }
  1558. module_init(xarray_checks);
  1559. module_exit(xarray_exit);
  1560. MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
  1561. MODULE_LICENSE("GPL");