1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Code for working with individual keys, and sorted sets of keys with in a 4 * btree node 5 * 6 * Copyright 2012 Google, Inc. 7 */ 8 9 #define pr_fmt(fmt) "bcache: %s() " fmt "\n", __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_DEBUG 20 21 void 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 else 34 pr_err("%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 43 void 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 54 int __bch_count_data(struct btree_keys *b) 55 { 56 unsigned int ret = 0; 57 struct btree_iter iter; 58 struct bkey *k; 59 60 if (b->ops->is_extents) 61 for_each_key(b, k, &iter) 62 ret += KEY_SIZE(k); 63 return ret; 64 } 65 66 void __bch_check_keys(struct btree_keys *b, const char *fmt, ...) 67 { 68 va_list args; 69 struct bkey *k, *p = NULL; 70 struct btree_iter iter; 71 const char *err; 72 73 for_each_key(b, k, &iter) { 74 if (b->ops->is_extents) { 75 err = "Keys out of order"; 76 if (p && bkey_cmp(&START_KEY(p), &START_KEY(k)) > 0) 77 goto bug; 78 79 if (bch_ptr_invalid(b, k)) 80 continue; 81 82 err = "Overlapping keys"; 83 if (p && bkey_cmp(p, &START_KEY(k)) > 0) 84 goto bug; 85 } else { 86 if (bch_ptr_bad(b, k)) 87 continue; 88 89 err = "Duplicate keys"; 90 if (p && !bkey_cmp(p, k)) 91 goto bug; 92 } 93 p = k; 94 } 95 #if 0 96 err = "Key larger than btree node key"; 97 if (p && bkey_cmp(p, &b->key) > 0) 98 goto bug; 99 #endif 100 return; 101 bug: 102 bch_dump_bucket(b); 103 104 va_start(args, fmt); 105 vprintk(fmt, args); 106 va_end(args); 107 108 panic("bch_check_keys error: %s:\n", err); 109 } 110 111 static void bch_btree_iter_next_check(struct btree_iter *iter) 112 { 113 struct bkey *k = iter->data->k, *next = bkey_next(k); 114 115 if (next < iter->data->end && 116 bkey_cmp(k, iter->b->ops->is_extents ? 117 &START_KEY(next) : next) > 0) { 118 bch_dump_bucket(iter->b); 119 panic("Key skipped backwards\n"); 120 } 121 } 122 123 #else 124 125 static inline void bch_btree_iter_next_check(struct btree_iter *iter) {} 126 127 #endif 128 129 /* Keylists */ 130 131 int __bch_keylist_realloc(struct keylist *l, unsigned int u64s) 132 { 133 size_t oldsize = bch_keylist_nkeys(l); 134 size_t newsize = oldsize + u64s; 135 uint64_t *old_keys = l->keys_p == l->inline_keys ? NULL : l->keys_p; 136 uint64_t *new_keys; 137 138 newsize = roundup_pow_of_two(newsize); 139 140 if (newsize <= KEYLIST_INLINE || 141 roundup_pow_of_two(oldsize) == newsize) 142 return 0; 143 144 new_keys = krealloc(old_keys, sizeof(uint64_t) * newsize, GFP_NOIO); 145 146 if (!new_keys) 147 return -ENOMEM; 148 149 if (!old_keys) 150 memcpy(new_keys, l->inline_keys, sizeof(uint64_t) * oldsize); 151 152 l->keys_p = new_keys; 153 l->top_p = new_keys + oldsize; 154 155 return 0; 156 } 157 158 struct bkey *bch_keylist_pop(struct keylist *l) 159 { 160 struct bkey *k = l->keys; 161 162 if (k == l->top) 163 return NULL; 164 165 while (bkey_next(k) != l->top) 166 k = bkey_next(k); 167 168 return l->top = k; 169 } 170 171 void bch_keylist_pop_front(struct keylist *l) 172 { 173 l->top_p -= bkey_u64s(l->keys); 174 175 memmove(l->keys, 176 bkey_next(l->keys), 177 bch_keylist_bytes(l)); 178 } 179 180 /* Key/pointer manipulation */ 181 182 void bch_bkey_copy_single_ptr(struct bkey *dest, const struct bkey *src, 183 unsigned int i) 184 { 185 BUG_ON(i > KEY_PTRS(src)); 186 187 /* Only copy the header, key, and one pointer. */ 188 memcpy(dest, src, 2 * sizeof(uint64_t)); 189 dest->ptr[0] = src->ptr[i]; 190 SET_KEY_PTRS(dest, 1); 191 /* We didn't copy the checksum so clear that bit. */ 192 SET_KEY_CSUM(dest, 0); 193 } 194 195 bool __bch_cut_front(const struct bkey *where, struct bkey *k) 196 { 197 unsigned int i, len = 0; 198 199 if (bkey_cmp(where, &START_KEY(k)) <= 0) 200 return false; 201 202 if (bkey_cmp(where, k) < 0) 203 len = KEY_OFFSET(k) - KEY_OFFSET(where); 204 else 205 bkey_copy_key(k, where); 206 207 for (i = 0; i < KEY_PTRS(k); i++) 208 SET_PTR_OFFSET(k, i, PTR_OFFSET(k, i) + KEY_SIZE(k) - len); 209 210 BUG_ON(len > KEY_SIZE(k)); 211 SET_KEY_SIZE(k, len); 212 return true; 213 } 214 215 bool __bch_cut_back(const struct bkey *where, struct bkey *k) 216 { 217 unsigned int len = 0; 218 219 if (bkey_cmp(where, k) >= 0) 220 return false; 221 222 BUG_ON(KEY_INODE(where) != KEY_INODE(k)); 223 224 if (bkey_cmp(where, &START_KEY(k)) > 0) 225 len = KEY_OFFSET(where) - KEY_START(k); 226 227 bkey_copy_key(k, where); 228 229 BUG_ON(len > KEY_SIZE(k)); 230 SET_KEY_SIZE(k, len); 231 return true; 232 } 233 234 /* Auxiliary search trees */ 235 236 /* 32 bits total: */ 237 #define BKEY_MID_BITS 3 238 #define BKEY_EXPONENT_BITS 7 239 #define BKEY_MANTISSA_BITS (32 - BKEY_MID_BITS - BKEY_EXPONENT_BITS) 240 #define BKEY_MANTISSA_MASK ((1 << BKEY_MANTISSA_BITS) - 1) 241 242 struct bkey_float { 243 unsigned int exponent:BKEY_EXPONENT_BITS; 244 unsigned int m:BKEY_MID_BITS; 245 unsigned int mantissa:BKEY_MANTISSA_BITS; 246 } __packed; 247 248 /* 249 * BSET_CACHELINE was originally intended to match the hardware cacheline size - 250 * it used to be 64, but I realized the lookup code would touch slightly less 251 * memory if it was 128. 252 * 253 * It definites the number of bytes (in struct bset) per struct bkey_float in 254 * the auxiliar search tree - when we're done searching the bset_float tree we 255 * have this many bytes left that we do a linear search over. 256 * 257 * Since (after level 5) every level of the bset_tree is on a new cacheline, 258 * we're touching one fewer cacheline in the bset tree in exchange for one more 259 * cacheline in the linear search - but the linear search might stop before it 260 * gets to the second cacheline. 261 */ 262 263 #define BSET_CACHELINE 128 264 265 /* Space required for the btree node keys */ 266 static inline size_t btree_keys_bytes(struct btree_keys *b) 267 { 268 return PAGE_SIZE << b->page_order; 269 } 270 271 static inline size_t btree_keys_cachelines(struct btree_keys *b) 272 { 273 return btree_keys_bytes(b) / BSET_CACHELINE; 274 } 275 276 /* Space required for the auxiliary search trees */ 277 static inline size_t bset_tree_bytes(struct btree_keys *b) 278 { 279 return btree_keys_cachelines(b) * sizeof(struct bkey_float); 280 } 281 282 /* Space required for the prev pointers */ 283 static inline size_t bset_prev_bytes(struct btree_keys *b) 284 { 285 return btree_keys_cachelines(b) * sizeof(uint8_t); 286 } 287 288 /* Memory allocation */ 289 290 void bch_btree_keys_free(struct btree_keys *b) 291 { 292 struct bset_tree *t = b->set; 293 294 if (bset_prev_bytes(b) < PAGE_SIZE) 295 kfree(t->prev); 296 else 297 free_pages((unsigned long) t->prev, 298 get_order(bset_prev_bytes(b))); 299 300 if (bset_tree_bytes(b) < PAGE_SIZE) 301 kfree(t->tree); 302 else 303 free_pages((unsigned long) t->tree, 304 get_order(bset_tree_bytes(b))); 305 306 free_pages((unsigned long) t->data, b->page_order); 307 308 t->prev = NULL; 309 t->tree = NULL; 310 t->data = NULL; 311 } 312 EXPORT_SYMBOL(bch_btree_keys_free); 313 314 int bch_btree_keys_alloc(struct btree_keys *b, 315 unsigned int page_order, 316 gfp_t gfp) 317 { 318 struct bset_tree *t = b->set; 319 320 BUG_ON(t->data); 321 322 b->page_order = page_order; 323 324 t->data = (void *) __get_free_pages(gfp, b->page_order); 325 if (!t->data) 326 goto err; 327 328 t->tree = bset_tree_bytes(b) < PAGE_SIZE 329 ? kmalloc(bset_tree_bytes(b), gfp) 330 : (void *) __get_free_pages(gfp, get_order(bset_tree_bytes(b))); 331 if (!t->tree) 332 goto err; 333 334 t->prev = bset_prev_bytes(b) < PAGE_SIZE 335 ? kmalloc(bset_prev_bytes(b), gfp) 336 : (void *) __get_free_pages(gfp, get_order(bset_prev_bytes(b))); 337 if (!t->prev) 338 goto err; 339 340 return 0; 341 err: 342 bch_btree_keys_free(b); 343 return -ENOMEM; 344 } 345 EXPORT_SYMBOL(bch_btree_keys_alloc); 346 347 void bch_btree_keys_init(struct btree_keys *b, const struct btree_keys_ops *ops, 348 bool *expensive_debug_checks) 349 { 350 unsigned int i; 351 352 b->ops = ops; 353 b->expensive_debug_checks = expensive_debug_checks; 354 b->nsets = 0; 355 b->last_set_unwritten = 0; 356 357 /* XXX: shouldn't be needed */ 358 for (i = 0; i < MAX_BSETS; i++) 359 b->set[i].size = 0; 360 /* 361 * Second loop starts at 1 because b->keys[0]->data is the memory we 362 * allocated 363 */ 364 for (i = 1; i < MAX_BSETS; i++) 365 b->set[i].data = NULL; 366 } 367 EXPORT_SYMBOL(bch_btree_keys_init); 368 369 /* Binary tree stuff for auxiliary search trees */ 370 371 /* 372 * return array index next to j when does in-order traverse 373 * of a binary tree which is stored in a linear array 374 */ 375 static 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 } else 383 j >>= ffz(j) + 1; 384 385 return j; 386 } 387 388 /* 389 * return array index previous to j when does in-order traverse 390 * of a binary tree which is stored in a linear array 391 */ 392 static 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 } else 400 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 it 407 * 408 * However, I do know what it does: 409 * Given a binary tree constructed in an array (i.e. how you normally implement 410 * a heap), it converts a node in the tree - referenced by array index - to the 411 * 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 0 416 * extra is a function of size: 417 * extra = (size - rounddown_pow_of_two(size - 1)) << 1; 418 */ 419 static 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 index 439 * from a linear array which stores the auxiliar binary tree 440 */ 441 static unsigned int to_inorder(unsigned int j, struct bset_tree *t) 442 { 443 return __to_inorder(j, t->size, t->extra); 444 } 445 446 static 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 binary 465 * tree, j is the cacheline index of t->data. 466 */ 467 static 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 0 473 void 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 #endif 509 510 /* 511 * Cacheline/offset <-> bkey pointer arithmetic: 512 * 513 * t->tree is a binary search tree in an array; each node corresponds to a key 514 * 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 in 517 * the binary tree points to; to_inorder() gives us the cacheline, and then 518 * 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 to 521 * make this work. 522 * 523 * To construct the bfloat for an arbitrary key we need to know what the key 524 * immediately preceding it is: we have to check if the two keys differ in the 525 * bits we're going to store in bkey_float->mantissa. t->prev[j] stores the size 526 * of the previous key so we can walk backwards to it from t->tree[j]'s key. 527 */ 528 529 static 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 536 static unsigned int bkey_to_cacheline(struct bset_tree *t, struct bkey *k) 537 { 538 return ((void *) k - (void *) t->data) / BSET_CACHELINE; 539 } 540 541 static 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 548 static 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 553 static 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't 560 * maintain a full search tree, we just keep a simple lookup table in t->prev. 561 */ 562 static 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 567 static 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, then 577 * - f->exponent >> 6 is 0 578 * - p[0] points to bkey->low 579 * - p[-1] borrows bits from KEY_INODE() of bkey->high 580 * if most isgnificant bits of f->exponent is set, then 581 * - f->exponent >> 6 is 1 582 * - p[0] points to bits from KEY_INODE() of bkey->high 583 * - p[-1] points to other bits from KEY_INODE() of 584 * bkey->high too. 585 * See make_bfloat() to check when most significant bit of f->exponent 586 * is set or not. 587 */ 588 static 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 596 static 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->start 604 : 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 backing 615 * device), f->exponent records how many least significant bits 616 * are different in KEY_INODE values and sets most significant 617 * bits to 1 (by +64). 618 * If l and r have same KEY_INODE value, f->exponent records 619 * how many different bits in least significant bits of bkey->low. 620 * See bfloat_mantiss() how the most significant bit of 621 * 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 else 626 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 the 632 * 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 else 638 f->exponent = 127; 639 } 640 641 static 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 655 static 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 670 void 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 } else 676 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 EXPORT_SYMBOL(bch_bset_init_next); 685 686 /* 687 * Build auxiliary binary tree 'struct bset_tree *t', this tree is used to 688 * accelerate bkey search in a btree node (pointed by bset_tree->data in 689 * memory). After search in the auxiliar tree by calling bset_search_tree(), 690 * a struct bset_search_iter is returned which indicates range [l, r] from 691 * bset_tree->data where the searching bkey might be inside. Then a followed 692 * linear comparison does the exact search, see __bch_bset_search() for how 693 * the auxiliary tree is used. 694 */ 695 void bch_bset_build_written_tree(struct btree_keys *b) 696 { 697 struct bset_tree *t = bset_tree_last(b); 698 struct bkey *prev = NULL, *k = t->data->start; 699 unsigned int j, cacheline = 1; 700 701 b->last_set_unwritten = 0; 702 703 bset_alloc_tree(b, t); 704 705 t->size = min_t(unsigned int, 706 bkey_to_cacheline(t, bset_bkey_last(t->data)), 707 b->set->tree + btree_keys_cachelines(b) - t->tree); 708 709 if (t->size < 2) { 710 t->size = 0; 711 return; 712 } 713 714 t->extra = (t->size - rounddown_pow_of_two(t->size - 1)) << 1; 715 716 /* First we figure out where the first key in each cacheline is */ 717 for (j = inorder_next(0, t->size); 718 j; 719 j = inorder_next(j, t->size)) { 720 while (bkey_to_cacheline(t, k) < cacheline) 721 prev = k, k = bkey_next(k); 722 723 t->prev[j] = bkey_u64s(prev); 724 t->tree[j].m = bkey_to_cacheline_offset(t, cacheline++, k); 725 } 726 727 while (bkey_next(k) != bset_bkey_last(t->data)) 728 k = bkey_next(k); 729 730 t->end = *k; 731 732 /* Then we build the tree */ 733 for (j = inorder_next(0, t->size); 734 j; 735 j = inorder_next(j, t->size)) 736 make_bfloat(t, j); 737 } 738 EXPORT_SYMBOL(bch_bset_build_written_tree); 739 740 /* Insert */ 741 742 void 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(); 752 found_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)) 771 fix_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)) 781 fix_right: do { 782 make_bfloat(t, j); 783 j = j * 2 + 1; 784 } while (j < t->size); 785 } 786 EXPORT_SYMBOL(bch_bset_fix_invalidated_key); 787 788 static void bch_bset_fix_lookup_table(struct btree_keys *b, 789 struct bset_tree *t, 790 struct bkey *k) 791 { 792 unsigned int shift = bkey_u64s(k); 793 unsigned int j = bkey_to_cacheline(t, k); 794 795 /* We're getting called from btree_split() or btree_gc, just bail out */ 796 if (!t->size) 797 return; 798 799 /* 800 * k is the key we just inserted; we need to find the entry in the 801 * lookup table for the first key that is strictly greater than k: 802 * it's either k's cacheline or the next one 803 */ 804 while (j < t->size && 805 table_to_bkey(t, j) <= k) 806 j++; 807 808 /* 809 * Adjust all the lookup table entries, and find a new key for any that 810 * have gotten too big 811 */ 812 for (; j < t->size; j++) { 813 t->prev[j] += shift; 814 815 if (t->prev[j] > 7) { 816 k = table_to_bkey(t, j - 1); 817 818 while (k < cacheline_to_bkey(t, j, 0)) 819 k = bkey_next(k); 820 821 t->prev[j] = bkey_to_cacheline_offset(t, j, k); 822 } 823 } 824 825 if (t->size == b->set->tree + btree_keys_cachelines(b) - t->tree) 826 return; 827 828 /* Possibly add a new entry to the end of the lookup table */ 829 830 for (k = table_to_bkey(t, t->size - 1); 831 k != bset_bkey_last(t->data); 832 k = bkey_next(k)) 833 if (t->size == bkey_to_cacheline(t, k)) { 834 t->prev[t->size] = 835 bkey_to_cacheline_offset(t, t->size, k); 836 t->size++; 837 } 838 } 839 840 /* 841 * Tries to merge l and r: l should be lower than r 842 * Returns true if we were able to merge. If we did merge, l will be the merged 843 * key, r will be untouched. 844 */ 845 bool bch_bkey_try_merge(struct btree_keys *b, struct bkey *l, struct bkey *r) 846 { 847 if (!b->ops->key_merge) 848 return false; 849 850 /* 851 * Generic header checks 852 * Assumes left and right are in order 853 * Left and right must be exactly aligned 854 */ 855 if (!bch_bkey_equal_header(l, r) || 856 bkey_cmp(l, &START_KEY(r))) 857 return false; 858 859 return b->ops->key_merge(b, l, r); 860 } 861 EXPORT_SYMBOL(bch_bkey_try_merge); 862 863 void bch_bset_insert(struct btree_keys *b, struct bkey *where, 864 struct bkey *insert) 865 { 866 struct bset_tree *t = bset_tree_last(b); 867 868 BUG_ON(!b->last_set_unwritten); 869 BUG_ON(bset_byte_offset(b, t->data) + 870 __set_bytes(t->data, t->data->keys + bkey_u64s(insert)) > 871 PAGE_SIZE << b->page_order); 872 873 memmove((uint64_t *) where + bkey_u64s(insert), 874 where, 875 (void *) bset_bkey_last(t->data) - (void *) where); 876 877 t->data->keys += bkey_u64s(insert); 878 bkey_copy(where, insert); 879 bch_bset_fix_lookup_table(b, t, where); 880 } 881 EXPORT_SYMBOL(bch_bset_insert); 882 883 unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k, 884 struct bkey *replace_key) 885 { 886 unsigned int status = BTREE_INSERT_STATUS_NO_INSERT; 887 struct bset *i = bset_tree_last(b)->data; 888 struct bkey *m, *prev = NULL; 889 struct btree_iter iter; 890 struct bkey preceding_key_on_stack = ZERO_KEY; 891 struct bkey *preceding_key_p = &preceding_key_on_stack; 892 893 BUG_ON(b->ops->is_extents && !KEY_SIZE(k)); 894 895 /* 896 * If k has preceding key, preceding_key_p will be set to address 897 * of k's preceding key; otherwise preceding_key_p will be set 898 * to NULL inside preceding_key(). 899 */ 900 if (b->ops->is_extents) 901 preceding_key(&START_KEY(k), &preceding_key_p); 902 else 903 preceding_key(k, &preceding_key_p); 904 905 m = bch_btree_iter_init(b, &iter, preceding_key_p); 906 907 if (b->ops->insert_fixup(b, k, &iter, replace_key)) 908 return status; 909 910 status = BTREE_INSERT_STATUS_INSERT; 911 912 while (m != bset_bkey_last(i) && 913 bkey_cmp(k, b->ops->is_extents ? &START_KEY(m) : m) > 0) 914 prev = m, m = bkey_next(m); 915 916 /* prev is in the tree, if we merge we're done */ 917 status = BTREE_INSERT_STATUS_BACK_MERGE; 918 if (prev && 919 bch_bkey_try_merge(b, prev, k)) 920 goto merged; 921 #if 0 922 status = BTREE_INSERT_STATUS_OVERWROTE; 923 if (m != bset_bkey_last(i) && 924 KEY_PTRS(m) == KEY_PTRS(k) && !KEY_SIZE(m)) 925 goto copy; 926 #endif 927 status = BTREE_INSERT_STATUS_FRONT_MERGE; 928 if (m != bset_bkey_last(i) && 929 bch_bkey_try_merge(b, k, m)) 930 goto copy; 931 932 bch_bset_insert(b, m, k); 933 copy: bkey_copy(m, k); 934 merged: 935 return status; 936 } 937 EXPORT_SYMBOL(bch_btree_insert_key); 938 939 /* Lookup */ 940 941 struct bset_search_iter { 942 struct bkey *l, *r; 943 }; 944 945 static 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 else 956 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 965 static 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 /* 974 * A bit trick here. 975 * If p < t->size, (int)(p - t->size) is a minus value and 976 * the most significant bit is set, right shifting 31 bits 977 * gets 1. If p >= t->size, the most significant bit is 978 * not set, right shifting 31 bits gets 0. 979 * So the following 2 lines equals to 980 * if (p >= t->size) 981 * p = 0; 982 * but a branch instruction is avoided. 983 */ 984 unsigned int p = n << 4; 985 986 p &= ((int) (p - t->size)) >> 31; 987 988 prefetch(&t->tree[p]); 989 990 j = n; 991 f = &t->tree[j]; 992 993 /* 994 * Similar bit trick, use subtract operation to avoid a branch 995 * instruction. 996 * 997 * n = (f->mantissa > bfloat_mantissa()) 998 * ? j * 2 999 * : j * 2 + 1; 1000 * 1001 * We need to subtract 1 from f->mantissa for the sign bit trick 1002 * to work - that's done in make_bfloat() 1003 */ 1004 if (likely(f->exponent != 127)) 1005 n = j * 2 + (((unsigned int) 1006 (f->mantissa - 1007 bfloat_mantissa(search, f))) >> 31); 1008 else 1009 n = (bkey_cmp(tree_to_bkey(t, j), search) > 0) 1010 ? j * 2 1011 : j * 2 + 1; 1012 } while (n < t->size); 1013 1014 inorder = to_inorder(j, t); 1015 1016 /* 1017 * n would have been the node we recursed to - the low bit tells us if 1018 * we recursed left or recursed right. 1019 */ 1020 if (n & 1) { 1021 l = cacheline_to_bkey(t, inorder, f->m); 1022 1023 if (++inorder != t->size) { 1024 f = &t->tree[inorder_next(j, t->size)]; 1025 r = cacheline_to_bkey(t, inorder, f->m); 1026 } else 1027 r = bset_bkey_last(t->data); 1028 } else { 1029 r = cacheline_to_bkey(t, inorder, f->m); 1030 1031 if (--inorder) { 1032 f = &t->tree[inorder_prev(j, t->size)]; 1033 l = cacheline_to_bkey(t, inorder, f->m); 1034 } else 1035 l = t->data->start; 1036 } 1037 1038 return (struct bset_search_iter) {l, r}; 1039 } 1040 1041 struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, 1042 const struct bkey *search) 1043 { 1044 struct bset_search_iter i; 1045 1046 /* 1047 * First, we search for a cacheline, then lastly we do a linear search 1048 * within that cacheline. 1049 * 1050 * To search for the cacheline, there's three different possibilities: 1051 * * The set is too small to have a search tree, so we just do a linear 1052 * search over the whole set. 1053 * * The set is the one we're currently inserting into; keeping a full 1054 * auxiliary search tree up to date would be too expensive, so we 1055 * use a much simpler lookup table to do a binary search - 1056 * bset_search_write_set(). 1057 * * Or we use the auxiliary search tree we constructed earlier - 1058 * bset_search_tree() 1059 */ 1060 1061 if (unlikely(!t->size)) { 1062 i.l = t->data->start; 1063 i.r = bset_bkey_last(t->data); 1064 } else if (bset_written(b, t)) { 1065 /* 1066 * Each node in the auxiliary search tree covers a certain range 1067 * of bits, and keys above and below the set it covers might 1068 * differ outside those bits - so we have to special case the 1069 * start and end - handle that here: 1070 */ 1071 1072 if (unlikely(bkey_cmp(search, &t->end) >= 0)) 1073 return bset_bkey_last(t->data); 1074 1075 if (unlikely(bkey_cmp(search, t->data->start) < 0)) 1076 return t->data->start; 1077 1078 i = bset_search_tree(t, search); 1079 } else { 1080 BUG_ON(!b->nsets && 1081 t->size < bkey_to_cacheline(t, bset_bkey_last(t->data))); 1082 1083 i = bset_search_write_set(t, search); 1084 } 1085 1086 if (btree_keys_expensive_checks(b)) { 1087 BUG_ON(bset_written(b, t) && 1088 i.l != t->data->start && 1089 bkey_cmp(tree_to_prev_bkey(t, 1090 inorder_to_tree(bkey_to_cacheline(t, i.l), t)), 1091 search) > 0); 1092 1093 BUG_ON(i.r != bset_bkey_last(t->data) && 1094 bkey_cmp(i.r, search) <= 0); 1095 } 1096 1097 while (likely(i.l != i.r) && 1098 bkey_cmp(i.l, search) <= 0) 1099 i.l = bkey_next(i.l); 1100 1101 return i.l; 1102 } 1103 EXPORT_SYMBOL(__bch_bset_search); 1104 1105 /* Btree iterator */ 1106 1107 typedef bool (btree_iter_cmp_fn)(struct btree_iter_set, 1108 struct btree_iter_set); 1109 1110 static inline bool btree_iter_cmp(struct btree_iter_set l, 1111 struct btree_iter_set r) 1112 { 1113 return bkey_cmp(l.k, r.k) > 0; 1114 } 1115 1116 static inline bool btree_iter_end(struct btree_iter *iter) 1117 { 1118 return !iter->used; 1119 } 1120 1121 void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, 1122 struct bkey *end) 1123 { 1124 if (k != end) 1125 BUG_ON(!heap_add(iter, 1126 ((struct btree_iter_set) { k, end }), 1127 btree_iter_cmp)); 1128 } 1129 1130 static struct bkey *__bch_btree_iter_init(struct btree_keys *b, 1131 struct btree_iter *iter, 1132 struct bkey *search, 1133 struct bset_tree *start) 1134 { 1135 struct bkey *ret = NULL; 1136 1137 iter->size = ARRAY_SIZE(iter->data); 1138 iter->used = 0; 1139 1140 #ifdef CONFIG_BCACHE_DEBUG 1141 iter->b = b; 1142 #endif 1143 1144 for (; start <= bset_tree_last(b); start++) { 1145 ret = bch_bset_search(b, start, search); 1146 bch_btree_iter_push(iter, ret, bset_bkey_last(start->data)); 1147 } 1148 1149 return ret; 1150 } 1151 1152 struct bkey *bch_btree_iter_init(struct btree_keys *b, 1153 struct btree_iter *iter, 1154 struct bkey *search) 1155 { 1156 return __bch_btree_iter_init(b, iter, search, b->set); 1157 } 1158 EXPORT_SYMBOL(bch_btree_iter_init); 1159 1160 static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, 1161 btree_iter_cmp_fn *cmp) 1162 { 1163 struct btree_iter_set b __maybe_unused; 1164 struct bkey *ret = NULL; 1165 1166 if (!btree_iter_end(iter)) { 1167 bch_btree_iter_next_check(iter); 1168 1169 ret = iter->data->k; 1170 iter->data->k = bkey_next(iter->data->k); 1171 1172 if (iter->data->k > iter->data->end) { 1173 WARN_ONCE(1, "bset was corrupt!\n"); 1174 iter->data->k = iter->data->end; 1175 } 1176 1177 if (iter->data->k == iter->data->end) 1178 heap_pop(iter, b, cmp); 1179 else 1180 heap_sift(iter, 0, cmp); 1181 } 1182 1183 return ret; 1184 } 1185 1186 struct bkey *bch_btree_iter_next(struct btree_iter *iter) 1187 { 1188 return __bch_btree_iter_next(iter, btree_iter_cmp); 1189 1190 } 1191 EXPORT_SYMBOL(bch_btree_iter_next); 1192 1193 struct 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 1207 void bch_bset_sort_state_free(struct bset_sort_state *state) 1208 { 1209 mempool_exit(&state->pool); 1210 } 1211 1212 int 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 EXPORT_SYMBOL(bch_bset_sort_state_init); 1223 1224 static void btree_mergesort(struct btree_keys *b, struct bset *out, 1225 struct btree_iter *iter, 1226 bool fixup, bool remove_stale) 1227 { 1228 int i; 1229 struct bkey *k, *last = NULL; 1230 BKEY_PADDED(k) tmp; 1231 bool (*bad)(struct btree_keys *, const struct bkey *) = remove_stale 1232 ? bch_ptr_bad 1233 : bch_ptr_invalid; 1234 1235 /* Heapify the iterator, using our comparison function */ 1236 for (i = iter->used / 2 - 1; i >= 0; --i) 1237 heap_sift(iter, i, b->ops->sort_cmp); 1238 1239 while (!btree_iter_end(iter)) { 1240 if (b->ops->sort_fixup && fixup) 1241 k = b->ops->sort_fixup(iter, &tmp.k); 1242 else 1243 k = NULL; 1244 1245 if (!k) 1246 k = __bch_btree_iter_next(iter, b->ops->sort_cmp); 1247 1248 if (bad(b, k)) 1249 continue; 1250 1251 if (!last) { 1252 last = out->start; 1253 bkey_copy(last, k); 1254 } else if (!bch_bkey_try_merge(b, last, k)) { 1255 last = bkey_next(last); 1256 bkey_copy(last, k); 1257 } 1258 } 1259 1260 out->keys = last ? (uint64_t *) bkey_next(last) - out->d : 0; 1261 1262 pr_debug("sorted %i keys", out->keys); 1263 } 1264 1265 static void __btree_sort(struct btree_keys *b, struct btree_iter *iter, 1266 unsigned int start, unsigned int order, bool fixup, 1267 struct bset_sort_state *state) 1268 { 1269 uint64_t start_time; 1270 bool used_mempool = false; 1271 struct bset *out = (void *) __get_free_pages(__GFP_NOWARN|GFP_NOWAIT, 1272 order); 1273 if (!out) { 1274 struct page *outp; 1275 1276 BUG_ON(order > state->page_order); 1277 1278 outp = mempool_alloc(&state->pool, GFP_NOIO); 1279 out = page_address(outp); 1280 used_mempool = true; 1281 order = state->page_order; 1282 } 1283 1284 start_time = local_clock(); 1285 1286 btree_mergesort(b, out, iter, fixup, false); 1287 b->nsets = start; 1288 1289 if (!start && order == b->page_order) { 1290 /* 1291 * Our temporary buffer is the same size as the btree node's 1292 * buffer, we can just swap buffers instead of doing a big 1293 * memcpy() 1294 */ 1295 1296 out->magic = b->set->data->magic; 1297 out->seq = b->set->data->seq; 1298 out->version = b->set->data->version; 1299 swap(out, b->set->data); 1300 } else { 1301 b->set[start].data->keys = out->keys; 1302 memcpy(b->set[start].data->start, out->start, 1303 (void *) bset_bkey_last(out) - (void *) out->start); 1304 } 1305 1306 if (used_mempool) 1307 mempool_free(virt_to_page(out), &state->pool); 1308 else 1309 free_pages((unsigned long) out, order); 1310 1311 bch_bset_build_written_tree(b); 1312 1313 if (!start) 1314 bch_time_stats_update(&state->time, start_time); 1315 } 1316 1317 void bch_btree_sort_partial(struct btree_keys *b, unsigned int start, 1318 struct bset_sort_state *state) 1319 { 1320 size_t order = b->page_order, keys = 0; 1321 struct btree_iter iter; 1322 int oldsize = bch_count_data(b); 1323 1324 __bch_btree_iter_init(b, &iter, NULL, &b->set[start]); 1325 1326 if (start) { 1327 unsigned int i; 1328 1329 for (i = start; i <= b->nsets; i++) 1330 keys += b->set[i].data->keys; 1331 1332 order = get_order(__set_bytes(b->set->data, keys)); 1333 } 1334 1335 __btree_sort(b, &iter, start, order, false, state); 1336 1337 EBUG_ON(oldsize >= 0 && bch_count_data(b) != oldsize); 1338 } 1339 EXPORT_SYMBOL(bch_btree_sort_partial); 1340 1341 void bch_btree_sort_and_fix_extents(struct btree_keys *b, 1342 struct btree_iter *iter, 1343 struct bset_sort_state *state) 1344 { 1345 __btree_sort(b, iter, 0, b->page_order, true, state); 1346 } 1347 1348 void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new, 1349 struct bset_sort_state *state) 1350 { 1351 uint64_t start_time = local_clock(); 1352 struct btree_iter iter; 1353 1354 bch_btree_iter_init(b, &iter, NULL); 1355 1356 btree_mergesort(b, new->set->data, &iter, false, true); 1357 1358 bch_time_stats_update(&state->time, start_time); 1359 1360 new->set->size = 0; // XXX: why? 1361 } 1362 1363 #define SORT_CRIT (4096 / sizeof(uint64_t)) 1364 1365 void bch_btree_sort_lazy(struct btree_keys *b, struct bset_sort_state *state) 1366 { 1367 unsigned int crit = SORT_CRIT; 1368 int i; 1369 1370 /* Don't sort if nothing to do */ 1371 if (!b->nsets) 1372 goto out; 1373 1374 for (i = b->nsets - 1; i >= 0; --i) { 1375 crit *= state->crit_factor; 1376 1377 if (b->set[i].data->keys < crit) { 1378 bch_btree_sort_partial(b, i, state); 1379 return; 1380 } 1381 } 1382 1383 /* Sort if we'd overflow */ 1384 if (b->nsets + 1 == MAX_BSETS) { 1385 bch_btree_sort(b, state); 1386 return; 1387 } 1388 1389 out: 1390 bch_bset_build_written_tree(b); 1391 } 1392 EXPORT_SYMBOL(bch_btree_sort_lazy); 1393 1394 void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *stats) 1395 { 1396 unsigned int i; 1397 1398 for (i = 0; i <= b->nsets; i++) { 1399 struct bset_tree *t = &b->set[i]; 1400 size_t bytes = t->data->keys * sizeof(uint64_t); 1401 size_t j; 1402 1403 if (bset_written(b, t)) { 1404 stats->sets_written++; 1405 stats->bytes_written += bytes; 1406 1407 stats->floats += t->size - 1; 1408 1409 for (j = 1; j < t->size; j++) 1410 if (t->tree[j].exponent == 127) 1411 stats->failed++; 1412 } else { 1413 stats->sets_unwritten++; 1414 stats->bytes_unwritten += bytes; 1415 } 1416 } 1417 } 1418