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/assoc_array_priv.h>
18 * Iterate over an associative array. The caller must hold the RCU read lock
21 static int assoc_array_subtree_iterate(const struct assoc_array_ptr *root,
22 const struct assoc_array_ptr *stop,
23 int (*iterator)(const void *leaf,
27 const struct assoc_array_shortcut *shortcut;
28 const struct assoc_array_node *node;
29 const struct assoc_array_ptr *cursor, *ptr, *parent;
30 unsigned long has_meta;
36 if (assoc_array_ptr_is_shortcut(cursor)) {
37 /* Descend through a shortcut */
38 shortcut = assoc_array_ptr_to_shortcut(cursor);
39 smp_read_barrier_depends();
40 cursor = ACCESS_ONCE(shortcut->next_node);
43 node = assoc_array_ptr_to_node(cursor);
44 smp_read_barrier_depends();
47 /* We perform two passes of each node.
49 * The first pass does all the leaves in this node. This means we
50 * don't miss any leaves if the node is split up by insertion whilst
51 * we're iterating over the branches rooted here (we may, however, see
55 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
56 ptr = ACCESS_ONCE(node->slots[slot]);
57 has_meta |= (unsigned long)ptr;
58 if (ptr && assoc_array_ptr_is_leaf(ptr)) {
59 /* We need a barrier between the read of the pointer
60 * and dereferencing the pointer - but only if we are
61 * actually going to dereference it.
63 smp_read_barrier_depends();
65 /* Invoke the callback */
66 ret = iterator(assoc_array_ptr_to_leaf(ptr),
73 /* The second pass attends to all the metadata pointers. If we follow
74 * one of these we may find that we don't come back here, but rather go
75 * back to a replacement node with the leaves in a different layout.
77 * We are guaranteed to make progress, however, as the slot number for
78 * a particular portion of the key space cannot change - and we
79 * continue at the back pointer + 1.
81 if (!(has_meta & ASSOC_ARRAY_PTR_META_TYPE))
86 node = assoc_array_ptr_to_node(cursor);
87 smp_read_barrier_depends();
89 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
90 ptr = ACCESS_ONCE(node->slots[slot]);
91 if (assoc_array_ptr_is_meta(ptr)) {
98 /* Move up to the parent (may need to skip back over a shortcut) */
99 parent = ACCESS_ONCE(node->back_pointer);
100 slot = node->parent_slot;
104 if (assoc_array_ptr_is_shortcut(parent)) {
105 shortcut = assoc_array_ptr_to_shortcut(parent);
106 smp_read_barrier_depends();
108 parent = ACCESS_ONCE(shortcut->back_pointer);
109 slot = shortcut->parent_slot;
114 /* Ascend to next slot in parent node */
121 * assoc_array_iterate - Pass all objects in the array to a callback
122 * @array: The array to iterate over.
123 * @iterator: The callback function.
124 * @iterator_data: Private data for the callback function.
126 * Iterate over all the objects in an associative array. Each one will be
127 * presented to the iterator function.
129 * If the array is being modified concurrently with the iteration then it is
130 * possible that some objects in the array will be passed to the iterator
131 * callback more than once - though every object should be passed at least
132 * once. If this is undesirable then the caller must lock against modification
133 * for the duration of this function.
135 * The function will return 0 if no objects were in the array or else it will
136 * return the result of the last iterator function called. Iteration stops
137 * immediately if any call to the iteration function results in a non-zero
140 * The caller should hold the RCU read lock or better if concurrent
141 * modification is possible.
143 int assoc_array_iterate(const struct assoc_array *array,
144 int (*iterator)(const void *object,
145 void *iterator_data),
148 struct assoc_array_ptr *root = ACCESS_ONCE(array->root);
152 return assoc_array_subtree_iterate(root, NULL, iterator, iterator_data);
155 enum assoc_array_walk_status {
156 assoc_array_walk_tree_empty,
157 assoc_array_walk_found_terminal_node,
158 assoc_array_walk_found_wrong_shortcut,
161 struct assoc_array_walk_result {
163 struct assoc_array_node *node; /* Node in which leaf might be found */
168 struct assoc_array_shortcut *shortcut;
171 unsigned long sc_segments;
172 unsigned long dissimilarity;
177 * Navigate through the internal tree looking for the closest node to the key.
179 static enum assoc_array_walk_status
180 assoc_array_walk(const struct assoc_array *array,
181 const struct assoc_array_ops *ops,
182 const void *index_key,
183 struct assoc_array_walk_result *result)
185 struct assoc_array_shortcut *shortcut;
186 struct assoc_array_node *node;
187 struct assoc_array_ptr *cursor, *ptr;
188 unsigned long sc_segments, dissimilarity;
189 unsigned long segments;
190 int level, sc_level, next_sc_level;
193 pr_devel("-->%s()\n", __func__);
195 cursor = ACCESS_ONCE(array->root);
197 return assoc_array_walk_tree_empty;
201 /* Use segments from the key for the new leaf to navigate through the
202 * internal tree, skipping through nodes and shortcuts that are on
203 * route to the destination. Eventually we'll come to a slot that is
204 * either empty or contains a leaf at which point we've found a node in
205 * which the leaf we're looking for might be found or into which it
206 * should be inserted.
209 segments = ops->get_key_chunk(index_key, level);
210 pr_devel("segments[%d]: %lx\n", level, segments);
212 if (assoc_array_ptr_is_shortcut(cursor))
213 goto follow_shortcut;
216 node = assoc_array_ptr_to_node(cursor);
217 smp_read_barrier_depends();
219 slot = segments >> (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
220 slot &= ASSOC_ARRAY_FAN_MASK;
221 ptr = ACCESS_ONCE(node->slots[slot]);
223 pr_devel("consider slot %x [ix=%d type=%lu]\n",
224 slot, level, (unsigned long)ptr & 3);
226 if (!assoc_array_ptr_is_meta(ptr)) {
227 /* The node doesn't have a node/shortcut pointer in the slot
228 * corresponding to the index key that we have to follow.
230 result->terminal_node.node = node;
231 result->terminal_node.level = level;
232 result->terminal_node.slot = slot;
233 pr_devel("<--%s() = terminal_node\n", __func__);
234 return assoc_array_walk_found_terminal_node;
237 if (assoc_array_ptr_is_node(ptr)) {
238 /* There is a pointer to a node in the slot corresponding to
239 * this index key segment, so we need to follow it.
242 level += ASSOC_ARRAY_LEVEL_STEP;
243 if ((level & ASSOC_ARRAY_KEY_CHUNK_MASK) != 0)
248 /* There is a shortcut in the slot corresponding to the index key
249 * segment. We follow the shortcut if its partial index key matches
250 * this leaf's. Otherwise we need to split the shortcut.
254 shortcut = assoc_array_ptr_to_shortcut(cursor);
255 smp_read_barrier_depends();
256 pr_devel("shortcut to %d\n", shortcut->skip_to_level);
257 sc_level = level + ASSOC_ARRAY_LEVEL_STEP;
258 BUG_ON(sc_level > shortcut->skip_to_level);
261 /* Check the leaf against the shortcut's index key a word at a
262 * time, trimming the final word (the shortcut stores the index
263 * key completely from the root to the shortcut's target).
265 if ((sc_level & ASSOC_ARRAY_KEY_CHUNK_MASK) == 0)
266 segments = ops->get_key_chunk(index_key, sc_level);
268 sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
269 dissimilarity = segments ^ sc_segments;
271 if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) {
272 /* Trim segments that are beyond the shortcut */
273 int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
274 dissimilarity &= ~(ULONG_MAX << shift);
275 next_sc_level = shortcut->skip_to_level;
277 next_sc_level = sc_level + ASSOC_ARRAY_KEY_CHUNK_SIZE;
278 next_sc_level = round_down(next_sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
281 if (dissimilarity != 0) {
282 /* This shortcut points elsewhere */
283 result->wrong_shortcut.shortcut = shortcut;
284 result->wrong_shortcut.level = level;
285 result->wrong_shortcut.sc_level = sc_level;
286 result->wrong_shortcut.sc_segments = sc_segments;
287 result->wrong_shortcut.dissimilarity = dissimilarity;
288 return assoc_array_walk_found_wrong_shortcut;
291 sc_level = next_sc_level;
292 } while (sc_level < shortcut->skip_to_level);
294 /* The shortcut matches the leaf's index to this point. */
295 cursor = ACCESS_ONCE(shortcut->next_node);
296 if (((level ^ sc_level) & ~ASSOC_ARRAY_KEY_CHUNK_MASK) != 0) {
306 * assoc_array_find - Find an object by index key
307 * @array: The associative array to search.
308 * @ops: The operations to use.
309 * @index_key: The key to the object.
311 * Find an object in an associative array by walking through the internal tree
312 * to the node that should contain the object and then searching the leaves
313 * there. NULL is returned if the requested object was not found in the array.
315 * The caller must hold the RCU read lock or better.
317 void *assoc_array_find(const struct assoc_array *array,
318 const struct assoc_array_ops *ops,
319 const void *index_key)
321 struct assoc_array_walk_result result;
322 const struct assoc_array_node *node;
323 const struct assoc_array_ptr *ptr;
327 if (assoc_array_walk(array, ops, index_key, &result) !=
328 assoc_array_walk_found_terminal_node)
331 node = result.terminal_node.node;
332 smp_read_barrier_depends();
334 /* If the target key is available to us, it's has to be pointed to by
337 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
338 ptr = ACCESS_ONCE(node->slots[slot]);
339 if (ptr && assoc_array_ptr_is_leaf(ptr)) {
340 /* We need a barrier between the read of the pointer
341 * and dereferencing the pointer - but only if we are
342 * actually going to dereference it.
344 leaf = assoc_array_ptr_to_leaf(ptr);
345 smp_read_barrier_depends();
346 if (ops->compare_object(leaf, index_key))
355 * Destructively iterate over an associative array. The caller must prevent
356 * other simultaneous accesses.
358 static void assoc_array_destroy_subtree(struct assoc_array_ptr *root,
359 const struct assoc_array_ops *ops)
361 struct assoc_array_shortcut *shortcut;
362 struct assoc_array_node *node;
363 struct assoc_array_ptr *cursor, *parent = NULL;
366 pr_devel("-->%s()\n", __func__);
375 if (assoc_array_ptr_is_shortcut(cursor)) {
376 /* Descend through a shortcut */
377 pr_devel("[%d] shortcut\n", slot);
378 BUG_ON(!assoc_array_ptr_is_shortcut(cursor));
379 shortcut = assoc_array_ptr_to_shortcut(cursor);
380 BUG_ON(shortcut->back_pointer != parent);
381 BUG_ON(slot != -1 && shortcut->parent_slot != slot);
383 cursor = shortcut->next_node;
385 BUG_ON(!assoc_array_ptr_is_node(cursor));
388 pr_devel("[%d] node\n", slot);
389 node = assoc_array_ptr_to_node(cursor);
390 BUG_ON(node->back_pointer != parent);
391 BUG_ON(slot != -1 && node->parent_slot != slot);
395 pr_devel("Node %p [back=%p]\n", node, node->back_pointer);
396 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
397 struct assoc_array_ptr *ptr = node->slots[slot];
400 if (assoc_array_ptr_is_meta(ptr)) {
407 pr_devel("[%d] free leaf\n", slot);
408 ops->free_object(assoc_array_ptr_to_leaf(ptr));
412 parent = node->back_pointer;
413 slot = node->parent_slot;
414 pr_devel("free node\n");
419 /* Move back up to the parent (may need to free a shortcut on
421 if (assoc_array_ptr_is_shortcut(parent)) {
422 shortcut = assoc_array_ptr_to_shortcut(parent);
423 BUG_ON(shortcut->next_node != cursor);
425 parent = shortcut->back_pointer;
426 slot = shortcut->parent_slot;
427 pr_devel("free shortcut\n");
432 BUG_ON(!assoc_array_ptr_is_node(parent));
435 /* Ascend to next slot in parent node */
436 pr_devel("ascend to %p[%d]\n", parent, slot);
438 node = assoc_array_ptr_to_node(cursor);
444 * assoc_array_destroy - Destroy an associative array
445 * @array: The array to destroy.
446 * @ops: The operations to use.
448 * Discard all metadata and free all objects in an associative array. The
449 * array will be empty and ready to use again upon completion. This function
452 * The caller must prevent all other accesses whilst this takes place as no
453 * attempt is made to adjust pointers gracefully to permit RCU readlock-holding
454 * accesses to continue. On the other hand, no memory allocation is required.
456 void assoc_array_destroy(struct assoc_array *array,
457 const struct assoc_array_ops *ops)
459 assoc_array_destroy_subtree(array->root, ops);
464 * Handle insertion into an empty tree.
466 static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit)
468 struct assoc_array_node *new_n0;
470 pr_devel("-->%s()\n", __func__);
472 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
476 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
477 edit->leaf_p = &new_n0->slots[0];
478 edit->adjust_count_on = new_n0;
479 edit->set[0].ptr = &edit->array->root;
480 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
482 pr_devel("<--%s() = ok [no root]\n", __func__);
487 * Handle insertion into a terminal node.
489 static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
490 const struct assoc_array_ops *ops,
491 const void *index_key,
492 struct assoc_array_walk_result *result)
494 struct assoc_array_shortcut *shortcut, *new_s0;
495 struct assoc_array_node *node, *new_n0, *new_n1, *side;
496 struct assoc_array_ptr *ptr;
497 unsigned long dissimilarity, base_seg, blank;
501 int slot, next_slot, free_slot, i, j;
503 node = result->terminal_node.node;
504 level = result->terminal_node.level;
505 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot;
507 pr_devel("-->%s()\n", __func__);
509 /* We arrived at a node which doesn't have an onward node or shortcut
510 * pointer that we have to follow. This means that (a) the leaf we
511 * want must go here (either by insertion or replacement) or (b) we
512 * need to split this node and insert in one of the fragments.
516 /* Firstly, we have to check the leaves in this node to see if there's
517 * a matching one we should replace in place.
519 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
520 ptr = node->slots[i];
525 if (ops->compare_object(assoc_array_ptr_to_leaf(ptr), index_key)) {
526 pr_devel("replace in slot %d\n", i);
527 edit->leaf_p = &node->slots[i];
528 edit->dead_leaf = node->slots[i];
529 pr_devel("<--%s() = ok [replace]\n", __func__);
534 /* If there is a free slot in this node then we can just insert the
537 if (free_slot >= 0) {
538 pr_devel("insert in free slot %d\n", free_slot);
539 edit->leaf_p = &node->slots[free_slot];
540 edit->adjust_count_on = node;
541 pr_devel("<--%s() = ok [insert]\n", __func__);
545 /* The node has no spare slots - so we're either going to have to split
546 * it or insert another node before it.
548 * Whatever, we're going to need at least two new nodes - so allocate
549 * those now. We may also need a new shortcut, but we deal with that
552 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
555 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
556 new_n1 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
559 edit->new_meta[1] = assoc_array_node_to_ptr(new_n1);
561 /* We need to find out how similar the leaves are. */
562 pr_devel("no spare slots\n");
564 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
565 ptr = node->slots[i];
566 if (assoc_array_ptr_is_meta(ptr)) {
567 edit->segment_cache[i] = 0xff;
571 base_seg = ops->get_object_key_chunk(
572 assoc_array_ptr_to_leaf(ptr), level);
573 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
574 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
578 pr_devel("have meta\n");
582 /* The node contains only leaves */
584 base_seg = edit->segment_cache[0];
585 for (i = 1; i < ASSOC_ARRAY_FAN_OUT; i++)
586 dissimilarity |= edit->segment_cache[i] ^ base_seg;
588 pr_devel("only leaves; dissimilarity=%lx\n", dissimilarity);
590 if ((dissimilarity & ASSOC_ARRAY_FAN_MASK) == 0) {
591 /* The old leaves all cluster in the same slot. We will need
592 * to insert a shortcut if the new node wants to cluster with them.
594 if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)
595 goto all_leaves_cluster_together;
597 /* Otherwise we can just insert a new node ahead of the old
600 goto present_leaves_cluster_but_not_new_leaf;
604 pr_devel("split node\n");
606 /* We need to split the current node; we know that the node doesn't
607 * simply contain a full set of leaves that cluster together (it
608 * contains meta pointers and/or non-clustering leaves).
610 * We need to expel at least two leaves out of a set consisting of the
611 * leaves in the node and the new leaf.
613 * We need a new node (n0) to replace the current one and a new node to
614 * take the expelled nodes (n1).
616 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
617 new_n0->back_pointer = node->back_pointer;
618 new_n0->parent_slot = node->parent_slot;
619 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
620 new_n1->parent_slot = -1; /* Need to calculate this */
623 pr_devel("do_split_node\n");
625 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
626 new_n1->nr_leaves_on_branch = 0;
628 /* Begin by finding two matching leaves. There have to be at least two
629 * that match - even if there are meta pointers - because any leaf that
630 * would match a slot with a meta pointer in it must be somewhere
631 * behind that meta pointer and cannot be here. Further, given N
632 * remaining leaf slots, we now have N+1 leaves to go in them.
634 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
635 slot = edit->segment_cache[i];
637 for (j = i + 1; j < ASSOC_ARRAY_FAN_OUT + 1; j++)
638 if (edit->segment_cache[j] == slot)
639 goto found_slot_for_multiple_occupancy;
641 found_slot_for_multiple_occupancy:
642 pr_devel("same slot: %x %x [%02x]\n", i, j, slot);
643 BUG_ON(i >= ASSOC_ARRAY_FAN_OUT);
644 BUG_ON(j >= ASSOC_ARRAY_FAN_OUT + 1);
645 BUG_ON(slot >= ASSOC_ARRAY_FAN_OUT);
647 new_n1->parent_slot = slot;
649 /* Metadata pointers cannot change slot */
650 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
651 if (assoc_array_ptr_is_meta(node->slots[i]))
652 new_n0->slots[i] = node->slots[i];
654 new_n0->slots[i] = NULL;
655 BUG_ON(new_n0->slots[slot] != NULL);
656 new_n0->slots[slot] = assoc_array_node_to_ptr(new_n1);
658 /* Filter the leaf pointers between the new nodes */
661 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
662 if (assoc_array_ptr_is_meta(node->slots[i]))
664 if (edit->segment_cache[i] == slot) {
665 new_n1->slots[next_slot++] = node->slots[i];
666 new_n1->nr_leaves_on_branch++;
670 } while (new_n0->slots[free_slot] != NULL);
671 new_n0->slots[free_slot] = node->slots[i];
675 pr_devel("filtered: f=%x n=%x\n", free_slot, next_slot);
677 if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {
680 } while (new_n0->slots[free_slot] != NULL);
681 edit->leaf_p = &new_n0->slots[free_slot];
682 edit->adjust_count_on = new_n0;
684 edit->leaf_p = &new_n1->slots[next_slot++];
685 edit->adjust_count_on = new_n1;
688 BUG_ON(next_slot <= 1);
690 edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);
691 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
692 if (edit->segment_cache[i] == 0xff) {
693 ptr = node->slots[i];
694 BUG_ON(assoc_array_ptr_is_leaf(ptr));
695 if (assoc_array_ptr_is_node(ptr)) {
696 side = assoc_array_ptr_to_node(ptr);
697 edit->set_backpointers[i] = &side->back_pointer;
699 shortcut = assoc_array_ptr_to_shortcut(ptr);
700 edit->set_backpointers[i] = &shortcut->back_pointer;
705 ptr = node->back_pointer;
707 edit->set[0].ptr = &edit->array->root;
708 else if (assoc_array_ptr_is_node(ptr))
709 edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];
711 edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node;
712 edit->excised_meta[0] = assoc_array_node_to_ptr(node);
713 pr_devel("<--%s() = ok [split node]\n", __func__);
716 present_leaves_cluster_but_not_new_leaf:
717 /* All the old leaves cluster in the same slot, but the new leaf wants
718 * to go into a different slot, so we create a new node to hold the new
719 * leaf and a pointer to a new node holding all the old leaves.
721 pr_devel("present leaves cluster but not new leaf\n");
723 new_n0->back_pointer = node->back_pointer;
724 new_n0->parent_slot = node->parent_slot;
725 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
726 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
727 new_n1->parent_slot = edit->segment_cache[0];
728 new_n1->nr_leaves_on_branch = node->nr_leaves_on_branch;
729 edit->adjust_count_on = new_n0;
731 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
732 new_n1->slots[i] = node->slots[i];
734 new_n0->slots[edit->segment_cache[0]] = assoc_array_node_to_ptr(new_n0);
735 edit->leaf_p = &new_n0->slots[edit->segment_cache[ASSOC_ARRAY_FAN_OUT]];
737 edit->set[0].ptr = &assoc_array_ptr_to_node(node->back_pointer)->slots[node->parent_slot];
738 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
739 edit->excised_meta[0] = assoc_array_node_to_ptr(node);
740 pr_devel("<--%s() = ok [insert node before]\n", __func__);
743 all_leaves_cluster_together:
744 /* All the leaves, new and old, want to cluster together in this node
745 * in the same slot, so we have to replace this node with a shortcut to
746 * skip over the identical parts of the key and then place a pair of
747 * nodes, one inside the other, at the end of the shortcut and
748 * distribute the keys between them.
750 * Firstly we need to work out where the leaves start diverging as a
751 * bit position into their keys so that we know how big the shortcut
754 * We only need to make a single pass of N of the N+1 leaves because if
755 * any keys differ between themselves at bit X then at least one of
756 * them must also differ with the base key at bit X or before.
758 pr_devel("all leaves cluster together\n");
760 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
761 int x = ops->diff_objects(assoc_array_ptr_to_leaf(edit->leaf),
762 assoc_array_ptr_to_leaf(node->slots[i]));
768 BUG_ON(diff == INT_MAX);
769 BUG_ON(diff < level + ASSOC_ARRAY_LEVEL_STEP);
771 keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
772 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
774 new_s0 = kzalloc(sizeof(struct assoc_array_shortcut) +
775 keylen * sizeof(unsigned long), GFP_KERNEL);
778 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);
780 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
781 new_s0->back_pointer = node->back_pointer;
782 new_s0->parent_slot = node->parent_slot;
783 new_s0->next_node = assoc_array_node_to_ptr(new_n0);
784 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
785 new_n0->parent_slot = 0;
786 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
787 new_n1->parent_slot = -1; /* Need to calculate this */
789 new_s0->skip_to_level = level = diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK;
790 pr_devel("skip_to_level = %d [diff %d]\n", level, diff);
793 for (i = 0; i < keylen; i++)
794 new_s0->index_key[i] =
795 ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE);
797 blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
798 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank);
799 new_s0->index_key[keylen - 1] &= ~blank;
801 /* This now reduces to a node splitting exercise for which we'll need
802 * to regenerate the disparity table.
804 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
805 ptr = node->slots[i];
806 base_seg = ops->get_object_key_chunk(assoc_array_ptr_to_leaf(ptr),
808 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
809 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
812 base_seg = ops->get_key_chunk(index_key, level);
813 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
814 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;
819 * Handle insertion into the middle of a shortcut.
821 static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
822 const struct assoc_array_ops *ops,
823 struct assoc_array_walk_result *result)
825 struct assoc_array_shortcut *shortcut, *new_s0, *new_s1;
826 struct assoc_array_node *node, *new_n0, *side;
827 unsigned long sc_segments, dissimilarity, blank;
829 int level, sc_level, diff;
832 shortcut = result->wrong_shortcut.shortcut;
833 level = result->wrong_shortcut.level;
834 sc_level = result->wrong_shortcut.sc_level;
835 sc_segments = result->wrong_shortcut.sc_segments;
836 dissimilarity = result->wrong_shortcut.dissimilarity;
838 pr_devel("-->%s(ix=%d dis=%lx scix=%d)\n",
839 __func__, level, dissimilarity, sc_level);
841 /* We need to split a shortcut and insert a node between the two
842 * pieces. Zero-length pieces will be dispensed with entirely.
844 * First of all, we need to find out in which level the first
847 diff = __ffs(dissimilarity);
848 diff &= ~ASSOC_ARRAY_LEVEL_STEP_MASK;
849 diff += sc_level & ~ASSOC_ARRAY_KEY_CHUNK_MASK;
850 pr_devel("diff=%d\n", diff);
852 if (!shortcut->back_pointer) {
853 edit->set[0].ptr = &edit->array->root;
854 } else if (assoc_array_ptr_is_node(shortcut->back_pointer)) {
855 node = assoc_array_ptr_to_node(shortcut->back_pointer);
856 edit->set[0].ptr = &node->slots[shortcut->parent_slot];
861 edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);
863 /* Create a new node now since we're going to need it anyway */
864 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
867 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
868 edit->adjust_count_on = new_n0;
870 /* Insert a new shortcut before the new node if this segment isn't of
871 * zero length - otherwise we just connect the new node directly to the
874 level += ASSOC_ARRAY_LEVEL_STEP;
876 pr_devel("pre-shortcut %d...%d\n", level, diff);
877 keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
878 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
880 new_s0 = kzalloc(sizeof(struct assoc_array_shortcut) +
881 keylen * sizeof(unsigned long), GFP_KERNEL);
884 edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);
885 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
886 new_s0->back_pointer = shortcut->back_pointer;
887 new_s0->parent_slot = shortcut->parent_slot;
888 new_s0->next_node = assoc_array_node_to_ptr(new_n0);
889 new_s0->skip_to_level = diff;
891 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
892 new_n0->parent_slot = 0;
894 memcpy(new_s0->index_key, shortcut->index_key,
895 keylen * sizeof(unsigned long));
897 blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
898 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);
899 new_s0->index_key[keylen - 1] &= ~blank;
901 pr_devel("no pre-shortcut\n");
902 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
903 new_n0->back_pointer = shortcut->back_pointer;
904 new_n0->parent_slot = shortcut->parent_slot;
907 side = assoc_array_ptr_to_node(shortcut->next_node);
908 new_n0->nr_leaves_on_branch = side->nr_leaves_on_branch;
910 /* We need to know which slot in the new node is going to take a
913 sc_slot = sc_segments >> (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
914 sc_slot &= ASSOC_ARRAY_FAN_MASK;
916 pr_devel("new slot %lx >> %d -> %d\n",
917 sc_segments, diff & ASSOC_ARRAY_KEY_CHUNK_MASK, sc_slot);
919 /* Determine whether we need to follow the new node with a replacement
920 * for the current shortcut. We could in theory reuse the current
921 * shortcut if its parent slot number doesn't change - but that's a
922 * 1-in-16 chance so not worth expending the code upon.
924 level = diff + ASSOC_ARRAY_LEVEL_STEP;
925 if (level < shortcut->skip_to_level) {
926 pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level);
927 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
928 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
930 new_s1 = kzalloc(sizeof(struct assoc_array_shortcut) +
931 keylen * sizeof(unsigned long), GFP_KERNEL);
934 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);
936 new_s1->back_pointer = assoc_array_node_to_ptr(new_n0);
937 new_s1->parent_slot = sc_slot;
938 new_s1->next_node = shortcut->next_node;
939 new_s1->skip_to_level = shortcut->skip_to_level;
941 new_n0->slots[sc_slot] = assoc_array_shortcut_to_ptr(new_s1);
943 memcpy(new_s1->index_key, shortcut->index_key,
944 keylen * sizeof(unsigned long));
946 edit->set[1].ptr = &side->back_pointer;
947 edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);
949 pr_devel("no post-shortcut\n");
951 /* We don't have to replace the pointed-to node as long as we
952 * use memory barriers to make sure the parent slot number is
953 * changed before the back pointer (the parent slot number is
954 * irrelevant to the old parent shortcut).
956 new_n0->slots[sc_slot] = shortcut->next_node;
957 edit->set_parent_slot[0].p = &side->parent_slot;
958 edit->set_parent_slot[0].to = sc_slot;
959 edit->set[1].ptr = &side->back_pointer;
960 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
963 /* Install the new leaf in a spare slot in the new node. */
965 edit->leaf_p = &new_n0->slots[1];
967 edit->leaf_p = &new_n0->slots[0];
969 pr_devel("<--%s() = ok [split shortcut]\n", __func__);
974 * assoc_array_insert - Script insertion of an object into an associative array
975 * @array: The array to insert into.
976 * @ops: The operations to use.
977 * @index_key: The key to insert at.
978 * @object: The object to insert.
980 * Precalculate and preallocate a script for the insertion or replacement of an
981 * object in an associative array. This results in an edit script that can
982 * either be applied or cancelled.
984 * The function returns a pointer to an edit script or -ENOMEM.
986 * The caller should lock against other modifications and must continue to hold
987 * the lock until assoc_array_apply_edit() has been called.
989 * Accesses to the tree may take place concurrently with this function,
990 * provided they hold the RCU read lock.
992 struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
993 const struct assoc_array_ops *ops,
994 const void *index_key,
997 struct assoc_array_walk_result result;
998 struct assoc_array_edit *edit;
1000 pr_devel("-->%s()\n", __func__);
1002 /* The leaf pointer we're given must not have the bottom bit set as we
1003 * use those for type-marking the pointer. NULL pointers are also not
1004 * allowed as they indicate an empty slot but we have to allow them
1005 * here as they can be updated later.
1007 BUG_ON(assoc_array_ptr_is_meta(object));
1009 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1011 return ERR_PTR(-ENOMEM);
1012 edit->array = array;
1014 edit->leaf = assoc_array_leaf_to_ptr(object);
1015 edit->adjust_count_by = 1;
1017 switch (assoc_array_walk(array, ops, index_key, &result)) {
1018 case assoc_array_walk_tree_empty:
1019 /* Allocate a root node if there isn't one yet */
1020 if (!assoc_array_insert_in_empty_tree(edit))
1024 case assoc_array_walk_found_terminal_node:
1025 /* We found a node that doesn't have a node/shortcut pointer in
1026 * the slot corresponding to the index key that we have to
1029 if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,
1034 case assoc_array_walk_found_wrong_shortcut:
1035 /* We found a shortcut that didn't match our key in a slot we
1038 if (!assoc_array_insert_mid_shortcut(edit, ops, &result))
1044 /* Clean up after an out of memory error */
1045 pr_devel("enomem\n");
1046 assoc_array_cancel_edit(edit);
1047 return ERR_PTR(-ENOMEM);
1051 * assoc_array_insert_set_object - Set the new object pointer in an edit script
1052 * @edit: The edit script to modify.
1053 * @object: The object pointer to set.
1055 * Change the object to be inserted in an edit script. The object pointed to
1056 * by the old object is not freed. This must be done prior to applying the
1059 void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)
1062 edit->leaf = assoc_array_leaf_to_ptr(object);
1065 struct assoc_array_delete_collapse_context {
1066 struct assoc_array_node *node;
1067 const void *skip_leaf;
1072 * Subtree collapse to node iterator.
1074 static int assoc_array_delete_collapse_iterator(const void *leaf,
1075 void *iterator_data)
1077 struct assoc_array_delete_collapse_context *collapse = iterator_data;
1079 if (leaf == collapse->skip_leaf)
1082 BUG_ON(collapse->slot >= ASSOC_ARRAY_FAN_OUT);
1084 collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf);
1089 * assoc_array_delete - Script deletion of an object from an associative array
1090 * @array: The array to search.
1091 * @ops: The operations to use.
1092 * @index_key: The key to the object.
1094 * Precalculate and preallocate a script for the deletion of an object from an
1095 * associative array. This results in an edit script that can either be
1096 * applied or cancelled.
1098 * The function returns a pointer to an edit script if the object was found,
1099 * NULL if the object was not found or -ENOMEM.
1101 * The caller should lock against other modifications and must continue to hold
1102 * the lock until assoc_array_apply_edit() has been called.
1104 * Accesses to the tree may take place concurrently with this function,
1105 * provided they hold the RCU read lock.
1107 struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
1108 const struct assoc_array_ops *ops,
1109 const void *index_key)
1111 struct assoc_array_delete_collapse_context collapse;
1112 struct assoc_array_walk_result result;
1113 struct assoc_array_node *node, *new_n0;
1114 struct assoc_array_edit *edit;
1115 struct assoc_array_ptr *ptr;
1119 pr_devel("-->%s()\n", __func__);
1121 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1123 return ERR_PTR(-ENOMEM);
1124 edit->array = array;
1126 edit->adjust_count_by = -1;
1128 switch (assoc_array_walk(array, ops, index_key, &result)) {
1129 case assoc_array_walk_found_terminal_node:
1130 /* We found a node that should contain the leaf we've been
1131 * asked to remove - *if* it's in the tree.
1133 pr_devel("terminal_node\n");
1134 node = result.terminal_node.node;
1136 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1137 ptr = node->slots[slot];
1139 assoc_array_ptr_is_leaf(ptr) &&
1140 ops->compare_object(assoc_array_ptr_to_leaf(ptr),
1144 case assoc_array_walk_tree_empty:
1145 case assoc_array_walk_found_wrong_shortcut:
1147 assoc_array_cancel_edit(edit);
1148 pr_devel("not found\n");
1153 BUG_ON(array->nr_leaves_on_tree <= 0);
1155 /* In the simplest form of deletion we just clear the slot and release
1156 * the leaf after a suitable interval.
1158 edit->dead_leaf = node->slots[slot];
1159 edit->set[0].ptr = &node->slots[slot];
1160 edit->set[0].to = NULL;
1161 edit->adjust_count_on = node;
1163 /* If that concludes erasure of the last leaf, then delete the entire
1166 if (array->nr_leaves_on_tree == 1) {
1167 edit->set[1].ptr = &array->root;
1168 edit->set[1].to = NULL;
1169 edit->adjust_count_on = NULL;
1170 edit->excised_subtree = array->root;
1171 pr_devel("all gone\n");
1175 /* However, we'd also like to clear up some metadata blocks if we
1178 * We go for a simple algorithm of: if this node has FAN_OUT or fewer
1179 * leaves in it, then attempt to collapse it - and attempt to
1180 * recursively collapse up the tree.
1182 * We could also try and collapse in partially filled subtrees to take
1183 * up space in this node.
1185 if (node->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
1186 struct assoc_array_node *parent, *grandparent;
1187 struct assoc_array_ptr *ptr;
1189 /* First of all, we need to know if this node has metadata so
1190 * that we don't try collapsing if all the leaves are already
1194 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
1195 ptr = node->slots[i];
1196 if (assoc_array_ptr_is_meta(ptr)) {
1202 pr_devel("leaves: %ld [m=%d]\n",
1203 node->nr_leaves_on_branch - 1, has_meta);
1205 /* Look further up the tree to see if we can collapse this node
1206 * into a more proximal node too.
1210 pr_devel("collapse subtree: %ld\n", parent->nr_leaves_on_branch);
1212 ptr = parent->back_pointer;
1215 if (assoc_array_ptr_is_shortcut(ptr)) {
1216 struct assoc_array_shortcut *s = assoc_array_ptr_to_shortcut(ptr);
1217 ptr = s->back_pointer;
1222 grandparent = assoc_array_ptr_to_node(ptr);
1223 if (grandparent->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
1224 parent = grandparent;
1229 /* There's no point collapsing if the original node has no meta
1230 * pointers to discard and if we didn't merge into one of that
1233 if (has_meta || parent != node) {
1236 /* Create a new node to collapse into */
1237 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
1240 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
1242 new_n0->back_pointer = node->back_pointer;
1243 new_n0->parent_slot = node->parent_slot;
1244 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
1245 edit->adjust_count_on = new_n0;
1247 collapse.node = new_n0;
1248 collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);
1250 assoc_array_subtree_iterate(assoc_array_node_to_ptr(node),
1252 assoc_array_delete_collapse_iterator,
1254 pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch);
1255 BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1);
1257 if (!node->back_pointer) {
1258 edit->set[1].ptr = &array->root;
1259 } else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
1261 } else if (assoc_array_ptr_is_node(node->back_pointer)) {
1262 struct assoc_array_node *p =
1263 assoc_array_ptr_to_node(node->back_pointer);
1264 edit->set[1].ptr = &p->slots[node->parent_slot];
1265 } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) {
1266 struct assoc_array_shortcut *s =
1267 assoc_array_ptr_to_shortcut(node->back_pointer);
1268 edit->set[1].ptr = &s->next_node;
1270 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
1271 edit->excised_subtree = assoc_array_node_to_ptr(node);
1278 /* Clean up after an out of memory error */
1279 pr_devel("enomem\n");
1280 assoc_array_cancel_edit(edit);
1281 return ERR_PTR(-ENOMEM);
1285 * assoc_array_clear - Script deletion of all objects from an associative array
1286 * @array: The array to clear.
1287 * @ops: The operations to use.
1289 * Precalculate and preallocate a script for the deletion of all the objects
1290 * from an associative array. This results in an edit script that can either
1291 * be applied or cancelled.
1293 * The function returns a pointer to an edit script if there are objects to be
1294 * deleted, NULL if there are no objects in the array or -ENOMEM.
1296 * The caller should lock against other modifications and must continue to hold
1297 * the lock until assoc_array_apply_edit() has been called.
1299 * Accesses to the tree may take place concurrently with this function,
1300 * provided they hold the RCU read lock.
1302 struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
1303 const struct assoc_array_ops *ops)
1305 struct assoc_array_edit *edit;
1307 pr_devel("-->%s()\n", __func__);
1312 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1314 return ERR_PTR(-ENOMEM);
1315 edit->array = array;
1317 edit->set[1].ptr = &array->root;
1318 edit->set[1].to = NULL;
1319 edit->excised_subtree = array->root;
1320 edit->ops_for_excised_subtree = ops;
1321 pr_devel("all gone\n");
1326 * Handle the deferred destruction after an applied edit.
1328 static void assoc_array_rcu_cleanup(struct rcu_head *head)
1330 struct assoc_array_edit *edit =
1331 container_of(head, struct assoc_array_edit, rcu);
1334 pr_devel("-->%s()\n", __func__);
1336 if (edit->dead_leaf)
1337 edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));
1338 for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)
1339 if (edit->excised_meta[i])
1340 kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));
1342 if (edit->excised_subtree) {
1343 BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));
1344 if (assoc_array_ptr_is_node(edit->excised_subtree)) {
1345 struct assoc_array_node *n =
1346 assoc_array_ptr_to_node(edit->excised_subtree);
1347 n->back_pointer = NULL;
1349 struct assoc_array_shortcut *s =
1350 assoc_array_ptr_to_shortcut(edit->excised_subtree);
1351 s->back_pointer = NULL;
1353 assoc_array_destroy_subtree(edit->excised_subtree,
1354 edit->ops_for_excised_subtree);
1361 * assoc_array_apply_edit - Apply an edit script to an associative array
1362 * @edit: The script to apply.
1364 * Apply an edit script to an associative array to effect an insertion,
1365 * deletion or clearance. As the edit script includes preallocated memory,
1366 * this is guaranteed not to fail.
1368 * The edit script, dead objects and dead metadata will be scheduled for
1369 * destruction after an RCU grace period to permit those doing read-only
1370 * accesses on the array to continue to do so under the RCU read lock whilst
1371 * the edit is taking place.
1373 void assoc_array_apply_edit(struct assoc_array_edit *edit)
1375 struct assoc_array_shortcut *shortcut;
1376 struct assoc_array_node *node;
1377 struct assoc_array_ptr *ptr;
1380 pr_devel("-->%s()\n", __func__);
1384 *edit->leaf_p = edit->leaf;
1387 for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)
1388 if (edit->set_parent_slot[i].p)
1389 *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;
1392 for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)
1393 if (edit->set_backpointers[i])
1394 *edit->set_backpointers[i] = edit->set_backpointers_to;
1397 for (i = 0; i < ARRAY_SIZE(edit->set); i++)
1398 if (edit->set[i].ptr)
1399 *edit->set[i].ptr = edit->set[i].to;
1401 if (edit->array->root == NULL) {
1402 edit->array->nr_leaves_on_tree = 0;
1403 } else if (edit->adjust_count_on) {
1404 node = edit->adjust_count_on;
1406 node->nr_leaves_on_branch += edit->adjust_count_by;
1408 ptr = node->back_pointer;
1411 if (assoc_array_ptr_is_shortcut(ptr)) {
1412 shortcut = assoc_array_ptr_to_shortcut(ptr);
1413 ptr = shortcut->back_pointer;
1417 BUG_ON(!assoc_array_ptr_is_node(ptr));
1418 node = assoc_array_ptr_to_node(ptr);
1421 edit->array->nr_leaves_on_tree += edit->adjust_count_by;
1424 call_rcu(&edit->rcu, assoc_array_rcu_cleanup);
1428 * assoc_array_cancel_edit - Discard an edit script.
1429 * @edit: The script to discard.
1431 * Free an edit script and all the preallocated data it holds without making
1432 * any changes to the associative array it was intended for.
1434 * NOTE! In the case of an insertion script, this does _not_ release the leaf
1435 * that was to be inserted. That is left to the caller.
1437 void assoc_array_cancel_edit(struct assoc_array_edit *edit)
1439 struct assoc_array_ptr *ptr;
1442 pr_devel("-->%s()\n", __func__);
1444 /* Clean up after an out of memory error */
1445 for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {
1446 ptr = edit->new_meta[i];
1448 if (assoc_array_ptr_is_node(ptr))
1449 kfree(assoc_array_ptr_to_node(ptr));
1451 kfree(assoc_array_ptr_to_shortcut(ptr));
1458 * assoc_array_gc - Garbage collect an associative array.
1459 * @array: The array to clean.
1460 * @ops: The operations to use.
1461 * @iterator: A callback function to pass judgement on each object.
1462 * @iterator_data: Private data for the callback function.
1464 * Collect garbage from an associative array and pack down the internal tree to
1467 * The iterator function is asked to pass judgement upon each object in the
1468 * array. If it returns false, the object is discard and if it returns true,
1469 * the object is kept. If it returns true, it must increment the object's
1470 * usage count (or whatever it needs to do to retain it) before returning.
1472 * This function returns 0 if successful or -ENOMEM if out of memory. In the
1473 * latter case, the array is not changed.
1475 * The caller should lock against other modifications and must continue to hold
1476 * the lock until assoc_array_apply_edit() has been called.
1478 * Accesses to the tree may take place concurrently with this function,
1479 * provided they hold the RCU read lock.
1481 int assoc_array_gc(struct assoc_array *array,
1482 const struct assoc_array_ops *ops,
1483 bool (*iterator)(void *object, void *iterator_data),
1484 void *iterator_data)
1486 struct assoc_array_shortcut *shortcut, *new_s;
1487 struct assoc_array_node *node, *new_n;
1488 struct assoc_array_edit *edit;
1489 struct assoc_array_ptr *cursor, *ptr;
1490 struct assoc_array_ptr *new_root, *new_parent, **new_ptr_pp;
1491 unsigned long nr_leaves_on_tree;
1492 int keylen, slot, nr_free, next_slot, i;
1494 pr_devel("-->%s()\n", __func__);
1499 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1502 edit->array = array;
1504 edit->ops_for_excised_subtree = ops;
1505 edit->set[0].ptr = &array->root;
1506 edit->excised_subtree = array->root;
1508 new_root = new_parent = NULL;
1509 new_ptr_pp = &new_root;
1510 cursor = array->root;
1513 /* If this point is a shortcut, then we need to duplicate it and
1514 * advance the target cursor.
1516 if (assoc_array_ptr_is_shortcut(cursor)) {
1517 shortcut = assoc_array_ptr_to_shortcut(cursor);
1518 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
1519 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
1520 new_s = kmalloc(sizeof(struct assoc_array_shortcut) +
1521 keylen * sizeof(unsigned long), GFP_KERNEL);
1524 pr_devel("dup shortcut %p -> %p\n", shortcut, new_s);
1525 memcpy(new_s, shortcut, (sizeof(struct assoc_array_shortcut) +
1526 keylen * sizeof(unsigned long)));
1527 new_s->back_pointer = new_parent;
1528 new_s->parent_slot = shortcut->parent_slot;
1529 *new_ptr_pp = new_parent = assoc_array_shortcut_to_ptr(new_s);
1530 new_ptr_pp = &new_s->next_node;
1531 cursor = shortcut->next_node;
1534 /* Duplicate the node at this position */
1535 node = assoc_array_ptr_to_node(cursor);
1536 new_n = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
1539 pr_devel("dup node %p -> %p\n", node, new_n);
1540 new_n->back_pointer = new_parent;
1541 new_n->parent_slot = node->parent_slot;
1542 *new_ptr_pp = new_parent = assoc_array_node_to_ptr(new_n);
1547 /* Filter across any leaves and gc any subtrees */
1548 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1549 ptr = node->slots[slot];
1553 if (assoc_array_ptr_is_leaf(ptr)) {
1554 if (iterator(assoc_array_ptr_to_leaf(ptr),
1556 /* The iterator will have done any reference
1557 * counting on the object for us.
1559 new_n->slots[slot] = ptr;
1563 new_ptr_pp = &new_n->slots[slot];
1568 pr_devel("-- compress node %p --\n", new_n);
1570 /* Count up the number of empty slots in this node and work out the
1571 * subtree leaf count.
1573 new_n->nr_leaves_on_branch = 0;
1575 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1576 ptr = new_n->slots[slot];
1579 else if (assoc_array_ptr_is_leaf(ptr))
1580 new_n->nr_leaves_on_branch++;
1582 pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch);
1584 /* See what we can fold in */
1586 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1587 struct assoc_array_shortcut *s;
1588 struct assoc_array_node *child;
1590 ptr = new_n->slots[slot];
1591 if (!ptr || assoc_array_ptr_is_leaf(ptr))
1595 if (assoc_array_ptr_is_shortcut(ptr)) {
1596 s = assoc_array_ptr_to_shortcut(ptr);
1600 child = assoc_array_ptr_to_node(ptr);
1601 new_n->nr_leaves_on_branch += child->nr_leaves_on_branch;
1603 if (child->nr_leaves_on_branch <= nr_free + 1) {
1604 /* Fold the child node into this one */
1605 pr_devel("[%d] fold node %lu/%d [nx %d]\n",
1606 slot, child->nr_leaves_on_branch, nr_free + 1,
1609 /* We would already have reaped an intervening shortcut
1610 * on the way back up the tree.
1614 new_n->slots[slot] = NULL;
1616 if (slot < next_slot)
1618 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
1619 struct assoc_array_ptr *p = child->slots[i];
1622 BUG_ON(assoc_array_ptr_is_meta(p));
1623 while (new_n->slots[next_slot])
1625 BUG_ON(next_slot >= ASSOC_ARRAY_FAN_OUT);
1626 new_n->slots[next_slot++] = p;
1631 pr_devel("[%d] retain node %lu/%d [nx %d]\n",
1632 slot, child->nr_leaves_on_branch, nr_free + 1,
1637 pr_devel("after: %lu\n", new_n->nr_leaves_on_branch);
1639 nr_leaves_on_tree = new_n->nr_leaves_on_branch;
1641 /* Excise this node if it is singly occupied by a shortcut */
1642 if (nr_free == ASSOC_ARRAY_FAN_OUT - 1) {
1643 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++)
1644 if ((ptr = new_n->slots[slot]))
1647 if (assoc_array_ptr_is_meta(ptr) &&
1648 assoc_array_ptr_is_shortcut(ptr)) {
1649 pr_devel("excise node %p with 1 shortcut\n", new_n);
1650 new_s = assoc_array_ptr_to_shortcut(ptr);
1651 new_parent = new_n->back_pointer;
1652 slot = new_n->parent_slot;
1655 new_s->back_pointer = NULL;
1656 new_s->parent_slot = 0;
1661 if (assoc_array_ptr_is_shortcut(new_parent)) {
1662 /* We can discard any preceding shortcut also */
1663 struct assoc_array_shortcut *s =
1664 assoc_array_ptr_to_shortcut(new_parent);
1666 pr_devel("excise preceding shortcut\n");
1668 new_parent = new_s->back_pointer = s->back_pointer;
1669 slot = new_s->parent_slot = s->parent_slot;
1672 new_s->back_pointer = NULL;
1673 new_s->parent_slot = 0;
1679 new_s->back_pointer = new_parent;
1680 new_s->parent_slot = slot;
1681 new_n = assoc_array_ptr_to_node(new_parent);
1682 new_n->slots[slot] = ptr;
1683 goto ascend_old_tree;
1687 /* Excise any shortcuts we might encounter that point to nodes that
1688 * only contain leaves.
1690 ptr = new_n->back_pointer;
1694 if (assoc_array_ptr_is_shortcut(ptr)) {
1695 new_s = assoc_array_ptr_to_shortcut(ptr);
1696 new_parent = new_s->back_pointer;
1697 slot = new_s->parent_slot;
1699 if (new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
1700 struct assoc_array_node *n;
1702 pr_devel("excise shortcut\n");
1703 new_n->back_pointer = new_parent;
1704 new_n->parent_slot = slot;
1707 new_root = assoc_array_node_to_ptr(new_n);
1711 n = assoc_array_ptr_to_node(new_parent);
1712 n->slots[slot] = assoc_array_node_to_ptr(new_n);
1717 new_n = assoc_array_ptr_to_node(new_parent);
1720 ptr = node->back_pointer;
1721 if (assoc_array_ptr_is_shortcut(ptr)) {
1722 shortcut = assoc_array_ptr_to_shortcut(ptr);
1723 slot = shortcut->parent_slot;
1724 cursor = shortcut->back_pointer;
1726 slot = node->parent_slot;
1730 node = assoc_array_ptr_to_node(cursor);
1735 edit->set[0].to = new_root;
1736 assoc_array_apply_edit(edit);
1737 edit->array->nr_leaves_on_tree = nr_leaves_on_tree;
1741 pr_devel("enomem\n");
1742 assoc_array_destroy_subtree(new_root, edit->ops);