Release 4.9 lib/assoc_array.c

/* Generic associative array implementation.
 *
 * See Documentation/assoc_array.txt for information.
 *
 * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
 * Written by David Howells (dhowells@redhat.com)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public Licence
 * as published by the Free Software Foundation; either version
 * 2 of the Licence, or (at your option) any later version.
 */
//#define DEBUG
#include <linux/rcupdate.h>
#include <linux/slab.h>
#include <linux/err.h>
#include <linux/assoc_array_priv.h>

/*
 * Iterate over an associative array.  The caller must hold the RCU read lock
 * or better.
 */


static int assoc_array_subtree_iterate(const struct assoc_array_ptr *root,
				       const struct assoc_array_ptr *stop,
				       int (*iterator)(const void *leaf,
						       void *iterator_data),
				       void *iterator_data)
{
	const struct assoc_array_shortcut *shortcut;
	const struct assoc_array_node *node;
	const struct assoc_array_ptr *cursor, *ptr, *parent;
	unsigned long has_meta;
	int slot, ret;

	cursor = root;

begin_node:
	if (assoc_array_ptr_is_shortcut(cursor)) {
		/* Descend through a shortcut */
		shortcut = assoc_array_ptr_to_shortcut(cursor);
		smp_read_barrier_depends();
		cursor = ACCESS_ONCE(shortcut->next_node);
	}

	node = assoc_array_ptr_to_node(cursor);
	smp_read_barrier_depends();
	slot = 0;

	/* We perform two passes of each node.
         *
         * The first pass does all the leaves in this node.  This means we
         * don't miss any leaves if the node is split up by insertion whilst
         * we're iterating over the branches rooted here (we may, however, see
         * some leaves twice).
         */
	has_meta = 0;
	for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
		ptr = ACCESS_ONCE(node->slots[slot]);
		has_meta |= (unsigned long)ptr;
		if (ptr && assoc_array_ptr_is_leaf(ptr)) {
			/* We need a barrier between the read of the pointer
                         * and dereferencing the pointer - but only if we are
                         * actually going to dereference it.
                         */
			smp_read_barrier_depends();

			/* Invoke the callback */
			ret = iterator(assoc_array_ptr_to_leaf(ptr),
				       iterator_data);
			if (ret)
				return ret;
		}
	}

	/* The second pass attends to all the metadata pointers.  If we follow
         * one of these we may find that we don't come back here, but rather go
         * back to a replacement node with the leaves in a different layout.
         *
         * We are guaranteed to make progress, however, as the slot number for
         * a particular portion of the key space cannot change - and we
         * continue at the back pointer + 1.
         */
	if (!(has_meta & ASSOC_ARRAY_PTR_META_TYPE))
		goto finished_node;
	slot = 0;

continue_node:
	node = assoc_array_ptr_to_node(cursor);
	smp_read_barrier_depends();

	for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
		ptr = ACCESS_ONCE(node->slots[slot]);
		if (assoc_array_ptr_is_meta(ptr)) {
			cursor = ptr;
			goto begin_node;
		}
	}

finished_node:
	/* Move up to the parent (may need to skip back over a shortcut) */
	parent = ACCESS_ONCE(node->back_pointer);
	slot = node->parent_slot;
	if (parent == stop)
		return 0;

	if (assoc_array_ptr_is_shortcut(parent)) {
		shortcut = assoc_array_ptr_to_shortcut(parent);
		smp_read_barrier_depends();
		cursor = parent;
		parent = ACCESS_ONCE(shortcut->back_pointer);
		slot = shortcut->parent_slot;
		if (parent == stop)
			return 0;
	}

	/* Ascend to next slot in parent node */
	cursor = parent;
	slot++;
	goto continue_node;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
david howells
david howells
346
100.00%
1
100.00%
Total
346
100.00%
1
100.00%

/**
 * assoc_array_iterate - Pass all objects in the array to a callback
 * @array: The array to iterate over.
 * @iterator: The callback function.
 * @iterator_data: Private data for the callback function.
 *
 * Iterate over all the objects in an associative array.  Each one will be
 * presented to the iterator function.
 *
 * If the array is being modified concurrently with the iteration then it is
 * possible that some objects in the array will be passed to the iterator
 * callback more than once - though every object should be passed at least
 * once.  If this is undesirable then the caller must lock against modification
 * for the duration of this function.
 *
 * The function will return 0 if no objects were in the array or else it will
 * return the result of the last iterator function called.  Iteration stops
 * immediately if any call to the iteration function results in a non-zero
 * return.
 *
 * The caller should hold the RCU read lock or better if concurrent
 * modification is possible.
 */


int assoc_array_iterate(const struct assoc_array *array,
			int (*iterator)(const void *object,
					void *iterator_data),
			void *iterator_data)
{
	struct assoc_array_ptr *root = ACCESS_ONCE(array->root);

	if (!root)
		return 0;
	return assoc_array_subtree_iterate(root, NULL, iterator, iterator_data);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
david howells
david howells
63
100.00%
1
100.00%
Total
63
100.00%
1
100.00%


enum assoc_array_walk_status {
	
assoc_array_walk_tree_empty,
	
assoc_array_walk_found_terminal_node,
	
assoc_array_walk_found_wrong_shortcut,
};


struct assoc_array_walk_result {
	struct {
		
struct assoc_array_node	*node;	/* Node in which leaf might be found */
		
int		level;
		
int		slot;
	} 
terminal_node;
	struct {
		
struct assoc_array_shortcut *shortcut;
		
int		level;
		
int		sc_level;
		
unsigned long	sc_segments;
		
unsigned long	dissimilarity;
	} 
wrong_shortcut;
};

/*
 * Navigate through the internal tree looking for the closest node to the key.
 */

static enum assoc_array_walk_status

assoc_array_walk(const struct assoc_array *array,
		 const struct assoc_array_ops *ops,
		 const void *index_key,
		 struct assoc_array_walk_result *result)
{
	struct assoc_array_shortcut *shortcut;
	struct assoc_array_node *node;
	struct assoc_array_ptr *cursor, *ptr;
	unsigned long sc_segments, dissimilarity;
	unsigned long segments;
	int level, sc_level, next_sc_level;
	int slot;

	pr_devel("-->%s()\n", __func__);

	cursor = ACCESS_ONCE(array->root);
	if (!cursor)
		return assoc_array_walk_tree_empty;

	level = 0;

	/* Use segments from the key for the new leaf to navigate through the
         * internal tree, skipping through nodes and shortcuts that are on
         * route to the destination.  Eventually we'll come to a slot that is
         * either empty or contains a leaf at which point we've found a node in
         * which the leaf we're looking for might be found or into which it
         * should be inserted.
         */
jumped:
	segments = ops->get_key_chunk(index_key, level);
	pr_devel("segments[%d]: %lx\n", level, segments);

	if (assoc_array_ptr_is_shortcut(cursor))
		goto follow_shortcut;

consider_node:
	node = assoc_array_ptr_to_node(cursor);
	smp_read_barrier_depends();

	slot = segments >> (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
	slot &= ASSOC_ARRAY_FAN_MASK;
	ptr = ACCESS_ONCE(node->slots[slot]);

	pr_devel("consider slot %x [ix=%d type=%lu]\n",
		 slot, level, (unsigned long)ptr & 3);

	if (!assoc_array_ptr_is_meta(ptr)) {
		/* The node doesn't have a node/shortcut pointer in the slot
                 * corresponding to the index key that we have to follow.
                 */
		result->terminal_node.node = node;
		result->terminal_node.level = level;
		result->terminal_node.slot = slot;
		pr_devel("<--%s() = terminal_node\n", __func__);
		return assoc_array_walk_found_terminal_node;
	}

	if (assoc_array_ptr_is_node(ptr)) {
		/* There is a pointer to a node in the slot corresponding to
                 * this index key segment, so we need to follow it.
                 */
		cursor = ptr;
		level += ASSOC_ARRAY_LEVEL_STEP;
		if ((level & ASSOC_ARRAY_KEY_CHUNK_MASK) != 0)
			goto consider_node;
		goto jumped;
	}

	/* There is a shortcut in the slot corresponding to the index key
         * segment.  We follow the shortcut if its partial index key matches
         * this leaf's.  Otherwise we need to split the shortcut.
         */
	cursor = ptr;
follow_shortcut:
	shortcut = assoc_array_ptr_to_shortcut(cursor);
	smp_read_barrier_depends();
	pr_devel("shortcut to %d\n", shortcut->skip_to_level);
	sc_level = level + ASSOC_ARRAY_LEVEL_STEP;
	BUG_ON(sc_level > shortcut->skip_to_level);

	do {
		/* Check the leaf against the shortcut's index key a word at a
                 * time, trimming the final word (the shortcut stores the index
                 * key completely from the root to the shortcut's target).
                 */
		if ((sc_level & ASSOC_ARRAY_KEY_CHUNK_MASK) == 0)
			segments = ops->get_key_chunk(index_key, sc_level);

		sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
		dissimilarity = segments ^ sc_segments;

		if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) {
			/* Trim segments that are beyond the shortcut */
			int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
			dissimilarity &= ~(ULONG_MAX << shift);
			next_sc_level = shortcut->skip_to_level;
		} else {
			next_sc_level = sc_level + ASSOC_ARRAY_KEY_CHUNK_SIZE;
			next_sc_level = round_down(next_sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
		}

		if (dissimilarity != 0) {
			/* This shortcut points elsewhere */
			result->wrong_shortcut.shortcut = shortcut;
			result->wrong_shortcut.level = level;
			result->wrong_shortcut.sc_level = sc_level;
			result->wrong_shortcut.sc_segments = sc_segments;
			result->wrong_shortcut.dissimilarity = dissimilarity;
			return assoc_array_walk_found_wrong_shortcut;
		}

		sc_level = next_sc_level;
	} while (sc_level < shortcut->skip_to_level);

	/* The shortcut matches the leaf's index to this point. */
	cursor = ACCESS_ONCE(shortcut->next_node);
	if (((level ^ sc_level) & ~ASSOC_ARRAY_KEY_CHUNK_MASK) != 0) {
		level = sc_level;
		goto jumped;
	} else {
		level = sc_level;
		goto consider_node;
	}
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
david howells
david howells
512
100.00%
1
100.00%
Total
512
100.00%
1
100.00%

/**
 * assoc_array_find - Find an object by index key
 * @array: The associative array to search.
 * @ops: The operations to use.
 * @index_key: The key to the object.
 *
 * Find an object in an associative array by walking through the internal tree
 * to the node that should contain the object and then searching the leaves
 * there.  NULL is returned if the requested object was not found in the array.
 *
 * The caller must hold the RCU read lock or better.
 */


void *assoc_array_find(const struct assoc_array *array,
		       const struct assoc_array_ops *ops,
		       const void *index_key)
{
	struct assoc_array_walk_result result;
	const struct assoc_array_node *node;
	const struct assoc_array_ptr *ptr;
	const void *leaf;
	int slot;

	if (assoc_array_walk(array, ops, index_key, &result) !=
	    assoc_array_walk_found_terminal_node)
		return NULL;

	node = result.terminal_node.node;
	smp_read_barrier_depends();

	/* If the target key is available to us, it's has to be pointed to by
         * the terminal node.
         */
	for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
		ptr = ACCESS_ONCE(node->slots[slot]);
		if (ptr && assoc_array_ptr_is_leaf(ptr)) {
			/* We need a barrier between the read of the pointer
                         * and dereferencing the pointer - but only if we are
                         * actually going to dereference it.
                         */
			leaf = assoc_array_ptr_to_leaf(ptr);
			smp_read_barrier_depends();
			if (ops->compare_object(leaf, index_key))
				return (void *)leaf;
		}
	}

	return NULL;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
david howells
david howells
148
100.00%
1
100.00%
Total
148
100.00%
1
100.00%

/*
 * Destructively iterate over an associative array.  The caller must prevent
 * other simultaneous accesses.
 */


static void assoc_array_destroy_subtree(struct assoc_array_ptr *root,
					const struct assoc_array_ops *ops)
{
	struct assoc_array_shortcut *shortcut;
	struct assoc_array_node *node;
	struct assoc_array_ptr *cursor, *parent = NULL;
	int slot = -1;

	pr_devel("-->%s()\n", __func__);

	cursor = root;
	if (!cursor) {
		pr_devel("empty\n");
		return;
	}

move_to_meta:
	if (assoc_array_ptr_is_shortcut(cursor)) {
		/* Descend through a shortcut */
		pr_devel("[%d] shortcut\n", slot);
		BUG_ON(!assoc_array_ptr_is_shortcut(cursor));
		shortcut = assoc_array_ptr_to_shortcut(cursor);
		BUG_ON(shortcut->back_pointer != parent);
		BUG_ON(slot != -1 && shortcut->parent_slot != slot);
		parent = cursor;
		cursor = shortcut->next_node;
		slot = -1;
		BUG_ON(!assoc_array_ptr_is_node(cursor));
	}

	pr_devel("[%d] node\n", slot);
	node = assoc_array_ptr_to_node(cursor);
	BUG_ON(node->back_pointer != parent);
	BUG_ON(slot != -1 && node->parent_slot != slot);
	slot = 0;

continue_node:
	pr_devel("Node %p [back=%p]\n", node, node->back_pointer);
	for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
		struct assoc_array_ptr *ptr = node->slots[slot];
		if (!ptr)
			continue;
		if (assoc_array_ptr_is_meta(ptr)) {
			parent = cursor;
			cursor = ptr;
			goto move_to_meta;
		}

		if (ops) {
			pr_devel("[%d] free leaf\n", slot);
			ops->free_object(assoc_array_ptr_to_leaf(ptr));
		}
	}

	parent = node->back_pointer;
	slot = node->parent_slot;
	pr_devel("free node\n");
	kfree(node);
	if (!parent)
		return; /* Done */

	/* Move back up to the parent (may need to free a shortcut on
         * the way up) */
	if (assoc_array_ptr_is_shortcut(parent)) {
		shortcut = assoc_array_ptr_to_shortcut(parent);
		BUG_ON(shortcut->next_node != cursor);
		cursor = parent;
		parent = shortcut->back_pointer;
		slot = shortcut->parent_slot;
		pr_devel("free shortcut\n");
		kfree(shortcut);
		if (!parent)
			return;

		BUG_ON(!assoc_array_ptr_is_node(parent));
	}

	/* Ascend to next slot in parent node */
	pr_devel("ascend to %p[%d]\n", parent, slot);
	cursor = parent;
	node = assoc_array_ptr_to_node(cursor);
	slot++;
	goto continue_node;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
david howells
david howells
399
100.00%
1
100.00%
Total
399
100.00%
1
100.00%

/**
 * assoc_array_destroy - Destroy an associative array
 * @array: The array to destroy.
 * @ops: The operations to use.
 *
 * Discard all metadata and free all objects in an associative array.  The
 * array will be empty and ready to use again upon completion.  This function
 * cannot fail.
 *
 * The caller must prevent all other accesses whilst this takes place as no
 * attempt is made to adjust pointers gracefully to permit RCU readlock-holding
 * accesses to continue.  On the other hand, no memory allocation is required.
 */


void assoc_array_destroy(struct assoc_array *array,
			 const struct assoc_array_ops *ops)
{
	assoc_array_destroy_subtree(array->root, ops);
	array->root = NULL;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
david howells
david howells
31
100.00%
1
100.00%
Total
31
100.00%
1
100.00%

/*
 * Handle insertion into an empty tree.
 */


static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit)
{
	struct assoc_array_node *new_n0;

	pr_devel("-->%s()\n", __func__);

	new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
	if (!new_n0)
		return false;

	edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
	edit->leaf_p = &new_n0->slots[0];
	edit->adjust_count_on = new_n0;
	edit->set[0].ptr = &edit->array->root;
	edit->set[0].to = assoc_array_node_to_ptr(new_n0);

	pr_devel("<--%s() = ok [no root]\n", __func__);
	return true;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
david howells
david howells
114
100.00%
1
100.00%
Total
114
100.00%
1
100.00%

/*
 * Handle insertion into a terminal node.
 */


static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
						  const struct assoc_array_ops *ops,
						  const void *index_key,
						  struct assoc_array_walk_result *result)
{
	struct assoc_array_shortcut *shortcut, *new_s0;
	struct assoc_array_node *node, *new_n0, *new_n1, *side;
	struct assoc_array_ptr *ptr;
	unsigned long dissimilarity, base_seg, blank;
	size_t keylen;
	bool have_meta;
	int level, diff;
	int slot, next_slot, free_slot, i, j;

	node	= result->terminal_node.node;
	level	= result->terminal_node.level;
	edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot;

	pr_devel("-->%s()\n", __func__);

	/* We arrived at a node which doesn't have an onward node or shortcut
         * pointer that we have to follow.  This means that (a) the leaf we
         * want must go here (either by insertion or replacement) or (b) we
         * need to split this node and insert in one of the fragments.
         */
	free_slot = -1;

	/* Firstly, we have to check the leaves in this node to see if there's
         * a matching one we should replace in place.
         */
	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
		ptr = node->slots[i];
		if (!ptr) {
			free_slot = i;
			continue;
		}
		if (assoc_array_ptr_is_leaf(ptr) &&
		    ops->compare_object(assoc_array_ptr_to_leaf(ptr),
					index_key)) {
			pr_devel("replace in slot %d\n", i);
			edit->leaf_p = &node->slots[i];
			edit->dead_leaf = node->slots[i];
			pr_devel("<--%s() = ok [replace]\n", __func__);
			return true;
		}
	}

	/* If there is a free slot in this node then we can just insert the
         * leaf here.
         */
	if (free_slot >= 0) {
		pr_devel("insert in free slot %d\n", free_slot);
		edit->leaf_p = &node->slots[free_slot];
		edit->adjust_count_on = node;
		pr_devel("<--%s() = ok [insert]\n", __func__);
		return true;
	}

	/* The node has no spare slots - so we're either going to have to split
         * it or insert another node before it.
         *
         * Whatever, we're going to need at least two new nodes - so allocate
         * those now.  We may also need a new shortcut, but we deal with that
         * when we need it.
         */
	new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
	if (!new_n0)
		return false;
	edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
	new_n1 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
	if (!new_n1)
		return false;
	edit->new_meta[1] = assoc_array_node_to_ptr(new_n1);

	/* We need to find out how similar the leaves are. */
	pr_devel("no spare slots\n");
	have_meta = false;
	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
		ptr = node->slots[i];
		if (assoc_array_ptr_is_meta(ptr)) {
			edit->segment_cache[i] = 0xff;
			have_meta = true;
			continue;
		}
		base_seg = ops->get_object_key_chunk(
			assoc_array_ptr_to_leaf(ptr), level);
		base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
		edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
	}

	if (have_meta) {
		pr_devel("have meta\n");
		goto split_node;
	}

	/* The node contains only leaves */
	dissimilarity = 0;
	base_seg = edit->segment_cache[0];
	for (i = 1; i < ASSOC_ARRAY_FAN_OUT; i++)
		dissimilarity |= edit->segment_cache[i] ^ base_seg;

	pr_devel("only leaves; dissimilarity=%lx\n", dissimilarity);

	if ((dissimilarity & ASSOC_ARRAY_FAN_MASK) == 0) {
		/* The old leaves all cluster in the same slot.  We will need
                 * to insert a shortcut if the new node wants to cluster with them.
                 */
		if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)
			goto all_leaves_cluster_together;

		/* Otherwise we can just insert a new node ahead of the old
                 * one.
                 */
		goto present_leaves_cluster_but_not_new_leaf;
	}

split_node:
	pr_devel("split node\n");

	/* We need to split the current node; we know that the node doesn't
         * simply contain a full set of leaves that cluster together (it
         * contains meta pointers and/or non-clustering leaves).
         *
         * We need to expel at least two leaves out of a set consisting of the
         * leaves in the node and the new leaf.
         *
         * We need a new node (n0) to replace the current one and a new node to
         * take the expelled nodes (n1).
         */
	edit->set[0].to = assoc_array_node_to_ptr(new_n0);
	new_n0->back_pointer = node->back_pointer;
	new_n0->parent_slot = node->parent_slot;
	new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
	new_n1->parent_slot = -1; /* Need to calculate this */

do_split_node:
	pr_devel("do_split_node\n");

	new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
	new_n1->nr_leaves_on_branch = 0;

	/* Begin by finding two matching leaves.  There have to be at least two
         * that match - even if there are meta pointers - because any leaf that
         * would match a slot with a meta pointer in it must be somewhere
         * behind that meta pointer and cannot be here.  Further, given N
         * remaining leaf slots, we now have N+1 leaves to go in them.
         */
	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
		slot = edit->segment_cache[i];
		if (slot != 0xff)
			for (j = i + 1; j < ASSOC_ARRAY_FAN_OUT + 1; j++)
				if (edit->segment_cache[j] == slot)
					goto found_slot_for_multiple_occupancy;
	}
found_slot_for_multiple_occupancy:
	pr_devel("same slot: %x %x [%02x]\n", i, j, slot);
	BUG_ON(i >= ASSOC_ARRAY_FAN_OUT);
	BUG_ON(j >= ASSOC_ARRAY_FAN_OUT + 1);
	BUG_ON(slot >= ASSOC_ARRAY_FAN_OUT);

	new_n1->parent_slot = slot;

	/* Metadata pointers cannot change slot */
	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
		if (assoc_array_ptr_is_meta(node->slots[i]))
			new_n0->slots[i] = node->slots[i];
		else
			new_n0->slots[i] = NULL;
	BUG_ON(new_n0->slots[slot] != NULL);
	new_n0->slots[slot] = assoc_array_node_to_ptr(new_n1);

	/* Filter the leaf pointers between the new nodes */
	free_slot = -1;
	next_slot = 0;
	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
		if (assoc_array_ptr_is_meta(node->slots[i]))
			continue;
		if (edit->segment_cache[i] == slot) {
			new_n1->slots[next_slot++] = node->slots[i];
			new_n1->nr_leaves_on_branch++;
		} else {
			do {
				free_slot++;
			} while (new_n0->slots[free_slot] != NULL);
			new_n0->slots[free_slot] = node->slots[i];
		}
	}

	pr_devel("filtered: f=%x n=%x\n", free_slot, next_slot);

	if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {
		do {
			free_slot++;
		} while (new_n0->slots[free_slot] != NULL);
		edit->leaf_p = &new_n0->slots[free_slot];
		edit->adjust_count_on = new_n0;
	} else {
		edit->leaf_p = &new_n1->slots[next_slot++];
		edit->adjust_count_on = new_n1;
	}

	BUG_ON(next_slot <= 1);

	edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);
	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
		if (edit->segment_cache[i] == 0xff) {
			ptr = node->slots[i];
			BUG_ON(assoc_array_ptr_is_leaf(ptr));
			if (assoc_array_ptr_is_node(ptr)) {
				side = assoc_array_ptr_to_node(ptr);
				edit->set_backpointers[i] = &side->back_pointer;
			} else {
				shortcut = assoc_array_ptr_to_shortcut(ptr);
				edit->set_backpointers[i] = &shortcut->back_pointer;
			}
		}
	}

	ptr = node->back_pointer;
	if (!ptr)
		edit->set[0].ptr = &edit->array->root;
	else if (assoc_array_ptr_is_node(ptr))
		edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];
	else
		edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node;
	edit->excised_meta[0] = assoc_array_node_to_ptr(node);
	pr_devel("<--%s() = ok [split node]\n", __func__);
	return true;

present_leaves_cluster_but_not_new_leaf:
	/* All the old leaves cluster in the same slot, but the new leaf wants
         * to go into a different slot, so we create a new node to hold the new
         * leaf and a pointer to a new node holding all the old leaves.
         */
	pr_devel("present leaves cluster but not new leaf\n");

	new_n0->back_pointer = node->back_pointer;
	new_n0->parent_slot = node->parent_slot;
	new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
	new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
	new_n1->parent_slot = edit->segment_cache[0];
	new_n1->nr_leaves_on_branch = node->nr_leaves_on_branch;
	edit->adjust_count_on = new_n0;

	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
		new_n1->slots[i]