1 /* Generic associative array implementation.
3 * See Documentation/assoc_array.txt for information.
5 * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
6 * Written by David Howells (dhowells@redhat.com)
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public Licence
10 * as published by the Free Software Foundation; either version
11 * 2 of the Licence, or (at your option) any later version.
14 #include <linux/slab.h>
15 #include <linux/err.h>
16 #include <linux/assoc_array_priv.h>
19 * Iterate over an associative array. The caller must hold the RCU read lock
22 static int assoc_array_subtree_iterate(const struct assoc_array_ptr *root,
23 const struct assoc_array_ptr *stop,
24 int (*iterator)(const void *leaf,
28 const struct assoc_array_shortcut *shortcut;
29 const struct assoc_array_node *node;
30 const struct assoc_array_ptr *cursor, *ptr, *parent;
31 unsigned long has_meta;
37 if (assoc_array_ptr_is_shortcut(cursor)) {
38 /* Descend through a shortcut */
39 shortcut = assoc_array_ptr_to_shortcut(cursor);
40 smp_read_barrier_depends();
41 cursor = ACCESS_ONCE(shortcut->next_node);
44 node = assoc_array_ptr_to_node(cursor);
45 smp_read_barrier_depends();
48 /* We perform two passes of each node.
50 * The first pass does all the leaves in this node. This means we
51 * don't miss any leaves if the node is split up by insertion whilst
52 * we're iterating over the branches rooted here (we may, however, see
56 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
57 ptr = ACCESS_ONCE(node->slots[slot]);
58 has_meta |= (unsigned long)ptr;
59 if (ptr && assoc_array_ptr_is_leaf(ptr)) {
60 /* We need a barrier between the read of the pointer
61 * and dereferencing the pointer - but only if we are
62 * actually going to dereference it.
64 smp_read_barrier_depends();
66 /* Invoke the callback */
67 ret = iterator(assoc_array_ptr_to_leaf(ptr),
74 /* The second pass attends to all the metadata pointers. If we follow
75 * one of these we may find that we don't come back here, but rather go
76 * back to a replacement node with the leaves in a different layout.
78 * We are guaranteed to make progress, however, as the slot number for
79 * a particular portion of the key space cannot change - and we
80 * continue at the back pointer + 1.
82 if (!(has_meta & ASSOC_ARRAY_PTR_META_TYPE))
87 node = assoc_array_ptr_to_node(cursor);
88 smp_read_barrier_depends();
90 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
91 ptr = ACCESS_ONCE(node->slots[slot]);
92 if (assoc_array_ptr_is_meta(ptr)) {
99 /* Move up to the parent (may need to skip back over a shortcut) */
100 parent = ACCESS_ONCE(node->back_pointer);
101 slot = node->parent_slot;
105 if (assoc_array_ptr_is_shortcut(parent)) {
106 shortcut = assoc_array_ptr_to_shortcut(parent);
107 smp_read_barrier_depends();
109 parent = ACCESS_ONCE(shortcut->back_pointer);
110 slot = shortcut->parent_slot;
115 /* Ascend to next slot in parent node */
122 * assoc_array_iterate - Pass all objects in the array to a callback
123 * @array: The array to iterate over.
124 * @iterator: The callback function.
125 * @iterator_data: Private data for the callback function.
127 * Iterate over all the objects in an associative array. Each one will be
128 * presented to the iterator function.
130 * If the array is being modified concurrently with the iteration then it is
131 * possible that some objects in the array will be passed to the iterator
132 * callback more than once - though every object should be passed at least
133 * once. If this is undesirable then the caller must lock against modification
134 * for the duration of this function.
136 * The function will return 0 if no objects were in the array or else it will
137 * return the result of the last iterator function called. Iteration stops
138 * immediately if any call to the iteration function results in a non-zero
141 * The caller should hold the RCU read lock or better if concurrent
142 * modification is possible.
144 int assoc_array_iterate(const struct assoc_array *array,
145 int (*iterator)(const void *object,
146 void *iterator_data),
149 struct assoc_array_ptr *root = ACCESS_ONCE(array->root);
153 return assoc_array_subtree_iterate(root, NULL, iterator, iterator_data);
156 enum assoc_array_walk_status {
157 assoc_array_walk_tree_empty,
158 assoc_array_walk_found_terminal_node,
159 assoc_array_walk_found_wrong_shortcut,
162 struct assoc_array_walk_result {
164 struct assoc_array_node *node; /* Node in which leaf might be found */
169 struct assoc_array_shortcut *shortcut;
172 unsigned long sc_segments;
173 unsigned long dissimilarity;
178 * Navigate through the internal tree looking for the closest node to the key.
180 static enum assoc_array_walk_status
181 assoc_array_walk(const struct assoc_array *array,
182 const struct assoc_array_ops *ops,
183 const void *index_key,
184 struct assoc_array_walk_result *result)
186 struct assoc_array_shortcut *shortcut;
187 struct assoc_array_node *node;
188 struct assoc_array_ptr *cursor, *ptr;
189 unsigned long sc_segments, dissimilarity;
190 unsigned long segments;
191 int level, sc_level, next_sc_level;
194 pr_devel("-->%s()\n", __func__);
196 cursor = ACCESS_ONCE(array->root);
198 return assoc_array_walk_tree_empty;
202 /* Use segments from the key for the new leaf to navigate through the
203 * internal tree, skipping through nodes and shortcuts that are on
204 * route to the destination. Eventually we'll come to a slot that is
205 * either empty or contains a leaf at which point we've found a node in
206 * which the leaf we're looking for might be found or into which it
207 * should be inserted.
210 segments = ops->get_key_chunk(index_key, level);
211 pr_devel("segments[%d]: %lx\n", level, segments);
213 if (assoc_array_ptr_is_shortcut(cursor))
214 goto follow_shortcut;
217 node = assoc_array_ptr_to_node(cursor);
218 smp_read_barrier_depends();
220 slot = segments >> (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
221 slot &= ASSOC_ARRAY_FAN_MASK;
222 ptr = ACCESS_ONCE(node->slots[slot]);
224 pr_devel("consider slot %x [ix=%d type=%lu]\n",
225 slot, level, (unsigned long)ptr & 3);
227 if (!assoc_array_ptr_is_meta(ptr)) {
228 /* The node doesn't have a node/shortcut pointer in the slot
229 * corresponding to the index key that we have to follow.
231 result->terminal_node.node = node;
232 result->terminal_node.level = level;
233 result->terminal_node.slot = slot;
234 pr_devel("<--%s() = terminal_node\n", __func__);
235 return assoc_array_walk_found_terminal_node;
238 if (assoc_array_ptr_is_node(ptr)) {
239 /* There is a pointer to a node in the slot corresponding to
240 * this index key segment, so we need to follow it.
243 level += ASSOC_ARRAY_LEVEL_STEP;
244 if ((level & ASSOC_ARRAY_KEY_CHUNK_MASK) != 0)
249 /* There is a shortcut in the slot corresponding to the index key
250 * segment. We follow the shortcut if its partial index key matches
251 * this leaf's. Otherwise we need to split the shortcut.
255 shortcut = assoc_array_ptr_to_shortcut(cursor);
256 smp_read_barrier_depends();
257 pr_devel("shortcut to %d\n", shortcut->skip_to_level);
258 sc_level = level + ASSOC_ARRAY_LEVEL_STEP;
259 BUG_ON(sc_level > shortcut->skip_to_level);
262 /* Check the leaf against the shortcut's index key a word at a
263 * time, trimming the final word (the shortcut stores the index
264 * key completely from the root to the shortcut's target).
266 if ((sc_level & ASSOC_ARRAY_KEY_CHUNK_MASK) == 0)
267 segments = ops->get_key_chunk(index_key, sc_level);
269 sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
270 dissimilarity = segments ^ sc_segments;
272 if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) {
273 /* Trim segments that are beyond the shortcut */
274 int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
275 dissimilarity &= ~(ULONG_MAX << shift);
276 next_sc_level = shortcut->skip_to_level;
278 next_sc_level = sc_level + ASSOC_ARRAY_KEY_CHUNK_SIZE;
279 next_sc_level = round_down(next_sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
282 if (dissimilarity != 0) {
283 /* This shortcut points elsewhere */
284 result->wrong_shortcut.shortcut = shortcut;
285 result->wrong_shortcut.level = level;
286 result->wrong_shortcut.sc_level = sc_level;
287 result->wrong_shortcut.sc_segments = sc_segments;
288 result->wrong_shortcut.dissimilarity = dissimilarity;
289 return assoc_array_walk_found_wrong_shortcut;
292 sc_level = next_sc_level;
293 } while (sc_level < shortcut->skip_to_level);
295 /* The shortcut matches the leaf's index to this point. */
296 cursor = ACCESS_ONCE(shortcut->next_node);
297 if (((level ^ sc_level) & ~ASSOC_ARRAY_KEY_CHUNK_MASK) != 0) {
307 * assoc_array_find - Find an object by index key
308 * @array: The associative array to search.
309 * @ops: The operations to use.
310 * @index_key: The key to the object.
312 * Find an object in an associative array by walking through the internal tree
313 * to the node that should contain the object and then searching the leaves
314 * there. NULL is returned if the requested object was not found in the array.
316 * The caller must hold the RCU read lock or better.
318 void *assoc_array_find(const struct assoc_array *array,
319 const struct assoc_array_ops *ops,
320 const void *index_key)
322 struct assoc_array_walk_result result;
323 const struct assoc_array_node *node;
324 const struct assoc_array_ptr *ptr;
328 if (assoc_array_walk(array, ops, index_key, &result) !=
329 assoc_array_walk_found_terminal_node)
332 node = result.terminal_node.node;
333 smp_read_barrier_depends();
335 /* If the target key is available to us, it's has to be pointed to by
338 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
339 ptr = ACCESS_ONCE(node->slots[slot]);
340 if (ptr && assoc_array_ptr_is_leaf(ptr)) {
341 /* We need a barrier between the read of the pointer
342 * and dereferencing the pointer - but only if we are
343 * actually going to dereference it.
345 leaf = assoc_array_ptr_to_leaf(ptr);
346 smp_read_barrier_depends();
347 if (ops->compare_object(leaf, index_key))
356 * Destructively iterate over an associative array. The caller must prevent
357 * other simultaneous accesses.
359 static void assoc_array_destroy_subtree(struct assoc_array_ptr *root,
360 const struct assoc_array_ops *ops)
362 struct assoc_array_shortcut *shortcut;
363 struct assoc_array_node *node;
364 struct assoc_array_ptr *cursor, *parent = NULL;
367 pr_devel("-->%s()\n", __func__);
376 if (assoc_array_ptr_is_shortcut(cursor)) {
377 /* Descend through a shortcut */
378 pr_devel("[%d] shortcut\n", slot);
379 BUG_ON(!assoc_array_ptr_is_shortcut(cursor));
380 shortcut = assoc_array_ptr_to_shortcut(cursor);
381 BUG_ON(shortcut->back_pointer != parent);
382 BUG_ON(slot != -1 && shortcut->parent_slot != slot);
384 cursor = shortcut->next_node;
386 BUG_ON(!assoc_array_ptr_is_node(cursor));
389 pr_devel("[%d] node\n", slot);
390 node = assoc_array_ptr_to_node(cursor);
391 BUG_ON(node->back_pointer != parent);
392 BUG_ON(slot != -1 && node->parent_slot != slot);
396 pr_devel("Node %p [back=%p]\n", node, node->back_pointer);
397 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
398 struct assoc_array_ptr *ptr = node->slots[slot];
401 if (assoc_array_ptr_is_meta(ptr)) {
408 pr_devel("[%d] free leaf\n", slot);
409 ops->free_object(assoc_array_ptr_to_leaf(ptr));
413 parent = node->back_pointer;
414 slot = node->parent_slot;
415 pr_devel("free node\n");
420 /* Move back up to the parent (may need to free a shortcut on
422 if (assoc_array_ptr_is_shortcut(parent)) {
423 shortcut = assoc_array_ptr_to_shortcut(parent);
424 BUG_ON(shortcut->next_node != cursor);
426 parent = shortcut->back_pointer;
427 slot = shortcut->parent_slot;
428 pr_devel("free shortcut\n");
433 BUG_ON(!assoc_array_ptr_is_node(parent));
436 /* Ascend to next slot in parent node */
437 pr_devel("ascend to %p[%d]\n", parent, slot);
439 node = assoc_array_ptr_to_node(cursor);
445 * assoc_array_destroy - Destroy an associative array
446 * @array: The array to destroy.
447 * @ops: The operations to use.
449 * Discard all metadata and free all objects in an associative array. The
450 * array will be empty and ready to use again upon completion. This function
453 * The caller must prevent all other accesses whilst this takes place as no
454 * attempt is made to adjust pointers gracefully to permit RCU readlock-holding
455 * accesses to continue. On the other hand, no memory allocation is required.
457 void assoc_array_destroy(struct assoc_array *array,
458 const struct assoc_array_ops *ops)
460 assoc_array_destroy_subtree(array->root, ops);
465 * Handle insertion into an empty tree.
467 static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit)
469 struct assoc_array_node *new_n0;
471 pr_devel("-->%s()\n", __func__);
473 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
477 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
478 edit->leaf_p = &new_n0->slots[0];
479 edit->adjust_count_on = new_n0;
480 edit->set[0].ptr = &edit->array->root;
481 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
483 pr_devel("<--%s() = ok [no root]\n", __func__);
488 * Handle insertion into a terminal node.
490 static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
491 const struct assoc_array_ops *ops,
492 const void *index_key,
493 struct assoc_array_walk_result *result)
495 struct assoc_array_shortcut *shortcut, *new_s0;
496 struct assoc_array_node *node, *new_n0, *new_n1, *side;
497 struct assoc_array_ptr *ptr;
498 unsigned long dissimilarity, base_seg, blank;
502 int slot, next_slot, free_slot, i, j;
504 node = result->terminal_node.node;
505 level = result->terminal_node.level;
506 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot;
508 pr_devel("-->%s()\n", __func__);
510 /* We arrived at a node which doesn't have an onward node or shortcut
511 * pointer that we have to follow. This means that (a) the leaf we
512 * want must go here (either by insertion or replacement) or (b) we
513 * need to split this node and insert in one of the fragments.
517 /* Firstly, we have to check the leaves in this node to see if there's
518 * a matching one we should replace in place.
520 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
521 ptr = node->slots[i];
526 if (assoc_array_ptr_is_leaf(ptr) &&
527 ops->compare_object(assoc_array_ptr_to_leaf(ptr),
529 pr_devel("replace in slot %d\n", i);
530 edit->leaf_p = &node->slots[i];
531 edit->dead_leaf = node->slots[i];
532 pr_devel("<--%s() = ok [replace]\n", __func__);
537 /* If there is a free slot in this node then we can just insert the
540 if (free_slot >= 0) {
541 pr_devel("insert in free slot %d\n", free_slot);
542 edit->leaf_p = &node->slots[free_slot];
543 edit->adjust_count_on = node;
544 pr_devel("<--%s() = ok [insert]\n", __func__);
548 /* The node has no spare slots - so we're either going to have to split
549 * it or insert another node before it.
551 * Whatever, we're going to need at least two new nodes - so allocate
552 * those now. We may also need a new shortcut, but we deal with that
555 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
558 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
559 new_n1 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
562 edit->new_meta[1] = assoc_array_node_to_ptr(new_n1);
564 /* We need to find out how similar the leaves are. */
565 pr_devel("no spare slots\n");
567 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
568 ptr = node->slots[i];
569 if (assoc_array_ptr_is_meta(ptr)) {
570 edit->segment_cache[i] = 0xff;
574 base_seg = ops->get_object_key_chunk(
575 assoc_array_ptr_to_leaf(ptr), level);
576 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
577 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
581 pr_devel("have meta\n");
585 /* The node contains only leaves */
587 base_seg = edit->segment_cache[0];
588 for (i = 1; i < ASSOC_ARRAY_FAN_OUT; i++)
589 dissimilarity |= edit->segment_cache[i] ^ base_seg;
591 pr_devel("only leaves; dissimilarity=%lx\n", dissimilarity);
593 if ((dissimilarity & ASSOC_ARRAY_FAN_MASK) == 0) {
594 /* The old leaves all cluster in the same slot. We will need
595 * to insert a shortcut if the new node wants to cluster with them.
597 if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)
598 goto all_leaves_cluster_together;
600 /* Otherwise all the old leaves cluster in the same slot, but
601 * the new leaf wants to go into a different slot - so we
602 * create a new node (n0) to hold the new leaf and a pointer to
603 * a new node (n1) holding all the old leaves.
605 * This can be done by falling through to the node splitting
608 pr_devel("present leaves cluster but not new leaf\n");
612 pr_devel("split node\n");
614 /* We need to split the current node. The node must contain anything
615 * from a single leaf (in the one leaf case, this leaf will cluster
616 * with the new leaf) and the rest meta-pointers, to all leaves, some
617 * of which may cluster.
619 * It won't contain the case in which all the current leaves plus the
620 * new leaves want to cluster in the same slot.
622 * We need to expel at least two leaves out of a set consisting of the
623 * leaves in the node and the new leaf. The current meta pointers can
624 * just be copied as they shouldn't cluster with any of the leaves.
626 * We need a new node (n0) to replace the current one and a new node to
627 * take the expelled nodes (n1).
629 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
630 new_n0->back_pointer = node->back_pointer;
631 new_n0->parent_slot = node->parent_slot;
632 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
633 new_n1->parent_slot = -1; /* Need to calculate this */
636 pr_devel("do_split_node\n");
638 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
639 new_n1->nr_leaves_on_branch = 0;
641 /* Begin by finding two matching leaves. There have to be at least two
642 * that match - even if there are meta pointers - because any leaf that
643 * would match a slot with a meta pointer in it must be somewhere
644 * behind that meta pointer and cannot be here. Further, given N
645 * remaining leaf slots, we now have N+1 leaves to go in them.
647 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
648 slot = edit->segment_cache[i];
650 for (j = i + 1; j < ASSOC_ARRAY_FAN_OUT + 1; j++)
651 if (edit->segment_cache[j] == slot)
652 goto found_slot_for_multiple_occupancy;
654 found_slot_for_multiple_occupancy:
655 pr_devel("same slot: %x %x [%02x]\n", i, j, slot);
656 BUG_ON(i >= ASSOC_ARRAY_FAN_OUT);
657 BUG_ON(j >= ASSOC_ARRAY_FAN_OUT + 1);
658 BUG_ON(slot >= ASSOC_ARRAY_FAN_OUT);
660 new_n1->parent_slot = slot;
662 /* Metadata pointers cannot change slot */
663 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
664 if (assoc_array_ptr_is_meta(node->slots[i]))
665 new_n0->slots[i] = node->slots[i];
667 new_n0->slots[i] = NULL;
668 BUG_ON(new_n0->slots[slot] != NULL);
669 new_n0->slots[slot] = assoc_array_node_to_ptr(new_n1);
671 /* Filter the leaf pointers between the new nodes */
674 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
675 if (assoc_array_ptr_is_meta(node->slots[i]))
677 if (edit->segment_cache[i] == slot) {
678 new_n1->slots[next_slot++] = node->slots[i];
679 new_n1->nr_leaves_on_branch++;
683 } while (new_n0->slots[free_slot] != NULL);
684 new_n0->slots[free_slot] = node->slots[i];
688 pr_devel("filtered: f=%x n=%x\n", free_slot, next_slot);
690 if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {
693 } while (new_n0->slots[free_slot] != NULL);
694 edit->leaf_p = &new_n0->slots[free_slot];
695 edit->adjust_count_on = new_n0;
697 edit->leaf_p = &new_n1->slots[next_slot++];
698 edit->adjust_count_on = new_n1;
701 BUG_ON(next_slot <= 1);
703 edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);
704 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
705 if (edit->segment_cache[i] == 0xff) {
706 ptr = node->slots[i];
707 BUG_ON(assoc_array_ptr_is_leaf(ptr));
708 if (assoc_array_ptr_is_node(ptr)) {
709 side = assoc_array_ptr_to_node(ptr);
710 edit->set_backpointers[i] = &side->back_pointer;
712 shortcut = assoc_array_ptr_to_shortcut(ptr);
713 edit->set_backpointers[i] = &shortcut->back_pointer;
718 ptr = node->back_pointer;
720 edit->set[0].ptr = &edit->array->root;
721 else if (assoc_array_ptr_is_node(ptr))
722 edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];
724 edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node;
725 edit->excised_meta[0] = assoc_array_node_to_ptr(node);
726 pr_devel("<--%s() = ok [split node]\n", __func__);
729 all_leaves_cluster_together:
730 /* All the leaves, new and old, want to cluster together in this node
731 * in the same slot, so we have to replace this node with a shortcut to
732 * skip over the identical parts of the key and then place a pair of
733 * nodes, one inside the other, at the end of the shortcut and
734 * distribute the keys between them.
736 * Firstly we need to work out where the leaves start diverging as a
737 * bit position into their keys so that we know how big the shortcut
740 * We only need to make a single pass of N of the N+1 leaves because if
741 * any keys differ between themselves at bit X then at least one of
742 * them must also differ with the base key at bit X or before.
744 pr_devel("all leaves cluster together\n");
746 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
747 int x = ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]),
754 BUG_ON(diff == INT_MAX);
755 BUG_ON(diff < level + ASSOC_ARRAY_LEVEL_STEP);
757 keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
758 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
760 new_s0 = kzalloc(sizeof(struct assoc_array_shortcut) +
761 keylen * sizeof(unsigned long), GFP_KERNEL);
764 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);
766 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
767 new_s0->back_pointer = node->back_pointer;
768 new_s0->parent_slot = node->parent_slot;
769 new_s0->next_node = assoc_array_node_to_ptr(new_n0);
770 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
771 new_n0->parent_slot = 0;
772 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
773 new_n1->parent_slot = -1; /* Need to calculate this */
775 new_s0->skip_to_level = level = diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK;
776 pr_devel("skip_to_level = %d [diff %d]\n", level, diff);
779 for (i = 0; i < keylen; i++)
780 new_s0->index_key[i] =
781 ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE);
783 blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
784 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank);
785 new_s0->index_key[keylen - 1] &= ~blank;
787 /* This now reduces to a node splitting exercise for which we'll need
788 * to regenerate the disparity table.
790 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
791 ptr = node->slots[i];
792 base_seg = ops->get_object_key_chunk(assoc_array_ptr_to_leaf(ptr),
794 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
795 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
798 base_seg = ops->get_key_chunk(index_key, level);
799 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
800 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;
805 * Handle insertion into the middle of a shortcut.
807 static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
808 const struct assoc_array_ops *ops,
809 struct assoc_array_walk_result *result)
811 struct assoc_array_shortcut *shortcut, *new_s0, *new_s1;
812 struct assoc_array_node *node, *new_n0, *side;
813 unsigned long sc_segments, dissimilarity, blank;
815 int level, sc_level, diff;
818 shortcut = result->wrong_shortcut.shortcut;
819 level = result->wrong_shortcut.level;
820 sc_level = result->wrong_shortcut.sc_level;
821 sc_segments = result->wrong_shortcut.sc_segments;
822 dissimilarity = result->wrong_shortcut.dissimilarity;
824 pr_devel("-->%s(ix=%d dis=%lx scix=%d)\n",
825 __func__, level, dissimilarity, sc_level);
827 /* We need to split a shortcut and insert a node between the two
828 * pieces. Zero-length pieces will be dispensed with entirely.
830 * First of all, we need to find out in which level the first
833 diff = __ffs(dissimilarity);
834 diff &= ~ASSOC_ARRAY_LEVEL_STEP_MASK;
835 diff += sc_level & ~ASSOC_ARRAY_KEY_CHUNK_MASK;
836 pr_devel("diff=%d\n", diff);
838 if (!shortcut->back_pointer) {
839 edit->set[0].ptr = &edit->array->root;
840 } else if (assoc_array_ptr_is_node(shortcut->back_pointer)) {
841 node = assoc_array_ptr_to_node(shortcut->back_pointer);
842 edit->set[0].ptr = &node->slots[shortcut->parent_slot];
847 edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);
849 /* Create a new node now since we're going to need it anyway */
850 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
853 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
854 edit->adjust_count_on = new_n0;
856 /* Insert a new shortcut before the new node if this segment isn't of
857 * zero length - otherwise we just connect the new node directly to the
860 level += ASSOC_ARRAY_LEVEL_STEP;
862 pr_devel("pre-shortcut %d...%d\n", level, diff);
863 keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
864 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
866 new_s0 = kzalloc(sizeof(struct assoc_array_shortcut) +
867 keylen * sizeof(unsigned long), GFP_KERNEL);
870 edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);
871 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
872 new_s0->back_pointer = shortcut->back_pointer;
873 new_s0->parent_slot = shortcut->parent_slot;
874 new_s0->next_node = assoc_array_node_to_ptr(new_n0);
875 new_s0->skip_to_level = diff;
877 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
878 new_n0->parent_slot = 0;
880 memcpy(new_s0->index_key, shortcut->index_key,
881 keylen * sizeof(unsigned long));
883 blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
884 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);
885 new_s0->index_key[keylen - 1] &= ~blank;
887 pr_devel("no pre-shortcut\n");
888 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
889 new_n0->back_pointer = shortcut->back_pointer;
890 new_n0->parent_slot = shortcut->parent_slot;
893 side = assoc_array_ptr_to_node(shortcut->next_node);
894 new_n0->nr_leaves_on_branch = side->nr_leaves_on_branch;
896 /* We need to know which slot in the new node is going to take a
899 sc_slot = sc_segments >> (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
900 sc_slot &= ASSOC_ARRAY_FAN_MASK;
902 pr_devel("new slot %lx >> %d -> %d\n",
903 sc_segments, diff & ASSOC_ARRAY_KEY_CHUNK_MASK, sc_slot);
905 /* Determine whether we need to follow the new node with a replacement
906 * for the current shortcut. We could in theory reuse the current
907 * shortcut if its parent slot number doesn't change - but that's a
908 * 1-in-16 chance so not worth expending the code upon.
910 level = diff + ASSOC_ARRAY_LEVEL_STEP;
911 if (level < shortcut->skip_to_level) {
912 pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level);
913 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
914 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
916 new_s1 = kzalloc(sizeof(struct assoc_array_shortcut) +
917 keylen * sizeof(unsigned long), GFP_KERNEL);
920 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);
922 new_s1->back_pointer = assoc_array_node_to_ptr(new_n0);
923 new_s1->parent_slot = sc_slot;
924 new_s1->next_node = shortcut->next_node;
925 new_s1->skip_to_level = shortcut->skip_to_level;
927 new_n0->slots[sc_slot] = assoc_array_shortcut_to_ptr(new_s1);
929 memcpy(new_s1->index_key, shortcut->index_key,
930 keylen * sizeof(unsigned long));
932 edit->set[1].ptr = &side->back_pointer;
933 edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);
935 pr_devel("no post-shortcut\n");
937 /* We don't have to replace the pointed-to node as long as we
938 * use memory barriers to make sure the parent slot number is
939 * changed before the back pointer (the parent slot number is
940 * irrelevant to the old parent shortcut).
942 new_n0->slots[sc_slot] = shortcut->next_node;
943 edit->set_parent_slot[0].p = &side->parent_slot;
944 edit->set_parent_slot[0].to = sc_slot;
945 edit->set[1].ptr = &side->back_pointer;
946 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
949 /* Install the new leaf in a spare slot in the new node. */
951 edit->leaf_p = &new_n0->slots[1];
953 edit->leaf_p = &new_n0->slots[0];
955 pr_devel("<--%s() = ok [split shortcut]\n", __func__);
960 * assoc_array_insert - Script insertion of an object into an associative array
961 * @array: The array to insert into.
962 * @ops: The operations to use.
963 * @index_key: The key to insert at.
964 * @object: The object to insert.
966 * Precalculate and preallocate a script for the insertion or replacement of an
967 * object in an associative array. This results in an edit script that can
968 * either be applied or cancelled.
970 * The function returns a pointer to an edit script or -ENOMEM.
972 * The caller should lock against other modifications and must continue to hold
973 * the lock until assoc_array_apply_edit() has been called.
975 * Accesses to the tree may take place concurrently with this function,
976 * provided they hold the RCU read lock.
978 struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
979 const struct assoc_array_ops *ops,
980 const void *index_key,
983 struct assoc_array_walk_result result;
984 struct assoc_array_edit *edit;
986 pr_devel("-->%s()\n", __func__);
988 /* The leaf pointer we're given must not have the bottom bit set as we
989 * use those for type-marking the pointer. NULL pointers are also not
990 * allowed as they indicate an empty slot but we have to allow them
991 * here as they can be updated later.
993 BUG_ON(assoc_array_ptr_is_meta(object));
995 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
997 return ERR_PTR(-ENOMEM);
1000 edit->leaf = assoc_array_leaf_to_ptr(object);
1001 edit->adjust_count_by = 1;
1003 switch (assoc_array_walk(array, ops, index_key, &result)) {
1004 case assoc_array_walk_tree_empty:
1005 /* Allocate a root node if there isn't one yet */
1006 if (!assoc_array_insert_in_empty_tree(edit))
1010 case assoc_array_walk_found_terminal_node:
1011 /* We found a node that doesn't have a node/shortcut pointer in
1012 * the slot corresponding to the index key that we have to
1015 if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,
1020 case assoc_array_walk_found_wrong_shortcut:
1021 /* We found a shortcut that didn't match our key in a slot we
1024 if (!assoc_array_insert_mid_shortcut(edit, ops, &result))
1030 /* Clean up after an out of memory error */
1031 pr_devel("enomem\n");
1032 assoc_array_cancel_edit(edit);
1033 return ERR_PTR(-ENOMEM);
1037 * assoc_array_insert_set_object - Set the new object pointer in an edit script
1038 * @edit: The edit script to modify.
1039 * @object: The object pointer to set.
1041 * Change the object to be inserted in an edit script. The object pointed to
1042 * by the old object is not freed. This must be done prior to applying the
1045 void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)
1048 edit->leaf = assoc_array_leaf_to_ptr(object);
1051 struct assoc_array_delete_collapse_context {
1052 struct assoc_array_node *node;
1053 const void *skip_leaf;
1058 * Subtree collapse to node iterator.
1060 static int assoc_array_delete_collapse_iterator(const void *leaf,
1061 void *iterator_data)
1063 struct assoc_array_delete_collapse_context *collapse = iterator_data;
1065 if (leaf == collapse->skip_leaf)
1068 BUG_ON(collapse->slot >= ASSOC_ARRAY_FAN_OUT);
1070 collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf);
1075 * assoc_array_delete - Script deletion of an object from an associative array
1076 * @array: The array to search.
1077 * @ops: The operations to use.
1078 * @index_key: The key to the object.
1080 * Precalculate and preallocate a script for the deletion of an object from an
1081 * associative array. This results in an edit script that can either be
1082 * applied or cancelled.
1084 * The function returns a pointer to an edit script if the object was found,
1085 * NULL if the object was not found or -ENOMEM.
1087 * The caller should lock against other modifications and must continue to hold
1088 * the lock until assoc_array_apply_edit() has been called.
1090 * Accesses to the tree may take place concurrently with this function,
1091 * provided they hold the RCU read lock.
1093 struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
1094 const struct assoc_array_ops *ops,
1095 const void *index_key)
1097 struct assoc_array_delete_collapse_context collapse;
1098 struct assoc_array_walk_result result;
1099 struct assoc_array_node *node, *new_n0;
1100 struct assoc_array_edit *edit;
1101 struct assoc_array_ptr *ptr;
1105 pr_devel("-->%s()\n", __func__);
1107 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1109 return ERR_PTR(-ENOMEM);
1110 edit->array = array;
1112 edit->adjust_count_by = -1;
1114 switch (assoc_array_walk(array, ops, index_key, &result)) {
1115 case assoc_array_walk_found_terminal_node:
1116 /* We found a node that should contain the leaf we've been
1117 * asked to remove - *if* it's in the tree.
1119 pr_devel("terminal_node\n");
1120 node = result.terminal_node.node;
1122 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1123 ptr = node->slots[slot];
1125 assoc_array_ptr_is_leaf(ptr) &&
1126 ops->compare_object(assoc_array_ptr_to_leaf(ptr),
1130 case assoc_array_walk_tree_empty:
1131 case assoc_array_walk_found_wrong_shortcut:
1133 assoc_array_cancel_edit(edit);
1134 pr_devel("not found\n");
1139 BUG_ON(array->nr_leaves_on_tree <= 0);
1141 /* In the simplest form of deletion we just clear the slot and release
1142 * the leaf after a suitable interval.
1144 edit->dead_leaf = node->slots[slot];
1145 edit->set[0].ptr = &node->slots[slot];
1146 edit->set[0].to = NULL;
1147 edit->adjust_count_on = node;
1149 /* If that concludes erasure of the last leaf, then delete the entire
1152 if (array->nr_leaves_on_tree == 1) {
1153 edit->set[1].ptr = &array->root;
1154 edit->set[1].to = NULL;
1155 edit->adjust_count_on = NULL;
1156 edit->excised_subtree = array->root;
1157 pr_devel("all gone\n");
1161 /* However, we'd also like to clear up some metadata blocks if we
1164 * We go for a simple algorithm of: if this node has FAN_OUT or fewer
1165 * leaves in it, then attempt to collapse it - and attempt to
1166 * recursively collapse up the tree.
1168 * We could also try and collapse in partially filled subtrees to take
1169 * up space in this node.
1171 if (node->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
1172 struct assoc_array_node *parent, *grandparent;
1173 struct assoc_array_ptr *ptr;
1175 /* First of all, we need to know if this node has metadata so
1176 * that we don't try collapsing if all the leaves are already
1180 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
1181 ptr = node->slots[i];
1182 if (assoc_array_ptr_is_meta(ptr)) {
1188 pr_devel("leaves: %ld [m=%d]\n",
1189 node->nr_leaves_on_branch - 1, has_meta);
1191 /* Look further up the tree to see if we can collapse this node
1192 * into a more proximal node too.
1196 pr_devel("collapse subtree: %ld\n", parent->nr_leaves_on_branch);
1198 ptr = parent->back_pointer;
1201 if (assoc_array_ptr_is_shortcut(ptr)) {
1202 struct assoc_array_shortcut *s = assoc_array_ptr_to_shortcut(ptr);
1203 ptr = s->back_pointer;
1208 grandparent = assoc_array_ptr_to_node(ptr);
1209 if (grandparent->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
1210 parent = grandparent;
1215 /* There's no point collapsing if the original node has no meta
1216 * pointers to discard and if we didn't merge into one of that
1219 if (has_meta || parent != node) {
1222 /* Create a new node to collapse into */
1223 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
1226 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
1228 new_n0->back_pointer = node->back_pointer;
1229 new_n0->parent_slot = node->parent_slot;
1230 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
1231 edit->adjust_count_on = new_n0;
1233 collapse.node = new_n0;
1234 collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);
1236 assoc_array_subtree_iterate(assoc_array_node_to_ptr(node),
1238 assoc_array_delete_collapse_iterator,
1240 pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch);
1241 BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1);
1243 if (!node->back_pointer) {
1244 edit->set[1].ptr = &array->root;
1245 } else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
1247 } else if (assoc_array_ptr_is_node(node->back_pointer)) {
1248 struct assoc_array_node *p =
1249 assoc_array_ptr_to_node(node->back_pointer);
1250 edit->set[1].ptr = &p->slots[node->parent_slot];
1251 } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) {
1252 struct assoc_array_shortcut *s =
1253 assoc_array_ptr_to_shortcut(node->back_pointer);
1254 edit->set[1].ptr = &s->next_node;
1256 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
1257 edit->excised_subtree = assoc_array_node_to_ptr(node);
1264 /* Clean up after an out of memory error */
1265 pr_devel("enomem\n");
1266 assoc_array_cancel_edit(edit);
1267 return ERR_PTR(-ENOMEM);
1271 * assoc_array_clear - Script deletion of all objects from an associative array
1272 * @array: The array to clear.
1273 * @ops: The operations to use.
1275 * Precalculate and preallocate a script for the deletion of all the objects
1276 * from an associative array. This results in an edit script that can either
1277 * be applied or cancelled.
1279 * The function returns a pointer to an edit script if there are objects to be
1280 * deleted, NULL if there are no objects in the array or -ENOMEM.
1282 * The caller should lock against other modifications and must continue to hold
1283 * the lock until assoc_array_apply_edit() has been called.
1285 * Accesses to the tree may take place concurrently with this function,
1286 * provided they hold the RCU read lock.
1288 struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
1289 const struct assoc_array_ops *ops)
1291 struct assoc_array_edit *edit;
1293 pr_devel("-->%s()\n", __func__);
1298 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1300 return ERR_PTR(-ENOMEM);
1301 edit->array = array;
1303 edit->set[1].ptr = &array->root;
1304 edit->set[1].to = NULL;
1305 edit->excised_subtree = array->root;
1306 edit->ops_for_excised_subtree = ops;
1307 pr_devel("all gone\n");
1312 * Handle the deferred destruction after an applied edit.
1314 static void assoc_array_rcu_cleanup(struct rcu_head *head)
1316 struct assoc_array_edit *edit =
1317 container_of(head, struct assoc_array_edit, rcu);
1320 pr_devel("-->%s()\n", __func__);
1322 if (edit->dead_leaf)
1323 edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));
1324 for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)
1325 if (edit->excised_meta[i])
1326 kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));
1328 if (edit->excised_subtree) {
1329 BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));
1330 if (assoc_array_ptr_is_node(edit->excised_subtree)) {
1331 struct assoc_array_node *n =
1332 assoc_array_ptr_to_node(edit->excised_subtree);
1333 n->back_pointer = NULL;
1335 struct assoc_array_shortcut *s =
1336 assoc_array_ptr_to_shortcut(edit->excised_subtree);
1337 s->back_pointer = NULL;
1339 assoc_array_destroy_subtree(edit->excised_subtree,
1340 edit->ops_for_excised_subtree);
1347 * assoc_array_apply_edit - Apply an edit script to an associative array
1348 * @edit: The script to apply.
1350 * Apply an edit script to an associative array to effect an insertion,
1351 * deletion or clearance. As the edit script includes preallocated memory,
1352 * this is guaranteed not to fail.
1354 * The edit script, dead objects and dead metadata will be scheduled for
1355 * destruction after an RCU grace period to permit those doing read-only
1356 * accesses on the array to continue to do so under the RCU read lock whilst
1357 * the edit is taking place.
1359 void assoc_array_apply_edit(struct assoc_array_edit *edit)
1361 struct assoc_array_shortcut *shortcut;
1362 struct assoc_array_node *node;
1363 struct assoc_array_ptr *ptr;
1366 pr_devel("-->%s()\n", __func__);
1370 *edit->leaf_p = edit->leaf;
1373 for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)
1374 if (edit->set_parent_slot[i].p)
1375 *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;
1378 for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)
1379 if (edit->set_backpointers[i])
1380 *edit->set_backpointers[i] = edit->set_backpointers_to;
1383 for (i = 0; i < ARRAY_SIZE(edit->set); i++)
1384 if (edit->set[i].ptr)
1385 *edit->set[i].ptr = edit->set[i].to;
1387 if (edit->array->root == NULL) {
1388 edit->array->nr_leaves_on_tree = 0;
1389 } else if (edit->adjust_count_on) {
1390 node = edit->adjust_count_on;
1392 node->nr_leaves_on_branch += edit->adjust_count_by;
1394 ptr = node->back_pointer;
1397 if (assoc_array_ptr_is_shortcut(ptr)) {
1398 shortcut = assoc_array_ptr_to_shortcut(ptr);
1399 ptr = shortcut->back_pointer;
1403 BUG_ON(!assoc_array_ptr_is_node(ptr));
1404 node = assoc_array_ptr_to_node(ptr);
1407 edit->array->nr_leaves_on_tree += edit->adjust_count_by;
1410 call_rcu(&edit->rcu, assoc_array_rcu_cleanup);
1414 * assoc_array_cancel_edit - Discard an edit script.
1415 * @edit: The script to discard.
1417 * Free an edit script and all the preallocated data it holds without making
1418 * any changes to the associative array it was intended for.
1420 * NOTE! In the case of an insertion script, this does _not_ release the leaf
1421 * that was to be inserted. That is left to the caller.
1423 void assoc_array_cancel_edit(struct assoc_array_edit *edit)
1425 struct assoc_array_ptr *ptr;
1428 pr_devel("-->%s()\n", __func__);
1430 /* Clean up after an out of memory error */
1431 for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {
1432 ptr = edit->new_meta[i];
1434 if (assoc_array_ptr_is_node(ptr))
1435 kfree(assoc_array_ptr_to_node(ptr));
1437 kfree(assoc_array_ptr_to_shortcut(ptr));
1444 * assoc_array_gc - Garbage collect an associative array.
1445 * @array: The array to clean.
1446 * @ops: The operations to use.
1447 * @iterator: A callback function to pass judgement on each object.
1448 * @iterator_data: Private data for the callback function.
1450 * Collect garbage from an associative array and pack down the internal tree to
1453 * The iterator function is asked to pass judgement upon each object in the
1454 * array. If it returns false, the object is discard and if it returns true,
1455 * the object is kept. If it returns true, it must increment the object's
1456 * usage count (or whatever it needs to do to retain it) before returning.
1458 * This function returns 0 if successful or -ENOMEM if out of memory. In the
1459 * latter case, the array is not changed.
1461 * The caller should lock against other modifications and must continue to hold
1462 * the lock until assoc_array_apply_edit() has been called.
1464 * Accesses to the tree may take place concurrently with this function,
1465 * provided they hold the RCU read lock.
1467 int assoc_array_gc(struct assoc_array *array,
1468 const struct assoc_array_ops *ops,
1469 bool (*iterator)(void *object, void *iterator_data),
1470 void *iterator_data)
1472 struct assoc_array_shortcut *shortcut, *new_s;
1473 struct assoc_array_node *node, *new_n;
1474 struct assoc_array_edit *edit;
1475 struct assoc_array_ptr *cursor, *ptr;
1476 struct assoc_array_ptr *new_root, *new_parent, **new_ptr_pp;
1477 unsigned long nr_leaves_on_tree;
1478 int keylen, slot, nr_free, next_slot, i;
1480 pr_devel("-->%s()\n", __func__);
1485 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1488 edit->array = array;
1490 edit->ops_for_excised_subtree = ops;
1491 edit->set[0].ptr = &array->root;
1492 edit->excised_subtree = array->root;
1494 new_root = new_parent = NULL;
1495 new_ptr_pp = &new_root;
1496 cursor = array->root;
1499 /* If this point is a shortcut, then we need to duplicate it and
1500 * advance the target cursor.
1502 if (assoc_array_ptr_is_shortcut(cursor)) {
1503 shortcut = assoc_array_ptr_to_shortcut(cursor);
1504 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
1505 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
1506 new_s = kmalloc(sizeof(struct assoc_array_shortcut) +
1507 keylen * sizeof(unsigned long), GFP_KERNEL);
1510 pr_devel("dup shortcut %p -> %p\n", shortcut, new_s);
1511 memcpy(new_s, shortcut, (sizeof(struct assoc_array_shortcut) +
1512 keylen * sizeof(unsigned long)));
1513 new_s->back_pointer = new_parent;
1514 new_s->parent_slot = shortcut->parent_slot;
1515 *new_ptr_pp = new_parent = assoc_array_shortcut_to_ptr(new_s);
1516 new_ptr_pp = &new_s->next_node;
1517 cursor = shortcut->next_node;
1520 /* Duplicate the node at this position */
1521 node = assoc_array_ptr_to_node(cursor);
1522 new_n = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
1525 pr_devel("dup node %p -> %p\n", node, new_n);
1526 new_n->back_pointer = new_parent;
1527 new_n->parent_slot = node->parent_slot;
1528 *new_ptr_pp = new_parent = assoc_array_node_to_ptr(new_n);
1533 /* Filter across any leaves and gc any subtrees */
1534 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1535 ptr = node->slots[slot];
1539 if (assoc_array_ptr_is_leaf(ptr)) {
1540 if (iterator(assoc_array_ptr_to_leaf(ptr),
1542 /* The iterator will have done any reference
1543 * counting on the object for us.
1545 new_n->slots[slot] = ptr;
1549 new_ptr_pp = &new_n->slots[slot];
1554 pr_devel("-- compress node %p --\n", new_n);
1556 /* Count up the number of empty slots in this node and work out the
1557 * subtree leaf count.
1559 new_n->nr_leaves_on_branch = 0;
1561 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1562 ptr = new_n->slots[slot];
1565 else if (assoc_array_ptr_is_leaf(ptr))
1566 new_n->nr_leaves_on_branch++;
1568 pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch);
1570 /* See what we can fold in */
1572 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1573 struct assoc_array_shortcut *s;
1574 struct assoc_array_node *child;
1576 ptr = new_n->slots[slot];
1577 if (!ptr || assoc_array_ptr_is_leaf(ptr))
1581 if (assoc_array_ptr_is_shortcut(ptr)) {
1582 s = assoc_array_ptr_to_shortcut(ptr);
1586 child = assoc_array_ptr_to_node(ptr);
1587 new_n->nr_leaves_on_branch += child->nr_leaves_on_branch;
1589 if (child->nr_leaves_on_branch <= nr_free + 1) {
1590 /* Fold the child node into this one */
1591 pr_devel("[%d] fold node %lu/%d [nx %d]\n",
1592 slot, child->nr_leaves_on_branch, nr_free + 1,
1595 /* We would already have reaped an intervening shortcut
1596 * on the way back up the tree.
1600 new_n->slots[slot] = NULL;
1602 if (slot < next_slot)
1604 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
1605 struct assoc_array_ptr *p = child->slots[i];
1608 BUG_ON(assoc_array_ptr_is_meta(p));
1609 while (new_n->slots[next_slot])
1611 BUG_ON(next_slot >= ASSOC_ARRAY_FAN_OUT);
1612 new_n->slots[next_slot++] = p;
1617 pr_devel("[%d] retain node %lu/%d [nx %d]\n",
1618 slot, child->nr_leaves_on_branch, nr_free + 1,
1623 pr_devel("after: %lu\n", new_n->nr_leaves_on_branch);
1625 nr_leaves_on_tree = new_n->nr_leaves_on_branch;
1627 /* Excise this node if it is singly occupied by a shortcut */
1628 if (nr_free == ASSOC_ARRAY_FAN_OUT - 1) {
1629 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++)
1630 if ((ptr = new_n->slots[slot]))
1633 if (assoc_array_ptr_is_meta(ptr) &&
1634 assoc_array_ptr_is_shortcut(ptr)) {
1635 pr_devel("excise node %p with 1 shortcut\n", new_n);
1636 new_s = assoc_array_ptr_to_shortcut(ptr);
1637 new_parent = new_n->back_pointer;
1638 slot = new_n->parent_slot;
1641 new_s->back_pointer = NULL;
1642 new_s->parent_slot = 0;
1647 if (assoc_array_ptr_is_shortcut(new_parent)) {
1648 /* We can discard any preceding shortcut also */
1649 struct assoc_array_shortcut *s =
1650 assoc_array_ptr_to_shortcut(new_parent);
1652 pr_devel("excise preceding shortcut\n");
1654 new_parent = new_s->back_pointer = s->back_pointer;
1655 slot = new_s->parent_slot = s->parent_slot;
1658 new_s->back_pointer = NULL;
1659 new_s->parent_slot = 0;
1665 new_s->back_pointer = new_parent;
1666 new_s->parent_slot = slot;
1667 new_n = assoc_array_ptr_to_node(new_parent);
1668 new_n->slots[slot] = ptr;
1669 goto ascend_old_tree;
1673 /* Excise any shortcuts we might encounter that point to nodes that
1674 * only contain leaves.
1676 ptr = new_n->back_pointer;
1680 if (assoc_array_ptr_is_shortcut(ptr)) {
1681 new_s = assoc_array_ptr_to_shortcut(ptr);
1682 new_parent = new_s->back_pointer;
1683 slot = new_s->parent_slot;
1685 if (new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
1686 struct assoc_array_node *n;
1688 pr_devel("excise shortcut\n");
1689 new_n->back_pointer = new_parent;
1690 new_n->parent_slot = slot;
1693 new_root = assoc_array_node_to_ptr(new_n);
1697 n = assoc_array_ptr_to_node(new_parent);
1698 n->slots[slot] = assoc_array_node_to_ptr(new_n);
1703 new_n = assoc_array_ptr_to_node(new_parent);
1706 ptr = node->back_pointer;
1707 if (assoc_array_ptr_is_shortcut(ptr)) {
1708 shortcut = assoc_array_ptr_to_shortcut(ptr);
1709 slot = shortcut->parent_slot;
1710 cursor = shortcut->back_pointer;
1714 slot = node->parent_slot;
1718 node = assoc_array_ptr_to_node(cursor);
1723 edit->set[0].to = new_root;
1724 assoc_array_apply_edit(edit);
1725 array->nr_leaves_on_tree = nr_leaves_on_tree;
1729 pr_devel("enomem\n");
1730 assoc_array_destroy_subtree(new_root, edit->ops);