extents.c 15 KB

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