extents.c 15 KB

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