replay.c 29 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075
  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 contains journal replay code. It runs when the file-system is being
  12. * mounted and requires no locking.
  13. *
  14. * The larger is the journal, the longer it takes to scan it, so the longer it
  15. * takes to mount UBIFS. This is why the journal has limited size which may be
  16. * changed depending on the system requirements. But a larger journal gives
  17. * faster I/O speed because it writes the index less frequently. So this is a
  18. * trade-off. Also, the journal is indexed by the in-memory index (TNC), so the
  19. * larger is the journal, the more memory its index may consume.
  20. */
  21. #ifdef __UBOOT__
  22. #include <linux/compat.h>
  23. #include <linux/err.h>
  24. #endif
  25. #include "ubifs.h"
  26. #include <linux/bug.h>
  27. #include <linux/list_sort.h>
  28. /**
  29. * struct replay_entry - replay list entry.
  30. * @lnum: logical eraseblock number of the node
  31. * @offs: node offset
  32. * @len: node length
  33. * @deletion: non-zero if this entry corresponds to a node deletion
  34. * @sqnum: node sequence number
  35. * @list: links the replay list
  36. * @key: node key
  37. * @nm: directory entry name
  38. * @old_size: truncation old size
  39. * @new_size: truncation new size
  40. *
  41. * The replay process first scans all buds and builds the replay list, then
  42. * sorts the replay list in nodes sequence number order, and then inserts all
  43. * the replay entries to the TNC.
  44. */
  45. struct replay_entry {
  46. int lnum;
  47. int offs;
  48. int len;
  49. unsigned int deletion:1;
  50. unsigned long long sqnum;
  51. struct list_head list;
  52. union ubifs_key key;
  53. union {
  54. struct qstr nm;
  55. struct {
  56. loff_t old_size;
  57. loff_t new_size;
  58. };
  59. };
  60. };
  61. /**
  62. * struct bud_entry - entry in the list of buds to replay.
  63. * @list: next bud in the list
  64. * @bud: bud description object
  65. * @sqnum: reference node sequence number
  66. * @free: free bytes in the bud
  67. * @dirty: dirty bytes in the bud
  68. */
  69. struct bud_entry {
  70. struct list_head list;
  71. struct ubifs_bud *bud;
  72. unsigned long long sqnum;
  73. int free;
  74. int dirty;
  75. };
  76. /**
  77. * set_bud_lprops - set free and dirty space used by a bud.
  78. * @c: UBIFS file-system description object
  79. * @b: bud entry which describes the bud
  80. *
  81. * This function makes sure the LEB properties of bud @b are set correctly
  82. * after the replay. Returns zero in case of success and a negative error code
  83. * in case of failure.
  84. */
  85. static int set_bud_lprops(struct ubifs_info *c, struct bud_entry *b)
  86. {
  87. const struct ubifs_lprops *lp;
  88. int err = 0, dirty;
  89. ubifs_get_lprops(c);
  90. lp = ubifs_lpt_lookup_dirty(c, b->bud->lnum);
  91. if (IS_ERR(lp)) {
  92. err = PTR_ERR(lp);
  93. goto out;
  94. }
  95. dirty = lp->dirty;
  96. if (b->bud->start == 0 && (lp->free != c->leb_size || lp->dirty != 0)) {
  97. /*
  98. * The LEB was added to the journal with a starting offset of
  99. * zero which means the LEB must have been empty. The LEB
  100. * property values should be @lp->free == @c->leb_size and
  101. * @lp->dirty == 0, but that is not the case. The reason is that
  102. * the LEB had been garbage collected before it became the bud,
  103. * and there was not commit inbetween. The garbage collector
  104. * resets the free and dirty space without recording it
  105. * anywhere except lprops, so if there was no commit then
  106. * lprops does not have that information.
  107. *
  108. * We do not need to adjust free space because the scan has told
  109. * us the exact value which is recorded in the replay entry as
  110. * @b->free.
  111. *
  112. * However we do need to subtract from the dirty space the
  113. * amount of space that the garbage collector reclaimed, which
  114. * is the whole LEB minus the amount of space that was free.
  115. */
  116. dbg_mnt("bud LEB %d was GC'd (%d free, %d dirty)", b->bud->lnum,
  117. lp->free, lp->dirty);
  118. dbg_gc("bud LEB %d was GC'd (%d free, %d dirty)", b->bud->lnum,
  119. lp->free, lp->dirty);
  120. dirty -= c->leb_size - lp->free;
  121. /*
  122. * If the replay order was perfect the dirty space would now be
  123. * zero. The order is not perfect because the journal heads
  124. * race with each other. This is not a problem but is does mean
  125. * that the dirty space may temporarily exceed c->leb_size
  126. * during the replay.
  127. */
  128. if (dirty != 0)
  129. dbg_mnt("LEB %d lp: %d free %d dirty replay: %d free %d dirty",
  130. b->bud->lnum, lp->free, lp->dirty, b->free,
  131. b->dirty);
  132. }
  133. lp = ubifs_change_lp(c, lp, b->free, dirty + b->dirty,
  134. lp->flags | LPROPS_TAKEN, 0);
  135. if (IS_ERR(lp)) {
  136. err = PTR_ERR(lp);
  137. goto out;
  138. }
  139. /* Make sure the journal head points to the latest bud */
  140. err = ubifs_wbuf_seek_nolock(&c->jheads[b->bud->jhead].wbuf,
  141. b->bud->lnum, c->leb_size - b->free);
  142. out:
  143. ubifs_release_lprops(c);
  144. return err;
  145. }
  146. /**
  147. * set_buds_lprops - set free and dirty space for all replayed buds.
  148. * @c: UBIFS file-system description object
  149. *
  150. * This function sets LEB properties for all replayed buds. Returns zero in
  151. * case of success and a negative error code in case of failure.
  152. */
  153. static int set_buds_lprops(struct ubifs_info *c)
  154. {
  155. struct bud_entry *b;
  156. int err;
  157. list_for_each_entry(b, &c->replay_buds, list) {
  158. err = set_bud_lprops(c, b);
  159. if (err)
  160. return err;
  161. }
  162. return 0;
  163. }
  164. /**
  165. * trun_remove_range - apply a replay entry for a truncation to the TNC.
  166. * @c: UBIFS file-system description object
  167. * @r: replay entry of truncation
  168. */
  169. static int trun_remove_range(struct ubifs_info *c, struct replay_entry *r)
  170. {
  171. unsigned min_blk, max_blk;
  172. union ubifs_key min_key, max_key;
  173. ino_t ino;
  174. min_blk = r->new_size / UBIFS_BLOCK_SIZE;
  175. if (r->new_size & (UBIFS_BLOCK_SIZE - 1))
  176. min_blk += 1;
  177. max_blk = r->old_size / UBIFS_BLOCK_SIZE;
  178. if ((r->old_size & (UBIFS_BLOCK_SIZE - 1)) == 0)
  179. max_blk -= 1;
  180. ino = key_inum(c, &r->key);
  181. data_key_init(c, &min_key, ino, min_blk);
  182. data_key_init(c, &max_key, ino, max_blk);
  183. return ubifs_tnc_remove_range(c, &min_key, &max_key);
  184. }
  185. /**
  186. * apply_replay_entry - apply a replay entry to the TNC.
  187. * @c: UBIFS file-system description object
  188. * @r: replay entry to apply
  189. *
  190. * Apply a replay entry to the TNC.
  191. */
  192. static int apply_replay_entry(struct ubifs_info *c, struct replay_entry *r)
  193. {
  194. int err;
  195. dbg_mntk(&r->key, "LEB %d:%d len %d deletion %d sqnum %llu key ",
  196. r->lnum, r->offs, r->len, r->deletion, r->sqnum);
  197. /* Set c->replay_sqnum to help deal with dangling branches. */
  198. c->replay_sqnum = r->sqnum;
  199. if (is_hash_key(c, &r->key)) {
  200. if (r->deletion)
  201. err = ubifs_tnc_remove_nm(c, &r->key, &r->nm);
  202. else
  203. err = ubifs_tnc_add_nm(c, &r->key, r->lnum, r->offs,
  204. r->len, &r->nm);
  205. } else {
  206. if (r->deletion)
  207. switch (key_type(c, &r->key)) {
  208. case UBIFS_INO_KEY:
  209. {
  210. ino_t inum = key_inum(c, &r->key);
  211. err = ubifs_tnc_remove_ino(c, inum);
  212. break;
  213. }
  214. case UBIFS_TRUN_KEY:
  215. err = trun_remove_range(c, r);
  216. break;
  217. default:
  218. err = ubifs_tnc_remove(c, &r->key);
  219. break;
  220. }
  221. else
  222. err = ubifs_tnc_add(c, &r->key, r->lnum, r->offs,
  223. r->len);
  224. if (err)
  225. return err;
  226. if (c->need_recovery)
  227. err = ubifs_recover_size_accum(c, &r->key, r->deletion,
  228. r->new_size);
  229. }
  230. return err;
  231. }
  232. /**
  233. * replay_entries_cmp - compare 2 replay entries.
  234. * @priv: UBIFS file-system description object
  235. * @a: first replay entry
  236. * @a: second replay entry
  237. *
  238. * This is a comparios function for 'list_sort()' which compares 2 replay
  239. * entries @a and @b by comparing their sequence numer. Returns %1 if @a has
  240. * greater sequence number and %-1 otherwise.
  241. */
  242. static int replay_entries_cmp(void *priv, struct list_head *a,
  243. struct list_head *b)
  244. {
  245. struct replay_entry *ra, *rb;
  246. cond_resched();
  247. if (a == b)
  248. return 0;
  249. ra = list_entry(a, struct replay_entry, list);
  250. rb = list_entry(b, struct replay_entry, list);
  251. ubifs_assert(ra->sqnum != rb->sqnum);
  252. if (ra->sqnum > rb->sqnum)
  253. return 1;
  254. return -1;
  255. }
  256. /**
  257. * apply_replay_list - apply the replay list to the TNC.
  258. * @c: UBIFS file-system description object
  259. *
  260. * Apply all entries in the replay list to the TNC. Returns zero in case of
  261. * success and a negative error code in case of failure.
  262. */
  263. static int apply_replay_list(struct ubifs_info *c)
  264. {
  265. struct replay_entry *r;
  266. int err;
  267. list_sort(c, &c->replay_list, &replay_entries_cmp);
  268. list_for_each_entry(r, &c->replay_list, list) {
  269. cond_resched();
  270. err = apply_replay_entry(c, r);
  271. if (err)
  272. return err;
  273. }
  274. return 0;
  275. }
  276. /**
  277. * destroy_replay_list - destroy the replay.
  278. * @c: UBIFS file-system description object
  279. *
  280. * Destroy the replay list.
  281. */
  282. static void destroy_replay_list(struct ubifs_info *c)
  283. {
  284. struct replay_entry *r, *tmp;
  285. list_for_each_entry_safe(r, tmp, &c->replay_list, list) {
  286. if (is_hash_key(c, &r->key))
  287. kfree(r->nm.name);
  288. list_del(&r->list);
  289. kfree(r);
  290. }
  291. }
  292. /**
  293. * insert_node - insert a node to the replay list
  294. * @c: UBIFS file-system description object
  295. * @lnum: node logical eraseblock number
  296. * @offs: node offset
  297. * @len: node length
  298. * @key: node key
  299. * @sqnum: sequence number
  300. * @deletion: non-zero if this is a deletion
  301. * @used: number of bytes in use in a LEB
  302. * @old_size: truncation old size
  303. * @new_size: truncation new size
  304. *
  305. * This function inserts a scanned non-direntry node to the replay list. The
  306. * replay list contains @struct replay_entry elements, and we sort this list in
  307. * sequence number order before applying it. The replay list is applied at the
  308. * very end of the replay process. Since the list is sorted in sequence number
  309. * order, the older modifications are applied first. This function returns zero
  310. * in case of success and a negative error code in case of failure.
  311. */
  312. static int insert_node(struct ubifs_info *c, int lnum, int offs, int len,
  313. union ubifs_key *key, unsigned long long sqnum,
  314. int deletion, int *used, loff_t old_size,
  315. loff_t new_size)
  316. {
  317. struct replay_entry *r;
  318. dbg_mntk(key, "add LEB %d:%d, key ", lnum, offs);
  319. if (key_inum(c, key) >= c->highest_inum)
  320. c->highest_inum = key_inum(c, key);
  321. r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
  322. if (!r)
  323. return -ENOMEM;
  324. if (!deletion)
  325. *used += ALIGN(len, 8);
  326. r->lnum = lnum;
  327. r->offs = offs;
  328. r->len = len;
  329. r->deletion = !!deletion;
  330. r->sqnum = sqnum;
  331. key_copy(c, key, &r->key);
  332. r->old_size = old_size;
  333. r->new_size = new_size;
  334. list_add_tail(&r->list, &c->replay_list);
  335. return 0;
  336. }
  337. /**
  338. * insert_dent - insert a directory entry node into the replay list.
  339. * @c: UBIFS file-system description object
  340. * @lnum: node logical eraseblock number
  341. * @offs: node offset
  342. * @len: node length
  343. * @key: node key
  344. * @name: directory entry name
  345. * @nlen: directory entry name length
  346. * @sqnum: sequence number
  347. * @deletion: non-zero if this is a deletion
  348. * @used: number of bytes in use in a LEB
  349. *
  350. * This function inserts a scanned directory entry node or an extended
  351. * attribute entry to the replay list. Returns zero in case of success and a
  352. * negative error code in case of failure.
  353. */
  354. static int insert_dent(struct ubifs_info *c, int lnum, int offs, int len,
  355. union ubifs_key *key, const char *name, int nlen,
  356. unsigned long long sqnum, int deletion, int *used)
  357. {
  358. struct replay_entry *r;
  359. char *nbuf;
  360. dbg_mntk(key, "add LEB %d:%d, key ", lnum, offs);
  361. if (key_inum(c, key) >= c->highest_inum)
  362. c->highest_inum = key_inum(c, key);
  363. r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
  364. if (!r)
  365. return -ENOMEM;
  366. nbuf = kmalloc(nlen + 1, GFP_KERNEL);
  367. if (!nbuf) {
  368. kfree(r);
  369. return -ENOMEM;
  370. }
  371. if (!deletion)
  372. *used += ALIGN(len, 8);
  373. r->lnum = lnum;
  374. r->offs = offs;
  375. r->len = len;
  376. r->deletion = !!deletion;
  377. r->sqnum = sqnum;
  378. key_copy(c, key, &r->key);
  379. r->nm.len = nlen;
  380. memcpy(nbuf, name, nlen);
  381. nbuf[nlen] = '\0';
  382. r->nm.name = nbuf;
  383. list_add_tail(&r->list, &c->replay_list);
  384. return 0;
  385. }
  386. /**
  387. * ubifs_validate_entry - validate directory or extended attribute entry node.
  388. * @c: UBIFS file-system description object
  389. * @dent: the node to validate
  390. *
  391. * This function validates directory or extended attribute entry node @dent.
  392. * Returns zero if the node is all right and a %-EINVAL if not.
  393. */
  394. int ubifs_validate_entry(struct ubifs_info *c,
  395. const struct ubifs_dent_node *dent)
  396. {
  397. int key_type = key_type_flash(c, dent->key);
  398. int nlen = le16_to_cpu(dent->nlen);
  399. if (le32_to_cpu(dent->ch.len) != nlen + UBIFS_DENT_NODE_SZ + 1 ||
  400. dent->type >= UBIFS_ITYPES_CNT ||
  401. nlen > UBIFS_MAX_NLEN || dent->name[nlen] != 0 ||
  402. strnlen(dent->name, nlen) != nlen ||
  403. le64_to_cpu(dent->inum) > MAX_INUM) {
  404. ubifs_err(c, "bad %s node", key_type == UBIFS_DENT_KEY ?
  405. "directory entry" : "extended attribute entry");
  406. return -EINVAL;
  407. }
  408. if (key_type != UBIFS_DENT_KEY && key_type != UBIFS_XENT_KEY) {
  409. ubifs_err(c, "bad key type %d", key_type);
  410. return -EINVAL;
  411. }
  412. return 0;
  413. }
  414. /**
  415. * is_last_bud - check if the bud is the last in the journal head.
  416. * @c: UBIFS file-system description object
  417. * @bud: bud description object
  418. *
  419. * This function checks if bud @bud is the last bud in its journal head. This
  420. * information is then used by 'replay_bud()' to decide whether the bud can
  421. * have corruptions or not. Indeed, only last buds can be corrupted by power
  422. * cuts. Returns %1 if this is the last bud, and %0 if not.
  423. */
  424. static int is_last_bud(struct ubifs_info *c, struct ubifs_bud *bud)
  425. {
  426. struct ubifs_jhead *jh = &c->jheads[bud->jhead];
  427. struct ubifs_bud *next;
  428. uint32_t data;
  429. int err;
  430. if (list_is_last(&bud->list, &jh->buds_list))
  431. return 1;
  432. /*
  433. * The following is a quirk to make sure we work correctly with UBIFS
  434. * images used with older UBIFS.
  435. *
  436. * Normally, the last bud will be the last in the journal head's list
  437. * of bud. However, there is one exception if the UBIFS image belongs
  438. * to older UBIFS. This is fairly unlikely: one would need to use old
  439. * UBIFS, then have a power cut exactly at the right point, and then
  440. * try to mount this image with new UBIFS.
  441. *
  442. * The exception is: it is possible to have 2 buds A and B, A goes
  443. * before B, and B is the last, bud B is contains no data, and bud A is
  444. * corrupted at the end. The reason is that in older versions when the
  445. * journal code switched the next bud (from A to B), it first added a
  446. * log reference node for the new bud (B), and only after this it
  447. * synchronized the write-buffer of current bud (A). But later this was
  448. * changed and UBIFS started to always synchronize the write-buffer of
  449. * the bud (A) before writing the log reference for the new bud (B).
  450. *
  451. * But because older UBIFS always synchronized A's write-buffer before
  452. * writing to B, we can recognize this exceptional situation but
  453. * checking the contents of bud B - if it is empty, then A can be
  454. * treated as the last and we can recover it.
  455. *
  456. * TODO: remove this piece of code in a couple of years (today it is
  457. * 16.05.2011).
  458. */
  459. next = list_entry(bud->list.next, struct ubifs_bud, list);
  460. if (!list_is_last(&next->list, &jh->buds_list))
  461. return 0;
  462. err = ubifs_leb_read(c, next->lnum, (char *)&data, next->start, 4, 1);
  463. if (err)
  464. return 0;
  465. return data == 0xFFFFFFFF;
  466. }
  467. /**
  468. * replay_bud - replay a bud logical eraseblock.
  469. * @c: UBIFS file-system description object
  470. * @b: bud entry which describes the bud
  471. *
  472. * This function replays bud @bud, recovers it if needed, and adds all nodes
  473. * from this bud to the replay list. Returns zero in case of success and a
  474. * negative error code in case of failure.
  475. */
  476. static int replay_bud(struct ubifs_info *c, struct bud_entry *b)
  477. {
  478. int is_last = is_last_bud(c, b->bud);
  479. int err = 0, used = 0, lnum = b->bud->lnum, offs = b->bud->start;
  480. struct ubifs_scan_leb *sleb;
  481. struct ubifs_scan_node *snod;
  482. dbg_mnt("replay bud LEB %d, head %d, offs %d, is_last %d",
  483. lnum, b->bud->jhead, offs, is_last);
  484. if (c->need_recovery && is_last)
  485. /*
  486. * Recover only last LEBs in the journal heads, because power
  487. * cuts may cause corruptions only in these LEBs, because only
  488. * these LEBs could possibly be written to at the power cut
  489. * time.
  490. */
  491. sleb = ubifs_recover_leb(c, lnum, offs, c->sbuf, b->bud->jhead);
  492. else
  493. sleb = ubifs_scan(c, lnum, offs, c->sbuf, 0);
  494. if (IS_ERR(sleb))
  495. return PTR_ERR(sleb);
  496. /*
  497. * The bud does not have to start from offset zero - the beginning of
  498. * the 'lnum' LEB may contain previously committed data. One of the
  499. * things we have to do in replay is to correctly update lprops with
  500. * newer information about this LEB.
  501. *
  502. * At this point lprops thinks that this LEB has 'c->leb_size - offs'
  503. * bytes of free space because it only contain information about
  504. * committed data.
  505. *
  506. * But we know that real amount of free space is 'c->leb_size -
  507. * sleb->endpt', and the space in the 'lnum' LEB between 'offs' and
  508. * 'sleb->endpt' is used by bud data. We have to correctly calculate
  509. * how much of these data are dirty and update lprops with this
  510. * information.
  511. *
  512. * The dirt in that LEB region is comprised of padding nodes, deletion
  513. * nodes, truncation nodes and nodes which are obsoleted by subsequent
  514. * nodes in this LEB. So instead of calculating clean space, we
  515. * calculate used space ('used' variable).
  516. */
  517. list_for_each_entry(snod, &sleb->nodes, list) {
  518. int deletion = 0;
  519. cond_resched();
  520. if (snod->sqnum >= SQNUM_WATERMARK) {
  521. ubifs_err(c, "file system's life ended");
  522. goto out_dump;
  523. }
  524. if (snod->sqnum > c->max_sqnum)
  525. c->max_sqnum = snod->sqnum;
  526. switch (snod->type) {
  527. case UBIFS_INO_NODE:
  528. {
  529. struct ubifs_ino_node *ino = snod->node;
  530. loff_t new_size = le64_to_cpu(ino->size);
  531. if (le32_to_cpu(ino->nlink) == 0)
  532. deletion = 1;
  533. err = insert_node(c, lnum, snod->offs, snod->len,
  534. &snod->key, snod->sqnum, deletion,
  535. &used, 0, new_size);
  536. break;
  537. }
  538. case UBIFS_DATA_NODE:
  539. {
  540. struct ubifs_data_node *dn = snod->node;
  541. loff_t new_size = le32_to_cpu(dn->size) +
  542. key_block(c, &snod->key) *
  543. UBIFS_BLOCK_SIZE;
  544. err = insert_node(c, lnum, snod->offs, snod->len,
  545. &snod->key, snod->sqnum, deletion,
  546. &used, 0, new_size);
  547. break;
  548. }
  549. case UBIFS_DENT_NODE:
  550. case UBIFS_XENT_NODE:
  551. {
  552. struct ubifs_dent_node *dent = snod->node;
  553. err = ubifs_validate_entry(c, dent);
  554. if (err)
  555. goto out_dump;
  556. err = insert_dent(c, lnum, snod->offs, snod->len,
  557. &snod->key, dent->name,
  558. le16_to_cpu(dent->nlen), snod->sqnum,
  559. !le64_to_cpu(dent->inum), &used);
  560. break;
  561. }
  562. case UBIFS_TRUN_NODE:
  563. {
  564. struct ubifs_trun_node *trun = snod->node;
  565. loff_t old_size = le64_to_cpu(trun->old_size);
  566. loff_t new_size = le64_to_cpu(trun->new_size);
  567. union ubifs_key key;
  568. /* Validate truncation node */
  569. if (old_size < 0 || old_size > c->max_inode_sz ||
  570. new_size < 0 || new_size > c->max_inode_sz ||
  571. old_size <= new_size) {
  572. ubifs_err(c, "bad truncation node");
  573. goto out_dump;
  574. }
  575. /*
  576. * Create a fake truncation key just to use the same
  577. * functions which expect nodes to have keys.
  578. */
  579. trun_key_init(c, &key, le32_to_cpu(trun->inum));
  580. err = insert_node(c, lnum, snod->offs, snod->len,
  581. &key, snod->sqnum, 1, &used,
  582. old_size, new_size);
  583. break;
  584. }
  585. default:
  586. ubifs_err(c, "unexpected node type %d in bud LEB %d:%d",
  587. snod->type, lnum, snod->offs);
  588. err = -EINVAL;
  589. goto out_dump;
  590. }
  591. if (err)
  592. goto out;
  593. }
  594. ubifs_assert(ubifs_search_bud(c, lnum));
  595. ubifs_assert(sleb->endpt - offs >= used);
  596. ubifs_assert(sleb->endpt % c->min_io_size == 0);
  597. b->dirty = sleb->endpt - offs - used;
  598. b->free = c->leb_size - sleb->endpt;
  599. dbg_mnt("bud LEB %d replied: dirty %d, free %d",
  600. lnum, b->dirty, b->free);
  601. out:
  602. ubifs_scan_destroy(sleb);
  603. return err;
  604. out_dump:
  605. ubifs_err(c, "bad node is at LEB %d:%d", lnum, snod->offs);
  606. ubifs_dump_node(c, snod->node);
  607. ubifs_scan_destroy(sleb);
  608. return -EINVAL;
  609. }
  610. /**
  611. * replay_buds - replay all buds.
  612. * @c: UBIFS file-system description object
  613. *
  614. * This function returns zero in case of success and a negative error code in
  615. * case of failure.
  616. */
  617. static int replay_buds(struct ubifs_info *c)
  618. {
  619. struct bud_entry *b;
  620. int err;
  621. unsigned long long prev_sqnum = 0;
  622. list_for_each_entry(b, &c->replay_buds, list) {
  623. err = replay_bud(c, b);
  624. if (err)
  625. return err;
  626. ubifs_assert(b->sqnum > prev_sqnum);
  627. prev_sqnum = b->sqnum;
  628. }
  629. return 0;
  630. }
  631. /**
  632. * destroy_bud_list - destroy the list of buds to replay.
  633. * @c: UBIFS file-system description object
  634. */
  635. static void destroy_bud_list(struct ubifs_info *c)
  636. {
  637. struct bud_entry *b;
  638. while (!list_empty(&c->replay_buds)) {
  639. b = list_entry(c->replay_buds.next, struct bud_entry, list);
  640. list_del(&b->list);
  641. kfree(b);
  642. }
  643. }
  644. /**
  645. * add_replay_bud - add a bud to the list of buds to replay.
  646. * @c: UBIFS file-system description object
  647. * @lnum: bud logical eraseblock number to replay
  648. * @offs: bud start offset
  649. * @jhead: journal head to which this bud belongs
  650. * @sqnum: reference node sequence number
  651. *
  652. * This function returns zero in case of success and a negative error code in
  653. * case of failure.
  654. */
  655. static int add_replay_bud(struct ubifs_info *c, int lnum, int offs, int jhead,
  656. unsigned long long sqnum)
  657. {
  658. struct ubifs_bud *bud;
  659. struct bud_entry *b;
  660. dbg_mnt("add replay bud LEB %d:%d, head %d", lnum, offs, jhead);
  661. bud = kmalloc(sizeof(struct ubifs_bud), GFP_KERNEL);
  662. if (!bud)
  663. return -ENOMEM;
  664. b = kmalloc(sizeof(struct bud_entry), GFP_KERNEL);
  665. if (!b) {
  666. kfree(bud);
  667. return -ENOMEM;
  668. }
  669. bud->lnum = lnum;
  670. bud->start = offs;
  671. bud->jhead = jhead;
  672. ubifs_add_bud(c, bud);
  673. b->bud = bud;
  674. b->sqnum = sqnum;
  675. list_add_tail(&b->list, &c->replay_buds);
  676. return 0;
  677. }
  678. /**
  679. * validate_ref - validate a reference node.
  680. * @c: UBIFS file-system description object
  681. * @ref: the reference node to validate
  682. * @ref_lnum: LEB number of the reference node
  683. * @ref_offs: reference node offset
  684. *
  685. * This function returns %1 if a bud reference already exists for the LEB. %0 is
  686. * returned if the reference node is new, otherwise %-EINVAL is returned if
  687. * validation failed.
  688. */
  689. static int validate_ref(struct ubifs_info *c, const struct ubifs_ref_node *ref)
  690. {
  691. struct ubifs_bud *bud;
  692. int lnum = le32_to_cpu(ref->lnum);
  693. unsigned int offs = le32_to_cpu(ref->offs);
  694. unsigned int jhead = le32_to_cpu(ref->jhead);
  695. /*
  696. * ref->offs may point to the end of LEB when the journal head points
  697. * to the end of LEB and we write reference node for it during commit.
  698. * So this is why we require 'offs > c->leb_size'.
  699. */
  700. if (jhead >= c->jhead_cnt || lnum >= c->leb_cnt ||
  701. lnum < c->main_first || offs > c->leb_size ||
  702. offs & (c->min_io_size - 1))
  703. return -EINVAL;
  704. /* Make sure we have not already looked at this bud */
  705. bud = ubifs_search_bud(c, lnum);
  706. if (bud) {
  707. if (bud->jhead == jhead && bud->start <= offs)
  708. return 1;
  709. ubifs_err(c, "bud at LEB %d:%d was already referred", lnum, offs);
  710. return -EINVAL;
  711. }
  712. return 0;
  713. }
  714. /**
  715. * replay_log_leb - replay a log logical eraseblock.
  716. * @c: UBIFS file-system description object
  717. * @lnum: log logical eraseblock to replay
  718. * @offs: offset to start replaying from
  719. * @sbuf: scan buffer
  720. *
  721. * This function replays a log LEB and returns zero in case of success, %1 if
  722. * this is the last LEB in the log, and a negative error code in case of
  723. * failure.
  724. */
  725. static int replay_log_leb(struct ubifs_info *c, int lnum, int offs, void *sbuf)
  726. {
  727. int err;
  728. struct ubifs_scan_leb *sleb;
  729. struct ubifs_scan_node *snod;
  730. const struct ubifs_cs_node *node;
  731. dbg_mnt("replay log LEB %d:%d", lnum, offs);
  732. sleb = ubifs_scan(c, lnum, offs, sbuf, c->need_recovery);
  733. if (IS_ERR(sleb)) {
  734. if (PTR_ERR(sleb) != -EUCLEAN || !c->need_recovery)
  735. return PTR_ERR(sleb);
  736. /*
  737. * Note, the below function will recover this log LEB only if
  738. * it is the last, because unclean reboots can possibly corrupt
  739. * only the tail of the log.
  740. */
  741. sleb = ubifs_recover_log_leb(c, lnum, offs, sbuf);
  742. if (IS_ERR(sleb))
  743. return PTR_ERR(sleb);
  744. }
  745. if (sleb->nodes_cnt == 0) {
  746. err = 1;
  747. goto out;
  748. }
  749. node = sleb->buf;
  750. snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
  751. if (c->cs_sqnum == 0) {
  752. /*
  753. * This is the first log LEB we are looking at, make sure that
  754. * the first node is a commit start node. Also record its
  755. * sequence number so that UBIFS can determine where the log
  756. * ends, because all nodes which were have higher sequence
  757. * numbers.
  758. */
  759. if (snod->type != UBIFS_CS_NODE) {
  760. ubifs_err(c, "first log node at LEB %d:%d is not CS node",
  761. lnum, offs);
  762. goto out_dump;
  763. }
  764. if (le64_to_cpu(node->cmt_no) != c->cmt_no) {
  765. ubifs_err(c, "first CS node at LEB %d:%d has wrong commit number %llu expected %llu",
  766. lnum, offs,
  767. (unsigned long long)le64_to_cpu(node->cmt_no),
  768. c->cmt_no);
  769. goto out_dump;
  770. }
  771. c->cs_sqnum = le64_to_cpu(node->ch.sqnum);
  772. dbg_mnt("commit start sqnum %llu", c->cs_sqnum);
  773. }
  774. if (snod->sqnum < c->cs_sqnum) {
  775. /*
  776. * This means that we reached end of log and now
  777. * look to the older log data, which was already
  778. * committed but the eraseblock was not erased (UBIFS
  779. * only un-maps it). So this basically means we have to
  780. * exit with "end of log" code.
  781. */
  782. err = 1;
  783. goto out;
  784. }
  785. /* Make sure the first node sits at offset zero of the LEB */
  786. if (snod->offs != 0) {
  787. ubifs_err(c, "first node is not at zero offset");
  788. goto out_dump;
  789. }
  790. list_for_each_entry(snod, &sleb->nodes, list) {
  791. cond_resched();
  792. if (snod->sqnum >= SQNUM_WATERMARK) {
  793. ubifs_err(c, "file system's life ended");
  794. goto out_dump;
  795. }
  796. if (snod->sqnum < c->cs_sqnum) {
  797. ubifs_err(c, "bad sqnum %llu, commit sqnum %llu",
  798. snod->sqnum, c->cs_sqnum);
  799. goto out_dump;
  800. }
  801. if (snod->sqnum > c->max_sqnum)
  802. c->max_sqnum = snod->sqnum;
  803. switch (snod->type) {
  804. case UBIFS_REF_NODE: {
  805. const struct ubifs_ref_node *ref = snod->node;
  806. err = validate_ref(c, ref);
  807. if (err == 1)
  808. break; /* Already have this bud */
  809. if (err)
  810. goto out_dump;
  811. err = add_replay_bud(c, le32_to_cpu(ref->lnum),
  812. le32_to_cpu(ref->offs),
  813. le32_to_cpu(ref->jhead),
  814. snod->sqnum);
  815. if (err)
  816. goto out;
  817. break;
  818. }
  819. case UBIFS_CS_NODE:
  820. /* Make sure it sits at the beginning of LEB */
  821. if (snod->offs != 0) {
  822. ubifs_err(c, "unexpected node in log");
  823. goto out_dump;
  824. }
  825. break;
  826. default:
  827. ubifs_err(c, "unexpected node in log");
  828. goto out_dump;
  829. }
  830. }
  831. if (sleb->endpt || c->lhead_offs >= c->leb_size) {
  832. c->lhead_lnum = lnum;
  833. c->lhead_offs = sleb->endpt;
  834. }
  835. err = !sleb->endpt;
  836. out:
  837. ubifs_scan_destroy(sleb);
  838. return err;
  839. out_dump:
  840. ubifs_err(c, "log error detected while replaying the log at LEB %d:%d",
  841. lnum, offs + snod->offs);
  842. ubifs_dump_node(c, snod->node);
  843. ubifs_scan_destroy(sleb);
  844. return -EINVAL;
  845. }
  846. /**
  847. * take_ihead - update the status of the index head in lprops to 'taken'.
  848. * @c: UBIFS file-system description object
  849. *
  850. * This function returns the amount of free space in the index head LEB or a
  851. * negative error code.
  852. */
  853. static int take_ihead(struct ubifs_info *c)
  854. {
  855. const struct ubifs_lprops *lp;
  856. int err, free;
  857. ubifs_get_lprops(c);
  858. lp = ubifs_lpt_lookup_dirty(c, c->ihead_lnum);
  859. if (IS_ERR(lp)) {
  860. err = PTR_ERR(lp);
  861. goto out;
  862. }
  863. free = lp->free;
  864. lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
  865. lp->flags | LPROPS_TAKEN, 0);
  866. if (IS_ERR(lp)) {
  867. err = PTR_ERR(lp);
  868. goto out;
  869. }
  870. err = free;
  871. out:
  872. ubifs_release_lprops(c);
  873. return err;
  874. }
  875. /**
  876. * ubifs_replay_journal - replay journal.
  877. * @c: UBIFS file-system description object
  878. *
  879. * This function scans the journal, replays and cleans it up. It makes sure all
  880. * memory data structures related to uncommitted journal are built (dirty TNC
  881. * tree, tree of buds, modified lprops, etc).
  882. */
  883. int ubifs_replay_journal(struct ubifs_info *c)
  884. {
  885. int err, lnum, free;
  886. BUILD_BUG_ON(UBIFS_TRUN_KEY > 5);
  887. /* Update the status of the index head in lprops to 'taken' */
  888. free = take_ihead(c);
  889. if (free < 0)
  890. return free; /* Error code */
  891. if (c->ihead_offs != c->leb_size - free) {
  892. ubifs_err(c, "bad index head LEB %d:%d", c->ihead_lnum,
  893. c->ihead_offs);
  894. return -EINVAL;
  895. }
  896. dbg_mnt("start replaying the journal");
  897. c->replaying = 1;
  898. lnum = c->ltail_lnum = c->lhead_lnum;
  899. do {
  900. err = replay_log_leb(c, lnum, 0, c->sbuf);
  901. if (err == 1) {
  902. if (lnum != c->lhead_lnum)
  903. /* We hit the end of the log */
  904. break;
  905. /*
  906. * The head of the log must always start with the
  907. * "commit start" node on a properly formatted UBIFS.
  908. * But we found no nodes at all, which means that
  909. * someting went wrong and we cannot proceed mounting
  910. * the file-system.
  911. */
  912. ubifs_err(c, "no UBIFS nodes found at the log head LEB %d:%d, possibly corrupted",
  913. lnum, 0);
  914. err = -EINVAL;
  915. }
  916. if (err)
  917. goto out;
  918. lnum = ubifs_next_log_lnum(c, lnum);
  919. } while (lnum != c->ltail_lnum);
  920. err = replay_buds(c);
  921. if (err)
  922. goto out;
  923. err = apply_replay_list(c);
  924. if (err)
  925. goto out;
  926. err = set_buds_lprops(c);
  927. if (err)
  928. goto out;
  929. /*
  930. * UBIFS budgeting calculations use @c->bi.uncommitted_idx variable
  931. * to roughly estimate index growth. Things like @c->bi.min_idx_lebs
  932. * depend on it. This means we have to initialize it to make sure
  933. * budgeting works properly.
  934. */
  935. c->bi.uncommitted_idx = atomic_long_read(&c->dirty_zn_cnt);
  936. c->bi.uncommitted_idx *= c->max_idx_node_sz;
  937. ubifs_assert(c->bud_bytes <= c->max_bud_bytes || c->need_recovery);
  938. dbg_mnt("finished, log head LEB %d:%d, max_sqnum %llu, highest_inum %lu",
  939. c->lhead_lnum, c->lhead_offs, c->max_sqnum,
  940. (unsigned long)c->highest_inum);
  941. out:
  942. destroy_replay_list(c);
  943. destroy_bud_list(c);
  944. c->replaying = 0;
  945. return err;
  946. }