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