btree.c 57 KB

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