drivers/md/bcache/extents.c

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