find.c 30 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985
  1. /*
  2. * This file is part of UBIFS.
  3. *
  4. * Copyright (C) 2006-2008 Nokia Corporation.
  5. *
  6. * This program is free software; you can redistribute it and/or modify it
  7. * under the terms of the GNU General Public License version 2 as published by
  8. * the Free Software Foundation.
  9. *
  10. * This program is distributed in the hope that it will be useful, but WITHOUT
  11. * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12. * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
  13. * more details.
  14. *
  15. * You should have received a copy of the GNU General Public License along with
  16. * this program; if not, write to the Free Software Foundation, Inc., 51
  17. * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  18. *
  19. * Authors: Artem Bityutskiy (Битюцкий Артём)
  20. * Adrian Hunter
  21. */
  22. /*
  23. * This file contains functions for finding LEBs for various purposes e.g.
  24. * garbage collection. In general, lprops category heaps and lists are used
  25. * for fast access, falling back on scanning the LPT as a last resort.
  26. */
  27. #include <linux/sort.h>
  28. #include "ubifs.h"
  29. /**
  30. * struct scan_data - data provided to scan callback functions
  31. * @min_space: minimum number of bytes for which to scan
  32. * @pick_free: whether it is OK to scan for empty LEBs
  33. * @lnum: LEB number found is returned here
  34. * @exclude_index: whether to exclude index LEBs
  35. */
  36. struct scan_data {
  37. int min_space;
  38. int pick_free;
  39. int lnum;
  40. int exclude_index;
  41. };
  42. /**
  43. * valuable - determine whether LEB properties are valuable.
  44. * @c: the UBIFS file-system description object
  45. * @lprops: LEB properties
  46. *
  47. * This function return %1 if the LEB properties should be added to the LEB
  48. * properties tree in memory. Otherwise %0 is returned.
  49. */
  50. static int valuable(struct ubifs_info *c, const struct ubifs_lprops *lprops)
  51. {
  52. int n, cat = lprops->flags & LPROPS_CAT_MASK;
  53. struct ubifs_lpt_heap *heap;
  54. switch (cat) {
  55. case LPROPS_DIRTY:
  56. case LPROPS_DIRTY_IDX:
  57. case LPROPS_FREE:
  58. heap = &c->lpt_heap[cat - 1];
  59. if (heap->cnt < heap->max_cnt)
  60. return 1;
  61. if (lprops->free + lprops->dirty >= c->dark_wm)
  62. return 1;
  63. return 0;
  64. case LPROPS_EMPTY:
  65. n = c->lst.empty_lebs + c->freeable_cnt -
  66. c->lst.taken_empty_lebs;
  67. if (n < c->lsave_cnt)
  68. return 1;
  69. return 0;
  70. case LPROPS_FREEABLE:
  71. return 1;
  72. case LPROPS_FRDI_IDX:
  73. return 1;
  74. }
  75. return 0;
  76. }
  77. /**
  78. * scan_for_dirty_cb - dirty space scan callback.
  79. * @c: the UBIFS file-system description object
  80. * @lprops: LEB properties to scan
  81. * @in_tree: whether the LEB properties are in main memory
  82. * @data: information passed to and from the caller of the scan
  83. *
  84. * This function returns a code that indicates whether the scan should continue
  85. * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
  86. * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
  87. * (%LPT_SCAN_STOP).
  88. */
  89. static int scan_for_dirty_cb(struct ubifs_info *c,
  90. const struct ubifs_lprops *lprops, int in_tree,
  91. struct scan_data *data)
  92. {
  93. int ret = LPT_SCAN_CONTINUE;
  94. /* Exclude LEBs that are currently in use */
  95. if (lprops->flags & LPROPS_TAKEN)
  96. return LPT_SCAN_CONTINUE;
  97. /* Determine whether to add these LEB properties to the tree */
  98. if (!in_tree && valuable(c, lprops))
  99. ret |= LPT_SCAN_ADD;
  100. /* Exclude LEBs with too little space */
  101. if (lprops->free + lprops->dirty < data->min_space)
  102. return ret;
  103. /* If specified, exclude index LEBs */
  104. if (data->exclude_index && lprops->flags & LPROPS_INDEX)
  105. return ret;
  106. /* If specified, exclude empty or freeable LEBs */
  107. if (lprops->free + lprops->dirty == c->leb_size) {
  108. if (!data->pick_free)
  109. return ret;
  110. /* Exclude LEBs with too little dirty space (unless it is empty) */
  111. } else if (lprops->dirty < c->dead_wm)
  112. return ret;
  113. /* Finally we found space */
  114. data->lnum = lprops->lnum;
  115. return LPT_SCAN_ADD | LPT_SCAN_STOP;
  116. }
  117. /**
  118. * scan_for_dirty - find a data LEB with free space.
  119. * @c: the UBIFS file-system description object
  120. * @min_space: minimum amount free plus dirty space the returned LEB has to
  121. * have
  122. * @pick_free: if it is OK to return a free or freeable LEB
  123. * @exclude_index: whether to exclude index LEBs
  124. *
  125. * This function returns a pointer to the LEB properties found or a negative
  126. * error code.
  127. */
  128. static const struct ubifs_lprops *scan_for_dirty(struct ubifs_info *c,
  129. int min_space, int pick_free,
  130. int exclude_index)
  131. {
  132. const struct ubifs_lprops *lprops;
  133. struct ubifs_lpt_heap *heap;
  134. struct scan_data data;
  135. int err, i;
  136. /* There may be an LEB with enough dirty space on the free heap */
  137. heap = &c->lpt_heap[LPROPS_FREE - 1];
  138. for (i = 0; i < heap->cnt; i++) {
  139. lprops = heap->arr[i];
  140. if (lprops->free + lprops->dirty < min_space)
  141. continue;
  142. if (lprops->dirty < c->dead_wm)
  143. continue;
  144. return lprops;
  145. }
  146. /*
  147. * A LEB may have fallen off of the bottom of the dirty heap, and ended
  148. * up as uncategorized even though it has enough dirty space for us now,
  149. * so check the uncategorized list. N.B. neither empty nor freeable LEBs
  150. * can end up as uncategorized because they are kept on lists not
  151. * finite-sized heaps.
  152. */
  153. list_for_each_entry(lprops, &c->uncat_list, list) {
  154. if (lprops->flags & LPROPS_TAKEN)
  155. continue;
  156. if (lprops->free + lprops->dirty < min_space)
  157. continue;
  158. if (exclude_index && (lprops->flags & LPROPS_INDEX))
  159. continue;
  160. if (lprops->dirty < c->dead_wm)
  161. continue;
  162. return lprops;
  163. }
  164. /* We have looked everywhere in main memory, now scan the flash */
  165. if (c->pnodes_have >= c->pnode_cnt)
  166. /* All pnodes are in memory, so skip scan */
  167. return ERR_PTR(-ENOSPC);
  168. data.min_space = min_space;
  169. data.pick_free = pick_free;
  170. data.lnum = -1;
  171. data.exclude_index = exclude_index;
  172. err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
  173. (ubifs_lpt_scan_callback)scan_for_dirty_cb,
  174. &data);
  175. if (err)
  176. return ERR_PTR(err);
  177. ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
  178. c->lscan_lnum = data.lnum;
  179. lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
  180. if (IS_ERR(lprops))
  181. return lprops;
  182. ubifs_assert(lprops->lnum == data.lnum);
  183. ubifs_assert(lprops->free + lprops->dirty >= min_space);
  184. ubifs_assert(lprops->dirty >= c->dead_wm ||
  185. (pick_free &&
  186. lprops->free + lprops->dirty == c->leb_size));
  187. ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
  188. ubifs_assert(!exclude_index || !(lprops->flags & LPROPS_INDEX));
  189. return lprops;
  190. }
  191. /**
  192. * ubifs_find_dirty_leb - find a dirty LEB for the Garbage Collector.
  193. * @c: the UBIFS file-system description object
  194. * @ret_lp: LEB properties are returned here on exit
  195. * @min_space: minimum amount free plus dirty space the returned LEB has to
  196. * have
  197. * @pick_free: controls whether it is OK to pick empty or index LEBs
  198. *
  199. * This function tries to find a dirty logical eraseblock which has at least
  200. * @min_space free and dirty space. It prefers to take an LEB from the dirty or
  201. * dirty index heap, and it falls-back to LPT scanning if the heaps are empty
  202. * or do not have an LEB which satisfies the @min_space criteria.
  203. *
  204. * Note, LEBs which have less than dead watermark of free + dirty space are
  205. * never picked by this function.
  206. *
  207. * The additional @pick_free argument controls if this function has to return a
  208. * free or freeable LEB if one is present. For example, GC must to set it to %1,
  209. * when called from the journal space reservation function, because the
  210. * appearance of free space may coincide with the loss of enough dirty space
  211. * for GC to succeed anyway.
  212. *
  213. * In contrast, if the Garbage Collector is called from budgeting, it should
  214. * just make free space, not return LEBs which are already free or freeable.
  215. *
  216. * In addition @pick_free is set to %2 by the recovery process in order to
  217. * recover gc_lnum in which case an index LEB must not be returned.
  218. *
  219. * This function returns zero and the LEB properties of found dirty LEB in case
  220. * of success, %-ENOSPC if no dirty LEB was found and a negative error code in
  221. * case of other failures. The returned LEB is marked as "taken".
  222. */
  223. int ubifs_find_dirty_leb(struct ubifs_info *c, struct ubifs_lprops *ret_lp,
  224. int min_space, int pick_free)
  225. {
  226. int err = 0, sum, exclude_index = pick_free == 2 ? 1 : 0;
  227. const struct ubifs_lprops *lp = NULL, *idx_lp = NULL;
  228. struct ubifs_lpt_heap *heap, *idx_heap;
  229. ubifs_get_lprops(c);
  230. if (pick_free) {
  231. int lebs, rsvd_idx_lebs = 0;
  232. spin_lock(&c->space_lock);
  233. lebs = c->lst.empty_lebs + c->idx_gc_cnt;
  234. lebs += c->freeable_cnt - c->lst.taken_empty_lebs;
  235. /*
  236. * Note, the index may consume more LEBs than have been reserved
  237. * for it. It is OK because it might be consolidated by GC.
  238. * But if the index takes fewer LEBs than it is reserved for it,
  239. * this function must avoid picking those reserved LEBs.
  240. */
  241. if (c->bi.min_idx_lebs >= c->lst.idx_lebs) {
  242. rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs;
  243. exclude_index = 1;
  244. }
  245. spin_unlock(&c->space_lock);
  246. /* Check if there are enough free LEBs for the index */
  247. if (rsvd_idx_lebs < lebs) {
  248. /* OK, try to find an empty LEB */
  249. lp = ubifs_fast_find_empty(c);
  250. if (lp)
  251. goto found;
  252. /* Or a freeable LEB */
  253. lp = ubifs_fast_find_freeable(c);
  254. if (lp)
  255. goto found;
  256. } else
  257. /*
  258. * We cannot pick free/freeable LEBs in the below code.
  259. */
  260. pick_free = 0;
  261. } else {
  262. spin_lock(&c->space_lock);
  263. exclude_index = (c->bi.min_idx_lebs >= c->lst.idx_lebs);
  264. spin_unlock(&c->space_lock);
  265. }
  266. /* Look on the dirty and dirty index heaps */
  267. heap = &c->lpt_heap[LPROPS_DIRTY - 1];
  268. idx_heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
  269. if (idx_heap->cnt && !exclude_index) {
  270. idx_lp = idx_heap->arr[0];
  271. sum = idx_lp->free + idx_lp->dirty;
  272. /*
  273. * Since we reserve thrice as much space for the index than it
  274. * actually takes, it does not make sense to pick indexing LEBs
  275. * with less than, say, half LEB of dirty space. May be half is
  276. * not the optimal boundary - this should be tested and
  277. * checked. This boundary should determine how much we use
  278. * in-the-gaps to consolidate the index comparing to how much
  279. * we use garbage collector to consolidate it. The "half"
  280. * criteria just feels to be fine.
  281. */
  282. if (sum < min_space || sum < c->half_leb_size)
  283. idx_lp = NULL;
  284. }
  285. if (heap->cnt) {
  286. lp = heap->arr[0];
  287. if (lp->dirty + lp->free < min_space)
  288. lp = NULL;
  289. }
  290. /* Pick the LEB with most space */
  291. if (idx_lp && lp) {
  292. if (idx_lp->free + idx_lp->dirty >= lp->free + lp->dirty)
  293. lp = idx_lp;
  294. } else if (idx_lp && !lp)
  295. lp = idx_lp;
  296. if (lp) {
  297. ubifs_assert(lp->free + lp->dirty >= c->dead_wm);
  298. goto found;
  299. }
  300. /* Did not find a dirty LEB on the dirty heaps, have to scan */
  301. dbg_find("scanning LPT for a dirty LEB");
  302. lp = scan_for_dirty(c, min_space, pick_free, exclude_index);
  303. if (IS_ERR(lp)) {
  304. err = PTR_ERR(lp);
  305. goto out;
  306. }
  307. ubifs_assert(lp->dirty >= c->dead_wm ||
  308. (pick_free && lp->free + lp->dirty == c->leb_size));
  309. found:
  310. dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
  311. lp->lnum, lp->free, lp->dirty, lp->flags);
  312. lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
  313. lp->flags | LPROPS_TAKEN, 0);
  314. if (IS_ERR(lp)) {
  315. err = PTR_ERR(lp);
  316. goto out;
  317. }
  318. memcpy(ret_lp, lp, sizeof(struct ubifs_lprops));
  319. out:
  320. ubifs_release_lprops(c);
  321. return err;
  322. }
  323. /**
  324. * scan_for_free_cb - free space scan callback.
  325. * @c: the UBIFS file-system description object
  326. * @lprops: LEB properties to scan
  327. * @in_tree: whether the LEB properties are in main memory
  328. * @data: information passed to and from the caller of the scan
  329. *
  330. * This function returns a code that indicates whether the scan should continue
  331. * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
  332. * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
  333. * (%LPT_SCAN_STOP).
  334. */
  335. static int scan_for_free_cb(struct ubifs_info *c,
  336. const struct ubifs_lprops *lprops, int in_tree,
  337. struct scan_data *data)
  338. {
  339. int ret = LPT_SCAN_CONTINUE;
  340. /* Exclude LEBs that are currently in use */
  341. if (lprops->flags & LPROPS_TAKEN)
  342. return LPT_SCAN_CONTINUE;
  343. /* Determine whether to add these LEB properties to the tree */
  344. if (!in_tree && valuable(c, lprops))
  345. ret |= LPT_SCAN_ADD;
  346. /* Exclude index LEBs */
  347. if (lprops->flags & LPROPS_INDEX)
  348. return ret;
  349. /* Exclude LEBs with too little space */
  350. if (lprops->free < data->min_space)
  351. return ret;
  352. /* If specified, exclude empty LEBs */
  353. if (!data->pick_free && lprops->free == c->leb_size)
  354. return ret;
  355. /*
  356. * LEBs that have only free and dirty space must not be allocated
  357. * because they may have been unmapped already or they may have data
  358. * that is obsolete only because of nodes that are still sitting in a
  359. * wbuf.
  360. */
  361. if (lprops->free + lprops->dirty == c->leb_size && lprops->dirty > 0)
  362. return ret;
  363. /* Finally we found space */
  364. data->lnum = lprops->lnum;
  365. return LPT_SCAN_ADD | LPT_SCAN_STOP;
  366. }
  367. /**
  368. * do_find_free_space - find a data LEB with free space.
  369. * @c: the UBIFS file-system description object
  370. * @min_space: minimum amount of free space required
  371. * @pick_free: whether it is OK to scan for empty LEBs
  372. * @squeeze: whether to try to find space in a non-empty LEB first
  373. *
  374. * This function returns a pointer to the LEB properties found or a negative
  375. * error code.
  376. */
  377. static
  378. const struct ubifs_lprops *do_find_free_space(struct ubifs_info *c,
  379. int min_space, int pick_free,
  380. int squeeze)
  381. {
  382. const struct ubifs_lprops *lprops;
  383. struct ubifs_lpt_heap *heap;
  384. struct scan_data data;
  385. int err, i;
  386. if (squeeze) {
  387. lprops = ubifs_fast_find_free(c);
  388. if (lprops && lprops->free >= min_space)
  389. return lprops;
  390. }
  391. if (pick_free) {
  392. lprops = ubifs_fast_find_empty(c);
  393. if (lprops)
  394. return lprops;
  395. }
  396. if (!squeeze) {
  397. lprops = ubifs_fast_find_free(c);
  398. if (lprops && lprops->free >= min_space)
  399. return lprops;
  400. }
  401. /* There may be an LEB with enough free space on the dirty heap */
  402. heap = &c->lpt_heap[LPROPS_DIRTY - 1];
  403. for (i = 0; i < heap->cnt; i++) {
  404. lprops = heap->arr[i];
  405. if (lprops->free >= min_space)
  406. return lprops;
  407. }
  408. /*
  409. * A LEB may have fallen off of the bottom of the free heap, and ended
  410. * up as uncategorized even though it has enough free space for us now,
  411. * so check the uncategorized list. N.B. neither empty nor freeable LEBs
  412. * can end up as uncategorized because they are kept on lists not
  413. * finite-sized heaps.
  414. */
  415. list_for_each_entry(lprops, &c->uncat_list, list) {
  416. if (lprops->flags & LPROPS_TAKEN)
  417. continue;
  418. if (lprops->flags & LPROPS_INDEX)
  419. continue;
  420. if (lprops->free >= min_space)
  421. return lprops;
  422. }
  423. /* We have looked everywhere in main memory, now scan the flash */
  424. if (c->pnodes_have >= c->pnode_cnt)
  425. /* All pnodes are in memory, so skip scan */
  426. return ERR_PTR(-ENOSPC);
  427. data.min_space = min_space;
  428. data.pick_free = pick_free;
  429. data.lnum = -1;
  430. err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
  431. (ubifs_lpt_scan_callback)scan_for_free_cb,
  432. &data);
  433. if (err)
  434. return ERR_PTR(err);
  435. ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
  436. c->lscan_lnum = data.lnum;
  437. lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
  438. if (IS_ERR(lprops))
  439. return lprops;
  440. ubifs_assert(lprops->lnum == data.lnum);
  441. ubifs_assert(lprops->free >= min_space);
  442. ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
  443. ubifs_assert(!(lprops->flags & LPROPS_INDEX));
  444. return lprops;
  445. }
  446. /**
  447. * ubifs_find_free_space - find a data LEB with free space.
  448. * @c: the UBIFS file-system description object
  449. * @min_space: minimum amount of required free space
  450. * @offs: contains offset of where free space starts on exit
  451. * @squeeze: whether to try to find space in a non-empty LEB first
  452. *
  453. * This function looks for an LEB with at least @min_space bytes of free space.
  454. * It tries to find an empty LEB if possible. If no empty LEBs are available,
  455. * this function searches for a non-empty data LEB. The returned LEB is marked
  456. * as "taken".
  457. *
  458. * This function returns found LEB number in case of success, %-ENOSPC if it
  459. * failed to find a LEB with @min_space bytes of free space and other a negative
  460. * error codes in case of failure.
  461. */
  462. int ubifs_find_free_space(struct ubifs_info *c, int min_space, int *offs,
  463. int squeeze)
  464. {
  465. const struct ubifs_lprops *lprops;
  466. int lebs, rsvd_idx_lebs, pick_free = 0, err, lnum, flags;
  467. dbg_find("min_space %d", min_space);
  468. ubifs_get_lprops(c);
  469. /* Check if there are enough empty LEBs for commit */
  470. spin_lock(&c->space_lock);
  471. if (c->bi.min_idx_lebs > c->lst.idx_lebs)
  472. rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs;
  473. else
  474. rsvd_idx_lebs = 0;
  475. lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt -
  476. c->lst.taken_empty_lebs;
  477. if (rsvd_idx_lebs < lebs)
  478. /*
  479. * OK to allocate an empty LEB, but we still don't want to go
  480. * looking for one if there aren't any.
  481. */
  482. if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {
  483. pick_free = 1;
  484. /*
  485. * Because we release the space lock, we must account
  486. * for this allocation here. After the LEB properties
  487. * flags have been updated, we subtract one. Note, the
  488. * result of this is that lprops also decreases
  489. * @taken_empty_lebs in 'ubifs_change_lp()', so it is
  490. * off by one for a short period of time which may
  491. * introduce a small disturbance to budgeting
  492. * calculations, but this is harmless because at the
  493. * worst case this would make the budgeting subsystem
  494. * be more pessimistic than needed.
  495. *
  496. * Fundamentally, this is about serialization of the
  497. * budgeting and lprops subsystems. We could make the
  498. * @space_lock a mutex and avoid dropping it before
  499. * calling 'ubifs_change_lp()', but mutex is more
  500. * heavy-weight, and we want budgeting to be as fast as
  501. * possible.
  502. */
  503. c->lst.taken_empty_lebs += 1;
  504. }
  505. spin_unlock(&c->space_lock);
  506. lprops = do_find_free_space(c, min_space, pick_free, squeeze);
  507. if (IS_ERR(lprops)) {
  508. err = PTR_ERR(lprops);
  509. goto out;
  510. }
  511. lnum = lprops->lnum;
  512. flags = lprops->flags | LPROPS_TAKEN;
  513. lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, flags, 0);
  514. if (IS_ERR(lprops)) {
  515. err = PTR_ERR(lprops);
  516. goto out;
  517. }
  518. if (pick_free) {
  519. spin_lock(&c->space_lock);
  520. c->lst.taken_empty_lebs -= 1;
  521. spin_unlock(&c->space_lock);
  522. }
  523. *offs = c->leb_size - lprops->free;
  524. ubifs_release_lprops(c);
  525. if (*offs == 0) {
  526. /*
  527. * Ensure that empty LEBs have been unmapped. They may not have
  528. * been, for example, because of an unclean unmount. Also
  529. * LEBs that were freeable LEBs (free + dirty == leb_size) will
  530. * not have been unmapped.
  531. */
  532. err = ubifs_leb_unmap(c, lnum);
  533. if (err)
  534. return err;
  535. }
  536. dbg_find("found LEB %d, free %d", lnum, c->leb_size - *offs);
  537. ubifs_assert(*offs <= c->leb_size - min_space);
  538. return lnum;
  539. out:
  540. if (pick_free) {
  541. spin_lock(&c->space_lock);
  542. c->lst.taken_empty_lebs -= 1;
  543. spin_unlock(&c->space_lock);
  544. }
  545. ubifs_release_lprops(c);
  546. return err;
  547. }
  548. /**
  549. * scan_for_idx_cb - callback used by the scan for a free LEB for the index.
  550. * @c: the UBIFS file-system description object
  551. * @lprops: LEB properties to scan
  552. * @in_tree: whether the LEB properties are in main memory
  553. * @data: information passed to and from the caller of the scan
  554. *
  555. * This function returns a code that indicates whether the scan should continue
  556. * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
  557. * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
  558. * (%LPT_SCAN_STOP).
  559. */
  560. static int scan_for_idx_cb(struct ubifs_info *c,
  561. const struct ubifs_lprops *lprops, int in_tree,
  562. struct scan_data *data)
  563. {
  564. int ret = LPT_SCAN_CONTINUE;
  565. /* Exclude LEBs that are currently in use */
  566. if (lprops->flags & LPROPS_TAKEN)
  567. return LPT_SCAN_CONTINUE;
  568. /* Determine whether to add these LEB properties to the tree */
  569. if (!in_tree && valuable(c, lprops))
  570. ret |= LPT_SCAN_ADD;
  571. /* Exclude index LEBS */
  572. if (lprops->flags & LPROPS_INDEX)
  573. return ret;
  574. /* Exclude LEBs that cannot be made empty */
  575. if (lprops->free + lprops->dirty != c->leb_size)
  576. return ret;
  577. /*
  578. * We are allocating for the index so it is safe to allocate LEBs with
  579. * only free and dirty space, because write buffers are sync'd at commit
  580. * start.
  581. */
  582. data->lnum = lprops->lnum;
  583. return LPT_SCAN_ADD | LPT_SCAN_STOP;
  584. }
  585. /**
  586. * scan_for_leb_for_idx - scan for a free LEB for the index.
  587. * @c: the UBIFS file-system description object
  588. */
  589. static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c)
  590. {
  591. struct ubifs_lprops *lprops;
  592. struct scan_data data;
  593. int err;
  594. data.lnum = -1;
  595. err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
  596. (ubifs_lpt_scan_callback)scan_for_idx_cb,
  597. &data);
  598. if (err)
  599. return ERR_PTR(err);
  600. ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
  601. c->lscan_lnum = data.lnum;
  602. lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
  603. if (IS_ERR(lprops))
  604. return lprops;
  605. ubifs_assert(lprops->lnum == data.lnum);
  606. ubifs_assert(lprops->free + lprops->dirty == c->leb_size);
  607. ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
  608. ubifs_assert(!(lprops->flags & LPROPS_INDEX));
  609. return lprops;
  610. }
  611. /**
  612. * ubifs_find_free_leb_for_idx - find a free LEB for the index.
  613. * @c: the UBIFS file-system description object
  614. *
  615. * This function looks for a free LEB and returns that LEB number. The returned
  616. * LEB is marked as "taken", "index".
  617. *
  618. * Only empty LEBs are allocated. This is for two reasons. First, the commit
  619. * calculates the number of LEBs to allocate based on the assumption that they
  620. * will be empty. Secondly, free space at the end of an index LEB is not
  621. * guaranteed to be empty because it may have been used by the in-the-gaps
  622. * method prior to an unclean unmount.
  623. *
  624. * If no LEB is found %-ENOSPC is returned. For other failures another negative
  625. * error code is returned.
  626. */
  627. int ubifs_find_free_leb_for_idx(struct ubifs_info *c)
  628. {
  629. const struct ubifs_lprops *lprops;
  630. int lnum = -1, err, flags;
  631. ubifs_get_lprops(c);
  632. lprops = ubifs_fast_find_empty(c);
  633. if (!lprops) {
  634. lprops = ubifs_fast_find_freeable(c);
  635. if (!lprops) {
  636. /*
  637. * The first condition means the following: go scan the
  638. * LPT if there are uncategorized lprops, which means
  639. * there may be freeable LEBs there (UBIFS does not
  640. * store the information about freeable LEBs in the
  641. * master node).
  642. */
  643. if (c->in_a_category_cnt != c->main_lebs ||
  644. c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {
  645. ubifs_assert(c->freeable_cnt == 0);
  646. lprops = scan_for_leb_for_idx(c);
  647. if (IS_ERR(lprops)) {
  648. err = PTR_ERR(lprops);
  649. goto out;
  650. }
  651. }
  652. }
  653. }
  654. if (!lprops) {
  655. err = -ENOSPC;
  656. goto out;
  657. }
  658. lnum = lprops->lnum;
  659. dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
  660. lnum, lprops->free, lprops->dirty, lprops->flags);
  661. flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX;
  662. lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0);
  663. if (IS_ERR(lprops)) {
  664. err = PTR_ERR(lprops);
  665. goto out;
  666. }
  667. ubifs_release_lprops(c);
  668. /*
  669. * Ensure that empty LEBs have been unmapped. They may not have been,
  670. * for example, because of an unclean unmount. Also LEBs that were
  671. * freeable LEBs (free + dirty == leb_size) will not have been unmapped.
  672. */
  673. err = ubifs_leb_unmap(c, lnum);
  674. if (err) {
  675. ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
  676. LPROPS_TAKEN | LPROPS_INDEX, 0);
  677. return err;
  678. }
  679. return lnum;
  680. out:
  681. ubifs_release_lprops(c);
  682. return err;
  683. }
  684. static int cmp_dirty_idx(const struct ubifs_lprops **a,
  685. const struct ubifs_lprops **b)
  686. {
  687. const struct ubifs_lprops *lpa = *a;
  688. const struct ubifs_lprops *lpb = *b;
  689. return lpa->dirty + lpa->free - lpb->dirty - lpb->free;
  690. }
  691. static void swap_dirty_idx(struct ubifs_lprops **a, struct ubifs_lprops **b,
  692. int size)
  693. {
  694. struct ubifs_lprops *t = *a;
  695. *a = *b;
  696. *b = t;
  697. }
  698. /**
  699. * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos.
  700. * @c: the UBIFS file-system description object
  701. *
  702. * This function is called each commit to create an array of LEB numbers of
  703. * dirty index LEBs sorted in order of dirty and free space. This is used by
  704. * the in-the-gaps method of TNC commit.
  705. */
  706. int ubifs_save_dirty_idx_lnums(struct ubifs_info *c)
  707. {
  708. int i;
  709. ubifs_get_lprops(c);
  710. /* Copy the LPROPS_DIRTY_IDX heap */
  711. c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt;
  712. memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr,
  713. sizeof(void *) * c->dirty_idx.cnt);
  714. /* Sort it so that the dirtiest is now at the end */
  715. sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *),
  716. (int (*)(const void *, const void *))cmp_dirty_idx,
  717. (void (*)(void *, void *, int))swap_dirty_idx);
  718. dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt);
  719. if (c->dirty_idx.cnt)
  720. dbg_find("dirtiest index LEB is %d with dirty %d and free %d",
  721. c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum,
  722. c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty,
  723. c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free);
  724. /* Replace the lprops pointers with LEB numbers */
  725. for (i = 0; i < c->dirty_idx.cnt; i++)
  726. c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum;
  727. ubifs_release_lprops(c);
  728. return 0;
  729. }
  730. /**
  731. * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB.
  732. * @c: the UBIFS file-system description object
  733. * @lprops: LEB properties to scan
  734. * @in_tree: whether the LEB properties are in main memory
  735. * @data: information passed to and from the caller of the scan
  736. *
  737. * This function returns a code that indicates whether the scan should continue
  738. * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
  739. * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
  740. * (%LPT_SCAN_STOP).
  741. */
  742. static int scan_dirty_idx_cb(struct ubifs_info *c,
  743. const struct ubifs_lprops *lprops, int in_tree,
  744. struct scan_data *data)
  745. {
  746. int ret = LPT_SCAN_CONTINUE;
  747. /* Exclude LEBs that are currently in use */
  748. if (lprops->flags & LPROPS_TAKEN)
  749. return LPT_SCAN_CONTINUE;
  750. /* Determine whether to add these LEB properties to the tree */
  751. if (!in_tree && valuable(c, lprops))
  752. ret |= LPT_SCAN_ADD;
  753. /* Exclude non-index LEBs */
  754. if (!(lprops->flags & LPROPS_INDEX))
  755. return ret;
  756. /* Exclude LEBs with too little space */
  757. if (lprops->free + lprops->dirty < c->min_idx_node_sz)
  758. return ret;
  759. /* Finally we found space */
  760. data->lnum = lprops->lnum;
  761. return LPT_SCAN_ADD | LPT_SCAN_STOP;
  762. }
  763. /**
  764. * find_dirty_idx_leb - find a dirty index LEB.
  765. * @c: the UBIFS file-system description object
  766. *
  767. * This function returns LEB number upon success and a negative error code upon
  768. * failure. In particular, -ENOSPC is returned if a dirty index LEB is not
  769. * found.
  770. *
  771. * Note that this function scans the entire LPT but it is called very rarely.
  772. */
  773. static int find_dirty_idx_leb(struct ubifs_info *c)
  774. {
  775. const struct ubifs_lprops *lprops;
  776. struct ubifs_lpt_heap *heap;
  777. struct scan_data data;
  778. int err, i, ret;
  779. /* Check all structures in memory first */
  780. data.lnum = -1;
  781. heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
  782. for (i = 0; i < heap->cnt; i++) {
  783. lprops = heap->arr[i];
  784. ret = scan_dirty_idx_cb(c, lprops, 1, &data);
  785. if (ret & LPT_SCAN_STOP)
  786. goto found;
  787. }
  788. list_for_each_entry(lprops, &c->frdi_idx_list, list) {
  789. ret = scan_dirty_idx_cb(c, lprops, 1, &data);
  790. if (ret & LPT_SCAN_STOP)
  791. goto found;
  792. }
  793. list_for_each_entry(lprops, &c->uncat_list, list) {
  794. ret = scan_dirty_idx_cb(c, lprops, 1, &data);
  795. if (ret & LPT_SCAN_STOP)
  796. goto found;
  797. }
  798. if (c->pnodes_have >= c->pnode_cnt)
  799. /* All pnodes are in memory, so skip scan */
  800. return -ENOSPC;
  801. err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
  802. (ubifs_lpt_scan_callback)scan_dirty_idx_cb,
  803. &data);
  804. if (err)
  805. return err;
  806. found:
  807. ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
  808. c->lscan_lnum = data.lnum;
  809. lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
  810. if (IS_ERR(lprops))
  811. return PTR_ERR(lprops);
  812. ubifs_assert(lprops->lnum == data.lnum);
  813. ubifs_assert(lprops->free + lprops->dirty >= c->min_idx_node_sz);
  814. ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
  815. ubifs_assert((lprops->flags & LPROPS_INDEX));
  816. dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x",
  817. lprops->lnum, lprops->free, lprops->dirty, lprops->flags);
  818. lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC,
  819. lprops->flags | LPROPS_TAKEN, 0);
  820. if (IS_ERR(lprops))
  821. return PTR_ERR(lprops);
  822. return lprops->lnum;
  823. }
  824. /**
  825. * get_idx_gc_leb - try to get a LEB number from trivial GC.
  826. * @c: the UBIFS file-system description object
  827. */
  828. static int get_idx_gc_leb(struct ubifs_info *c)
  829. {
  830. const struct ubifs_lprops *lp;
  831. int err, lnum;
  832. err = ubifs_get_idx_gc_leb(c);
  833. if (err < 0)
  834. return err;
  835. lnum = err;
  836. /*
  837. * The LEB was due to be unmapped after the commit but
  838. * it is needed now for this commit.
  839. */
  840. lp = ubifs_lpt_lookup_dirty(c, lnum);
  841. if (IS_ERR(lp))
  842. return PTR_ERR(lp);
  843. lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
  844. lp->flags | LPROPS_INDEX, -1);
  845. if (IS_ERR(lp))
  846. return PTR_ERR(lp);
  847. dbg_find("LEB %d, dirty %d and free %d flags %#x",
  848. lp->lnum, lp->dirty, lp->free, lp->flags);
  849. return lnum;
  850. }
  851. /**
  852. * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array.
  853. * @c: the UBIFS file-system description object
  854. */
  855. static int find_dirtiest_idx_leb(struct ubifs_info *c)
  856. {
  857. const struct ubifs_lprops *lp;
  858. int lnum;
  859. while (1) {
  860. if (!c->dirty_idx.cnt)
  861. return -ENOSPC;
  862. /* The lprops pointers were replaced by LEB numbers */
  863. lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt];
  864. lp = ubifs_lpt_lookup(c, lnum);
  865. if (IS_ERR(lp))
  866. return PTR_ERR(lp);
  867. if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX))
  868. continue;
  869. lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
  870. lp->flags | LPROPS_TAKEN, 0);
  871. if (IS_ERR(lp))
  872. return PTR_ERR(lp);
  873. break;
  874. }
  875. dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty,
  876. lp->free, lp->flags);
  877. ubifs_assert(lp->flags & LPROPS_TAKEN);
  878. ubifs_assert(lp->flags & LPROPS_INDEX);
  879. return lnum;
  880. }
  881. /**
  882. * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit.
  883. * @c: the UBIFS file-system description object
  884. *
  885. * This function attempts to find an untaken index LEB with the most free and
  886. * dirty space that can be used without overwriting index nodes that were in the
  887. * last index committed.
  888. */
  889. int ubifs_find_dirty_idx_leb(struct ubifs_info *c)
  890. {
  891. int err;
  892. ubifs_get_lprops(c);
  893. /*
  894. * We made an array of the dirtiest index LEB numbers as at the start of
  895. * last commit. Try that array first.
  896. */
  897. err = find_dirtiest_idx_leb(c);
  898. /* Next try scanning the entire LPT */
  899. if (err == -ENOSPC)
  900. err = find_dirty_idx_leb(c);
  901. /* Finally take any index LEBs awaiting trivial GC */
  902. if (err == -ENOSPC)
  903. err = get_idx_gc_leb(c);
  904. ubifs_release_lprops(c);
  905. return err;
  906. }