assoc_array.c 53 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746
  1. /* Generic associative array implementation.
  2. *
  3. * See Documentation/assoc_array.txt for information.
  4. *
  5. * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
  6. * Written by David Howells (dhowells@redhat.com)
  7. *
  8. * This program is free software; you can redistribute it and/or
  9. * modify it under the terms of the GNU General Public Licence
  10. * as published by the Free Software Foundation; either version
  11. * 2 of the Licence, or (at your option) any later version.
  12. */
  13. //#define DEBUG
  14. #include <linux/slab.h>
  15. #include <linux/err.h>
  16. #include <linux/assoc_array_priv.h>
  17. /*
  18. * Iterate over an associative array. The caller must hold the RCU read lock
  19. * or better.
  20. */
  21. static int assoc_array_subtree_iterate(const struct assoc_array_ptr *root,
  22. const struct assoc_array_ptr *stop,
  23. int (*iterator)(const void *leaf,
  24. void *iterator_data),
  25. void *iterator_data)
  26. {
  27. const struct assoc_array_shortcut *shortcut;
  28. const struct assoc_array_node *node;
  29. const struct assoc_array_ptr *cursor, *ptr, *parent;
  30. unsigned long has_meta;
  31. int slot, ret;
  32. cursor = root;
  33. begin_node:
  34. if (assoc_array_ptr_is_shortcut(cursor)) {
  35. /* Descend through a shortcut */
  36. shortcut = assoc_array_ptr_to_shortcut(cursor);
  37. smp_read_barrier_depends();
  38. cursor = ACCESS_ONCE(shortcut->next_node);
  39. }
  40. node = assoc_array_ptr_to_node(cursor);
  41. smp_read_barrier_depends();
  42. slot = 0;
  43. /* We perform two passes of each node.
  44. *
  45. * The first pass does all the leaves in this node. This means we
  46. * don't miss any leaves if the node is split up by insertion whilst
  47. * we're iterating over the branches rooted here (we may, however, see
  48. * some leaves twice).
  49. */
  50. has_meta = 0;
  51. for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
  52. ptr = ACCESS_ONCE(node->slots[slot]);
  53. has_meta |= (unsigned long)ptr;
  54. if (ptr && assoc_array_ptr_is_leaf(ptr)) {
  55. /* We need a barrier between the read of the pointer
  56. * and dereferencing the pointer - but only if we are
  57. * actually going to dereference it.
  58. */
  59. smp_read_barrier_depends();
  60. /* Invoke the callback */
  61. ret = iterator(assoc_array_ptr_to_leaf(ptr),
  62. iterator_data);
  63. if (ret)
  64. return ret;
  65. }
  66. }
  67. /* The second pass attends to all the metadata pointers. If we follow
  68. * one of these we may find that we don't come back here, but rather go
  69. * back to a replacement node with the leaves in a different layout.
  70. *
  71. * We are guaranteed to make progress, however, as the slot number for
  72. * a particular portion of the key space cannot change - and we
  73. * continue at the back pointer + 1.
  74. */
  75. if (!(has_meta & ASSOC_ARRAY_PTR_META_TYPE))
  76. goto finished_node;
  77. slot = 0;
  78. continue_node:
  79. node = assoc_array_ptr_to_node(cursor);
  80. smp_read_barrier_depends();
  81. for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
  82. ptr = ACCESS_ONCE(node->slots[slot]);
  83. if (assoc_array_ptr_is_meta(ptr)) {
  84. cursor = ptr;
  85. goto begin_node;
  86. }
  87. }
  88. finished_node:
  89. /* Move up to the parent (may need to skip back over a shortcut) */
  90. parent = ACCESS_ONCE(node->back_pointer);
  91. slot = node->parent_slot;
  92. if (parent == stop)
  93. return 0;
  94. if (assoc_array_ptr_is_shortcut(parent)) {
  95. shortcut = assoc_array_ptr_to_shortcut(parent);
  96. smp_read_barrier_depends();
  97. cursor = parent;
  98. parent = ACCESS_ONCE(shortcut->back_pointer);
  99. slot = shortcut->parent_slot;
  100. if (parent == stop)
  101. return 0;
  102. }
  103. /* Ascend to next slot in parent node */
  104. cursor = parent;
  105. slot++;
  106. goto continue_node;
  107. }
  108. /**
  109. * assoc_array_iterate - Pass all objects in the array to a callback
  110. * @array: The array to iterate over.
  111. * @iterator: The callback function.
  112. * @iterator_data: Private data for the callback function.
  113. *
  114. * Iterate over all the objects in an associative array. Each one will be
  115. * presented to the iterator function.
  116. *
  117. * If the array is being modified concurrently with the iteration then it is
  118. * possible that some objects in the array will be passed to the iterator
  119. * callback more than once - though every object should be passed at least
  120. * once. If this is undesirable then the caller must lock against modification
  121. * for the duration of this function.
  122. *
  123. * The function will return 0 if no objects were in the array or else it will
  124. * return the result of the last iterator function called. Iteration stops
  125. * immediately if any call to the iteration function results in a non-zero
  126. * return.
  127. *
  128. * The caller should hold the RCU read lock or better if concurrent
  129. * modification is possible.
  130. */
  131. int assoc_array_iterate(const struct assoc_array *array,
  132. int (*iterator)(const void *object,
  133. void *iterator_data),
  134. void *iterator_data)
  135. {
  136. struct assoc_array_ptr *root = ACCESS_ONCE(array->root);
  137. if (!root)
  138. return 0;
  139. return assoc_array_subtree_iterate(root, NULL, iterator, iterator_data);
  140. }
  141. enum assoc_array_walk_status {
  142. assoc_array_walk_tree_empty,
  143. assoc_array_walk_found_terminal_node,
  144. assoc_array_walk_found_wrong_shortcut,
  145. } status;
  146. struct assoc_array_walk_result {
  147. struct {
  148. struct assoc_array_node *node; /* Node in which leaf might be found */
  149. int level;
  150. int slot;
  151. } terminal_node;
  152. struct {
  153. struct assoc_array_shortcut *shortcut;
  154. int level;
  155. int sc_level;
  156. unsigned long sc_segments;
  157. unsigned long dissimilarity;
  158. } wrong_shortcut;
  159. };
  160. /*
  161. * Navigate through the internal tree looking for the closest node to the key.
  162. */
  163. static enum assoc_array_walk_status
  164. assoc_array_walk(const struct assoc_array *array,
  165. const struct assoc_array_ops *ops,
  166. const void *index_key,
  167. struct assoc_array_walk_result *result)
  168. {
  169. struct assoc_array_shortcut *shortcut;
  170. struct assoc_array_node *node;
  171. struct assoc_array_ptr *cursor, *ptr;
  172. unsigned long sc_segments, dissimilarity;
  173. unsigned long segments;
  174. int level, sc_level, next_sc_level;
  175. int slot;
  176. pr_devel("-->%s()\n", __func__);
  177. cursor = ACCESS_ONCE(array->root);
  178. if (!cursor)
  179. return assoc_array_walk_tree_empty;
  180. level = 0;
  181. /* Use segments from the key for the new leaf to navigate through the
  182. * internal tree, skipping through nodes and shortcuts that are on
  183. * route to the destination. Eventually we'll come to a slot that is
  184. * either empty or contains a leaf at which point we've found a node in
  185. * which the leaf we're looking for might be found or into which it
  186. * should be inserted.
  187. */
  188. jumped:
  189. segments = ops->get_key_chunk(index_key, level);
  190. pr_devel("segments[%d]: %lx\n", level, segments);
  191. if (assoc_array_ptr_is_shortcut(cursor))
  192. goto follow_shortcut;
  193. consider_node:
  194. node = assoc_array_ptr_to_node(cursor);
  195. smp_read_barrier_depends();
  196. slot = segments >> (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
  197. slot &= ASSOC_ARRAY_FAN_MASK;
  198. ptr = ACCESS_ONCE(node->slots[slot]);
  199. pr_devel("consider slot %x [ix=%d type=%lu]\n",
  200. slot, level, (unsigned long)ptr & 3);
  201. if (!assoc_array_ptr_is_meta(ptr)) {
  202. /* The node doesn't have a node/shortcut pointer in the slot
  203. * corresponding to the index key that we have to follow.
  204. */
  205. result->terminal_node.node = node;
  206. result->terminal_node.level = level;
  207. result->terminal_node.slot = slot;
  208. pr_devel("<--%s() = terminal_node\n", __func__);
  209. return assoc_array_walk_found_terminal_node;
  210. }
  211. if (assoc_array_ptr_is_node(ptr)) {
  212. /* There is a pointer to a node in the slot corresponding to
  213. * this index key segment, so we need to follow it.
  214. */
  215. cursor = ptr;
  216. level += ASSOC_ARRAY_LEVEL_STEP;
  217. if ((level & ASSOC_ARRAY_KEY_CHUNK_MASK) != 0)
  218. goto consider_node;
  219. goto jumped;
  220. }
  221. /* There is a shortcut in the slot corresponding to the index key
  222. * segment. We follow the shortcut if its partial index key matches
  223. * this leaf's. Otherwise we need to split the shortcut.
  224. */
  225. cursor = ptr;
  226. follow_shortcut:
  227. shortcut = assoc_array_ptr_to_shortcut(cursor);
  228. smp_read_barrier_depends();
  229. pr_devel("shortcut to %d\n", shortcut->skip_to_level);
  230. sc_level = level + ASSOC_ARRAY_LEVEL_STEP;
  231. BUG_ON(sc_level > shortcut->skip_to_level);
  232. do {
  233. /* Check the leaf against the shortcut's index key a word at a
  234. * time, trimming the final word (the shortcut stores the index
  235. * key completely from the root to the shortcut's target).
  236. */
  237. if ((sc_level & ASSOC_ARRAY_KEY_CHUNK_MASK) == 0)
  238. segments = ops->get_key_chunk(index_key, sc_level);
  239. sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
  240. dissimilarity = segments ^ sc_segments;
  241. if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) {
  242. /* Trim segments that are beyond the shortcut */
  243. int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
  244. dissimilarity &= ~(ULONG_MAX << shift);
  245. next_sc_level = shortcut->skip_to_level;
  246. } else {
  247. next_sc_level = sc_level + ASSOC_ARRAY_KEY_CHUNK_SIZE;
  248. next_sc_level = round_down(next_sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
  249. }
  250. if (dissimilarity != 0) {
  251. /* This shortcut points elsewhere */
  252. result->wrong_shortcut.shortcut = shortcut;
  253. result->wrong_shortcut.level = level;
  254. result->wrong_shortcut.sc_level = sc_level;
  255. result->wrong_shortcut.sc_segments = sc_segments;
  256. result->wrong_shortcut.dissimilarity = dissimilarity;
  257. return assoc_array_walk_found_wrong_shortcut;
  258. }
  259. sc_level = next_sc_level;
  260. } while (sc_level < shortcut->skip_to_level);
  261. /* The shortcut matches the leaf's index to this point. */
  262. cursor = ACCESS_ONCE(shortcut->next_node);
  263. if (((level ^ sc_level) & ~ASSOC_ARRAY_KEY_CHUNK_MASK) != 0) {
  264. level = sc_level;
  265. goto jumped;
  266. } else {
  267. level = sc_level;
  268. goto consider_node;
  269. }
  270. }
  271. /**
  272. * assoc_array_find - Find an object by index key
  273. * @array: The associative array to search.
  274. * @ops: The operations to use.
  275. * @index_key: The key to the object.
  276. *
  277. * Find an object in an associative array by walking through the internal tree
  278. * to the node that should contain the object and then searching the leaves
  279. * there. NULL is returned if the requested object was not found in the array.
  280. *
  281. * The caller must hold the RCU read lock or better.
  282. */
  283. void *assoc_array_find(const struct assoc_array *array,
  284. const struct assoc_array_ops *ops,
  285. const void *index_key)
  286. {
  287. struct assoc_array_walk_result result;
  288. const struct assoc_array_node *node;
  289. const struct assoc_array_ptr *ptr;
  290. const void *leaf;
  291. int slot;
  292. if (assoc_array_walk(array, ops, index_key, &result) !=
  293. assoc_array_walk_found_terminal_node)
  294. return NULL;
  295. node = result.terminal_node.node;
  296. smp_read_barrier_depends();
  297. /* If the target key is available to us, it's has to be pointed to by
  298. * the terminal node.
  299. */
  300. for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
  301. ptr = ACCESS_ONCE(node->slots[slot]);
  302. if (ptr && assoc_array_ptr_is_leaf(ptr)) {
  303. /* We need a barrier between the read of the pointer
  304. * and dereferencing the pointer - but only if we are
  305. * actually going to dereference it.
  306. */
  307. leaf = assoc_array_ptr_to_leaf(ptr);
  308. smp_read_barrier_depends();
  309. if (ops->compare_object(leaf, index_key))
  310. return (void *)leaf;
  311. }
  312. }
  313. return NULL;
  314. }
  315. /*
  316. * Destructively iterate over an associative array. The caller must prevent
  317. * other simultaneous accesses.
  318. */
  319. static void assoc_array_destroy_subtree(struct assoc_array_ptr *root,
  320. const struct assoc_array_ops *ops)
  321. {
  322. struct assoc_array_shortcut *shortcut;
  323. struct assoc_array_node *node;
  324. struct assoc_array_ptr *cursor, *parent = NULL;
  325. int slot = -1;
  326. pr_devel("-->%s()\n", __func__);
  327. cursor = root;
  328. if (!cursor) {
  329. pr_devel("empty\n");
  330. return;
  331. }
  332. move_to_meta:
  333. if (assoc_array_ptr_is_shortcut(cursor)) {
  334. /* Descend through a shortcut */
  335. pr_devel("[%d] shortcut\n", slot);
  336. BUG_ON(!assoc_array_ptr_is_shortcut(cursor));
  337. shortcut = assoc_array_ptr_to_shortcut(cursor);
  338. BUG_ON(shortcut->back_pointer != parent);
  339. BUG_ON(slot != -1 && shortcut->parent_slot != slot);
  340. parent = cursor;
  341. cursor = shortcut->next_node;
  342. slot = -1;
  343. BUG_ON(!assoc_array_ptr_is_node(cursor));
  344. }
  345. pr_devel("[%d] node\n", slot);
  346. node = assoc_array_ptr_to_node(cursor);
  347. BUG_ON(node->back_pointer != parent);
  348. BUG_ON(slot != -1 && node->parent_slot != slot);
  349. slot = 0;
  350. continue_node:
  351. pr_devel("Node %p [back=%p]\n", node, node->back_pointer);
  352. for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
  353. struct assoc_array_ptr *ptr = node->slots[slot];
  354. if (!ptr)
  355. continue;
  356. if (assoc_array_ptr_is_meta(ptr)) {
  357. parent = cursor;
  358. cursor = ptr;
  359. goto move_to_meta;
  360. }
  361. if (ops) {
  362. pr_devel("[%d] free leaf\n", slot);
  363. ops->free_object(assoc_array_ptr_to_leaf(ptr));
  364. }
  365. }
  366. parent = node->back_pointer;
  367. slot = node->parent_slot;
  368. pr_devel("free node\n");
  369. kfree(node);
  370. if (!parent)
  371. return; /* Done */
  372. /* Move back up to the parent (may need to free a shortcut on
  373. * the way up) */
  374. if (assoc_array_ptr_is_shortcut(parent)) {
  375. shortcut = assoc_array_ptr_to_shortcut(parent);
  376. BUG_ON(shortcut->next_node != cursor);
  377. cursor = parent;
  378. parent = shortcut->back_pointer;
  379. slot = shortcut->parent_slot;
  380. pr_devel("free shortcut\n");
  381. kfree(shortcut);
  382. if (!parent)
  383. return;
  384. BUG_ON(!assoc_array_ptr_is_node(parent));
  385. }
  386. /* Ascend to next slot in parent node */
  387. pr_devel("ascend to %p[%d]\n", parent, slot);
  388. cursor = parent;
  389. node = assoc_array_ptr_to_node(cursor);
  390. slot++;
  391. goto continue_node;
  392. }
  393. /**
  394. * assoc_array_destroy - Destroy an associative array
  395. * @array: The array to destroy.
  396. * @ops: The operations to use.
  397. *
  398. * Discard all metadata and free all objects in an associative array. The
  399. * array will be empty and ready to use again upon completion. This function
  400. * cannot fail.
  401. *
  402. * The caller must prevent all other accesses whilst this takes place as no
  403. * attempt is made to adjust pointers gracefully to permit RCU readlock-holding
  404. * accesses to continue. On the other hand, no memory allocation is required.
  405. */
  406. void assoc_array_destroy(struct assoc_array *array,
  407. const struct assoc_array_ops *ops)
  408. {
  409. assoc_array_destroy_subtree(array->root, ops);
  410. array->root = NULL;
  411. }
  412. /*
  413. * Handle insertion into an empty tree.
  414. */
  415. static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit)
  416. {
  417. struct assoc_array_node *new_n0;
  418. pr_devel("-->%s()\n", __func__);
  419. new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
  420. if (!new_n0)
  421. return false;
  422. edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
  423. edit->leaf_p = &new_n0->slots[0];
  424. edit->adjust_count_on = new_n0;
  425. edit->set[0].ptr = &edit->array->root;
  426. edit->set[0].to = assoc_array_node_to_ptr(new_n0);
  427. pr_devel("<--%s() = ok [no root]\n", __func__);
  428. return true;
  429. }
  430. /*
  431. * Handle insertion into a terminal node.
  432. */
  433. static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
  434. const struct assoc_array_ops *ops,
  435. const void *index_key,
  436. struct assoc_array_walk_result *result)
  437. {
  438. struct assoc_array_shortcut *shortcut, *new_s0;
  439. struct assoc_array_node *node, *new_n0, *new_n1, *side;
  440. struct assoc_array_ptr *ptr;
  441. unsigned long dissimilarity, base_seg, blank;
  442. size_t keylen;
  443. bool have_meta;
  444. int level, diff;
  445. int slot, next_slot, free_slot, i, j;
  446. node = result->terminal_node.node;
  447. level = result->terminal_node.level;
  448. edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot;
  449. pr_devel("-->%s()\n", __func__);
  450. /* We arrived at a node which doesn't have an onward node or shortcut
  451. * pointer that we have to follow. This means that (a) the leaf we
  452. * want must go here (either by insertion or replacement) or (b) we
  453. * need to split this node and insert in one of the fragments.
  454. */
  455. free_slot = -1;
  456. /* Firstly, we have to check the leaves in this node to see if there's
  457. * a matching one we should replace in place.
  458. */
  459. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
  460. ptr = node->slots[i];
  461. if (!ptr) {
  462. free_slot = i;
  463. continue;
  464. }
  465. if (ops->compare_object(assoc_array_ptr_to_leaf(ptr), index_key)) {
  466. pr_devel("replace in slot %d\n", i);
  467. edit->leaf_p = &node->slots[i];
  468. edit->dead_leaf = node->slots[i];
  469. pr_devel("<--%s() = ok [replace]\n", __func__);
  470. return true;
  471. }
  472. }
  473. /* If there is a free slot in this node then we can just insert the
  474. * leaf here.
  475. */
  476. if (free_slot >= 0) {
  477. pr_devel("insert in free slot %d\n", free_slot);
  478. edit->leaf_p = &node->slots[free_slot];
  479. edit->adjust_count_on = node;
  480. pr_devel("<--%s() = ok [insert]\n", __func__);
  481. return true;
  482. }
  483. /* The node has no spare slots - so we're either going to have to split
  484. * it or insert another node before it.
  485. *
  486. * Whatever, we're going to need at least two new nodes - so allocate
  487. * those now. We may also need a new shortcut, but we deal with that
  488. * when we need it.
  489. */
  490. new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
  491. if (!new_n0)
  492. return false;
  493. edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
  494. new_n1 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
  495. if (!new_n1)
  496. return false;
  497. edit->new_meta[1] = assoc_array_node_to_ptr(new_n1);
  498. /* We need to find out how similar the leaves are. */
  499. pr_devel("no spare slots\n");
  500. have_meta = false;
  501. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
  502. ptr = node->slots[i];
  503. if (assoc_array_ptr_is_meta(ptr)) {
  504. edit->segment_cache[i] = 0xff;
  505. have_meta = true;
  506. continue;
  507. }
  508. base_seg = ops->get_object_key_chunk(
  509. assoc_array_ptr_to_leaf(ptr), level);
  510. base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
  511. edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
  512. }
  513. if (have_meta) {
  514. pr_devel("have meta\n");
  515. goto split_node;
  516. }
  517. /* The node contains only leaves */
  518. dissimilarity = 0;
  519. base_seg = edit->segment_cache[0];
  520. for (i = 1; i < ASSOC_ARRAY_FAN_OUT; i++)
  521. dissimilarity |= edit->segment_cache[i] ^ base_seg;
  522. pr_devel("only leaves; dissimilarity=%lx\n", dissimilarity);
  523. if ((dissimilarity & ASSOC_ARRAY_FAN_MASK) == 0) {
  524. /* The old leaves all cluster in the same slot. We will need
  525. * to insert a shortcut if the new node wants to cluster with them.
  526. */
  527. if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)
  528. goto all_leaves_cluster_together;
  529. /* Otherwise we can just insert a new node ahead of the old
  530. * one.
  531. */
  532. goto present_leaves_cluster_but_not_new_leaf;
  533. }
  534. split_node:
  535. pr_devel("split node\n");
  536. /* We need to split the current node; we know that the node doesn't
  537. * simply contain a full set of leaves that cluster together (it
  538. * contains meta pointers and/or non-clustering leaves).
  539. *
  540. * We need to expel at least two leaves out of a set consisting of the
  541. * leaves in the node and the new leaf.
  542. *
  543. * We need a new node (n0) to replace the current one and a new node to
  544. * take the expelled nodes (n1).
  545. */
  546. edit->set[0].to = assoc_array_node_to_ptr(new_n0);
  547. new_n0->back_pointer = node->back_pointer;
  548. new_n0->parent_slot = node->parent_slot;
  549. new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
  550. new_n1->parent_slot = -1; /* Need to calculate this */
  551. do_split_node:
  552. pr_devel("do_split_node\n");
  553. new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
  554. new_n1->nr_leaves_on_branch = 0;
  555. /* Begin by finding two matching leaves. There have to be at least two
  556. * that match - even if there are meta pointers - because any leaf that
  557. * would match a slot with a meta pointer in it must be somewhere
  558. * behind that meta pointer and cannot be here. Further, given N
  559. * remaining leaf slots, we now have N+1 leaves to go in them.
  560. */
  561. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
  562. slot = edit->segment_cache[i];
  563. if (slot != 0xff)
  564. for (j = i + 1; j < ASSOC_ARRAY_FAN_OUT + 1; j++)
  565. if (edit->segment_cache[j] == slot)
  566. goto found_slot_for_multiple_occupancy;
  567. }
  568. found_slot_for_multiple_occupancy:
  569. pr_devel("same slot: %x %x [%02x]\n", i, j, slot);
  570. BUG_ON(i >= ASSOC_ARRAY_FAN_OUT);
  571. BUG_ON(j >= ASSOC_ARRAY_FAN_OUT + 1);
  572. BUG_ON(slot >= ASSOC_ARRAY_FAN_OUT);
  573. new_n1->parent_slot = slot;
  574. /* Metadata pointers cannot change slot */
  575. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
  576. if (assoc_array_ptr_is_meta(node->slots[i]))
  577. new_n0->slots[i] = node->slots[i];
  578. else
  579. new_n0->slots[i] = NULL;
  580. BUG_ON(new_n0->slots[slot] != NULL);
  581. new_n0->slots[slot] = assoc_array_node_to_ptr(new_n1);
  582. /* Filter the leaf pointers between the new nodes */
  583. free_slot = -1;
  584. next_slot = 0;
  585. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
  586. if (assoc_array_ptr_is_meta(node->slots[i]))
  587. continue;
  588. if (edit->segment_cache[i] == slot) {
  589. new_n1->slots[next_slot++] = node->slots[i];
  590. new_n1->nr_leaves_on_branch++;
  591. } else {
  592. do {
  593. free_slot++;
  594. } while (new_n0->slots[free_slot] != NULL);
  595. new_n0->slots[free_slot] = node->slots[i];
  596. }
  597. }
  598. pr_devel("filtered: f=%x n=%x\n", free_slot, next_slot);
  599. if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {
  600. do {
  601. free_slot++;
  602. } while (new_n0->slots[free_slot] != NULL);
  603. edit->leaf_p = &new_n0->slots[free_slot];
  604. edit->adjust_count_on = new_n0;
  605. } else {
  606. edit->leaf_p = &new_n1->slots[next_slot++];
  607. edit->adjust_count_on = new_n1;
  608. }
  609. BUG_ON(next_slot <= 1);
  610. edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);
  611. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
  612. if (edit->segment_cache[i] == 0xff) {
  613. ptr = node->slots[i];
  614. BUG_ON(assoc_array_ptr_is_leaf(ptr));
  615. if (assoc_array_ptr_is_node(ptr)) {
  616. side = assoc_array_ptr_to_node(ptr);
  617. edit->set_backpointers[i] = &side->back_pointer;
  618. } else {
  619. shortcut = assoc_array_ptr_to_shortcut(ptr);
  620. edit->set_backpointers[i] = &shortcut->back_pointer;
  621. }
  622. }
  623. }
  624. ptr = node->back_pointer;
  625. if (!ptr)
  626. edit->set[0].ptr = &edit->array->root;
  627. else if (assoc_array_ptr_is_node(ptr))
  628. edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];
  629. else
  630. edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node;
  631. edit->excised_meta[0] = assoc_array_node_to_ptr(node);
  632. pr_devel("<--%s() = ok [split node]\n", __func__);
  633. return true;
  634. present_leaves_cluster_but_not_new_leaf:
  635. /* All the old leaves cluster in the same slot, but the new leaf wants
  636. * to go into a different slot, so we create a new node to hold the new
  637. * leaf and a pointer to a new node holding all the old leaves.
  638. */
  639. pr_devel("present leaves cluster but not new leaf\n");
  640. new_n0->back_pointer = node->back_pointer;
  641. new_n0->parent_slot = node->parent_slot;
  642. new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
  643. new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
  644. new_n1->parent_slot = edit->segment_cache[0];
  645. new_n1->nr_leaves_on_branch = node->nr_leaves_on_branch;
  646. edit->adjust_count_on = new_n0;
  647. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
  648. new_n1->slots[i] = node->slots[i];
  649. new_n0->slots[edit->segment_cache[0]] = assoc_array_node_to_ptr(new_n0);
  650. edit->leaf_p = &new_n0->slots[edit->segment_cache[ASSOC_ARRAY_FAN_OUT]];
  651. edit->set[0].ptr = &assoc_array_ptr_to_node(node->back_pointer)->slots[node->parent_slot];
  652. edit->set[0].to = assoc_array_node_to_ptr(new_n0);
  653. edit->excised_meta[0] = assoc_array_node_to_ptr(node);
  654. pr_devel("<--%s() = ok [insert node before]\n", __func__);
  655. return true;
  656. all_leaves_cluster_together:
  657. /* All the leaves, new and old, want to cluster together in this node
  658. * in the same slot, so we have to replace this node with a shortcut to
  659. * skip over the identical parts of the key and then place a pair of
  660. * nodes, one inside the other, at the end of the shortcut and
  661. * distribute the keys between them.
  662. *
  663. * Firstly we need to work out where the leaves start diverging as a
  664. * bit position into their keys so that we know how big the shortcut
  665. * needs to be.
  666. *
  667. * We only need to make a single pass of N of the N+1 leaves because if
  668. * any keys differ between themselves at bit X then at least one of
  669. * them must also differ with the base key at bit X or before.
  670. */
  671. pr_devel("all leaves cluster together\n");
  672. diff = INT_MAX;
  673. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
  674. int x = ops->diff_objects(assoc_array_ptr_to_leaf(edit->leaf),
  675. assoc_array_ptr_to_leaf(node->slots[i]));
  676. if (x < diff) {
  677. BUG_ON(x < 0);
  678. diff = x;
  679. }
  680. }
  681. BUG_ON(diff == INT_MAX);
  682. BUG_ON(diff < level + ASSOC_ARRAY_LEVEL_STEP);
  683. keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
  684. keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
  685. new_s0 = kzalloc(sizeof(struct assoc_array_shortcut) +
  686. keylen * sizeof(unsigned long), GFP_KERNEL);
  687. if (!new_s0)
  688. return false;
  689. edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);
  690. edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
  691. new_s0->back_pointer = node->back_pointer;
  692. new_s0->parent_slot = node->parent_slot;
  693. new_s0->next_node = assoc_array_node_to_ptr(new_n0);
  694. new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
  695. new_n0->parent_slot = 0;
  696. new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
  697. new_n1->parent_slot = -1; /* Need to calculate this */
  698. new_s0->skip_to_level = level = diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK;
  699. pr_devel("skip_to_level = %d [diff %d]\n", level, diff);
  700. BUG_ON(level <= 0);
  701. for (i = 0; i < keylen; i++)
  702. new_s0->index_key[i] =
  703. ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE);
  704. blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
  705. pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank);
  706. new_s0->index_key[keylen - 1] &= ~blank;
  707. /* This now reduces to a node splitting exercise for which we'll need
  708. * to regenerate the disparity table.
  709. */
  710. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
  711. ptr = node->slots[i];
  712. base_seg = ops->get_object_key_chunk(assoc_array_ptr_to_leaf(ptr),
  713. level);
  714. base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
  715. edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
  716. }
  717. base_seg = ops->get_key_chunk(index_key, level);
  718. base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
  719. edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;
  720. goto do_split_node;
  721. }
  722. /*
  723. * Handle insertion into the middle of a shortcut.
  724. */
  725. static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
  726. const struct assoc_array_ops *ops,
  727. struct assoc_array_walk_result *result)
  728. {
  729. struct assoc_array_shortcut *shortcut, *new_s0, *new_s1;
  730. struct assoc_array_node *node, *new_n0, *side;
  731. unsigned long sc_segments, dissimilarity, blank;
  732. size_t keylen;
  733. int level, sc_level, diff;
  734. int sc_slot;
  735. shortcut = result->wrong_shortcut.shortcut;
  736. level = result->wrong_shortcut.level;
  737. sc_level = result->wrong_shortcut.sc_level;
  738. sc_segments = result->wrong_shortcut.sc_segments;
  739. dissimilarity = result->wrong_shortcut.dissimilarity;
  740. pr_devel("-->%s(ix=%d dis=%lx scix=%d)\n",
  741. __func__, level, dissimilarity, sc_level);
  742. /* We need to split a shortcut and insert a node between the two
  743. * pieces. Zero-length pieces will be dispensed with entirely.
  744. *
  745. * First of all, we need to find out in which level the first
  746. * difference was.
  747. */
  748. diff = __ffs(dissimilarity);
  749. diff &= ~ASSOC_ARRAY_LEVEL_STEP_MASK;
  750. diff += sc_level & ~ASSOC_ARRAY_KEY_CHUNK_MASK;
  751. pr_devel("diff=%d\n", diff);
  752. if (!shortcut->back_pointer) {
  753. edit->set[0].ptr = &edit->array->root;
  754. } else if (assoc_array_ptr_is_node(shortcut->back_pointer)) {
  755. node = assoc_array_ptr_to_node(shortcut->back_pointer);
  756. edit->set[0].ptr = &node->slots[shortcut->parent_slot];
  757. } else {
  758. BUG();
  759. }
  760. edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);
  761. /* Create a new node now since we're going to need it anyway */
  762. new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
  763. if (!new_n0)
  764. return false;
  765. edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
  766. edit->adjust_count_on = new_n0;
  767. /* Insert a new shortcut before the new node if this segment isn't of
  768. * zero length - otherwise we just connect the new node directly to the
  769. * parent.
  770. */
  771. level += ASSOC_ARRAY_LEVEL_STEP;
  772. if (diff > level) {
  773. pr_devel("pre-shortcut %d...%d\n", level, diff);
  774. keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
  775. keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
  776. new_s0 = kzalloc(sizeof(struct assoc_array_shortcut) +
  777. keylen * sizeof(unsigned long), GFP_KERNEL);
  778. if (!new_s0)
  779. return false;
  780. edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);
  781. edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
  782. new_s0->back_pointer = shortcut->back_pointer;
  783. new_s0->parent_slot = shortcut->parent_slot;
  784. new_s0->next_node = assoc_array_node_to_ptr(new_n0);
  785. new_s0->skip_to_level = diff;
  786. new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
  787. new_n0->parent_slot = 0;
  788. memcpy(new_s0->index_key, shortcut->index_key,
  789. keylen * sizeof(unsigned long));
  790. blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
  791. pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);
  792. new_s0->index_key[keylen - 1] &= ~blank;
  793. } else {
  794. pr_devel("no pre-shortcut\n");
  795. edit->set[0].to = assoc_array_node_to_ptr(new_n0);
  796. new_n0->back_pointer = shortcut->back_pointer;
  797. new_n0->parent_slot = shortcut->parent_slot;
  798. }
  799. side = assoc_array_ptr_to_node(shortcut->next_node);
  800. new_n0->nr_leaves_on_branch = side->nr_leaves_on_branch;
  801. /* We need to know which slot in the new node is going to take a
  802. * metadata pointer.
  803. */
  804. sc_slot = sc_segments >> (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
  805. sc_slot &= ASSOC_ARRAY_FAN_MASK;
  806. pr_devel("new slot %lx >> %d -> %d\n",
  807. sc_segments, diff & ASSOC_ARRAY_KEY_CHUNK_MASK, sc_slot);
  808. /* Determine whether we need to follow the new node with a replacement
  809. * for the current shortcut. We could in theory reuse the current
  810. * shortcut if its parent slot number doesn't change - but that's a
  811. * 1-in-16 chance so not worth expending the code upon.
  812. */
  813. level = diff + ASSOC_ARRAY_LEVEL_STEP;
  814. if (level < shortcut->skip_to_level) {
  815. pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level);
  816. keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
  817. keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
  818. new_s1 = kzalloc(sizeof(struct assoc_array_shortcut) +
  819. keylen * sizeof(unsigned long), GFP_KERNEL);
  820. if (!new_s1)
  821. return false;
  822. edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);
  823. new_s1->back_pointer = assoc_array_node_to_ptr(new_n0);
  824. new_s1->parent_slot = sc_slot;
  825. new_s1->next_node = shortcut->next_node;
  826. new_s1->skip_to_level = shortcut->skip_to_level;
  827. new_n0->slots[sc_slot] = assoc_array_shortcut_to_ptr(new_s1);
  828. memcpy(new_s1->index_key, shortcut->index_key,
  829. keylen * sizeof(unsigned long));
  830. edit->set[1].ptr = &side->back_pointer;
  831. edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);
  832. } else {
  833. pr_devel("no post-shortcut\n");
  834. /* We don't have to replace the pointed-to node as long as we
  835. * use memory barriers to make sure the parent slot number is
  836. * changed before the back pointer (the parent slot number is
  837. * irrelevant to the old parent shortcut).
  838. */
  839. new_n0->slots[sc_slot] = shortcut->next_node;
  840. edit->set_parent_slot[0].p = &side->parent_slot;
  841. edit->set_parent_slot[0].to = sc_slot;
  842. edit->set[1].ptr = &side->back_pointer;
  843. edit->set[1].to = assoc_array_node_to_ptr(new_n0);
  844. }
  845. /* Install the new leaf in a spare slot in the new node. */
  846. if (sc_slot == 0)
  847. edit->leaf_p = &new_n0->slots[1];
  848. else
  849. edit->leaf_p = &new_n0->slots[0];
  850. pr_devel("<--%s() = ok [split shortcut]\n", __func__);
  851. return edit;
  852. }
  853. /**
  854. * assoc_array_insert - Script insertion of an object into an associative array
  855. * @array: The array to insert into.
  856. * @ops: The operations to use.
  857. * @index_key: The key to insert at.
  858. * @object: The object to insert.
  859. *
  860. * Precalculate and preallocate a script for the insertion or replacement of an
  861. * object in an associative array. This results in an edit script that can
  862. * either be applied or cancelled.
  863. *
  864. * The function returns a pointer to an edit script or -ENOMEM.
  865. *
  866. * The caller should lock against other modifications and must continue to hold
  867. * the lock until assoc_array_apply_edit() has been called.
  868. *
  869. * Accesses to the tree may take place concurrently with this function,
  870. * provided they hold the RCU read lock.
  871. */
  872. struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
  873. const struct assoc_array_ops *ops,
  874. const void *index_key,
  875. void *object)
  876. {
  877. struct assoc_array_walk_result result;
  878. struct assoc_array_edit *edit;
  879. pr_devel("-->%s()\n", __func__);
  880. /* The leaf pointer we're given must not have the bottom bit set as we
  881. * use those for type-marking the pointer. NULL pointers are also not
  882. * allowed as they indicate an empty slot but we have to allow them
  883. * here as they can be updated later.
  884. */
  885. BUG_ON(assoc_array_ptr_is_meta(object));
  886. edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
  887. if (!edit)
  888. return ERR_PTR(-ENOMEM);
  889. edit->array = array;
  890. edit->ops = ops;
  891. edit->leaf = assoc_array_leaf_to_ptr(object);
  892. edit->adjust_count_by = 1;
  893. switch (assoc_array_walk(array, ops, index_key, &result)) {
  894. case assoc_array_walk_tree_empty:
  895. /* Allocate a root node if there isn't one yet */
  896. if (!assoc_array_insert_in_empty_tree(edit))
  897. goto enomem;
  898. return edit;
  899. case assoc_array_walk_found_terminal_node:
  900. /* We found a node that doesn't have a node/shortcut pointer in
  901. * the slot corresponding to the index key that we have to
  902. * follow.
  903. */
  904. if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,
  905. &result))
  906. goto enomem;
  907. return edit;
  908. case assoc_array_walk_found_wrong_shortcut:
  909. /* We found a shortcut that didn't match our key in a slot we
  910. * needed to follow.
  911. */
  912. if (!assoc_array_insert_mid_shortcut(edit, ops, &result))
  913. goto enomem;
  914. return edit;
  915. }
  916. enomem:
  917. /* Clean up after an out of memory error */
  918. pr_devel("enomem\n");
  919. assoc_array_cancel_edit(edit);
  920. return ERR_PTR(-ENOMEM);
  921. }
  922. /**
  923. * assoc_array_insert_set_object - Set the new object pointer in an edit script
  924. * @edit: The edit script to modify.
  925. * @object: The object pointer to set.
  926. *
  927. * Change the object to be inserted in an edit script. The object pointed to
  928. * by the old object is not freed. This must be done prior to applying the
  929. * script.
  930. */
  931. void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)
  932. {
  933. BUG_ON(!object);
  934. edit->leaf = assoc_array_leaf_to_ptr(object);
  935. }
  936. struct assoc_array_delete_collapse_context {
  937. struct assoc_array_node *node;
  938. const void *skip_leaf;
  939. int slot;
  940. };
  941. /*
  942. * Subtree collapse to node iterator.
  943. */
  944. static int assoc_array_delete_collapse_iterator(const void *leaf,
  945. void *iterator_data)
  946. {
  947. struct assoc_array_delete_collapse_context *collapse = iterator_data;
  948. if (leaf == collapse->skip_leaf)
  949. return 0;
  950. BUG_ON(collapse->slot >= ASSOC_ARRAY_FAN_OUT);
  951. collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf);
  952. return 0;
  953. }
  954. /**
  955. * assoc_array_delete - Script deletion of an object from an associative array
  956. * @array: The array to search.
  957. * @ops: The operations to use.
  958. * @index_key: The key to the object.
  959. *
  960. * Precalculate and preallocate a script for the deletion of an object from an
  961. * associative array. This results in an edit script that can either be
  962. * applied or cancelled.
  963. *
  964. * The function returns a pointer to an edit script if the object was found,
  965. * NULL if the object was not found or -ENOMEM.
  966. *
  967. * The caller should lock against other modifications and must continue to hold
  968. * the lock until assoc_array_apply_edit() has been called.
  969. *
  970. * Accesses to the tree may take place concurrently with this function,
  971. * provided they hold the RCU read lock.
  972. */
  973. struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
  974. const struct assoc_array_ops *ops,
  975. const void *index_key)
  976. {
  977. struct assoc_array_delete_collapse_context collapse;
  978. struct assoc_array_walk_result result;
  979. struct assoc_array_node *node, *new_n0;
  980. struct assoc_array_edit *edit;
  981. struct assoc_array_ptr *ptr;
  982. bool has_meta;
  983. int slot, i;
  984. pr_devel("-->%s()\n", __func__);
  985. edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
  986. if (!edit)
  987. return ERR_PTR(-ENOMEM);
  988. edit->array = array;
  989. edit->ops = ops;
  990. edit->adjust_count_by = -1;
  991. switch (assoc_array_walk(array, ops, index_key, &result)) {
  992. case assoc_array_walk_found_terminal_node:
  993. /* We found a node that should contain the leaf we've been
  994. * asked to remove - *if* it's in the tree.
  995. */
  996. pr_devel("terminal_node\n");
  997. node = result.terminal_node.node;
  998. for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
  999. ptr = node->slots[slot];
  1000. if (ptr &&
  1001. assoc_array_ptr_is_leaf(ptr) &&
  1002. ops->compare_object(assoc_array_ptr_to_leaf(ptr),
  1003. index_key))
  1004. goto found_leaf;
  1005. }
  1006. case assoc_array_walk_tree_empty:
  1007. case assoc_array_walk_found_wrong_shortcut:
  1008. default:
  1009. assoc_array_cancel_edit(edit);
  1010. pr_devel("not found\n");
  1011. return NULL;
  1012. }
  1013. found_leaf:
  1014. BUG_ON(array->nr_leaves_on_tree <= 0);
  1015. /* In the simplest form of deletion we just clear the slot and release
  1016. * the leaf after a suitable interval.
  1017. */
  1018. edit->dead_leaf = node->slots[slot];
  1019. edit->set[0].ptr = &node->slots[slot];
  1020. edit->set[0].to = NULL;
  1021. edit->adjust_count_on = node;
  1022. /* If that concludes erasure of the last leaf, then delete the entire
  1023. * internal array.
  1024. */
  1025. if (array->nr_leaves_on_tree == 1) {
  1026. edit->set[1].ptr = &array->root;
  1027. edit->set[1].to = NULL;
  1028. edit->adjust_count_on = NULL;
  1029. edit->excised_subtree = array->root;
  1030. pr_devel("all gone\n");
  1031. return edit;
  1032. }
  1033. /* However, we'd also like to clear up some metadata blocks if we
  1034. * possibly can.
  1035. *
  1036. * We go for a simple algorithm of: if this node has FAN_OUT or fewer
  1037. * leaves in it, then attempt to collapse it - and attempt to
  1038. * recursively collapse up the tree.
  1039. *
  1040. * We could also try and collapse in partially filled subtrees to take
  1041. * up space in this node.
  1042. */
  1043. if (node->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
  1044. struct assoc_array_node *parent, *grandparent;
  1045. struct assoc_array_ptr *ptr;
  1046. /* First of all, we need to know if this node has metadata so
  1047. * that we don't try collapsing if all the leaves are already
  1048. * here.
  1049. */
  1050. has_meta = false;
  1051. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
  1052. ptr = node->slots[i];
  1053. if (assoc_array_ptr_is_meta(ptr)) {
  1054. has_meta = true;
  1055. break;
  1056. }
  1057. }
  1058. pr_devel("leaves: %ld [m=%d]\n",
  1059. node->nr_leaves_on_branch - 1, has_meta);
  1060. /* Look further up the tree to see if we can collapse this node
  1061. * into a more proximal node too.
  1062. */
  1063. parent = node;
  1064. collapse_up:
  1065. pr_devel("collapse subtree: %ld\n", parent->nr_leaves_on_branch);
  1066. ptr = parent->back_pointer;
  1067. if (!ptr)
  1068. goto do_collapse;
  1069. if (assoc_array_ptr_is_shortcut(ptr)) {
  1070. struct assoc_array_shortcut *s = assoc_array_ptr_to_shortcut(ptr);
  1071. ptr = s->back_pointer;
  1072. if (!ptr)
  1073. goto do_collapse;
  1074. }
  1075. grandparent = assoc_array_ptr_to_node(ptr);
  1076. if (grandparent->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
  1077. parent = grandparent;
  1078. goto collapse_up;
  1079. }
  1080. do_collapse:
  1081. /* There's no point collapsing if the original node has no meta
  1082. * pointers to discard and if we didn't merge into one of that
  1083. * node's ancestry.
  1084. */
  1085. if (has_meta || parent != node) {
  1086. node = parent;
  1087. /* Create a new node to collapse into */
  1088. new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
  1089. if (!new_n0)
  1090. goto enomem;
  1091. edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
  1092. new_n0->back_pointer = node->back_pointer;
  1093. new_n0->parent_slot = node->parent_slot;
  1094. new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
  1095. edit->adjust_count_on = new_n0;
  1096. collapse.node = new_n0;
  1097. collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);
  1098. collapse.slot = 0;
  1099. assoc_array_subtree_iterate(assoc_array_node_to_ptr(node),
  1100. node->back_pointer,
  1101. assoc_array_delete_collapse_iterator,
  1102. &collapse);
  1103. pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch);
  1104. BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1);
  1105. if (!node->back_pointer) {
  1106. edit->set[1].ptr = &array->root;
  1107. } else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
  1108. BUG();
  1109. } else if (assoc_array_ptr_is_node(node->back_pointer)) {
  1110. struct assoc_array_node *p =
  1111. assoc_array_ptr_to_node(node->back_pointer);
  1112. edit->set[1].ptr = &p->slots[node->parent_slot];
  1113. } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) {
  1114. struct assoc_array_shortcut *s =
  1115. assoc_array_ptr_to_shortcut(node->back_pointer);
  1116. edit->set[1].ptr = &s->next_node;
  1117. }
  1118. edit->set[1].to = assoc_array_node_to_ptr(new_n0);
  1119. edit->excised_subtree = assoc_array_node_to_ptr(node);
  1120. }
  1121. }
  1122. return edit;
  1123. enomem:
  1124. /* Clean up after an out of memory error */
  1125. pr_devel("enomem\n");
  1126. assoc_array_cancel_edit(edit);
  1127. return ERR_PTR(-ENOMEM);
  1128. }
  1129. /**
  1130. * assoc_array_clear - Script deletion of all objects from an associative array
  1131. * @array: The array to clear.
  1132. * @ops: The operations to use.
  1133. *
  1134. * Precalculate and preallocate a script for the deletion of all the objects
  1135. * from an associative array. This results in an edit script that can either
  1136. * be applied or cancelled.
  1137. *
  1138. * The function returns a pointer to an edit script if there are objects to be
  1139. * deleted, NULL if there are no objects in the array or -ENOMEM.
  1140. *
  1141. * The caller should lock against other modifications and must continue to hold
  1142. * the lock until assoc_array_apply_edit() has been called.
  1143. *
  1144. * Accesses to the tree may take place concurrently with this function,
  1145. * provided they hold the RCU read lock.
  1146. */
  1147. struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
  1148. const struct assoc_array_ops *ops)
  1149. {
  1150. struct assoc_array_edit *edit;
  1151. pr_devel("-->%s()\n", __func__);
  1152. if (!array->root)
  1153. return NULL;
  1154. edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
  1155. if (!edit)
  1156. return ERR_PTR(-ENOMEM);
  1157. edit->array = array;
  1158. edit->ops = ops;
  1159. edit->set[1].ptr = &array->root;
  1160. edit->set[1].to = NULL;
  1161. edit->excised_subtree = array->root;
  1162. edit->ops_for_excised_subtree = ops;
  1163. pr_devel("all gone\n");
  1164. return edit;
  1165. }
  1166. /*
  1167. * Handle the deferred destruction after an applied edit.
  1168. */
  1169. static void assoc_array_rcu_cleanup(struct rcu_head *head)
  1170. {
  1171. struct assoc_array_edit *edit =
  1172. container_of(head, struct assoc_array_edit, rcu);
  1173. int i;
  1174. pr_devel("-->%s()\n", __func__);
  1175. if (edit->dead_leaf)
  1176. edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));
  1177. for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)
  1178. if (edit->excised_meta[i])
  1179. kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));
  1180. if (edit->excised_subtree) {
  1181. BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));
  1182. if (assoc_array_ptr_is_node(edit->excised_subtree)) {
  1183. struct assoc_array_node *n =
  1184. assoc_array_ptr_to_node(edit->excised_subtree);
  1185. n->back_pointer = NULL;
  1186. } else {
  1187. struct assoc_array_shortcut *s =
  1188. assoc_array_ptr_to_shortcut(edit->excised_subtree);
  1189. s->back_pointer = NULL;
  1190. }
  1191. assoc_array_destroy_subtree(edit->excised_subtree,
  1192. edit->ops_for_excised_subtree);
  1193. }
  1194. kfree(edit);
  1195. }
  1196. /**
  1197. * assoc_array_apply_edit - Apply an edit script to an associative array
  1198. * @edit: The script to apply.
  1199. *
  1200. * Apply an edit script to an associative array to effect an insertion,
  1201. * deletion or clearance. As the edit script includes preallocated memory,
  1202. * this is guaranteed not to fail.
  1203. *
  1204. * The edit script, dead objects and dead metadata will be scheduled for
  1205. * destruction after an RCU grace period to permit those doing read-only
  1206. * accesses on the array to continue to do so under the RCU read lock whilst
  1207. * the edit is taking place.
  1208. */
  1209. void assoc_array_apply_edit(struct assoc_array_edit *edit)
  1210. {
  1211. struct assoc_array_shortcut *shortcut;
  1212. struct assoc_array_node *node;
  1213. struct assoc_array_ptr *ptr;
  1214. int i;
  1215. pr_devel("-->%s()\n", __func__);
  1216. smp_wmb();
  1217. if (edit->leaf_p)
  1218. *edit->leaf_p = edit->leaf;
  1219. smp_wmb();
  1220. for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)
  1221. if (edit->set_parent_slot[i].p)
  1222. *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;
  1223. smp_wmb();
  1224. for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)
  1225. if (edit->set_backpointers[i])
  1226. *edit->set_backpointers[i] = edit->set_backpointers_to;
  1227. smp_wmb();
  1228. for (i = 0; i < ARRAY_SIZE(edit->set); i++)
  1229. if (edit->set[i].ptr)
  1230. *edit->set[i].ptr = edit->set[i].to;
  1231. if (edit->array->root == NULL) {
  1232. edit->array->nr_leaves_on_tree = 0;
  1233. } else if (edit->adjust_count_on) {
  1234. node = edit->adjust_count_on;
  1235. for (;;) {
  1236. node->nr_leaves_on_branch += edit->adjust_count_by;
  1237. ptr = node->back_pointer;
  1238. if (!ptr)
  1239. break;
  1240. if (assoc_array_ptr_is_shortcut(ptr)) {
  1241. shortcut = assoc_array_ptr_to_shortcut(ptr);
  1242. ptr = shortcut->back_pointer;
  1243. if (!ptr)
  1244. break;
  1245. }
  1246. BUG_ON(!assoc_array_ptr_is_node(ptr));
  1247. node = assoc_array_ptr_to_node(ptr);
  1248. }
  1249. edit->array->nr_leaves_on_tree += edit->adjust_count_by;
  1250. }
  1251. call_rcu(&edit->rcu, assoc_array_rcu_cleanup);
  1252. }
  1253. /**
  1254. * assoc_array_cancel_edit - Discard an edit script.
  1255. * @edit: The script to discard.
  1256. *
  1257. * Free an edit script and all the preallocated data it holds without making
  1258. * any changes to the associative array it was intended for.
  1259. *
  1260. * NOTE! In the case of an insertion script, this does _not_ release the leaf
  1261. * that was to be inserted. That is left to the caller.
  1262. */
  1263. void assoc_array_cancel_edit(struct assoc_array_edit *edit)
  1264. {
  1265. struct assoc_array_ptr *ptr;
  1266. int i;
  1267. pr_devel("-->%s()\n", __func__);
  1268. /* Clean up after an out of memory error */
  1269. for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {
  1270. ptr = edit->new_meta[i];
  1271. if (ptr) {
  1272. if (assoc_array_ptr_is_node(ptr))
  1273. kfree(assoc_array_ptr_to_node(ptr));
  1274. else
  1275. kfree(assoc_array_ptr_to_shortcut(ptr));
  1276. }
  1277. }
  1278. kfree(edit);
  1279. }
  1280. /**
  1281. * assoc_array_gc - Garbage collect an associative array.
  1282. * @array: The array to clean.
  1283. * @ops: The operations to use.
  1284. * @iterator: A callback function to pass judgement on each object.
  1285. * @iterator_data: Private data for the callback function.
  1286. *
  1287. * Collect garbage from an associative array and pack down the internal tree to
  1288. * save memory.
  1289. *
  1290. * The iterator function is asked to pass judgement upon each object in the
  1291. * array. If it returns false, the object is discard and if it returns true,
  1292. * the object is kept. If it returns true, it must increment the object's
  1293. * usage count (or whatever it needs to do to retain it) before returning.
  1294. *
  1295. * This function returns 0 if successful or -ENOMEM if out of memory. In the
  1296. * latter case, the array is not changed.
  1297. *
  1298. * The caller should lock against other modifications and must continue to hold
  1299. * the lock until assoc_array_apply_edit() has been called.
  1300. *
  1301. * Accesses to the tree may take place concurrently with this function,
  1302. * provided they hold the RCU read lock.
  1303. */
  1304. int assoc_array_gc(struct assoc_array *array,
  1305. const struct assoc_array_ops *ops,
  1306. bool (*iterator)(void *object, void *iterator_data),
  1307. void *iterator_data)
  1308. {
  1309. struct assoc_array_shortcut *shortcut, *new_s;
  1310. struct assoc_array_node *node, *new_n;
  1311. struct assoc_array_edit *edit;
  1312. struct assoc_array_ptr *cursor, *ptr;
  1313. struct assoc_array_ptr *new_root, *new_parent, **new_ptr_pp;
  1314. unsigned long nr_leaves_on_tree;
  1315. int keylen, slot, nr_free, next_slot, i;
  1316. pr_devel("-->%s()\n", __func__);
  1317. if (!array->root)
  1318. return 0;
  1319. edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
  1320. if (!edit)
  1321. return -ENOMEM;
  1322. edit->array = array;
  1323. edit->ops = ops;
  1324. edit->ops_for_excised_subtree = ops;
  1325. edit->set[0].ptr = &array->root;
  1326. edit->excised_subtree = array->root;
  1327. new_root = new_parent = NULL;
  1328. new_ptr_pp = &new_root;
  1329. cursor = array->root;
  1330. descend:
  1331. /* If this point is a shortcut, then we need to duplicate it and
  1332. * advance the target cursor.
  1333. */
  1334. if (assoc_array_ptr_is_shortcut(cursor)) {
  1335. shortcut = assoc_array_ptr_to_shortcut(cursor);
  1336. keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
  1337. keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
  1338. new_s = kmalloc(sizeof(struct assoc_array_shortcut) +
  1339. keylen * sizeof(unsigned long), GFP_KERNEL);
  1340. if (!new_s)
  1341. goto enomem;
  1342. pr_devel("dup shortcut %p -> %p\n", shortcut, new_s);
  1343. memcpy(new_s, shortcut, (sizeof(struct assoc_array_shortcut) +
  1344. keylen * sizeof(unsigned long)));
  1345. new_s->back_pointer = new_parent;
  1346. new_s->parent_slot = shortcut->parent_slot;
  1347. *new_ptr_pp = new_parent = assoc_array_shortcut_to_ptr(new_s);
  1348. new_ptr_pp = &new_s->next_node;
  1349. cursor = shortcut->next_node;
  1350. }
  1351. /* Duplicate the node at this position */
  1352. node = assoc_array_ptr_to_node(cursor);
  1353. new_n = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
  1354. if (!new_n)
  1355. goto enomem;
  1356. pr_devel("dup node %p -> %p\n", node, new_n);
  1357. new_n->back_pointer = new_parent;
  1358. new_n->parent_slot = node->parent_slot;
  1359. *new_ptr_pp = new_parent = assoc_array_node_to_ptr(new_n);
  1360. new_ptr_pp = NULL;
  1361. slot = 0;
  1362. continue_node:
  1363. /* Filter across any leaves and gc any subtrees */
  1364. for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
  1365. ptr = node->slots[slot];
  1366. if (!ptr)
  1367. continue;
  1368. if (assoc_array_ptr_is_leaf(ptr)) {
  1369. if (iterator(assoc_array_ptr_to_leaf(ptr),
  1370. iterator_data))
  1371. /* The iterator will have done any reference
  1372. * counting on the object for us.
  1373. */
  1374. new_n->slots[slot] = ptr;
  1375. continue;
  1376. }
  1377. new_ptr_pp = &new_n->slots[slot];
  1378. cursor = ptr;
  1379. goto descend;
  1380. }
  1381. pr_devel("-- compress node %p --\n", new_n);
  1382. /* Count up the number of empty slots in this node and work out the
  1383. * subtree leaf count.
  1384. */
  1385. new_n->nr_leaves_on_branch = 0;
  1386. nr_free = 0;
  1387. for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
  1388. ptr = new_n->slots[slot];
  1389. if (!ptr)
  1390. nr_free++;
  1391. else if (assoc_array_ptr_is_leaf(ptr))
  1392. new_n->nr_leaves_on_branch++;
  1393. }
  1394. pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch);
  1395. /* See what we can fold in */
  1396. next_slot = 0;
  1397. for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
  1398. struct assoc_array_shortcut *s;
  1399. struct assoc_array_node *child;
  1400. ptr = new_n->slots[slot];
  1401. if (!ptr || assoc_array_ptr_is_leaf(ptr))
  1402. continue;
  1403. s = NULL;
  1404. if (assoc_array_ptr_is_shortcut(ptr)) {
  1405. s = assoc_array_ptr_to_shortcut(ptr);
  1406. ptr = s->next_node;
  1407. }
  1408. child = assoc_array_ptr_to_node(ptr);
  1409. new_n->nr_leaves_on_branch += child->nr_leaves_on_branch;
  1410. if (child->nr_leaves_on_branch <= nr_free + 1) {
  1411. /* Fold the child node into this one */
  1412. pr_devel("[%d] fold node %lu/%d [nx %d]\n",
  1413. slot, child->nr_leaves_on_branch, nr_free + 1,
  1414. next_slot);
  1415. /* We would already have reaped an intervening shortcut
  1416. * on the way back up the tree.
  1417. */
  1418. BUG_ON(s);
  1419. new_n->slots[slot] = NULL;
  1420. nr_free++;
  1421. if (slot < next_slot)
  1422. next_slot = slot;
  1423. for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
  1424. struct assoc_array_ptr *p = child->slots[i];
  1425. if (!p)
  1426. continue;
  1427. BUG_ON(assoc_array_ptr_is_meta(p));
  1428. while (new_n->slots[next_slot])
  1429. next_slot++;
  1430. BUG_ON(next_slot >= ASSOC_ARRAY_FAN_OUT);
  1431. new_n->slots[next_slot++] = p;
  1432. nr_free--;
  1433. }
  1434. kfree(child);
  1435. } else {
  1436. pr_devel("[%d] retain node %lu/%d [nx %d]\n",
  1437. slot, child->nr_leaves_on_branch, nr_free + 1,
  1438. next_slot);
  1439. }
  1440. }
  1441. pr_devel("after: %lu\n", new_n->nr_leaves_on_branch);
  1442. nr_leaves_on_tree = new_n->nr_leaves_on_branch;
  1443. /* Excise this node if it is singly occupied by a shortcut */
  1444. if (nr_free == ASSOC_ARRAY_FAN_OUT - 1) {
  1445. for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++)
  1446. if ((ptr = new_n->slots[slot]))
  1447. break;
  1448. if (assoc_array_ptr_is_meta(ptr) &&
  1449. assoc_array_ptr_is_shortcut(ptr)) {
  1450. pr_devel("excise node %p with 1 shortcut\n", new_n);
  1451. new_s = assoc_array_ptr_to_shortcut(ptr);
  1452. new_parent = new_n->back_pointer;
  1453. slot = new_n->parent_slot;
  1454. kfree(new_n);
  1455. if (!new_parent) {
  1456. new_s->back_pointer = NULL;
  1457. new_s->parent_slot = 0;
  1458. new_root = ptr;
  1459. goto gc_complete;
  1460. }
  1461. if (assoc_array_ptr_is_shortcut(new_parent)) {
  1462. /* We can discard any preceding shortcut also */
  1463. struct assoc_array_shortcut *s =
  1464. assoc_array_ptr_to_shortcut(new_parent);
  1465. pr_devel("excise preceding shortcut\n");
  1466. new_parent = new_s->back_pointer = s->back_pointer;
  1467. slot = new_s->parent_slot = s->parent_slot;
  1468. kfree(s);
  1469. if (!new_parent) {
  1470. new_s->back_pointer = NULL;
  1471. new_s->parent_slot = 0;
  1472. new_root = ptr;
  1473. goto gc_complete;
  1474. }
  1475. }
  1476. new_s->back_pointer = new_parent;
  1477. new_s->parent_slot = slot;
  1478. new_n = assoc_array_ptr_to_node(new_parent);
  1479. new_n->slots[slot] = ptr;
  1480. goto ascend_old_tree;
  1481. }
  1482. }
  1483. /* Excise any shortcuts we might encounter that point to nodes that
  1484. * only contain leaves.
  1485. */
  1486. ptr = new_n->back_pointer;
  1487. if (!ptr)
  1488. goto gc_complete;
  1489. if (assoc_array_ptr_is_shortcut(ptr)) {
  1490. new_s = assoc_array_ptr_to_shortcut(ptr);
  1491. new_parent = new_s->back_pointer;
  1492. slot = new_s->parent_slot;
  1493. if (new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
  1494. struct assoc_array_node *n;
  1495. pr_devel("excise shortcut\n");
  1496. new_n->back_pointer = new_parent;
  1497. new_n->parent_slot = slot;
  1498. kfree(new_s);
  1499. if (!new_parent) {
  1500. new_root = assoc_array_node_to_ptr(new_n);
  1501. goto gc_complete;
  1502. }
  1503. n = assoc_array_ptr_to_node(new_parent);
  1504. n->slots[slot] = assoc_array_node_to_ptr(new_n);
  1505. }
  1506. } else {
  1507. new_parent = ptr;
  1508. }
  1509. new_n = assoc_array_ptr_to_node(new_parent);
  1510. ascend_old_tree:
  1511. ptr = node->back_pointer;
  1512. if (assoc_array_ptr_is_shortcut(ptr)) {
  1513. shortcut = assoc_array_ptr_to_shortcut(ptr);
  1514. slot = shortcut->parent_slot;
  1515. cursor = shortcut->back_pointer;
  1516. } else {
  1517. slot = node->parent_slot;
  1518. cursor = ptr;
  1519. }
  1520. BUG_ON(!ptr);
  1521. node = assoc_array_ptr_to_node(cursor);
  1522. slot++;
  1523. goto continue_node;
  1524. gc_complete:
  1525. edit->set[0].to = new_root;
  1526. assoc_array_apply_edit(edit);
  1527. edit->array->nr_leaves_on_tree = nr_leaves_on_tree;
  1528. return 0;
  1529. enomem:
  1530. pr_devel("enomem\n");
  1531. assoc_array_destroy_subtree(new_root, edit->ops);
  1532. kfree(edit);
  1533. return -ENOMEM;
  1534. }