tnc_commit.c 28 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111
  1. // SPDX-License-Identifier: GPL-2.0-only
  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. /* This file implements TNC functions for committing */
  11. #include <linux/random.h>
  12. #include "ubifs.h"
  13. /**
  14. * make_idx_node - make an index node for fill-the-gaps method of TNC commit.
  15. * @c: UBIFS file-system description object
  16. * @idx: buffer in which to place new index node
  17. * @znode: znode from which to make new index node
  18. * @lnum: LEB number where new index node will be written
  19. * @offs: offset where new index node will be written
  20. * @len: length of new index node
  21. */
  22. static int make_idx_node(struct ubifs_info *c, struct ubifs_idx_node *idx,
  23. struct ubifs_znode *znode, int lnum, int offs, int len)
  24. {
  25. struct ubifs_znode *zp;
  26. u8 hash[UBIFS_HASH_ARR_SZ];
  27. int i, err;
  28. /* Make index node */
  29. idx->ch.node_type = UBIFS_IDX_NODE;
  30. idx->child_cnt = cpu_to_le16(znode->child_cnt);
  31. idx->level = cpu_to_le16(znode->level);
  32. for (i = 0; i < znode->child_cnt; i++) {
  33. struct ubifs_branch *br = ubifs_idx_branch(c, idx, i);
  34. struct ubifs_zbranch *zbr = &znode->zbranch[i];
  35. key_write_idx(c, &zbr->key, &br->key);
  36. br->lnum = cpu_to_le32(zbr->lnum);
  37. br->offs = cpu_to_le32(zbr->offs);
  38. br->len = cpu_to_le32(zbr->len);
  39. ubifs_copy_hash(c, zbr->hash, ubifs_branch_hash(c, br));
  40. if (!zbr->lnum || !zbr->len) {
  41. ubifs_err(c, "bad ref in znode");
  42. ubifs_dump_znode(c, znode);
  43. if (zbr->znode)
  44. ubifs_dump_znode(c, zbr->znode);
  45. return -EINVAL;
  46. }
  47. }
  48. ubifs_prepare_node(c, idx, len, 0);
  49. ubifs_node_calc_hash(c, idx, hash);
  50. znode->lnum = lnum;
  51. znode->offs = offs;
  52. znode->len = len;
  53. err = insert_old_idx_znode(c, znode);
  54. /* Update the parent */
  55. zp = znode->parent;
  56. if (zp) {
  57. struct ubifs_zbranch *zbr;
  58. zbr = &zp->zbranch[znode->iip];
  59. zbr->lnum = lnum;
  60. zbr->offs = offs;
  61. zbr->len = len;
  62. ubifs_copy_hash(c, hash, zbr->hash);
  63. } else {
  64. c->zroot.lnum = lnum;
  65. c->zroot.offs = offs;
  66. c->zroot.len = len;
  67. ubifs_copy_hash(c, hash, c->zroot.hash);
  68. }
  69. c->calc_idx_sz += ALIGN(len, 8);
  70. atomic_long_dec(&c->dirty_zn_cnt);
  71. ubifs_assert(c, ubifs_zn_dirty(znode));
  72. ubifs_assert(c, ubifs_zn_cow(znode));
  73. /*
  74. * Note, unlike 'write_index()' we do not add memory barriers here
  75. * because this function is called with @c->tnc_mutex locked.
  76. */
  77. __clear_bit(DIRTY_ZNODE, &znode->flags);
  78. __clear_bit(COW_ZNODE, &znode->flags);
  79. return err;
  80. }
  81. /**
  82. * fill_gap - make index nodes in gaps in dirty index LEBs.
  83. * @c: UBIFS file-system description object
  84. * @lnum: LEB number that gap appears in
  85. * @gap_start: offset of start of gap
  86. * @gap_end: offset of end of gap
  87. * @dirt: adds dirty space to this
  88. *
  89. * This function returns the number of index nodes written into the gap.
  90. */
  91. static int fill_gap(struct ubifs_info *c, int lnum, int gap_start, int gap_end,
  92. int *dirt)
  93. {
  94. int len, gap_remains, gap_pos, written, pad_len;
  95. ubifs_assert(c, (gap_start & 7) == 0);
  96. ubifs_assert(c, (gap_end & 7) == 0);
  97. ubifs_assert(c, gap_end >= gap_start);
  98. gap_remains = gap_end - gap_start;
  99. if (!gap_remains)
  100. return 0;
  101. gap_pos = gap_start;
  102. written = 0;
  103. while (c->enext) {
  104. len = ubifs_idx_node_sz(c, c->enext->child_cnt);
  105. if (len < gap_remains) {
  106. struct ubifs_znode *znode = c->enext;
  107. const int alen = ALIGN(len, 8);
  108. int err;
  109. ubifs_assert(c, alen <= gap_remains);
  110. err = make_idx_node(c, c->ileb_buf + gap_pos, znode,
  111. lnum, gap_pos, len);
  112. if (err)
  113. return err;
  114. gap_remains -= alen;
  115. gap_pos += alen;
  116. c->enext = znode->cnext;
  117. if (c->enext == c->cnext)
  118. c->enext = NULL;
  119. written += 1;
  120. } else
  121. break;
  122. }
  123. if (gap_end == c->leb_size) {
  124. c->ileb_len = ALIGN(gap_pos, c->min_io_size);
  125. /* Pad to end of min_io_size */
  126. pad_len = c->ileb_len - gap_pos;
  127. } else
  128. /* Pad to end of gap */
  129. pad_len = gap_remains;
  130. dbg_gc("LEB %d:%d to %d len %d nodes written %d wasted bytes %d",
  131. lnum, gap_start, gap_end, gap_end - gap_start, written, pad_len);
  132. ubifs_pad(c, c->ileb_buf + gap_pos, pad_len);
  133. *dirt += pad_len;
  134. return written;
  135. }
  136. /**
  137. * find_old_idx - find an index node obsoleted since the last commit start.
  138. * @c: UBIFS file-system description object
  139. * @lnum: LEB number of obsoleted index node
  140. * @offs: offset of obsoleted index node
  141. *
  142. * Returns %1 if found and %0 otherwise.
  143. */
  144. static int find_old_idx(struct ubifs_info *c, int lnum, int offs)
  145. {
  146. struct ubifs_old_idx *o;
  147. struct rb_node *p;
  148. p = c->old_idx.rb_node;
  149. while (p) {
  150. o = rb_entry(p, struct ubifs_old_idx, rb);
  151. if (lnum < o->lnum)
  152. p = p->rb_left;
  153. else if (lnum > o->lnum)
  154. p = p->rb_right;
  155. else if (offs < o->offs)
  156. p = p->rb_left;
  157. else if (offs > o->offs)
  158. p = p->rb_right;
  159. else
  160. return 1;
  161. }
  162. return 0;
  163. }
  164. /**
  165. * is_idx_node_in_use - determine if an index node can be overwritten.
  166. * @c: UBIFS file-system description object
  167. * @key: key of index node
  168. * @level: index node level
  169. * @lnum: LEB number of index node
  170. * @offs: offset of index node
  171. *
  172. * If @key / @lnum / @offs identify an index node that was not part of the old
  173. * index, then this function returns %0 (obsolete). Else if the index node was
  174. * part of the old index but is now dirty %1 is returned, else if it is clean %2
  175. * is returned. A negative error code is returned on failure.
  176. */
  177. static int is_idx_node_in_use(struct ubifs_info *c, union ubifs_key *key,
  178. int level, int lnum, int offs)
  179. {
  180. int ret;
  181. ret = is_idx_node_in_tnc(c, key, level, lnum, offs);
  182. if (ret < 0)
  183. return ret; /* Error code */
  184. if (ret == 0)
  185. if (find_old_idx(c, lnum, offs))
  186. return 1;
  187. return ret;
  188. }
  189. /**
  190. * layout_leb_in_gaps - layout index nodes using in-the-gaps method.
  191. * @c: UBIFS file-system description object
  192. * @p: return LEB number in @c->gap_lebs[p]
  193. *
  194. * This function lays out new index nodes for dirty znodes using in-the-gaps
  195. * method of TNC commit.
  196. * This function merely puts the next znode into the next gap, making no attempt
  197. * to try to maximise the number of znodes that fit.
  198. * This function returns the number of index nodes written into the gaps, or a
  199. * negative error code on failure.
  200. */
  201. static int layout_leb_in_gaps(struct ubifs_info *c, int p)
  202. {
  203. struct ubifs_scan_leb *sleb;
  204. struct ubifs_scan_node *snod;
  205. int lnum, dirt = 0, gap_start, gap_end, err, written, tot_written;
  206. tot_written = 0;
  207. /* Get an index LEB with lots of obsolete index nodes */
  208. lnum = ubifs_find_dirty_idx_leb(c);
  209. if (lnum < 0)
  210. /*
  211. * There also may be dirt in the index head that could be
  212. * filled, however we do not check there at present.
  213. */
  214. return lnum; /* Error code */
  215. c->gap_lebs[p] = lnum;
  216. dbg_gc("LEB %d", lnum);
  217. /*
  218. * Scan the index LEB. We use the generic scan for this even though
  219. * it is more comprehensive and less efficient than is needed for this
  220. * purpose.
  221. */
  222. sleb = ubifs_scan(c, lnum, 0, c->ileb_buf, 0);
  223. c->ileb_len = 0;
  224. if (IS_ERR(sleb))
  225. return PTR_ERR(sleb);
  226. gap_start = 0;
  227. list_for_each_entry(snod, &sleb->nodes, list) {
  228. struct ubifs_idx_node *idx;
  229. int in_use, level;
  230. ubifs_assert(c, snod->type == UBIFS_IDX_NODE);
  231. idx = snod->node;
  232. key_read(c, ubifs_idx_key(c, idx), &snod->key);
  233. level = le16_to_cpu(idx->level);
  234. /* Determine if the index node is in use (not obsolete) */
  235. in_use = is_idx_node_in_use(c, &snod->key, level, lnum,
  236. snod->offs);
  237. if (in_use < 0) {
  238. ubifs_scan_destroy(sleb);
  239. return in_use; /* Error code */
  240. }
  241. if (in_use) {
  242. if (in_use == 1)
  243. dirt += ALIGN(snod->len, 8);
  244. /*
  245. * The obsolete index nodes form gaps that can be
  246. * overwritten. This gap has ended because we have
  247. * found an index node that is still in use
  248. * i.e. not obsolete
  249. */
  250. gap_end = snod->offs;
  251. /* Try to fill gap */
  252. written = fill_gap(c, lnum, gap_start, gap_end, &dirt);
  253. if (written < 0) {
  254. ubifs_scan_destroy(sleb);
  255. return written; /* Error code */
  256. }
  257. tot_written += written;
  258. gap_start = ALIGN(snod->offs + snod->len, 8);
  259. }
  260. }
  261. ubifs_scan_destroy(sleb);
  262. c->ileb_len = c->leb_size;
  263. gap_end = c->leb_size;
  264. /* Try to fill gap */
  265. written = fill_gap(c, lnum, gap_start, gap_end, &dirt);
  266. if (written < 0)
  267. return written; /* Error code */
  268. tot_written += written;
  269. if (tot_written == 0) {
  270. struct ubifs_lprops lp;
  271. dbg_gc("LEB %d wrote %d index nodes", lnum, tot_written);
  272. err = ubifs_read_one_lp(c, lnum, &lp);
  273. if (err)
  274. return err;
  275. if (lp.free == c->leb_size) {
  276. /*
  277. * We must have snatched this LEB from the idx_gc list
  278. * so we need to correct the free and dirty space.
  279. */
  280. err = ubifs_change_one_lp(c, lnum,
  281. c->leb_size - c->ileb_len,
  282. dirt, 0, 0, 0);
  283. if (err)
  284. return err;
  285. }
  286. return 0;
  287. }
  288. err = ubifs_change_one_lp(c, lnum, c->leb_size - c->ileb_len, dirt,
  289. 0, 0, 0);
  290. if (err)
  291. return err;
  292. err = ubifs_leb_change(c, lnum, c->ileb_buf, c->ileb_len);
  293. if (err)
  294. return err;
  295. dbg_gc("LEB %d wrote %d index nodes", lnum, tot_written);
  296. return tot_written;
  297. }
  298. /**
  299. * get_leb_cnt - calculate the number of empty LEBs needed to commit.
  300. * @c: UBIFS file-system description object
  301. * @cnt: number of znodes to commit
  302. *
  303. * This function returns the number of empty LEBs needed to commit @cnt znodes
  304. * to the current index head. The number is not exact and may be more than
  305. * needed.
  306. */
  307. static int get_leb_cnt(struct ubifs_info *c, int cnt)
  308. {
  309. int d;
  310. /* Assume maximum index node size (i.e. overestimate space needed) */
  311. cnt -= (c->leb_size - c->ihead_offs) / c->max_idx_node_sz;
  312. if (cnt < 0)
  313. cnt = 0;
  314. d = c->leb_size / c->max_idx_node_sz;
  315. return DIV_ROUND_UP(cnt, d);
  316. }
  317. /**
  318. * layout_in_gaps - in-the-gaps method of committing TNC.
  319. * @c: UBIFS file-system description object
  320. * @cnt: number of dirty znodes to commit.
  321. *
  322. * This function lays out new index nodes for dirty znodes using in-the-gaps
  323. * method of TNC commit.
  324. *
  325. * This function returns %0 on success and a negative error code on failure.
  326. */
  327. static int layout_in_gaps(struct ubifs_info *c, int cnt)
  328. {
  329. int err, leb_needed_cnt, written, p = 0, old_idx_lebs, *gap_lebs;
  330. dbg_gc("%d znodes to write", cnt);
  331. c->gap_lebs = kmalloc_array(c->lst.idx_lebs + 1, sizeof(int),
  332. GFP_NOFS);
  333. if (!c->gap_lebs)
  334. return -ENOMEM;
  335. old_idx_lebs = c->lst.idx_lebs;
  336. do {
  337. ubifs_assert(c, p < c->lst.idx_lebs);
  338. written = layout_leb_in_gaps(c, p);
  339. if (written < 0) {
  340. err = written;
  341. if (err != -ENOSPC) {
  342. kfree(c->gap_lebs);
  343. c->gap_lebs = NULL;
  344. return err;
  345. }
  346. if (!dbg_is_chk_index(c)) {
  347. /*
  348. * Do not print scary warnings if the debugging
  349. * option which forces in-the-gaps is enabled.
  350. */
  351. ubifs_warn(c, "out of space");
  352. ubifs_dump_budg(c, &c->bi);
  353. ubifs_dump_lprops(c);
  354. }
  355. /* Try to commit anyway */
  356. break;
  357. }
  358. p++;
  359. cnt -= written;
  360. leb_needed_cnt = get_leb_cnt(c, cnt);
  361. dbg_gc("%d znodes remaining, need %d LEBs, have %d", cnt,
  362. leb_needed_cnt, c->ileb_cnt);
  363. /*
  364. * Dynamically change the size of @c->gap_lebs to prevent
  365. * oob, because @c->lst.idx_lebs could be increased by
  366. * function @get_idx_gc_leb (called by layout_leb_in_gaps->
  367. * ubifs_find_dirty_idx_leb) during loop. Only enlarge
  368. * @c->gap_lebs when needed.
  369. *
  370. */
  371. if (leb_needed_cnt > c->ileb_cnt && p >= old_idx_lebs &&
  372. old_idx_lebs < c->lst.idx_lebs) {
  373. old_idx_lebs = c->lst.idx_lebs;
  374. gap_lebs = krealloc(c->gap_lebs, sizeof(int) *
  375. (old_idx_lebs + 1), GFP_NOFS);
  376. if (!gap_lebs) {
  377. kfree(c->gap_lebs);
  378. c->gap_lebs = NULL;
  379. return -ENOMEM;
  380. }
  381. c->gap_lebs = gap_lebs;
  382. }
  383. } while (leb_needed_cnt > c->ileb_cnt);
  384. c->gap_lebs[p] = -1;
  385. return 0;
  386. }
  387. /**
  388. * layout_in_empty_space - layout index nodes in empty space.
  389. * @c: UBIFS file-system description object
  390. *
  391. * This function lays out new index nodes for dirty znodes using empty LEBs.
  392. *
  393. * This function returns %0 on success and a negative error code on failure.
  394. */
  395. static int layout_in_empty_space(struct ubifs_info *c)
  396. {
  397. struct ubifs_znode *znode, *cnext, *zp;
  398. int lnum, offs, len, next_len, buf_len, buf_offs, used, avail;
  399. int wlen, blen, err;
  400. cnext = c->enext;
  401. if (!cnext)
  402. return 0;
  403. lnum = c->ihead_lnum;
  404. buf_offs = c->ihead_offs;
  405. buf_len = ubifs_idx_node_sz(c, c->fanout);
  406. buf_len = ALIGN(buf_len, c->min_io_size);
  407. used = 0;
  408. avail = buf_len;
  409. /* Ensure there is enough room for first write */
  410. next_len = ubifs_idx_node_sz(c, cnext->child_cnt);
  411. if (buf_offs + next_len > c->leb_size)
  412. lnum = -1;
  413. while (1) {
  414. znode = cnext;
  415. len = ubifs_idx_node_sz(c, znode->child_cnt);
  416. /* Determine the index node position */
  417. if (lnum == -1) {
  418. if (c->ileb_nxt >= c->ileb_cnt) {
  419. ubifs_err(c, "out of space");
  420. return -ENOSPC;
  421. }
  422. lnum = c->ilebs[c->ileb_nxt++];
  423. buf_offs = 0;
  424. used = 0;
  425. avail = buf_len;
  426. }
  427. offs = buf_offs + used;
  428. znode->lnum = lnum;
  429. znode->offs = offs;
  430. znode->len = len;
  431. /* Update the parent */
  432. zp = znode->parent;
  433. if (zp) {
  434. struct ubifs_zbranch *zbr;
  435. int i;
  436. i = znode->iip;
  437. zbr = &zp->zbranch[i];
  438. zbr->lnum = lnum;
  439. zbr->offs = offs;
  440. zbr->len = len;
  441. } else {
  442. c->zroot.lnum = lnum;
  443. c->zroot.offs = offs;
  444. c->zroot.len = len;
  445. }
  446. c->calc_idx_sz += ALIGN(len, 8);
  447. /*
  448. * Once lprops is updated, we can decrease the dirty znode count
  449. * but it is easier to just do it here.
  450. */
  451. atomic_long_dec(&c->dirty_zn_cnt);
  452. /*
  453. * Calculate the next index node length to see if there is
  454. * enough room for it
  455. */
  456. cnext = znode->cnext;
  457. if (cnext == c->cnext)
  458. next_len = 0;
  459. else
  460. next_len = ubifs_idx_node_sz(c, cnext->child_cnt);
  461. /* Update buffer positions */
  462. wlen = used + len;
  463. used += ALIGN(len, 8);
  464. avail -= ALIGN(len, 8);
  465. if (next_len != 0 &&
  466. buf_offs + used + next_len <= c->leb_size &&
  467. avail > 0)
  468. continue;
  469. if (avail <= 0 && next_len &&
  470. buf_offs + used + next_len <= c->leb_size)
  471. blen = buf_len;
  472. else
  473. blen = ALIGN(wlen, c->min_io_size);
  474. /* The buffer is full or there are no more znodes to do */
  475. buf_offs += blen;
  476. if (next_len) {
  477. if (buf_offs + next_len > c->leb_size) {
  478. err = ubifs_update_one_lp(c, lnum,
  479. c->leb_size - buf_offs, blen - used,
  480. 0, 0);
  481. if (err)
  482. return err;
  483. lnum = -1;
  484. }
  485. used -= blen;
  486. if (used < 0)
  487. used = 0;
  488. avail = buf_len - used;
  489. continue;
  490. }
  491. err = ubifs_update_one_lp(c, lnum, c->leb_size - buf_offs,
  492. blen - used, 0, 0);
  493. if (err)
  494. return err;
  495. break;
  496. }
  497. c->dbg->new_ihead_lnum = lnum;
  498. c->dbg->new_ihead_offs = buf_offs;
  499. return 0;
  500. }
  501. /**
  502. * layout_commit - determine positions of index nodes to commit.
  503. * @c: UBIFS file-system description object
  504. * @no_space: indicates that insufficient empty LEBs were allocated
  505. * @cnt: number of znodes to commit
  506. *
  507. * Calculate and update the positions of index nodes to commit. If there were
  508. * an insufficient number of empty LEBs allocated, then index nodes are placed
  509. * into the gaps created by obsolete index nodes in non-empty index LEBs. For
  510. * this purpose, an obsolete index node is one that was not in the index as at
  511. * the end of the last commit. To write "in-the-gaps" requires that those index
  512. * LEBs are updated atomically in-place.
  513. */
  514. static int layout_commit(struct ubifs_info *c, int no_space, int cnt)
  515. {
  516. int err;
  517. if (no_space) {
  518. err = layout_in_gaps(c, cnt);
  519. if (err)
  520. return err;
  521. }
  522. err = layout_in_empty_space(c);
  523. return err;
  524. }
  525. /**
  526. * find_first_dirty - find first dirty znode.
  527. * @znode: znode to begin searching from
  528. */
  529. static struct ubifs_znode *find_first_dirty(struct ubifs_znode *znode)
  530. {
  531. int i, cont;
  532. if (!znode)
  533. return NULL;
  534. while (1) {
  535. if (znode->level == 0) {
  536. if (ubifs_zn_dirty(znode))
  537. return znode;
  538. return NULL;
  539. }
  540. cont = 0;
  541. for (i = 0; i < znode->child_cnt; i++) {
  542. struct ubifs_zbranch *zbr = &znode->zbranch[i];
  543. if (zbr->znode && ubifs_zn_dirty(zbr->znode)) {
  544. znode = zbr->znode;
  545. cont = 1;
  546. break;
  547. }
  548. }
  549. if (!cont) {
  550. if (ubifs_zn_dirty(znode))
  551. return znode;
  552. return NULL;
  553. }
  554. }
  555. }
  556. /**
  557. * find_next_dirty - find next dirty znode.
  558. * @znode: znode to begin searching from
  559. */
  560. static struct ubifs_znode *find_next_dirty(struct ubifs_znode *znode)
  561. {
  562. int n = znode->iip + 1;
  563. znode = znode->parent;
  564. if (!znode)
  565. return NULL;
  566. for (; n < znode->child_cnt; n++) {
  567. struct ubifs_zbranch *zbr = &znode->zbranch[n];
  568. if (zbr->znode && ubifs_zn_dirty(zbr->znode))
  569. return find_first_dirty(zbr->znode);
  570. }
  571. return znode;
  572. }
  573. /**
  574. * get_znodes_to_commit - create list of dirty znodes to commit.
  575. * @c: UBIFS file-system description object
  576. *
  577. * This function returns the number of znodes to commit.
  578. */
  579. static int get_znodes_to_commit(struct ubifs_info *c)
  580. {
  581. struct ubifs_znode *znode, *cnext;
  582. int cnt = 0;
  583. c->cnext = find_first_dirty(c->zroot.znode);
  584. znode = c->enext = c->cnext;
  585. if (!znode) {
  586. dbg_cmt("no znodes to commit");
  587. return 0;
  588. }
  589. cnt += 1;
  590. while (1) {
  591. ubifs_assert(c, !ubifs_zn_cow(znode));
  592. __set_bit(COW_ZNODE, &znode->flags);
  593. znode->alt = 0;
  594. cnext = find_next_dirty(znode);
  595. if (!cnext) {
  596. znode->cnext = c->cnext;
  597. break;
  598. }
  599. znode->cparent = znode->parent;
  600. znode->ciip = znode->iip;
  601. znode->cnext = cnext;
  602. znode = cnext;
  603. cnt += 1;
  604. }
  605. dbg_cmt("committing %d znodes", cnt);
  606. ubifs_assert(c, cnt == atomic_long_read(&c->dirty_zn_cnt));
  607. return cnt;
  608. }
  609. /**
  610. * alloc_idx_lebs - allocate empty LEBs to be used to commit.
  611. * @c: UBIFS file-system description object
  612. * @cnt: number of znodes to commit
  613. *
  614. * This function returns %-ENOSPC if it cannot allocate a sufficient number of
  615. * empty LEBs. %0 is returned on success, otherwise a negative error code
  616. * is returned.
  617. */
  618. static int alloc_idx_lebs(struct ubifs_info *c, int cnt)
  619. {
  620. int i, leb_cnt, lnum;
  621. c->ileb_cnt = 0;
  622. c->ileb_nxt = 0;
  623. leb_cnt = get_leb_cnt(c, cnt);
  624. dbg_cmt("need about %d empty LEBS for TNC commit", leb_cnt);
  625. if (!leb_cnt)
  626. return 0;
  627. c->ilebs = kmalloc_array(leb_cnt, sizeof(int), GFP_NOFS);
  628. if (!c->ilebs)
  629. return -ENOMEM;
  630. for (i = 0; i < leb_cnt; i++) {
  631. lnum = ubifs_find_free_leb_for_idx(c);
  632. if (lnum < 0)
  633. return lnum;
  634. c->ilebs[c->ileb_cnt++] = lnum;
  635. dbg_cmt("LEB %d", lnum);
  636. }
  637. if (dbg_is_chk_index(c) && !(prandom_u32() & 7))
  638. return -ENOSPC;
  639. return 0;
  640. }
  641. /**
  642. * free_unused_idx_lebs - free unused LEBs that were allocated for the commit.
  643. * @c: UBIFS file-system description object
  644. *
  645. * It is possible that we allocate more empty LEBs for the commit than we need.
  646. * This functions frees the surplus.
  647. *
  648. * This function returns %0 on success and a negative error code on failure.
  649. */
  650. static int free_unused_idx_lebs(struct ubifs_info *c)
  651. {
  652. int i, err = 0, lnum, er;
  653. for (i = c->ileb_nxt; i < c->ileb_cnt; i++) {
  654. lnum = c->ilebs[i];
  655. dbg_cmt("LEB %d", lnum);
  656. er = ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
  657. LPROPS_INDEX | LPROPS_TAKEN, 0);
  658. if (!err)
  659. err = er;
  660. }
  661. return err;
  662. }
  663. /**
  664. * free_idx_lebs - free unused LEBs after commit end.
  665. * @c: UBIFS file-system description object
  666. *
  667. * This function returns %0 on success and a negative error code on failure.
  668. */
  669. static int free_idx_lebs(struct ubifs_info *c)
  670. {
  671. int err;
  672. err = free_unused_idx_lebs(c);
  673. kfree(c->ilebs);
  674. c->ilebs = NULL;
  675. return err;
  676. }
  677. /**
  678. * ubifs_tnc_start_commit - start TNC commit.
  679. * @c: UBIFS file-system description object
  680. * @zroot: new index root position is returned here
  681. *
  682. * This function prepares the list of indexing nodes to commit and lays out
  683. * their positions on flash. If there is not enough free space it uses the
  684. * in-gap commit method. Returns zero in case of success and a negative error
  685. * code in case of failure.
  686. */
  687. int ubifs_tnc_start_commit(struct ubifs_info *c, struct ubifs_zbranch *zroot)
  688. {
  689. int err = 0, cnt;
  690. mutex_lock(&c->tnc_mutex);
  691. err = dbg_check_tnc(c, 1);
  692. if (err)
  693. goto out;
  694. cnt = get_znodes_to_commit(c);
  695. if (cnt != 0) {
  696. int no_space = 0;
  697. err = alloc_idx_lebs(c, cnt);
  698. if (err == -ENOSPC)
  699. no_space = 1;
  700. else if (err)
  701. goto out_free;
  702. err = layout_commit(c, no_space, cnt);
  703. if (err)
  704. goto out_free;
  705. ubifs_assert(c, atomic_long_read(&c->dirty_zn_cnt) == 0);
  706. err = free_unused_idx_lebs(c);
  707. if (err)
  708. goto out;
  709. }
  710. destroy_old_idx(c);
  711. memcpy(zroot, &c->zroot, sizeof(struct ubifs_zbranch));
  712. err = ubifs_save_dirty_idx_lnums(c);
  713. if (err)
  714. goto out;
  715. spin_lock(&c->space_lock);
  716. /*
  717. * Although we have not finished committing yet, update size of the
  718. * committed index ('c->bi.old_idx_sz') and zero out the index growth
  719. * budget. It is OK to do this now, because we've reserved all the
  720. * space which is needed to commit the index, and it is save for the
  721. * budgeting subsystem to assume the index is already committed,
  722. * even though it is not.
  723. */
  724. ubifs_assert(c, c->bi.min_idx_lebs == ubifs_calc_min_idx_lebs(c));
  725. c->bi.old_idx_sz = c->calc_idx_sz;
  726. c->bi.uncommitted_idx = 0;
  727. c->bi.min_idx_lebs = ubifs_calc_min_idx_lebs(c);
  728. spin_unlock(&c->space_lock);
  729. mutex_unlock(&c->tnc_mutex);
  730. dbg_cmt("number of index LEBs %d", c->lst.idx_lebs);
  731. dbg_cmt("size of index %llu", c->calc_idx_sz);
  732. return err;
  733. out_free:
  734. free_idx_lebs(c);
  735. out:
  736. mutex_unlock(&c->tnc_mutex);
  737. return err;
  738. }
  739. /**
  740. * write_index - write index nodes.
  741. * @c: UBIFS file-system description object
  742. *
  743. * This function writes the index nodes whose positions were laid out in the
  744. * layout_in_empty_space function.
  745. */
  746. static int write_index(struct ubifs_info *c)
  747. {
  748. struct ubifs_idx_node *idx;
  749. struct ubifs_znode *znode, *cnext;
  750. int i, lnum, offs, len, next_len, buf_len, buf_offs, used;
  751. int avail, wlen, err, lnum_pos = 0, blen, nxt_offs;
  752. cnext = c->enext;
  753. if (!cnext)
  754. return 0;
  755. /*
  756. * Always write index nodes to the index head so that index nodes and
  757. * other types of nodes are never mixed in the same erase block.
  758. */
  759. lnum = c->ihead_lnum;
  760. buf_offs = c->ihead_offs;
  761. /* Allocate commit buffer */
  762. buf_len = ALIGN(c->max_idx_node_sz, c->min_io_size);
  763. used = 0;
  764. avail = buf_len;
  765. /* Ensure there is enough room for first write */
  766. next_len = ubifs_idx_node_sz(c, cnext->child_cnt);
  767. if (buf_offs + next_len > c->leb_size) {
  768. err = ubifs_update_one_lp(c, lnum, LPROPS_NC, 0, 0,
  769. LPROPS_TAKEN);
  770. if (err)
  771. return err;
  772. lnum = -1;
  773. }
  774. while (1) {
  775. u8 hash[UBIFS_HASH_ARR_SZ];
  776. cond_resched();
  777. znode = cnext;
  778. idx = c->cbuf + used;
  779. /* Make index node */
  780. idx->ch.node_type = UBIFS_IDX_NODE;
  781. idx->child_cnt = cpu_to_le16(znode->child_cnt);
  782. idx->level = cpu_to_le16(znode->level);
  783. for (i = 0; i < znode->child_cnt; i++) {
  784. struct ubifs_branch *br = ubifs_idx_branch(c, idx, i);
  785. struct ubifs_zbranch *zbr = &znode->zbranch[i];
  786. key_write_idx(c, &zbr->key, &br->key);
  787. br->lnum = cpu_to_le32(zbr->lnum);
  788. br->offs = cpu_to_le32(zbr->offs);
  789. br->len = cpu_to_le32(zbr->len);
  790. ubifs_copy_hash(c, zbr->hash, ubifs_branch_hash(c, br));
  791. if (!zbr->lnum || !zbr->len) {
  792. ubifs_err(c, "bad ref in znode");
  793. ubifs_dump_znode(c, znode);
  794. if (zbr->znode)
  795. ubifs_dump_znode(c, zbr->znode);
  796. return -EINVAL;
  797. }
  798. }
  799. len = ubifs_idx_node_sz(c, znode->child_cnt);
  800. ubifs_prepare_node(c, idx, len, 0);
  801. ubifs_node_calc_hash(c, idx, hash);
  802. mutex_lock(&c->tnc_mutex);
  803. if (znode->cparent)
  804. ubifs_copy_hash(c, hash,
  805. znode->cparent->zbranch[znode->ciip].hash);
  806. if (znode->parent) {
  807. if (!ubifs_zn_obsolete(znode))
  808. ubifs_copy_hash(c, hash,
  809. znode->parent->zbranch[znode->iip].hash);
  810. } else {
  811. ubifs_copy_hash(c, hash, c->zroot.hash);
  812. }
  813. mutex_unlock(&c->tnc_mutex);
  814. /* Determine the index node position */
  815. if (lnum == -1) {
  816. lnum = c->ilebs[lnum_pos++];
  817. buf_offs = 0;
  818. used = 0;
  819. avail = buf_len;
  820. }
  821. offs = buf_offs + used;
  822. if (lnum != znode->lnum || offs != znode->offs ||
  823. len != znode->len) {
  824. ubifs_err(c, "inconsistent znode posn");
  825. return -EINVAL;
  826. }
  827. /* Grab some stuff from znode while we still can */
  828. cnext = znode->cnext;
  829. ubifs_assert(c, ubifs_zn_dirty(znode));
  830. ubifs_assert(c, ubifs_zn_cow(znode));
  831. /*
  832. * It is important that other threads should see %DIRTY_ZNODE
  833. * flag cleared before %COW_ZNODE. Specifically, it matters in
  834. * the 'dirty_cow_znode()' function. This is the reason for the
  835. * first barrier. Also, we want the bit changes to be seen to
  836. * other threads ASAP, to avoid unnecesarry copying, which is
  837. * the reason for the second barrier.
  838. */
  839. clear_bit(DIRTY_ZNODE, &znode->flags);
  840. smp_mb__before_atomic();
  841. clear_bit(COW_ZNODE, &znode->flags);
  842. smp_mb__after_atomic();
  843. /*
  844. * We have marked the znode as clean but have not updated the
  845. * @c->clean_zn_cnt counter. If this znode becomes dirty again
  846. * before 'free_obsolete_znodes()' is called, then
  847. * @c->clean_zn_cnt will be decremented before it gets
  848. * incremented (resulting in 2 decrements for the same znode).
  849. * This means that @c->clean_zn_cnt may become negative for a
  850. * while.
  851. *
  852. * Q: why we cannot increment @c->clean_zn_cnt?
  853. * A: because we do not have the @c->tnc_mutex locked, and the
  854. * following code would be racy and buggy:
  855. *
  856. * if (!ubifs_zn_obsolete(znode)) {
  857. * atomic_long_inc(&c->clean_zn_cnt);
  858. * atomic_long_inc(&ubifs_clean_zn_cnt);
  859. * }
  860. *
  861. * Thus, we just delay the @c->clean_zn_cnt update until we
  862. * have the mutex locked.
  863. */
  864. /* Do not access znode from this point on */
  865. /* Update buffer positions */
  866. wlen = used + len;
  867. used += ALIGN(len, 8);
  868. avail -= ALIGN(len, 8);
  869. /*
  870. * Calculate the next index node length to see if there is
  871. * enough room for it
  872. */
  873. if (cnext == c->cnext)
  874. next_len = 0;
  875. else
  876. next_len = ubifs_idx_node_sz(c, cnext->child_cnt);
  877. nxt_offs = buf_offs + used + next_len;
  878. if (next_len && nxt_offs <= c->leb_size) {
  879. if (avail > 0)
  880. continue;
  881. else
  882. blen = buf_len;
  883. } else {
  884. wlen = ALIGN(wlen, 8);
  885. blen = ALIGN(wlen, c->min_io_size);
  886. ubifs_pad(c, c->cbuf + wlen, blen - wlen);
  887. }
  888. /* The buffer is full or there are no more znodes to do */
  889. err = ubifs_leb_write(c, lnum, c->cbuf, buf_offs, blen);
  890. if (err)
  891. return err;
  892. buf_offs += blen;
  893. if (next_len) {
  894. if (nxt_offs > c->leb_size) {
  895. err = ubifs_update_one_lp(c, lnum, LPROPS_NC, 0,
  896. 0, LPROPS_TAKEN);
  897. if (err)
  898. return err;
  899. lnum = -1;
  900. }
  901. used -= blen;
  902. if (used < 0)
  903. used = 0;
  904. avail = buf_len - used;
  905. memmove(c->cbuf, c->cbuf + blen, used);
  906. continue;
  907. }
  908. break;
  909. }
  910. if (lnum != c->dbg->new_ihead_lnum ||
  911. buf_offs != c->dbg->new_ihead_offs) {
  912. ubifs_err(c, "inconsistent ihead");
  913. return -EINVAL;
  914. }
  915. c->ihead_lnum = lnum;
  916. c->ihead_offs = buf_offs;
  917. return 0;
  918. }
  919. /**
  920. * free_obsolete_znodes - free obsolete znodes.
  921. * @c: UBIFS file-system description object
  922. *
  923. * At the end of commit end, obsolete znodes are freed.
  924. */
  925. static void free_obsolete_znodes(struct ubifs_info *c)
  926. {
  927. struct ubifs_znode *znode, *cnext;
  928. cnext = c->cnext;
  929. do {
  930. znode = cnext;
  931. cnext = znode->cnext;
  932. if (ubifs_zn_obsolete(znode))
  933. kfree(znode);
  934. else {
  935. znode->cnext = NULL;
  936. atomic_long_inc(&c->clean_zn_cnt);
  937. atomic_long_inc(&ubifs_clean_zn_cnt);
  938. }
  939. } while (cnext != c->cnext);
  940. }
  941. /**
  942. * return_gap_lebs - return LEBs used by the in-gap commit method.
  943. * @c: UBIFS file-system description object
  944. *
  945. * This function clears the "taken" flag for the LEBs which were used by the
  946. * "commit in-the-gaps" method.
  947. */
  948. static int return_gap_lebs(struct ubifs_info *c)
  949. {
  950. int *p, err;
  951. if (!c->gap_lebs)
  952. return 0;
  953. dbg_cmt("");
  954. for (p = c->gap_lebs; *p != -1; p++) {
  955. err = ubifs_change_one_lp(c, *p, LPROPS_NC, LPROPS_NC, 0,
  956. LPROPS_TAKEN, 0);
  957. if (err)
  958. return err;
  959. }
  960. kfree(c->gap_lebs);
  961. c->gap_lebs = NULL;
  962. return 0;
  963. }
  964. /**
  965. * ubifs_tnc_end_commit - update the TNC for commit end.
  966. * @c: UBIFS file-system description object
  967. *
  968. * Write the dirty znodes.
  969. */
  970. int ubifs_tnc_end_commit(struct ubifs_info *c)
  971. {
  972. int err;
  973. if (!c->cnext)
  974. return 0;
  975. err = return_gap_lebs(c);
  976. if (err)
  977. return err;
  978. err = write_index(c);
  979. if (err)
  980. return err;
  981. mutex_lock(&c->tnc_mutex);
  982. dbg_cmt("TNC height is %d", c->zroot.znode->level + 1);
  983. free_obsolete_znodes(c);
  984. c->cnext = NULL;
  985. kfree(c->ilebs);
  986. c->ilebs = NULL;
  987. mutex_unlock(&c->tnc_mutex);
  988. return 0;
  989. }