gc.c 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * This file is part of UBIFS.
  4. *
  5. * Copyright (C) 2006-2008 Nokia Corporation.
  6. *
  7. * Authors: Adrian Hunter
  8. * Artem Bityutskiy (Битюцкий Артём)
  9. */
  10. /*
  11. * This file implements garbage collection. The procedure for garbage collection
  12. * is different depending on whether a LEB as an index LEB (contains index
  13. * nodes) or not. For non-index LEBs, garbage collection finds a LEB which
  14. * contains a lot of dirty space (obsolete nodes), and copies the non-obsolete
  15. * nodes to the journal, at which point the garbage-collected LEB is free to be
  16. * reused. For index LEBs, garbage collection marks the non-obsolete index nodes
  17. * dirty in the TNC, and after the next commit, the garbage-collected LEB is
  18. * to be reused. Garbage collection will cause the number of dirty index nodes
  19. * to grow, however sufficient space is reserved for the index to ensure the
  20. * commit will never run out of space.
  21. *
  22. * Notes about dead watermark. At current UBIFS implementation we assume that
  23. * LEBs which have less than @c->dead_wm bytes of free + dirty space are full
  24. * and not worth garbage-collecting. The dead watermark is one min. I/O unit
  25. * size, or min. UBIFS node size, depending on what is greater. Indeed, UBIFS
  26. * Garbage Collector has to synchronize the GC head's write buffer before
  27. * returning, so this is about wasting one min. I/O unit. However, UBIFS GC can
  28. * actually reclaim even very small pieces of dirty space by garbage collecting
  29. * enough dirty LEBs, but we do not bother doing this at this implementation.
  30. *
  31. * Notes about dark watermark. The results of GC work depends on how big are
  32. * the UBIFS nodes GC deals with. Large nodes make GC waste more space. Indeed,
  33. * if GC move data from LEB A to LEB B and nodes in LEB A are large, GC would
  34. * have to waste large pieces of free space at the end of LEB B, because nodes
  35. * from LEB A would not fit. And the worst situation is when all nodes are of
  36. * maximum size. So dark watermark is the amount of free + dirty space in LEB
  37. * which are guaranteed to be reclaimable. If LEB has less space, the GC might
  38. * be unable to reclaim it. So, LEBs with free + dirty greater than dark
  39. * watermark are "good" LEBs from GC's point of few. The other LEBs are not so
  40. * good, and GC takes extra care when moving them.
  41. */
  42. #ifndef __UBOOT__
  43. #include <dm/devres.h>
  44. #include <linux/slab.h>
  45. #include <linux/pagemap.h>
  46. #include <linux/list_sort.h>
  47. #endif
  48. #include "ubifs.h"
  49. #ifndef __UBOOT__
  50. /*
  51. * GC may need to move more than one LEB to make progress. The below constants
  52. * define "soft" and "hard" limits on the number of LEBs the garbage collector
  53. * may move.
  54. */
  55. #define SOFT_LEBS_LIMIT 4
  56. #define HARD_LEBS_LIMIT 32
  57. /**
  58. * switch_gc_head - switch the garbage collection journal head.
  59. * @c: UBIFS file-system description object
  60. * @buf: buffer to write
  61. * @len: length of the buffer to write
  62. * @lnum: LEB number written is returned here
  63. * @offs: offset written is returned here
  64. *
  65. * This function switch the GC head to the next LEB which is reserved in
  66. * @c->gc_lnum. Returns %0 in case of success, %-EAGAIN if commit is required,
  67. * and other negative error code in case of failures.
  68. */
  69. static int switch_gc_head(struct ubifs_info *c)
  70. {
  71. int err, gc_lnum = c->gc_lnum;
  72. struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
  73. ubifs_assert(gc_lnum != -1);
  74. dbg_gc("switch GC head from LEB %d:%d to LEB %d (waste %d bytes)",
  75. wbuf->lnum, wbuf->offs + wbuf->used, gc_lnum,
  76. c->leb_size - wbuf->offs - wbuf->used);
  77. err = ubifs_wbuf_sync_nolock(wbuf);
  78. if (err)
  79. return err;
  80. /*
  81. * The GC write-buffer was synchronized, we may safely unmap
  82. * 'c->gc_lnum'.
  83. */
  84. err = ubifs_leb_unmap(c, gc_lnum);
  85. if (err)
  86. return err;
  87. err = ubifs_wbuf_sync_nolock(wbuf);
  88. if (err)
  89. return err;
  90. err = ubifs_add_bud_to_log(c, GCHD, gc_lnum, 0);
  91. if (err)
  92. return err;
  93. c->gc_lnum = -1;
  94. err = ubifs_wbuf_seek_nolock(wbuf, gc_lnum, 0);
  95. return err;
  96. }
  97. /**
  98. * data_nodes_cmp - compare 2 data nodes.
  99. * @priv: UBIFS file-system description object
  100. * @a: first data node
  101. * @a: second data node
  102. *
  103. * This function compares data nodes @a and @b. Returns %1 if @a has greater
  104. * inode or block number, and %-1 otherwise.
  105. */
  106. static int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
  107. {
  108. ino_t inuma, inumb;
  109. struct ubifs_info *c = priv;
  110. struct ubifs_scan_node *sa, *sb;
  111. cond_resched();
  112. if (a == b)
  113. return 0;
  114. sa = list_entry(a, struct ubifs_scan_node, list);
  115. sb = list_entry(b, struct ubifs_scan_node, list);
  116. ubifs_assert(key_type(c, &sa->key) == UBIFS_DATA_KEY);
  117. ubifs_assert(key_type(c, &sb->key) == UBIFS_DATA_KEY);
  118. ubifs_assert(sa->type == UBIFS_DATA_NODE);
  119. ubifs_assert(sb->type == UBIFS_DATA_NODE);
  120. inuma = key_inum(c, &sa->key);
  121. inumb = key_inum(c, &sb->key);
  122. if (inuma == inumb) {
  123. unsigned int blka = key_block(c, &sa->key);
  124. unsigned int blkb = key_block(c, &sb->key);
  125. if (blka <= blkb)
  126. return -1;
  127. } else if (inuma <= inumb)
  128. return -1;
  129. return 1;
  130. }
  131. /*
  132. * nondata_nodes_cmp - compare 2 non-data nodes.
  133. * @priv: UBIFS file-system description object
  134. * @a: first node
  135. * @a: second node
  136. *
  137. * This function compares nodes @a and @b. It makes sure that inode nodes go
  138. * first and sorted by length in descending order. Directory entry nodes go
  139. * after inode nodes and are sorted in ascending hash valuer order.
  140. */
  141. static int nondata_nodes_cmp(void *priv, struct list_head *a,
  142. struct list_head *b)
  143. {
  144. ino_t inuma, inumb;
  145. struct ubifs_info *c = priv;
  146. struct ubifs_scan_node *sa, *sb;
  147. cond_resched();
  148. if (a == b)
  149. return 0;
  150. sa = list_entry(a, struct ubifs_scan_node, list);
  151. sb = list_entry(b, struct ubifs_scan_node, list);
  152. ubifs_assert(key_type(c, &sa->key) != UBIFS_DATA_KEY &&
  153. key_type(c, &sb->key) != UBIFS_DATA_KEY);
  154. ubifs_assert(sa->type != UBIFS_DATA_NODE &&
  155. sb->type != UBIFS_DATA_NODE);
  156. /* Inodes go before directory entries */
  157. if (sa->type == UBIFS_INO_NODE) {
  158. if (sb->type == UBIFS_INO_NODE)
  159. return sb->len - sa->len;
  160. return -1;
  161. }
  162. if (sb->type == UBIFS_INO_NODE)
  163. return 1;
  164. ubifs_assert(key_type(c, &sa->key) == UBIFS_DENT_KEY ||
  165. key_type(c, &sa->key) == UBIFS_XENT_KEY);
  166. ubifs_assert(key_type(c, &sb->key) == UBIFS_DENT_KEY ||
  167. key_type(c, &sb->key) == UBIFS_XENT_KEY);
  168. ubifs_assert(sa->type == UBIFS_DENT_NODE ||
  169. sa->type == UBIFS_XENT_NODE);
  170. ubifs_assert(sb->type == UBIFS_DENT_NODE ||
  171. sb->type == UBIFS_XENT_NODE);
  172. inuma = key_inum(c, &sa->key);
  173. inumb = key_inum(c, &sb->key);
  174. if (inuma == inumb) {
  175. uint32_t hasha = key_hash(c, &sa->key);
  176. uint32_t hashb = key_hash(c, &sb->key);
  177. if (hasha <= hashb)
  178. return -1;
  179. } else if (inuma <= inumb)
  180. return -1;
  181. return 1;
  182. }
  183. /**
  184. * sort_nodes - sort nodes for GC.
  185. * @c: UBIFS file-system description object
  186. * @sleb: describes nodes to sort and contains the result on exit
  187. * @nondata: contains non-data nodes on exit
  188. * @min: minimum node size is returned here
  189. *
  190. * This function sorts the list of inodes to garbage collect. First of all, it
  191. * kills obsolete nodes and separates data and non-data nodes to the
  192. * @sleb->nodes and @nondata lists correspondingly.
  193. *
  194. * Data nodes are then sorted in block number order - this is important for
  195. * bulk-read; data nodes with lower inode number go before data nodes with
  196. * higher inode number, and data nodes with lower block number go before data
  197. * nodes with higher block number;
  198. *
  199. * Non-data nodes are sorted as follows.
  200. * o First go inode nodes - they are sorted in descending length order.
  201. * o Then go directory entry nodes - they are sorted in hash order, which
  202. * should supposedly optimize 'readdir()'. Direntry nodes with lower parent
  203. * inode number go before direntry nodes with higher parent inode number,
  204. * and direntry nodes with lower name hash values go before direntry nodes
  205. * with higher name hash values.
  206. *
  207. * This function returns zero in case of success and a negative error code in
  208. * case of failure.
  209. */
  210. static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
  211. struct list_head *nondata, int *min)
  212. {
  213. int err;
  214. struct ubifs_scan_node *snod, *tmp;
  215. *min = INT_MAX;
  216. /* Separate data nodes and non-data nodes */
  217. list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
  218. ubifs_assert(snod->type == UBIFS_INO_NODE ||
  219. snod->type == UBIFS_DATA_NODE ||
  220. snod->type == UBIFS_DENT_NODE ||
  221. snod->type == UBIFS_XENT_NODE ||
  222. snod->type == UBIFS_TRUN_NODE);
  223. if (snod->type != UBIFS_INO_NODE &&
  224. snod->type != UBIFS_DATA_NODE &&
  225. snod->type != UBIFS_DENT_NODE &&
  226. snod->type != UBIFS_XENT_NODE) {
  227. /* Probably truncation node, zap it */
  228. list_del(&snod->list);
  229. kfree(snod);
  230. continue;
  231. }
  232. ubifs_assert(key_type(c, &snod->key) == UBIFS_DATA_KEY ||
  233. key_type(c, &snod->key) == UBIFS_INO_KEY ||
  234. key_type(c, &snod->key) == UBIFS_DENT_KEY ||
  235. key_type(c, &snod->key) == UBIFS_XENT_KEY);
  236. err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum,
  237. snod->offs, 0);
  238. if (err < 0)
  239. return err;
  240. if (!err) {
  241. /* The node is obsolete, remove it from the list */
  242. list_del(&snod->list);
  243. kfree(snod);
  244. continue;
  245. }
  246. if (snod->len < *min)
  247. *min = snod->len;
  248. if (key_type(c, &snod->key) != UBIFS_DATA_KEY)
  249. list_move_tail(&snod->list, nondata);
  250. }
  251. /* Sort data and non-data nodes */
  252. list_sort(c, &sleb->nodes, &data_nodes_cmp);
  253. list_sort(c, nondata, &nondata_nodes_cmp);
  254. err = dbg_check_data_nodes_order(c, &sleb->nodes);
  255. if (err)
  256. return err;
  257. err = dbg_check_nondata_nodes_order(c, nondata);
  258. if (err)
  259. return err;
  260. return 0;
  261. }
  262. /**
  263. * move_node - move a node.
  264. * @c: UBIFS file-system description object
  265. * @sleb: describes the LEB to move nodes from
  266. * @snod: the mode to move
  267. * @wbuf: write-buffer to move node to
  268. *
  269. * This function moves node @snod to @wbuf, changes TNC correspondingly, and
  270. * destroys @snod. Returns zero in case of success and a negative error code in
  271. * case of failure.
  272. */
  273. static int move_node(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
  274. struct ubifs_scan_node *snod, struct ubifs_wbuf *wbuf)
  275. {
  276. int err, new_lnum = wbuf->lnum, new_offs = wbuf->offs + wbuf->used;
  277. cond_resched();
  278. err = ubifs_wbuf_write_nolock(wbuf, snod->node, snod->len);
  279. if (err)
  280. return err;
  281. err = ubifs_tnc_replace(c, &snod->key, sleb->lnum,
  282. snod->offs, new_lnum, new_offs,
  283. snod->len);
  284. list_del(&snod->list);
  285. kfree(snod);
  286. return err;
  287. }
  288. /**
  289. * move_nodes - move nodes.
  290. * @c: UBIFS file-system description object
  291. * @sleb: describes the LEB to move nodes from
  292. *
  293. * This function moves valid nodes from data LEB described by @sleb to the GC
  294. * journal head. This function returns zero in case of success, %-EAGAIN if
  295. * commit is required, and other negative error codes in case of other
  296. * failures.
  297. */
  298. static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
  299. {
  300. int err, min;
  301. LIST_HEAD(nondata);
  302. struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
  303. if (wbuf->lnum == -1) {
  304. /*
  305. * The GC journal head is not set, because it is the first GC
  306. * invocation since mount.
  307. */
  308. err = switch_gc_head(c);
  309. if (err)
  310. return err;
  311. }
  312. err = sort_nodes(c, sleb, &nondata, &min);
  313. if (err)
  314. goto out;
  315. /* Write nodes to their new location. Use the first-fit strategy */
  316. while (1) {
  317. int avail;
  318. struct ubifs_scan_node *snod, *tmp;
  319. /* Move data nodes */
  320. list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
  321. avail = c->leb_size - wbuf->offs - wbuf->used;
  322. if (snod->len > avail)
  323. /*
  324. * Do not skip data nodes in order to optimize
  325. * bulk-read.
  326. */
  327. break;
  328. err = move_node(c, sleb, snod, wbuf);
  329. if (err)
  330. goto out;
  331. }
  332. /* Move non-data nodes */
  333. list_for_each_entry_safe(snod, tmp, &nondata, list) {
  334. avail = c->leb_size - wbuf->offs - wbuf->used;
  335. if (avail < min)
  336. break;
  337. if (snod->len > avail) {
  338. /*
  339. * Keep going only if this is an inode with
  340. * some data. Otherwise stop and switch the GC
  341. * head. IOW, we assume that data-less inode
  342. * nodes and direntry nodes are roughly of the
  343. * same size.
  344. */
  345. if (key_type(c, &snod->key) == UBIFS_DENT_KEY ||
  346. snod->len == UBIFS_INO_NODE_SZ)
  347. break;
  348. continue;
  349. }
  350. err = move_node(c, sleb, snod, wbuf);
  351. if (err)
  352. goto out;
  353. }
  354. if (list_empty(&sleb->nodes) && list_empty(&nondata))
  355. break;
  356. /*
  357. * Waste the rest of the space in the LEB and switch to the
  358. * next LEB.
  359. */
  360. err = switch_gc_head(c);
  361. if (err)
  362. goto out;
  363. }
  364. return 0;
  365. out:
  366. list_splice_tail(&nondata, &sleb->nodes);
  367. return err;
  368. }
  369. /**
  370. * gc_sync_wbufs - sync write-buffers for GC.
  371. * @c: UBIFS file-system description object
  372. *
  373. * We must guarantee that obsoleting nodes are on flash. Unfortunately they may
  374. * be in a write-buffer instead. That is, a node could be written to a
  375. * write-buffer, obsoleting another node in a LEB that is GC'd. If that LEB is
  376. * erased before the write-buffer is sync'd and then there is an unclean
  377. * unmount, then an existing node is lost. To avoid this, we sync all
  378. * write-buffers.
  379. *
  380. * This function returns %0 on success or a negative error code on failure.
  381. */
  382. static int gc_sync_wbufs(struct ubifs_info *c)
  383. {
  384. int err, i;
  385. for (i = 0; i < c->jhead_cnt; i++) {
  386. if (i == GCHD)
  387. continue;
  388. err = ubifs_wbuf_sync(&c->jheads[i].wbuf);
  389. if (err)
  390. return err;
  391. }
  392. return 0;
  393. }
  394. /**
  395. * ubifs_garbage_collect_leb - garbage-collect a logical eraseblock.
  396. * @c: UBIFS file-system description object
  397. * @lp: describes the LEB to garbage collect
  398. *
  399. * This function garbage-collects an LEB and returns one of the @LEB_FREED,
  400. * @LEB_RETAINED, etc positive codes in case of success, %-EAGAIN if commit is
  401. * required, and other negative error codes in case of failures.
  402. */
  403. int ubifs_garbage_collect_leb(struct ubifs_info *c, struct ubifs_lprops *lp)
  404. {
  405. struct ubifs_scan_leb *sleb;
  406. struct ubifs_scan_node *snod;
  407. struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
  408. int err = 0, lnum = lp->lnum;
  409. ubifs_assert(c->gc_lnum != -1 || wbuf->offs + wbuf->used == 0 ||
  410. c->need_recovery);
  411. ubifs_assert(c->gc_lnum != lnum);
  412. ubifs_assert(wbuf->lnum != lnum);
  413. if (lp->free + lp->dirty == c->leb_size) {
  414. /* Special case - a free LEB */
  415. dbg_gc("LEB %d is free, return it", lp->lnum);
  416. ubifs_assert(!(lp->flags & LPROPS_INDEX));
  417. if (lp->free != c->leb_size) {
  418. /*
  419. * Write buffers must be sync'd before unmapping
  420. * freeable LEBs, because one of them may contain data
  421. * which obsoletes something in 'lp->pnum'.
  422. */
  423. err = gc_sync_wbufs(c);
  424. if (err)
  425. return err;
  426. err = ubifs_change_one_lp(c, lp->lnum, c->leb_size,
  427. 0, 0, 0, 0);
  428. if (err)
  429. return err;
  430. }
  431. err = ubifs_leb_unmap(c, lp->lnum);
  432. if (err)
  433. return err;
  434. if (c->gc_lnum == -1) {
  435. c->gc_lnum = lnum;
  436. return LEB_RETAINED;
  437. }
  438. return LEB_FREED;
  439. }
  440. /*
  441. * We scan the entire LEB even though we only really need to scan up to
  442. * (c->leb_size - lp->free).
  443. */
  444. sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0);
  445. if (IS_ERR(sleb))
  446. return PTR_ERR(sleb);
  447. ubifs_assert(!list_empty(&sleb->nodes));
  448. snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
  449. if (snod->type == UBIFS_IDX_NODE) {
  450. struct ubifs_gced_idx_leb *idx_gc;
  451. dbg_gc("indexing LEB %d (free %d, dirty %d)",
  452. lnum, lp->free, lp->dirty);
  453. list_for_each_entry(snod, &sleb->nodes, list) {
  454. struct ubifs_idx_node *idx = snod->node;
  455. int level = le16_to_cpu(idx->level);
  456. ubifs_assert(snod->type == UBIFS_IDX_NODE);
  457. key_read(c, ubifs_idx_key(c, idx), &snod->key);
  458. err = ubifs_dirty_idx_node(c, &snod->key, level, lnum,
  459. snod->offs);
  460. if (err)
  461. goto out;
  462. }
  463. idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
  464. if (!idx_gc) {
  465. err = -ENOMEM;
  466. goto out;
  467. }
  468. idx_gc->lnum = lnum;
  469. idx_gc->unmap = 0;
  470. list_add(&idx_gc->list, &c->idx_gc);
  471. /*
  472. * Don't release the LEB until after the next commit, because
  473. * it may contain data which is needed for recovery. So
  474. * although we freed this LEB, it will become usable only after
  475. * the commit.
  476. */
  477. err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0,
  478. LPROPS_INDEX, 1);
  479. if (err)
  480. goto out;
  481. err = LEB_FREED_IDX;
  482. } else {
  483. dbg_gc("data LEB %d (free %d, dirty %d)",
  484. lnum, lp->free, lp->dirty);
  485. err = move_nodes(c, sleb);
  486. if (err)
  487. goto out_inc_seq;
  488. err = gc_sync_wbufs(c);
  489. if (err)
  490. goto out_inc_seq;
  491. err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 0, 0);
  492. if (err)
  493. goto out_inc_seq;
  494. /* Allow for races with TNC */
  495. c->gced_lnum = lnum;
  496. smp_wmb();
  497. c->gc_seq += 1;
  498. smp_wmb();
  499. if (c->gc_lnum == -1) {
  500. c->gc_lnum = lnum;
  501. err = LEB_RETAINED;
  502. } else {
  503. err = ubifs_wbuf_sync_nolock(wbuf);
  504. if (err)
  505. goto out;
  506. err = ubifs_leb_unmap(c, lnum);
  507. if (err)
  508. goto out;
  509. err = LEB_FREED;
  510. }
  511. }
  512. out:
  513. ubifs_scan_destroy(sleb);
  514. return err;
  515. out_inc_seq:
  516. /* We may have moved at least some nodes so allow for races with TNC */
  517. c->gced_lnum = lnum;
  518. smp_wmb();
  519. c->gc_seq += 1;
  520. smp_wmb();
  521. goto out;
  522. }
  523. /**
  524. * ubifs_garbage_collect - UBIFS garbage collector.
  525. * @c: UBIFS file-system description object
  526. * @anyway: do GC even if there are free LEBs
  527. *
  528. * This function does out-of-place garbage collection. The return codes are:
  529. * o positive LEB number if the LEB has been freed and may be used;
  530. * o %-EAGAIN if the caller has to run commit;
  531. * o %-ENOSPC if GC failed to make any progress;
  532. * o other negative error codes in case of other errors.
  533. *
  534. * Garbage collector writes data to the journal when GC'ing data LEBs, and just
  535. * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point
  536. * commit may be required. But commit cannot be run from inside GC, because the
  537. * caller might be holding the commit lock, so %-EAGAIN is returned instead;
  538. * And this error code means that the caller has to run commit, and re-run GC
  539. * if there is still no free space.
  540. *
  541. * There are many reasons why this function may return %-EAGAIN:
  542. * o the log is full and there is no space to write an LEB reference for
  543. * @c->gc_lnum;
  544. * o the journal is too large and exceeds size limitations;
  545. * o GC moved indexing LEBs, but they can be used only after the commit;
  546. * o the shrinker fails to find clean znodes to free and requests the commit;
  547. * o etc.
  548. *
  549. * Note, if the file-system is close to be full, this function may return
  550. * %-EAGAIN infinitely, so the caller has to limit amount of re-invocations of
  551. * the function. E.g., this happens if the limits on the journal size are too
  552. * tough and GC writes too much to the journal before an LEB is freed. This
  553. * might also mean that the journal is too large, and the TNC becomes to big,
  554. * so that the shrinker is constantly called, finds not clean znodes to free,
  555. * and requests commit. Well, this may also happen if the journal is all right,
  556. * but another kernel process consumes too much memory. Anyway, infinite
  557. * %-EAGAIN may happen, but in some extreme/misconfiguration cases.
  558. */
  559. int ubifs_garbage_collect(struct ubifs_info *c, int anyway)
  560. {
  561. int i, err, ret, min_space = c->dead_wm;
  562. struct ubifs_lprops lp;
  563. struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
  564. ubifs_assert_cmt_locked(c);
  565. ubifs_assert(!c->ro_media && !c->ro_mount);
  566. if (ubifs_gc_should_commit(c))
  567. return -EAGAIN;
  568. mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
  569. if (c->ro_error) {
  570. ret = -EROFS;
  571. goto out_unlock;
  572. }
  573. /* We expect the write-buffer to be empty on entry */
  574. ubifs_assert(!wbuf->used);
  575. for (i = 0; ; i++) {
  576. int space_before, space_after;
  577. cond_resched();
  578. /* Give the commit an opportunity to run */
  579. if (ubifs_gc_should_commit(c)) {
  580. ret = -EAGAIN;
  581. break;
  582. }
  583. if (i > SOFT_LEBS_LIMIT && !list_empty(&c->idx_gc)) {
  584. /*
  585. * We've done enough iterations. Indexing LEBs were
  586. * moved and will be available after the commit.
  587. */
  588. dbg_gc("soft limit, some index LEBs GC'ed, -EAGAIN");
  589. ubifs_commit_required(c);
  590. ret = -EAGAIN;
  591. break;
  592. }
  593. if (i > HARD_LEBS_LIMIT) {
  594. /*
  595. * We've moved too many LEBs and have not made
  596. * progress, give up.
  597. */
  598. dbg_gc("hard limit, -ENOSPC");
  599. ret = -ENOSPC;
  600. break;
  601. }
  602. /*
  603. * Empty and freeable LEBs can turn up while we waited for
  604. * the wbuf lock, or while we have been running GC. In that
  605. * case, we should just return one of those instead of
  606. * continuing to GC dirty LEBs. Hence we request
  607. * 'ubifs_find_dirty_leb()' to return an empty LEB if it can.
  608. */
  609. ret = ubifs_find_dirty_leb(c, &lp, min_space, anyway ? 0 : 1);
  610. if (ret) {
  611. if (ret == -ENOSPC)
  612. dbg_gc("no more dirty LEBs");
  613. break;
  614. }
  615. dbg_gc("found LEB %d: free %d, dirty %d, sum %d (min. space %d)",
  616. lp.lnum, lp.free, lp.dirty, lp.free + lp.dirty,
  617. min_space);
  618. space_before = c->leb_size - wbuf->offs - wbuf->used;
  619. if (wbuf->lnum == -1)
  620. space_before = 0;
  621. ret = ubifs_garbage_collect_leb(c, &lp);
  622. if (ret < 0) {
  623. if (ret == -EAGAIN) {
  624. /*
  625. * This is not error, so we have to return the
  626. * LEB to lprops. But if 'ubifs_return_leb()'
  627. * fails, its failure code is propagated to the
  628. * caller instead of the original '-EAGAIN'.
  629. */
  630. err = ubifs_return_leb(c, lp.lnum);
  631. if (err)
  632. ret = err;
  633. break;
  634. }
  635. goto out;
  636. }
  637. if (ret == LEB_FREED) {
  638. /* An LEB has been freed and is ready for use */
  639. dbg_gc("LEB %d freed, return", lp.lnum);
  640. ret = lp.lnum;
  641. break;
  642. }
  643. if (ret == LEB_FREED_IDX) {
  644. /*
  645. * This was an indexing LEB and it cannot be
  646. * immediately used. And instead of requesting the
  647. * commit straight away, we try to garbage collect some
  648. * more.
  649. */
  650. dbg_gc("indexing LEB %d freed, continue", lp.lnum);
  651. continue;
  652. }
  653. ubifs_assert(ret == LEB_RETAINED);
  654. space_after = c->leb_size - wbuf->offs - wbuf->used;
  655. dbg_gc("LEB %d retained, freed %d bytes", lp.lnum,
  656. space_after - space_before);
  657. if (space_after > space_before) {
  658. /* GC makes progress, keep working */
  659. min_space >>= 1;
  660. if (min_space < c->dead_wm)
  661. min_space = c->dead_wm;
  662. continue;
  663. }
  664. dbg_gc("did not make progress");
  665. /*
  666. * GC moved an LEB bud have not done any progress. This means
  667. * that the previous GC head LEB contained too few free space
  668. * and the LEB which was GC'ed contained only large nodes which
  669. * did not fit that space.
  670. *
  671. * We can do 2 things:
  672. * 1. pick another LEB in a hope it'll contain a small node
  673. * which will fit the space we have at the end of current GC
  674. * head LEB, but there is no guarantee, so we try this out
  675. * unless we have already been working for too long;
  676. * 2. request an LEB with more dirty space, which will force
  677. * 'ubifs_find_dirty_leb()' to start scanning the lprops
  678. * table, instead of just picking one from the heap
  679. * (previously it already picked the dirtiest LEB).
  680. */
  681. if (i < SOFT_LEBS_LIMIT) {
  682. dbg_gc("try again");
  683. continue;
  684. }
  685. min_space <<= 1;
  686. if (min_space > c->dark_wm)
  687. min_space = c->dark_wm;
  688. dbg_gc("set min. space to %d", min_space);
  689. }
  690. if (ret == -ENOSPC && !list_empty(&c->idx_gc)) {
  691. dbg_gc("no space, some index LEBs GC'ed, -EAGAIN");
  692. ubifs_commit_required(c);
  693. ret = -EAGAIN;
  694. }
  695. err = ubifs_wbuf_sync_nolock(wbuf);
  696. if (!err)
  697. err = ubifs_leb_unmap(c, c->gc_lnum);
  698. if (err) {
  699. ret = err;
  700. goto out;
  701. }
  702. out_unlock:
  703. mutex_unlock(&wbuf->io_mutex);
  704. return ret;
  705. out:
  706. ubifs_assert(ret < 0);
  707. ubifs_assert(ret != -ENOSPC && ret != -EAGAIN);
  708. ubifs_wbuf_sync_nolock(wbuf);
  709. ubifs_ro_mode(c, ret);
  710. mutex_unlock(&wbuf->io_mutex);
  711. ubifs_return_leb(c, lp.lnum);
  712. return ret;
  713. }
  714. /**
  715. * ubifs_gc_start_commit - garbage collection at start of commit.
  716. * @c: UBIFS file-system description object
  717. *
  718. * If a LEB has only dirty and free space, then we may safely unmap it and make
  719. * it free. Note, we cannot do this with indexing LEBs because dirty space may
  720. * correspond index nodes that are required for recovery. In that case, the
  721. * LEB cannot be unmapped until after the next commit.
  722. *
  723. * This function returns %0 upon success and a negative error code upon failure.
  724. */
  725. int ubifs_gc_start_commit(struct ubifs_info *c)
  726. {
  727. struct ubifs_gced_idx_leb *idx_gc;
  728. const struct ubifs_lprops *lp;
  729. int err = 0, flags;
  730. ubifs_get_lprops(c);
  731. /*
  732. * Unmap (non-index) freeable LEBs. Note that recovery requires that all
  733. * wbufs are sync'd before this, which is done in 'do_commit()'.
  734. */
  735. while (1) {
  736. lp = ubifs_fast_find_freeable(c);
  737. if (IS_ERR(lp)) {
  738. err = PTR_ERR(lp);
  739. goto out;
  740. }
  741. if (!lp)
  742. break;
  743. ubifs_assert(!(lp->flags & LPROPS_TAKEN));
  744. ubifs_assert(!(lp->flags & LPROPS_INDEX));
  745. err = ubifs_leb_unmap(c, lp->lnum);
  746. if (err)
  747. goto out;
  748. lp = ubifs_change_lp(c, lp, c->leb_size, 0, lp->flags, 0);
  749. if (IS_ERR(lp)) {
  750. err = PTR_ERR(lp);
  751. goto out;
  752. }
  753. ubifs_assert(!(lp->flags & LPROPS_TAKEN));
  754. ubifs_assert(!(lp->flags & LPROPS_INDEX));
  755. }
  756. /* Mark GC'd index LEBs OK to unmap after this commit finishes */
  757. list_for_each_entry(idx_gc, &c->idx_gc, list)
  758. idx_gc->unmap = 1;
  759. /* Record index freeable LEBs for unmapping after commit */
  760. while (1) {
  761. lp = ubifs_fast_find_frdi_idx(c);
  762. if (IS_ERR(lp)) {
  763. err = PTR_ERR(lp);
  764. goto out;
  765. }
  766. if (!lp)
  767. break;
  768. idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
  769. if (!idx_gc) {
  770. err = -ENOMEM;
  771. goto out;
  772. }
  773. ubifs_assert(!(lp->flags & LPROPS_TAKEN));
  774. ubifs_assert(lp->flags & LPROPS_INDEX);
  775. /* Don't release the LEB until after the next commit */
  776. flags = (lp->flags | LPROPS_TAKEN) ^ LPROPS_INDEX;
  777. lp = ubifs_change_lp(c, lp, c->leb_size, 0, flags, 1);
  778. if (IS_ERR(lp)) {
  779. err = PTR_ERR(lp);
  780. kfree(idx_gc);
  781. goto out;
  782. }
  783. ubifs_assert(lp->flags & LPROPS_TAKEN);
  784. ubifs_assert(!(lp->flags & LPROPS_INDEX));
  785. idx_gc->lnum = lp->lnum;
  786. idx_gc->unmap = 1;
  787. list_add(&idx_gc->list, &c->idx_gc);
  788. }
  789. out:
  790. ubifs_release_lprops(c);
  791. return err;
  792. }
  793. /**
  794. * ubifs_gc_end_commit - garbage collection at end of commit.
  795. * @c: UBIFS file-system description object
  796. *
  797. * This function completes out-of-place garbage collection of index LEBs.
  798. */
  799. int ubifs_gc_end_commit(struct ubifs_info *c)
  800. {
  801. struct ubifs_gced_idx_leb *idx_gc, *tmp;
  802. struct ubifs_wbuf *wbuf;
  803. int err = 0;
  804. wbuf = &c->jheads[GCHD].wbuf;
  805. mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
  806. list_for_each_entry_safe(idx_gc, tmp, &c->idx_gc, list)
  807. if (idx_gc->unmap) {
  808. dbg_gc("LEB %d", idx_gc->lnum);
  809. err = ubifs_leb_unmap(c, idx_gc->lnum);
  810. if (err)
  811. goto out;
  812. err = ubifs_change_one_lp(c, idx_gc->lnum, LPROPS_NC,
  813. LPROPS_NC, 0, LPROPS_TAKEN, -1);
  814. if (err)
  815. goto out;
  816. list_del(&idx_gc->list);
  817. kfree(idx_gc);
  818. }
  819. out:
  820. mutex_unlock(&wbuf->io_mutex);
  821. return err;
  822. }
  823. #endif
  824. /**
  825. * ubifs_destroy_idx_gc - destroy idx_gc list.
  826. * @c: UBIFS file-system description object
  827. *
  828. * This function destroys the @c->idx_gc list. It is called when unmounting
  829. * so locks are not needed. Returns zero in case of success and a negative
  830. * error code in case of failure.
  831. */
  832. void ubifs_destroy_idx_gc(struct ubifs_info *c)
  833. {
  834. while (!list_empty(&c->idx_gc)) {
  835. struct ubifs_gced_idx_leb *idx_gc;
  836. idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb,
  837. list);
  838. c->idx_gc_cnt -= 1;
  839. list_del(&idx_gc->list);
  840. kfree(idx_gc);
  841. }
  842. }
  843. #ifndef __UBOOT__
  844. /**
  845. * ubifs_get_idx_gc_leb - get a LEB from GC'd index LEB list.
  846. * @c: UBIFS file-system description object
  847. *
  848. * Called during start commit so locks are not needed.
  849. */
  850. int ubifs_get_idx_gc_leb(struct ubifs_info *c)
  851. {
  852. struct ubifs_gced_idx_leb *idx_gc;
  853. int lnum;
  854. if (list_empty(&c->idx_gc))
  855. return -ENOSPC;
  856. idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, list);
  857. lnum = idx_gc->lnum;
  858. /* c->idx_gc_cnt is updated by the caller when lprops are updated */
  859. list_del(&idx_gc->list);
  860. kfree(idx_gc);
  861. return lnum;
  862. }
  863. #endif