alloc.c 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Primary bucket allocation code
  4. *
  5. * Copyright 2012 Google, Inc.
  6. *
  7. * Allocation in bcache is done in terms of buckets:
  8. *
  9. * Each bucket has associated an 8 bit gen; this gen corresponds to the gen in
  10. * btree pointers - they must match for the pointer to be considered valid.
  11. *
  12. * Thus (assuming a bucket has no dirty data or metadata in it) we can reuse a
  13. * bucket simply by incrementing its gen.
  14. *
  15. * The gens (along with the priorities; it's really the gens are important but
  16. * the code is named as if it's the priorities) are written in an arbitrary list
  17. * of buckets on disk, with a pointer to them in the journal header.
  18. *
  19. * When we invalidate a bucket, we have to write its new gen to disk and wait
  20. * for that write to complete before we use it - otherwise after a crash we
  21. * could have pointers that appeared to be good but pointed to data that had
  22. * been overwritten.
  23. *
  24. * Since the gens and priorities are all stored contiguously on disk, we can
  25. * batch this up: We fill up the free_inc list with freshly invalidated buckets,
  26. * call prio_write(), and when prio_write() finishes we pull buckets off the
  27. * free_inc list and optionally discard them.
  28. *
  29. * free_inc isn't the only freelist - if it was, we'd often to sleep while
  30. * priorities and gens were being written before we could allocate. c->free is a
  31. * smaller freelist, and buckets on that list are always ready to be used.
  32. *
  33. * If we've got discards enabled, that happens when a bucket moves from the
  34. * free_inc list to the free list.
  35. *
  36. * There is another freelist, because sometimes we have buckets that we know
  37. * have nothing pointing into them - these we can reuse without waiting for
  38. * priorities to be rewritten. These come from freed btree nodes and buckets
  39. * that garbage collection discovered no longer had valid keys pointing into
  40. * them (because they were overwritten). That's the unused list - buckets on the
  41. * unused list move to the free list, optionally being discarded in the process.
  42. *
  43. * It's also important to ensure that gens don't wrap around - with respect to
  44. * either the oldest gen in the btree or the gen on disk. This is quite
  45. * difficult to do in practice, but we explicitly guard against it anyways - if
  46. * a bucket is in danger of wrapping around we simply skip invalidating it that
  47. * time around, and we garbage collect or rewrite the priorities sooner than we
  48. * would have otherwise.
  49. *
  50. * bch_bucket_alloc() allocates a single bucket from a specific cache.
  51. *
  52. * bch_bucket_alloc_set() allocates one bucket from different caches
  53. * out of a cache set.
  54. *
  55. * free_some_buckets() drives all the processes described above. It's called
  56. * from bch_bucket_alloc() and a few other places that need to make sure free
  57. * buckets are ready.
  58. *
  59. * invalidate_buckets_(lru|fifo)() find buckets that are available to be
  60. * invalidated, and then invalidate them and stick them on the free_inc list -
  61. * in either lru or fifo order.
  62. */
  63. #include "bcache.h"
  64. #include "btree.h"
  65. #include <linux/blkdev.h>
  66. #include <linux/kthread.h>
  67. #include <linux/random.h>
  68. #include <trace/events/bcache.h>
  69. #define MAX_OPEN_BUCKETS 128
  70. /* Bucket heap / gen */
  71. uint8_t bch_inc_gen(struct cache *ca, struct bucket *b)
  72. {
  73. uint8_t ret = ++b->gen;
  74. ca->set->need_gc = max(ca->set->need_gc, bucket_gc_gen(b));
  75. WARN_ON_ONCE(ca->set->need_gc > BUCKET_GC_GEN_MAX);
  76. return ret;
  77. }
  78. void bch_rescale_priorities(struct cache_set *c, int sectors)
  79. {
  80. struct cache *ca;
  81. struct bucket *b;
  82. unsigned long next = c->nbuckets * c->cache->sb.bucket_size / 1024;
  83. int r;
  84. atomic_sub(sectors, &c->rescale);
  85. do {
  86. r = atomic_read(&c->rescale);
  87. if (r >= 0)
  88. return;
  89. } while (atomic_cmpxchg(&c->rescale, r, r + next) != r);
  90. mutex_lock(&c->bucket_lock);
  91. c->min_prio = USHRT_MAX;
  92. ca = c->cache;
  93. for_each_bucket(b, ca)
  94. if (b->prio &&
  95. b->prio != BTREE_PRIO &&
  96. !atomic_read(&b->pin)) {
  97. b->prio--;
  98. c->min_prio = min(c->min_prio, b->prio);
  99. }
  100. mutex_unlock(&c->bucket_lock);
  101. }
  102. /*
  103. * Background allocation thread: scans for buckets to be invalidated,
  104. * invalidates them, rewrites prios/gens (marking them as invalidated on disk),
  105. * then optionally issues discard commands to the newly free buckets, then puts
  106. * them on the various freelists.
  107. */
  108. static inline bool can_inc_bucket_gen(struct bucket *b)
  109. {
  110. return bucket_gc_gen(b) < BUCKET_GC_GEN_MAX;
  111. }
  112. bool bch_can_invalidate_bucket(struct cache *ca, struct bucket *b)
  113. {
  114. BUG_ON(!ca->set->gc_mark_valid);
  115. return (!GC_MARK(b) ||
  116. GC_MARK(b) == GC_MARK_RECLAIMABLE) &&
  117. !atomic_read(&b->pin) &&
  118. can_inc_bucket_gen(b);
  119. }
  120. void __bch_invalidate_one_bucket(struct cache *ca, struct bucket *b)
  121. {
  122. lockdep_assert_held(&ca->set->bucket_lock);
  123. BUG_ON(GC_MARK(b) && GC_MARK(b) != GC_MARK_RECLAIMABLE);
  124. if (GC_SECTORS_USED(b))
  125. trace_bcache_invalidate(ca, b - ca->buckets);
  126. bch_inc_gen(ca, b);
  127. b->prio = INITIAL_PRIO;
  128. atomic_inc(&b->pin);
  129. }
  130. static void bch_invalidate_one_bucket(struct cache *ca, struct bucket *b)
  131. {
  132. __bch_invalidate_one_bucket(ca, b);
  133. fifo_push(&ca->free_inc, b - ca->buckets);
  134. }
  135. /*
  136. * Determines what order we're going to reuse buckets, smallest bucket_prio()
  137. * first: we also take into account the number of sectors of live data in that
  138. * bucket, and in order for that multiply to make sense we have to scale bucket
  139. *
  140. * Thus, we scale the bucket priorities so that the bucket with the smallest
  141. * prio is worth 1/8th of what INITIAL_PRIO is worth.
  142. */
  143. #define bucket_prio(b) \
  144. ({ \
  145. unsigned int min_prio = (INITIAL_PRIO - ca->set->min_prio) / 8; \
  146. \
  147. (b->prio - ca->set->min_prio + min_prio) * GC_SECTORS_USED(b); \
  148. })
  149. #define bucket_max_cmp(l, r) (bucket_prio(l) < bucket_prio(r))
  150. #define bucket_min_cmp(l, r) (bucket_prio(l) > bucket_prio(r))
  151. static void invalidate_buckets_lru(struct cache *ca)
  152. {
  153. struct bucket *b;
  154. ssize_t i;
  155. ca->heap.used = 0;
  156. for_each_bucket(b, ca) {
  157. if (!bch_can_invalidate_bucket(ca, b))
  158. continue;
  159. if (!heap_full(&ca->heap))
  160. heap_add(&ca->heap, b, bucket_max_cmp);
  161. else if (bucket_max_cmp(b, heap_peek(&ca->heap))) {
  162. ca->heap.data[0] = b;
  163. heap_sift(&ca->heap, 0, bucket_max_cmp);
  164. }
  165. }
  166. for (i = ca->heap.used / 2 - 1; i >= 0; --i)
  167. heap_sift(&ca->heap, i, bucket_min_cmp);
  168. while (!fifo_full(&ca->free_inc)) {
  169. if (!heap_pop(&ca->heap, b, bucket_min_cmp)) {
  170. /*
  171. * We don't want to be calling invalidate_buckets()
  172. * multiple times when it can't do anything
  173. */
  174. ca->invalidate_needs_gc = 1;
  175. wake_up_gc(ca->set);
  176. return;
  177. }
  178. bch_invalidate_one_bucket(ca, b);
  179. }
  180. }
  181. static void invalidate_buckets_fifo(struct cache *ca)
  182. {
  183. struct bucket *b;
  184. size_t checked = 0;
  185. while (!fifo_full(&ca->free_inc)) {
  186. if (ca->fifo_last_bucket < ca->sb.first_bucket ||
  187. ca->fifo_last_bucket >= ca->sb.nbuckets)
  188. ca->fifo_last_bucket = ca->sb.first_bucket;
  189. b = ca->buckets + ca->fifo_last_bucket++;
  190. if (bch_can_invalidate_bucket(ca, b))
  191. bch_invalidate_one_bucket(ca, b);
  192. if (++checked >= ca->sb.nbuckets) {
  193. ca->invalidate_needs_gc = 1;
  194. wake_up_gc(ca->set);
  195. return;
  196. }
  197. }
  198. }
  199. static void invalidate_buckets_random(struct cache *ca)
  200. {
  201. struct bucket *b;
  202. size_t checked = 0;
  203. while (!fifo_full(&ca->free_inc)) {
  204. size_t n;
  205. get_random_bytes(&n, sizeof(n));
  206. n %= (size_t) (ca->sb.nbuckets - ca->sb.first_bucket);
  207. n += ca->sb.first_bucket;
  208. b = ca->buckets + n;
  209. if (bch_can_invalidate_bucket(ca, b))
  210. bch_invalidate_one_bucket(ca, b);
  211. if (++checked >= ca->sb.nbuckets / 2) {
  212. ca->invalidate_needs_gc = 1;
  213. wake_up_gc(ca->set);
  214. return;
  215. }
  216. }
  217. }
  218. static void invalidate_buckets(struct cache *ca)
  219. {
  220. BUG_ON(ca->invalidate_needs_gc);
  221. switch (CACHE_REPLACEMENT(&ca->sb)) {
  222. case CACHE_REPLACEMENT_LRU:
  223. invalidate_buckets_lru(ca);
  224. break;
  225. case CACHE_REPLACEMENT_FIFO:
  226. invalidate_buckets_fifo(ca);
  227. break;
  228. case CACHE_REPLACEMENT_RANDOM:
  229. invalidate_buckets_random(ca);
  230. break;
  231. }
  232. }
  233. #define allocator_wait(ca, cond) \
  234. do { \
  235. while (1) { \
  236. set_current_state(TASK_INTERRUPTIBLE); \
  237. if (cond) \
  238. break; \
  239. \
  240. mutex_unlock(&(ca)->set->bucket_lock); \
  241. if (kthread_should_stop() || \
  242. test_bit(CACHE_SET_IO_DISABLE, &ca->set->flags)) { \
  243. set_current_state(TASK_RUNNING); \
  244. goto out; \
  245. } \
  246. \
  247. schedule(); \
  248. mutex_lock(&(ca)->set->bucket_lock); \
  249. } \
  250. __set_current_state(TASK_RUNNING); \
  251. } while (0)
  252. static int bch_allocator_push(struct cache *ca, long bucket)
  253. {
  254. unsigned int i;
  255. /* Prios/gens are actually the most important reserve */
  256. if (fifo_push(&ca->free[RESERVE_PRIO], bucket))
  257. return true;
  258. for (i = 0; i < RESERVE_NR; i++)
  259. if (fifo_push(&ca->free[i], bucket))
  260. return true;
  261. return false;
  262. }
  263. static int bch_allocator_thread(void *arg)
  264. {
  265. struct cache *ca = arg;
  266. mutex_lock(&ca->set->bucket_lock);
  267. while (1) {
  268. /*
  269. * First, we pull buckets off of the unused and free_inc lists,
  270. * possibly issue discards to them, then we add the bucket to
  271. * the free list:
  272. */
  273. while (1) {
  274. long bucket;
  275. if (!fifo_pop(&ca->free_inc, bucket))
  276. break;
  277. if (ca->discard) {
  278. mutex_unlock(&ca->set->bucket_lock);
  279. blkdev_issue_discard(ca->bdev,
  280. bucket_to_sector(ca->set, bucket),
  281. ca->sb.bucket_size, GFP_KERNEL, 0);
  282. mutex_lock(&ca->set->bucket_lock);
  283. }
  284. allocator_wait(ca, bch_allocator_push(ca, bucket));
  285. wake_up(&ca->set->btree_cache_wait);
  286. wake_up(&ca->set->bucket_wait);
  287. }
  288. /*
  289. * We've run out of free buckets, we need to find some buckets
  290. * we can invalidate. First, invalidate them in memory and add
  291. * them to the free_inc list:
  292. */
  293. retry_invalidate:
  294. allocator_wait(ca, ca->set->gc_mark_valid &&
  295. !ca->invalidate_needs_gc);
  296. invalidate_buckets(ca);
  297. /*
  298. * Now, we write their new gens to disk so we can start writing
  299. * new stuff to them:
  300. */
  301. allocator_wait(ca, !atomic_read(&ca->set->prio_blocked));
  302. if (CACHE_SYNC(&ca->sb)) {
  303. /*
  304. * This could deadlock if an allocation with a btree
  305. * node locked ever blocked - having the btree node
  306. * locked would block garbage collection, but here we're
  307. * waiting on garbage collection before we invalidate
  308. * and free anything.
  309. *
  310. * But this should be safe since the btree code always
  311. * uses btree_check_reserve() before allocating now, and
  312. * if it fails it blocks without btree nodes locked.
  313. */
  314. if (!fifo_full(&ca->free_inc))
  315. goto retry_invalidate;
  316. if (bch_prio_write(ca, false) < 0) {
  317. ca->invalidate_needs_gc = 1;
  318. wake_up_gc(ca->set);
  319. }
  320. }
  321. }
  322. out:
  323. wait_for_kthread_stop();
  324. return 0;
  325. }
  326. /* Allocation */
  327. long bch_bucket_alloc(struct cache *ca, unsigned int reserve, bool wait)
  328. {
  329. DEFINE_WAIT(w);
  330. struct bucket *b;
  331. long r;
  332. /* No allocation if CACHE_SET_IO_DISABLE bit is set */
  333. if (unlikely(test_bit(CACHE_SET_IO_DISABLE, &ca->set->flags)))
  334. return -1;
  335. /* fastpath */
  336. if (fifo_pop(&ca->free[RESERVE_NONE], r) ||
  337. fifo_pop(&ca->free[reserve], r))
  338. goto out;
  339. if (!wait) {
  340. trace_bcache_alloc_fail(ca, reserve);
  341. return -1;
  342. }
  343. do {
  344. prepare_to_wait(&ca->set->bucket_wait, &w,
  345. TASK_UNINTERRUPTIBLE);
  346. mutex_unlock(&ca->set->bucket_lock);
  347. schedule();
  348. mutex_lock(&ca->set->bucket_lock);
  349. } while (!fifo_pop(&ca->free[RESERVE_NONE], r) &&
  350. !fifo_pop(&ca->free[reserve], r));
  351. finish_wait(&ca->set->bucket_wait, &w);
  352. out:
  353. if (ca->alloc_thread)
  354. wake_up_process(ca->alloc_thread);
  355. trace_bcache_alloc(ca, reserve);
  356. if (expensive_debug_checks(ca->set)) {
  357. size_t iter;
  358. long i;
  359. unsigned int j;
  360. for (iter = 0; iter < prio_buckets(ca) * 2; iter++)
  361. BUG_ON(ca->prio_buckets[iter] == (uint64_t) r);
  362. for (j = 0; j < RESERVE_NR; j++)
  363. fifo_for_each(i, &ca->free[j], iter)
  364. BUG_ON(i == r);
  365. fifo_for_each(i, &ca->free_inc, iter)
  366. BUG_ON(i == r);
  367. }
  368. b = ca->buckets + r;
  369. BUG_ON(atomic_read(&b->pin) != 1);
  370. SET_GC_SECTORS_USED(b, ca->sb.bucket_size);
  371. if (reserve <= RESERVE_PRIO) {
  372. SET_GC_MARK(b, GC_MARK_METADATA);
  373. SET_GC_MOVE(b, 0);
  374. b->prio = BTREE_PRIO;
  375. } else {
  376. SET_GC_MARK(b, GC_MARK_RECLAIMABLE);
  377. SET_GC_MOVE(b, 0);
  378. b->prio = INITIAL_PRIO;
  379. }
  380. if (ca->set->avail_nbuckets > 0) {
  381. ca->set->avail_nbuckets--;
  382. bch_update_bucket_in_use(ca->set, &ca->set->gc_stats);
  383. }
  384. return r;
  385. }
  386. void __bch_bucket_free(struct cache *ca, struct bucket *b)
  387. {
  388. SET_GC_MARK(b, 0);
  389. SET_GC_SECTORS_USED(b, 0);
  390. if (ca->set->avail_nbuckets < ca->set->nbuckets) {
  391. ca->set->avail_nbuckets++;
  392. bch_update_bucket_in_use(ca->set, &ca->set->gc_stats);
  393. }
  394. }
  395. void bch_bucket_free(struct cache_set *c, struct bkey *k)
  396. {
  397. unsigned int i;
  398. for (i = 0; i < KEY_PTRS(k); i++)
  399. __bch_bucket_free(PTR_CACHE(c, k, i),
  400. PTR_BUCKET(c, k, i));
  401. }
  402. int __bch_bucket_alloc_set(struct cache_set *c, unsigned int reserve,
  403. struct bkey *k, bool wait)
  404. {
  405. struct cache *ca;
  406. long b;
  407. /* No allocation if CACHE_SET_IO_DISABLE bit is set */
  408. if (unlikely(test_bit(CACHE_SET_IO_DISABLE, &c->flags)))
  409. return -1;
  410. lockdep_assert_held(&c->bucket_lock);
  411. bkey_init(k);
  412. ca = c->cache;
  413. b = bch_bucket_alloc(ca, reserve, wait);
  414. if (b == -1)
  415. goto err;
  416. k->ptr[0] = MAKE_PTR(ca->buckets[b].gen,
  417. bucket_to_sector(c, b),
  418. ca->sb.nr_this_dev);
  419. SET_KEY_PTRS(k, 1);
  420. return 0;
  421. err:
  422. bch_bucket_free(c, k);
  423. bkey_put(c, k);
  424. return -1;
  425. }
  426. int bch_bucket_alloc_set(struct cache_set *c, unsigned int reserve,
  427. struct bkey *k, bool wait)
  428. {
  429. int ret;
  430. mutex_lock(&c->bucket_lock);
  431. ret = __bch_bucket_alloc_set(c, reserve, k, wait);
  432. mutex_unlock(&c->bucket_lock);
  433. return ret;
  434. }
  435. /* Sector allocator */
  436. struct open_bucket {
  437. struct list_head list;
  438. unsigned int last_write_point;
  439. unsigned int sectors_free;
  440. BKEY_PADDED(key);
  441. };
  442. /*
  443. * We keep multiple buckets open for writes, and try to segregate different
  444. * write streams for better cache utilization: first we try to segregate flash
  445. * only volume write streams from cached devices, secondly we look for a bucket
  446. * where the last write to it was sequential with the current write, and
  447. * failing that we look for a bucket that was last used by the same task.
  448. *
  449. * The ideas is if you've got multiple tasks pulling data into the cache at the
  450. * same time, you'll get better cache utilization if you try to segregate their
  451. * data and preserve locality.
  452. *
  453. * For example, dirty sectors of flash only volume is not reclaimable, if their
  454. * dirty sectors mixed with dirty sectors of cached device, such buckets will
  455. * be marked as dirty and won't be reclaimed, though the dirty data of cached
  456. * device have been written back to backend device.
  457. *
  458. * And say you've starting Firefox at the same time you're copying a
  459. * bunch of files. Firefox will likely end up being fairly hot and stay in the
  460. * cache awhile, but the data you copied might not be; if you wrote all that
  461. * data to the same buckets it'd get invalidated at the same time.
  462. *
  463. * Both of those tasks will be doing fairly random IO so we can't rely on
  464. * detecting sequential IO to segregate their data, but going off of the task
  465. * should be a sane heuristic.
  466. */
  467. static struct open_bucket *pick_data_bucket(struct cache_set *c,
  468. const struct bkey *search,
  469. unsigned int write_point,
  470. struct bkey *alloc)
  471. {
  472. struct open_bucket *ret, *ret_task = NULL;
  473. list_for_each_entry_reverse(ret, &c->data_buckets, list)
  474. if (UUID_FLASH_ONLY(&c->uuids[KEY_INODE(&ret->key)]) !=
  475. UUID_FLASH_ONLY(&c->uuids[KEY_INODE(search)]))
  476. continue;
  477. else if (!bkey_cmp(&ret->key, search))
  478. goto found;
  479. else if (ret->last_write_point == write_point)
  480. ret_task = ret;
  481. ret = ret_task ?: list_first_entry(&c->data_buckets,
  482. struct open_bucket, list);
  483. found:
  484. if (!ret->sectors_free && KEY_PTRS(alloc)) {
  485. ret->sectors_free = c->cache->sb.bucket_size;
  486. bkey_copy(&ret->key, alloc);
  487. bkey_init(alloc);
  488. }
  489. if (!ret->sectors_free)
  490. ret = NULL;
  491. return ret;
  492. }
  493. /*
  494. * Allocates some space in the cache to write to, and k to point to the newly
  495. * allocated space, and updates KEY_SIZE(k) and KEY_OFFSET(k) (to point to the
  496. * end of the newly allocated space).
  497. *
  498. * May allocate fewer sectors than @sectors, KEY_SIZE(k) indicates how many
  499. * sectors were actually allocated.
  500. *
  501. * If s->writeback is true, will not fail.
  502. */
  503. bool bch_alloc_sectors(struct cache_set *c,
  504. struct bkey *k,
  505. unsigned int sectors,
  506. unsigned int write_point,
  507. unsigned int write_prio,
  508. bool wait)
  509. {
  510. struct open_bucket *b;
  511. BKEY_PADDED(key) alloc;
  512. unsigned int i;
  513. /*
  514. * We might have to allocate a new bucket, which we can't do with a
  515. * spinlock held. So if we have to allocate, we drop the lock, allocate
  516. * and then retry. KEY_PTRS() indicates whether alloc points to
  517. * allocated bucket(s).
  518. */
  519. bkey_init(&alloc.key);
  520. spin_lock(&c->data_bucket_lock);
  521. while (!(b = pick_data_bucket(c, k, write_point, &alloc.key))) {
  522. unsigned int watermark = write_prio
  523. ? RESERVE_MOVINGGC
  524. : RESERVE_NONE;
  525. spin_unlock(&c->data_bucket_lock);
  526. if (bch_bucket_alloc_set(c, watermark, &alloc.key, wait))
  527. return false;
  528. spin_lock(&c->data_bucket_lock);
  529. }
  530. /*
  531. * If we had to allocate, we might race and not need to allocate the
  532. * second time we call pick_data_bucket(). If we allocated a bucket but
  533. * didn't use it, drop the refcount bch_bucket_alloc_set() took:
  534. */
  535. if (KEY_PTRS(&alloc.key))
  536. bkey_put(c, &alloc.key);
  537. for (i = 0; i < KEY_PTRS(&b->key); i++)
  538. EBUG_ON(ptr_stale(c, &b->key, i));
  539. /* Set up the pointer to the space we're allocating: */
  540. for (i = 0; i < KEY_PTRS(&b->key); i++)
  541. k->ptr[i] = b->key.ptr[i];
  542. sectors = min(sectors, b->sectors_free);
  543. SET_KEY_OFFSET(k, KEY_OFFSET(k) + sectors);
  544. SET_KEY_SIZE(k, sectors);
  545. SET_KEY_PTRS(k, KEY_PTRS(&b->key));
  546. /*
  547. * Move b to the end of the lru, and keep track of what this bucket was
  548. * last used for:
  549. */
  550. list_move_tail(&b->list, &c->data_buckets);
  551. bkey_copy_key(&b->key, k);
  552. b->last_write_point = write_point;
  553. b->sectors_free -= sectors;
  554. for (i = 0; i < KEY_PTRS(&b->key); i++) {
  555. SET_PTR_OFFSET(&b->key, i, PTR_OFFSET(&b->key, i) + sectors);
  556. atomic_long_add(sectors,
  557. &PTR_CACHE(c, &b->key, i)->sectors_written);
  558. }
  559. if (b->sectors_free < c->cache->sb.block_size)
  560. b->sectors_free = 0;
  561. /*
  562. * k takes refcounts on the buckets it points to until it's inserted
  563. * into the btree, but if we're done with this bucket we just transfer
  564. * get_data_bucket()'s refcount.
  565. */
  566. if (b->sectors_free)
  567. for (i = 0; i < KEY_PTRS(&b->key); i++)
  568. atomic_inc(&PTR_BUCKET(c, &b->key, i)->pin);
  569. spin_unlock(&c->data_bucket_lock);
  570. return true;
  571. }
  572. /* Init */
  573. void bch_open_buckets_free(struct cache_set *c)
  574. {
  575. struct open_bucket *b;
  576. while (!list_empty(&c->data_buckets)) {
  577. b = list_first_entry(&c->data_buckets,
  578. struct open_bucket, list);
  579. list_del(&b->list);
  580. kfree(b);
  581. }
  582. }
  583. int bch_open_buckets_alloc(struct cache_set *c)
  584. {
  585. int i;
  586. spin_lock_init(&c->data_bucket_lock);
  587. for (i = 0; i < MAX_OPEN_BUCKETS; i++) {
  588. struct open_bucket *b = kzalloc(sizeof(*b), GFP_KERNEL);
  589. if (!b)
  590. return -ENOMEM;
  591. list_add(&b->list, &c->data_buckets);
  592. }
  593. return 0;
  594. }
  595. int bch_cache_allocator_start(struct cache *ca)
  596. {
  597. struct task_struct *k = kthread_run(bch_allocator_thread,
  598. ca, "bcache_allocator");
  599. if (IS_ERR(k))
  600. return PTR_ERR(k);
  601. ca->alloc_thread = k;
  602. return 0;
  603. }