tnc_commit.c 27 KB

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