replay.c 27 KB

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