1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com> 4 * 5 * Uses a block device as cache for other block devices; optimized for SSDs. 6 * All allocation is done in buckets, which should match the erase block size 7 * of the device. 8 * 9 * Buckets containing cached data are kept on a heap sorted by priority; 10 * bucket priority is increased on cache hit, and periodically all the buckets 11 * on the heap have their priority scaled down. This currently is just used as 12 * an LRU but in the future should allow for more intelligent heuristics. 13 * 14 * Buckets have an 8 bit counter; freeing is accomplished by incrementing the 15 * counter. Garbage collection is used to remove stale pointers. 16 * 17 * Indexing is done via a btree; nodes are not necessarily fully sorted, rather 18 * as keys are inserted we only sort the pages that have not yet been written. 19 * When garbage collection is run, we resort the entire node. 20 * 21 * All configuration is done via sysfs; see Documentation/bcache.txt. 22 */ 23 24 #include "bcache.h" 25 #include "btree.h" 26 #include "debug.h" 27 #include "extents.h" 28 #include "writeback.h" 29 30 static void sort_key_next(struct btree_iter *iter, 31 struct btree_iter_set *i) 32 { 33 i->k = bkey_next(i->k); 34 35 if (i->k == i->end) 36 *i = iter->data[--iter->used]; 37 } 38 39 static bool bch_key_sort_cmp(struct btree_iter_set l, 40 struct btree_iter_set r) 41 { 42 int64_t c = bkey_cmp(l.k, r.k); 43 44 return c ? c > 0 : l.k < r.k; 45 } 46 47 static bool __ptr_invalid(struct cache_set *c, const struct bkey *k) 48 { 49 unsigned i; 50 51 for (i = 0; i < KEY_PTRS(k); i++) 52 if (ptr_available(c, k, i)) { 53 struct cache *ca = PTR_CACHE(c, k, i); 54 size_t bucket = PTR_BUCKET_NR(c, k, i); 55 size_t r = bucket_remainder(c, PTR_OFFSET(k, i)); 56 57 if (KEY_SIZE(k) + r > c->sb.bucket_size || 58 bucket < ca->sb.first_bucket || 59 bucket >= ca->sb.nbuckets) 60 return true; 61 } 62 63 return false; 64 } 65 66 /* Common among btree and extent ptrs */ 67 68 static const char *bch_ptr_status(struct cache_set *c, const struct bkey *k) 69 { 70 unsigned i; 71 72 for (i = 0; i < KEY_PTRS(k); i++) 73 if (ptr_available(c, k, i)) { 74 struct cache *ca = PTR_CACHE(c, k, i); 75 size_t bucket = PTR_BUCKET_NR(c, k, i); 76 size_t r = bucket_remainder(c, PTR_OFFSET(k, i)); 77 78 if (KEY_SIZE(k) + r > c->sb.bucket_size) 79 return "bad, length too big"; 80 if (bucket < ca->sb.first_bucket) 81 return "bad, short offset"; 82 if (bucket >= ca->sb.nbuckets) 83 return "bad, offset past end of device"; 84 if (ptr_stale(c, k, i)) 85 return "stale"; 86 } 87 88 if (!bkey_cmp(k, &ZERO_KEY)) 89 return "bad, null key"; 90 if (!KEY_PTRS(k)) 91 return "bad, no pointers"; 92 if (!KEY_SIZE(k)) 93 return "zeroed key"; 94 return ""; 95 } 96 97 void bch_extent_to_text(char *buf, size_t size, const struct bkey *k) 98 { 99 unsigned i = 0; 100 char *out = buf, *end = buf + size; 101 102 #define p(...) (out += scnprintf(out, end - out, __VA_ARGS__)) 103 104 p("%llu:%llu len %llu -> [", KEY_INODE(k), KEY_START(k), KEY_SIZE(k)); 105 106 for (i = 0; i < KEY_PTRS(k); i++) { 107 if (i) 108 p(", "); 109 110 if (PTR_DEV(k, i) == PTR_CHECK_DEV) 111 p("check dev"); 112 else 113 p("%llu:%llu gen %llu", PTR_DEV(k, i), 114 PTR_OFFSET(k, i), PTR_GEN(k, i)); 115 } 116 117 p("]"); 118 119 if (KEY_DIRTY(k)) 120 p(" dirty"); 121 if (KEY_CSUM(k)) 122 p(" cs%llu %llx", KEY_CSUM(k), k->ptr[1]); 123 #undef p 124 } 125 126 static void bch_bkey_dump(struct btree_keys *keys, const struct bkey *k) 127 { 128 struct btree *b = container_of(keys, struct btree, keys); 129 unsigned j; 130 char buf[80]; 131 132 bch_extent_to_text(buf, sizeof(buf), k); 133 printk(" %s", buf); 134 135 for (j = 0; j < KEY_PTRS(k); j++) { 136 size_t n = PTR_BUCKET_NR(b->c, k, j); 137 printk(" bucket %zu", n); 138 139 if (n >= b->c->sb.first_bucket && n < b->c->sb.nbuckets) 140 printk(" prio %i", 141 PTR_BUCKET(b->c, k, j)->prio); 142 } 143 144 printk(" %s\n", bch_ptr_status(b->c, k)); 145 } 146 147 /* Btree ptrs */ 148 149 bool __bch_btree_ptr_invalid(struct cache_set *c, const struct bkey *k) 150 { 151 char buf[80]; 152 153 if (!KEY_PTRS(k) || !KEY_SIZE(k) || KEY_DIRTY(k)) 154 goto bad; 155 156 if (__ptr_invalid(c, k)) 157 goto bad; 158 159 return false; 160 bad: 161 bch_extent_to_text(buf, sizeof(buf), k); 162 cache_bug(c, "spotted btree ptr %s: %s", buf, bch_ptr_status(c, k)); 163 return true; 164 } 165 166 static bool bch_btree_ptr_invalid(struct btree_keys *bk, const struct bkey *k) 167 { 168 struct btree *b = container_of(bk, struct btree, keys); 169 return __bch_btree_ptr_invalid(b->c, k); 170 } 171 172 static bool btree_ptr_bad_expensive(struct btree *b, const struct bkey *k) 173 { 174 unsigned i; 175 char buf[80]; 176 struct bucket *g; 177 178 if (mutex_trylock(&b->c->bucket_lock)) { 179 for (i = 0; i < KEY_PTRS(k); i++) 180 if (ptr_available(b->c, k, i)) { 181 g = PTR_BUCKET(b->c, k, i); 182 183 if (KEY_DIRTY(k) || 184 g->prio != BTREE_PRIO || 185 (b->c->gc_mark_valid && 186 GC_MARK(g) != GC_MARK_METADATA)) 187 goto err; 188 } 189 190 mutex_unlock(&b->c->bucket_lock); 191 } 192 193 return false; 194 err: 195 mutex_unlock(&b->c->bucket_lock); 196 bch_extent_to_text(buf, sizeof(buf), k); 197 btree_bug(b, 198 "inconsistent btree pointer %s: bucket %zi pin %i prio %i gen %i last_gc %i mark %llu", 199 buf, PTR_BUCKET_NR(b->c, k, i), atomic_read(&g->pin), 200 g->prio, g->gen, g->last_gc, GC_MARK(g)); 201 return true; 202 } 203 204 static bool bch_btree_ptr_bad(struct btree_keys *bk, const struct bkey *k) 205 { 206 struct btree *b = container_of(bk, struct btree, keys); 207 unsigned i; 208 209 if (!bkey_cmp(k, &ZERO_KEY) || 210 !KEY_PTRS(k) || 211 bch_ptr_invalid(bk, k)) 212 return true; 213 214 for (i = 0; i < KEY_PTRS(k); i++) 215 if (!ptr_available(b->c, k, i) || 216 ptr_stale(b->c, k, i)) 217 return true; 218 219 if (expensive_debug_checks(b->c) && 220 btree_ptr_bad_expensive(b, k)) 221 return true; 222 223 return false; 224 } 225 226 static bool bch_btree_ptr_insert_fixup(struct btree_keys *bk, 227 struct bkey *insert, 228 struct btree_iter *iter, 229 struct bkey *replace_key) 230 { 231 struct btree *b = container_of(bk, struct btree, keys); 232 233 if (!KEY_OFFSET(insert)) 234 btree_current_write(b)->prio_blocked++; 235 236 return false; 237 } 238 239 const struct btree_keys_ops bch_btree_keys_ops = { 240 .sort_cmp = bch_key_sort_cmp, 241 .insert_fixup = bch_btree_ptr_insert_fixup, 242 .key_invalid = bch_btree_ptr_invalid, 243 .key_bad = bch_btree_ptr_bad, 244 .key_to_text = bch_extent_to_text, 245 .key_dump = bch_bkey_dump, 246 }; 247 248 /* Extents */ 249 250 /* 251 * Returns true if l > r - unless l == r, in which case returns true if l is 252 * older than r. 253 * 254 * Necessary for btree_sort_fixup() - if there are multiple keys that compare 255 * equal in different sets, we have to process them newest to oldest. 256 */ 257 static bool bch_extent_sort_cmp(struct btree_iter_set l, 258 struct btree_iter_set r) 259 { 260 int64_t c = bkey_cmp(&START_KEY(l.k), &START_KEY(r.k)); 261 262 return c ? c > 0 : l.k < r.k; 263 } 264 265 static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, 266 struct bkey *tmp) 267 { 268 while (iter->used > 1) { 269 struct btree_iter_set *top = iter->data, *i = top + 1; 270 271 if (iter->used > 2 && 272 bch_extent_sort_cmp(i[0], i[1])) 273 i++; 274 275 if (bkey_cmp(top->k, &START_KEY(i->k)) <= 0) 276 break; 277 278 if (!KEY_SIZE(i->k)) { 279 sort_key_next(iter, i); 280 heap_sift(iter, i - top, bch_extent_sort_cmp); 281 continue; 282 } 283 284 if (top->k > i->k) { 285 if (bkey_cmp(top->k, i->k) >= 0) 286 sort_key_next(iter, i); 287 else 288 bch_cut_front(top->k, i->k); 289 290 heap_sift(iter, i - top, bch_extent_sort_cmp); 291 } else { 292 /* can't happen because of comparison func */ 293 BUG_ON(!bkey_cmp(&START_KEY(top->k), &START_KEY(i->k))); 294 295 if (bkey_cmp(i->k, top->k) < 0) { 296 bkey_copy(tmp, top->k); 297 298 bch_cut_back(&START_KEY(i->k), tmp); 299 bch_cut_front(i->k, top->k); 300 heap_sift(iter, 0, bch_extent_sort_cmp); 301 302 return tmp; 303 } else { 304 bch_cut_back(&START_KEY(i->k), top->k); 305 } 306 } 307 } 308 309 return NULL; 310 } 311 312 static void bch_subtract_dirty(struct bkey *k, 313 struct cache_set *c, 314 uint64_t offset, 315 int sectors) 316 { 317 if (KEY_DIRTY(k)) 318 bcache_dev_sectors_dirty_add(c, KEY_INODE(k), 319 offset, -sectors); 320 } 321 322 static bool bch_extent_insert_fixup(struct btree_keys *b, 323 struct bkey *insert, 324 struct btree_iter *iter, 325 struct bkey *replace_key) 326 { 327 struct cache_set *c = container_of(b, struct btree, keys)->c; 328 329 uint64_t old_offset; 330 unsigned old_size, sectors_found = 0; 331 332 BUG_ON(!KEY_OFFSET(insert)); 333 BUG_ON(!KEY_SIZE(insert)); 334 335 while (1) { 336 struct bkey *k = bch_btree_iter_next(iter); 337 if (!k) 338 break; 339 340 if (bkey_cmp(&START_KEY(k), insert) >= 0) { 341 if (KEY_SIZE(k)) 342 break; 343 else 344 continue; 345 } 346 347 if (bkey_cmp(k, &START_KEY(insert)) <= 0) 348 continue; 349 350 old_offset = KEY_START(k); 351 old_size = KEY_SIZE(k); 352 353 /* 354 * We might overlap with 0 size extents; we can't skip these 355 * because if they're in the set we're inserting to we have to 356 * adjust them so they don't overlap with the key we're 357 * inserting. But we don't want to check them for replace 358 * operations. 359 */ 360 361 if (replace_key && KEY_SIZE(k)) { 362 /* 363 * k might have been split since we inserted/found the 364 * key we're replacing 365 */ 366 unsigned i; 367 uint64_t offset = KEY_START(k) - 368 KEY_START(replace_key); 369 370 /* But it must be a subset of the replace key */ 371 if (KEY_START(k) < KEY_START(replace_key) || 372 KEY_OFFSET(k) > KEY_OFFSET(replace_key)) 373 goto check_failed; 374 375 /* We didn't find a key that we were supposed to */ 376 if (KEY_START(k) > KEY_START(insert) + sectors_found) 377 goto check_failed; 378 379 if (!bch_bkey_equal_header(k, replace_key)) 380 goto check_failed; 381 382 /* skip past gen */ 383 offset <<= 8; 384 385 BUG_ON(!KEY_PTRS(replace_key)); 386 387 for (i = 0; i < KEY_PTRS(replace_key); i++) 388 if (k->ptr[i] != replace_key->ptr[i] + offset) 389 goto check_failed; 390 391 sectors_found = KEY_OFFSET(k) - KEY_START(insert); 392 } 393 394 if (bkey_cmp(insert, k) < 0 && 395 bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0) { 396 /* 397 * We overlapped in the middle of an existing key: that 398 * means we have to split the old key. But we have to do 399 * slightly different things depending on whether the 400 * old key has been written out yet. 401 */ 402 403 struct bkey *top; 404 405 bch_subtract_dirty(k, c, KEY_START(insert), 406 KEY_SIZE(insert)); 407 408 if (bkey_written(b, k)) { 409 /* 410 * We insert a new key to cover the top of the 411 * old key, and the old key is modified in place 412 * to represent the bottom split. 413 * 414 * It's completely arbitrary whether the new key 415 * is the top or the bottom, but it has to match 416 * up with what btree_sort_fixup() does - it 417 * doesn't check for this kind of overlap, it 418 * depends on us inserting a new key for the top 419 * here. 420 */ 421 top = bch_bset_search(b, bset_tree_last(b), 422 insert); 423 bch_bset_insert(b, top, k); 424 } else { 425 BKEY_PADDED(key) temp; 426 bkey_copy(&temp.key, k); 427 bch_bset_insert(b, k, &temp.key); 428 top = bkey_next(k); 429 } 430 431 bch_cut_front(insert, top); 432 bch_cut_back(&START_KEY(insert), k); 433 bch_bset_fix_invalidated_key(b, k); 434 goto out; 435 } 436 437 if (bkey_cmp(insert, k) < 0) { 438 bch_cut_front(insert, k); 439 } else { 440 if (bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0) 441 old_offset = KEY_START(insert); 442 443 if (bkey_written(b, k) && 444 bkey_cmp(&START_KEY(insert), &START_KEY(k)) <= 0) { 445 /* 446 * Completely overwrote, so we don't have to 447 * invalidate the binary search tree 448 */ 449 bch_cut_front(k, k); 450 } else { 451 __bch_cut_back(&START_KEY(insert), k); 452 bch_bset_fix_invalidated_key(b, k); 453 } 454 } 455 456 bch_subtract_dirty(k, c, old_offset, old_size - KEY_SIZE(k)); 457 } 458 459 check_failed: 460 if (replace_key) { 461 if (!sectors_found) { 462 return true; 463 } else if (sectors_found < KEY_SIZE(insert)) { 464 SET_KEY_OFFSET(insert, KEY_OFFSET(insert) - 465 (KEY_SIZE(insert) - sectors_found)); 466 SET_KEY_SIZE(insert, sectors_found); 467 } 468 } 469 out: 470 if (KEY_DIRTY(insert)) 471 bcache_dev_sectors_dirty_add(c, KEY_INODE(insert), 472 KEY_START(insert), 473 KEY_SIZE(insert)); 474 475 return false; 476 } 477 478 bool __bch_extent_invalid(struct cache_set *c, const struct bkey *k) 479 { 480 char buf[80]; 481 482 if (!KEY_SIZE(k)) 483 return true; 484 485 if (KEY_SIZE(k) > KEY_OFFSET(k)) 486 goto bad; 487 488 if (__ptr_invalid(c, k)) 489 goto bad; 490 491 return false; 492 bad: 493 bch_extent_to_text(buf, sizeof(buf), k); 494 cache_bug(c, "spotted extent %s: %s", buf, bch_ptr_status(c, k)); 495 return true; 496 } 497 498 static bool bch_extent_invalid(struct btree_keys *bk, const struct bkey *k) 499 { 500 struct btree *b = container_of(bk, struct btree, keys); 501 return __bch_extent_invalid(b->c, k); 502 } 503 504 static bool bch_extent_bad_expensive(struct btree *b, const struct bkey *k, 505 unsigned ptr) 506 { 507 struct bucket *g = PTR_BUCKET(b->c, k, ptr); 508 char buf[80]; 509 510 if (mutex_trylock(&b->c->bucket_lock)) { 511 if (b->c->gc_mark_valid && 512 (!GC_MARK(g) || 513 GC_MARK(g) == GC_MARK_METADATA || 514 (GC_MARK(g) != GC_MARK_DIRTY && KEY_DIRTY(k)))) 515 goto err; 516 517 if (g->prio == BTREE_PRIO) 518 goto err; 519 520 mutex_unlock(&b->c->bucket_lock); 521 } 522 523 return false; 524 err: 525 mutex_unlock(&b->c->bucket_lock); 526 bch_extent_to_text(buf, sizeof(buf), k); 527 btree_bug(b, 528 "inconsistent extent pointer %s:\nbucket %zu pin %i prio %i gen %i last_gc %i mark %llu", 529 buf, PTR_BUCKET_NR(b->c, k, ptr), atomic_read(&g->pin), 530 g->prio, g->gen, g->last_gc, GC_MARK(g)); 531 return true; 532 } 533 534 static bool bch_extent_bad(struct btree_keys *bk, const struct bkey *k) 535 { 536 struct btree *b = container_of(bk, struct btree, keys); 537 struct bucket *g; 538 unsigned i, stale; 539 540 if (!KEY_PTRS(k) || 541 bch_extent_invalid(bk, k)) 542 return true; 543 544 for (i = 0; i < KEY_PTRS(k); i++) 545 if (!ptr_available(b->c, k, i)) 546 return true; 547 548 if (!expensive_debug_checks(b->c) && KEY_DIRTY(k)) 549 return false; 550 551 for (i = 0; i < KEY_PTRS(k); i++) { 552 g = PTR_BUCKET(b->c, k, i); 553 stale = ptr_stale(b->c, k, i); 554 555 btree_bug_on(stale > 96, b, 556 "key too stale: %i, need_gc %u", 557 stale, b->c->need_gc); 558 559 btree_bug_on(stale && KEY_DIRTY(k) && KEY_SIZE(k), 560 b, "stale dirty pointer"); 561 562 if (stale) 563 return true; 564 565 if (expensive_debug_checks(b->c) && 566 bch_extent_bad_expensive(b, k, i)) 567 return true; 568 } 569 570 return false; 571 } 572 573 static uint64_t merge_chksums(struct bkey *l, struct bkey *r) 574 { 575 return (l->ptr[KEY_PTRS(l)] + r->ptr[KEY_PTRS(r)]) & 576 ~((uint64_t)1 << 63); 577 } 578 579 static bool bch_extent_merge(struct btree_keys *bk, struct bkey *l, struct bkey *r) 580 { 581 struct btree *b = container_of(bk, struct btree, keys); 582 unsigned i; 583 584 if (key_merging_disabled(b->c)) 585 return false; 586 587 for (i = 0; i < KEY_PTRS(l); i++) 588 if (l->ptr[i] + MAKE_PTR(0, KEY_SIZE(l), 0) != r->ptr[i] || 589 PTR_BUCKET_NR(b->c, l, i) != PTR_BUCKET_NR(b->c, r, i)) 590 return false; 591 592 /* Keys with no pointers aren't restricted to one bucket and could 593 * overflow KEY_SIZE 594 */ 595 if (KEY_SIZE(l) + KEY_SIZE(r) > USHRT_MAX) { 596 SET_KEY_OFFSET(l, KEY_OFFSET(l) + USHRT_MAX - KEY_SIZE(l)); 597 SET_KEY_SIZE(l, USHRT_MAX); 598 599 bch_cut_front(l, r); 600 return false; 601 } 602 603 if (KEY_CSUM(l)) { 604 if (KEY_CSUM(r)) 605 l->ptr[KEY_PTRS(l)] = merge_chksums(l, r); 606 else 607 SET_KEY_CSUM(l, 0); 608 } 609 610 SET_KEY_OFFSET(l, KEY_OFFSET(l) + KEY_SIZE(r)); 611 SET_KEY_SIZE(l, KEY_SIZE(l) + KEY_SIZE(r)); 612 613 return true; 614 } 615 616 const struct btree_keys_ops bch_extent_keys_ops = { 617 .sort_cmp = bch_extent_sort_cmp, 618 .sort_fixup = bch_extent_sort_fixup, 619 .insert_fixup = bch_extent_insert_fixup, 620 .key_invalid = bch_extent_invalid, 621 .key_bad = bch_extent_bad, 622 .key_merge = bch_extent_merge, 623 .key_to_text = bch_extent_to_text, 624 .key_dump = bch_bkey_dump, 625 .is_extents = true, 626 }; 627