replay.c 29 KB

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