btree.c 54 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420
  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 <linux/slab.h>
  27. #include <linux/bitops.h>
  28. #include <linux/freezer.h>
  29. #include <linux/hash.h>
  30. #include <linux/kthread.h>
  31. #include <linux/prefetch.h>
  32. #include <linux/random.h>
  33. #include <linux/rcupdate.h>
  34. #include <trace/events/bcache.h>
  35. /*
  36. * Todo:
  37. * register_bcache: Return errors out to userspace correctly
  38. *
  39. * Writeback: don't undirty key until after a cache flush
  40. *
  41. * Create an iterator for key pointers
  42. *
  43. * On btree write error, mark bucket such that it won't be freed from the cache
  44. *
  45. * Journalling:
  46. * Check for bad keys in replay
  47. * Propagate barriers
  48. * Refcount journal entries in journal_replay
  49. *
  50. * Garbage collection:
  51. * Finish incremental gc
  52. * Gc should free old UUIDs, data for invalid UUIDs
  53. *
  54. * Provide a way to list backing device UUIDs we have data cached for, and
  55. * probably how long it's been since we've seen them, and a way to invalidate
  56. * dirty data for devices that will never be attached again
  57. *
  58. * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so
  59. * that based on that and how much dirty data we have we can keep writeback
  60. * from being starved
  61. *
  62. * Add a tracepoint or somesuch to watch for writeback starvation
  63. *
  64. * When btree depth > 1 and splitting an interior node, we have to make sure
  65. * alloc_bucket() cannot fail. This should be true but is not completely
  66. * obvious.
  67. *
  68. * Make sure all allocations get charged to the root cgroup
  69. *
  70. * Plugging?
  71. *
  72. * If data write is less than hard sector size of ssd, round up offset in open
  73. * bucket to the next whole sector
  74. *
  75. * Also lookup by cgroup in get_open_bucket()
  76. *
  77. * Superblock needs to be fleshed out for multiple cache devices
  78. *
  79. * Add a sysfs tunable for the number of writeback IOs in flight
  80. *
  81. * Add a sysfs tunable for the number of open data buckets
  82. *
  83. * IO tracking: Can we track when one process is doing io on behalf of another?
  84. * IO tracking: Don't use just an average, weigh more recent stuff higher
  85. *
  86. * Test module load/unload
  87. */
  88. #define MAX_NEED_GC 64
  89. #define MAX_SAVE_PRIO 72
  90. #define PTR_DIRTY_BIT (((uint64_t) 1 << 36))
  91. #define PTR_HASH(c, k) \
  92. (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0))
  93. static struct workqueue_struct *btree_io_wq;
  94. #define insert_lock(s, b) ((b)->level <= (s)->lock)
  95. /*
  96. * These macros are for recursing down the btree - they handle the details of
  97. * locking and looking up nodes in the cache for you. They're best treated as
  98. * mere syntax when reading code that uses them.
  99. *
  100. * op->lock determines whether we take a read or a write lock at a given depth.
  101. * If you've got a read lock and find that you need a write lock (i.e. you're
  102. * going to have to split), set op->lock and return -EINTR; btree_root() will
  103. * call you again and you'll have the correct lock.
  104. */
  105. /**
  106. * btree - recurse down the btree on a specified key
  107. * @fn: function to call, which will be passed the child node
  108. * @key: key to recurse on
  109. * @b: parent btree node
  110. * @op: pointer to struct btree_op
  111. */
  112. #define btree(fn, key, b, op, ...) \
  113. ({ \
  114. int _r, l = (b)->level - 1; \
  115. bool _w = l <= (op)->lock; \
  116. struct btree *_child = bch_btree_node_get((b)->c, key, l, _w); \
  117. if (!IS_ERR(_child)) { \
  118. _child->parent = (b); \
  119. _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \
  120. rw_unlock(_w, _child); \
  121. } else \
  122. _r = PTR_ERR(_child); \
  123. _r; \
  124. })
  125. /**
  126. * btree_root - call a function on the root of the btree
  127. * @fn: function to call, which will be passed the child node
  128. * @c: cache set
  129. * @op: pointer to struct btree_op
  130. */
  131. #define btree_root(fn, c, op, ...) \
  132. ({ \
  133. int _r = -EINTR; \
  134. do { \
  135. struct btree *_b = (c)->root; \
  136. bool _w = insert_lock(op, _b); \
  137. rw_lock(_w, _b, _b->level); \
  138. if (_b == (c)->root && \
  139. _w == insert_lock(op, _b)) { \
  140. _b->parent = NULL; \
  141. _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \
  142. } \
  143. rw_unlock(_w, _b); \
  144. if (_r == -EINTR) \
  145. schedule(); \
  146. bch_cannibalize_unlock(c); \
  147. if (_r == -ENOSPC) { \
  148. wait_event((c)->try_wait, \
  149. !(c)->try_harder); \
  150. _r = -EINTR; \
  151. } \
  152. } while (_r == -EINTR); \
  153. \
  154. finish_wait(&(c)->bucket_wait, &(op)->wait); \
  155. _r; \
  156. })
  157. static inline struct bset *write_block(struct btree *b)
  158. {
  159. return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c);
  160. }
  161. /* Btree key manipulation */
  162. void bkey_put(struct cache_set *c, struct bkey *k)
  163. {
  164. unsigned i;
  165. for (i = 0; i < KEY_PTRS(k); i++)
  166. if (ptr_available(c, k, i))
  167. atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin);
  168. }
  169. /* Btree IO */
  170. static uint64_t btree_csum_set(struct btree *b, struct bset *i)
  171. {
  172. uint64_t crc = b->key.ptr[0];
  173. void *data = (void *) i + 8, *end = bset_bkey_last(i);
  174. crc = bch_crc64_update(crc, data, end - data);
  175. return crc ^ 0xffffffffffffffffULL;
  176. }
  177. void bch_btree_node_read_done(struct btree *b)
  178. {
  179. const char *err = "bad btree header";
  180. struct bset *i = btree_bset_first(b);
  181. struct btree_iter *iter;
  182. iter = mempool_alloc(b->c->fill_iter, GFP_NOWAIT);
  183. iter->size = b->c->sb.bucket_size / b->c->sb.block_size;
  184. iter->used = 0;
  185. #ifdef CONFIG_BCACHE_DEBUG
  186. iter->b = &b->keys;
  187. #endif
  188. if (!i->seq)
  189. goto err;
  190. for (;
  191. b->written < btree_blocks(b) && i->seq == b->keys.set[0].data->seq;
  192. i = write_block(b)) {
  193. err = "unsupported bset version";
  194. if (i->version > BCACHE_BSET_VERSION)
  195. goto err;
  196. err = "bad btree header";
  197. if (b->written + set_blocks(i, block_bytes(b->c)) >
  198. btree_blocks(b))
  199. goto err;
  200. err = "bad magic";
  201. if (i->magic != bset_magic(&b->c->sb))
  202. goto err;
  203. err = "bad checksum";
  204. switch (i->version) {
  205. case 0:
  206. if (i->csum != csum_set(i))
  207. goto err;
  208. break;
  209. case BCACHE_BSET_VERSION:
  210. if (i->csum != btree_csum_set(b, i))
  211. goto err;
  212. break;
  213. }
  214. err = "empty set";
  215. if (i != b->keys.set[0].data && !i->keys)
  216. goto err;
  217. bch_btree_iter_push(iter, i->start, bset_bkey_last(i));
  218. b->written += set_blocks(i, block_bytes(b->c));
  219. }
  220. err = "corrupted btree";
  221. for (i = write_block(b);
  222. bset_sector_offset(&b->keys, i) < KEY_SIZE(&b->key);
  223. i = ((void *) i) + block_bytes(b->c))
  224. if (i->seq == b->keys.set[0].data->seq)
  225. goto err;
  226. bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort);
  227. i = b->keys.set[0].data;
  228. err = "short btree key";
  229. if (b->keys.set[0].size &&
  230. bkey_cmp(&b->key, &b->keys.set[0].end) < 0)
  231. goto err;
  232. if (b->written < btree_blocks(b))
  233. bch_bset_init_next(&b->keys, write_block(b),
  234. bset_magic(&b->c->sb));
  235. out:
  236. mempool_free(iter, b->c->fill_iter);
  237. return;
  238. err:
  239. set_btree_node_io_error(b);
  240. bch_cache_set_error(b->c, "%s at bucket %zu, block %u, %u keys",
  241. err, PTR_BUCKET_NR(b->c, &b->key, 0),
  242. bset_block_offset(b, i), i->keys);
  243. goto out;
  244. }
  245. static void btree_node_read_endio(struct bio *bio, int error)
  246. {
  247. struct closure *cl = bio->bi_private;
  248. closure_put(cl);
  249. }
  250. static void bch_btree_node_read(struct btree *b)
  251. {
  252. uint64_t start_time = local_clock();
  253. struct closure cl;
  254. struct bio *bio;
  255. trace_bcache_btree_read(b);
  256. closure_init_stack(&cl);
  257. bio = bch_bbio_alloc(b->c);
  258. bio->bi_rw = REQ_META|READ_SYNC;
  259. bio->bi_iter.bi_size = KEY_SIZE(&b->key) << 9;
  260. bio->bi_end_io = btree_node_read_endio;
  261. bio->bi_private = &cl;
  262. bch_bio_map(bio, b->keys.set[0].data);
  263. bch_submit_bbio(bio, b->c, &b->key, 0);
  264. closure_sync(&cl);
  265. if (!test_bit(BIO_UPTODATE, &bio->bi_flags))
  266. set_btree_node_io_error(b);
  267. bch_bbio_free(bio, b->c);
  268. if (btree_node_io_error(b))
  269. goto err;
  270. bch_btree_node_read_done(b);
  271. bch_time_stats_update(&b->c->btree_read_time, start_time);
  272. return;
  273. err:
  274. bch_cache_set_error(b->c, "io error reading bucket %zu",
  275. PTR_BUCKET_NR(b->c, &b->key, 0));
  276. }
  277. static void btree_complete_write(struct btree *b, struct btree_write *w)
  278. {
  279. if (w->prio_blocked &&
  280. !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked))
  281. wake_up_allocators(b->c);
  282. if (w->journal) {
  283. atomic_dec_bug(w->journal);
  284. __closure_wake_up(&b->c->journal.wait);
  285. }
  286. w->prio_blocked = 0;
  287. w->journal = NULL;
  288. }
  289. static void btree_node_write_unlock(struct closure *cl)
  290. {
  291. struct btree *b = container_of(cl, struct btree, io);
  292. up(&b->io_mutex);
  293. }
  294. static void __btree_node_write_done(struct closure *cl)
  295. {
  296. struct btree *b = container_of(cl, struct btree, io);
  297. struct btree_write *w = btree_prev_write(b);
  298. bch_bbio_free(b->bio, b->c);
  299. b->bio = NULL;
  300. btree_complete_write(b, w);
  301. if (btree_node_dirty(b))
  302. queue_delayed_work(btree_io_wq, &b->work,
  303. msecs_to_jiffies(30000));
  304. closure_return_with_destructor(cl, btree_node_write_unlock);
  305. }
  306. static void btree_node_write_done(struct closure *cl)
  307. {
  308. struct btree *b = container_of(cl, struct btree, io);
  309. struct bio_vec *bv;
  310. int n;
  311. bio_for_each_segment_all(bv, b->bio, n)
  312. __free_page(bv->bv_page);
  313. __btree_node_write_done(cl);
  314. }
  315. static void btree_node_write_endio(struct bio *bio, int error)
  316. {
  317. struct closure *cl = bio->bi_private;
  318. struct btree *b = container_of(cl, struct btree, io);
  319. if (error)
  320. set_btree_node_io_error(b);
  321. bch_bbio_count_io_errors(b->c, bio, error, "writing btree");
  322. closure_put(cl);
  323. }
  324. static void do_btree_node_write(struct btree *b)
  325. {
  326. struct closure *cl = &b->io;
  327. struct bset *i = btree_bset_last(b);
  328. BKEY_PADDED(key) k;
  329. i->version = BCACHE_BSET_VERSION;
  330. i->csum = btree_csum_set(b, i);
  331. BUG_ON(b->bio);
  332. b->bio = bch_bbio_alloc(b->c);
  333. b->bio->bi_end_io = btree_node_write_endio;
  334. b->bio->bi_private = cl;
  335. b->bio->bi_rw = REQ_META|WRITE_SYNC|REQ_FUA;
  336. b->bio->bi_iter.bi_size = roundup(set_bytes(i), block_bytes(b->c));
  337. bch_bio_map(b->bio, i);
  338. /*
  339. * If we're appending to a leaf node, we don't technically need FUA -
  340. * this write just needs to be persisted before the next journal write,
  341. * which will be marked FLUSH|FUA.
  342. *
  343. * Similarly if we're writing a new btree root - the pointer is going to
  344. * be in the next journal entry.
  345. *
  346. * But if we're writing a new btree node (that isn't a root) or
  347. * appending to a non leaf btree node, we need either FUA or a flush
  348. * when we write the parent with the new pointer. FUA is cheaper than a
  349. * flush, and writes appending to leaf nodes aren't blocking anything so
  350. * just make all btree node writes FUA to keep things sane.
  351. */
  352. bkey_copy(&k.key, &b->key);
  353. SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) +
  354. bset_sector_offset(&b->keys, i));
  355. if (!bio_alloc_pages(b->bio, GFP_NOIO)) {
  356. int j;
  357. struct bio_vec *bv;
  358. void *base = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1));
  359. bio_for_each_segment_all(bv, b->bio, j)
  360. memcpy(page_address(bv->bv_page),
  361. base + j * PAGE_SIZE, PAGE_SIZE);
  362. bch_submit_bbio(b->bio, b->c, &k.key, 0);
  363. continue_at(cl, btree_node_write_done, NULL);
  364. } else {
  365. b->bio->bi_vcnt = 0;
  366. bch_bio_map(b->bio, i);
  367. bch_submit_bbio(b->bio, b->c, &k.key, 0);
  368. closure_sync(cl);
  369. continue_at_nobarrier(cl, __btree_node_write_done, NULL);
  370. }
  371. }
  372. void bch_btree_node_write(struct btree *b, struct closure *parent)
  373. {
  374. struct bset *i = btree_bset_last(b);
  375. trace_bcache_btree_write(b);
  376. BUG_ON(current->bio_list);
  377. BUG_ON(b->written >= btree_blocks(b));
  378. BUG_ON(b->written && !i->keys);
  379. BUG_ON(btree_bset_first(b)->seq != i->seq);
  380. bch_check_keys(&b->keys, "writing");
  381. cancel_delayed_work(&b->work);
  382. /* If caller isn't waiting for write, parent refcount is cache set */
  383. down(&b->io_mutex);
  384. closure_init(&b->io, parent ?: &b->c->cl);
  385. clear_bit(BTREE_NODE_dirty, &b->flags);
  386. change_bit(BTREE_NODE_write_idx, &b->flags);
  387. do_btree_node_write(b);
  388. atomic_long_add(set_blocks(i, block_bytes(b->c)) * b->c->sb.block_size,
  389. &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written);
  390. b->written += set_blocks(i, block_bytes(b->c));
  391. /* If not a leaf node, always sort */
  392. if (b->level && b->keys.nsets)
  393. bch_btree_sort(&b->keys, &b->c->sort);
  394. else
  395. bch_btree_sort_lazy(&b->keys, &b->c->sort);
  396. /*
  397. * do verify if there was more than one set initially (i.e. we did a
  398. * sort) and we sorted down to a single set:
  399. */
  400. if (i != b->keys.set->data && !b->keys.nsets)
  401. bch_btree_verify(b);
  402. if (b->written < btree_blocks(b))
  403. bch_bset_init_next(&b->keys, write_block(b),
  404. bset_magic(&b->c->sb));
  405. }
  406. static void bch_btree_node_write_sync(struct btree *b)
  407. {
  408. struct closure cl;
  409. closure_init_stack(&cl);
  410. bch_btree_node_write(b, &cl);
  411. closure_sync(&cl);
  412. }
  413. static void btree_node_write_work(struct work_struct *w)
  414. {
  415. struct btree *b = container_of(to_delayed_work(w), struct btree, work);
  416. rw_lock(true, b, b->level);
  417. if (btree_node_dirty(b))
  418. bch_btree_node_write(b, NULL);
  419. rw_unlock(true, b);
  420. }
  421. static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref)
  422. {
  423. struct bset *i = btree_bset_last(b);
  424. struct btree_write *w = btree_current_write(b);
  425. BUG_ON(!b->written);
  426. BUG_ON(!i->keys);
  427. if (!btree_node_dirty(b))
  428. queue_delayed_work(btree_io_wq, &b->work, 30 * HZ);
  429. set_btree_node_dirty(b);
  430. if (journal_ref) {
  431. if (w->journal &&
  432. journal_pin_cmp(b->c, w->journal, journal_ref)) {
  433. atomic_dec_bug(w->journal);
  434. w->journal = NULL;
  435. }
  436. if (!w->journal) {
  437. w->journal = journal_ref;
  438. atomic_inc(w->journal);
  439. }
  440. }
  441. /* Force write if set is too big */
  442. if (set_bytes(i) > PAGE_SIZE - 48 &&
  443. !current->bio_list)
  444. bch_btree_node_write(b, NULL);
  445. }
  446. /*
  447. * Btree in memory cache - allocation/freeing
  448. * mca -> memory cache
  449. */
  450. #define mca_reserve(c) (((c->root && c->root->level) \
  451. ? c->root->level : 1) * 8 + 16)
  452. #define mca_can_free(c) \
  453. max_t(int, 0, c->bucket_cache_used - mca_reserve(c))
  454. static void mca_data_free(struct btree *b)
  455. {
  456. BUG_ON(b->io_mutex.count != 1);
  457. bch_btree_keys_free(&b->keys);
  458. b->c->bucket_cache_used--;
  459. list_move(&b->list, &b->c->btree_cache_freed);
  460. }
  461. static void mca_bucket_free(struct btree *b)
  462. {
  463. BUG_ON(btree_node_dirty(b));
  464. b->key.ptr[0] = 0;
  465. hlist_del_init_rcu(&b->hash);
  466. list_move(&b->list, &b->c->btree_cache_freeable);
  467. }
  468. static unsigned btree_order(struct bkey *k)
  469. {
  470. return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1);
  471. }
  472. static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp)
  473. {
  474. if (!bch_btree_keys_alloc(&b->keys,
  475. max_t(unsigned,
  476. ilog2(b->c->btree_pages),
  477. btree_order(k)),
  478. gfp)) {
  479. b->c->bucket_cache_used++;
  480. list_move(&b->list, &b->c->btree_cache);
  481. } else {
  482. list_move(&b->list, &b->c->btree_cache_freed);
  483. }
  484. }
  485. static struct btree *mca_bucket_alloc(struct cache_set *c,
  486. struct bkey *k, gfp_t gfp)
  487. {
  488. struct btree *b = kzalloc(sizeof(struct btree), gfp);
  489. if (!b)
  490. return NULL;
  491. init_rwsem(&b->lock);
  492. lockdep_set_novalidate_class(&b->lock);
  493. INIT_LIST_HEAD(&b->list);
  494. INIT_DELAYED_WORK(&b->work, btree_node_write_work);
  495. b->c = c;
  496. sema_init(&b->io_mutex, 1);
  497. mca_data_alloc(b, k, gfp);
  498. return b;
  499. }
  500. static int mca_reap(struct btree *b, unsigned min_order, bool flush)
  501. {
  502. struct closure cl;
  503. closure_init_stack(&cl);
  504. lockdep_assert_held(&b->c->bucket_lock);
  505. if (!down_write_trylock(&b->lock))
  506. return -ENOMEM;
  507. BUG_ON(btree_node_dirty(b) && !b->keys.set[0].data);
  508. if (b->keys.page_order < min_order)
  509. goto out_unlock;
  510. if (!flush) {
  511. if (btree_node_dirty(b))
  512. goto out_unlock;
  513. if (down_trylock(&b->io_mutex))
  514. goto out_unlock;
  515. up(&b->io_mutex);
  516. }
  517. if (btree_node_dirty(b))
  518. bch_btree_node_write_sync(b);
  519. /* wait for any in flight btree write */
  520. down(&b->io_mutex);
  521. up(&b->io_mutex);
  522. return 0;
  523. out_unlock:
  524. rw_unlock(true, b);
  525. return -ENOMEM;
  526. }
  527. static unsigned long bch_mca_scan(struct shrinker *shrink,
  528. struct shrink_control *sc)
  529. {
  530. struct cache_set *c = container_of(shrink, struct cache_set, shrink);
  531. struct btree *b, *t;
  532. unsigned long i, nr = sc->nr_to_scan;
  533. unsigned long freed = 0;
  534. if (c->shrinker_disabled)
  535. return SHRINK_STOP;
  536. if (c->try_harder)
  537. return SHRINK_STOP;
  538. /* Return -1 if we can't do anything right now */
  539. if (sc->gfp_mask & __GFP_IO)
  540. mutex_lock(&c->bucket_lock);
  541. else if (!mutex_trylock(&c->bucket_lock))
  542. return -1;
  543. /*
  544. * It's _really_ critical that we don't free too many btree nodes - we
  545. * have to always leave ourselves a reserve. The reserve is how we
  546. * guarantee that allocating memory for a new btree node can always
  547. * succeed, so that inserting keys into the btree can always succeed and
  548. * IO can always make forward progress:
  549. */
  550. nr /= c->btree_pages;
  551. nr = min_t(unsigned long, nr, mca_can_free(c));
  552. i = 0;
  553. list_for_each_entry_safe(b, t, &c->btree_cache_freeable, list) {
  554. if (freed >= nr)
  555. break;
  556. if (++i > 3 &&
  557. !mca_reap(b, 0, false)) {
  558. mca_data_free(b);
  559. rw_unlock(true, b);
  560. freed++;
  561. }
  562. }
  563. for (i = 0; (nr--) && i < c->bucket_cache_used; i++) {
  564. if (list_empty(&c->btree_cache))
  565. goto out;
  566. b = list_first_entry(&c->btree_cache, struct btree, list);
  567. list_rotate_left(&c->btree_cache);
  568. if (!b->accessed &&
  569. !mca_reap(b, 0, false)) {
  570. mca_bucket_free(b);
  571. mca_data_free(b);
  572. rw_unlock(true, b);
  573. freed++;
  574. } else
  575. b->accessed = 0;
  576. }
  577. out:
  578. mutex_unlock(&c->bucket_lock);
  579. return freed;
  580. }
  581. static unsigned long bch_mca_count(struct shrinker *shrink,
  582. struct shrink_control *sc)
  583. {
  584. struct cache_set *c = container_of(shrink, struct cache_set, shrink);
  585. if (c->shrinker_disabled)
  586. return 0;
  587. if (c->try_harder)
  588. return 0;
  589. return mca_can_free(c) * c->btree_pages;
  590. }
  591. void bch_btree_cache_free(struct cache_set *c)
  592. {
  593. struct btree *b;
  594. struct closure cl;
  595. closure_init_stack(&cl);
  596. if (c->shrink.list.next)
  597. unregister_shrinker(&c->shrink);
  598. mutex_lock(&c->bucket_lock);
  599. #ifdef CONFIG_BCACHE_DEBUG
  600. if (c->verify_data)
  601. list_move(&c->verify_data->list, &c->btree_cache);
  602. free_pages((unsigned long) c->verify_ondisk, ilog2(bucket_pages(c)));
  603. #endif
  604. list_splice(&c->btree_cache_freeable,
  605. &c->btree_cache);
  606. while (!list_empty(&c->btree_cache)) {
  607. b = list_first_entry(&c->btree_cache, struct btree, list);
  608. if (btree_node_dirty(b))
  609. btree_complete_write(b, btree_current_write(b));
  610. clear_bit(BTREE_NODE_dirty, &b->flags);
  611. mca_data_free(b);
  612. }
  613. while (!list_empty(&c->btree_cache_freed)) {
  614. b = list_first_entry(&c->btree_cache_freed,
  615. struct btree, list);
  616. list_del(&b->list);
  617. cancel_delayed_work_sync(&b->work);
  618. kfree(b);
  619. }
  620. mutex_unlock(&c->bucket_lock);
  621. }
  622. int bch_btree_cache_alloc(struct cache_set *c)
  623. {
  624. unsigned i;
  625. for (i = 0; i < mca_reserve(c); i++)
  626. if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL))
  627. return -ENOMEM;
  628. list_splice_init(&c->btree_cache,
  629. &c->btree_cache_freeable);
  630. #ifdef CONFIG_BCACHE_DEBUG
  631. mutex_init(&c->verify_lock);
  632. c->verify_ondisk = (void *)
  633. __get_free_pages(GFP_KERNEL, ilog2(bucket_pages(c)));
  634. c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL);
  635. if (c->verify_data &&
  636. c->verify_data->keys.set->data)
  637. list_del_init(&c->verify_data->list);
  638. else
  639. c->verify_data = NULL;
  640. #endif
  641. c->shrink.count_objects = bch_mca_count;
  642. c->shrink.scan_objects = bch_mca_scan;
  643. c->shrink.seeks = 4;
  644. c->shrink.batch = c->btree_pages * 2;
  645. register_shrinker(&c->shrink);
  646. return 0;
  647. }
  648. /* Btree in memory cache - hash table */
  649. static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k)
  650. {
  651. return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)];
  652. }
  653. static struct btree *mca_find(struct cache_set *c, struct bkey *k)
  654. {
  655. struct btree *b;
  656. rcu_read_lock();
  657. hlist_for_each_entry_rcu(b, mca_hash(c, k), hash)
  658. if (PTR_HASH(c, &b->key) == PTR_HASH(c, k))
  659. goto out;
  660. b = NULL;
  661. out:
  662. rcu_read_unlock();
  663. return b;
  664. }
  665. static struct btree *mca_cannibalize(struct cache_set *c, struct bkey *k)
  666. {
  667. struct btree *b;
  668. trace_bcache_btree_cache_cannibalize(c);
  669. if (!c->try_harder) {
  670. c->try_harder = current;
  671. c->try_harder_start = local_clock();
  672. } else if (c->try_harder != current)
  673. return ERR_PTR(-ENOSPC);
  674. list_for_each_entry_reverse(b, &c->btree_cache, list)
  675. if (!mca_reap(b, btree_order(k), false))
  676. return b;
  677. list_for_each_entry_reverse(b, &c->btree_cache, list)
  678. if (!mca_reap(b, btree_order(k), true))
  679. return b;
  680. return ERR_PTR(-ENOMEM);
  681. }
  682. /*
  683. * We can only have one thread cannibalizing other cached btree nodes at a time,
  684. * or we'll deadlock. We use an open coded mutex to ensure that, which a
  685. * cannibalize_bucket() will take. This means every time we unlock the root of
  686. * the btree, we need to release this lock if we have it held.
  687. */
  688. static void bch_cannibalize_unlock(struct cache_set *c)
  689. {
  690. if (c->try_harder == current) {
  691. bch_time_stats_update(&c->try_harder_time, c->try_harder_start);
  692. c->try_harder = NULL;
  693. wake_up(&c->try_wait);
  694. }
  695. }
  696. static struct btree *mca_alloc(struct cache_set *c, struct bkey *k, int level)
  697. {
  698. struct btree *b;
  699. BUG_ON(current->bio_list);
  700. lockdep_assert_held(&c->bucket_lock);
  701. if (mca_find(c, k))
  702. return NULL;
  703. /* btree_free() doesn't free memory; it sticks the node on the end of
  704. * the list. Check if there's any freed nodes there:
  705. */
  706. list_for_each_entry(b, &c->btree_cache_freeable, list)
  707. if (!mca_reap(b, btree_order(k), false))
  708. goto out;
  709. /* We never free struct btree itself, just the memory that holds the on
  710. * disk node. Check the freed list before allocating a new one:
  711. */
  712. list_for_each_entry(b, &c->btree_cache_freed, list)
  713. if (!mca_reap(b, 0, false)) {
  714. mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO);
  715. if (!b->keys.set[0].data)
  716. goto err;
  717. else
  718. goto out;
  719. }
  720. b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO);
  721. if (!b)
  722. goto err;
  723. BUG_ON(!down_write_trylock(&b->lock));
  724. if (!b->keys.set->data)
  725. goto err;
  726. out:
  727. BUG_ON(b->io_mutex.count != 1);
  728. bkey_copy(&b->key, k);
  729. list_move(&b->list, &c->btree_cache);
  730. hlist_del_init_rcu(&b->hash);
  731. hlist_add_head_rcu(&b->hash, mca_hash(c, k));
  732. lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_);
  733. b->parent = (void *) ~0UL;
  734. b->flags = 0;
  735. b->written = 0;
  736. b->level = level;
  737. if (!b->level)
  738. bch_btree_keys_init(&b->keys, &bch_extent_keys_ops,
  739. &b->c->expensive_debug_checks);
  740. else
  741. bch_btree_keys_init(&b->keys, &bch_btree_keys_ops,
  742. &b->c->expensive_debug_checks);
  743. return b;
  744. err:
  745. if (b)
  746. rw_unlock(true, b);
  747. b = mca_cannibalize(c, k);
  748. if (!IS_ERR(b))
  749. goto out;
  750. return b;
  751. }
  752. /**
  753. * bch_btree_node_get - find a btree node in the cache and lock it, reading it
  754. * in from disk if necessary.
  755. *
  756. * If IO is necessary and running under generic_make_request, returns -EAGAIN.
  757. *
  758. * The btree node will have either a read or a write lock held, depending on
  759. * level and op->lock.
  760. */
  761. struct btree *bch_btree_node_get(struct cache_set *c, struct bkey *k,
  762. int level, bool write)
  763. {
  764. int i = 0;
  765. struct btree *b;
  766. BUG_ON(level < 0);
  767. retry:
  768. b = mca_find(c, k);
  769. if (!b) {
  770. if (current->bio_list)
  771. return ERR_PTR(-EAGAIN);
  772. mutex_lock(&c->bucket_lock);
  773. b = mca_alloc(c, k, level);
  774. mutex_unlock(&c->bucket_lock);
  775. if (!b)
  776. goto retry;
  777. if (IS_ERR(b))
  778. return b;
  779. bch_btree_node_read(b);
  780. if (!write)
  781. downgrade_write(&b->lock);
  782. } else {
  783. rw_lock(write, b, level);
  784. if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) {
  785. rw_unlock(write, b);
  786. goto retry;
  787. }
  788. BUG_ON(b->level != level);
  789. }
  790. b->accessed = 1;
  791. for (; i <= b->keys.nsets && b->keys.set[i].size; i++) {
  792. prefetch(b->keys.set[i].tree);
  793. prefetch(b->keys.set[i].data);
  794. }
  795. for (; i <= b->keys.nsets; i++)
  796. prefetch(b->keys.set[i].data);
  797. if (btree_node_io_error(b)) {
  798. rw_unlock(write, b);
  799. return ERR_PTR(-EIO);
  800. }
  801. BUG_ON(!b->written);
  802. return b;
  803. }
  804. static void btree_node_prefetch(struct cache_set *c, struct bkey *k, int level)
  805. {
  806. struct btree *b;
  807. mutex_lock(&c->bucket_lock);
  808. b = mca_alloc(c, k, level);
  809. mutex_unlock(&c->bucket_lock);
  810. if (!IS_ERR_OR_NULL(b)) {
  811. bch_btree_node_read(b);
  812. rw_unlock(true, b);
  813. }
  814. }
  815. /* Btree alloc */
  816. static void btree_node_free(struct btree *b)
  817. {
  818. unsigned i;
  819. trace_bcache_btree_node_free(b);
  820. BUG_ON(b == b->c->root);
  821. if (btree_node_dirty(b))
  822. btree_complete_write(b, btree_current_write(b));
  823. clear_bit(BTREE_NODE_dirty, &b->flags);
  824. cancel_delayed_work(&b->work);
  825. mutex_lock(&b->c->bucket_lock);
  826. for (i = 0; i < KEY_PTRS(&b->key); i++) {
  827. BUG_ON(atomic_read(&PTR_BUCKET(b->c, &b->key, i)->pin));
  828. bch_inc_gen(PTR_CACHE(b->c, &b->key, i),
  829. PTR_BUCKET(b->c, &b->key, i));
  830. }
  831. bch_bucket_free(b->c, &b->key);
  832. mca_bucket_free(b);
  833. mutex_unlock(&b->c->bucket_lock);
  834. }
  835. struct btree *bch_btree_node_alloc(struct cache_set *c, int level, bool wait)
  836. {
  837. BKEY_PADDED(key) k;
  838. struct btree *b = ERR_PTR(-EAGAIN);
  839. mutex_lock(&c->bucket_lock);
  840. retry:
  841. if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, 1, wait))
  842. goto err;
  843. bkey_put(c, &k.key);
  844. SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS);
  845. b = mca_alloc(c, &k.key, level);
  846. if (IS_ERR(b))
  847. goto err_free;
  848. if (!b) {
  849. cache_bug(c,
  850. "Tried to allocate bucket that was in btree cache");
  851. goto retry;
  852. }
  853. b->accessed = 1;
  854. bch_bset_init_next(&b->keys, b->keys.set->data, bset_magic(&b->c->sb));
  855. mutex_unlock(&c->bucket_lock);
  856. trace_bcache_btree_node_alloc(b);
  857. return b;
  858. err_free:
  859. bch_bucket_free(c, &k.key);
  860. err:
  861. mutex_unlock(&c->bucket_lock);
  862. trace_bcache_btree_node_alloc_fail(b);
  863. return b;
  864. }
  865. static struct btree *btree_node_alloc_replacement(struct btree *b, bool wait)
  866. {
  867. struct btree *n = bch_btree_node_alloc(b->c, b->level, wait);
  868. if (!IS_ERR_OR_NULL(n)) {
  869. bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort);
  870. bkey_copy_key(&n->key, &b->key);
  871. }
  872. return n;
  873. }
  874. static void make_btree_freeing_key(struct btree *b, struct bkey *k)
  875. {
  876. unsigned i;
  877. bkey_copy(k, &b->key);
  878. bkey_copy_key(k, &ZERO_KEY);
  879. for (i = 0; i < KEY_PTRS(k); i++) {
  880. uint8_t g = PTR_BUCKET(b->c, k, i)->gen + 1;
  881. SET_PTR_GEN(k, i, g);
  882. }
  883. atomic_inc(&b->c->prio_blocked);
  884. }
  885. static int btree_check_reserve(struct btree *b, struct btree_op *op)
  886. {
  887. struct cache_set *c = b->c;
  888. struct cache *ca;
  889. unsigned i, reserve = c->root->level * 2 + 1;
  890. int ret = 0;
  891. mutex_lock(&c->bucket_lock);
  892. for_each_cache(ca, c, i)
  893. if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) {
  894. if (op)
  895. prepare_to_wait(&c->bucket_wait, &op->wait,
  896. TASK_UNINTERRUPTIBLE);
  897. ret = -EINTR;
  898. break;
  899. }
  900. mutex_unlock(&c->bucket_lock);
  901. return ret;
  902. }
  903. /* Garbage collection */
  904. uint8_t __bch_btree_mark_key(struct cache_set *c, int level, struct bkey *k)
  905. {
  906. uint8_t stale = 0;
  907. unsigned i;
  908. struct bucket *g;
  909. /*
  910. * ptr_invalid() can't return true for the keys that mark btree nodes as
  911. * freed, but since ptr_bad() returns true we'll never actually use them
  912. * for anything and thus we don't want mark their pointers here
  913. */
  914. if (!bkey_cmp(k, &ZERO_KEY))
  915. return stale;
  916. for (i = 0; i < KEY_PTRS(k); i++) {
  917. if (!ptr_available(c, k, i))
  918. continue;
  919. g = PTR_BUCKET(c, k, i);
  920. if (gen_after(g->gc_gen, PTR_GEN(k, i)))
  921. g->gc_gen = PTR_GEN(k, i);
  922. if (ptr_stale(c, k, i)) {
  923. stale = max(stale, ptr_stale(c, k, i));
  924. continue;
  925. }
  926. cache_bug_on(GC_MARK(g) &&
  927. (GC_MARK(g) == GC_MARK_METADATA) != (level != 0),
  928. c, "inconsistent ptrs: mark = %llu, level = %i",
  929. GC_MARK(g), level);
  930. if (level)
  931. SET_GC_MARK(g, GC_MARK_METADATA);
  932. else if (KEY_DIRTY(k))
  933. SET_GC_MARK(g, GC_MARK_DIRTY);
  934. /* guard against overflow */
  935. SET_GC_SECTORS_USED(g, min_t(unsigned,
  936. GC_SECTORS_USED(g) + KEY_SIZE(k),
  937. MAX_GC_SECTORS_USED));
  938. BUG_ON(!GC_SECTORS_USED(g));
  939. }
  940. return stale;
  941. }
  942. #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k)
  943. static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc)
  944. {
  945. uint8_t stale = 0;
  946. unsigned keys = 0, good_keys = 0;
  947. struct bkey *k;
  948. struct btree_iter iter;
  949. struct bset_tree *t;
  950. gc->nodes++;
  951. for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) {
  952. stale = max(stale, btree_mark_key(b, k));
  953. keys++;
  954. if (bch_ptr_bad(&b->keys, k))
  955. continue;
  956. gc->key_bytes += bkey_u64s(k);
  957. gc->nkeys++;
  958. good_keys++;
  959. gc->data += KEY_SIZE(k);
  960. }
  961. for (t = b->keys.set; t <= &b->keys.set[b->keys.nsets]; t++)
  962. btree_bug_on(t->size &&
  963. bset_written(&b->keys, t) &&
  964. bkey_cmp(&b->key, &t->end) < 0,
  965. b, "found short btree key in gc");
  966. if (b->c->gc_always_rewrite)
  967. return true;
  968. if (stale > 10)
  969. return true;
  970. if ((keys - good_keys) * 2 > keys)
  971. return true;
  972. return false;
  973. }
  974. #define GC_MERGE_NODES 4U
  975. struct gc_merge_info {
  976. struct btree *b;
  977. unsigned keys;
  978. };
  979. static int bch_btree_insert_node(struct btree *, struct btree_op *,
  980. struct keylist *, atomic_t *, struct bkey *);
  981. static int btree_gc_coalesce(struct btree *b, struct btree_op *op,
  982. struct keylist *keylist, struct gc_stat *gc,
  983. struct gc_merge_info *r)
  984. {
  985. unsigned i, nodes = 0, keys = 0, blocks;
  986. struct btree *new_nodes[GC_MERGE_NODES];
  987. struct closure cl;
  988. struct bkey *k;
  989. memset(new_nodes, 0, sizeof(new_nodes));
  990. closure_init_stack(&cl);
  991. while (nodes < GC_MERGE_NODES && !IS_ERR_OR_NULL(r[nodes].b))
  992. keys += r[nodes++].keys;
  993. blocks = btree_default_blocks(b->c) * 2 / 3;
  994. if (nodes < 2 ||
  995. __set_blocks(b->keys.set[0].data, keys,
  996. block_bytes(b->c)) > blocks * (nodes - 1))
  997. return 0;
  998. for (i = 0; i < nodes; i++) {
  999. new_nodes[i] = btree_node_alloc_replacement(r[i].b, false);
  1000. if (IS_ERR_OR_NULL(new_nodes[i]))
  1001. goto out_nocoalesce;
  1002. }
  1003. for (i = nodes - 1; i > 0; --i) {
  1004. struct bset *n1 = btree_bset_first(new_nodes[i]);
  1005. struct bset *n2 = btree_bset_first(new_nodes[i - 1]);
  1006. struct bkey *k, *last = NULL;
  1007. keys = 0;
  1008. if (i > 1) {
  1009. for (k = n2->start;
  1010. k < bset_bkey_last(n2);
  1011. k = bkey_next(k)) {
  1012. if (__set_blocks(n1, n1->keys + keys +
  1013. bkey_u64s(k),
  1014. block_bytes(b->c)) > blocks)
  1015. break;
  1016. last = k;
  1017. keys += bkey_u64s(k);
  1018. }
  1019. } else {
  1020. /*
  1021. * Last node we're not getting rid of - we're getting
  1022. * rid of the node at r[0]. Have to try and fit all of
  1023. * the remaining keys into this node; we can't ensure
  1024. * they will always fit due to rounding and variable
  1025. * length keys (shouldn't be possible in practice,
  1026. * though)
  1027. */
  1028. if (__set_blocks(n1, n1->keys + n2->keys,
  1029. block_bytes(b->c)) >
  1030. btree_blocks(new_nodes[i]))
  1031. goto out_nocoalesce;
  1032. keys = n2->keys;
  1033. /* Take the key of the node we're getting rid of */
  1034. last = &r->b->key;
  1035. }
  1036. BUG_ON(__set_blocks(n1, n1->keys + keys, block_bytes(b->c)) >
  1037. btree_blocks(new_nodes[i]));
  1038. if (last)
  1039. bkey_copy_key(&new_nodes[i]->key, last);
  1040. memcpy(bset_bkey_last(n1),
  1041. n2->start,
  1042. (void *) bset_bkey_idx(n2, keys) - (void *) n2->start);
  1043. n1->keys += keys;
  1044. r[i].keys = n1->keys;
  1045. memmove(n2->start,
  1046. bset_bkey_idx(n2, keys),
  1047. (void *) bset_bkey_last(n2) -
  1048. (void *) bset_bkey_idx(n2, keys));
  1049. n2->keys -= keys;
  1050. if (__bch_keylist_realloc(keylist,
  1051. bkey_u64s(&new_nodes[i]->key)))
  1052. goto out_nocoalesce;
  1053. bch_btree_node_write(new_nodes[i], &cl);
  1054. bch_keylist_add(keylist, &new_nodes[i]->key);
  1055. }
  1056. for (i = 0; i < nodes; i++) {
  1057. if (__bch_keylist_realloc(keylist, bkey_u64s(&r[i].b->key)))
  1058. goto out_nocoalesce;
  1059. make_btree_freeing_key(r[i].b, keylist->top);
  1060. bch_keylist_push(keylist);
  1061. }
  1062. /* We emptied out this node */
  1063. BUG_ON(btree_bset_first(new_nodes[0])->keys);
  1064. btree_node_free(new_nodes[0]);
  1065. rw_unlock(true, new_nodes[0]);
  1066. closure_sync(&cl);
  1067. for (i = 0; i < nodes; i++) {
  1068. btree_node_free(r[i].b);
  1069. rw_unlock(true, r[i].b);
  1070. r[i].b = new_nodes[i];
  1071. }
  1072. bch_btree_insert_node(b, op, keylist, NULL, NULL);
  1073. BUG_ON(!bch_keylist_empty(keylist));
  1074. memmove(r, r + 1, sizeof(r[0]) * (nodes - 1));
  1075. r[nodes - 1].b = ERR_PTR(-EINTR);
  1076. trace_bcache_btree_gc_coalesce(nodes);
  1077. gc->nodes--;
  1078. /* Invalidated our iterator */
  1079. return -EINTR;
  1080. out_nocoalesce:
  1081. closure_sync(&cl);
  1082. while ((k = bch_keylist_pop(keylist)))
  1083. if (!bkey_cmp(k, &ZERO_KEY))
  1084. atomic_dec(&b->c->prio_blocked);
  1085. for (i = 0; i < nodes; i++)
  1086. if (!IS_ERR_OR_NULL(new_nodes[i])) {
  1087. btree_node_free(new_nodes[i]);
  1088. rw_unlock(true, new_nodes[i]);
  1089. }
  1090. return 0;
  1091. }
  1092. static unsigned btree_gc_count_keys(struct btree *b)
  1093. {
  1094. struct bkey *k;
  1095. struct btree_iter iter;
  1096. unsigned ret = 0;
  1097. for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad)
  1098. ret += bkey_u64s(k);
  1099. return ret;
  1100. }
  1101. static int btree_gc_recurse(struct btree *b, struct btree_op *op,
  1102. struct closure *writes, struct gc_stat *gc)
  1103. {
  1104. unsigned i;
  1105. int ret = 0;
  1106. bool should_rewrite;
  1107. struct btree *n;
  1108. struct bkey *k;
  1109. struct keylist keys;
  1110. struct btree_iter iter;
  1111. struct gc_merge_info r[GC_MERGE_NODES];
  1112. struct gc_merge_info *last = r + GC_MERGE_NODES - 1;
  1113. bch_keylist_init(&keys);
  1114. bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done);
  1115. for (i = 0; i < GC_MERGE_NODES; i++)
  1116. r[i].b = ERR_PTR(-EINTR);
  1117. while (1) {
  1118. k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad);
  1119. if (k) {
  1120. r->b = bch_btree_node_get(b->c, k, b->level - 1, true);
  1121. if (IS_ERR(r->b)) {
  1122. ret = PTR_ERR(r->b);
  1123. break;
  1124. }
  1125. r->keys = btree_gc_count_keys(r->b);
  1126. ret = btree_gc_coalesce(b, op, &keys, gc, r);
  1127. if (ret)
  1128. break;
  1129. }
  1130. if (!last->b)
  1131. break;
  1132. if (!IS_ERR(last->b)) {
  1133. should_rewrite = btree_gc_mark_node(last->b, gc);
  1134. if (should_rewrite &&
  1135. !btree_check_reserve(b, NULL)) {
  1136. n = btree_node_alloc_replacement(last->b,
  1137. false);
  1138. if (!IS_ERR_OR_NULL(n)) {
  1139. bch_btree_node_write_sync(n);
  1140. bch_keylist_add(&keys, &n->key);
  1141. make_btree_freeing_key(last->b,
  1142. keys.top);
  1143. bch_keylist_push(&keys);
  1144. btree_node_free(last->b);
  1145. bch_btree_insert_node(b, op, &keys,
  1146. NULL, NULL);
  1147. BUG_ON(!bch_keylist_empty(&keys));
  1148. rw_unlock(true, last->b);
  1149. last->b = n;
  1150. /* Invalidated our iterator */
  1151. ret = -EINTR;
  1152. break;
  1153. }
  1154. }
  1155. if (last->b->level) {
  1156. ret = btree_gc_recurse(last->b, op, writes, gc);
  1157. if (ret)
  1158. break;
  1159. }
  1160. bkey_copy_key(&b->c->gc_done, &last->b->key);
  1161. /*
  1162. * Must flush leaf nodes before gc ends, since replace
  1163. * operations aren't journalled
  1164. */
  1165. if (btree_node_dirty(last->b))
  1166. bch_btree_node_write(last->b, writes);
  1167. rw_unlock(true, last->b);
  1168. }
  1169. memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1));
  1170. r->b = NULL;
  1171. if (need_resched()) {
  1172. ret = -EAGAIN;
  1173. break;
  1174. }
  1175. }
  1176. for (i = 0; i < GC_MERGE_NODES; i++)
  1177. if (!IS_ERR_OR_NULL(r[i].b)) {
  1178. if (btree_node_dirty(r[i].b))
  1179. bch_btree_node_write(r[i].b, writes);
  1180. rw_unlock(true, r[i].b);
  1181. }
  1182. bch_keylist_free(&keys);
  1183. return ret;
  1184. }
  1185. static int bch_btree_gc_root(struct btree *b, struct btree_op *op,
  1186. struct closure *writes, struct gc_stat *gc)
  1187. {
  1188. struct btree *n = NULL;
  1189. int ret = 0;
  1190. bool should_rewrite;
  1191. should_rewrite = btree_gc_mark_node(b, gc);
  1192. if (should_rewrite) {
  1193. n = btree_node_alloc_replacement(b, false);
  1194. if (!IS_ERR_OR_NULL(n)) {
  1195. bch_btree_node_write_sync(n);
  1196. bch_btree_set_root(n);
  1197. btree_node_free(b);
  1198. rw_unlock(true, n);
  1199. return -EINTR;
  1200. }
  1201. }
  1202. if (b->level) {
  1203. ret = btree_gc_recurse(b, op, writes, gc);
  1204. if (ret)
  1205. return ret;
  1206. }
  1207. bkey_copy_key(&b->c->gc_done, &b->key);
  1208. return ret;
  1209. }
  1210. static void btree_gc_start(struct cache_set *c)
  1211. {
  1212. struct cache *ca;
  1213. struct bucket *b;
  1214. unsigned i;
  1215. if (!c->gc_mark_valid)
  1216. return;
  1217. mutex_lock(&c->bucket_lock);
  1218. c->gc_mark_valid = 0;
  1219. c->gc_done = ZERO_KEY;
  1220. for_each_cache(ca, c, i)
  1221. for_each_bucket(b, ca) {
  1222. b->gc_gen = b->gen;
  1223. if (!atomic_read(&b->pin)) {
  1224. SET_GC_MARK(b, GC_MARK_RECLAIMABLE);
  1225. SET_GC_SECTORS_USED(b, 0);
  1226. }
  1227. }
  1228. mutex_unlock(&c->bucket_lock);
  1229. }
  1230. size_t bch_btree_gc_finish(struct cache_set *c)
  1231. {
  1232. size_t available = 0;
  1233. struct bucket *b;
  1234. struct cache *ca;
  1235. unsigned i;
  1236. mutex_lock(&c->bucket_lock);
  1237. set_gc_sectors(c);
  1238. c->gc_mark_valid = 1;
  1239. c->need_gc = 0;
  1240. if (c->root)
  1241. for (i = 0; i < KEY_PTRS(&c->root->key); i++)
  1242. SET_GC_MARK(PTR_BUCKET(c, &c->root->key, i),
  1243. GC_MARK_METADATA);
  1244. for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++)
  1245. SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i),
  1246. GC_MARK_METADATA);
  1247. /* don't reclaim buckets to which writeback keys point */
  1248. rcu_read_lock();
  1249. for (i = 0; i < c->nr_uuids; i++) {
  1250. struct bcache_device *d = c->devices[i];
  1251. struct cached_dev *dc;
  1252. struct keybuf_key *w, *n;
  1253. unsigned j;
  1254. if (!d || UUID_FLASH_ONLY(&c->uuids[i]))
  1255. continue;
  1256. dc = container_of(d, struct cached_dev, disk);
  1257. spin_lock(&dc->writeback_keys.lock);
  1258. rbtree_postorder_for_each_entry_safe(w, n,
  1259. &dc->writeback_keys.keys, node)
  1260. for (j = 0; j < KEY_PTRS(&w->key); j++)
  1261. SET_GC_MARK(PTR_BUCKET(c, &w->key, j),
  1262. GC_MARK_DIRTY);
  1263. spin_unlock(&dc->writeback_keys.lock);
  1264. }
  1265. rcu_read_unlock();
  1266. for_each_cache(ca, c, i) {
  1267. uint64_t *i;
  1268. ca->invalidate_needs_gc = 0;
  1269. for (i = ca->sb.d; i < ca->sb.d + ca->sb.keys; i++)
  1270. SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA);
  1271. for (i = ca->prio_buckets;
  1272. i < ca->prio_buckets + prio_buckets(ca) * 2; i++)
  1273. SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA);
  1274. for_each_bucket(b, ca) {
  1275. b->last_gc = b->gc_gen;
  1276. c->need_gc = max(c->need_gc, bucket_gc_gen(b));
  1277. if (!atomic_read(&b->pin) &&
  1278. GC_MARK(b) == GC_MARK_RECLAIMABLE) {
  1279. available++;
  1280. if (!GC_SECTORS_USED(b))
  1281. bch_bucket_add_unused(ca, b);
  1282. }
  1283. }
  1284. }
  1285. mutex_unlock(&c->bucket_lock);
  1286. return available;
  1287. }
  1288. static void bch_btree_gc(struct cache_set *c)
  1289. {
  1290. int ret;
  1291. unsigned long available;
  1292. struct gc_stat stats;
  1293. struct closure writes;
  1294. struct btree_op op;
  1295. uint64_t start_time = local_clock();
  1296. trace_bcache_gc_start(c);
  1297. memset(&stats, 0, sizeof(struct gc_stat));
  1298. closure_init_stack(&writes);
  1299. bch_btree_op_init(&op, SHRT_MAX);
  1300. btree_gc_start(c);
  1301. do {
  1302. ret = btree_root(gc_root, c, &op, &writes, &stats);
  1303. closure_sync(&writes);
  1304. if (ret && ret != -EAGAIN)
  1305. pr_warn("gc failed!");
  1306. } while (ret);
  1307. available = bch_btree_gc_finish(c);
  1308. wake_up_allocators(c);
  1309. bch_time_stats_update(&c->btree_gc_time, start_time);
  1310. stats.key_bytes *= sizeof(uint64_t);
  1311. stats.data <<= 9;
  1312. stats.in_use = (c->nbuckets - available) * 100 / c->nbuckets;
  1313. memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat));
  1314. trace_bcache_gc_end(c);
  1315. bch_moving_gc(c);
  1316. }
  1317. static int bch_gc_thread(void *arg)
  1318. {
  1319. struct cache_set *c = arg;
  1320. struct cache *ca;
  1321. unsigned i;
  1322. while (1) {
  1323. again:
  1324. bch_btree_gc(c);
  1325. set_current_state(TASK_INTERRUPTIBLE);
  1326. if (kthread_should_stop())
  1327. break;
  1328. mutex_lock(&c->bucket_lock);
  1329. for_each_cache(ca, c, i)
  1330. if (ca->invalidate_needs_gc) {
  1331. mutex_unlock(&c->bucket_lock);
  1332. set_current_state(TASK_RUNNING);
  1333. goto again;
  1334. }
  1335. mutex_unlock(&c->bucket_lock);
  1336. try_to_freeze();
  1337. schedule();
  1338. }
  1339. return 0;
  1340. }
  1341. int bch_gc_thread_start(struct cache_set *c)
  1342. {
  1343. c->gc_thread = kthread_create(bch_gc_thread, c, "bcache_gc");
  1344. if (IS_ERR(c->gc_thread))
  1345. return PTR_ERR(c->gc_thread);
  1346. set_task_state(c->gc_thread, TASK_INTERRUPTIBLE);
  1347. return 0;
  1348. }
  1349. /* Initial partial gc */
  1350. static int bch_btree_check_recurse(struct btree *b, struct btree_op *op,
  1351. unsigned long **seen)
  1352. {
  1353. int ret = 0;
  1354. unsigned i;
  1355. struct bkey *k, *p = NULL;
  1356. struct bucket *g;
  1357. struct btree_iter iter;
  1358. for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) {
  1359. for (i = 0; i < KEY_PTRS(k); i++) {
  1360. if (!ptr_available(b->c, k, i))
  1361. continue;
  1362. g = PTR_BUCKET(b->c, k, i);
  1363. if (!__test_and_set_bit(PTR_BUCKET_NR(b->c, k, i),
  1364. seen[PTR_DEV(k, i)]) ||
  1365. !ptr_stale(b->c, k, i)) {
  1366. g->gen = PTR_GEN(k, i);
  1367. if (b->level)
  1368. g->prio = BTREE_PRIO;
  1369. else if (g->prio == BTREE_PRIO)
  1370. g->prio = INITIAL_PRIO;
  1371. }
  1372. }
  1373. btree_mark_key(b, k);
  1374. }
  1375. if (b->level) {
  1376. bch_btree_iter_init(&b->keys, &iter, NULL);
  1377. do {
  1378. k = bch_btree_iter_next_filter(&iter, &b->keys,
  1379. bch_ptr_bad);
  1380. if (k)
  1381. btree_node_prefetch(b->c, k, b->level - 1);
  1382. if (p)
  1383. ret = btree(check_recurse, p, b, op, seen);
  1384. p = k;
  1385. } while (p && !ret);
  1386. }
  1387. return 0;
  1388. }
  1389. int bch_btree_check(struct cache_set *c)
  1390. {
  1391. int ret = -ENOMEM;
  1392. unsigned i;
  1393. unsigned long *seen[MAX_CACHES_PER_SET];
  1394. struct btree_op op;
  1395. memset(seen, 0, sizeof(seen));
  1396. bch_btree_op_init(&op, SHRT_MAX);
  1397. for (i = 0; c->cache[i]; i++) {
  1398. size_t n = DIV_ROUND_UP(c->cache[i]->sb.nbuckets, 8);
  1399. seen[i] = kmalloc(n, GFP_KERNEL);
  1400. if (!seen[i])
  1401. goto err;
  1402. /* Disables the seen array until prio_read() uses it too */
  1403. memset(seen[i], 0xFF, n);
  1404. }
  1405. ret = btree_root(check_recurse, c, &op, seen);
  1406. err:
  1407. for (i = 0; i < MAX_CACHES_PER_SET; i++)
  1408. kfree(seen[i]);
  1409. return ret;
  1410. }
  1411. /* Btree insertion */
  1412. static bool btree_insert_key(struct btree *b, struct bkey *k,
  1413. struct bkey *replace_key)
  1414. {
  1415. unsigned status;
  1416. BUG_ON(bkey_cmp(k, &b->key) > 0);
  1417. status = bch_btree_insert_key(&b->keys, k, replace_key);
  1418. if (status != BTREE_INSERT_STATUS_NO_INSERT) {
  1419. bch_check_keys(&b->keys, "%u for %s", status,
  1420. replace_key ? "replace" : "insert");
  1421. trace_bcache_btree_insert_key(b, k, replace_key != NULL,
  1422. status);
  1423. return true;
  1424. } else
  1425. return false;
  1426. }
  1427. static size_t insert_u64s_remaining(struct btree *b)
  1428. {
  1429. long ret = bch_btree_keys_u64s_remaining(&b->keys);
  1430. /*
  1431. * Might land in the middle of an existing extent and have to split it
  1432. */
  1433. if (b->keys.ops->is_extents)
  1434. ret -= KEY_MAX_U64S;
  1435. return max(ret, 0L);
  1436. }
  1437. static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op,
  1438. struct keylist *insert_keys,
  1439. struct bkey *replace_key)
  1440. {
  1441. bool ret = false;
  1442. int oldsize = bch_count_data(&b->keys);
  1443. while (!bch_keylist_empty(insert_keys)) {
  1444. struct bkey *k = insert_keys->keys;
  1445. if (bkey_u64s(k) > insert_u64s_remaining(b))
  1446. break;
  1447. if (bkey_cmp(k, &b->key) <= 0) {
  1448. if (!b->level)
  1449. bkey_put(b->c, k);
  1450. ret |= btree_insert_key(b, k, replace_key);
  1451. bch_keylist_pop_front(insert_keys);
  1452. } else if (bkey_cmp(&START_KEY(k), &b->key) < 0) {
  1453. BKEY_PADDED(key) temp;
  1454. bkey_copy(&temp.key, insert_keys->keys);
  1455. bch_cut_back(&b->key, &temp.key);
  1456. bch_cut_front(&b->key, insert_keys->keys);
  1457. ret |= btree_insert_key(b, &temp.key, replace_key);
  1458. break;
  1459. } else {
  1460. break;
  1461. }
  1462. }
  1463. if (!ret)
  1464. op->insert_collision = true;
  1465. BUG_ON(!bch_keylist_empty(insert_keys) && b->level);
  1466. BUG_ON(bch_count_data(&b->keys) < oldsize);
  1467. return ret;
  1468. }
  1469. static int btree_split(struct btree *b, struct btree_op *op,
  1470. struct keylist *insert_keys,
  1471. struct bkey *replace_key)
  1472. {
  1473. bool split;
  1474. struct btree *n1, *n2 = NULL, *n3 = NULL;
  1475. uint64_t start_time = local_clock();
  1476. struct closure cl;
  1477. struct keylist parent_keys;
  1478. closure_init_stack(&cl);
  1479. bch_keylist_init(&parent_keys);
  1480. if (!b->level &&
  1481. btree_check_reserve(b, op))
  1482. return -EINTR;
  1483. n1 = btree_node_alloc_replacement(b, true);
  1484. if (IS_ERR(n1))
  1485. goto err;
  1486. split = set_blocks(btree_bset_first(n1),
  1487. block_bytes(n1->c)) > (btree_blocks(b) * 4) / 5;
  1488. if (split) {
  1489. unsigned keys = 0;
  1490. trace_bcache_btree_node_split(b, btree_bset_first(n1)->keys);
  1491. n2 = bch_btree_node_alloc(b->c, b->level, true);
  1492. if (IS_ERR(n2))
  1493. goto err_free1;
  1494. if (!b->parent) {
  1495. n3 = bch_btree_node_alloc(b->c, b->level + 1, true);
  1496. if (IS_ERR(n3))
  1497. goto err_free2;
  1498. }
  1499. bch_btree_insert_keys(n1, op, insert_keys, replace_key);
  1500. /*
  1501. * Has to be a linear search because we don't have an auxiliary
  1502. * search tree yet
  1503. */
  1504. while (keys < (btree_bset_first(n1)->keys * 3) / 5)
  1505. keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1),
  1506. keys));
  1507. bkey_copy_key(&n1->key,
  1508. bset_bkey_idx(btree_bset_first(n1), keys));
  1509. keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), keys));
  1510. btree_bset_first(n2)->keys = btree_bset_first(n1)->keys - keys;
  1511. btree_bset_first(n1)->keys = keys;
  1512. memcpy(btree_bset_first(n2)->start,
  1513. bset_bkey_last(btree_bset_first(n1)),
  1514. btree_bset_first(n2)->keys * sizeof(uint64_t));
  1515. bkey_copy_key(&n2->key, &b->key);
  1516. bch_keylist_add(&parent_keys, &n2->key);
  1517. bch_btree_node_write(n2, &cl);
  1518. rw_unlock(true, n2);
  1519. } else {
  1520. trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys);
  1521. bch_btree_insert_keys(n1, op, insert_keys, replace_key);
  1522. }
  1523. bch_keylist_add(&parent_keys, &n1->key);
  1524. bch_btree_node_write(n1, &cl);
  1525. if (n3) {
  1526. /* Depth increases, make a new root */
  1527. bkey_copy_key(&n3->key, &MAX_KEY);
  1528. bch_btree_insert_keys(n3, op, &parent_keys, NULL);
  1529. bch_btree_node_write(n3, &cl);
  1530. closure_sync(&cl);
  1531. bch_btree_set_root(n3);
  1532. rw_unlock(true, n3);
  1533. btree_node_free(b);
  1534. } else if (!b->parent) {
  1535. /* Root filled up but didn't need to be split */
  1536. closure_sync(&cl);
  1537. bch_btree_set_root(n1);
  1538. btree_node_free(b);
  1539. } else {
  1540. /* Split a non root node */
  1541. closure_sync(&cl);
  1542. make_btree_freeing_key(b, parent_keys.top);
  1543. bch_keylist_push(&parent_keys);
  1544. btree_node_free(b);
  1545. bch_btree_insert_node(b->parent, op, &parent_keys, NULL, NULL);
  1546. BUG_ON(!bch_keylist_empty(&parent_keys));
  1547. }
  1548. rw_unlock(true, n1);
  1549. bch_time_stats_update(&b->c->btree_split_time, start_time);
  1550. return 0;
  1551. err_free2:
  1552. bkey_put(b->c, &n2->key);
  1553. btree_node_free(n2);
  1554. rw_unlock(true, n2);
  1555. err_free1:
  1556. bkey_put(b->c, &n1->key);
  1557. btree_node_free(n1);
  1558. rw_unlock(true, n1);
  1559. err:
  1560. WARN(1, "bcache: btree split failed");
  1561. if (n3 == ERR_PTR(-EAGAIN) ||
  1562. n2 == ERR_PTR(-EAGAIN) ||
  1563. n1 == ERR_PTR(-EAGAIN))
  1564. return -EAGAIN;
  1565. return -ENOMEM;
  1566. }
  1567. static int bch_btree_insert_node(struct btree *b, struct btree_op *op,
  1568. struct keylist *insert_keys,
  1569. atomic_t *journal_ref,
  1570. struct bkey *replace_key)
  1571. {
  1572. BUG_ON(b->level && replace_key);
  1573. if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) {
  1574. if (current->bio_list) {
  1575. op->lock = b->c->root->level + 1;
  1576. return -EAGAIN;
  1577. } else if (op->lock <= b->c->root->level) {
  1578. op->lock = b->c->root->level + 1;
  1579. return -EINTR;
  1580. } else {
  1581. /* Invalidated all iterators */
  1582. int ret = btree_split(b, op, insert_keys, replace_key);
  1583. return bch_keylist_empty(insert_keys) ?
  1584. 0 : ret ?: -EINTR;
  1585. }
  1586. } else {
  1587. BUG_ON(write_block(b) != btree_bset_last(b));
  1588. if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) {
  1589. if (!b->level)
  1590. bch_btree_leaf_dirty(b, journal_ref);
  1591. else
  1592. bch_btree_node_write_sync(b);
  1593. }
  1594. return 0;
  1595. }
  1596. }
  1597. int bch_btree_insert_check_key(struct btree *b, struct btree_op *op,
  1598. struct bkey *check_key)
  1599. {
  1600. int ret = -EINTR;
  1601. uint64_t btree_ptr = b->key.ptr[0];
  1602. unsigned long seq = b->seq;
  1603. struct keylist insert;
  1604. bool upgrade = op->lock == -1;
  1605. bch_keylist_init(&insert);
  1606. if (upgrade) {
  1607. rw_unlock(false, b);
  1608. rw_lock(true, b, b->level);
  1609. if (b->key.ptr[0] != btree_ptr ||
  1610. b->seq != seq + 1)
  1611. goto out;
  1612. }
  1613. SET_KEY_PTRS(check_key, 1);
  1614. get_random_bytes(&check_key->ptr[0], sizeof(uint64_t));
  1615. SET_PTR_DEV(check_key, 0, PTR_CHECK_DEV);
  1616. bch_keylist_add(&insert, check_key);
  1617. ret = bch_btree_insert_node(b, op, &insert, NULL, NULL);
  1618. BUG_ON(!ret && !bch_keylist_empty(&insert));
  1619. out:
  1620. if (upgrade)
  1621. downgrade_write(&b->lock);
  1622. return ret;
  1623. }
  1624. struct btree_insert_op {
  1625. struct btree_op op;
  1626. struct keylist *keys;
  1627. atomic_t *journal_ref;
  1628. struct bkey *replace_key;
  1629. };
  1630. static int btree_insert_fn(struct btree_op *b_op, struct btree *b)
  1631. {
  1632. struct btree_insert_op *op = container_of(b_op,
  1633. struct btree_insert_op, op);
  1634. int ret = bch_btree_insert_node(b, &op->op, op->keys,
  1635. op->journal_ref, op->replace_key);
  1636. if (ret && !bch_keylist_empty(op->keys))
  1637. return ret;
  1638. else
  1639. return MAP_DONE;
  1640. }
  1641. int bch_btree_insert(struct cache_set *c, struct keylist *keys,
  1642. atomic_t *journal_ref, struct bkey *replace_key)
  1643. {
  1644. struct btree_insert_op op;
  1645. int ret = 0;
  1646. BUG_ON(current->bio_list);
  1647. BUG_ON(bch_keylist_empty(keys));
  1648. bch_btree_op_init(&op.op, 0);
  1649. op.keys = keys;
  1650. op.journal_ref = journal_ref;
  1651. op.replace_key = replace_key;
  1652. while (!ret && !bch_keylist_empty(keys)) {
  1653. op.op.lock = 0;
  1654. ret = bch_btree_map_leaf_nodes(&op.op, c,
  1655. &START_KEY(keys->keys),
  1656. btree_insert_fn);
  1657. }
  1658. if (ret) {
  1659. struct bkey *k;
  1660. pr_err("error %i", ret);
  1661. while ((k = bch_keylist_pop(keys)))
  1662. bkey_put(c, k);
  1663. } else if (op.op.insert_collision)
  1664. ret = -ESRCH;
  1665. return ret;
  1666. }
  1667. void bch_btree_set_root(struct btree *b)
  1668. {
  1669. unsigned i;
  1670. struct closure cl;
  1671. closure_init_stack(&cl);
  1672. trace_bcache_btree_set_root(b);
  1673. BUG_ON(!b->written);
  1674. for (i = 0; i < KEY_PTRS(&b->key); i++)
  1675. BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO);
  1676. mutex_lock(&b->c->bucket_lock);
  1677. list_del_init(&b->list);
  1678. mutex_unlock(&b->c->bucket_lock);
  1679. b->c->root = b;
  1680. bch_journal_meta(b->c, &cl);
  1681. closure_sync(&cl);
  1682. }
  1683. /* Map across nodes or keys */
  1684. static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op,
  1685. struct bkey *from,
  1686. btree_map_nodes_fn *fn, int flags)
  1687. {
  1688. int ret = MAP_CONTINUE;
  1689. if (b->level) {
  1690. struct bkey *k;
  1691. struct btree_iter iter;
  1692. bch_btree_iter_init(&b->keys, &iter, from);
  1693. while ((k = bch_btree_iter_next_filter(&iter, &b->keys,
  1694. bch_ptr_bad))) {
  1695. ret = btree(map_nodes_recurse, k, b,
  1696. op, from, fn, flags);
  1697. from = NULL;
  1698. if (ret != MAP_CONTINUE)
  1699. return ret;
  1700. }
  1701. }
  1702. if (!b->level || flags == MAP_ALL_NODES)
  1703. ret = fn(op, b);
  1704. return ret;
  1705. }
  1706. int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c,
  1707. struct bkey *from, btree_map_nodes_fn *fn, int flags)
  1708. {
  1709. return btree_root(map_nodes_recurse, c, op, from, fn, flags);
  1710. }
  1711. static int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op,
  1712. struct bkey *from, btree_map_keys_fn *fn,
  1713. int flags)
  1714. {
  1715. int ret = MAP_CONTINUE;
  1716. struct bkey *k;
  1717. struct btree_iter iter;
  1718. bch_btree_iter_init(&b->keys, &iter, from);
  1719. while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) {
  1720. ret = !b->level
  1721. ? fn(op, b, k)
  1722. : btree(map_keys_recurse, k, b, op, from, fn, flags);
  1723. from = NULL;
  1724. if (ret != MAP_CONTINUE)
  1725. return ret;
  1726. }
  1727. if (!b->level && (flags & MAP_END_KEY))
  1728. ret = fn(op, b, &KEY(KEY_INODE(&b->key),
  1729. KEY_OFFSET(&b->key), 0));
  1730. return ret;
  1731. }
  1732. int bch_btree_map_keys(struct btree_op *op, struct cache_set *c,
  1733. struct bkey *from, btree_map_keys_fn *fn, int flags)
  1734. {
  1735. return btree_root(map_keys_recurse, c, op, from, fn, flags);
  1736. }
  1737. /* Keybuf code */
  1738. static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r)
  1739. {
  1740. /* Overlapping keys compare equal */
  1741. if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0)
  1742. return -1;
  1743. if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0)
  1744. return 1;
  1745. return 0;
  1746. }
  1747. static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l,
  1748. struct keybuf_key *r)
  1749. {
  1750. return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1);
  1751. }
  1752. struct refill {
  1753. struct btree_op op;
  1754. unsigned nr_found;
  1755. struct keybuf *buf;
  1756. struct bkey *end;
  1757. keybuf_pred_fn *pred;
  1758. };
  1759. static int refill_keybuf_fn(struct btree_op *op, struct btree *b,
  1760. struct bkey *k)
  1761. {
  1762. struct refill *refill = container_of(op, struct refill, op);
  1763. struct keybuf *buf = refill->buf;
  1764. int ret = MAP_CONTINUE;
  1765. if (bkey_cmp(k, refill->end) >= 0) {
  1766. ret = MAP_DONE;
  1767. goto out;
  1768. }
  1769. if (!KEY_SIZE(k)) /* end key */
  1770. goto out;
  1771. if (refill->pred(buf, k)) {
  1772. struct keybuf_key *w;
  1773. spin_lock(&buf->lock);
  1774. w = array_alloc(&buf->freelist);
  1775. if (!w) {
  1776. spin_unlock(&buf->lock);
  1777. return MAP_DONE;
  1778. }
  1779. w->private = NULL;
  1780. bkey_copy(&w->key, k);
  1781. if (RB_INSERT(&buf->keys, w, node, keybuf_cmp))
  1782. array_free(&buf->freelist, w);
  1783. else
  1784. refill->nr_found++;
  1785. if (array_freelist_empty(&buf->freelist))
  1786. ret = MAP_DONE;
  1787. spin_unlock(&buf->lock);
  1788. }
  1789. out:
  1790. buf->last_scanned = *k;
  1791. return ret;
  1792. }
  1793. void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf,
  1794. struct bkey *end, keybuf_pred_fn *pred)
  1795. {
  1796. struct bkey start = buf->last_scanned;
  1797. struct refill refill;
  1798. cond_resched();
  1799. bch_btree_op_init(&refill.op, -1);
  1800. refill.nr_found = 0;
  1801. refill.buf = buf;
  1802. refill.end = end;
  1803. refill.pred = pred;
  1804. bch_btree_map_keys(&refill.op, c, &buf->last_scanned,
  1805. refill_keybuf_fn, MAP_END_KEY);
  1806. trace_bcache_keyscan(refill.nr_found,
  1807. KEY_INODE(&start), KEY_OFFSET(&start),
  1808. KEY_INODE(&buf->last_scanned),
  1809. KEY_OFFSET(&buf->last_scanned));
  1810. spin_lock(&buf->lock);
  1811. if (!RB_EMPTY_ROOT(&buf->keys)) {
  1812. struct keybuf_key *w;
  1813. w = RB_FIRST(&buf->keys, struct keybuf_key, node);
  1814. buf->start = START_KEY(&w->key);
  1815. w = RB_LAST(&buf->keys, struct keybuf_key, node);
  1816. buf->end = w->key;
  1817. } else {
  1818. buf->start = MAX_KEY;
  1819. buf->end = MAX_KEY;
  1820. }
  1821. spin_unlock(&buf->lock);
  1822. }
  1823. static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w)
  1824. {
  1825. rb_erase(&w->node, &buf->keys);
  1826. array_free(&buf->freelist, w);
  1827. }
  1828. void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w)
  1829. {
  1830. spin_lock(&buf->lock);
  1831. __bch_keybuf_del(buf, w);
  1832. spin_unlock(&buf->lock);
  1833. }
  1834. bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start,
  1835. struct bkey *end)
  1836. {
  1837. bool ret = false;
  1838. struct keybuf_key *p, *w, s;
  1839. s.key = *start;
  1840. if (bkey_cmp(end, &buf->start) <= 0 ||
  1841. bkey_cmp(start, &buf->end) >= 0)
  1842. return false;
  1843. spin_lock(&buf->lock);
  1844. w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp);
  1845. while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) {
  1846. p = w;
  1847. w = RB_NEXT(w, node);
  1848. if (p->private)
  1849. ret = true;
  1850. else
  1851. __bch_keybuf_del(buf, p);
  1852. }
  1853. spin_unlock(&buf->lock);
  1854. return ret;
  1855. }
  1856. struct keybuf_key *bch_keybuf_next(struct keybuf *buf)
  1857. {
  1858. struct keybuf_key *w;
  1859. spin_lock(&buf->lock);
  1860. w = RB_FIRST(&buf->keys, struct keybuf_key, node);
  1861. while (w && w->private)
  1862. w = RB_NEXT(w, node);
  1863. if (w)
  1864. w->private = ERR_PTR(-EINTR);
  1865. spin_unlock(&buf->lock);
  1866. return w;
  1867. }
  1868. struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c,
  1869. struct keybuf *buf,
  1870. struct bkey *end,
  1871. keybuf_pred_fn *pred)
  1872. {
  1873. struct keybuf_key *ret;
  1874. while (1) {
  1875. ret = bch_keybuf_next(buf);
  1876. if (ret)
  1877. break;
  1878. if (bkey_cmp(&buf->last_scanned, end) >= 0) {
  1879. pr_debug("scan finished");
  1880. break;
  1881. }
  1882. bch_refill_keybuf(c, buf, end, pred);
  1883. }
  1884. return ret;
  1885. }
  1886. void bch_keybuf_init(struct keybuf *buf)
  1887. {
  1888. buf->last_scanned = MAX_KEY;
  1889. buf->keys = RB_ROOT;
  1890. spin_lock_init(&buf->lock);
  1891. array_allocator_init(&buf->freelist);
  1892. }
  1893. void bch_btree_exit(void)
  1894. {
  1895. if (btree_io_wq)
  1896. destroy_workqueue(btree_io_wq);
  1897. }
  1898. int __init bch_btree_init(void)
  1899. {
  1900. btree_io_wq = create_singlethread_workqueue("bch_btree_io");
  1901. if (!btree_io_wq)
  1902. return -ENOMEM;
  1903. return 0;
  1904. }