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