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