projects/linux·blob assoc-array-fixes · refs

1884 lines · 56.8 KiB

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 ([email protected])
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/*
16 * Iterate over an associative array. The caller must hold the RCU read lock
17 * or better.
18 */
19static int assoc_array_subtree_iterate(const struct assoc_array_ptr *root,
20 const struct assoc_array_ptr *stop,
21 int (*iterator)(const void *leaf,
22 void *iterator_data),
23 void *iterator_data)
24{
25 const struct assoc_array_shortcut *shortcut;
26 const struct assoc_array_node *node;
27 const struct assoc_array_ptr *cursor, *ptr, *parent;
28 unsigned long has_meta;
29 int slot, ret;
30
31 cursor = root;
32
33begin_node:
34 if (assoc_array_ptr_is_shortcut(cursor)) {
35 /* Descend through a shortcut */
36 shortcut = assoc_array_ptr_to_shortcut(cursor);
37 cursor = READ_ONCE(shortcut->next_node); /* Address dependency. */
38 }
39
40 node = assoc_array_ptr_to_node(cursor);
41 slot = 0;
42
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 = READ_ONCE(node->slots[slot]); /* Address dependency. */
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 * which is supplied by the above READ_ONCE().
57 */
58 /* Invoke the callback */
59 ret = iterator(assoc_array_ptr_to_leaf(ptr),
60 iterator_data);
61 if (ret)
62 return ret;
63 }
64 }
65
66 /* The second pass attends to all the metadata pointers. If we follow
67 * one of these we may find that we don't come back here, but rather go
68 * back to a replacement node with the leaves in a different layout.
69 *
70 * We are guaranteed to make progress, however, as the slot number for
71 * a particular portion of the key space cannot change - and we
72 * continue at the back pointer + 1.
73 */
74 if (!(has_meta & ASSOC_ARRAY_PTR_META_TYPE))
75 goto finished_node;
76 slot = 0;
77
78continue_node:
79 node = assoc_array_ptr_to_node(cursor);
80 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
81 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
82 if (assoc_array_ptr_is_meta(ptr)) {
83 cursor = ptr;
84 goto begin_node;
85 }
86 }
87
88finished_node:
89 /* Move up to the parent (may need to skip back over a shortcut) */
90 parent = READ_ONCE(node->back_pointer); /* Address dependency. */
91 slot = node->parent_slot;
92 if (parent == stop)
93 return 0;
94
95 if (assoc_array_ptr_is_shortcut(parent)) {
96 shortcut = assoc_array_ptr_to_shortcut(parent);
97 cursor = parent;
98 parent = READ_ONCE(shortcut->back_pointer); /* Address dependency. */
99 slot = shortcut->parent_slot;
100 if (parent == stop)
101 return 0;
102 }
103
104 /* Ascend to next slot in parent node */
105 cursor = parent;
106 slot++;
107 goto continue_node;
108}
109
110/**
111 * assoc_array_iterate - Pass all objects in the array to a callback
112 * @array: The array to iterate over.
113 * @iterator: The callback function.
114 * @iterator_data: Private data for the callback function.
115 *
116 * Iterate over all the objects in an associative array. Each one will be
117 * presented to the iterator function.
118 *
119 * If the array is being modified concurrently with the iteration then it is
120 * possible that some objects in the array will be passed to the iterator
121 * callback more than once - though every object should be passed at least
122 * once. If this is undesirable then the caller must lock against modification
123 * for the duration of this function.
124 *
125 * The function will return 0 if no objects were in the array or else it will
126 * return the result of the last iterator function called. Iteration stops
127 * immediately if any call to the iteration function results in a non-zero
128 * return.
129 *
130 * The caller should hold the RCU read lock or better if concurrent
131 * modification is possible.
132 */
133int assoc_array_iterate(const struct assoc_array *array,
134 int (*iterator)(const void *object,
135 void *iterator_data),
136 void *iterator_data)
137{
138 struct assoc_array_ptr *root = READ_ONCE(array->root); /* Address dependency. */
139
140 if (!root)
141 return 0;
142 return assoc_array_subtree_iterate(root, NULL, iterator, iterator_data);
143}
144
145enum assoc_array_walk_status {
146 assoc_array_walk_tree_empty,
147 assoc_array_walk_found_terminal_node,
148 assoc_array_walk_found_wrong_shortcut,
149};
150
151struct assoc_array_walk_result {
152 struct {
153 struct assoc_array_node *node; /* Node in which leaf might be found */
154 int level;
155 int slot;
156 } terminal_node;
157 struct {
158 struct assoc_array_shortcut *shortcut;
159 int level;
160 int sc_level;
161 unsigned long sc_segments;
162 unsigned long dissimilarity;
163 } wrong_shortcut;
164};
165
166/*
167 * Navigate through the internal tree looking for the closest node to the key.
168 */
169static enum assoc_array_walk_status
170assoc_array_walk(const struct assoc_array *array,
171 const struct assoc_array_ops *ops,
172 const void *index_key,
173 struct assoc_array_walk_result *result)
174{
175 struct assoc_array_shortcut *shortcut;
176 struct assoc_array_node *node;
177 struct assoc_array_ptr *cursor, *ptr;
178 unsigned long sc_segments, dissimilarity;
179 unsigned long segments;
180 int level, sc_level, next_sc_level;
181 int slot;
182
183 pr_devel("-->%s()\n", __func__);
184
185 cursor = READ_ONCE(array->root); /* Address dependency. */
186 if (!cursor)
187 return assoc_array_walk_tree_empty;
188
189 level = 0;
190
191 /* Use segments from the key for the new leaf to navigate through the
192 * internal tree, skipping through nodes and shortcuts that are on
193 * route to the destination. Eventually we'll come to a slot that is
194 * either empty or contains a leaf at which point we've found a node in
195 * which the leaf we're looking for might be found or into which it
196 * should be inserted.
197 */
198jumped:
199 segments = ops->get_key_chunk(index_key, level);
200 pr_devel("segments[%d]: %lx\n", level, segments);
201
202 if (assoc_array_ptr_is_shortcut(cursor))
203 goto follow_shortcut;
204
205consider_node:
206 node = assoc_array_ptr_to_node(cursor);
207 slot = segments >> (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
208 slot &= ASSOC_ARRAY_FAN_MASK;
209 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
210
211 pr_devel("consider slot %x [ix=%d type=%lu]\n",
212 slot, level, (unsigned long)ptr & 3);
213
214 if (!assoc_array_ptr_is_meta(ptr)) {
215 /* The node doesn't have a node/shortcut pointer in the slot
216 * corresponding to the index key that we have to follow.
217 */
218 result->terminal_node.node = node;
219 result->terminal_node.level = level;
220 result->terminal_node.slot = slot;
221 pr_devel("<--%s() = terminal_node\n", __func__);
222 return assoc_array_walk_found_terminal_node;
223 }
224
225 if (assoc_array_ptr_is_node(ptr)) {
226 /* There is a pointer to a node in the slot corresponding to
227 * this index key segment, so we need to follow it.
228 */
229 cursor = ptr;
230 level += ASSOC_ARRAY_LEVEL_STEP;
231 if ((level & ASSOC_ARRAY_KEY_CHUNK_MASK) != 0)
232 goto consider_node;
233 goto jumped;
234 }
235
236 /* There is a shortcut in the slot corresponding to the index key
237 * segment. We follow the shortcut if its partial index key matches
238 * this leaf's. Otherwise we need to split the shortcut.
239 */
240 cursor = ptr;
241follow_shortcut:
242 shortcut = assoc_array_ptr_to_shortcut(cursor);
243 pr_devel("shortcut to %d\n", shortcut->skip_to_level);
244 sc_level = level + ASSOC_ARRAY_LEVEL_STEP;
245 BUG_ON(sc_level > shortcut->skip_to_level);
246
247 do {
248 /* Check the leaf against the shortcut's index key a word at a
249 * time, trimming the final word (the shortcut stores the index
250 * key completely from the root to the shortcut's target).
251 */
252 if ((sc_level & ASSOC_ARRAY_KEY_CHUNK_MASK) == 0)
253 segments = ops->get_key_chunk(index_key, sc_level);
254
255 sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
256 dissimilarity = segments ^ sc_segments;
257
258 if (shortcut->skip_to_level < round_down(sc_level,
259 ASSOC_ARRAY_KEY_CHUNK_SIZE) + ASSOC_ARRAY_KEY_CHUNK_SIZE) {
260 /* Trim segments that are beyond the shortcut */
261 int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
262 dissimilarity &= ~(ULONG_MAX << shift);
263 next_sc_level = shortcut->skip_to_level;
264 } else {
265 next_sc_level = sc_level + ASSOC_ARRAY_KEY_CHUNK_SIZE;
266 next_sc_level = round_down(next_sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
267 }
268
269 if (dissimilarity != 0) {
270 /* This shortcut points elsewhere */
271 result->wrong_shortcut.shortcut = shortcut;
272 result->wrong_shortcut.level = level;
273 result->wrong_shortcut.sc_level = sc_level;
274 result->wrong_shortcut.sc_segments = sc_segments;
275 result->wrong_shortcut.dissimilarity = dissimilarity;
276 return assoc_array_walk_found_wrong_shortcut;
277 }
278
279 sc_level = next_sc_level;
280 } while (sc_level < shortcut->skip_to_level);
281
282 /* The shortcut matches the leaf's index to this point. */
283 cursor = READ_ONCE(shortcut->next_node); /* Address dependency. */
284 if (((level ^ sc_level) & ~ASSOC_ARRAY_KEY_CHUNK_MASK) != 0) {
285 level = sc_level;
286 goto jumped;
287 } else {
288 level = sc_level;
289 goto consider_node;
290 }
291}
292
293/**
294 * assoc_array_find - Find an object by index key
295 * @array: The associative array to search.
296 * @ops: The operations to use.
297 * @index_key: The key to the object.
298 *
299 * Find an object in an associative array by walking through the internal tree
300 * to the node that should contain the object and then searching the leaves
301 * there. NULL is returned if the requested object was not found in the array.
302 *
303 * The caller must hold the RCU read lock or better.
304 */
305void *assoc_array_find(const struct assoc_array *array,
306 const struct assoc_array_ops *ops,
307 const void *index_key)
308{
309 struct assoc_array_walk_result result;
310 const struct assoc_array_node *node;
311 const struct assoc_array_ptr *ptr;
312 const void *leaf;
313 int slot;
314
315 if (assoc_array_walk(array, ops, index_key, &result) !=
316 assoc_array_walk_found_terminal_node)
317 return NULL;
318
319 node = result.terminal_node.node;
320
321 /* If the target key is available to us, it's has to be pointed to by
322 * the terminal node.
323 */
324 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
325 ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
326 if (ptr && assoc_array_ptr_is_leaf(ptr)) {
327 /* We need a barrier between the read of the pointer
328 * and dereferencing the pointer - but only if we are
329 * actually going to dereference it.
330 */
331 leaf = assoc_array_ptr_to_leaf(ptr);
332 if (ops->compare_object(leaf, index_key))
333 return (void *)leaf;
334 }
335 }
336
337 return NULL;
338}
339
340/*
341 * Destructively iterate over an associative array. The caller must prevent
342 * other simultaneous accesses.
343 */
344static void assoc_array_destroy_subtree(struct assoc_array_ptr *root,
345 const struct assoc_array_ops *ops)
346{
347 struct assoc_array_shortcut *shortcut;
348 struct assoc_array_node *node;
349 struct assoc_array_ptr *cursor, *parent = NULL;
350 int slot = -1;
351
352 pr_devel("-->%s()\n", __func__);
353
354 cursor = root;
355 if (!cursor) {
356 pr_devel("empty\n");
357 return;
358 }
359
360move_to_meta:
361 if (assoc_array_ptr_is_shortcut(cursor)) {
362 /* Descend through a shortcut */
363 pr_devel("[%d] shortcut\n", slot);
364 BUG_ON(!assoc_array_ptr_is_shortcut(cursor));
365 shortcut = assoc_array_ptr_to_shortcut(cursor);
366 BUG_ON(shortcut->back_pointer != parent);
367 BUG_ON(slot != -1 && shortcut->parent_slot != slot);
368 parent = cursor;
369 cursor = shortcut->next_node;
370 slot = -1;
371 BUG_ON(!assoc_array_ptr_is_node(cursor));
372 }
373
374 pr_devel("[%d] node\n", slot);
375 node = assoc_array_ptr_to_node(cursor);
376 BUG_ON(node->back_pointer != parent);
377 BUG_ON(slot != -1 && node->parent_slot != slot);
378 slot = 0;
379
380continue_node:
381 pr_devel("Node %p [back=%p]\n", node, node->back_pointer);
382 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
383 struct assoc_array_ptr *ptr = node->slots[slot];
384 if (!ptr)
385 continue;
386 if (assoc_array_ptr_is_meta(ptr)) {
387 parent = cursor;
388 cursor = ptr;
389 goto move_to_meta;
390 }
391
392 if (ops) {
393 pr_devel("[%d] free leaf\n", slot);
394 ops->free_object(assoc_array_ptr_to_leaf(ptr));
395 }
396 }
397
398 parent = node->back_pointer;
399 slot = node->parent_slot;
400 pr_devel("free node\n");
401 kfree(node);
402 if (!parent)
403 return; /* Done */
404
405 /* Move back up to the parent (may need to free a shortcut on
406 * the way up) */
407 if (assoc_array_ptr_is_shortcut(parent)) {
408 shortcut = assoc_array_ptr_to_shortcut(parent);
409 BUG_ON(shortcut->next_node != cursor);
410 cursor = parent;
411 parent = shortcut->back_pointer;
412 slot = shortcut->parent_slot;
413 pr_devel("free shortcut\n");
414 kfree(shortcut);
415 if (!parent)
416 return;
417
418 BUG_ON(!assoc_array_ptr_is_node(parent));
419 }
420
421 /* Ascend to next slot in parent node */
422 pr_devel("ascend to %p[%d]\n", parent, slot);
423 cursor = parent;
424 node = assoc_array_ptr_to_node(cursor);
425 slot++;
426 goto continue_node;
427}
428
429/**
430 * assoc_array_destroy - Destroy an associative array
431 * @array: The array to destroy.
432 * @ops: The operations to use.
433 *
434 * Discard all metadata and free all objects in an associative array. The
435 * array will be empty and ready to use again upon completion. This function
436 * cannot fail.
437 *
438 * The caller must prevent all other accesses whilst this takes place as no
439 * attempt is made to adjust pointers gracefully to permit RCU readlock-holding
440 * accesses to continue. On the other hand, no memory allocation is required.
441 */
442void assoc_array_destroy(struct assoc_array *array,
443 const struct assoc_array_ops *ops)
444{
445 assoc_array_destroy_subtree(array->root, ops);
446 array->root = NULL;
447}
448
449/*
450 * Handle insertion into an empty tree.
451 */
452static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit)
453{
454 struct assoc_array_node *new_n0;
455
456 pr_devel("-->%s()\n", __func__);
457
458 new_n0 = kzalloc_obj(struct assoc_array_node);
459 if (!new_n0)
460 return false;
461
462 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
463 edit->leaf_p = &new_n0->slots[0];
464 edit->adjust_count_on = new_n0;
465 edit->set[0].ptr = &edit->array->root;
466 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
467
468 pr_devel("<--%s() = ok [no root]\n", __func__);
469 return true;
470}
471
472/*
473 * The pointer that leads to a node or shortcut with the given back pointer
474 * and parent slot: the root, a slot in a node, or a shortcut's next node.
475 */
476static struct assoc_array_ptr **assoc_array_parent_link(struct assoc_array *array,
477 struct assoc_array_ptr *back_pointer,
478 int parent_slot)
479{
480 if (!back_pointer)
481 return &array->root;
482 if (assoc_array_ptr_is_node(back_pointer))
483 return &assoc_array_ptr_to_node(back_pointer)->slots[parent_slot];
484 return &assoc_array_ptr_to_shortcut(back_pointer)->next_node;
485}
486
487/*
488 * Insert into a terminal node without changing its shape, if that can be
489 * done: in place of a leaf with the same index key, or in a free slot.
490 */
491static bool assoc_array_insert_in_node(struct assoc_array_edit *edit,
492 const struct assoc_array_ops *ops,
493 const void *index_key,
494 struct assoc_array_node *node)
495{
496 struct assoc_array_ptr *ptr;
497 int free_slot, i;
498
499 free_slot = -1;
500
501 /* Firstly, we have to check the leaves in this node to see if there's
502 * a matching one we should replace in place.
503 */
504 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
505 ptr = node->slots[i];
506 if (!ptr) {
507 free_slot = i;
508 continue;
509 }
510 if (assoc_array_ptr_is_leaf(ptr) &&
511 ops->compare_object(assoc_array_ptr_to_leaf(ptr),
512 index_key)) {
513 pr_devel("replace in slot %d\n", i);
514 edit->leaf_p = &node->slots[i];
515 edit->dead_leaf = node->slots[i];
516 return true;
517 }
518 }
519
520 /* If there is a free slot in this node then we can just insert the
521 * leaf here.
522 */
523 if (free_slot >= 0) {
524 pr_devel("insert in free slot %d\n", free_slot);
525 edit->leaf_p = &node->slots[free_slot];
526 edit->adjust_count_on = node;
527 return true;
528 }
529
530 return false;
531}
532
533/*
534 * Fill in the edit script's segment cache for a full node: the segment at
535 * this level of each leaf's index key, or 0xff for a metadata pointer.
536 * The new key's segment, in the last entry, is left to the caller. Returns
537 * true if there are any metadata pointers.
538 */
539static bool assoc_array_segment_leaves(struct assoc_array_edit *edit,
540 const struct assoc_array_ops *ops,
541 const struct assoc_array_node *node,
542 int level)
543{
544 struct assoc_array_ptr *ptr;
545 unsigned long base_seg;
546 bool have_meta;
547 int i;
548
549 have_meta = false;
550 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
551 ptr = node->slots[i];
552 if (assoc_array_ptr_is_meta(ptr)) {
553 edit->segment_cache[i] = 0xff;
554 have_meta = true;
555 continue;
556 }
557 base_seg = ops->get_object_key_chunk(
558 assoc_array_ptr_to_leaf(ptr), level);
559 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
560 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
561 }
562 return have_meta;
563}
564
565/*
566 * Whether the leaves of a full node and the new key all share one segment,
567 * so that splitting the node cannot make room.
568 */
569static bool assoc_array_all_one_segment(const struct assoc_array_edit *edit)
570{
571 int i;
572
573 for (i = 1; i < ASSOC_ARRAY_FAN_OUT + 1; i++)
574 if (edit->segment_cache[i] != edit->segment_cache[0])
575 return false;
576 return true;
577}
578
579/*
580 * Split a full node into new_n0, which takes its place, and new_n1, below
581 * new_n0 in the slot of a segment that at least two of the leaves share,
582 * the new one included. The caller has filled in the segment cache and
583 * set new_n0's back pointer and parent slot.
584 */
585static void assoc_array_split_node(struct assoc_array_edit *edit,
586 struct assoc_array_node *node,
587 struct assoc_array_node *new_n0,
588 struct assoc_array_node *new_n1)
589{
590 struct assoc_array_shortcut *shortcut;
591 struct assoc_array_node *side;
592 struct assoc_array_ptr *ptr;
593 int slot, next_slot, free_slot, i, j;
594
595 pr_devel("split node\n");
596
597 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
598 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
599 new_n1->nr_leaves_on_branch = 0;
600
601 /* Begin by finding two matching leaves. There have to be at least two
602 * that match - even if there are meta pointers - because any leaf that
603 * would match a slot with a meta pointer in it must be somewhere
604 * behind that meta pointer and cannot be here. Further, given N
605 * remaining leaf slots, we now have N+1 leaves to go in them.
606 */
607 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
608 slot = edit->segment_cache[i];
609 if (slot != 0xff)
610 for (j = i + 1; j < ASSOC_ARRAY_FAN_OUT + 1; j++)
611 if (edit->segment_cache[j] == slot)
612 goto found_slot_for_multiple_occupancy;
613 }
614found_slot_for_multiple_occupancy:
615 pr_devel("same slot: %x %x [%02x]\n", i, j, slot);
616 BUG_ON(i >= ASSOC_ARRAY_FAN_OUT);
617 BUG_ON(j >= ASSOC_ARRAY_FAN_OUT + 1);
618 BUG_ON(slot >= ASSOC_ARRAY_FAN_OUT);
619
620 new_n1->parent_slot = slot;
621
622 /* Metadata pointers cannot change slot */
623 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
624 if (assoc_array_ptr_is_meta(node->slots[i]))
625 new_n0->slots[i] = node->slots[i];
626 else
627 new_n0->slots[i] = NULL;
628 BUG_ON(new_n0->slots[slot] != NULL);
629 new_n0->slots[slot] = assoc_array_node_to_ptr(new_n1);
630
631 /* Filter the leaf pointers between the new nodes */
632 free_slot = -1;
633 next_slot = 0;
634 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
635 if (assoc_array_ptr_is_meta(node->slots[i]))
636 continue;
637 if (edit->segment_cache[i] == slot) {
638 new_n1->slots[next_slot++] = node->slots[i];
639 new_n1->nr_leaves_on_branch++;
640 } else {
641 do {
642 free_slot++;
643 } while (new_n0->slots[free_slot] != NULL);
644 new_n0->slots[free_slot] = node->slots[i];
645 }
646 }
647
648 pr_devel("filtered: f=%x n=%x\n", free_slot, next_slot);
649
650 if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {
651 do {
652 free_slot++;
653 } while (new_n0->slots[free_slot] != NULL);
654 edit->leaf_p = &new_n0->slots[free_slot];
655 edit->adjust_count_on = new_n0;
656 } else {
657 edit->leaf_p = &new_n1->slots[next_slot++];
658 edit->adjust_count_on = new_n1;
659 }
660
661 BUG_ON(next_slot <= 1);
662
663 edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);
664 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
665 if (edit->segment_cache[i] == 0xff) {
666 ptr = node->slots[i];
667 BUG_ON(assoc_array_ptr_is_leaf(ptr));
668 if (assoc_array_ptr_is_node(ptr)) {
669 side = assoc_array_ptr_to_node(ptr);
670 edit->set_backpointers[i] = &side->back_pointer;
671 } else {
672 shortcut = assoc_array_ptr_to_shortcut(ptr);
673 edit->set_backpointers[i] = &shortcut->back_pointer;
674 }
675 }
676 }
677}
678
679/*
680 * All the leaves, new and old, want to cluster together in this node in the
681 * same slot, so we have to replace this node with a shortcut to skip over
682 * the identical parts of the key, leading to new_n0. If the node is the
683 * target of a shortcut, the new one replaces that shortcut as well. The
684 * caller then splits the leaves between new_n0 and new_n1 at the shortcut's
685 * far end, for which this fills in the segment cache.
686 */
687static struct assoc_array_shortcut *
688assoc_array_insert_shortcut(struct assoc_array_edit *edit,
689 const struct assoc_array_ops *ops,
690 const void *index_key,
691 struct assoc_array_node *node, int level,
692 struct assoc_array_node *new_n0)
693{
694 struct assoc_array_shortcut *new_s0;
695 unsigned long base_seg, blank;
696 size_t keylen;
697 int diff, i;
698
699 /* Firstly we need to work out where the leaves start diverging as a
700 * bit position into their keys so that we know how big the shortcut
701 * needs to be.
702 *
703 * We only need to make a single pass of N of the N+1 leaves because if
704 * any keys differ between themselves at bit X then at least one of
705 * them must also differ with the base key at bit X or before.
706 */
707 pr_devel("all leaves cluster together\n");
708 diff = INT_MAX;
709 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
710 int x = ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]),
711 index_key);
712 if (x < diff) {
713 BUG_ON(x < 0);
714 diff = x;
715 }
716 }
717 BUG_ON(diff == INT_MAX);
718 BUG_ON(diff < level + ASSOC_ARRAY_LEVEL_STEP);
719
720 keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
721 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
722
723 new_s0 = kzalloc_flex(*new_s0, index_key, keylen);
724 if (!new_s0)
725 return NULL;
726 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);
727
728 new_s0->back_pointer = node->back_pointer;
729 new_s0->parent_slot = node->parent_slot;
730
731 /* A shortcut has to lead to a node, so a node at the end of a shortcut
732 * is replaced together with that shortcut. The new one holds the index
733 * key from the root, so it covers what the old one did.
734 */
735 if (node->back_pointer &&
736 assoc_array_ptr_is_shortcut(node->back_pointer)) {
737 struct assoc_array_shortcut *above =
738 assoc_array_ptr_to_shortcut(node->back_pointer);
739
740 new_s0->back_pointer = above->back_pointer;
741 new_s0->parent_slot = above->parent_slot;
742 edit->excised_meta[1] = node->back_pointer;
743 }
744 new_s0->next_node = assoc_array_node_to_ptr(new_n0);
745 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
746 new_n0->parent_slot = 0;
747
748 new_s0->skip_to_level = level = diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK;
749 pr_devel("skip_to_level = %d [diff %d]\n", level, diff);
750 BUG_ON(level <= 0);
751
752 for (i = 0; i < keylen; i++)
753 new_s0->index_key[i] =
754 ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE);
755
756 if (level & ASSOC_ARRAY_KEY_CHUNK_MASK) {
757 blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
758 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank);
759 new_s0->index_key[keylen - 1] &= ~blank;
760 }
761
762 /* This now reduces to a node splitting exercise for which we'll need
763 * to regenerate the disparity table.
764 */
765 assoc_array_segment_leaves(edit, ops, node, level);
766 base_seg = ops->get_key_chunk(index_key, level);
767 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
768 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;
769 return new_s0;
770}
771
772/*
773 * Handle insertion into a terminal node.
774 */
775static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
776 const struct assoc_array_ops *ops,
777 const void *index_key,
778 struct assoc_array_walk_result *result)
779{
780 struct assoc_array_shortcut *new_s0;
781 struct assoc_array_node *node, *new_n0, *new_n1;
782 bool have_meta;
783 int level;
784
785 node = result->terminal_node.node;
786 level = result->terminal_node.level;
787
788 pr_devel("-->%s()\n", __func__);
789
790 /* We arrived at a node which doesn't have an onward node or shortcut
791 * pointer that we have to follow. This means that (a) the leaf we
792 * want must go here (either by insertion or replacement) or (b) we
793 * need to split this node and insert in one of the fragments.
794 */
795 if (assoc_array_insert_in_node(edit, ops, index_key, node)) {
796 pr_devel("<--%s() = ok [in node]\n", __func__);
797 return true;
798 }
799
800 /* The node has no spare slots - so we're either going to have to split
801 * it or insert another node before it.
802 *
803 * Whatever, we're going to need at least two new nodes - so allocate
804 * those now. We may also need a new shortcut, but we deal with that
805 * when we need it.
806 */
807 new_n0 = kzalloc_obj(struct assoc_array_node);
808 if (!new_n0)
809 return false;
810 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
811 new_n1 = kzalloc_obj(struct assoc_array_node);
812 if (!new_n1)
813 return false;
814 edit->new_meta[1] = assoc_array_node_to_ptr(new_n1);
815
816 /* We need to find out how similar the leaves are. */
817 pr_devel("no spare slots\n");
818 have_meta = assoc_array_segment_leaves(edit, ops, node, level);
819 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot;
820
821 if (!have_meta && assoc_array_all_one_segment(edit)) {
822 /* Splitting the node would leave all the leaves in one slot, so
823 * a shortcut takes the node's place instead, and the node is
824 * split at the shortcut's far end. The shortcut goes wherever
825 * its back pointer says, which may be further up than the node.
826 */
827 new_s0 = assoc_array_insert_shortcut(edit, ops, index_key,
828 node, level, new_n0);
829 if (!new_s0)
830 return false;
831 edit->set[0].ptr = assoc_array_parent_link(edit->array,
832 new_s0->back_pointer,
833 new_s0->parent_slot);
834 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
835 } else {
836 /* We need to split the current node. The node must contain
837 * anything from a single leaf (in the one leaf case, this leaf
838 * will cluster with the new leaf) and the rest meta-pointers,
839 * to all leaves, some of which may cluster.
840 *
841 * We need to expel at least two leaves out of a set consisting
842 * of the leaves in the node and the new leaf. The current meta
843 * pointers can just be copied as they shouldn't cluster with
844 * any of the leaves. If all the old leaves cluster in one slot
845 * and the new leaf does not, they all go and the new leaf stays.
846 *
847 * We need a new node (n0) to replace the current one and a new
848 * node to take the expelled nodes (n1).
849 */
850 new_n0->back_pointer = node->back_pointer;
851 new_n0->parent_slot = node->parent_slot;
852 edit->set[0].ptr = assoc_array_parent_link(edit->array,
853 new_n0->back_pointer,
854 new_n0->parent_slot);
855 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
856 }
857
858 assoc_array_split_node(edit, node, new_n0, new_n1);
859 edit->excised_meta[0] = assoc_array_node_to_ptr(node);
860 pr_devel("<--%s() = ok [split node]\n", __func__);
861 return true;
862}
863
864/*
865 * Handle insertion into the middle of a shortcut.
866 */
867static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
868 const struct assoc_array_ops *ops,
869 struct assoc_array_walk_result *result)
870{
871 struct assoc_array_shortcut *shortcut, *new_s0, *new_s1;
872 struct assoc_array_node *new_n0, *side;
873 unsigned long sc_segments, dissimilarity, blank;
874 size_t keylen;
875 int level, sc_level, diff;
876 int sc_slot;
877
878 shortcut = result->wrong_shortcut.shortcut;
879 level = result->wrong_shortcut.level;
880 sc_level = result->wrong_shortcut.sc_level;
881 sc_segments = result->wrong_shortcut.sc_segments;
882 dissimilarity = result->wrong_shortcut.dissimilarity;
883
884 pr_devel("-->%s(ix=%d dis=%lx scix=%d)\n",
885 __func__, level, dissimilarity, sc_level);
886
887 /* We need to split a shortcut and insert a node between the two
888 * pieces. Zero-length pieces will be dispensed with entirely.
889 *
890 * First of all, we need to find out in which level the first
891 * difference was.
892 */
893 diff = __ffs(dissimilarity);
894 diff &= ~ASSOC_ARRAY_LEVEL_STEP_MASK;
895 diff += sc_level & ~ASSOC_ARRAY_KEY_CHUNK_MASK;
896 pr_devel("diff=%d\n", diff);
897
898 BUG_ON(shortcut->back_pointer &&
899 !assoc_array_ptr_is_node(shortcut->back_pointer));
900 edit->set[0].ptr = assoc_array_parent_link(edit->array,
901 shortcut->back_pointer,
902 shortcut->parent_slot);
903
904 edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);
905
906 /* Create a new node now since we're going to need it anyway */
907 new_n0 = kzalloc_obj(struct assoc_array_node);
908 if (!new_n0)
909 return false;
910 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
911 edit->adjust_count_on = new_n0;
912
913 /* Insert a new shortcut before the new node if this segment isn't of
914 * zero length - otherwise we just connect the new node directly to the
915 * parent.
916 */
917 if (shortcut->back_pointer)
918 level += ASSOC_ARRAY_LEVEL_STEP;
919 if (diff > level) {
920 pr_devel("pre-shortcut %d...%d\n", level, diff);
921 keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
922 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
923
924 new_s0 = kzalloc_flex(*new_s0, index_key, keylen);
925 if (!new_s0)
926 return false;
927 edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);
928 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
929 new_s0->back_pointer = shortcut->back_pointer;
930 new_s0->parent_slot = shortcut->parent_slot;
931 new_s0->next_node = assoc_array_node_to_ptr(new_n0);
932 new_s0->skip_to_level = diff;
933
934 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
935 new_n0->parent_slot = 0;
936
937 memcpy(new_s0->index_key, shortcut->index_key,
938 flex_array_size(new_s0, index_key, keylen));
939
940 if (diff & ASSOC_ARRAY_KEY_CHUNK_MASK) {
941 blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
942 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);
943 new_s0->index_key[keylen - 1] &= ~blank;
944 }
945 } else {
946 pr_devel("no pre-shortcut\n");
947 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
948 new_n0->back_pointer = shortcut->back_pointer;
949 new_n0->parent_slot = shortcut->parent_slot;
950 }
951
952 side = assoc_array_ptr_to_node(shortcut->next_node);
953 new_n0->nr_leaves_on_branch = side->nr_leaves_on_branch;
954
955 /* We need to know which slot in the new node is going to take a
956 * metadata pointer.
957 */
958 sc_slot = sc_segments >> (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
959 sc_slot &= ASSOC_ARRAY_FAN_MASK;
960
961 pr_devel("new slot %lx >> %d -> %d\n",
962 sc_segments, diff & ASSOC_ARRAY_KEY_CHUNK_MASK, sc_slot);
963
964 /* Determine whether we need to follow the new node with a replacement
965 * for the current shortcut. We could in theory reuse the current
966 * shortcut if its parent slot number doesn't change - but that's a
967 * 1-in-16 chance so not worth expending the code upon.
968 */
969 level = diff + ASSOC_ARRAY_LEVEL_STEP;
970 if (level < shortcut->skip_to_level) {
971 pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level);
972 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
973 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
974
975 new_s1 = kzalloc_flex(*new_s1, index_key, keylen);
976 if (!new_s1)
977 return false;
978 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);
979
980 new_s1->back_pointer = assoc_array_node_to_ptr(new_n0);
981 new_s1->parent_slot = sc_slot;
982 new_s1->next_node = shortcut->next_node;
983 new_s1->skip_to_level = shortcut->skip_to_level;
984
985 new_n0->slots[sc_slot] = assoc_array_shortcut_to_ptr(new_s1);
986
987 memcpy(new_s1->index_key, shortcut->index_key,
988 flex_array_size(new_s1, index_key, keylen));
989
990 edit->set[1].ptr = &side->back_pointer;
991 edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);
992 } else {
993 pr_devel("no post-shortcut\n");
994
995 /* We don't have to replace the pointed-to node as long as we
996 * use memory barriers to make sure the parent slot number is
997 * changed before the back pointer (the parent slot number is
998 * irrelevant to the old parent shortcut).
999 */
1000 new_n0->slots[sc_slot] = shortcut->next_node;
1001 edit->set_parent_slot[0].p = &side->parent_slot;
1002 edit->set_parent_slot[0].to = sc_slot;
1003 edit->set[1].ptr = &side->back_pointer;
1004 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
1005 }
1006
1007 /* Install the new leaf in a spare slot in the new node. */
1008 if (sc_slot == 0)
1009 edit->leaf_p = &new_n0->slots[1];
1010 else
1011 edit->leaf_p = &new_n0->slots[0];
1012
1013 pr_devel("<--%s() = ok [split shortcut]\n", __func__);
1014 return true;
1015}
1016
1017/**
1018 * assoc_array_insert - Script insertion of an object into an associative array
1019 * @array: The array to insert into.
1020 * @ops: The operations to use.
1021 * @index_key: The key to insert at.
1022 * @object: The object to insert.
1023 *
1024 * Precalculate and preallocate a script for the insertion or replacement of an
1025 * object in an associative array. This results in an edit script that can
1026 * either be applied or cancelled.
1027 *
1028 * The function returns a pointer to an edit script or -ENOMEM.
1029 *
1030 * The caller should lock against other modifications and must continue to hold
1031 * the lock until assoc_array_apply_edit() has been called.
1032 *
1033 * Accesses to the tree may take place concurrently with this function,
1034 * provided they hold the RCU read lock.
1035 */
1036struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
1037 const struct assoc_array_ops *ops,
1038 const void *index_key,
1039 void *object)
1040{
1041 struct assoc_array_walk_result result;
1042 struct assoc_array_edit *edit;
1043
1044 pr_devel("-->%s()\n", __func__);
1045
1046 /* The leaf pointer we're given must not have the bottom bit set as we
1047 * use those for type-marking the pointer. NULL pointers are also not
1048 * allowed as they indicate an empty slot but we have to allow them
1049 * here as they can be updated later.
1050 */
1051 BUG_ON(assoc_array_ptr_is_meta(object));
1052
1053 edit = kzalloc_obj(struct assoc_array_edit);
1054 if (!edit)
1055 return ERR_PTR(-ENOMEM);
1056 edit->array = array;
1057 edit->ops = ops;
1058 edit->leaf = assoc_array_leaf_to_ptr(object);
1059 edit->adjust_count_by = 1;
1060
1061 switch (assoc_array_walk(array, ops, index_key, &result)) {
1062 case assoc_array_walk_tree_empty:
1063 /* Allocate a root node if there isn't one yet */
1064 if (!assoc_array_insert_in_empty_tree(edit))
1065 goto enomem;
1066 return edit;
1067
1068 case assoc_array_walk_found_terminal_node:
1069 /* We found a node that doesn't have a node/shortcut pointer in
1070 * the slot corresponding to the index key that we have to
1071 * follow.
1072 */
1073 if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,
1074 &result))
1075 goto enomem;
1076 return edit;
1077
1078 case assoc_array_walk_found_wrong_shortcut:
1079 /* We found a shortcut that didn't match our key in a slot we
1080 * needed to follow.
1081 */
1082 if (!assoc_array_insert_mid_shortcut(edit, ops, &result))
1083 goto enomem;
1084 return edit;
1085 }
1086
1087enomem:
1088 /* Clean up after an out of memory error */
1089 pr_devel("enomem\n");
1090 assoc_array_cancel_edit(edit);
1091 return ERR_PTR(-ENOMEM);
1092}
1093
1094/**
1095 * assoc_array_insert_set_object - Set the new object pointer in an edit script
1096 * @edit: The edit script to modify.
1097 * @object: The object pointer to set.
1098 *
1099 * Change the object to be inserted in an edit script. The object pointed to
1100 * by the old object is not freed. This must be done prior to applying the
1101 * script.
1102 */
1103void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)
1104{
1105 BUG_ON(!object);
1106 edit->leaf = assoc_array_leaf_to_ptr(object);
1107}
1108
1109struct assoc_array_delete_collapse_context {
1110 struct assoc_array_node *node;
1111 const void *skip_leaf;
1112 int slot;
1113};
1114
1115/*
1116 * Subtree collapse to node iterator.
1117 */
1118static int assoc_array_delete_collapse_iterator(const void *leaf,
1119 void *iterator_data)
1120{
1121 struct assoc_array_delete_collapse_context *collapse = iterator_data;
1122
1123 if (leaf == collapse->skip_leaf)
1124 return 0;
1125
1126 BUG_ON(collapse->slot >= ASSOC_ARRAY_FAN_OUT);
1127
1128 collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf);
1129 return 0;
1130}
1131
1132/*
1133 * Deleting a leaf from node leaves its subtree with FAN_OUT or fewer leaves:
1134 * collapse the subtree into one new node, together with as much of the tree
1135 * above it as also fits. Returns false if the new node cannot be allocated.
1136 */
1137static bool assoc_array_delete_collapse(struct assoc_array_edit *edit,
1138 struct assoc_array_node *node)
1139{
1140 struct assoc_array_delete_collapse_context collapse;
1141 struct assoc_array_node *parent, *grandparent, *new_n0;
1142 struct assoc_array_ptr *ptr;
1143 bool has_meta;
1144 int i;
1145
1146 /* First of all, we need to know if this node has metadata so
1147 * that we don't try collapsing if all the leaves are already
1148 * here.
1149 */
1150 has_meta = false;
1151 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
1152 ptr = node->slots[i];
1153 if (assoc_array_ptr_is_meta(ptr)) {
1154 has_meta = true;
1155 break;
1156 }
1157 }
1158
1159 pr_devel("leaves: %ld [m=%d]\n",
1160 node->nr_leaves_on_branch - 1, has_meta);
1161
1162 /* Look further up the tree to see if we can collapse this node
1163 * into a more proximal node too.
1164 */
1165 for (parent = node;; parent = grandparent) {
1166 pr_devel("collapse subtree: %ld\n", parent->nr_leaves_on_branch);
1167
1168 ptr = parent->back_pointer;
1169 if (ptr && assoc_array_ptr_is_shortcut(ptr))
1170 ptr = assoc_array_ptr_to_shortcut(ptr)->back_pointer;
1171 if (!ptr)
1172 break;
1173
1174 grandparent = assoc_array_ptr_to_node(ptr);
1175 if (grandparent->nr_leaves_on_branch > ASSOC_ARRAY_FAN_OUT + 1)
1176 break;
1177 }
1178
1179 /* There's no point collapsing if the original node has no meta
1180 * pointers to discard and if we didn't merge into one of that
1181 * node's ancestry.
1182 */
1183 if (has_meta || parent != node) {
1184 node = parent;
1185
1186 /* Create a new node to collapse into */
1187 new_n0 = kzalloc_obj(struct assoc_array_node);
1188 if (!new_n0)
1189 return false;
1190 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
1191
1192 new_n0->back_pointer = node->back_pointer;
1193 new_n0->parent_slot = node->parent_slot;
1194 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
1195 edit->adjust_count_on = new_n0;
1196
1197 collapse.node = new_n0;
1198 collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);
1199 collapse.slot = 0;
1200 assoc_array_subtree_iterate(assoc_array_node_to_ptr(node),
1201 node->back_pointer,
1202 assoc_array_delete_collapse_iterator,
1203 &collapse);
1204 pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch);
1205 BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1);
1206
1207 BUG_ON(node->back_pointer &&
1208 assoc_array_ptr_is_leaf(node->back_pointer));
1209 edit->set[1].ptr = assoc_array_parent_link(edit->array,
1210 node->back_pointer,
1211 node->parent_slot);
1212 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
1213 edit->excised_subtree = assoc_array_node_to_ptr(node);
1214 }
1215 return true;
1216}
1217
1218/**
1219 * assoc_array_delete - Script deletion of an object from an associative array
1220 * @array: The array to search.
1221 * @ops: The operations to use.
1222 * @index_key: The key to the object.
1223 *
1224 * Precalculate and preallocate a script for the deletion of an object from an
1225 * associative array. This results in an edit script that can either be
1226 * applied or cancelled.
1227 *
1228 * The function returns a pointer to an edit script if the object was found,
1229 * NULL if the object was not found or -ENOMEM.
1230 *
1231 * The caller should lock against other modifications and must continue to hold
1232 * the lock until assoc_array_apply_edit() has been called.
1233 *
1234 * Accesses to the tree may take place concurrently with this function,
1235 * provided they hold the RCU read lock.
1236 */
1237struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
1238 const struct assoc_array_ops *ops,
1239 const void *index_key)
1240{
1241 struct assoc_array_walk_result result;
1242 struct assoc_array_node *node;
1243 struct assoc_array_edit *edit;
1244 struct assoc_array_ptr *ptr;
1245 int slot;
1246
1247 pr_devel("-->%s()\n", __func__);
1248
1249 edit = kzalloc_obj(struct assoc_array_edit);
1250 if (!edit)
1251 return ERR_PTR(-ENOMEM);
1252 edit->array = array;
1253 edit->ops = ops;
1254 edit->adjust_count_by = -1;
1255
1256 node = NULL;
1257 slot = ASSOC_ARRAY_FAN_OUT;
1258 if (assoc_array_walk(array, ops, index_key, &result) ==
1259 assoc_array_walk_found_terminal_node) {
1260 /* We found a node that should contain the leaf we've been
1261 * asked to remove - *if* it's in the tree.
1262 */
1263 pr_devel("terminal_node\n");
1264 node = result.terminal_node.node;
1265
1266 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1267 ptr = node->slots[slot];
1268 if (ptr &&
1269 assoc_array_ptr_is_leaf(ptr) &&
1270 ops->compare_object(assoc_array_ptr_to_leaf(ptr),
1271 index_key))
1272 break;
1273 }
1274 }
1275 if (slot == ASSOC_ARRAY_FAN_OUT) {
1276 assoc_array_cancel_edit(edit);
1277 pr_devel("not found\n");
1278 return NULL;
1279 }
1280
1281 BUG_ON(array->nr_leaves_on_tree <= 0);
1282
1283 /* In the simplest form of deletion we just clear the slot and release
1284 * the leaf after a suitable interval.
1285 */
1286 edit->dead_leaf = node->slots[slot];
1287 edit->set[0].ptr = &node->slots[slot];
1288 edit->set[0].to = NULL;
1289 edit->adjust_count_on = node;
1290
1291 /* If that concludes erasure of the last leaf, then delete the entire
1292 * internal array.
1293 */
1294 if (array->nr_leaves_on_tree == 1) {
1295 edit->set[1].ptr = &array->root;
1296 edit->set[1].to = NULL;
1297 edit->adjust_count_on = NULL;
1298 edit->excised_subtree = array->root;
1299 pr_devel("all gone\n");
1300 return edit;
1301 }
1302
1303 /* However, we'd also like to clear up some metadata blocks if we
1304 * possibly can.
1305 *
1306 * We go for a simple algorithm of: if this node has FAN_OUT or fewer
1307 * leaves in it, then attempt to collapse it - and attempt to
1308 * recursively collapse up the tree.
1309 *
1310 * We could also try and collapse in partially filled subtrees to take
1311 * up space in this node.
1312 */
1313 if (node->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1 &&
1314 !assoc_array_delete_collapse(edit, node)) {
1315 /* Clean up after an out of memory error */
1316 pr_devel("enomem\n");
1317 assoc_array_cancel_edit(edit);
1318 return ERR_PTR(-ENOMEM);
1319 }
1320
1321 return edit;
1322}
1323
1324/**
1325 * assoc_array_clear - Script deletion of all objects from an associative array
1326 * @array: The array to clear.
1327 * @ops: The operations to use.
1328 *
1329 * Precalculate and preallocate a script for the deletion of all the objects
1330 * from an associative array. This results in an edit script that can either
1331 * be applied or cancelled.
1332 *
1333 * The function returns a pointer to an edit script if there are objects to be
1334 * deleted, NULL if there are no objects in the array or -ENOMEM.
1335 *
1336 * The caller should lock against other modifications and must continue to hold
1337 * the lock until assoc_array_apply_edit() has been called.
1338 *
1339 * Accesses to the tree may take place concurrently with this function,
1340 * provided they hold the RCU read lock.
1341 */
1342struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
1343 const struct assoc_array_ops *ops)
1344{
1345 struct assoc_array_edit *edit;
1346
1347 pr_devel("-->%s()\n", __func__);
1348
1349 if (!array->root)
1350 return NULL;
1351
1352 edit = kzalloc_obj(struct assoc_array_edit);
1353 if (!edit)
1354 return ERR_PTR(-ENOMEM);
1355 edit->array = array;
1356 edit->ops = ops;
1357 edit->set[1].ptr = &array->root;
1358 edit->set[1].to = NULL;
1359 edit->excised_subtree = array->root;
1360 edit->ops_for_excised_subtree = ops;
1361 pr_devel("all gone\n");
1362 return edit;
1363}
1364
1365/*
1366 * Handle the deferred destruction after an applied edit.
1367 */
1368static void assoc_array_rcu_cleanup(struct rcu_head *head)
1369{
1370 struct assoc_array_edit *edit =
1371 container_of(head, struct assoc_array_edit, rcu);
1372 int i;
1373
1374 pr_devel("-->%s()\n", __func__);
1375
1376 if (edit->dead_leaf)
1377 edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));
1378 for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)
1379 if (edit->excised_meta[i])
1380 kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));
1381
1382 if (edit->excised_subtree) {
1383 BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));
1384 if (assoc_array_ptr_is_node(edit->excised_subtree)) {
1385 struct assoc_array_node *n =
1386 assoc_array_ptr_to_node(edit->excised_subtree);
1387 n->back_pointer = NULL;
1388 } else {
1389 struct assoc_array_shortcut *s =
1390 assoc_array_ptr_to_shortcut(edit->excised_subtree);
1391 s->back_pointer = NULL;
1392 }
1393 assoc_array_destroy_subtree(edit->excised_subtree,
1394 edit->ops_for_excised_subtree);
1395 }
1396
1397 kfree(edit);
1398}
1399
1400/**
1401 * assoc_array_apply_edit - Apply an edit script to an associative array
1402 * @edit: The script to apply.
1403 *
1404 * Apply an edit script to an associative array to effect an insertion,
1405 * deletion or clearance. As the edit script includes preallocated memory,
1406 * this is guaranteed not to fail.
1407 *
1408 * The edit script, dead objects and dead metadata will be scheduled for
1409 * destruction after an RCU grace period to permit those doing read-only
1410 * accesses on the array to continue to do so under the RCU read lock whilst
1411 * the edit is taking place.
1412 */
1413void assoc_array_apply_edit(struct assoc_array_edit *edit)
1414{
1415 struct assoc_array_shortcut *shortcut;
1416 struct assoc_array_node *node;
1417 struct assoc_array_ptr *ptr;
1418 int i;
1419
1420 pr_devel("-->%s()\n", __func__);
1421
1422 smp_wmb();
1423 if (edit->leaf_p)
1424 *edit->leaf_p = edit->leaf;
1425
1426 smp_wmb();
1427 for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)
1428 if (edit->set_parent_slot[i].p)
1429 *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;
1430
1431 smp_wmb();
1432 for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)
1433 if (edit->set_backpointers[i])
1434 *edit->set_backpointers[i] = edit->set_backpointers_to;
1435
1436 smp_wmb();
1437 for (i = 0; i < ARRAY_SIZE(edit->set); i++)
1438 if (edit->set[i].ptr)
1439 *edit->set[i].ptr = edit->set[i].to;
1440
1441 if (edit->array->root == NULL) {
1442 edit->array->nr_leaves_on_tree = 0;
1443 } else if (edit->adjust_count_on) {
1444 node = edit->adjust_count_on;
1445 for (;;) {
1446 node->nr_leaves_on_branch += edit->adjust_count_by;
1447
1448 ptr = node->back_pointer;
1449 if (!ptr)
1450 break;
1451 if (assoc_array_ptr_is_shortcut(ptr)) {
1452 shortcut = assoc_array_ptr_to_shortcut(ptr);
1453 ptr = shortcut->back_pointer;
1454 if (!ptr)
1455 break;
1456 }
1457 BUG_ON(!assoc_array_ptr_is_node(ptr));
1458 node = assoc_array_ptr_to_node(ptr);
1459 }
1460
1461 edit->array->nr_leaves_on_tree += edit->adjust_count_by;
1462 }
1463
1464 call_rcu(&edit->rcu, assoc_array_rcu_cleanup);
1465}
1466
1467/**
1468 * assoc_array_cancel_edit - Discard an edit script.
1469 * @edit: The script to discard.
1470 *
1471 * Free an edit script and all the preallocated data it holds without making
1472 * any changes to the associative array it was intended for.
1473 *
1474 * NOTE! In the case of an insertion script, this does _not_ release the leaf
1475 * that was to be inserted. That is left to the caller.
1476 */
1477void assoc_array_cancel_edit(struct assoc_array_edit *edit)
1478{
1479 struct assoc_array_ptr *ptr;
1480 int i;
1481
1482 pr_devel("-->%s()\n", __func__);
1483
1484 /* Clean up after an out of memory error */
1485 for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {
1486 ptr = edit->new_meta[i];
1487 if (ptr) {
1488 if (assoc_array_ptr_is_node(ptr))
1489 kfree(assoc_array_ptr_to_node(ptr));
1490 else
1491 kfree(assoc_array_ptr_to_shortcut(ptr));
1492 }
1493 }
1494 kfree(edit);
1495}
1496
1497/*
1498 * Where assoc_array_gc() has got to. It copies the tree depth first without
1499 * recursion: on reaching a subtree it copies it and carries on there, and on
1500 * finishing a node it climbs back up the old tree to the node above.
1501 */
1502struct assoc_array_gc_walk {
1503 struct assoc_array_node *node; /* The node being copied */
1504 struct assoc_array_node *new_n; /* Its copy */
1505 int slot; /* The next slot of node to look at */
1506 struct assoc_array_ptr *new_root; /* The root of the copy */
1507 unsigned long nr_leaves_on_tree;
1508 bool (*iterator)(void *object, void *iterator_data);
1509 void *iterator_data;
1510};
1511
1512/*
1513 * Copy the node at cursor, and the shortcut in front of it if there is one,
1514 * into the new tree at *link, below the copy of the node being worked on,
1515 * and work on that node next.
1516 */
1517static bool assoc_array_gc_copy(struct assoc_array_gc_walk *w,
1518 struct assoc_array_ptr *cursor,
1519 struct assoc_array_ptr **link)
1520{
1521 struct assoc_array_shortcut *shortcut, *new_s;
1522 struct assoc_array_node *new_n;
1523 struct assoc_array_ptr *new_parent;
1524 int keylen;
1525
1526 new_parent = w->new_n ? assoc_array_node_to_ptr(w->new_n) : NULL;
1527
1528 /* The node at this position is duplicated, and so is the shortcut in
1529 * front of it if there is one. The node is allocated first: the copy
1530 * of the shortcut starts out pointing at the old node, and must not be
1531 * in the new tree if the node cannot be allocated, or the cleanup
1532 * would follow it into the old tree.
1533 */
1534 new_n = kzalloc_obj(struct assoc_array_node);
1535 if (!new_n)
1536 return false;
1537
1538 if (assoc_array_ptr_is_shortcut(cursor)) {
1539 shortcut = assoc_array_ptr_to_shortcut(cursor);
1540 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
1541 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
1542 new_s = kmalloc_flex(*new_s, index_key, keylen);
1543 if (!new_s) {
1544 kfree(new_n);
1545 return false;
1546 }
1547 pr_devel("dup shortcut %p -> %p\n", shortcut, new_s);
1548 memcpy(new_s, shortcut, struct_size(new_s, index_key, keylen));
1549 new_s->back_pointer = new_parent;
1550 new_s->parent_slot = shortcut->parent_slot;
1551 *link = new_parent = assoc_array_shortcut_to_ptr(new_s);
1552 link = &new_s->next_node;
1553 cursor = shortcut->next_node;
1554 }
1555
1556 w->node = assoc_array_ptr_to_node(cursor);
1557 pr_devel("dup node %p -> %p\n", w->node, new_n);
1558 new_n->back_pointer = new_parent;
1559 new_n->parent_slot = w->node->parent_slot;
1560 *link = assoc_array_node_to_ptr(new_n);
1561 w->new_n = new_n;
1562 w->slot = 0;
1563 return true;
1564}
1565
1566/*
1567 * Carry on through the slots of the node being copied, putting the leaves
1568 * the iterator keeps into the copy, as far as the next pointer to a subtree.
1569 * Returns that pointer, with w->slot at it, or NULL when the node is done.
1570 */
1571static struct assoc_array_ptr *assoc_array_gc_next(struct assoc_array_gc_walk *w)
1572{
1573 struct assoc_array_ptr *ptr;
1574
1575 /* Filter across any leaves and gc any subtrees */
1576 for (; w->slot < ASSOC_ARRAY_FAN_OUT; w->slot++) {
1577 ptr = w->node->slots[w->slot];
1578 if (!ptr)
1579 continue;
1580
1581 if (assoc_array_ptr_is_leaf(ptr)) {
1582 if (w->iterator(assoc_array_ptr_to_leaf(ptr),
1583 w->iterator_data))
1584 /* The iterator will have done any reference
1585 * counting on the object for us.
1586 */
1587 w->new_n->slots[w->slot] = ptr;
1588 continue;
1589 }
1590
1591 return ptr;
1592 }
1593 return NULL;
1594}
1595
1596/*
1597 * Fold the children of a finished copy into it where their leaves fit in
1598 * its free slots, and count its leaves. Returns the number of free slots
1599 * left.
1600 */
1601static int assoc_array_gc_fold(struct assoc_array_node *new_n)
1602{
1603 struct assoc_array_ptr *ptr;
1604 bool retained;
1605 int slot, nr_free, next_slot, i;
1606
1607retry_compress:
1608 pr_devel("-- compress node %p --\n", new_n);
1609
1610 /* Count up the number of empty slots in this node and work out the
1611 * subtree leaf count.
1612 */
1613 new_n->nr_leaves_on_branch = 0;
1614 nr_free = 0;
1615 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1616 ptr = new_n->slots[slot];
1617 if (!ptr)
1618 nr_free++;
1619 else if (assoc_array_ptr_is_leaf(ptr))
1620 new_n->nr_leaves_on_branch++;
1621 }
1622 pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch);
1623
1624 /* See what we can fold in */
1625 retained = false;
1626 next_slot = 0;
1627 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1628 struct assoc_array_shortcut *s;
1629 struct assoc_array_node *child;
1630
1631 ptr = new_n->slots[slot];
1632 if (!ptr || assoc_array_ptr_is_leaf(ptr))
1633 continue;
1634
1635 s = NULL;
1636 if (assoc_array_ptr_is_shortcut(ptr)) {
1637 s = assoc_array_ptr_to_shortcut(ptr);
1638 ptr = s->next_node;
1639 }
1640
1641 child = assoc_array_ptr_to_node(ptr);
1642 new_n->nr_leaves_on_branch += child->nr_leaves_on_branch;
1643
1644 if (child->nr_leaves_on_branch <= nr_free + 1) {
1645 /* Fold the child node into this one */
1646 pr_devel("[%d] fold node %lu/%d [nx %d]\n",
1647 slot, child->nr_leaves_on_branch, nr_free + 1,
1648 next_slot);
1649
1650 /* We would already have reaped an intervening shortcut
1651 * on the way back up the tree.
1652 */
1653 BUG_ON(s);
1654
1655 new_n->slots[slot] = NULL;
1656 nr_free++;
1657 if (slot < next_slot)
1658 next_slot = slot;
1659 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
1660 struct assoc_array_ptr *p = child->slots[i];
1661 if (!p)
1662 continue;
1663 BUG_ON(assoc_array_ptr_is_meta(p));
1664 while (new_n->slots[next_slot])
1665 next_slot++;
1666 BUG_ON(next_slot >= ASSOC_ARRAY_FAN_OUT);
1667 new_n->slots[next_slot++] = p;
1668 nr_free--;
1669 }
1670 kfree(child);
1671 } else {
1672 pr_devel("[%d] retain node %lu/%d [nx %d]\n",
1673 slot, child->nr_leaves_on_branch, nr_free + 1,
1674 next_slot);
1675 retained = true;
1676 }
1677 }
1678
1679 if (retained && new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
1680 pr_devel("internal nodes remain despite enough space, retrying\n");
1681 goto retry_compress;
1682 }
1683 pr_devel("after: %lu\n", new_n->nr_leaves_on_branch);
1684 return nr_free;
1685}
1686
1687/*
1688 * The copy of the node being worked on is finished: fold its children into
1689 * it, then remove it if all it holds is a shortcut, or remove the shortcut
1690 * in front of it if it is small. Returns what is then the copy's parent, or
1691 * NULL if it is at the root, when the whole tree has been copied.
1692 */
1693static struct assoc_array_ptr *assoc_array_gc_pack(struct assoc_array_gc_walk *w)
1694{
1695 struct assoc_array_shortcut *new_s;
1696 struct assoc_array_node *new_n = w->new_n;
1697 struct assoc_array_ptr *ptr, *new_parent;
1698 int nr_free, slot;
1699
1700 nr_free = assoc_array_gc_fold(new_n);
1701 w->nr_leaves_on_tree = new_n->nr_leaves_on_branch;
1702
1703 /* Excise this node if it is singly occupied by a shortcut */
1704 if (nr_free == ASSOC_ARRAY_FAN_OUT - 1) {
1705 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++)
1706 if ((ptr = new_n->slots[slot]))
1707 break;
1708
1709 if (assoc_array_ptr_is_meta(ptr) &&
1710 assoc_array_ptr_is_shortcut(ptr)) {
1711 pr_devel("excise node %p with 1 shortcut\n", new_n);
1712 new_s = assoc_array_ptr_to_shortcut(ptr);
1713 new_parent = new_n->back_pointer;
1714 slot = new_n->parent_slot;
1715 kfree(new_n);
1716 if (!new_parent) {
1717 new_s->back_pointer = NULL;
1718 new_s->parent_slot = 0;
1719 w->new_root = ptr;
1720 return NULL;
1721 }
1722
1723 if (assoc_array_ptr_is_shortcut(new_parent)) {
1724 /* We can discard any preceding shortcut also */
1725 struct assoc_array_shortcut *s =
1726 assoc_array_ptr_to_shortcut(new_parent);
1727
1728 pr_devel("excise preceding shortcut\n");
1729
1730 new_parent = new_s->back_pointer = s->back_pointer;
1731 slot = new_s->parent_slot = s->parent_slot;
1732 kfree(s);
1733 if (!new_parent) {
1734 new_s->back_pointer = NULL;
1735 new_s->parent_slot = 0;
1736 w->new_root = ptr;
1737 return NULL;
1738 }
1739 }
1740
1741 new_s->back_pointer = new_parent;
1742 new_s->parent_slot = slot;
1743 assoc_array_ptr_to_node(new_parent)->slots[slot] = ptr;
1744 return new_parent;
1745 }
1746 }
1747
1748 /* Excise any shortcuts we might encounter that point to nodes that
1749 * only contain leaves.
1750 */
1751 ptr = new_n->back_pointer;
1752 if (!ptr)
1753 return NULL;
1754
1755 if (!assoc_array_ptr_is_shortcut(ptr))
1756 return ptr;
1757
1758 new_s = assoc_array_ptr_to_shortcut(ptr);
1759 new_parent = new_s->back_pointer;
1760 slot = new_s->parent_slot;
1761
1762 if (new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
1763 pr_devel("excise shortcut\n");
1764 new_n->back_pointer = new_parent;
1765 new_n->parent_slot = slot;
1766 kfree(new_s);
1767 if (!new_parent) {
1768 w->new_root = assoc_array_node_to_ptr(new_n);
1769 return NULL;
1770 }
1771
1772 assoc_array_ptr_to_node(new_parent)->slots[slot] =
1773 assoc_array_node_to_ptr(new_n);
1774 }
1775 return new_parent;
1776}
1777
1778/*
1779 * Go back up from the node just finished to the node above it, whose copy is
1780 * parent, and on to that node's next slot.
1781 */
1782static void assoc_array_gc_ascend(struct assoc_array_gc_walk *w,
1783 struct assoc_array_ptr *parent)
1784{
1785 struct assoc_array_shortcut *shortcut;
1786 struct assoc_array_ptr *ptr, *cursor;
1787 int slot;
1788
1789 w->new_n = assoc_array_ptr_to_node(parent);
1790
1791 ptr = w->node->back_pointer;
1792 if (assoc_array_ptr_is_shortcut(ptr)) {
1793 shortcut = assoc_array_ptr_to_shortcut(ptr);
1794 slot = shortcut->parent_slot;
1795 cursor = shortcut->back_pointer;
1796 } else {
1797 slot = w->node->parent_slot;
1798 cursor = ptr;
1799 }
1800 BUG_ON(!cursor);
1801 w->node = assoc_array_ptr_to_node(cursor);
1802 w->slot = slot + 1;
1803}
1804
1805/**
1806 * assoc_array_gc - Garbage collect an associative array.
1807 * @array: The array to clean.
1808 * @ops: The operations to use.
1809 * @iterator: A callback function to pass judgement on each object.
1810 * @iterator_data: Private data for the callback function.
1811 *
1812 * Collect garbage from an associative array and pack down the internal tree to
1813 * save memory.
1814 *
1815 * The iterator function is asked to pass judgement upon each object in the
1816 * array. If it returns false, the object is discard and if it returns true,
1817 * the object is kept. If it returns true, it must increment the object's
1818 * usage count (or whatever it needs to do to retain it) before returning.
1819 *
1820 * This function returns 0 if successful or -ENOMEM if out of memory. In the
1821 * latter case, the array is not changed.
1822 *
1823 * The caller should lock against other modifications and must continue to hold
1824 * the lock until assoc_array_apply_edit() has been called.
1825 *
1826 * Accesses to the tree may take place concurrently with this function,
1827 * provided they hold the RCU read lock.
1828 */
1829int assoc_array_gc(struct assoc_array *array,
1830 const struct assoc_array_ops *ops,
1831 bool (*iterator)(void *object, void *iterator_data),
1832 void *iterator_data)
1833{
1834 struct assoc_array_gc_walk w = {
1835 .iterator = iterator,
1836 .iterator_data = iterator_data,
1837 };
1838 struct assoc_array_edit *edit;
1839 struct assoc_array_ptr *ptr, *parent, **link;
1840
1841 pr_devel("-->%s()\n", __func__);
1842
1843 if (!array->root)
1844 return 0;
1845
1846 edit = kzalloc_obj(struct assoc_array_edit);
1847 if (!edit)
1848 return -ENOMEM;
1849 edit->array = array;
1850 edit->ops = ops;
1851 edit->ops_for_excised_subtree = ops;
1852 edit->set[0].ptr = &array->root;
1853 edit->excised_subtree = array->root;
1854
1855 ptr = array->root;
1856 link = &w.new_root;
1857 for (;;) {
1858 if (!assoc_array_gc_copy(&w, ptr, link))
1859 goto enomem;
1860
1861 /* Find the next subtree to copy: further on in this node, or,
1862 * when it is done, in the nodes above it.
1863 */
1864 while (!(ptr = assoc_array_gc_next(&w))) {
1865 parent = assoc_array_gc_pack(&w);
1866 if (!parent)
1867 goto copied;
1868 assoc_array_gc_ascend(&w, parent);
1869 }
1870 link = &w.new_n->slots[w.slot];
1871 }
1872
1873copied:
1874 edit->set[0].to = w.new_root;
1875 assoc_array_apply_edit(edit);
1876 array->nr_leaves_on_tree = w.nr_leaves_on_tree;
1877 return 0;
1878
1879enomem:
1880 pr_devel("enomem\n");
1881 assoc_array_destroy_subtree(w.new_root, edit->ops);
1882 kfree(edit);
1883 return -ENOMEM;
1884}