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

1885 lines · 56.9 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_fill_segment_cache(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_fill_segment_cache(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_fill_segment_cache(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 /* The node only contains leaves and all the leaves cluster in
823 * the same slot, so we need to insert a shortcut to skip the
824 * common portion of the key and split the node at the
825 * shortcut's far end. The shortcut goes wherever its back
826 * pointer says, which may be further up than the node.
827 */
828 new_s0 = assoc_array_insert_shortcut(edit, ops, index_key,
829 node, level, new_n0);
830 if (!new_s0)
831 return false;
832 edit->set[0].ptr = assoc_array_parent_link(edit->array,
833 new_s0->back_pointer,
834 new_s0->parent_slot);
835 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
836 } else {
837 /* We need to split the current node. The node must contain
838 * anything from a single leaf (in the one leaf case, this leaf
839 * will cluster with the new leaf) and the rest meta-pointers,
840 * to all leaves, some of which may cluster.
841 *
842 * We need to expel at least two leaves out of a set consisting
843 * of the leaves in the node and the new leaf. The current meta
844 * pointers can just be copied as they shouldn't cluster with
845 * any of the leaves. If all the old leaves cluster in one slot
846 * and the new leaf does not, they all go and the new leaf stays.
847 *
848 * We need a new node (n0) to replace the current one and a new
849 * node to take the expelled nodes (n1).
850 */
851 new_n0->back_pointer = node->back_pointer;
852 new_n0->parent_slot = node->parent_slot;
853 edit->set[0].ptr = assoc_array_parent_link(edit->array,
854 new_n0->back_pointer,
855 new_n0->parent_slot);
856 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
857 }
858
859 assoc_array_split_node(edit, node, new_n0, new_n1);
860 edit->excised_meta[0] = assoc_array_node_to_ptr(node);
861 pr_devel("<--%s() = ok [split node]\n", __func__);
862 return true;
863}
864
865/*
866 * Handle insertion into the middle of a shortcut.
867 */
868static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
869 const struct assoc_array_ops *ops,
870 struct assoc_array_walk_result *result)
871{
872 struct assoc_array_shortcut *shortcut, *new_s0, *new_s1;
873 struct assoc_array_node *new_n0, *side;
874 unsigned long sc_segments, dissimilarity, blank;
875 size_t keylen;
876 int level, sc_level, diff;
877 int sc_slot;
878
879 shortcut = result->wrong_shortcut.shortcut;
880 level = result->wrong_shortcut.level;
881 sc_level = result->wrong_shortcut.sc_level;
882 sc_segments = result->wrong_shortcut.sc_segments;
883 dissimilarity = result->wrong_shortcut.dissimilarity;
884
885 pr_devel("-->%s(ix=%d dis=%lx scix=%d)\n",
886 __func__, level, dissimilarity, sc_level);
887
888 /* We need to split a shortcut and insert a node between the two
889 * pieces. Zero-length pieces will be dispensed with entirely.
890 *
891 * First of all, we need to find out in which level the first
892 * difference was.
893 */
894 diff = __ffs(dissimilarity);
895 diff &= ~ASSOC_ARRAY_LEVEL_STEP_MASK;
896 diff += sc_level & ~ASSOC_ARRAY_KEY_CHUNK_MASK;
897 pr_devel("diff=%d\n", diff);
898
899 BUG_ON(shortcut->back_pointer &&
900 !assoc_array_ptr_is_node(shortcut->back_pointer));
901 edit->set[0].ptr = assoc_array_parent_link(edit->array,
902 shortcut->back_pointer,
903 shortcut->parent_slot);
904
905 edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);
906
907 /* Create a new node now since we're going to need it anyway */
908 new_n0 = kzalloc_obj(struct assoc_array_node);
909 if (!new_n0)
910 return false;
911 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
912 edit->adjust_count_on = new_n0;
913
914 /* Insert a new shortcut before the new node if this segment isn't of
915 * zero length - otherwise we just connect the new node directly to the
916 * parent.
917 */
918 if (shortcut->back_pointer)
919 level += ASSOC_ARRAY_LEVEL_STEP;
920 if (diff > level) {
921 pr_devel("pre-shortcut %d...%d\n", level, diff);
922 keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
923 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
924
925 new_s0 = kzalloc_flex(*new_s0, index_key, keylen);
926 if (!new_s0)
927 return false;
928 edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);
929 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
930 new_s0->back_pointer = shortcut->back_pointer;
931 new_s0->parent_slot = shortcut->parent_slot;
932 new_s0->next_node = assoc_array_node_to_ptr(new_n0);
933 new_s0->skip_to_level = diff;
934
935 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
936 new_n0->parent_slot = 0;
937
938 memcpy(new_s0->index_key, shortcut->index_key,
939 flex_array_size(new_s0, index_key, keylen));
940
941 if (diff & ASSOC_ARRAY_KEY_CHUNK_MASK) {
942 blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
943 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);
944 new_s0->index_key[keylen - 1] &= ~blank;
945 }
946 } else {
947 pr_devel("no pre-shortcut\n");
948 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
949 new_n0->back_pointer = shortcut->back_pointer;
950 new_n0->parent_slot = shortcut->parent_slot;
951 }
952
953 side = assoc_array_ptr_to_node(shortcut->next_node);
954 new_n0->nr_leaves_on_branch = side->nr_leaves_on_branch;
955
956 /* We need to know which slot in the new node is going to take a
957 * metadata pointer.
958 */
959 sc_slot = sc_segments >> (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
960 sc_slot &= ASSOC_ARRAY_FAN_MASK;
961
962 pr_devel("new slot %lx >> %d -> %d\n",
963 sc_segments, diff & ASSOC_ARRAY_KEY_CHUNK_MASK, sc_slot);
964
965 /* Determine whether we need to follow the new node with a replacement
966 * for the current shortcut. We could in theory reuse the current
967 * shortcut if its parent slot number doesn't change - but that's a
968 * 1-in-16 chance so not worth expending the code upon.
969 */
970 level = diff + ASSOC_ARRAY_LEVEL_STEP;
971 if (level < shortcut->skip_to_level) {
972 pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level);
973 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
974 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
975
976 new_s1 = kzalloc_flex(*new_s1, index_key, keylen);
977 if (!new_s1)
978 return false;
979 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);
980
981 new_s1->back_pointer = assoc_array_node_to_ptr(new_n0);
982 new_s1->parent_slot = sc_slot;
983 new_s1->next_node = shortcut->next_node;
984 new_s1->skip_to_level = shortcut->skip_to_level;
985
986 new_n0->slots[sc_slot] = assoc_array_shortcut_to_ptr(new_s1);
987
988 memcpy(new_s1->index_key, shortcut->index_key,
989 flex_array_size(new_s1, index_key, keylen));
990
991 edit->set[1].ptr = &side->back_pointer;
992 edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);
993 } else {
994 pr_devel("no post-shortcut\n");
995
996 /* We don't have to replace the pointed-to node as long as we
997 * use memory barriers to make sure the parent slot number is
998 * changed before the back pointer (the parent slot number is
999 * irrelevant to the old parent shortcut).
1000 */
1001 new_n0->slots[sc_slot] = shortcut->next_node;
1002 edit->set_parent_slot[0].p = &side->parent_slot;
1003 edit->set_parent_slot[0].to = sc_slot;
1004 edit->set[1].ptr = &side->back_pointer;
1005 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
1006 }
1007
1008 /* Install the new leaf in a spare slot in the new node. */
1009 if (sc_slot == 0)
1010 edit->leaf_p = &new_n0->slots[1];
1011 else
1012 edit->leaf_p = &new_n0->slots[0];
1013
1014 pr_devel("<--%s() = ok [split shortcut]\n", __func__);
1015 return true;
1016}
1017
1018/**
1019 * assoc_array_insert - Script insertion of an object into an associative array
1020 * @array: The array to insert into.
1021 * @ops: The operations to use.
1022 * @index_key: The key to insert at.
1023 * @object: The object to insert.
1024 *
1025 * Precalculate and preallocate a script for the insertion or replacement of an
1026 * object in an associative array. This results in an edit script that can
1027 * either be applied or cancelled.
1028 *
1029 * The function returns a pointer to an edit script or -ENOMEM.
1030 *
1031 * The caller should lock against other modifications and must continue to hold
1032 * the lock until assoc_array_apply_edit() has been called.
1033 *
1034 * Accesses to the tree may take place concurrently with this function,
1035 * provided they hold the RCU read lock.
1036 */
1037struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
1038 const struct assoc_array_ops *ops,
1039 const void *index_key,
1040 void *object)
1041{
1042 struct assoc_array_walk_result result;
1043 struct assoc_array_edit *edit;
1044
1045 pr_devel("-->%s()\n", __func__);
1046
1047 /* The leaf pointer we're given must not have the bottom bit set as we
1048 * use those for type-marking the pointer. NULL pointers are also not
1049 * allowed as they indicate an empty slot but we have to allow them
1050 * here as they can be updated later.
1051 */
1052 BUG_ON(assoc_array_ptr_is_meta(object));
1053
1054 edit = kzalloc_obj(struct assoc_array_edit);
1055 if (!edit)
1056 return ERR_PTR(-ENOMEM);
1057 edit->array = array;
1058 edit->ops = ops;
1059 edit->leaf = assoc_array_leaf_to_ptr(object);
1060 edit->adjust_count_by = 1;
1061
1062 switch (assoc_array_walk(array, ops, index_key, &result)) {
1063 case assoc_array_walk_tree_empty:
1064 /* Allocate a root node if there isn't one yet */
1065 if (!assoc_array_insert_in_empty_tree(edit))
1066 goto enomem;
1067 return edit;
1068
1069 case assoc_array_walk_found_terminal_node:
1070 /* We found a node that doesn't have a node/shortcut pointer in
1071 * the slot corresponding to the index key that we have to
1072 * follow.
1073 */
1074 if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,
1075 &result))
1076 goto enomem;
1077 return edit;
1078
1079 case assoc_array_walk_found_wrong_shortcut:
1080 /* We found a shortcut that didn't match our key in a slot we
1081 * needed to follow.
1082 */
1083 if (!assoc_array_insert_mid_shortcut(edit, ops, &result))
1084 goto enomem;
1085 return edit;
1086 }
1087
1088enomem:
1089 /* Clean up after an out of memory error */
1090 pr_devel("enomem\n");
1091 assoc_array_cancel_edit(edit);
1092 return ERR_PTR(-ENOMEM);
1093}
1094
1095/**
1096 * assoc_array_insert_set_object - Set the new object pointer in an edit script
1097 * @edit: The edit script to modify.
1098 * @object: The object pointer to set.
1099 *
1100 * Change the object to be inserted in an edit script. The object pointed to
1101 * by the old object is not freed. This must be done prior to applying the
1102 * script.
1103 */
1104void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)
1105{
1106 BUG_ON(!object);
1107 edit->leaf = assoc_array_leaf_to_ptr(object);
1108}
1109
1110struct assoc_array_delete_collapse_context {
1111 struct assoc_array_node *node;
1112 const void *skip_leaf;
1113 int slot;
1114};
1115
1116/*
1117 * Subtree collapse to node iterator.
1118 */
1119static int assoc_array_delete_collapse_iterator(const void *leaf,
1120 void *iterator_data)
1121{
1122 struct assoc_array_delete_collapse_context *collapse = iterator_data;
1123
1124 if (leaf == collapse->skip_leaf)
1125 return 0;
1126
1127 BUG_ON(collapse->slot >= ASSOC_ARRAY_FAN_OUT);
1128
1129 collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf);
1130 return 0;
1131}
1132
1133/*
1134 * Deleting a leaf from node leaves its subtree with FAN_OUT or fewer leaves:
1135 * collapse the subtree into one new node, together with as much of the tree
1136 * above it as also fits. Returns false if the new node cannot be allocated.
1137 */
1138static bool assoc_array_delete_collapse(struct assoc_array_edit *edit,
1139 struct assoc_array_node *node)
1140{
1141 struct assoc_array_delete_collapse_context collapse;
1142 struct assoc_array_node *parent, *grandparent, *new_n0;
1143 struct assoc_array_ptr *ptr;
1144 bool has_meta;
1145 int i;
1146
1147 /* First of all, we need to know if this node has metadata so
1148 * that we don't try collapsing if all the leaves are already
1149 * here.
1150 */
1151 has_meta = false;
1152 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
1153 ptr = node->slots[i];
1154 if (assoc_array_ptr_is_meta(ptr)) {
1155 has_meta = true;
1156 break;
1157 }
1158 }
1159
1160 pr_devel("leaves: %ld [m=%d]\n",
1161 node->nr_leaves_on_branch - 1, has_meta);
1162
1163 /* Look further up the tree to see if we can collapse this node
1164 * into a more proximal node too.
1165 */
1166 for (parent = node;; parent = grandparent) {
1167 pr_devel("collapse subtree: %ld\n", parent->nr_leaves_on_branch);
1168
1169 ptr = parent->back_pointer;
1170 if (ptr && assoc_array_ptr_is_shortcut(ptr))
1171 ptr = assoc_array_ptr_to_shortcut(ptr)->back_pointer;
1172 if (!ptr)
1173 break;
1174
1175 grandparent = assoc_array_ptr_to_node(ptr);
1176 if (grandparent->nr_leaves_on_branch > ASSOC_ARRAY_FAN_OUT + 1)
1177 break;
1178 }
1179
1180 /* There's no point collapsing if the original node has no meta
1181 * pointers to discard and if we didn't merge into one of that
1182 * node's ancestry.
1183 */
1184 if (has_meta || parent != node) {
1185 node = parent;
1186
1187 /* Create a new node to collapse into */
1188 new_n0 = kzalloc_obj(struct assoc_array_node);
1189 if (!new_n0)
1190 return false;
1191 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
1192
1193 new_n0->back_pointer = node->back_pointer;
1194 new_n0->parent_slot = node->parent_slot;
1195 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
1196 edit->adjust_count_on = new_n0;
1197
1198 collapse.node = new_n0;
1199 collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);
1200 collapse.slot = 0;
1201 assoc_array_subtree_iterate(assoc_array_node_to_ptr(node),
1202 node->back_pointer,
1203 assoc_array_delete_collapse_iterator,
1204 &collapse);
1205 pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch);
1206 BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1);
1207
1208 BUG_ON(node->back_pointer &&
1209 assoc_array_ptr_is_leaf(node->back_pointer));
1210 edit->set[1].ptr = assoc_array_parent_link(edit->array,
1211 node->back_pointer,
1212 node->parent_slot);
1213 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
1214 edit->excised_subtree = assoc_array_node_to_ptr(node);
1215 }
1216 return true;
1217}
1218
1219/**
1220 * assoc_array_delete - Script deletion of an object from an associative array
1221 * @array: The array to search.
1222 * @ops: The operations to use.
1223 * @index_key: The key to the object.
1224 *
1225 * Precalculate and preallocate a script for the deletion of an object from an
1226 * associative array. This results in an edit script that can either be
1227 * applied or cancelled.
1228 *
1229 * The function returns a pointer to an edit script if the object was found,
1230 * NULL if the object was not found or -ENOMEM.
1231 *
1232 * The caller should lock against other modifications and must continue to hold
1233 * the lock until assoc_array_apply_edit() has been called.
1234 *
1235 * Accesses to the tree may take place concurrently with this function,
1236 * provided they hold the RCU read lock.
1237 */
1238struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
1239 const struct assoc_array_ops *ops,
1240 const void *index_key)
1241{
1242 struct assoc_array_walk_result result;
1243 struct assoc_array_node *node;
1244 struct assoc_array_edit *edit;
1245 struct assoc_array_ptr *ptr;
1246 int slot;
1247
1248 pr_devel("-->%s()\n", __func__);
1249
1250 edit = kzalloc_obj(struct assoc_array_edit);
1251 if (!edit)
1252 return ERR_PTR(-ENOMEM);
1253 edit->array = array;
1254 edit->ops = ops;
1255 edit->adjust_count_by = -1;
1256
1257 node = NULL;
1258 slot = ASSOC_ARRAY_FAN_OUT;
1259 if (assoc_array_walk(array, ops, index_key, &result) ==
1260 assoc_array_walk_found_terminal_node) {
1261 /* We found a node that should contain the leaf we've been
1262 * asked to remove - *if* it's in the tree.
1263 */
1264 pr_devel("terminal_node\n");
1265 node = result.terminal_node.node;
1266
1267 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1268 ptr = node->slots[slot];
1269 if (ptr &&
1270 assoc_array_ptr_is_leaf(ptr) &&
1271 ops->compare_object(assoc_array_ptr_to_leaf(ptr),
1272 index_key))
1273 break;
1274 }
1275 }
1276 if (slot == ASSOC_ARRAY_FAN_OUT) {
1277 assoc_array_cancel_edit(edit);
1278 pr_devel("not found\n");
1279 return NULL;
1280 }
1281
1282 BUG_ON(array->nr_leaves_on_tree <= 0);
1283
1284 /* In the simplest form of deletion we just clear the slot and release
1285 * the leaf after a suitable interval.
1286 */
1287 edit->dead_leaf = node->slots[slot];
1288 edit->set[0].ptr = &node->slots[slot];
1289 edit->set[0].to = NULL;
1290 edit->adjust_count_on = node;
1291
1292 /* If that concludes erasure of the last leaf, then delete the entire
1293 * internal array.
1294 */
1295 if (array->nr_leaves_on_tree == 1) {
1296 edit->set[1].ptr = &array->root;
1297 edit->set[1].to = NULL;
1298 edit->adjust_count_on = NULL;
1299 edit->excised_subtree = array->root;
1300 pr_devel("all gone\n");
1301 return edit;
1302 }
1303
1304 /* However, we'd also like to clear up some metadata blocks if we
1305 * possibly can.
1306 *
1307 * We go for a simple algorithm of: if this node has FAN_OUT or fewer
1308 * leaves in it, then attempt to collapse it - and attempt to
1309 * recursively collapse up the tree.
1310 *
1311 * We could also try and collapse in partially filled subtrees to take
1312 * up space in this node.
1313 */
1314 if (node->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1 &&
1315 !assoc_array_delete_collapse(edit, node)) {
1316 /* Clean up after an out of memory error */
1317 pr_devel("enomem\n");
1318 assoc_array_cancel_edit(edit);
1319 return ERR_PTR(-ENOMEM);
1320 }
1321
1322 return edit;
1323}
1324
1325/**
1326 * assoc_array_clear - Script deletion of all objects from an associative array
1327 * @array: The array to clear.
1328 * @ops: The operations to use.
1329 *
1330 * Precalculate and preallocate a script for the deletion of all the objects
1331 * from an associative array. This results in an edit script that can either
1332 * be applied or cancelled.
1333 *
1334 * The function returns a pointer to an edit script if there are objects to be
1335 * deleted, NULL if there are no objects in the array or -ENOMEM.
1336 *
1337 * The caller should lock against other modifications and must continue to hold
1338 * the lock until assoc_array_apply_edit() has been called.
1339 *
1340 * Accesses to the tree may take place concurrently with this function,
1341 * provided they hold the RCU read lock.
1342 */
1343struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
1344 const struct assoc_array_ops *ops)
1345{
1346 struct assoc_array_edit *edit;
1347
1348 pr_devel("-->%s()\n", __func__);
1349
1350 if (!array->root)
1351 return NULL;
1352
1353 edit = kzalloc_obj(struct assoc_array_edit);
1354 if (!edit)
1355 return ERR_PTR(-ENOMEM);
1356 edit->array = array;
1357 edit->ops = ops;
1358 edit->set[1].ptr = &array->root;
1359 edit->set[1].to = NULL;
1360 edit->excised_subtree = array->root;
1361 edit->ops_for_excised_subtree = ops;
1362 pr_devel("all gone\n");
1363 return edit;
1364}
1365
1366/*
1367 * Handle the deferred destruction after an applied edit.
1368 */
1369static void assoc_array_rcu_cleanup(struct rcu_head *head)
1370{
1371 struct assoc_array_edit *edit =
1372 container_of(head, struct assoc_array_edit, rcu);
1373 int i;
1374
1375 pr_devel("-->%s()\n", __func__);
1376
1377 if (edit->dead_leaf)
1378 edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));
1379 for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)
1380 if (edit->excised_meta[i])
1381 kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));
1382
1383 if (edit->excised_subtree) {
1384 BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));
1385 if (assoc_array_ptr_is_node(edit->excised_subtree)) {
1386 struct assoc_array_node *n =
1387 assoc_array_ptr_to_node(edit->excised_subtree);
1388 n->back_pointer = NULL;
1389 } else {
1390 struct assoc_array_shortcut *s =
1391 assoc_array_ptr_to_shortcut(edit->excised_subtree);
1392 s->back_pointer = NULL;
1393 }
1394 assoc_array_destroy_subtree(edit->excised_subtree,
1395 edit->ops_for_excised_subtree);
1396 }
1397
1398 kfree(edit);
1399}
1400
1401/**
1402 * assoc_array_apply_edit - Apply an edit script to an associative array
1403 * @edit: The script to apply.
1404 *
1405 * Apply an edit script to an associative array to effect an insertion,
1406 * deletion or clearance. As the edit script includes preallocated memory,
1407 * this is guaranteed not to fail.
1408 *
1409 * The edit script, dead objects and dead metadata will be scheduled for
1410 * destruction after an RCU grace period to permit those doing read-only
1411 * accesses on the array to continue to do so under the RCU read lock whilst
1412 * the edit is taking place.
1413 */
1414void assoc_array_apply_edit(struct assoc_array_edit *edit)
1415{
1416 struct assoc_array_shortcut *shortcut;
1417 struct assoc_array_node *node;
1418 struct assoc_array_ptr *ptr;
1419 int i;
1420
1421 pr_devel("-->%s()\n", __func__);
1422
1423 smp_wmb();
1424 if (edit->leaf_p)
1425 *edit->leaf_p = edit->leaf;
1426
1427 smp_wmb();
1428 for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)
1429 if (edit->set_parent_slot[i].p)
1430 *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;
1431
1432 smp_wmb();
1433 for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)
1434 if (edit->set_backpointers[i])
1435 *edit->set_backpointers[i] = edit->set_backpointers_to;
1436
1437 smp_wmb();
1438 for (i = 0; i < ARRAY_SIZE(edit->set); i++)
1439 if (edit->set[i].ptr)
1440 *edit->set[i].ptr = edit->set[i].to;
1441
1442 if (edit->array->root == NULL) {
1443 edit->array->nr_leaves_on_tree = 0;
1444 } else if (edit->adjust_count_on) {
1445 node = edit->adjust_count_on;
1446 for (;;) {
1447 node->nr_leaves_on_branch += edit->adjust_count_by;
1448
1449 ptr = node->back_pointer;
1450 if (!ptr)
1451 break;
1452 if (assoc_array_ptr_is_shortcut(ptr)) {
1453 shortcut = assoc_array_ptr_to_shortcut(ptr);
1454 ptr = shortcut->back_pointer;
1455 if (!ptr)
1456 break;
1457 }
1458 BUG_ON(!assoc_array_ptr_is_node(ptr));
1459 node = assoc_array_ptr_to_node(ptr);
1460 }
1461
1462 edit->array->nr_leaves_on_tree += edit->adjust_count_by;
1463 }
1464
1465 call_rcu(&edit->rcu, assoc_array_rcu_cleanup);
1466}
1467
1468/**
1469 * assoc_array_cancel_edit - Discard an edit script.
1470 * @edit: The script to discard.
1471 *
1472 * Free an edit script and all the preallocated data it holds without making
1473 * any changes to the associative array it was intended for.
1474 *
1475 * NOTE! In the case of an insertion script, this does _not_ release the leaf
1476 * that was to be inserted. That is left to the caller.
1477 */
1478void assoc_array_cancel_edit(struct assoc_array_edit *edit)
1479{
1480 struct assoc_array_ptr *ptr;
1481 int i;
1482
1483 pr_devel("-->%s()\n", __func__);
1484
1485 /* Clean up after an out of memory error */
1486 for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {
1487 ptr = edit->new_meta[i];
1488 if (ptr) {
1489 if (assoc_array_ptr_is_node(ptr))
1490 kfree(assoc_array_ptr_to_node(ptr));
1491 else
1492 kfree(assoc_array_ptr_to_shortcut(ptr));
1493 }
1494 }
1495 kfree(edit);
1496}
1497
1498/*
1499 * Where assoc_array_gc() has got to. It copies the tree depth first without
1500 * recursion: on reaching a subtree it copies it and carries on there, and on
1501 * finishing a node it climbs back up the old tree to the node above.
1502 */
1503struct assoc_array_gc_walk {
1504 struct assoc_array_node *node; /* The node being copied */
1505 struct assoc_array_node *new_n; /* Its copy */
1506 int slot; /* The next slot of node to look at */
1507 struct assoc_array_ptr *new_root; /* The root of the copy */
1508 unsigned long nr_leaves_on_tree;
1509 bool (*iterator)(void *object, void *iterator_data);
1510 void *iterator_data;
1511};
1512
1513/*
1514 * Copy the node at cursor, and the shortcut in front of it if there is one,
1515 * into the new tree at *link, below the copy of the node being worked on,
1516 * and work on that node next.
1517 */
1518static bool assoc_array_gc_copy(struct assoc_array_gc_walk *w,
1519 struct assoc_array_ptr *cursor,
1520 struct assoc_array_ptr **link)
1521{
1522 struct assoc_array_shortcut *shortcut, *new_s;
1523 struct assoc_array_node *new_n;
1524 struct assoc_array_ptr *new_parent;
1525 int keylen;
1526
1527 new_parent = w->new_n ? assoc_array_node_to_ptr(w->new_n) : NULL;
1528
1529 /* The node at this position is duplicated, and so is the shortcut in
1530 * front of it if there is one. The node is allocated first: the copy
1531 * of the shortcut starts out pointing at the old node, and must not be
1532 * in the new tree if the node cannot be allocated, or the cleanup
1533 * would follow it into the old tree.
1534 */
1535 new_n = kzalloc_obj(struct assoc_array_node);
1536 if (!new_n)
1537 return false;
1538
1539 if (assoc_array_ptr_is_shortcut(cursor)) {
1540 shortcut = assoc_array_ptr_to_shortcut(cursor);
1541 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
1542 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
1543 new_s = kmalloc_flex(*new_s, index_key, keylen);
1544 if (!new_s) {
1545 kfree(new_n);
1546 return false;
1547 }
1548 pr_devel("dup shortcut %p -> %p\n", shortcut, new_s);
1549 memcpy(new_s, shortcut, struct_size(new_s, index_key, keylen));
1550 new_s->back_pointer = new_parent;
1551 new_s->parent_slot = shortcut->parent_slot;
1552 *link = new_parent = assoc_array_shortcut_to_ptr(new_s);
1553 link = &new_s->next_node;
1554 cursor = shortcut->next_node;
1555 }
1556
1557 w->node = assoc_array_ptr_to_node(cursor);
1558 pr_devel("dup node %p -> %p\n", w->node, new_n);
1559 new_n->back_pointer = new_parent;
1560 new_n->parent_slot = w->node->parent_slot;
1561 *link = assoc_array_node_to_ptr(new_n);
1562 w->new_n = new_n;
1563 w->slot = 0;
1564 return true;
1565}
1566
1567/*
1568 * Carry on through the slots of the node being copied, putting the leaves
1569 * the iterator keeps into the copy, as far as the next pointer to a subtree.
1570 * Returns that pointer, with w->slot at it, or NULL when the node is done.
1571 */
1572static struct assoc_array_ptr *assoc_array_gc_next(struct assoc_array_gc_walk *w)
1573{
1574 struct assoc_array_ptr *ptr;
1575
1576 /* Filter across any leaves and gc any subtrees */
1577 for (; w->slot < ASSOC_ARRAY_FAN_OUT; w->slot++) {
1578 ptr = w->node->slots[w->slot];
1579 if (!ptr)
1580 continue;
1581
1582 if (assoc_array_ptr_is_leaf(ptr)) {
1583 if (w->iterator(assoc_array_ptr_to_leaf(ptr),
1584 w->iterator_data))
1585 /* The iterator will have done any reference
1586 * counting on the object for us.
1587 */
1588 w->new_n->slots[w->slot] = ptr;
1589 continue;
1590 }
1591
1592 return ptr;
1593 }
1594 return NULL;
1595}
1596
1597/*
1598 * Fold the children of a finished copy into it where their leaves fit in
1599 * its free slots, and count its leaves. Returns the number of free slots
1600 * left.
1601 */
1602static int assoc_array_gc_fold(struct assoc_array_node *new_n)
1603{
1604 struct assoc_array_ptr *ptr;
1605 bool retained;
1606 int slot, nr_free, next_slot, i;
1607
1608retry_compress:
1609 pr_devel("-- compress node %p --\n", new_n);
1610
1611 /* Count up the number of empty slots in this node and work out the
1612 * subtree leaf count.
1613 */
1614 new_n->nr_leaves_on_branch = 0;
1615 nr_free = 0;
1616 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1617 ptr = new_n->slots[slot];
1618 if (!ptr)
1619 nr_free++;
1620 else if (assoc_array_ptr_is_leaf(ptr))
1621 new_n->nr_leaves_on_branch++;
1622 }
1623 pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch);
1624
1625 /* See what we can fold in */
1626 retained = false;
1627 next_slot = 0;
1628 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1629 struct assoc_array_shortcut *s;
1630 struct assoc_array_node *child;
1631
1632 ptr = new_n->slots[slot];
1633 if (!ptr || assoc_array_ptr_is_leaf(ptr))
1634 continue;
1635
1636 s = NULL;
1637 if (assoc_array_ptr_is_shortcut(ptr)) {
1638 s = assoc_array_ptr_to_shortcut(ptr);
1639 ptr = s->next_node;
1640 }
1641
1642 child = assoc_array_ptr_to_node(ptr);
1643 new_n->nr_leaves_on_branch += child->nr_leaves_on_branch;
1644
1645 if (child->nr_leaves_on_branch <= nr_free + 1) {
1646 /* Fold the child node into this one */
1647 pr_devel("[%d] fold node %lu/%d [nx %d]\n",
1648 slot, child->nr_leaves_on_branch, nr_free + 1,
1649 next_slot);
1650
1651 /* We would already have reaped an intervening shortcut
1652 * on the way back up the tree.
1653 */
1654 BUG_ON(s);
1655
1656 new_n->slots[slot] = NULL;
1657 nr_free++;
1658 if (slot < next_slot)
1659 next_slot = slot;
1660 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
1661 struct assoc_array_ptr *p = child->slots[i];
1662 if (!p)
1663 continue;
1664 BUG_ON(assoc_array_ptr_is_meta(p));
1665 while (new_n->slots[next_slot])
1666 next_slot++;
1667 BUG_ON(next_slot >= ASSOC_ARRAY_FAN_OUT);
1668 new_n->slots[next_slot++] = p;
1669 nr_free--;
1670 }
1671 kfree(child);
1672 } else {
1673 pr_devel("[%d] retain node %lu/%d [nx %d]\n",
1674 slot, child->nr_leaves_on_branch, nr_free + 1,
1675 next_slot);
1676 retained = true;
1677 }
1678 }
1679
1680 if (retained && new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
1681 pr_devel("internal nodes remain despite enough space, retrying\n");
1682 goto retry_compress;
1683 }
1684 pr_devel("after: %lu\n", new_n->nr_leaves_on_branch);
1685 return nr_free;
1686}
1687
1688/*
1689 * The copy of the node being worked on is finished: fold its children into
1690 * it, then remove it if all it holds is a shortcut, or remove the shortcut
1691 * in front of it if it is small. Returns what is then the copy's parent, or
1692 * NULL if it is at the root, when the whole tree has been copied.
1693 */
1694static struct assoc_array_ptr *assoc_array_gc_pack(struct assoc_array_gc_walk *w)
1695{
1696 struct assoc_array_shortcut *new_s;
1697 struct assoc_array_node *new_n = w->new_n;
1698 struct assoc_array_ptr *ptr, *new_parent;
1699 int nr_free, slot;
1700
1701 nr_free = assoc_array_gc_fold(new_n);
1702 w->nr_leaves_on_tree = new_n->nr_leaves_on_branch;
1703
1704 /* Excise this node if it is singly occupied by a shortcut */
1705 if (nr_free == ASSOC_ARRAY_FAN_OUT - 1) {
1706 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++)
1707 if ((ptr = new_n->slots[slot]))
1708 break;
1709
1710 if (assoc_array_ptr_is_meta(ptr) &&
1711 assoc_array_ptr_is_shortcut(ptr)) {
1712 pr_devel("excise node %p with 1 shortcut\n", new_n);
1713 new_s = assoc_array_ptr_to_shortcut(ptr);
1714 new_parent = new_n->back_pointer;
1715 slot = new_n->parent_slot;
1716 kfree(new_n);
1717 if (!new_parent) {
1718 new_s->back_pointer = NULL;
1719 new_s->parent_slot = 0;
1720 w->new_root = ptr;
1721 return NULL;
1722 }
1723
1724 if (assoc_array_ptr_is_shortcut(new_parent)) {
1725 /* We can discard any preceding shortcut also */
1726 struct assoc_array_shortcut *s =
1727 assoc_array_ptr_to_shortcut(new_parent);
1728
1729 pr_devel("excise preceding shortcut\n");
1730
1731 new_parent = new_s->back_pointer = s->back_pointer;
1732 slot = new_s->parent_slot = s->parent_slot;
1733 kfree(s);
1734 if (!new_parent) {
1735 new_s->back_pointer = NULL;
1736 new_s->parent_slot = 0;
1737 w->new_root = ptr;
1738 return NULL;
1739 }
1740 }
1741
1742 new_s->back_pointer = new_parent;
1743 new_s->parent_slot = slot;
1744 assoc_array_ptr_to_node(new_parent)->slots[slot] = ptr;
1745 return new_parent;
1746 }
1747 }
1748
1749 /* Excise any shortcuts we might encounter that point to nodes that
1750 * only contain leaves.
1751 */
1752 ptr = new_n->back_pointer;
1753 if (!ptr)
1754 return NULL;
1755
1756 if (!assoc_array_ptr_is_shortcut(ptr))
1757 return ptr;
1758
1759 new_s = assoc_array_ptr_to_shortcut(ptr);
1760 new_parent = new_s->back_pointer;
1761 slot = new_s->parent_slot;
1762
1763 if (new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
1764 pr_devel("excise shortcut\n");
1765 new_n->back_pointer = new_parent;
1766 new_n->parent_slot = slot;
1767 kfree(new_s);
1768 if (!new_parent) {
1769 w->new_root = assoc_array_node_to_ptr(new_n);
1770 return NULL;
1771 }
1772
1773 assoc_array_ptr_to_node(new_parent)->slots[slot] =
1774 assoc_array_node_to_ptr(new_n);
1775 }
1776 return new_parent;
1777}
1778
1779/*
1780 * Go back up from the node just finished to the node above it, whose copy is
1781 * parent, and on to that node's next slot.
1782 */
1783static void assoc_array_gc_ascend(struct assoc_array_gc_walk *w,
1784 struct assoc_array_ptr *parent)
1785{
1786 struct assoc_array_shortcut *shortcut;
1787 struct assoc_array_ptr *ptr, *cursor;
1788 int slot;
1789
1790 w->new_n = assoc_array_ptr_to_node(parent);
1791
1792 ptr = w->node->back_pointer;
1793 if (assoc_array_ptr_is_shortcut(ptr)) {
1794 shortcut = assoc_array_ptr_to_shortcut(ptr);
1795 slot = shortcut->parent_slot;
1796 cursor = shortcut->back_pointer;
1797 } else {
1798 slot = w->node->parent_slot;
1799 cursor = ptr;
1800 }
1801 BUG_ON(!cursor);
1802 w->node = assoc_array_ptr_to_node(cursor);
1803 w->slot = slot + 1;
1804}
1805
1806/**
1807 * assoc_array_gc - Garbage collect an associative array.
1808 * @array: The array to clean.
1809 * @ops: The operations to use.
1810 * @iterator: A callback function to pass judgement on each object.
1811 * @iterator_data: Private data for the callback function.
1812 *
1813 * Collect garbage from an associative array and pack down the internal tree to
1814 * save memory.
1815 *
1816 * The iterator function is asked to pass judgement upon each object in the
1817 * array. If it returns false, the object is discard and if it returns true,
1818 * the object is kept. If it returns true, it must increment the object's
1819 * usage count (or whatever it needs to do to retain it) before returning.
1820 *
1821 * This function returns 0 if successful or -ENOMEM if out of memory. In the
1822 * latter case, the array is not changed.
1823 *
1824 * The caller should lock against other modifications and must continue to hold
1825 * the lock until assoc_array_apply_edit() has been called.
1826 *
1827 * Accesses to the tree may take place concurrently with this function,
1828 * provided they hold the RCU read lock.
1829 */
1830int assoc_array_gc(struct assoc_array *array,
1831 const struct assoc_array_ops *ops,
1832 bool (*iterator)(void *object, void *iterator_data),
1833 void *iterator_data)
1834{
1835 struct assoc_array_gc_walk w = {
1836 .iterator = iterator,
1837 .iterator_data = iterator_data,
1838 };
1839 struct assoc_array_edit *edit;
1840 struct assoc_array_ptr *ptr, *parent, **link;
1841
1842 pr_devel("-->%s()\n", __func__);
1843
1844 if (!array->root)
1845 return 0;
1846
1847 edit = kzalloc_obj(struct assoc_array_edit);
1848 if (!edit)
1849 return -ENOMEM;
1850 edit->array = array;
1851 edit->ops = ops;
1852 edit->ops_for_excised_subtree = ops;
1853 edit->set[0].ptr = &array->root;
1854 edit->excised_subtree = array->root;
1855
1856 ptr = array->root;
1857 link = &w.new_root;
1858 for (;;) {
1859 if (!assoc_array_gc_copy(&w, ptr, link))
1860 goto enomem;
1861
1862 /* Find the next subtree to copy: further on in this node, or,
1863 * when it is done, in the nodes above it.
1864 */
1865 while (!(ptr = assoc_array_gc_next(&w))) {
1866 parent = assoc_array_gc_pack(&w);
1867 if (!parent)
1868 goto copied;
1869 assoc_array_gc_ascend(&w, parent);
1870 }
1871 link = &w.new_n->slots[w.slot];
1872 }
1873
1874copied:
1875 edit->set[0].to = w.new_root;
1876 assoc_array_apply_edit(edit);
1877 array->nr_leaves_on_tree = w.nr_leaves_on_tree;
1878 return 0;
1879
1880enomem:
1881 pr_devel("enomem\n");
1882 assoc_array_destroy_subtree(w.new_root, edit->ops);
1883 kfree(edit);
1884 return -ENOMEM;
1885}