assoc_array.c 52 KB

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