lprops.c 36 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321
  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: Adrian Hunter
  20. * Artem Bityutskiy (Битюцкий Артём)
  21. */
  22. /*
  23. * This file implements the functions that access LEB properties and their
  24. * categories. LEBs are categorized based on the needs of UBIFS, and the
  25. * categories are stored as either heaps or lists to provide a fast way of
  26. * finding a LEB in a particular category. For example, UBIFS may need to find
  27. * an empty LEB for the journal, or a very dirty LEB for garbage collection.
  28. */
  29. #include "ubifs.h"
  30. /**
  31. * get_heap_comp_val - get the LEB properties value for heap comparisons.
  32. * @lprops: LEB properties
  33. * @cat: LEB category
  34. */
  35. static int get_heap_comp_val(struct ubifs_lprops *lprops, int cat)
  36. {
  37. switch (cat) {
  38. case LPROPS_FREE:
  39. return lprops->free;
  40. case LPROPS_DIRTY_IDX:
  41. return lprops->free + lprops->dirty;
  42. default:
  43. return lprops->dirty;
  44. }
  45. }
  46. /**
  47. * move_up_lpt_heap - move a new heap entry up as far as possible.
  48. * @c: UBIFS file-system description object
  49. * @heap: LEB category heap
  50. * @lprops: LEB properties to move
  51. * @cat: LEB category
  52. *
  53. * New entries to a heap are added at the bottom and then moved up until the
  54. * parent's value is greater. In the case of LPT's category heaps, the value
  55. * is either the amount of free space or the amount of dirty space, depending
  56. * on the category.
  57. */
  58. static void move_up_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
  59. struct ubifs_lprops *lprops, int cat)
  60. {
  61. int val1, val2, hpos;
  62. hpos = lprops->hpos;
  63. if (!hpos)
  64. return; /* Already top of the heap */
  65. val1 = get_heap_comp_val(lprops, cat);
  66. /* Compare to parent and, if greater, move up the heap */
  67. do {
  68. int ppos = (hpos - 1) / 2;
  69. val2 = get_heap_comp_val(heap->arr[ppos], cat);
  70. if (val2 >= val1)
  71. return;
  72. /* Greater than parent so move up */
  73. heap->arr[ppos]->hpos = hpos;
  74. heap->arr[hpos] = heap->arr[ppos];
  75. heap->arr[ppos] = lprops;
  76. lprops->hpos = ppos;
  77. hpos = ppos;
  78. } while (hpos);
  79. }
  80. /**
  81. * adjust_lpt_heap - move a changed heap entry up or down the heap.
  82. * @c: UBIFS file-system description object
  83. * @heap: LEB category heap
  84. * @lprops: LEB properties to move
  85. * @hpos: heap position of @lprops
  86. * @cat: LEB category
  87. *
  88. * Changed entries in a heap are moved up or down until the parent's value is
  89. * greater. In the case of LPT's category heaps, the value is either the amount
  90. * of free space or the amount of dirty space, depending on the category.
  91. */
  92. static void adjust_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
  93. struct ubifs_lprops *lprops, int hpos, int cat)
  94. {
  95. int val1, val2, val3, cpos;
  96. val1 = get_heap_comp_val(lprops, cat);
  97. /* Compare to parent and, if greater than parent, move up the heap */
  98. if (hpos) {
  99. int ppos = (hpos - 1) / 2;
  100. val2 = get_heap_comp_val(heap->arr[ppos], cat);
  101. if (val1 > val2) {
  102. /* Greater than parent so move up */
  103. while (1) {
  104. heap->arr[ppos]->hpos = hpos;
  105. heap->arr[hpos] = heap->arr[ppos];
  106. heap->arr[ppos] = lprops;
  107. lprops->hpos = ppos;
  108. hpos = ppos;
  109. if (!hpos)
  110. return;
  111. ppos = (hpos - 1) / 2;
  112. val2 = get_heap_comp_val(heap->arr[ppos], cat);
  113. if (val1 <= val2)
  114. return;
  115. /* Still greater than parent so keep going */
  116. }
  117. }
  118. }
  119. /* Not greater than parent, so compare to children */
  120. while (1) {
  121. /* Compare to left child */
  122. cpos = hpos * 2 + 1;
  123. if (cpos >= heap->cnt)
  124. return;
  125. val2 = get_heap_comp_val(heap->arr[cpos], cat);
  126. if (val1 < val2) {
  127. /* Less than left child, so promote biggest child */
  128. if (cpos + 1 < heap->cnt) {
  129. val3 = get_heap_comp_val(heap->arr[cpos + 1],
  130. cat);
  131. if (val3 > val2)
  132. cpos += 1; /* Right child is bigger */
  133. }
  134. heap->arr[cpos]->hpos = hpos;
  135. heap->arr[hpos] = heap->arr[cpos];
  136. heap->arr[cpos] = lprops;
  137. lprops->hpos = cpos;
  138. hpos = cpos;
  139. continue;
  140. }
  141. /* Compare to right child */
  142. cpos += 1;
  143. if (cpos >= heap->cnt)
  144. return;
  145. val3 = get_heap_comp_val(heap->arr[cpos], cat);
  146. if (val1 < val3) {
  147. /* Less than right child, so promote right child */
  148. heap->arr[cpos]->hpos = hpos;
  149. heap->arr[hpos] = heap->arr[cpos];
  150. heap->arr[cpos] = lprops;
  151. lprops->hpos = cpos;
  152. hpos = cpos;
  153. continue;
  154. }
  155. return;
  156. }
  157. }
  158. /**
  159. * add_to_lpt_heap - add LEB properties to a LEB category heap.
  160. * @c: UBIFS file-system description object
  161. * @lprops: LEB properties to add
  162. * @cat: LEB category
  163. *
  164. * This function returns %1 if @lprops is added to the heap for LEB category
  165. * @cat, otherwise %0 is returned because the heap is full.
  166. */
  167. static int add_to_lpt_heap(struct ubifs_info *c, struct ubifs_lprops *lprops,
  168. int cat)
  169. {
  170. struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];
  171. if (heap->cnt >= heap->max_cnt) {
  172. const int b = LPT_HEAP_SZ / 2 - 1;
  173. int cpos, val1, val2;
  174. /* Compare to some other LEB on the bottom of heap */
  175. /* Pick a position kind of randomly */
  176. cpos = (((size_t)lprops >> 4) & b) + b;
  177. ubifs_assert(cpos >= b);
  178. ubifs_assert(cpos < LPT_HEAP_SZ);
  179. ubifs_assert(cpos < heap->cnt);
  180. val1 = get_heap_comp_val(lprops, cat);
  181. val2 = get_heap_comp_val(heap->arr[cpos], cat);
  182. if (val1 > val2) {
  183. struct ubifs_lprops *lp;
  184. lp = heap->arr[cpos];
  185. lp->flags &= ~LPROPS_CAT_MASK;
  186. lp->flags |= LPROPS_UNCAT;
  187. list_add(&lp->list, &c->uncat_list);
  188. lprops->hpos = cpos;
  189. heap->arr[cpos] = lprops;
  190. move_up_lpt_heap(c, heap, lprops, cat);
  191. dbg_check_heap(c, heap, cat, lprops->hpos);
  192. return 1; /* Added to heap */
  193. }
  194. dbg_check_heap(c, heap, cat, -1);
  195. return 0; /* Not added to heap */
  196. } else {
  197. lprops->hpos = heap->cnt++;
  198. heap->arr[lprops->hpos] = lprops;
  199. move_up_lpt_heap(c, heap, lprops, cat);
  200. dbg_check_heap(c, heap, cat, lprops->hpos);
  201. return 1; /* Added to heap */
  202. }
  203. }
  204. /**
  205. * remove_from_lpt_heap - remove LEB properties from a LEB category heap.
  206. * @c: UBIFS file-system description object
  207. * @lprops: LEB properties to remove
  208. * @cat: LEB category
  209. */
  210. static void remove_from_lpt_heap(struct ubifs_info *c,
  211. struct ubifs_lprops *lprops, int cat)
  212. {
  213. struct ubifs_lpt_heap *heap;
  214. int hpos = lprops->hpos;
  215. heap = &c->lpt_heap[cat - 1];
  216. ubifs_assert(hpos >= 0 && hpos < heap->cnt);
  217. ubifs_assert(heap->arr[hpos] == lprops);
  218. heap->cnt -= 1;
  219. if (hpos < heap->cnt) {
  220. heap->arr[hpos] = heap->arr[heap->cnt];
  221. heap->arr[hpos]->hpos = hpos;
  222. adjust_lpt_heap(c, heap, heap->arr[hpos], hpos, cat);
  223. }
  224. dbg_check_heap(c, heap, cat, -1);
  225. }
  226. /**
  227. * lpt_heap_replace - replace lprops in a category heap.
  228. * @c: UBIFS file-system description object
  229. * @old_lprops: LEB properties to replace
  230. * @new_lprops: LEB properties with which to replace
  231. * @cat: LEB category
  232. *
  233. * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode)
  234. * and the lprops that the pnode contains. When that happens, references in
  235. * the category heaps to those lprops must be updated to point to the new
  236. * lprops. This function does that.
  237. */
  238. static void lpt_heap_replace(struct ubifs_info *c,
  239. struct ubifs_lprops *old_lprops,
  240. struct ubifs_lprops *new_lprops, int cat)
  241. {
  242. struct ubifs_lpt_heap *heap;
  243. int hpos = new_lprops->hpos;
  244. heap = &c->lpt_heap[cat - 1];
  245. heap->arr[hpos] = new_lprops;
  246. }
  247. /**
  248. * ubifs_add_to_cat - add LEB properties to a category list or heap.
  249. * @c: UBIFS file-system description object
  250. * @lprops: LEB properties to add
  251. * @cat: LEB category to which to add
  252. *
  253. * LEB properties are categorized to enable fast find operations.
  254. */
  255. void ubifs_add_to_cat(struct ubifs_info *c, struct ubifs_lprops *lprops,
  256. int cat)
  257. {
  258. switch (cat) {
  259. case LPROPS_DIRTY:
  260. case LPROPS_DIRTY_IDX:
  261. case LPROPS_FREE:
  262. if (add_to_lpt_heap(c, lprops, cat))
  263. break;
  264. /* No more room on heap so make it un-categorized */
  265. cat = LPROPS_UNCAT;
  266. /* Fall through */
  267. case LPROPS_UNCAT:
  268. list_add(&lprops->list, &c->uncat_list);
  269. break;
  270. case LPROPS_EMPTY:
  271. list_add(&lprops->list, &c->empty_list);
  272. break;
  273. case LPROPS_FREEABLE:
  274. list_add(&lprops->list, &c->freeable_list);
  275. c->freeable_cnt += 1;
  276. break;
  277. case LPROPS_FRDI_IDX:
  278. list_add(&lprops->list, &c->frdi_idx_list);
  279. break;
  280. default:
  281. ubifs_assert(0);
  282. }
  283. lprops->flags &= ~LPROPS_CAT_MASK;
  284. lprops->flags |= cat;
  285. c->in_a_category_cnt += 1;
  286. ubifs_assert(c->in_a_category_cnt <= c->main_lebs);
  287. }
  288. /**
  289. * ubifs_remove_from_cat - remove LEB properties from a category list or heap.
  290. * @c: UBIFS file-system description object
  291. * @lprops: LEB properties to remove
  292. * @cat: LEB category from which to remove
  293. *
  294. * LEB properties are categorized to enable fast find operations.
  295. */
  296. static void ubifs_remove_from_cat(struct ubifs_info *c,
  297. struct ubifs_lprops *lprops, int cat)
  298. {
  299. switch (cat) {
  300. case LPROPS_DIRTY:
  301. case LPROPS_DIRTY_IDX:
  302. case LPROPS_FREE:
  303. remove_from_lpt_heap(c, lprops, cat);
  304. break;
  305. case LPROPS_FREEABLE:
  306. c->freeable_cnt -= 1;
  307. ubifs_assert(c->freeable_cnt >= 0);
  308. /* Fall through */
  309. case LPROPS_UNCAT:
  310. case LPROPS_EMPTY:
  311. case LPROPS_FRDI_IDX:
  312. ubifs_assert(!list_empty(&lprops->list));
  313. list_del(&lprops->list);
  314. break;
  315. default:
  316. ubifs_assert(0);
  317. }
  318. c->in_a_category_cnt -= 1;
  319. ubifs_assert(c->in_a_category_cnt >= 0);
  320. }
  321. /**
  322. * ubifs_replace_cat - replace lprops in a category list or heap.
  323. * @c: UBIFS file-system description object
  324. * @old_lprops: LEB properties to replace
  325. * @new_lprops: LEB properties with which to replace
  326. *
  327. * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode)
  328. * and the lprops that the pnode contains. When that happens, references in
  329. * category lists and heaps must be replaced. This function does that.
  330. */
  331. void ubifs_replace_cat(struct ubifs_info *c, struct ubifs_lprops *old_lprops,
  332. struct ubifs_lprops *new_lprops)
  333. {
  334. int cat;
  335. cat = new_lprops->flags & LPROPS_CAT_MASK;
  336. switch (cat) {
  337. case LPROPS_DIRTY:
  338. case LPROPS_DIRTY_IDX:
  339. case LPROPS_FREE:
  340. lpt_heap_replace(c, old_lprops, new_lprops, cat);
  341. break;
  342. case LPROPS_UNCAT:
  343. case LPROPS_EMPTY:
  344. case LPROPS_FREEABLE:
  345. case LPROPS_FRDI_IDX:
  346. list_replace(&old_lprops->list, &new_lprops->list);
  347. break;
  348. default:
  349. ubifs_assert(0);
  350. }
  351. }
  352. /**
  353. * ubifs_ensure_cat - ensure LEB properties are categorized.
  354. * @c: UBIFS file-system description object
  355. * @lprops: LEB properties
  356. *
  357. * A LEB may have fallen off of the bottom of a heap, and ended up as
  358. * un-categorized even though it has enough space for us now. If that is the
  359. * case this function will put the LEB back onto a heap.
  360. */
  361. void ubifs_ensure_cat(struct ubifs_info *c, struct ubifs_lprops *lprops)
  362. {
  363. int cat = lprops->flags & LPROPS_CAT_MASK;
  364. if (cat != LPROPS_UNCAT)
  365. return;
  366. cat = ubifs_categorize_lprops(c, lprops);
  367. if (cat == LPROPS_UNCAT)
  368. return;
  369. ubifs_remove_from_cat(c, lprops, LPROPS_UNCAT);
  370. ubifs_add_to_cat(c, lprops, cat);
  371. }
  372. /**
  373. * ubifs_categorize_lprops - categorize LEB properties.
  374. * @c: UBIFS file-system description object
  375. * @lprops: LEB properties to categorize
  376. *
  377. * LEB properties are categorized to enable fast find operations. This function
  378. * returns the LEB category to which the LEB properties belong. Note however
  379. * that if the LEB category is stored as a heap and the heap is full, the
  380. * LEB properties may have their category changed to %LPROPS_UNCAT.
  381. */
  382. int ubifs_categorize_lprops(const struct ubifs_info *c,
  383. const struct ubifs_lprops *lprops)
  384. {
  385. if (lprops->flags & LPROPS_TAKEN)
  386. return LPROPS_UNCAT;
  387. if (lprops->free == c->leb_size) {
  388. ubifs_assert(!(lprops->flags & LPROPS_INDEX));
  389. return LPROPS_EMPTY;
  390. }
  391. if (lprops->free + lprops->dirty == c->leb_size) {
  392. if (lprops->flags & LPROPS_INDEX)
  393. return LPROPS_FRDI_IDX;
  394. else
  395. return LPROPS_FREEABLE;
  396. }
  397. if (lprops->flags & LPROPS_INDEX) {
  398. if (lprops->dirty + lprops->free >= c->min_idx_node_sz)
  399. return LPROPS_DIRTY_IDX;
  400. } else {
  401. if (lprops->dirty >= c->dead_wm &&
  402. lprops->dirty > lprops->free)
  403. return LPROPS_DIRTY;
  404. if (lprops->free > 0)
  405. return LPROPS_FREE;
  406. }
  407. return LPROPS_UNCAT;
  408. }
  409. /**
  410. * change_category - change LEB properties category.
  411. * @c: UBIFS file-system description object
  412. * @lprops: LEB properties to re-categorize
  413. *
  414. * LEB properties are categorized to enable fast find operations. When the LEB
  415. * properties change they must be re-categorized.
  416. */
  417. static void change_category(struct ubifs_info *c, struct ubifs_lprops *lprops)
  418. {
  419. int old_cat = lprops->flags & LPROPS_CAT_MASK;
  420. int new_cat = ubifs_categorize_lprops(c, lprops);
  421. if (old_cat == new_cat) {
  422. struct ubifs_lpt_heap *heap;
  423. /* lprops on a heap now must be moved up or down */
  424. if (new_cat < 1 || new_cat > LPROPS_HEAP_CNT)
  425. return; /* Not on a heap */
  426. heap = &c->lpt_heap[new_cat - 1];
  427. adjust_lpt_heap(c, heap, lprops, lprops->hpos, new_cat);
  428. } else {
  429. ubifs_remove_from_cat(c, lprops, old_cat);
  430. ubifs_add_to_cat(c, lprops, new_cat);
  431. }
  432. }
  433. /**
  434. * ubifs_calc_dark - calculate LEB dark space size.
  435. * @c: the UBIFS file-system description object
  436. * @spc: amount of free and dirty space in the LEB
  437. *
  438. * This function calculates and returns amount of dark space in an LEB which
  439. * has @spc bytes of free and dirty space.
  440. *
  441. * UBIFS is trying to account the space which might not be usable, and this
  442. * space is called "dark space". For example, if an LEB has only %512 free
  443. * bytes, it is dark space, because it cannot fit a large data node.
  444. */
  445. int ubifs_calc_dark(const struct ubifs_info *c, int spc)
  446. {
  447. ubifs_assert(!(spc & 7));
  448. if (spc < c->dark_wm)
  449. return spc;
  450. /*
  451. * If we have slightly more space then the dark space watermark, we can
  452. * anyway safely assume it we'll be able to write a node of the
  453. * smallest size there.
  454. */
  455. if (spc - c->dark_wm < MIN_WRITE_SZ)
  456. return spc - MIN_WRITE_SZ;
  457. return c->dark_wm;
  458. }
  459. /**
  460. * is_lprops_dirty - determine if LEB properties are dirty.
  461. * @c: the UBIFS file-system description object
  462. * @lprops: LEB properties to test
  463. */
  464. static int is_lprops_dirty(struct ubifs_info *c, struct ubifs_lprops *lprops)
  465. {
  466. struct ubifs_pnode *pnode;
  467. int pos;
  468. pos = (lprops->lnum - c->main_first) & (UBIFS_LPT_FANOUT - 1);
  469. pnode = (struct ubifs_pnode *)container_of(lprops - pos,
  470. struct ubifs_pnode,
  471. lprops[0]);
  472. return !test_bit(COW_CNODE, &pnode->flags) &&
  473. test_bit(DIRTY_CNODE, &pnode->flags);
  474. }
  475. /**
  476. * ubifs_change_lp - change LEB properties.
  477. * @c: the UBIFS file-system description object
  478. * @lp: LEB properties to change
  479. * @free: new free space amount
  480. * @dirty: new dirty space amount
  481. * @flags: new flags
  482. * @idx_gc_cnt: change to the count of @idx_gc list
  483. *
  484. * This function changes LEB properties (@free, @dirty or @flag). However, the
  485. * property which has the %LPROPS_NC value is not changed. Returns a pointer to
  486. * the updated LEB properties on success and a negative error code on failure.
  487. *
  488. * Note, the LEB properties may have had to be copied (due to COW) and
  489. * consequently the pointer returned may not be the same as the pointer
  490. * passed.
  491. */
  492. const struct ubifs_lprops *ubifs_change_lp(struct ubifs_info *c,
  493. const struct ubifs_lprops *lp,
  494. int free, int dirty, int flags,
  495. int idx_gc_cnt)
  496. {
  497. /*
  498. * This is the only function that is allowed to change lprops, so we
  499. * discard the "const" qualifier.
  500. */
  501. struct ubifs_lprops *lprops = (struct ubifs_lprops *)lp;
  502. dbg_lp("LEB %d, free %d, dirty %d, flags %d",
  503. lprops->lnum, free, dirty, flags);
  504. ubifs_assert(mutex_is_locked(&c->lp_mutex));
  505. ubifs_assert(c->lst.empty_lebs >= 0 &&
  506. c->lst.empty_lebs <= c->main_lebs);
  507. ubifs_assert(c->freeable_cnt >= 0);
  508. ubifs_assert(c->freeable_cnt <= c->main_lebs);
  509. ubifs_assert(c->lst.taken_empty_lebs >= 0);
  510. ubifs_assert(c->lst.taken_empty_lebs <= c->lst.empty_lebs);
  511. ubifs_assert(!(c->lst.total_free & 7) && !(c->lst.total_dirty & 7));
  512. ubifs_assert(!(c->lst.total_dead & 7) && !(c->lst.total_dark & 7));
  513. ubifs_assert(!(c->lst.total_used & 7));
  514. ubifs_assert(free == LPROPS_NC || free >= 0);
  515. ubifs_assert(dirty == LPROPS_NC || dirty >= 0);
  516. if (!is_lprops_dirty(c, lprops)) {
  517. lprops = ubifs_lpt_lookup_dirty(c, lprops->lnum);
  518. if (IS_ERR(lprops))
  519. return lprops;
  520. } else
  521. ubifs_assert(lprops == ubifs_lpt_lookup_dirty(c, lprops->lnum));
  522. ubifs_assert(!(lprops->free & 7) && !(lprops->dirty & 7));
  523. spin_lock(&c->space_lock);
  524. if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)
  525. c->lst.taken_empty_lebs -= 1;
  526. if (!(lprops->flags & LPROPS_INDEX)) {
  527. int old_spc;
  528. old_spc = lprops->free + lprops->dirty;
  529. if (old_spc < c->dead_wm)
  530. c->lst.total_dead -= old_spc;
  531. else
  532. c->lst.total_dark -= ubifs_calc_dark(c, old_spc);
  533. c->lst.total_used -= c->leb_size - old_spc;
  534. }
  535. if (free != LPROPS_NC) {
  536. free = ALIGN(free, 8);
  537. c->lst.total_free += free - lprops->free;
  538. /* Increase or decrease empty LEBs counter if needed */
  539. if (free == c->leb_size) {
  540. if (lprops->free != c->leb_size)
  541. c->lst.empty_lebs += 1;
  542. } else if (lprops->free == c->leb_size)
  543. c->lst.empty_lebs -= 1;
  544. lprops->free = free;
  545. }
  546. if (dirty != LPROPS_NC) {
  547. dirty = ALIGN(dirty, 8);
  548. c->lst.total_dirty += dirty - lprops->dirty;
  549. lprops->dirty = dirty;
  550. }
  551. if (flags != LPROPS_NC) {
  552. /* Take care about indexing LEBs counter if needed */
  553. if ((lprops->flags & LPROPS_INDEX)) {
  554. if (!(flags & LPROPS_INDEX))
  555. c->lst.idx_lebs -= 1;
  556. } else if (flags & LPROPS_INDEX)
  557. c->lst.idx_lebs += 1;
  558. lprops->flags = flags;
  559. }
  560. if (!(lprops->flags & LPROPS_INDEX)) {
  561. int new_spc;
  562. new_spc = lprops->free + lprops->dirty;
  563. if (new_spc < c->dead_wm)
  564. c->lst.total_dead += new_spc;
  565. else
  566. c->lst.total_dark += ubifs_calc_dark(c, new_spc);
  567. c->lst.total_used += c->leb_size - new_spc;
  568. }
  569. if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)
  570. c->lst.taken_empty_lebs += 1;
  571. change_category(c, lprops);
  572. c->idx_gc_cnt += idx_gc_cnt;
  573. spin_unlock(&c->space_lock);
  574. return lprops;
  575. }
  576. /**
  577. * ubifs_get_lp_stats - get lprops statistics.
  578. * @c: UBIFS file-system description object
  579. * @st: return statistics
  580. */
  581. void ubifs_get_lp_stats(struct ubifs_info *c, struct ubifs_lp_stats *lst)
  582. {
  583. spin_lock(&c->space_lock);
  584. memcpy(lst, &c->lst, sizeof(struct ubifs_lp_stats));
  585. spin_unlock(&c->space_lock);
  586. }
  587. /**
  588. * ubifs_change_one_lp - change LEB properties.
  589. * @c: the UBIFS file-system description object
  590. * @lnum: LEB to change properties for
  591. * @free: amount of free space
  592. * @dirty: amount of dirty space
  593. * @flags_set: flags to set
  594. * @flags_clean: flags to clean
  595. * @idx_gc_cnt: change to the count of idx_gc list
  596. *
  597. * This function changes properties of LEB @lnum. It is a helper wrapper over
  598. * 'ubifs_change_lp()' which hides lprops get/release. The arguments are the
  599. * same as in case of 'ubifs_change_lp()'. Returns zero in case of success and
  600. * a negative error code in case of failure.
  601. */
  602. int ubifs_change_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,
  603. int flags_set, int flags_clean, int idx_gc_cnt)
  604. {
  605. int err = 0, flags;
  606. const struct ubifs_lprops *lp;
  607. ubifs_get_lprops(c);
  608. lp = ubifs_lpt_lookup_dirty(c, lnum);
  609. if (IS_ERR(lp)) {
  610. err = PTR_ERR(lp);
  611. goto out;
  612. }
  613. flags = (lp->flags | flags_set) & ~flags_clean;
  614. lp = ubifs_change_lp(c, lp, free, dirty, flags, idx_gc_cnt);
  615. if (IS_ERR(lp))
  616. err = PTR_ERR(lp);
  617. out:
  618. ubifs_release_lprops(c);
  619. if (err)
  620. ubifs_err(c, "cannot change properties of LEB %d, error %d",
  621. lnum, err);
  622. return err;
  623. }
  624. /**
  625. * ubifs_update_one_lp - update LEB properties.
  626. * @c: the UBIFS file-system description object
  627. * @lnum: LEB to change properties for
  628. * @free: amount of free space
  629. * @dirty: amount of dirty space to add
  630. * @flags_set: flags to set
  631. * @flags_clean: flags to clean
  632. *
  633. * This function is the same as 'ubifs_change_one_lp()' but @dirty is added to
  634. * current dirty space, not substitutes it.
  635. */
  636. int ubifs_update_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,
  637. int flags_set, int flags_clean)
  638. {
  639. int err = 0, flags;
  640. const struct ubifs_lprops *lp;
  641. ubifs_get_lprops(c);
  642. lp = ubifs_lpt_lookup_dirty(c, lnum);
  643. if (IS_ERR(lp)) {
  644. err = PTR_ERR(lp);
  645. goto out;
  646. }
  647. flags = (lp->flags | flags_set) & ~flags_clean;
  648. lp = ubifs_change_lp(c, lp, free, lp->dirty + dirty, flags, 0);
  649. if (IS_ERR(lp))
  650. err = PTR_ERR(lp);
  651. out:
  652. ubifs_release_lprops(c);
  653. if (err)
  654. ubifs_err(c, "cannot update properties of LEB %d, error %d",
  655. lnum, err);
  656. return err;
  657. }
  658. /**
  659. * ubifs_read_one_lp - read LEB properties.
  660. * @c: the UBIFS file-system description object
  661. * @lnum: LEB to read properties for
  662. * @lp: where to store read properties
  663. *
  664. * This helper function reads properties of a LEB @lnum and stores them in @lp.
  665. * Returns zero in case of success and a negative error code in case of
  666. * failure.
  667. */
  668. int ubifs_read_one_lp(struct ubifs_info *c, int lnum, struct ubifs_lprops *lp)
  669. {
  670. int err = 0;
  671. const struct ubifs_lprops *lpp;
  672. ubifs_get_lprops(c);
  673. lpp = ubifs_lpt_lookup(c, lnum);
  674. if (IS_ERR(lpp)) {
  675. err = PTR_ERR(lpp);
  676. ubifs_err(c, "cannot read properties of LEB %d, error %d",
  677. lnum, err);
  678. goto out;
  679. }
  680. memcpy(lp, lpp, sizeof(struct ubifs_lprops));
  681. out:
  682. ubifs_release_lprops(c);
  683. return err;
  684. }
  685. /**
  686. * ubifs_fast_find_free - try to find a LEB with free space quickly.
  687. * @c: the UBIFS file-system description object
  688. *
  689. * This function returns LEB properties for a LEB with free space or %NULL if
  690. * the function is unable to find a LEB quickly.
  691. */
  692. const struct ubifs_lprops *ubifs_fast_find_free(struct ubifs_info *c)
  693. {
  694. struct ubifs_lprops *lprops;
  695. struct ubifs_lpt_heap *heap;
  696. ubifs_assert(mutex_is_locked(&c->lp_mutex));
  697. heap = &c->lpt_heap[LPROPS_FREE - 1];
  698. if (heap->cnt == 0)
  699. return NULL;
  700. lprops = heap->arr[0];
  701. ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
  702. ubifs_assert(!(lprops->flags & LPROPS_INDEX));
  703. return lprops;
  704. }
  705. /**
  706. * ubifs_fast_find_empty - try to find an empty LEB quickly.
  707. * @c: the UBIFS file-system description object
  708. *
  709. * This function returns LEB properties for an empty LEB or %NULL if the
  710. * function is unable to find an empty LEB quickly.
  711. */
  712. const struct ubifs_lprops *ubifs_fast_find_empty(struct ubifs_info *c)
  713. {
  714. struct ubifs_lprops *lprops;
  715. ubifs_assert(mutex_is_locked(&c->lp_mutex));
  716. if (list_empty(&c->empty_list))
  717. return NULL;
  718. lprops = list_entry(c->empty_list.next, struct ubifs_lprops, list);
  719. ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
  720. ubifs_assert(!(lprops->flags & LPROPS_INDEX));
  721. ubifs_assert(lprops->free == c->leb_size);
  722. return lprops;
  723. }
  724. /**
  725. * ubifs_fast_find_freeable - try to find a freeable LEB quickly.
  726. * @c: the UBIFS file-system description object
  727. *
  728. * This function returns LEB properties for a freeable LEB or %NULL if the
  729. * function is unable to find a freeable LEB quickly.
  730. */
  731. const struct ubifs_lprops *ubifs_fast_find_freeable(struct ubifs_info *c)
  732. {
  733. struct ubifs_lprops *lprops;
  734. ubifs_assert(mutex_is_locked(&c->lp_mutex));
  735. if (list_empty(&c->freeable_list))
  736. return NULL;
  737. lprops = list_entry(c->freeable_list.next, struct ubifs_lprops, list);
  738. ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
  739. ubifs_assert(!(lprops->flags & LPROPS_INDEX));
  740. ubifs_assert(lprops->free + lprops->dirty == c->leb_size);
  741. ubifs_assert(c->freeable_cnt > 0);
  742. return lprops;
  743. }
  744. /**
  745. * ubifs_fast_find_frdi_idx - try to find a freeable index LEB quickly.
  746. * @c: the UBIFS file-system description object
  747. *
  748. * This function returns LEB properties for a freeable index LEB or %NULL if the
  749. * function is unable to find a freeable index LEB quickly.
  750. */
  751. const struct ubifs_lprops *ubifs_fast_find_frdi_idx(struct ubifs_info *c)
  752. {
  753. struct ubifs_lprops *lprops;
  754. ubifs_assert(mutex_is_locked(&c->lp_mutex));
  755. if (list_empty(&c->frdi_idx_list))
  756. return NULL;
  757. lprops = list_entry(c->frdi_idx_list.next, struct ubifs_lprops, list);
  758. ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
  759. ubifs_assert((lprops->flags & LPROPS_INDEX));
  760. ubifs_assert(lprops->free + lprops->dirty == c->leb_size);
  761. return lprops;
  762. }
  763. /*
  764. * Everything below is related to debugging.
  765. */
  766. /**
  767. * dbg_check_cats - check category heaps and lists.
  768. * @c: UBIFS file-system description object
  769. *
  770. * This function returns %0 on success and a negative error code on failure.
  771. */
  772. int dbg_check_cats(struct ubifs_info *c)
  773. {
  774. struct ubifs_lprops *lprops;
  775. struct list_head *pos;
  776. int i, cat;
  777. if (!dbg_is_chk_gen(c) && !dbg_is_chk_lprops(c))
  778. return 0;
  779. list_for_each_entry(lprops, &c->empty_list, list) {
  780. if (lprops->free != c->leb_size) {
  781. ubifs_err(c, "non-empty LEB %d on empty list (free %d dirty %d flags %d)",
  782. lprops->lnum, lprops->free, lprops->dirty,
  783. lprops->flags);
  784. return -EINVAL;
  785. }
  786. if (lprops->flags & LPROPS_TAKEN) {
  787. ubifs_err(c, "taken LEB %d on empty list (free %d dirty %d flags %d)",
  788. lprops->lnum, lprops->free, lprops->dirty,
  789. lprops->flags);
  790. return -EINVAL;
  791. }
  792. }
  793. i = 0;
  794. list_for_each_entry(lprops, &c->freeable_list, list) {
  795. if (lprops->free + lprops->dirty != c->leb_size) {
  796. ubifs_err(c, "non-freeable LEB %d on freeable list (free %d dirty %d flags %d)",
  797. lprops->lnum, lprops->free, lprops->dirty,
  798. lprops->flags);
  799. return -EINVAL;
  800. }
  801. if (lprops->flags & LPROPS_TAKEN) {
  802. ubifs_err(c, "taken LEB %d on freeable list (free %d dirty %d flags %d)",
  803. lprops->lnum, lprops->free, lprops->dirty,
  804. lprops->flags);
  805. return -EINVAL;
  806. }
  807. i += 1;
  808. }
  809. if (i != c->freeable_cnt) {
  810. ubifs_err(c, "freeable list count %d expected %d", i,
  811. c->freeable_cnt);
  812. return -EINVAL;
  813. }
  814. i = 0;
  815. list_for_each(pos, &c->idx_gc)
  816. i += 1;
  817. if (i != c->idx_gc_cnt) {
  818. ubifs_err(c, "idx_gc list count %d expected %d", i,
  819. c->idx_gc_cnt);
  820. return -EINVAL;
  821. }
  822. list_for_each_entry(lprops, &c->frdi_idx_list, list) {
  823. if (lprops->free + lprops->dirty != c->leb_size) {
  824. ubifs_err(c, "non-freeable LEB %d on frdi_idx list (free %d dirty %d flags %d)",
  825. lprops->lnum, lprops->free, lprops->dirty,
  826. lprops->flags);
  827. return -EINVAL;
  828. }
  829. if (lprops->flags & LPROPS_TAKEN) {
  830. ubifs_err(c, "taken LEB %d on frdi_idx list (free %d dirty %d flags %d)",
  831. lprops->lnum, lprops->free, lprops->dirty,
  832. lprops->flags);
  833. return -EINVAL;
  834. }
  835. if (!(lprops->flags & LPROPS_INDEX)) {
  836. ubifs_err(c, "non-index LEB %d on frdi_idx list (free %d dirty %d flags %d)",
  837. lprops->lnum, lprops->free, lprops->dirty,
  838. lprops->flags);
  839. return -EINVAL;
  840. }
  841. }
  842. for (cat = 1; cat <= LPROPS_HEAP_CNT; cat++) {
  843. struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];
  844. for (i = 0; i < heap->cnt; i++) {
  845. lprops = heap->arr[i];
  846. if (!lprops) {
  847. ubifs_err(c, "null ptr in LPT heap cat %d", cat);
  848. return -EINVAL;
  849. }
  850. if (lprops->hpos != i) {
  851. ubifs_err(c, "bad ptr in LPT heap cat %d", cat);
  852. return -EINVAL;
  853. }
  854. if (lprops->flags & LPROPS_TAKEN) {
  855. ubifs_err(c, "taken LEB in LPT heap cat %d", cat);
  856. return -EINVAL;
  857. }
  858. }
  859. }
  860. return 0;
  861. }
  862. void dbg_check_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap, int cat,
  863. int add_pos)
  864. {
  865. int i = 0, j, err = 0;
  866. if (!dbg_is_chk_gen(c) && !dbg_is_chk_lprops(c))
  867. return;
  868. for (i = 0; i < heap->cnt; i++) {
  869. struct ubifs_lprops *lprops = heap->arr[i];
  870. struct ubifs_lprops *lp;
  871. if (i != add_pos)
  872. if ((lprops->flags & LPROPS_CAT_MASK) != cat) {
  873. err = 1;
  874. goto out;
  875. }
  876. if (lprops->hpos != i) {
  877. err = 2;
  878. goto out;
  879. }
  880. lp = ubifs_lpt_lookup(c, lprops->lnum);
  881. if (IS_ERR(lp)) {
  882. err = 3;
  883. goto out;
  884. }
  885. if (lprops != lp) {
  886. ubifs_err(c, "lprops %zx lp %zx lprops->lnum %d lp->lnum %d",
  887. (size_t)lprops, (size_t)lp, lprops->lnum,
  888. lp->lnum);
  889. err = 4;
  890. goto out;
  891. }
  892. for (j = 0; j < i; j++) {
  893. lp = heap->arr[j];
  894. if (lp == lprops) {
  895. err = 5;
  896. goto out;
  897. }
  898. if (lp->lnum == lprops->lnum) {
  899. err = 6;
  900. goto out;
  901. }
  902. }
  903. }
  904. out:
  905. if (err) {
  906. ubifs_err(c, "failed cat %d hpos %d err %d", cat, i, err);
  907. dump_stack();
  908. ubifs_dump_heap(c, heap, cat);
  909. }
  910. }
  911. /**
  912. * scan_check_cb - scan callback.
  913. * @c: the UBIFS file-system description object
  914. * @lp: LEB properties to scan
  915. * @in_tree: whether the LEB properties are in main memory
  916. * @lst: lprops statistics to update
  917. *
  918. * This function returns a code that indicates whether the scan should continue
  919. * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
  920. * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
  921. * (%LPT_SCAN_STOP).
  922. */
  923. static int scan_check_cb(struct ubifs_info *c,
  924. const struct ubifs_lprops *lp, int in_tree,
  925. struct ubifs_lp_stats *lst)
  926. {
  927. struct ubifs_scan_leb *sleb;
  928. struct ubifs_scan_node *snod;
  929. int cat, lnum = lp->lnum, is_idx = 0, used = 0, free, dirty, ret;
  930. void *buf = NULL;
  931. cat = lp->flags & LPROPS_CAT_MASK;
  932. if (cat != LPROPS_UNCAT) {
  933. cat = ubifs_categorize_lprops(c, lp);
  934. if (cat != (lp->flags & LPROPS_CAT_MASK)) {
  935. ubifs_err(c, "bad LEB category %d expected %d",
  936. (lp->flags & LPROPS_CAT_MASK), cat);
  937. return -EINVAL;
  938. }
  939. }
  940. /* Check lp is on its category list (if it has one) */
  941. if (in_tree) {
  942. struct list_head *list = NULL;
  943. switch (cat) {
  944. case LPROPS_EMPTY:
  945. list = &c->empty_list;
  946. break;
  947. case LPROPS_FREEABLE:
  948. list = &c->freeable_list;
  949. break;
  950. case LPROPS_FRDI_IDX:
  951. list = &c->frdi_idx_list;
  952. break;
  953. case LPROPS_UNCAT:
  954. list = &c->uncat_list;
  955. break;
  956. }
  957. if (list) {
  958. struct ubifs_lprops *lprops;
  959. int found = 0;
  960. list_for_each_entry(lprops, list, list) {
  961. if (lprops == lp) {
  962. found = 1;
  963. break;
  964. }
  965. }
  966. if (!found) {
  967. ubifs_err(c, "bad LPT list (category %d)", cat);
  968. return -EINVAL;
  969. }
  970. }
  971. }
  972. /* Check lp is on its category heap (if it has one) */
  973. if (in_tree && cat > 0 && cat <= LPROPS_HEAP_CNT) {
  974. struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];
  975. if ((lp->hpos != -1 && heap->arr[lp->hpos]->lnum != lnum) ||
  976. lp != heap->arr[lp->hpos]) {
  977. ubifs_err(c, "bad LPT heap (category %d)", cat);
  978. return -EINVAL;
  979. }
  980. }
  981. /*
  982. * After an unclean unmount, empty and freeable LEBs
  983. * may contain garbage - do not scan them.
  984. */
  985. if (lp->free == c->leb_size) {
  986. lst->empty_lebs += 1;
  987. lst->total_free += c->leb_size;
  988. lst->total_dark += ubifs_calc_dark(c, c->leb_size);
  989. return LPT_SCAN_CONTINUE;
  990. }
  991. if (lp->free + lp->dirty == c->leb_size &&
  992. !(lp->flags & LPROPS_INDEX)) {
  993. lst->total_free += lp->free;
  994. lst->total_dirty += lp->dirty;
  995. lst->total_dark += ubifs_calc_dark(c, c->leb_size);
  996. return LPT_SCAN_CONTINUE;
  997. }
  998. buf = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
  999. if (!buf)
  1000. return -ENOMEM;
  1001. sleb = ubifs_scan(c, lnum, 0, buf, 0);
  1002. if (IS_ERR(sleb)) {
  1003. ret = PTR_ERR(sleb);
  1004. if (ret == -EUCLEAN) {
  1005. ubifs_dump_lprops(c);
  1006. ubifs_dump_budg(c, &c->bi);
  1007. }
  1008. goto out;
  1009. }
  1010. is_idx = -1;
  1011. list_for_each_entry(snod, &sleb->nodes, list) {
  1012. int found, level = 0;
  1013. cond_resched();
  1014. if (is_idx == -1)
  1015. is_idx = (snod->type == UBIFS_IDX_NODE) ? 1 : 0;
  1016. if (is_idx && snod->type != UBIFS_IDX_NODE) {
  1017. ubifs_err(c, "indexing node in data LEB %d:%d",
  1018. lnum, snod->offs);
  1019. goto out_destroy;
  1020. }
  1021. if (snod->type == UBIFS_IDX_NODE) {
  1022. struct ubifs_idx_node *idx = snod->node;
  1023. key_read(c, ubifs_idx_key(c, idx), &snod->key);
  1024. level = le16_to_cpu(idx->level);
  1025. }
  1026. found = ubifs_tnc_has_node(c, &snod->key, level, lnum,
  1027. snod->offs, is_idx);
  1028. if (found) {
  1029. if (found < 0)
  1030. goto out_destroy;
  1031. used += ALIGN(snod->len, 8);
  1032. }
  1033. }
  1034. free = c->leb_size - sleb->endpt;
  1035. dirty = sleb->endpt - used;
  1036. if (free > c->leb_size || free < 0 || dirty > c->leb_size ||
  1037. dirty < 0) {
  1038. ubifs_err(c, "bad calculated accounting for LEB %d: free %d, dirty %d",
  1039. lnum, free, dirty);
  1040. goto out_destroy;
  1041. }
  1042. if (lp->free + lp->dirty == c->leb_size &&
  1043. free + dirty == c->leb_size)
  1044. if ((is_idx && !(lp->flags & LPROPS_INDEX)) ||
  1045. (!is_idx && free == c->leb_size) ||
  1046. lp->free == c->leb_size) {
  1047. /*
  1048. * Empty or freeable LEBs could contain index
  1049. * nodes from an uncompleted commit due to an
  1050. * unclean unmount. Or they could be empty for
  1051. * the same reason. Or it may simply not have been
  1052. * unmapped.
  1053. */
  1054. free = lp->free;
  1055. dirty = lp->dirty;
  1056. is_idx = 0;
  1057. }
  1058. if (is_idx && lp->free + lp->dirty == free + dirty &&
  1059. lnum != c->ihead_lnum) {
  1060. /*
  1061. * After an unclean unmount, an index LEB could have a different
  1062. * amount of free space than the value recorded by lprops. That
  1063. * is because the in-the-gaps method may use free space or
  1064. * create free space (as a side-effect of using ubi_leb_change
  1065. * and not writing the whole LEB). The incorrect free space
  1066. * value is not a problem because the index is only ever
  1067. * allocated empty LEBs, so there will never be an attempt to
  1068. * write to the free space at the end of an index LEB - except
  1069. * by the in-the-gaps method for which it is not a problem.
  1070. */
  1071. free = lp->free;
  1072. dirty = lp->dirty;
  1073. }
  1074. if (lp->free != free || lp->dirty != dirty)
  1075. goto out_print;
  1076. if (is_idx && !(lp->flags & LPROPS_INDEX)) {
  1077. if (free == c->leb_size)
  1078. /* Free but not unmapped LEB, it's fine */
  1079. is_idx = 0;
  1080. else {
  1081. ubifs_err(c, "indexing node without indexing flag");
  1082. goto out_print;
  1083. }
  1084. }
  1085. if (!is_idx && (lp->flags & LPROPS_INDEX)) {
  1086. ubifs_err(c, "data node with indexing flag");
  1087. goto out_print;
  1088. }
  1089. if (free == c->leb_size)
  1090. lst->empty_lebs += 1;
  1091. if (is_idx)
  1092. lst->idx_lebs += 1;
  1093. if (!(lp->flags & LPROPS_INDEX))
  1094. lst->total_used += c->leb_size - free - dirty;
  1095. lst->total_free += free;
  1096. lst->total_dirty += dirty;
  1097. if (!(lp->flags & LPROPS_INDEX)) {
  1098. int spc = free + dirty;
  1099. if (spc < c->dead_wm)
  1100. lst->total_dead += spc;
  1101. else
  1102. lst->total_dark += ubifs_calc_dark(c, spc);
  1103. }
  1104. ubifs_scan_destroy(sleb);
  1105. vfree(buf);
  1106. return LPT_SCAN_CONTINUE;
  1107. out_print:
  1108. ubifs_err(c, "bad accounting of LEB %d: free %d, dirty %d flags %#x, should be free %d, dirty %d",
  1109. lnum, lp->free, lp->dirty, lp->flags, free, dirty);
  1110. ubifs_dump_leb(c, lnum);
  1111. out_destroy:
  1112. ubifs_scan_destroy(sleb);
  1113. ret = -EINVAL;
  1114. out:
  1115. vfree(buf);
  1116. return ret;
  1117. }
  1118. /**
  1119. * dbg_check_lprops - check all LEB properties.
  1120. * @c: UBIFS file-system description object
  1121. *
  1122. * This function checks all LEB properties and makes sure they are all correct.
  1123. * It returns zero if everything is fine, %-EINVAL if there is an inconsistency
  1124. * and other negative error codes in case of other errors. This function is
  1125. * called while the file system is locked (because of commit start), so no
  1126. * additional locking is required. Note that locking the LPT mutex would cause
  1127. * a circular lock dependency with the TNC mutex.
  1128. */
  1129. int dbg_check_lprops(struct ubifs_info *c)
  1130. {
  1131. int i, err;
  1132. struct ubifs_lp_stats lst;
  1133. if (!dbg_is_chk_lprops(c))
  1134. return 0;
  1135. /*
  1136. * As we are going to scan the media, the write buffers have to be
  1137. * synchronized.
  1138. */
  1139. for (i = 0; i < c->jhead_cnt; i++) {
  1140. err = ubifs_wbuf_sync(&c->jheads[i].wbuf);
  1141. if (err)
  1142. return err;
  1143. }
  1144. memset(&lst, 0, sizeof(struct ubifs_lp_stats));
  1145. err = ubifs_lpt_scan_nolock(c, c->main_first, c->leb_cnt - 1,
  1146. (ubifs_lpt_scan_callback)scan_check_cb,
  1147. &lst);
  1148. if (err && err != -ENOSPC)
  1149. goto out;
  1150. if (lst.empty_lebs != c->lst.empty_lebs ||
  1151. lst.idx_lebs != c->lst.idx_lebs ||
  1152. lst.total_free != c->lst.total_free ||
  1153. lst.total_dirty != c->lst.total_dirty ||
  1154. lst.total_used != c->lst.total_used) {
  1155. ubifs_err(c, "bad overall accounting");
  1156. ubifs_err(c, "calculated: empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld, total_used %lld",
  1157. lst.empty_lebs, lst.idx_lebs, lst.total_free,
  1158. lst.total_dirty, lst.total_used);
  1159. ubifs_err(c, "read from lprops: empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld, total_used %lld",
  1160. c->lst.empty_lebs, c->lst.idx_lebs, c->lst.total_free,
  1161. c->lst.total_dirty, c->lst.total_used);
  1162. err = -EINVAL;
  1163. goto out;
  1164. }
  1165. if (lst.total_dead != c->lst.total_dead ||
  1166. lst.total_dark != c->lst.total_dark) {
  1167. ubifs_err(c, "bad dead/dark space accounting");
  1168. ubifs_err(c, "calculated: total_dead %lld, total_dark %lld",
  1169. lst.total_dead, lst.total_dark);
  1170. ubifs_err(c, "read from lprops: total_dead %lld, total_dark %lld",
  1171. c->lst.total_dead, c->lst.total_dark);
  1172. err = -EINVAL;
  1173. goto out;
  1174. }
  1175. err = dbg_check_cats(c);
  1176. out:
  1177. return err;
  1178. }