1 /*
2  * lib/btree.c	- Simple In-memory B+Tree
3  *
4  * As should be obvious for Linux kernel code, license is GPLv2
5  *
6  * Copyright (c) 2007-2008 Joern Engel <joern@logfs.org>
7  * Bits and pieces stolen from Peter Zijlstra's code, which is
8  * Copyright 2007, Red Hat Inc. Peter Zijlstra <pzijlstr@redhat.com>
9  * GPLv2
10  *
11  * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
12  *
13  * A relatively simple B+Tree implementation.  I have written it as a learning
14  * exercise to understand how B+Trees work.  Turned out to be useful as well.
15  *
16  * B+Trees can be used similar to Linux radix trees (which don't have anything
17  * in common with textbook radix trees, beware).  Prerequisite for them working
18  * well is that access to a random tree node is much faster than a large number
19  * of operations within each node.
20  *
21  * Disks have fulfilled the prerequisite for a long time.  More recently DRAM
22  * has gained similar properties, as memory access times, when measured in cpu
23  * cycles, have increased.  Cacheline sizes have increased as well, which also
24  * helps B+Trees.
25  *
26  * Compared to radix trees, B+Trees are more efficient when dealing with a
27  * sparsely populated address space.  Between 25% and 50% of the memory is
28  * occupied with valid pointers.  When densely populated, radix trees contain
29  * ~98% pointers - hard to beat.  Very sparse radix trees contain only ~2%
30  * pointers.
31  *
32  * This particular implementation stores pointers identified by a long value.
33  * Storing NULL pointers is illegal, lookup will return NULL when no entry
34  * was found.
35  *
36  * A tricks was used that is not commonly found in textbooks.  The lowest
37  * values are to the right, not to the left.  All used slots within a node
38  * are on the left, all unused slots contain NUL values.  Most operations
39  * simply loop once over all slots and terminate on the first NUL.
40  */
41 
42 #include <linux/btree.h>
43 #include <linux/cache.h>
44 #include <linux/kernel.h>
45 #include <linux/slab.h>
46 #include <linux/module.h>
47 
48 #define MAX(a, b) ((a) > (b) ? (a) : (b))
49 #define NODESIZE MAX(L1_CACHE_BYTES, 128)
50 
51 struct btree_geo {
52 	int keylen;
53 	int no_pairs;
54 	int no_longs;
55 };
56 
57 struct btree_geo btree_geo32 = {
58 	.keylen = 1,
59 	.no_pairs = NODESIZE / sizeof(long) / 2,
60 	.no_longs = NODESIZE / sizeof(long) / 2,
61 };
62 EXPORT_SYMBOL_GPL(btree_geo32);
63 
64 #define LONG_PER_U64 (64 / BITS_PER_LONG)
65 struct btree_geo btree_geo64 = {
66 	.keylen = LONG_PER_U64,
67 	.no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
68 	.no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),
69 };
70 EXPORT_SYMBOL_GPL(btree_geo64);
71 
72 struct btree_geo btree_geo128 = {
73 	.keylen = 2 * LONG_PER_U64,
74 	.no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
75 	.no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),
76 };
77 EXPORT_SYMBOL_GPL(btree_geo128);
78 
79 static struct kmem_cache *btree_cachep;
80 
btree_alloc(gfp_t gfp_mask,void * pool_data)81 void *btree_alloc(gfp_t gfp_mask, void *pool_data)
82 {
83 	return kmem_cache_alloc(btree_cachep, gfp_mask);
84 }
85 EXPORT_SYMBOL_GPL(btree_alloc);
86 
btree_free(void * element,void * pool_data)87 void btree_free(void *element, void *pool_data)
88 {
89 	kmem_cache_free(btree_cachep, element);
90 }
91 EXPORT_SYMBOL_GPL(btree_free);
92 
btree_node_alloc(struct btree_head * head,gfp_t gfp)93 static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
94 {
95 	unsigned long *node;
96 
97 	node = mempool_alloc(head->mempool, gfp);
98 	if (likely(node))
99 		memset(node, 0, NODESIZE);
100 	return node;
101 }
102 
longcmp(const unsigned long * l1,const unsigned long * l2,size_t n)103 static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n)
104 {
105 	size_t i;
106 
107 	for (i = 0; i < n; i++) {
108 		if (l1[i] < l2[i])
109 			return -1;
110 		if (l1[i] > l2[i])
111 			return 1;
112 	}
113 	return 0;
114 }
115 
longcpy(unsigned long * dest,const unsigned long * src,size_t n)116 static unsigned long *longcpy(unsigned long *dest, const unsigned long *src,
117 		size_t n)
118 {
119 	size_t i;
120 
121 	for (i = 0; i < n; i++)
122 		dest[i] = src[i];
123 	return dest;
124 }
125 
longset(unsigned long * s,unsigned long c,size_t n)126 static unsigned long *longset(unsigned long *s, unsigned long c, size_t n)
127 {
128 	size_t i;
129 
130 	for (i = 0; i < n; i++)
131 		s[i] = c;
132 	return s;
133 }
134 
dec_key(struct btree_geo * geo,unsigned long * key)135 static void dec_key(struct btree_geo *geo, unsigned long *key)
136 {
137 	unsigned long val;
138 	int i;
139 
140 	for (i = geo->keylen - 1; i >= 0; i--) {
141 		val = key[i];
142 		key[i] = val - 1;
143 		if (val)
144 			break;
145 	}
146 }
147 
bkey(struct btree_geo * geo,unsigned long * node,int n)148 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
149 {
150 	return &node[n * geo->keylen];
151 }
152 
bval(struct btree_geo * geo,unsigned long * node,int n)153 static void *bval(struct btree_geo *geo, unsigned long *node, int n)
154 {
155 	return (void *)node[geo->no_longs + n];
156 }
157 
setkey(struct btree_geo * geo,unsigned long * node,int n,unsigned long * key)158 static void setkey(struct btree_geo *geo, unsigned long *node, int n,
159 		   unsigned long *key)
160 {
161 	longcpy(bkey(geo, node, n), key, geo->keylen);
162 }
163 
setval(struct btree_geo * geo,unsigned long * node,int n,void * val)164 static void setval(struct btree_geo *geo, unsigned long *node, int n,
165 		   void *val)
166 {
167 	node[geo->no_longs + n] = (unsigned long) val;
168 }
169 
clearpair(struct btree_geo * geo,unsigned long * node,int n)170 static void clearpair(struct btree_geo *geo, unsigned long *node, int n)
171 {
172 	longset(bkey(geo, node, n), 0, geo->keylen);
173 	node[geo->no_longs + n] = 0;
174 }
175 
__btree_init(struct btree_head * head)176 static inline void __btree_init(struct btree_head *head)
177 {
178 	head->node = NULL;
179 	head->height = 0;
180 }
181 
btree_init_mempool(struct btree_head * head,mempool_t * mempool)182 void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
183 {
184 	__btree_init(head);
185 	head->mempool = mempool;
186 }
187 EXPORT_SYMBOL_GPL(btree_init_mempool);
188 
btree_init(struct btree_head * head)189 int btree_init(struct btree_head *head)
190 {
191 	__btree_init(head);
192 	head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);
193 	if (!head->mempool)
194 		return -ENOMEM;
195 	return 0;
196 }
197 EXPORT_SYMBOL_GPL(btree_init);
198 
btree_destroy(struct btree_head * head)199 void btree_destroy(struct btree_head *head)
200 {
201 	mempool_destroy(head->mempool);
202 	head->mempool = NULL;
203 }
204 EXPORT_SYMBOL_GPL(btree_destroy);
205 
btree_last(struct btree_head * head,struct btree_geo * geo,unsigned long * key)206 void *btree_last(struct btree_head *head, struct btree_geo *geo,
207 		 unsigned long *key)
208 {
209 	int height = head->height;
210 	unsigned long *node = head->node;
211 
212 	if (height == 0)
213 		return NULL;
214 
215 	for ( ; height > 1; height--)
216 		node = bval(geo, node, 0);
217 
218 	longcpy(key, bkey(geo, node, 0), geo->keylen);
219 	return bval(geo, node, 0);
220 }
221 EXPORT_SYMBOL_GPL(btree_last);
222 
keycmp(struct btree_geo * geo,unsigned long * node,int pos,unsigned long * key)223 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
224 		  unsigned long *key)
225 {
226 	return longcmp(bkey(geo, node, pos), key, geo->keylen);
227 }
228 
keyzero(struct btree_geo * geo,unsigned long * key)229 static int keyzero(struct btree_geo *geo, unsigned long *key)
230 {
231 	int i;
232 
233 	for (i = 0; i < geo->keylen; i++)
234 		if (key[i])
235 			return 0;
236 
237 	return 1;
238 }
239 
btree_lookup(struct btree_head * head,struct btree_geo * geo,unsigned long * key)240 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
241 		unsigned long *key)
242 {
243 	int i, height = head->height;
244 	unsigned long *node = head->node;
245 
246 	if (height == 0)
247 		return NULL;
248 
249 	for ( ; height > 1; height--) {
250 		for (i = 0; i < geo->no_pairs; i++)
251 			if (keycmp(geo, node, i, key) <= 0)
252 				break;
253 		if (i == geo->no_pairs)
254 			return NULL;
255 		node = bval(geo, node, i);
256 		if (!node)
257 			return NULL;
258 	}
259 
260 	if (!node)
261 		return NULL;
262 
263 	for (i = 0; i < geo->no_pairs; i++)
264 		if (keycmp(geo, node, i, key) == 0)
265 			return bval(geo, node, i);
266 	return NULL;
267 }
268 EXPORT_SYMBOL_GPL(btree_lookup);
269 
btree_update(struct btree_head * head,struct btree_geo * geo,unsigned long * key,void * val)270 int btree_update(struct btree_head *head, struct btree_geo *geo,
271 		 unsigned long *key, void *val)
272 {
273 	int i, height = head->height;
274 	unsigned long *node = head->node;
275 
276 	if (height == 0)
277 		return -ENOENT;
278 
279 	for ( ; height > 1; height--) {
280 		for (i = 0; i < geo->no_pairs; i++)
281 			if (keycmp(geo, node, i, key) <= 0)
282 				break;
283 		if (i == geo->no_pairs)
284 			return -ENOENT;
285 		node = bval(geo, node, i);
286 		if (!node)
287 			return -ENOENT;
288 	}
289 
290 	if (!node)
291 		return -ENOENT;
292 
293 	for (i = 0; i < geo->no_pairs; i++)
294 		if (keycmp(geo, node, i, key) == 0) {
295 			setval(geo, node, i, val);
296 			return 0;
297 		}
298 	return -ENOENT;
299 }
300 EXPORT_SYMBOL_GPL(btree_update);
301 
302 /*
303  * Usually this function is quite similar to normal lookup.  But the key of
304  * a parent node may be smaller than the smallest key of all its siblings.
305  * In such a case we cannot just return NULL, as we have only proven that no
306  * key smaller than __key, but larger than this parent key exists.
307  * So we set __key to the parent key and retry.  We have to use the smallest
308  * such parent key, which is the last parent key we encountered.
309  */
btree_get_prev(struct btree_head * head,struct btree_geo * geo,unsigned long * __key)310 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
311 		     unsigned long *__key)
312 {
313 	int i, height;
314 	unsigned long *node, *oldnode;
315 	unsigned long *retry_key = NULL, key[geo->keylen];
316 
317 	if (keyzero(geo, __key))
318 		return NULL;
319 
320 	if (head->height == 0)
321 		return NULL;
322 	longcpy(key, __key, geo->keylen);
323 retry:
324 	dec_key(geo, key);
325 
326 	node = head->node;
327 	for (height = head->height ; height > 1; height--) {
328 		for (i = 0; i < geo->no_pairs; i++)
329 			if (keycmp(geo, node, i, key) <= 0)
330 				break;
331 		if (i == geo->no_pairs)
332 			goto miss;
333 		oldnode = node;
334 		node = bval(geo, node, i);
335 		if (!node)
336 			goto miss;
337 		retry_key = bkey(geo, oldnode, i);
338 	}
339 
340 	if (!node)
341 		goto miss;
342 
343 	for (i = 0; i < geo->no_pairs; i++) {
344 		if (keycmp(geo, node, i, key) <= 0) {
345 			if (bval(geo, node, i)) {
346 				longcpy(__key, bkey(geo, node, i), geo->keylen);
347 				return bval(geo, node, i);
348 			} else
349 				goto miss;
350 		}
351 	}
352 miss:
353 	if (retry_key) {
354 		longcpy(key, retry_key, geo->keylen);
355 		retry_key = NULL;
356 		goto retry;
357 	}
358 	return NULL;
359 }
360 EXPORT_SYMBOL_GPL(btree_get_prev);
361 
getpos(struct btree_geo * geo,unsigned long * node,unsigned long * key)362 static int getpos(struct btree_geo *geo, unsigned long *node,
363 		unsigned long *key)
364 {
365 	int i;
366 
367 	for (i = 0; i < geo->no_pairs; i++) {
368 		if (keycmp(geo, node, i, key) <= 0)
369 			break;
370 	}
371 	return i;
372 }
373 
getfill(struct btree_geo * geo,unsigned long * node,int start)374 static int getfill(struct btree_geo *geo, unsigned long *node, int start)
375 {
376 	int i;
377 
378 	for (i = start; i < geo->no_pairs; i++)
379 		if (!bval(geo, node, i))
380 			break;
381 	return i;
382 }
383 
384 /*
385  * locate the correct leaf node in the btree
386  */
find_level(struct btree_head * head,struct btree_geo * geo,unsigned long * key,int level)387 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
388 		unsigned long *key, int level)
389 {
390 	unsigned long *node = head->node;
391 	int i, height;
392 
393 	for (height = head->height; height > level; height--) {
394 		for (i = 0; i < geo->no_pairs; i++)
395 			if (keycmp(geo, node, i, key) <= 0)
396 				break;
397 
398 		if ((i == geo->no_pairs) || !bval(geo, node, i)) {
399 			/* right-most key is too large, update it */
400 			/* FIXME: If the right-most key on higher levels is
401 			 * always zero, this wouldn't be necessary. */
402 			i--;
403 			setkey(geo, node, i, key);
404 		}
405 		BUG_ON(i < 0);
406 		node = bval(geo, node, i);
407 	}
408 	BUG_ON(!node);
409 	return node;
410 }
411 
btree_grow(struct btree_head * head,struct btree_geo * geo,gfp_t gfp)412 static int btree_grow(struct btree_head *head, struct btree_geo *geo,
413 		      gfp_t gfp)
414 {
415 	unsigned long *node;
416 	int fill;
417 
418 	node = btree_node_alloc(head, gfp);
419 	if (!node)
420 		return -ENOMEM;
421 	if (head->node) {
422 		fill = getfill(geo, head->node, 0);
423 		setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
424 		setval(geo, node, 0, head->node);
425 	}
426 	head->node = node;
427 	head->height++;
428 	return 0;
429 }
430 
btree_shrink(struct btree_head * head,struct btree_geo * geo)431 static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
432 {
433 	unsigned long *node;
434 	int fill;
435 
436 	if (head->height <= 1)
437 		return;
438 
439 	node = head->node;
440 	fill = getfill(geo, node, 0);
441 	BUG_ON(fill > 1);
442 	head->node = bval(geo, node, 0);
443 	head->height--;
444 	mempool_free(node, head->mempool);
445 }
446 
btree_insert_level(struct btree_head * head,struct btree_geo * geo,unsigned long * key,void * val,int level,gfp_t gfp)447 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
448 			      unsigned long *key, void *val, int level,
449 			      gfp_t gfp)
450 {
451 	unsigned long *node;
452 	int i, pos, fill, err;
453 
454 	BUG_ON(!val);
455 	if (head->height < level) {
456 		err = btree_grow(head, geo, gfp);
457 		if (err)
458 			return err;
459 	}
460 
461 retry:
462 	node = find_level(head, geo, key, level);
463 	pos = getpos(geo, node, key);
464 	fill = getfill(geo, node, pos);
465 	/* two identical keys are not allowed */
466 	BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
467 
468 	if (fill == geo->no_pairs) {
469 		/* need to split node */
470 		unsigned long *new;
471 
472 		new = btree_node_alloc(head, gfp);
473 		if (!new)
474 			return -ENOMEM;
475 		err = btree_insert_level(head, geo,
476 				bkey(geo, node, fill / 2 - 1),
477 				new, level + 1, gfp);
478 		if (err) {
479 			mempool_free(new, head->mempool);
480 			return err;
481 		}
482 		for (i = 0; i < fill / 2; i++) {
483 			setkey(geo, new, i, bkey(geo, node, i));
484 			setval(geo, new, i, bval(geo, node, i));
485 			setkey(geo, node, i, bkey(geo, node, i + fill / 2));
486 			setval(geo, node, i, bval(geo, node, i + fill / 2));
487 			clearpair(geo, node, i + fill / 2);
488 		}
489 		if (fill & 1) {
490 			setkey(geo, node, i, bkey(geo, node, fill - 1));
491 			setval(geo, node, i, bval(geo, node, fill - 1));
492 			clearpair(geo, node, fill - 1);
493 		}
494 		goto retry;
495 	}
496 	BUG_ON(fill >= geo->no_pairs);
497 
498 	/* shift and insert */
499 	for (i = fill; i > pos; i--) {
500 		setkey(geo, node, i, bkey(geo, node, i - 1));
501 		setval(geo, node, i, bval(geo, node, i - 1));
502 	}
503 	setkey(geo, node, pos, key);
504 	setval(geo, node, pos, val);
505 
506 	return 0;
507 }
508 
btree_insert(struct btree_head * head,struct btree_geo * geo,unsigned long * key,void * val,gfp_t gfp)509 int btree_insert(struct btree_head *head, struct btree_geo *geo,
510 		unsigned long *key, void *val, gfp_t gfp)
511 {
512 	return btree_insert_level(head, geo, key, val, 1, gfp);
513 }
514 EXPORT_SYMBOL_GPL(btree_insert);
515 
516 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
517 		unsigned long *key, int level);
merge(struct btree_head * head,struct btree_geo * geo,int level,unsigned long * left,int lfill,unsigned long * right,int rfill,unsigned long * parent,int lpos)518 static void merge(struct btree_head *head, struct btree_geo *geo, int level,
519 		unsigned long *left, int lfill,
520 		unsigned long *right, int rfill,
521 		unsigned long *parent, int lpos)
522 {
523 	int i;
524 
525 	for (i = 0; i < rfill; i++) {
526 		/* Move all keys to the left */
527 		setkey(geo, left, lfill + i, bkey(geo, right, i));
528 		setval(geo, left, lfill + i, bval(geo, right, i));
529 	}
530 	/* Exchange left and right child in parent */
531 	setval(geo, parent, lpos, right);
532 	setval(geo, parent, lpos + 1, left);
533 	/* Remove left (formerly right) child from parent */
534 	btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
535 	mempool_free(right, head->mempool);
536 }
537 
rebalance(struct btree_head * head,struct btree_geo * geo,unsigned long * key,int level,unsigned long * child,int fill)538 static void rebalance(struct btree_head *head, struct btree_geo *geo,
539 		unsigned long *key, int level, unsigned long *child, int fill)
540 {
541 	unsigned long *parent, *left = NULL, *right = NULL;
542 	int i, no_left, no_right;
543 
544 	if (fill == 0) {
545 		/* Because we don't steal entries from a neighbour, this case
546 		 * can happen.  Parent node contains a single child, this
547 		 * node, so merging with a sibling never happens.
548 		 */
549 		btree_remove_level(head, geo, key, level + 1);
550 		mempool_free(child, head->mempool);
551 		return;
552 	}
553 
554 	parent = find_level(head, geo, key, level + 1);
555 	i = getpos(geo, parent, key);
556 	BUG_ON(bval(geo, parent, i) != child);
557 
558 	if (i > 0) {
559 		left = bval(geo, parent, i - 1);
560 		no_left = getfill(geo, left, 0);
561 		if (fill + no_left <= geo->no_pairs) {
562 			merge(head, geo, level,
563 					left, no_left,
564 					child, fill,
565 					parent, i - 1);
566 			return;
567 		}
568 	}
569 	if (i + 1 < getfill(geo, parent, i)) {
570 		right = bval(geo, parent, i + 1);
571 		no_right = getfill(geo, right, 0);
572 		if (fill + no_right <= geo->no_pairs) {
573 			merge(head, geo, level,
574 					child, fill,
575 					right, no_right,
576 					parent, i);
577 			return;
578 		}
579 	}
580 	/*
581 	 * We could also try to steal one entry from the left or right
582 	 * neighbor.  By not doing so we changed the invariant from
583 	 * "all nodes are at least half full" to "no two neighboring
584 	 * nodes can be merged".  Which means that the average fill of
585 	 * all nodes is still half or better.
586 	 */
587 }
588 
btree_remove_level(struct btree_head * head,struct btree_geo * geo,unsigned long * key,int level)589 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
590 		unsigned long *key, int level)
591 {
592 	unsigned long *node;
593 	int i, pos, fill;
594 	void *ret;
595 
596 	if (level > head->height) {
597 		/* we recursed all the way up */
598 		head->height = 0;
599 		head->node = NULL;
600 		return NULL;
601 	}
602 
603 	node = find_level(head, geo, key, level);
604 	pos = getpos(geo, node, key);
605 	fill = getfill(geo, node, pos);
606 	if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
607 		return NULL;
608 	ret = bval(geo, node, pos);
609 
610 	/* remove and shift */
611 	for (i = pos; i < fill - 1; i++) {
612 		setkey(geo, node, i, bkey(geo, node, i + 1));
613 		setval(geo, node, i, bval(geo, node, i + 1));
614 	}
615 	clearpair(geo, node, fill - 1);
616 
617 	if (fill - 1 < geo->no_pairs / 2) {
618 		if (level < head->height)
619 			rebalance(head, geo, key, level, node, fill - 1);
620 		else if (fill - 1 == 1)
621 			btree_shrink(head, geo);
622 	}
623 
624 	return ret;
625 }
626 
btree_remove(struct btree_head * head,struct btree_geo * geo,unsigned long * key)627 void *btree_remove(struct btree_head *head, struct btree_geo *geo,
628 		unsigned long *key)
629 {
630 	if (head->height == 0)
631 		return NULL;
632 
633 	return btree_remove_level(head, geo, key, 1);
634 }
635 EXPORT_SYMBOL_GPL(btree_remove);
636 
btree_merge(struct btree_head * target,struct btree_head * victim,struct btree_geo * geo,gfp_t gfp)637 int btree_merge(struct btree_head *target, struct btree_head *victim,
638 		struct btree_geo *geo, gfp_t gfp)
639 {
640 	unsigned long key[geo->keylen];
641 	unsigned long dup[geo->keylen];
642 	void *val;
643 	int err;
644 
645 	BUG_ON(target == victim);
646 
647 	if (!(target->node)) {
648 		/* target is empty, just copy fields over */
649 		target->node = victim->node;
650 		target->height = victim->height;
651 		__btree_init(victim);
652 		return 0;
653 	}
654 
655 	/* TODO: This needs some optimizations.  Currently we do three tree
656 	 * walks to remove a single object from the victim.
657 	 */
658 	for (;;) {
659 		if (!btree_last(victim, geo, key))
660 			break;
661 		val = btree_lookup(victim, geo, key);
662 		err = btree_insert(target, geo, key, val, gfp);
663 		if (err)
664 			return err;
665 		/* We must make a copy of the key, as the original will get
666 		 * mangled inside btree_remove. */
667 		longcpy(dup, key, geo->keylen);
668 		btree_remove(victim, geo, dup);
669 	}
670 	return 0;
671 }
672 EXPORT_SYMBOL_GPL(btree_merge);
673 
__btree_for_each(struct btree_head * head,struct btree_geo * geo,unsigned long * node,unsigned long opaque,void (* func)(void * elem,unsigned long opaque,unsigned long * key,size_t index,void * func2),void * func2,int reap,int height,size_t count)674 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
675 			       unsigned long *node, unsigned long opaque,
676 			       void (*func)(void *elem, unsigned long opaque,
677 					    unsigned long *key, size_t index,
678 					    void *func2),
679 			       void *func2, int reap, int height, size_t count)
680 {
681 	int i;
682 	unsigned long *child;
683 
684 	for (i = 0; i < geo->no_pairs; i++) {
685 		child = bval(geo, node, i);
686 		if (!child)
687 			break;
688 		if (height > 1)
689 			count = __btree_for_each(head, geo, child, opaque,
690 					func, func2, reap, height - 1, count);
691 		else
692 			func(child, opaque, bkey(geo, node, i), count++,
693 					func2);
694 	}
695 	if (reap)
696 		mempool_free(node, head->mempool);
697 	return count;
698 }
699 
empty(void * elem,unsigned long opaque,unsigned long * key,size_t index,void * func2)700 static void empty(void *elem, unsigned long opaque, unsigned long *key,
701 		  size_t index, void *func2)
702 {
703 }
704 
visitorl(void * elem,unsigned long opaque,unsigned long * key,size_t index,void * __func)705 void visitorl(void *elem, unsigned long opaque, unsigned long *key,
706 	      size_t index, void *__func)
707 {
708 	visitorl_t func = __func;
709 
710 	func(elem, opaque, *key, index);
711 }
712 EXPORT_SYMBOL_GPL(visitorl);
713 
visitor32(void * elem,unsigned long opaque,unsigned long * __key,size_t index,void * __func)714 void visitor32(void *elem, unsigned long opaque, unsigned long *__key,
715 	       size_t index, void *__func)
716 {
717 	visitor32_t func = __func;
718 	u32 *key = (void *)__key;
719 
720 	func(elem, opaque, *key, index);
721 }
722 EXPORT_SYMBOL_GPL(visitor32);
723 
visitor64(void * elem,unsigned long opaque,unsigned long * __key,size_t index,void * __func)724 void visitor64(void *elem, unsigned long opaque, unsigned long *__key,
725 	       size_t index, void *__func)
726 {
727 	visitor64_t func = __func;
728 	u64 *key = (void *)__key;
729 
730 	func(elem, opaque, *key, index);
731 }
732 EXPORT_SYMBOL_GPL(visitor64);
733 
visitor128(void * elem,unsigned long opaque,unsigned long * __key,size_t index,void * __func)734 void visitor128(void *elem, unsigned long opaque, unsigned long *__key,
735 		size_t index, void *__func)
736 {
737 	visitor128_t func = __func;
738 	u64 *key = (void *)__key;
739 
740 	func(elem, opaque, key[0], key[1], index);
741 }
742 EXPORT_SYMBOL_GPL(visitor128);
743 
btree_visitor(struct btree_head * head,struct btree_geo * geo,unsigned long opaque,void (* func)(void * elem,unsigned long opaque,unsigned long * key,size_t index,void * func2),void * func2)744 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
745 		     unsigned long opaque,
746 		     void (*func)(void *elem, unsigned long opaque,
747 		     		  unsigned long *key,
748 		     		  size_t index, void *func2),
749 		     void *func2)
750 {
751 	size_t count = 0;
752 
753 	if (!func2)
754 		func = empty;
755 	if (head->node)
756 		count = __btree_for_each(head, geo, head->node, opaque, func,
757 				func2, 0, head->height, 0);
758 	return count;
759 }
760 EXPORT_SYMBOL_GPL(btree_visitor);
761 
btree_grim_visitor(struct btree_head * head,struct btree_geo * geo,unsigned long opaque,void (* func)(void * elem,unsigned long opaque,unsigned long * key,size_t index,void * func2),void * func2)762 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
763 			  unsigned long opaque,
764 			  void (*func)(void *elem, unsigned long opaque,
765 				       unsigned long *key,
766 				       size_t index, void *func2),
767 			  void *func2)
768 {
769 	size_t count = 0;
770 
771 	if (!func2)
772 		func = empty;
773 	if (head->node)
774 		count = __btree_for_each(head, geo, head->node, opaque, func,
775 				func2, 1, head->height, 0);
776 	__btree_init(head);
777 	return count;
778 }
779 EXPORT_SYMBOL_GPL(btree_grim_visitor);
780 
btree_module_init(void)781 static int __init btree_module_init(void)
782 {
783 	btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0,
784 			SLAB_HWCACHE_ALIGN, NULL);
785 	return 0;
786 }
787 
btree_module_exit(void)788 static void __exit btree_module_exit(void)
789 {
790 	kmem_cache_destroy(btree_cachep);
791 }
792 
793 /* If core code starts using btree, initialization should happen even earlier */
794 module_init(btree_module_init);
795 module_exit(btree_module_exit);
796 
797 MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
798 MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
799 MODULE_LICENSE("GPL");
800