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