1425 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Code for working with individual keys, and sorted sets of keys with in a4 * btree node5 *6 * Copyright 2012 Google, Inc.7 */8 9#define pr_fmt(fmt) "bcache: %s() " fmt, __func__10 11#include "util.h"12#include "bset.h"13 14#include <linux/console.h>15#include <linux/sched/clock.h>16#include <linux/random.h>17#include <linux/prefetch.h>18 19#ifdef CONFIG_BCACHE_DEBUG20 21void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned int set)22{23 struct bkey *k, *next;24 25 for (k = i->start; k < bset_bkey_last(i); k = next) {26 next = bkey_next(k);27 28 pr_err("block %u key %u/%u: ", set,29 (unsigned int) ((u64 *) k - i->d), i->keys);30 31 if (b->ops->key_dump)32 b->ops->key_dump(b, k);33 else34 pr_cont("%llu:%llu\n", KEY_INODE(k), KEY_OFFSET(k));35 36 if (next < bset_bkey_last(i) &&37 bkey_cmp(k, b->ops->is_extents ?38 &START_KEY(next) : next) > 0)39 pr_err("Key skipped backwards\n");40 }41}42 43void bch_dump_bucket(struct btree_keys *b)44{45 unsigned int i;46 47 console_lock();48 for (i = 0; i <= b->nsets; i++)49 bch_dump_bset(b, b->set[i].data,50 bset_sector_offset(b, b->set[i].data));51 console_unlock();52}53 54int __bch_count_data(struct btree_keys *b)55{56 unsigned int ret = 0;57 struct btree_iter iter;58 struct bkey *k;59 60 min_heap_init(&iter.heap, NULL, MAX_BSETS);61 62 if (b->ops->is_extents)63 for_each_key(b, k, &iter)64 ret += KEY_SIZE(k);65 return ret;66}67 68void __bch_check_keys(struct btree_keys *b, const char *fmt, ...)69{70 va_list args;71 struct bkey *k, *p = NULL;72 struct btree_iter iter;73 const char *err;74 75 min_heap_init(&iter.heap, NULL, MAX_BSETS);76 77 for_each_key(b, k, &iter) {78 if (b->ops->is_extents) {79 err = "Keys out of order";80 if (p && bkey_cmp(&START_KEY(p), &START_KEY(k)) > 0)81 goto bug;82 83 if (bch_ptr_invalid(b, k))84 continue;85 86 err = "Overlapping keys";87 if (p && bkey_cmp(p, &START_KEY(k)) > 0)88 goto bug;89 } else {90 if (bch_ptr_bad(b, k))91 continue;92 93 err = "Duplicate keys";94 if (p && !bkey_cmp(p, k))95 goto bug;96 }97 p = k;98 }99#if 0100 err = "Key larger than btree node key";101 if (p && bkey_cmp(p, &b->key) > 0)102 goto bug;103#endif104 return;105bug:106 bch_dump_bucket(b);107 108 va_start(args, fmt);109 vprintk(fmt, args);110 va_end(args);111 112 panic("bch_check_keys error: %s:\n", err);113}114 115static void bch_btree_iter_next_check(struct btree_iter *iter)116{117 struct bkey *k = iter->heap.data->k, *next = bkey_next(k);118 119 if (next < iter->heap.data->end &&120 bkey_cmp(k, iter->b->ops->is_extents ?121 &START_KEY(next) : next) > 0) {122 bch_dump_bucket(iter->b);123 panic("Key skipped backwards\n");124 }125}126 127#else128 129static inline void bch_btree_iter_next_check(struct btree_iter *iter) {}130 131#endif132 133/* Keylists */134 135int __bch_keylist_realloc(struct keylist *l, unsigned int u64s)136{137 size_t oldsize = bch_keylist_nkeys(l);138 size_t newsize = oldsize + u64s;139 uint64_t *old_keys = l->keys_p == l->inline_keys ? NULL : l->keys_p;140 uint64_t *new_keys;141 142 newsize = roundup_pow_of_two(newsize);143 144 if (newsize <= KEYLIST_INLINE ||145 roundup_pow_of_two(oldsize) == newsize)146 return 0;147 148 new_keys = krealloc(old_keys, sizeof(uint64_t) * newsize, GFP_NOIO);149 150 if (!new_keys)151 return -ENOMEM;152 153 if (!old_keys)154 memcpy(new_keys, l->inline_keys, sizeof(uint64_t) * oldsize);155 156 l->keys_p = new_keys;157 l->top_p = new_keys + oldsize;158 159 return 0;160}161 162/* Pop the top key of keylist by pointing l->top to its previous key */163struct bkey *bch_keylist_pop(struct keylist *l)164{165 struct bkey *k = l->keys;166 167 if (k == l->top)168 return NULL;169 170 while (bkey_next(k) != l->top)171 k = bkey_next(k);172 173 return l->top = k;174}175 176/* Pop the bottom key of keylist and update l->top_p */177void bch_keylist_pop_front(struct keylist *l)178{179 l->top_p -= bkey_u64s(l->keys);180 181 memmove(l->keys,182 bkey_next(l->keys),183 bch_keylist_bytes(l));184}185 186/* Key/pointer manipulation */187 188void bch_bkey_copy_single_ptr(struct bkey *dest, const struct bkey *src,189 unsigned int i)190{191 BUG_ON(i > KEY_PTRS(src));192 193 /* Only copy the header, key, and one pointer. */194 memcpy(dest, src, 2 * sizeof(uint64_t));195 dest->ptr[0] = src->ptr[i];196 SET_KEY_PTRS(dest, 1);197 /* We didn't copy the checksum so clear that bit. */198 SET_KEY_CSUM(dest, 0);199}200 201bool __bch_cut_front(const struct bkey *where, struct bkey *k)202{203 unsigned int i, len = 0;204 205 if (bkey_cmp(where, &START_KEY(k)) <= 0)206 return false;207 208 if (bkey_cmp(where, k) < 0)209 len = KEY_OFFSET(k) - KEY_OFFSET(where);210 else211 bkey_copy_key(k, where);212 213 for (i = 0; i < KEY_PTRS(k); i++)214 SET_PTR_OFFSET(k, i, PTR_OFFSET(k, i) + KEY_SIZE(k) - len);215 216 BUG_ON(len > KEY_SIZE(k));217 SET_KEY_SIZE(k, len);218 return true;219}220 221bool __bch_cut_back(const struct bkey *where, struct bkey *k)222{223 unsigned int len = 0;224 225 if (bkey_cmp(where, k) >= 0)226 return false;227 228 BUG_ON(KEY_INODE(where) != KEY_INODE(k));229 230 if (bkey_cmp(where, &START_KEY(k)) > 0)231 len = KEY_OFFSET(where) - KEY_START(k);232 233 bkey_copy_key(k, where);234 235 BUG_ON(len > KEY_SIZE(k));236 SET_KEY_SIZE(k, len);237 return true;238}239 240/* Auxiliary search trees */241 242/* 32 bits total: */243#define BKEY_MID_BITS 3244#define BKEY_EXPONENT_BITS 7245#define BKEY_MANTISSA_BITS (32 - BKEY_MID_BITS - BKEY_EXPONENT_BITS)246#define BKEY_MANTISSA_MASK ((1 << BKEY_MANTISSA_BITS) - 1)247 248struct bkey_float {249 unsigned int exponent:BKEY_EXPONENT_BITS;250 unsigned int m:BKEY_MID_BITS;251 unsigned int mantissa:BKEY_MANTISSA_BITS;252} __packed;253 254/*255 * BSET_CACHELINE was originally intended to match the hardware cacheline size -256 * it used to be 64, but I realized the lookup code would touch slightly less257 * memory if it was 128.258 *259 * It definites the number of bytes (in struct bset) per struct bkey_float in260 * the auxiliar search tree - when we're done searching the bset_float tree we261 * have this many bytes left that we do a linear search over.262 *263 * Since (after level 5) every level of the bset_tree is on a new cacheline,264 * we're touching one fewer cacheline in the bset tree in exchange for one more265 * cacheline in the linear search - but the linear search might stop before it266 * gets to the second cacheline.267 */268 269#define BSET_CACHELINE 128270 271/* Space required for the btree node keys */272static inline size_t btree_keys_bytes(struct btree_keys *b)273{274 return PAGE_SIZE << b->page_order;275}276 277static inline size_t btree_keys_cachelines(struct btree_keys *b)278{279 return btree_keys_bytes(b) / BSET_CACHELINE;280}281 282/* Space required for the auxiliary search trees */283static inline size_t bset_tree_bytes(struct btree_keys *b)284{285 return btree_keys_cachelines(b) * sizeof(struct bkey_float);286}287 288/* Space required for the prev pointers */289static inline size_t bset_prev_bytes(struct btree_keys *b)290{291 return btree_keys_cachelines(b) * sizeof(uint8_t);292}293 294/* Memory allocation */295 296void bch_btree_keys_free(struct btree_keys *b)297{298 struct bset_tree *t = b->set;299 300 if (bset_prev_bytes(b) < PAGE_SIZE)301 kfree(t->prev);302 else303 free_pages((unsigned long) t->prev,304 get_order(bset_prev_bytes(b)));305 306 if (bset_tree_bytes(b) < PAGE_SIZE)307 kfree(t->tree);308 else309 free_pages((unsigned long) t->tree,310 get_order(bset_tree_bytes(b)));311 312 free_pages((unsigned long) t->data, b->page_order);313 314 t->prev = NULL;315 t->tree = NULL;316 t->data = NULL;317}318 319int bch_btree_keys_alloc(struct btree_keys *b,320 unsigned int page_order,321 gfp_t gfp)322{323 struct bset_tree *t = b->set;324 325 BUG_ON(t->data);326 327 b->page_order = page_order;328 329 t->data = (void *) __get_free_pages(__GFP_COMP|gfp, b->page_order);330 if (!t->data)331 goto err;332 333 t->tree = bset_tree_bytes(b) < PAGE_SIZE334 ? kmalloc(bset_tree_bytes(b), gfp)335 : (void *) __get_free_pages(gfp, get_order(bset_tree_bytes(b)));336 if (!t->tree)337 goto err;338 339 t->prev = bset_prev_bytes(b) < PAGE_SIZE340 ? kmalloc(bset_prev_bytes(b), gfp)341 : (void *) __get_free_pages(gfp, get_order(bset_prev_bytes(b)));342 if (!t->prev)343 goto err;344 345 return 0;346err:347 bch_btree_keys_free(b);348 return -ENOMEM;349}350 351void bch_btree_keys_init(struct btree_keys *b, const struct btree_keys_ops *ops,352 bool *expensive_debug_checks)353{354 b->ops = ops;355 b->expensive_debug_checks = expensive_debug_checks;356 b->nsets = 0;357 b->last_set_unwritten = 0;358 359 /*360 * struct btree_keys in embedded in struct btree, and struct361 * bset_tree is embedded into struct btree_keys. They are all362 * initialized as 0 by kzalloc() in mca_bucket_alloc(), and363 * b->set[0].data is allocated in bch_btree_keys_alloc(), so we364 * don't have to initiate b->set[].size and b->set[].data here365 * any more.366 */367}368 369/* Binary tree stuff for auxiliary search trees */370 371/*372 * return array index next to j when does in-order traverse373 * of a binary tree which is stored in a linear array374 */375static unsigned int inorder_next(unsigned int j, unsigned int size)376{377 if (j * 2 + 1 < size) {378 j = j * 2 + 1;379 380 while (j * 2 < size)381 j *= 2;382 } else383 j >>= ffz(j) + 1;384 385 return j;386}387 388/*389 * return array index previous to j when does in-order traverse390 * of a binary tree which is stored in a linear array391 */392static unsigned int inorder_prev(unsigned int j, unsigned int size)393{394 if (j * 2 < size) {395 j = j * 2;396 397 while (j * 2 + 1 < size)398 j = j * 2 + 1;399 } else400 j >>= ffs(j);401 402 return j;403}404 405/*406 * I have no idea why this code works... and I'm the one who wrote it407 *408 * However, I do know what it does:409 * Given a binary tree constructed in an array (i.e. how you normally implement410 * a heap), it converts a node in the tree - referenced by array index - to the411 * index it would have if you did an inorder traversal.412 *413 * Also tested for every j, size up to size somewhere around 6 million.414 *415 * The binary tree starts at array index 1, not 0416 * extra is a function of size:417 * extra = (size - rounddown_pow_of_two(size - 1)) << 1;418 */419static unsigned int __to_inorder(unsigned int j,420 unsigned int size,421 unsigned int extra)422{423 unsigned int b = fls(j);424 unsigned int shift = fls(size - 1) - b;425 426 j ^= 1U << (b - 1);427 j <<= 1;428 j |= 1;429 j <<= shift;430 431 if (j > extra)432 j -= (j - extra) >> 1;433 434 return j;435}436 437/*438 * Return the cacheline index in bset_tree->data, where j is index439 * from a linear array which stores the auxiliar binary tree440 */441static unsigned int to_inorder(unsigned int j, struct bset_tree *t)442{443 return __to_inorder(j, t->size, t->extra);444}445 446static unsigned int __inorder_to_tree(unsigned int j,447 unsigned int size,448 unsigned int extra)449{450 unsigned int shift;451 452 if (j > extra)453 j += j - extra;454 455 shift = ffs(j);456 457 j >>= shift;458 j |= roundup_pow_of_two(size) >> shift;459 460 return j;461}462 463/*464 * Return an index from a linear array which stores the auxiliar binary465 * tree, j is the cacheline index of t->data.466 */467static unsigned int inorder_to_tree(unsigned int j, struct bset_tree *t)468{469 return __inorder_to_tree(j, t->size, t->extra);470}471 472#if 0473void inorder_test(void)474{475 unsigned long done = 0;476 ktime_t start = ktime_get();477 478 for (unsigned int size = 2;479 size < 65536000;480 size++) {481 unsigned int extra =482 (size - rounddown_pow_of_two(size - 1)) << 1;483 unsigned int i = 1, j = rounddown_pow_of_two(size - 1);484 485 if (!(size % 4096))486 pr_notice("loop %u, %llu per us\n", size,487 done / ktime_us_delta(ktime_get(), start));488 489 while (1) {490 if (__inorder_to_tree(i, size, extra) != j)491 panic("size %10u j %10u i %10u", size, j, i);492 493 if (__to_inorder(j, size, extra) != i)494 panic("size %10u j %10u i %10u", size, j, i);495 496 if (j == rounddown_pow_of_two(size) - 1)497 break;498 499 BUG_ON(inorder_prev(inorder_next(j, size), size) != j);500 501 j = inorder_next(j, size);502 i++;503 }504 505 done += size - 1;506 }507}508#endif509 510/*511 * Cacheline/offset <-> bkey pointer arithmetic:512 *513 * t->tree is a binary search tree in an array; each node corresponds to a key514 * in one cacheline in t->set (BSET_CACHELINE bytes).515 *516 * This means we don't have to store the full index of the key that a node in517 * the binary tree points to; to_inorder() gives us the cacheline, and then518 * bkey_float->m gives us the offset within that cacheline, in units of 8 bytes.519 *520 * cacheline_to_bkey() and friends abstract out all the pointer arithmetic to521 * make this work.522 *523 * To construct the bfloat for an arbitrary key we need to know what the key524 * immediately preceding it is: we have to check if the two keys differ in the525 * bits we're going to store in bkey_float->mantissa. t->prev[j] stores the size526 * of the previous key so we can walk backwards to it from t->tree[j]'s key.527 */528 529static struct bkey *cacheline_to_bkey(struct bset_tree *t,530 unsigned int cacheline,531 unsigned int offset)532{533 return ((void *) t->data) + cacheline * BSET_CACHELINE + offset * 8;534}535 536static unsigned int bkey_to_cacheline(struct bset_tree *t, struct bkey *k)537{538 return ((void *) k - (void *) t->data) / BSET_CACHELINE;539}540 541static unsigned int bkey_to_cacheline_offset(struct bset_tree *t,542 unsigned int cacheline,543 struct bkey *k)544{545 return (u64 *) k - (u64 *) cacheline_to_bkey(t, cacheline, 0);546}547 548static struct bkey *tree_to_bkey(struct bset_tree *t, unsigned int j)549{550 return cacheline_to_bkey(t, to_inorder(j, t), t->tree[j].m);551}552 553static struct bkey *tree_to_prev_bkey(struct bset_tree *t, unsigned int j)554{555 return (void *) (((uint64_t *) tree_to_bkey(t, j)) - t->prev[j]);556}557 558/*559 * For the write set - the one we're currently inserting keys into - we don't560 * maintain a full search tree, we just keep a simple lookup table in t->prev.561 */562static struct bkey *table_to_bkey(struct bset_tree *t, unsigned int cacheline)563{564 return cacheline_to_bkey(t, cacheline, t->prev[cacheline]);565}566 567static inline uint64_t shrd128(uint64_t high, uint64_t low, uint8_t shift)568{569 low >>= shift;570 low |= (high << 1) << (63U - shift);571 return low;572}573 574/*575 * Calculate mantissa value for struct bkey_float.576 * If most significant bit of f->exponent is not set, then577 * - f->exponent >> 6 is 0578 * - p[0] points to bkey->low579 * - p[-1] borrows bits from KEY_INODE() of bkey->high580 * if most isgnificant bits of f->exponent is set, then581 * - f->exponent >> 6 is 1582 * - p[0] points to bits from KEY_INODE() of bkey->high583 * - p[-1] points to other bits from KEY_INODE() of584 * bkey->high too.585 * See make_bfloat() to check when most significant bit of f->exponent586 * is set or not.587 */588static inline unsigned int bfloat_mantissa(const struct bkey *k,589 struct bkey_float *f)590{591 const uint64_t *p = &k->low - (f->exponent >> 6);592 593 return shrd128(p[-1], p[0], f->exponent & 63) & BKEY_MANTISSA_MASK;594}595 596static void make_bfloat(struct bset_tree *t, unsigned int j)597{598 struct bkey_float *f = &t->tree[j];599 struct bkey *m = tree_to_bkey(t, j);600 struct bkey *p = tree_to_prev_bkey(t, j);601 602 struct bkey *l = is_power_of_2(j)603 ? t->data->start604 : tree_to_prev_bkey(t, j >> ffs(j));605 606 struct bkey *r = is_power_of_2(j + 1)607 ? bset_bkey_idx(t->data, t->data->keys - bkey_u64s(&t->end))608 : tree_to_bkey(t, j >> (ffz(j) + 1));609 610 BUG_ON(m < l || m > r);611 BUG_ON(bkey_next(p) != m);612 613 /*614 * If l and r have different KEY_INODE values (different backing615 * device), f->exponent records how many least significant bits616 * are different in KEY_INODE values and sets most significant617 * bits to 1 (by +64).618 * If l and r have same KEY_INODE value, f->exponent records619 * how many different bits in least significant bits of bkey->low.620 * See bfloat_mantiss() how the most significant bit of621 * f->exponent is used to calculate bfloat mantissa value.622 */623 if (KEY_INODE(l) != KEY_INODE(r))624 f->exponent = fls64(KEY_INODE(r) ^ KEY_INODE(l)) + 64;625 else626 f->exponent = fls64(r->low ^ l->low);627 628 f->exponent = max_t(int, f->exponent - BKEY_MANTISSA_BITS, 0);629 630 /*631 * Setting f->exponent = 127 flags this node as failed, and causes the632 * lookup code to fall back to comparing against the original key.633 */634 635 if (bfloat_mantissa(m, f) != bfloat_mantissa(p, f))636 f->mantissa = bfloat_mantissa(m, f) - 1;637 else638 f->exponent = 127;639}640 641static void bset_alloc_tree(struct btree_keys *b, struct bset_tree *t)642{643 if (t != b->set) {644 unsigned int j = roundup(t[-1].size,645 64 / sizeof(struct bkey_float));646 647 t->tree = t[-1].tree + j;648 t->prev = t[-1].prev + j;649 }650 651 while (t < b->set + MAX_BSETS)652 t++->size = 0;653}654 655static void bch_bset_build_unwritten_tree(struct btree_keys *b)656{657 struct bset_tree *t = bset_tree_last(b);658 659 BUG_ON(b->last_set_unwritten);660 b->last_set_unwritten = 1;661 662 bset_alloc_tree(b, t);663 664 if (t->tree != b->set->tree + btree_keys_cachelines(b)) {665 t->prev[0] = bkey_to_cacheline_offset(t, 0, t->data->start);666 t->size = 1;667 }668}669 670void bch_bset_init_next(struct btree_keys *b, struct bset *i, uint64_t magic)671{672 if (i != b->set->data) {673 b->set[++b->nsets].data = i;674 i->seq = b->set->data->seq;675 } else676 get_random_bytes(&i->seq, sizeof(uint64_t));677 678 i->magic = magic;679 i->version = 0;680 i->keys = 0;681 682 bch_bset_build_unwritten_tree(b);683}684 685/*686 * Build auxiliary binary tree 'struct bset_tree *t', this tree is used to687 * accelerate bkey search in a btree node (pointed by bset_tree->data in688 * memory). After search in the auxiliar tree by calling bset_search_tree(),689 * a struct bset_search_iter is returned which indicates range [l, r] from690 * bset_tree->data where the searching bkey might be inside. Then a followed691 * linear comparison does the exact search, see __bch_bset_search() for how692 * the auxiliary tree is used.693 */694void bch_bset_build_written_tree(struct btree_keys *b)695{696 struct bset_tree *t = bset_tree_last(b);697 struct bkey *prev = NULL, *k = t->data->start;698 unsigned int j, cacheline = 1;699 700 b->last_set_unwritten = 0;701 702 bset_alloc_tree(b, t);703 704 t->size = min_t(unsigned int,705 bkey_to_cacheline(t, bset_bkey_last(t->data)),706 b->set->tree + btree_keys_cachelines(b) - t->tree);707 708 if (t->size < 2) {709 t->size = 0;710 return;711 }712 713 t->extra = (t->size - rounddown_pow_of_two(t->size - 1)) << 1;714 715 /* First we figure out where the first key in each cacheline is */716 for (j = inorder_next(0, t->size);717 j;718 j = inorder_next(j, t->size)) {719 while (bkey_to_cacheline(t, k) < cacheline) {720 prev = k;721 k = bkey_next(k);722 }723 724 t->prev[j] = bkey_u64s(prev);725 t->tree[j].m = bkey_to_cacheline_offset(t, cacheline++, k);726 }727 728 while (bkey_next(k) != bset_bkey_last(t->data))729 k = bkey_next(k);730 731 t->end = *k;732 733 /* Then we build the tree */734 for (j = inorder_next(0, t->size);735 j;736 j = inorder_next(j, t->size))737 make_bfloat(t, j);738}739 740/* Insert */741 742void bch_bset_fix_invalidated_key(struct btree_keys *b, struct bkey *k)743{744 struct bset_tree *t;745 unsigned int inorder, j = 1;746 747 for (t = b->set; t <= bset_tree_last(b); t++)748 if (k < bset_bkey_last(t->data))749 goto found_set;750 751 BUG();752found_set:753 if (!t->size || !bset_written(b, t))754 return;755 756 inorder = bkey_to_cacheline(t, k);757 758 if (k == t->data->start)759 goto fix_left;760 761 if (bkey_next(k) == bset_bkey_last(t->data)) {762 t->end = *k;763 goto fix_right;764 }765 766 j = inorder_to_tree(inorder, t);767 768 if (j &&769 j < t->size &&770 k == tree_to_bkey(t, j))771fix_left: do {772 make_bfloat(t, j);773 j = j * 2;774 } while (j < t->size);775 776 j = inorder_to_tree(inorder + 1, t);777 778 if (j &&779 j < t->size &&780 k == tree_to_prev_bkey(t, j))781fix_right: do {782 make_bfloat(t, j);783 j = j * 2 + 1;784 } while (j < t->size);785}786 787static void bch_bset_fix_lookup_table(struct btree_keys *b,788 struct bset_tree *t,789 struct bkey *k)790{791 unsigned int shift = bkey_u64s(k);792 unsigned int j = bkey_to_cacheline(t, k);793 794 /* We're getting called from btree_split() or btree_gc, just bail out */795 if (!t->size)796 return;797 798 /*799 * k is the key we just inserted; we need to find the entry in the800 * lookup table for the first key that is strictly greater than k:801 * it's either k's cacheline or the next one802 */803 while (j < t->size &&804 table_to_bkey(t, j) <= k)805 j++;806 807 /*808 * Adjust all the lookup table entries, and find a new key for any that809 * have gotten too big810 */811 for (; j < t->size; j++) {812 t->prev[j] += shift;813 814 if (t->prev[j] > 7) {815 k = table_to_bkey(t, j - 1);816 817 while (k < cacheline_to_bkey(t, j, 0))818 k = bkey_next(k);819 820 t->prev[j] = bkey_to_cacheline_offset(t, j, k);821 }822 }823 824 if (t->size == b->set->tree + btree_keys_cachelines(b) - t->tree)825 return;826 827 /* Possibly add a new entry to the end of the lookup table */828 829 for (k = table_to_bkey(t, t->size - 1);830 k != bset_bkey_last(t->data);831 k = bkey_next(k))832 if (t->size == bkey_to_cacheline(t, k)) {833 t->prev[t->size] =834 bkey_to_cacheline_offset(t, t->size, k);835 t->size++;836 }837}838 839/*840 * Tries to merge l and r: l should be lower than r841 * Returns true if we were able to merge. If we did merge, l will be the merged842 * key, r will be untouched.843 */844bool bch_bkey_try_merge(struct btree_keys *b, struct bkey *l, struct bkey *r)845{846 if (!b->ops->key_merge)847 return false;848 849 /*850 * Generic header checks851 * Assumes left and right are in order852 * Left and right must be exactly aligned853 */854 if (!bch_bkey_equal_header(l, r) ||855 bkey_cmp(l, &START_KEY(r)))856 return false;857 858 return b->ops->key_merge(b, l, r);859}860 861void bch_bset_insert(struct btree_keys *b, struct bkey *where,862 struct bkey *insert)863{864 struct bset_tree *t = bset_tree_last(b);865 866 BUG_ON(!b->last_set_unwritten);867 BUG_ON(bset_byte_offset(b, t->data) +868 __set_bytes(t->data, t->data->keys + bkey_u64s(insert)) >869 PAGE_SIZE << b->page_order);870 871 memmove((uint64_t *) where + bkey_u64s(insert),872 where,873 (void *) bset_bkey_last(t->data) - (void *) where);874 875 t->data->keys += bkey_u64s(insert);876 bkey_copy(where, insert);877 bch_bset_fix_lookup_table(b, t, where);878}879 880unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k,881 struct bkey *replace_key)882{883 unsigned int status = BTREE_INSERT_STATUS_NO_INSERT;884 struct bset *i = bset_tree_last(b)->data;885 struct bkey *m, *prev = NULL;886 struct btree_iter iter;887 struct bkey preceding_key_on_stack = ZERO_KEY;888 struct bkey *preceding_key_p = &preceding_key_on_stack;889 890 BUG_ON(b->ops->is_extents && !KEY_SIZE(k));891 892 min_heap_init(&iter.heap, NULL, MAX_BSETS);893 894 /*895 * If k has preceding key, preceding_key_p will be set to address896 * of k's preceding key; otherwise preceding_key_p will be set897 * to NULL inside preceding_key().898 */899 if (b->ops->is_extents)900 preceding_key(&START_KEY(k), &preceding_key_p);901 else902 preceding_key(k, &preceding_key_p);903 904 m = bch_btree_iter_init(b, &iter, preceding_key_p);905 906 if (b->ops->insert_fixup(b, k, &iter, replace_key))907 return status;908 909 status = BTREE_INSERT_STATUS_INSERT;910 911 while (m != bset_bkey_last(i) &&912 bkey_cmp(k, b->ops->is_extents ? &START_KEY(m) : m) > 0) {913 prev = m;914 m = bkey_next(m);915 }916 917 /* prev is in the tree, if we merge we're done */918 status = BTREE_INSERT_STATUS_BACK_MERGE;919 if (prev &&920 bch_bkey_try_merge(b, prev, k))921 goto merged;922#if 0923 status = BTREE_INSERT_STATUS_OVERWROTE;924 if (m != bset_bkey_last(i) &&925 KEY_PTRS(m) == KEY_PTRS(k) && !KEY_SIZE(m))926 goto copy;927#endif928 status = BTREE_INSERT_STATUS_FRONT_MERGE;929 if (m != bset_bkey_last(i) &&930 bch_bkey_try_merge(b, k, m))931 goto copy;932 933 bch_bset_insert(b, m, k);934copy: bkey_copy(m, k);935merged:936 return status;937}938 939/* Lookup */940 941struct bset_search_iter {942 struct bkey *l, *r;943};944 945static struct bset_search_iter bset_search_write_set(struct bset_tree *t,946 const struct bkey *search)947{948 unsigned int li = 0, ri = t->size;949 950 while (li + 1 != ri) {951 unsigned int m = (li + ri) >> 1;952 953 if (bkey_cmp(table_to_bkey(t, m), search) > 0)954 ri = m;955 else956 li = m;957 }958 959 return (struct bset_search_iter) {960 table_to_bkey(t, li),961 ri < t->size ? table_to_bkey(t, ri) : bset_bkey_last(t->data)962 };963}964 965static struct bset_search_iter bset_search_tree(struct bset_tree *t,966 const struct bkey *search)967{968 struct bkey *l, *r;969 struct bkey_float *f;970 unsigned int inorder, j, n = 1;971 972 do {973 unsigned int p = n << 4;974 975 if (p < t->size)976 prefetch(&t->tree[p]);977 978 j = n;979 f = &t->tree[j];980 981 if (likely(f->exponent != 127)) {982 if (f->mantissa >= bfloat_mantissa(search, f))983 n = j * 2;984 else985 n = j * 2 + 1;986 } else {987 if (bkey_cmp(tree_to_bkey(t, j), search) > 0)988 n = j * 2;989 else990 n = j * 2 + 1;991 }992 } while (n < t->size);993 994 inorder = to_inorder(j, t);995 996 /*997 * n would have been the node we recursed to - the low bit tells us if998 * we recursed left or recursed right.999 */1000 if (n & 1) {1001 l = cacheline_to_bkey(t, inorder, f->m);1002 1003 if (++inorder != t->size) {1004 f = &t->tree[inorder_next(j, t->size)];1005 r = cacheline_to_bkey(t, inorder, f->m);1006 } else1007 r = bset_bkey_last(t->data);1008 } else {1009 r = cacheline_to_bkey(t, inorder, f->m);1010 1011 if (--inorder) {1012 f = &t->tree[inorder_prev(j, t->size)];1013 l = cacheline_to_bkey(t, inorder, f->m);1014 } else1015 l = t->data->start;1016 }1017 1018 return (struct bset_search_iter) {l, r};1019}1020 1021struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t,1022 const struct bkey *search)1023{1024 struct bset_search_iter i;1025 1026 /*1027 * First, we search for a cacheline, then lastly we do a linear search1028 * within that cacheline.1029 *1030 * To search for the cacheline, there's three different possibilities:1031 * * The set is too small to have a search tree, so we just do a linear1032 * search over the whole set.1033 * * The set is the one we're currently inserting into; keeping a full1034 * auxiliary search tree up to date would be too expensive, so we1035 * use a much simpler lookup table to do a binary search -1036 * bset_search_write_set().1037 * * Or we use the auxiliary search tree we constructed earlier -1038 * bset_search_tree()1039 */1040 1041 if (unlikely(!t->size)) {1042 i.l = t->data->start;1043 i.r = bset_bkey_last(t->data);1044 } else if (bset_written(b, t)) {1045 /*1046 * Each node in the auxiliary search tree covers a certain range1047 * of bits, and keys above and below the set it covers might1048 * differ outside those bits - so we have to special case the1049 * start and end - handle that here:1050 */1051 1052 if (unlikely(bkey_cmp(search, &t->end) >= 0))1053 return bset_bkey_last(t->data);1054 1055 if (unlikely(bkey_cmp(search, t->data->start) < 0))1056 return t->data->start;1057 1058 i = bset_search_tree(t, search);1059 } else {1060 BUG_ON(!b->nsets &&1061 t->size < bkey_to_cacheline(t, bset_bkey_last(t->data)));1062 1063 i = bset_search_write_set(t, search);1064 }1065 1066 if (btree_keys_expensive_checks(b)) {1067 BUG_ON(bset_written(b, t) &&1068 i.l != t->data->start &&1069 bkey_cmp(tree_to_prev_bkey(t,1070 inorder_to_tree(bkey_to_cacheline(t, i.l), t)),1071 search) > 0);1072 1073 BUG_ON(i.r != bset_bkey_last(t->data) &&1074 bkey_cmp(i.r, search) <= 0);1075 }1076 1077 while (likely(i.l != i.r) &&1078 bkey_cmp(i.l, search) <= 0)1079 i.l = bkey_next(i.l);1080 1081 return i.l;1082}1083 1084/* Btree iterator */1085 1086typedef bool (new_btree_iter_cmp_fn)(const void *, const void *, void *);1087 1088static inline bool new_btree_iter_cmp(const void *l, const void *r, void __always_unused *args)1089{1090 const struct btree_iter_set *_l = l;1091 const struct btree_iter_set *_r = r;1092 1093 return bkey_cmp(_l->k, _r->k) <= 0;1094}1095 1096static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args)1097{1098 struct btree_iter_set *_iter1 = iter1;1099 struct btree_iter_set *_iter2 = iter2;1100 1101 swap(*_iter1, *_iter2);1102}1103 1104static inline bool btree_iter_end(struct btree_iter *iter)1105{1106 return !iter->heap.nr;1107}1108 1109void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k,1110 struct bkey *end)1111{1112 const struct min_heap_callbacks callbacks = {1113 .less = new_btree_iter_cmp,1114 .swp = new_btree_iter_swap,1115 };1116 1117 if (k != end)1118 BUG_ON(!min_heap_push(&iter->heap,1119 &((struct btree_iter_set) { k, end }),1120 &callbacks,1121 NULL));1122}1123 1124static struct bkey *__bch_btree_iter_init(struct btree_keys *b,1125 struct btree_iter *iter,1126 struct bkey *search,1127 struct bset_tree *start)1128{1129 struct bkey *ret = NULL;1130 1131 iter->heap.size = ARRAY_SIZE(iter->heap.preallocated);1132 iter->heap.nr = 0;1133 1134#ifdef CONFIG_BCACHE_DEBUG1135 iter->b = b;1136#endif1137 1138 for (; start <= bset_tree_last(b); start++) {1139 ret = bch_bset_search(b, start, search);1140 bch_btree_iter_push(iter, ret, bset_bkey_last(start->data));1141 }1142 1143 return ret;1144}1145 1146struct bkey *bch_btree_iter_init(struct btree_keys *b,1147 struct btree_iter *iter,1148 struct bkey *search)1149{1150 return __bch_btree_iter_init(b, iter, search, b->set);1151}1152 1153static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter,1154 new_btree_iter_cmp_fn *cmp)1155{1156 struct btree_iter_set b __maybe_unused;1157 struct bkey *ret = NULL;1158 const struct min_heap_callbacks callbacks = {1159 .less = cmp,1160 .swp = new_btree_iter_swap,1161 };1162 1163 if (!btree_iter_end(iter)) {1164 bch_btree_iter_next_check(iter);1165 1166 ret = iter->heap.data->k;1167 iter->heap.data->k = bkey_next(iter->heap.data->k);1168 1169 if (iter->heap.data->k > iter->heap.data->end) {1170 WARN_ONCE(1, "bset was corrupt!\n");1171 iter->heap.data->k = iter->heap.data->end;1172 }1173 1174 if (iter->heap.data->k == iter->heap.data->end) {1175 if (iter->heap.nr) {1176 b = min_heap_peek(&iter->heap)[0];1177 min_heap_pop(&iter->heap, &callbacks, NULL);1178 }1179 }1180 else1181 min_heap_sift_down(&iter->heap, 0, &callbacks, NULL);1182 }1183 1184 return ret;1185}1186 1187struct bkey *bch_btree_iter_next(struct btree_iter *iter)1188{1189 return __bch_btree_iter_next(iter, new_btree_iter_cmp);1190 1191}1192 1193struct bkey *bch_btree_iter_next_filter(struct btree_iter *iter,1194 struct btree_keys *b, ptr_filter_fn fn)1195{1196 struct bkey *ret;1197 1198 do {1199 ret = bch_btree_iter_next(iter);1200 } while (ret && fn(b, ret));1201 1202 return ret;1203}1204 1205/* Mergesort */1206 1207void bch_bset_sort_state_free(struct bset_sort_state *state)1208{1209 mempool_exit(&state->pool);1210}1211 1212int bch_bset_sort_state_init(struct bset_sort_state *state,1213 unsigned int page_order)1214{1215 spin_lock_init(&state->time.lock);1216 1217 state->page_order = page_order;1218 state->crit_factor = int_sqrt(1 << page_order);1219 1220 return mempool_init_page_pool(&state->pool, 1, page_order);1221}1222 1223static void btree_mergesort(struct btree_keys *b, struct bset *out,1224 struct btree_iter *iter,1225 bool fixup, bool remove_stale)1226{1227 struct bkey *k, *last = NULL;1228 BKEY_PADDED(k) tmp;1229 bool (*bad)(struct btree_keys *, const struct bkey *) = remove_stale1230 ? bch_ptr_bad1231 : bch_ptr_invalid;1232 const struct min_heap_callbacks callbacks = {1233 .less = b->ops->sort_cmp,1234 .swp = new_btree_iter_swap,1235 };1236 1237 /* Heapify the iterator, using our comparison function */1238 min_heapify_all(&iter->heap, &callbacks, NULL);1239 1240 while (!btree_iter_end(iter)) {1241 if (b->ops->sort_fixup && fixup)1242 k = b->ops->sort_fixup(iter, &tmp.k);1243 else1244 k = NULL;1245 1246 if (!k)1247 k = __bch_btree_iter_next(iter, b->ops->sort_cmp);1248 1249 if (bad(b, k))1250 continue;1251 1252 if (!last) {1253 last = out->start;1254 bkey_copy(last, k);1255 } else if (!bch_bkey_try_merge(b, last, k)) {1256 last = bkey_next(last);1257 bkey_copy(last, k);1258 }1259 }1260 1261 out->keys = last ? (uint64_t *) bkey_next(last) - out->d : 0;1262 1263 pr_debug("sorted %i keys\n", out->keys);1264}1265 1266static void __btree_sort(struct btree_keys *b, struct btree_iter *iter,1267 unsigned int start, unsigned int order, bool fixup,1268 struct bset_sort_state *state)1269{1270 uint64_t start_time;1271 bool used_mempool = false;1272 struct bset *out = (void *) __get_free_pages(__GFP_NOWARN|GFP_NOWAIT,1273 order);1274 if (!out) {1275 struct page *outp;1276 1277 BUG_ON(order > state->page_order);1278 1279 outp = mempool_alloc(&state->pool, GFP_NOIO);1280 out = page_address(outp);1281 used_mempool = true;1282 order = state->page_order;1283 }1284 1285 start_time = local_clock();1286 1287 btree_mergesort(b, out, iter, fixup, false);1288 b->nsets = start;1289 1290 if (!start && order == b->page_order) {1291 /*1292 * Our temporary buffer is the same size as the btree node's1293 * buffer, we can just swap buffers instead of doing a big1294 * memcpy()1295 *1296 * Don't worry event 'out' is allocated from mempool, it can1297 * still be swapped here. Because state->pool is a page mempool1298 * created by mempool_init_page_pool(), which allocates1299 * pages by alloc_pages() indeed.1300 */1301 1302 out->magic = b->set->data->magic;1303 out->seq = b->set->data->seq;1304 out->version = b->set->data->version;1305 swap(out, b->set->data);1306 } else {1307 b->set[start].data->keys = out->keys;1308 memcpy(b->set[start].data->start, out->start,1309 (void *) bset_bkey_last(out) - (void *) out->start);1310 }1311 1312 if (used_mempool)1313 mempool_free(virt_to_page(out), &state->pool);1314 else1315 free_pages((unsigned long) out, order);1316 1317 bch_bset_build_written_tree(b);1318 1319 if (!start)1320 bch_time_stats_update(&state->time, start_time);1321}1322 1323void bch_btree_sort_partial(struct btree_keys *b, unsigned int start,1324 struct bset_sort_state *state)1325{1326 size_t order = b->page_order, keys = 0;1327 struct btree_iter iter;1328 int oldsize = bch_count_data(b);1329 1330 min_heap_init(&iter.heap, NULL, MAX_BSETS);1331 __bch_btree_iter_init(b, &iter, NULL, &b->set[start]);1332 1333 if (start) {1334 unsigned int i;1335 1336 for (i = start; i <= b->nsets; i++)1337 keys += b->set[i].data->keys;1338 1339 order = get_order(__set_bytes(b->set->data, keys));1340 }1341 1342 __btree_sort(b, &iter, start, order, false, state);1343 1344 EBUG_ON(oldsize >= 0 && bch_count_data(b) != oldsize);1345}1346 1347void bch_btree_sort_and_fix_extents(struct btree_keys *b,1348 struct btree_iter *iter,1349 struct bset_sort_state *state)1350{1351 __btree_sort(b, iter, 0, b->page_order, true, state);1352}1353 1354void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new,1355 struct bset_sort_state *state)1356{1357 uint64_t start_time = local_clock();1358 struct btree_iter iter;1359 1360 min_heap_init(&iter.heap, NULL, MAX_BSETS);1361 1362 bch_btree_iter_init(b, &iter, NULL);1363 1364 btree_mergesort(b, new->set->data, &iter, false, true);1365 1366 bch_time_stats_update(&state->time, start_time);1367 1368 new->set->size = 0; // XXX: why?1369}1370 1371#define SORT_CRIT (4096 / sizeof(uint64_t))1372 1373void bch_btree_sort_lazy(struct btree_keys *b, struct bset_sort_state *state)1374{1375 unsigned int crit = SORT_CRIT;1376 int i;1377 1378 /* Don't sort if nothing to do */1379 if (!b->nsets)1380 goto out;1381 1382 for (i = b->nsets - 1; i >= 0; --i) {1383 crit *= state->crit_factor;1384 1385 if (b->set[i].data->keys < crit) {1386 bch_btree_sort_partial(b, i, state);1387 return;1388 }1389 }1390 1391 /* Sort if we'd overflow */1392 if (b->nsets + 1 == MAX_BSETS) {1393 bch_btree_sort(b, state);1394 return;1395 }1396 1397out:1398 bch_bset_build_written_tree(b);1399}1400 1401void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *stats)1402{1403 unsigned int i;1404 1405 for (i = 0; i <= b->nsets; i++) {1406 struct bset_tree *t = &b->set[i];1407 size_t bytes = t->data->keys * sizeof(uint64_t);1408 size_t j;1409 1410 if (bset_written(b, t)) {1411 stats->sets_written++;1412 stats->bytes_written += bytes;1413 1414 stats->floats += t->size - 1;1415 1416 for (j = 1; j < t->size; j++)1417 if (t->tree[j].exponent == 127)1418 stats->failed++;1419 } else {1420 stats->sets_unwritten++;1421 stats->bytes_unwritten += bytes;1422 }1423 }1424}1425