replay.c 29 KB

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