lprops.c 35 KB

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