recovery.c 42 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557
  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 implements functions needed to recover from unclean un-mounts.
  12. * When UBIFS is mounted, it checks a flag on the master node to determine if
  13. * an un-mount was completed successfully. If not, the process of mounting
  14. * incorporates additional checking and fixing of on-flash data structures.
  15. * UBIFS always cleans away all remnants of an unclean un-mount, so that
  16. * errors do not accumulate. However UBIFS defers recovery if it is mounted
  17. * read-only, and the flash is not modified in that case.
  18. *
  19. * The general UBIFS approach to the recovery is that it recovers from
  20. * corruptions which could be caused by power cuts, but it refuses to recover
  21. * from corruption caused by other reasons. And UBIFS tries to distinguish
  22. * between these 2 reasons of corruptions and silently recover in the former
  23. * case and loudly complain in the latter case.
  24. *
  25. * UBIFS writes only to erased LEBs, so it writes only to the flash space
  26. * containing only 0xFFs. UBIFS also always writes strictly from the beginning
  27. * of the LEB to the end. And UBIFS assumes that the underlying flash media
  28. * writes in @c->max_write_size bytes at a time.
  29. *
  30. * Hence, if UBIFS finds a corrupted node at offset X, it expects only the min.
  31. * I/O unit corresponding to offset X to contain corrupted data, all the
  32. * following min. I/O units have to contain empty space (all 0xFFs). If this is
  33. * not true, the corruption cannot be the result of a power cut, and UBIFS
  34. * refuses to mount.
  35. */
  36. #ifndef __UBOOT__
  37. #include <log.h>
  38. #include <dm/devres.h>
  39. #include <linux/crc32.h>
  40. #include <linux/slab.h>
  41. #include <u-boot/crc.h>
  42. #else
  43. #include <linux/err.h>
  44. #endif
  45. #include "ubifs.h"
  46. /**
  47. * is_empty - determine whether a buffer is empty (contains all 0xff).
  48. * @buf: buffer to clean
  49. * @len: length of buffer
  50. *
  51. * This function returns %1 if the buffer is empty (contains all 0xff) otherwise
  52. * %0 is returned.
  53. */
  54. static int is_empty(void *buf, int len)
  55. {
  56. uint8_t *p = buf;
  57. int i;
  58. for (i = 0; i < len; i++)
  59. if (*p++ != 0xff)
  60. return 0;
  61. return 1;
  62. }
  63. /**
  64. * first_non_ff - find offset of the first non-0xff byte.
  65. * @buf: buffer to search in
  66. * @len: length of buffer
  67. *
  68. * This function returns offset of the first non-0xff byte in @buf or %-1 if
  69. * the buffer contains only 0xff bytes.
  70. */
  71. static int first_non_ff(void *buf, int len)
  72. {
  73. uint8_t *p = buf;
  74. int i;
  75. for (i = 0; i < len; i++)
  76. if (*p++ != 0xff)
  77. return i;
  78. return -1;
  79. }
  80. /**
  81. * get_master_node - get the last valid master node allowing for corruption.
  82. * @c: UBIFS file-system description object
  83. * @lnum: LEB number
  84. * @pbuf: buffer containing the LEB read, is returned here
  85. * @mst: master node, if found, is returned here
  86. * @cor: corruption, if found, is returned here
  87. *
  88. * This function allocates a buffer, reads the LEB into it, and finds and
  89. * returns the last valid master node allowing for one area of corruption.
  90. * The corrupt area, if there is one, must be consistent with the assumption
  91. * that it is the result of an unclean unmount while the master node was being
  92. * written. Under those circumstances, it is valid to use the previously written
  93. * master node.
  94. *
  95. * This function returns %0 on success and a negative error code on failure.
  96. */
  97. static int get_master_node(const struct ubifs_info *c, int lnum, void **pbuf,
  98. struct ubifs_mst_node **mst, void **cor)
  99. {
  100. const int sz = c->mst_node_alsz;
  101. int err, offs, len;
  102. void *sbuf, *buf;
  103. sbuf = vmalloc(c->leb_size);
  104. if (!sbuf)
  105. return -ENOMEM;
  106. err = ubifs_leb_read(c, lnum, sbuf, 0, c->leb_size, 0);
  107. if (err && err != -EBADMSG)
  108. goto out_free;
  109. /* Find the first position that is definitely not a node */
  110. offs = 0;
  111. buf = sbuf;
  112. len = c->leb_size;
  113. while (offs + UBIFS_MST_NODE_SZ <= c->leb_size) {
  114. struct ubifs_ch *ch = buf;
  115. if (le32_to_cpu(ch->magic) != UBIFS_NODE_MAGIC)
  116. break;
  117. offs += sz;
  118. buf += sz;
  119. len -= sz;
  120. }
  121. /* See if there was a valid master node before that */
  122. if (offs) {
  123. int ret;
  124. offs -= sz;
  125. buf -= sz;
  126. len += sz;
  127. ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
  128. if (ret != SCANNED_A_NODE && offs) {
  129. /* Could have been corruption so check one place back */
  130. offs -= sz;
  131. buf -= sz;
  132. len += sz;
  133. ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
  134. if (ret != SCANNED_A_NODE)
  135. /*
  136. * We accept only one area of corruption because
  137. * we are assuming that it was caused while
  138. * trying to write a master node.
  139. */
  140. goto out_err;
  141. }
  142. if (ret == SCANNED_A_NODE) {
  143. struct ubifs_ch *ch = buf;
  144. if (ch->node_type != UBIFS_MST_NODE)
  145. goto out_err;
  146. dbg_rcvry("found a master node at %d:%d", lnum, offs);
  147. *mst = buf;
  148. offs += sz;
  149. buf += sz;
  150. len -= sz;
  151. }
  152. }
  153. /* Check for corruption */
  154. if (offs < c->leb_size) {
  155. if (!is_empty(buf, min_t(int, len, sz))) {
  156. *cor = buf;
  157. dbg_rcvry("found corruption at %d:%d", lnum, offs);
  158. }
  159. offs += sz;
  160. buf += sz;
  161. len -= sz;
  162. }
  163. /* Check remaining empty space */
  164. if (offs < c->leb_size)
  165. if (!is_empty(buf, len))
  166. goto out_err;
  167. *pbuf = sbuf;
  168. return 0;
  169. out_err:
  170. err = -EINVAL;
  171. out_free:
  172. vfree(sbuf);
  173. *mst = NULL;
  174. *cor = NULL;
  175. return err;
  176. }
  177. /**
  178. * write_rcvrd_mst_node - write recovered master node.
  179. * @c: UBIFS file-system description object
  180. * @mst: master node
  181. *
  182. * This function returns %0 on success and a negative error code on failure.
  183. */
  184. static int write_rcvrd_mst_node(struct ubifs_info *c,
  185. struct ubifs_mst_node *mst)
  186. {
  187. int err = 0, lnum = UBIFS_MST_LNUM, sz = c->mst_node_alsz;
  188. __le32 save_flags;
  189. dbg_rcvry("recovery");
  190. save_flags = mst->flags;
  191. mst->flags |= cpu_to_le32(UBIFS_MST_RCVRY);
  192. ubifs_prepare_node(c, mst, UBIFS_MST_NODE_SZ, 1);
  193. err = ubifs_leb_change(c, lnum, mst, sz);
  194. if (err)
  195. goto out;
  196. err = ubifs_leb_change(c, lnum + 1, mst, sz);
  197. if (err)
  198. goto out;
  199. out:
  200. mst->flags = save_flags;
  201. return err;
  202. }
  203. /**
  204. * ubifs_recover_master_node - recover the master node.
  205. * @c: UBIFS file-system description object
  206. *
  207. * This function recovers the master node from corruption that may occur due to
  208. * an unclean unmount.
  209. *
  210. * This function returns %0 on success and a negative error code on failure.
  211. */
  212. int ubifs_recover_master_node(struct ubifs_info *c)
  213. {
  214. void *buf1 = NULL, *buf2 = NULL, *cor1 = NULL, *cor2 = NULL;
  215. struct ubifs_mst_node *mst1 = NULL, *mst2 = NULL, *mst;
  216. const int sz = c->mst_node_alsz;
  217. int err, offs1, offs2;
  218. dbg_rcvry("recovery");
  219. err = get_master_node(c, UBIFS_MST_LNUM, &buf1, &mst1, &cor1);
  220. if (err)
  221. goto out_free;
  222. err = get_master_node(c, UBIFS_MST_LNUM + 1, &buf2, &mst2, &cor2);
  223. if (err)
  224. goto out_free;
  225. if (mst1) {
  226. offs1 = (void *)mst1 - buf1;
  227. if ((le32_to_cpu(mst1->flags) & UBIFS_MST_RCVRY) &&
  228. (offs1 == 0 && !cor1)) {
  229. /*
  230. * mst1 was written by recovery at offset 0 with no
  231. * corruption.
  232. */
  233. dbg_rcvry("recovery recovery");
  234. mst = mst1;
  235. } else if (mst2) {
  236. offs2 = (void *)mst2 - buf2;
  237. if (offs1 == offs2) {
  238. /* Same offset, so must be the same */
  239. if (memcmp((void *)mst1 + UBIFS_CH_SZ,
  240. (void *)mst2 + UBIFS_CH_SZ,
  241. UBIFS_MST_NODE_SZ - UBIFS_CH_SZ))
  242. goto out_err;
  243. mst = mst1;
  244. } else if (offs2 + sz == offs1) {
  245. /* 1st LEB was written, 2nd was not */
  246. if (cor1)
  247. goto out_err;
  248. mst = mst1;
  249. } else if (offs1 == 0 &&
  250. c->leb_size - offs2 - sz < sz) {
  251. /* 1st LEB was unmapped and written, 2nd not */
  252. if (cor1)
  253. goto out_err;
  254. mst = mst1;
  255. } else
  256. goto out_err;
  257. } else {
  258. /*
  259. * 2nd LEB was unmapped and about to be written, so
  260. * there must be only one master node in the first LEB
  261. * and no corruption.
  262. */
  263. if (offs1 != 0 || cor1)
  264. goto out_err;
  265. mst = mst1;
  266. }
  267. } else {
  268. if (!mst2)
  269. goto out_err;
  270. /*
  271. * 1st LEB was unmapped and about to be written, so there must
  272. * be no room left in 2nd LEB.
  273. */
  274. offs2 = (void *)mst2 - buf2;
  275. if (offs2 + sz + sz <= c->leb_size)
  276. goto out_err;
  277. mst = mst2;
  278. }
  279. ubifs_msg(c, "recovered master node from LEB %d",
  280. (mst == mst1 ? UBIFS_MST_LNUM : UBIFS_MST_LNUM + 1));
  281. memcpy(c->mst_node, mst, UBIFS_MST_NODE_SZ);
  282. if (c->ro_mount) {
  283. /* Read-only mode. Keep a copy for switching to rw mode */
  284. c->rcvrd_mst_node = kmalloc(sz, GFP_KERNEL);
  285. if (!c->rcvrd_mst_node) {
  286. err = -ENOMEM;
  287. goto out_free;
  288. }
  289. memcpy(c->rcvrd_mst_node, c->mst_node, UBIFS_MST_NODE_SZ);
  290. /*
  291. * We had to recover the master node, which means there was an
  292. * unclean reboot. However, it is possible that the master node
  293. * is clean at this point, i.e., %UBIFS_MST_DIRTY is not set.
  294. * E.g., consider the following chain of events:
  295. *
  296. * 1. UBIFS was cleanly unmounted, so the master node is clean
  297. * 2. UBIFS is being mounted R/W and starts changing the master
  298. * node in the first (%UBIFS_MST_LNUM). A power cut happens,
  299. * so this LEB ends up with some amount of garbage at the
  300. * end.
  301. * 3. UBIFS is being mounted R/O. We reach this place and
  302. * recover the master node from the second LEB
  303. * (%UBIFS_MST_LNUM + 1). But we cannot update the media
  304. * because we are being mounted R/O. We have to defer the
  305. * operation.
  306. * 4. However, this master node (@c->mst_node) is marked as
  307. * clean (since the step 1). And if we just return, the
  308. * mount code will be confused and won't recover the master
  309. * node when it is re-mounter R/W later.
  310. *
  311. * Thus, to force the recovery by marking the master node as
  312. * dirty.
  313. */
  314. c->mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
  315. #ifndef __UBOOT__
  316. } else {
  317. /* Write the recovered master node */
  318. c->max_sqnum = le64_to_cpu(mst->ch.sqnum) - 1;
  319. err = write_rcvrd_mst_node(c, c->mst_node);
  320. if (err)
  321. goto out_free;
  322. #endif
  323. }
  324. vfree(buf2);
  325. vfree(buf1);
  326. return 0;
  327. out_err:
  328. err = -EINVAL;
  329. out_free:
  330. ubifs_err(c, "failed to recover master node");
  331. if (mst1) {
  332. ubifs_err(c, "dumping first master node");
  333. ubifs_dump_node(c, mst1);
  334. }
  335. if (mst2) {
  336. ubifs_err(c, "dumping second master node");
  337. ubifs_dump_node(c, mst2);
  338. }
  339. vfree(buf2);
  340. vfree(buf1);
  341. return err;
  342. }
  343. /**
  344. * ubifs_write_rcvrd_mst_node - write the recovered master node.
  345. * @c: UBIFS file-system description object
  346. *
  347. * This function writes the master node that was recovered during mounting in
  348. * read-only mode and must now be written because we are remounting rw.
  349. *
  350. * This function returns %0 on success and a negative error code on failure.
  351. */
  352. int ubifs_write_rcvrd_mst_node(struct ubifs_info *c)
  353. {
  354. int err;
  355. if (!c->rcvrd_mst_node)
  356. return 0;
  357. c->rcvrd_mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
  358. c->mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
  359. err = write_rcvrd_mst_node(c, c->rcvrd_mst_node);
  360. if (err)
  361. return err;
  362. kfree(c->rcvrd_mst_node);
  363. c->rcvrd_mst_node = NULL;
  364. return 0;
  365. }
  366. /**
  367. * is_last_write - determine if an offset was in the last write to a LEB.
  368. * @c: UBIFS file-system description object
  369. * @buf: buffer to check
  370. * @offs: offset to check
  371. *
  372. * This function returns %1 if @offs was in the last write to the LEB whose data
  373. * is in @buf, otherwise %0 is returned. The determination is made by checking
  374. * for subsequent empty space starting from the next @c->max_write_size
  375. * boundary.
  376. */
  377. static int is_last_write(const struct ubifs_info *c, void *buf, int offs)
  378. {
  379. int empty_offs, check_len;
  380. uint8_t *p;
  381. /*
  382. * Round up to the next @c->max_write_size boundary i.e. @offs is in
  383. * the last wbuf written. After that should be empty space.
  384. */
  385. empty_offs = ALIGN(offs + 1, c->max_write_size);
  386. check_len = c->leb_size - empty_offs;
  387. p = buf + empty_offs - offs;
  388. return is_empty(p, check_len);
  389. }
  390. /**
  391. * clean_buf - clean the data from an LEB sitting in a buffer.
  392. * @c: UBIFS file-system description object
  393. * @buf: buffer to clean
  394. * @lnum: LEB number to clean
  395. * @offs: offset from which to clean
  396. * @len: length of buffer
  397. *
  398. * This function pads up to the next min_io_size boundary (if there is one) and
  399. * sets empty space to all 0xff. @buf, @offs and @len are updated to the next
  400. * @c->min_io_size boundary.
  401. */
  402. static void clean_buf(const struct ubifs_info *c, void **buf, int lnum,
  403. int *offs, int *len)
  404. {
  405. int empty_offs, pad_len;
  406. lnum = lnum;
  407. dbg_rcvry("cleaning corruption at %d:%d", lnum, *offs);
  408. ubifs_assert(!(*offs & 7));
  409. empty_offs = ALIGN(*offs, c->min_io_size);
  410. pad_len = empty_offs - *offs;
  411. ubifs_pad(c, *buf, pad_len);
  412. *offs += pad_len;
  413. *buf += pad_len;
  414. *len -= pad_len;
  415. memset(*buf, 0xff, c->leb_size - empty_offs);
  416. }
  417. /**
  418. * no_more_nodes - determine if there are no more nodes in a buffer.
  419. * @c: UBIFS file-system description object
  420. * @buf: buffer to check
  421. * @len: length of buffer
  422. * @lnum: LEB number of the LEB from which @buf was read
  423. * @offs: offset from which @buf was read
  424. *
  425. * This function ensures that the corrupted node at @offs is the last thing
  426. * written to a LEB. This function returns %1 if more data is not found and
  427. * %0 if more data is found.
  428. */
  429. static int no_more_nodes(const struct ubifs_info *c, void *buf, int len,
  430. int lnum, int offs)
  431. {
  432. struct ubifs_ch *ch = buf;
  433. int skip, dlen = le32_to_cpu(ch->len);
  434. /* Check for empty space after the corrupt node's common header */
  435. skip = ALIGN(offs + UBIFS_CH_SZ, c->max_write_size) - offs;
  436. if (is_empty(buf + skip, len - skip))
  437. return 1;
  438. /*
  439. * The area after the common header size is not empty, so the common
  440. * header must be intact. Check it.
  441. */
  442. if (ubifs_check_node(c, buf, lnum, offs, 1, 0) != -EUCLEAN) {
  443. dbg_rcvry("unexpected bad common header at %d:%d", lnum, offs);
  444. return 0;
  445. }
  446. /* Now we know the corrupt node's length we can skip over it */
  447. skip = ALIGN(offs + dlen, c->max_write_size) - offs;
  448. /* After which there should be empty space */
  449. if (is_empty(buf + skip, len - skip))
  450. return 1;
  451. dbg_rcvry("unexpected data at %d:%d", lnum, offs + skip);
  452. return 0;
  453. }
  454. /**
  455. * fix_unclean_leb - fix an unclean LEB.
  456. * @c: UBIFS file-system description object
  457. * @sleb: scanned LEB information
  458. * @start: offset where scan started
  459. */
  460. static int fix_unclean_leb(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
  461. int start)
  462. {
  463. int lnum = sleb->lnum, endpt = start;
  464. /* Get the end offset of the last node we are keeping */
  465. if (!list_empty(&sleb->nodes)) {
  466. struct ubifs_scan_node *snod;
  467. snod = list_entry(sleb->nodes.prev,
  468. struct ubifs_scan_node, list);
  469. endpt = snod->offs + snod->len;
  470. }
  471. if (c->ro_mount && !c->remounting_rw) {
  472. /* Add to recovery list */
  473. struct ubifs_unclean_leb *ucleb;
  474. dbg_rcvry("need to fix LEB %d start %d endpt %d",
  475. lnum, start, sleb->endpt);
  476. ucleb = kzalloc(sizeof(struct ubifs_unclean_leb), GFP_NOFS);
  477. if (!ucleb)
  478. return -ENOMEM;
  479. ucleb->lnum = lnum;
  480. ucleb->endpt = endpt;
  481. list_add_tail(&ucleb->list, &c->unclean_leb_list);
  482. #ifndef __UBOOT__
  483. } else {
  484. /* Write the fixed LEB back to flash */
  485. int err;
  486. dbg_rcvry("fixing LEB %d start %d endpt %d",
  487. lnum, start, sleb->endpt);
  488. if (endpt == 0) {
  489. err = ubifs_leb_unmap(c, lnum);
  490. if (err)
  491. return err;
  492. } else {
  493. int len = ALIGN(endpt, c->min_io_size);
  494. if (start) {
  495. err = ubifs_leb_read(c, lnum, sleb->buf, 0,
  496. start, 1);
  497. if (err)
  498. return err;
  499. }
  500. /* Pad to min_io_size */
  501. if (len > endpt) {
  502. int pad_len = len - ALIGN(endpt, 8);
  503. if (pad_len > 0) {
  504. void *buf = sleb->buf + len - pad_len;
  505. ubifs_pad(c, buf, pad_len);
  506. }
  507. }
  508. err = ubifs_leb_change(c, lnum, sleb->buf, len);
  509. if (err)
  510. return err;
  511. }
  512. #endif
  513. }
  514. return 0;
  515. }
  516. /**
  517. * drop_last_group - drop the last group of nodes.
  518. * @sleb: scanned LEB information
  519. * @offs: offset of dropped nodes is returned here
  520. *
  521. * This is a helper function for 'ubifs_recover_leb()' which drops the last
  522. * group of nodes of the scanned LEB.
  523. */
  524. static void drop_last_group(struct ubifs_scan_leb *sleb, int *offs)
  525. {
  526. while (!list_empty(&sleb->nodes)) {
  527. struct ubifs_scan_node *snod;
  528. struct ubifs_ch *ch;
  529. snod = list_entry(sleb->nodes.prev, struct ubifs_scan_node,
  530. list);
  531. ch = snod->node;
  532. if (ch->group_type != UBIFS_IN_NODE_GROUP)
  533. break;
  534. dbg_rcvry("dropping grouped node at %d:%d",
  535. sleb->lnum, snod->offs);
  536. *offs = snod->offs;
  537. list_del(&snod->list);
  538. kfree(snod);
  539. sleb->nodes_cnt -= 1;
  540. }
  541. }
  542. /**
  543. * drop_last_node - drop the last node.
  544. * @sleb: scanned LEB information
  545. * @offs: offset of dropped nodes is returned here
  546. *
  547. * This is a helper function for 'ubifs_recover_leb()' which drops the last
  548. * node of the scanned LEB.
  549. */
  550. static void drop_last_node(struct ubifs_scan_leb *sleb, int *offs)
  551. {
  552. struct ubifs_scan_node *snod;
  553. if (!list_empty(&sleb->nodes)) {
  554. snod = list_entry(sleb->nodes.prev, struct ubifs_scan_node,
  555. list);
  556. dbg_rcvry("dropping last node at %d:%d",
  557. sleb->lnum, snod->offs);
  558. *offs = snod->offs;
  559. list_del(&snod->list);
  560. kfree(snod);
  561. sleb->nodes_cnt -= 1;
  562. }
  563. }
  564. /**
  565. * ubifs_recover_leb - scan and recover a LEB.
  566. * @c: UBIFS file-system description object
  567. * @lnum: LEB number
  568. * @offs: offset
  569. * @sbuf: LEB-sized buffer to use
  570. * @jhead: journal head number this LEB belongs to (%-1 if the LEB does not
  571. * belong to any journal head)
  572. *
  573. * This function does a scan of a LEB, but caters for errors that might have
  574. * been caused by the unclean unmount from which we are attempting to recover.
  575. * Returns the scanned information on success and a negative error code on
  576. * failure.
  577. */
  578. struct ubifs_scan_leb *ubifs_recover_leb(struct ubifs_info *c, int lnum,
  579. int offs, void *sbuf, int jhead)
  580. {
  581. int ret = 0, err, len = c->leb_size - offs, start = offs, min_io_unit;
  582. int grouped = jhead == -1 ? 0 : c->jheads[jhead].grouped;
  583. struct ubifs_scan_leb *sleb;
  584. void *buf = sbuf + offs;
  585. dbg_rcvry("%d:%d, jhead %d, grouped %d", lnum, offs, jhead, grouped);
  586. sleb = ubifs_start_scan(c, lnum, offs, sbuf);
  587. if (IS_ERR(sleb))
  588. return sleb;
  589. ubifs_assert(len >= 8);
  590. while (len >= 8) {
  591. dbg_scan("look at LEB %d:%d (%d bytes left)",
  592. lnum, offs, len);
  593. cond_resched();
  594. /*
  595. * Scan quietly until there is an error from which we cannot
  596. * recover
  597. */
  598. ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
  599. if (ret == SCANNED_A_NODE) {
  600. /* A valid node, and not a padding node */
  601. struct ubifs_ch *ch = buf;
  602. int node_len;
  603. err = ubifs_add_snod(c, sleb, buf, offs);
  604. if (err)
  605. goto error;
  606. node_len = ALIGN(le32_to_cpu(ch->len), 8);
  607. offs += node_len;
  608. buf += node_len;
  609. len -= node_len;
  610. } else if (ret > 0) {
  611. /* Padding bytes or a valid padding node */
  612. offs += ret;
  613. buf += ret;
  614. len -= ret;
  615. } else if (ret == SCANNED_EMPTY_SPACE ||
  616. ret == SCANNED_GARBAGE ||
  617. ret == SCANNED_A_BAD_PAD_NODE ||
  618. ret == SCANNED_A_CORRUPT_NODE) {
  619. dbg_rcvry("found corruption (%d) at %d:%d",
  620. ret, lnum, offs);
  621. break;
  622. } else {
  623. ubifs_err(c, "unexpected return value %d", ret);
  624. err = -EINVAL;
  625. goto error;
  626. }
  627. }
  628. if (ret == SCANNED_GARBAGE || ret == SCANNED_A_BAD_PAD_NODE) {
  629. if (!is_last_write(c, buf, offs))
  630. goto corrupted_rescan;
  631. } else if (ret == SCANNED_A_CORRUPT_NODE) {
  632. if (!no_more_nodes(c, buf, len, lnum, offs))
  633. goto corrupted_rescan;
  634. } else if (!is_empty(buf, len)) {
  635. if (!is_last_write(c, buf, offs)) {
  636. int corruption = first_non_ff(buf, len);
  637. /*
  638. * See header comment for this file for more
  639. * explanations about the reasons we have this check.
  640. */
  641. ubifs_err(c, "corrupt empty space LEB %d:%d, corruption starts at %d",
  642. lnum, offs, corruption);
  643. /* Make sure we dump interesting non-0xFF data */
  644. offs += corruption;
  645. buf += corruption;
  646. goto corrupted;
  647. }
  648. }
  649. min_io_unit = round_down(offs, c->min_io_size);
  650. if (grouped)
  651. /*
  652. * If nodes are grouped, always drop the incomplete group at
  653. * the end.
  654. */
  655. drop_last_group(sleb, &offs);
  656. if (jhead == GCHD) {
  657. /*
  658. * If this LEB belongs to the GC head then while we are in the
  659. * middle of the same min. I/O unit keep dropping nodes. So
  660. * basically, what we want is to make sure that the last min.
  661. * I/O unit where we saw the corruption is dropped completely
  662. * with all the uncorrupted nodes which may possibly sit there.
  663. *
  664. * In other words, let's name the min. I/O unit where the
  665. * corruption starts B, and the previous min. I/O unit A. The
  666. * below code tries to deal with a situation when half of B
  667. * contains valid nodes or the end of a valid node, and the
  668. * second half of B contains corrupted data or garbage. This
  669. * means that UBIFS had been writing to B just before the power
  670. * cut happened. I do not know how realistic is this scenario
  671. * that half of the min. I/O unit had been written successfully
  672. * and the other half not, but this is possible in our 'failure
  673. * mode emulation' infrastructure at least.
  674. *
  675. * So what is the problem, why we need to drop those nodes? Why
  676. * can't we just clean-up the second half of B by putting a
  677. * padding node there? We can, and this works fine with one
  678. * exception which was reproduced with power cut emulation
  679. * testing and happens extremely rarely.
  680. *
  681. * Imagine the file-system is full, we run GC which starts
  682. * moving valid nodes from LEB X to LEB Y (obviously, LEB Y is
  683. * the current GC head LEB). The @c->gc_lnum is -1, which means
  684. * that GC will retain LEB X and will try to continue. Imagine
  685. * that LEB X is currently the dirtiest LEB, and the amount of
  686. * used space in LEB Y is exactly the same as amount of free
  687. * space in LEB X.
  688. *
  689. * And a power cut happens when nodes are moved from LEB X to
  690. * LEB Y. We are here trying to recover LEB Y which is the GC
  691. * head LEB. We find the min. I/O unit B as described above.
  692. * Then we clean-up LEB Y by padding min. I/O unit. And later
  693. * 'ubifs_rcvry_gc_commit()' function fails, because it cannot
  694. * find a dirty LEB which could be GC'd into LEB Y! Even LEB X
  695. * does not match because the amount of valid nodes there does
  696. * not fit the free space in LEB Y any more! And this is
  697. * because of the padding node which we added to LEB Y. The
  698. * user-visible effect of this which I once observed and
  699. * analysed is that we cannot mount the file-system with
  700. * -ENOSPC error.
  701. *
  702. * So obviously, to make sure that situation does not happen we
  703. * should free min. I/O unit B in LEB Y completely and the last
  704. * used min. I/O unit in LEB Y should be A. This is basically
  705. * what the below code tries to do.
  706. */
  707. while (offs > min_io_unit)
  708. drop_last_node(sleb, &offs);
  709. }
  710. buf = sbuf + offs;
  711. len = c->leb_size - offs;
  712. clean_buf(c, &buf, lnum, &offs, &len);
  713. ubifs_end_scan(c, sleb, lnum, offs);
  714. err = fix_unclean_leb(c, sleb, start);
  715. if (err)
  716. goto error;
  717. return sleb;
  718. corrupted_rescan:
  719. /* Re-scan the corrupted data with verbose messages */
  720. ubifs_err(c, "corruption %d", ret);
  721. ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
  722. corrupted:
  723. ubifs_scanned_corruption(c, lnum, offs, buf);
  724. err = -EUCLEAN;
  725. error:
  726. ubifs_err(c, "LEB %d scanning failed", lnum);
  727. ubifs_scan_destroy(sleb);
  728. return ERR_PTR(err);
  729. }
  730. /**
  731. * get_cs_sqnum - get commit start sequence number.
  732. * @c: UBIFS file-system description object
  733. * @lnum: LEB number of commit start node
  734. * @offs: offset of commit start node
  735. * @cs_sqnum: commit start sequence number is returned here
  736. *
  737. * This function returns %0 on success and a negative error code on failure.
  738. */
  739. static int get_cs_sqnum(struct ubifs_info *c, int lnum, int offs,
  740. unsigned long long *cs_sqnum)
  741. {
  742. struct ubifs_cs_node *cs_node = NULL;
  743. int err, ret;
  744. dbg_rcvry("at %d:%d", lnum, offs);
  745. cs_node = kmalloc(UBIFS_CS_NODE_SZ, GFP_KERNEL);
  746. if (!cs_node)
  747. return -ENOMEM;
  748. if (c->leb_size - offs < UBIFS_CS_NODE_SZ)
  749. goto out_err;
  750. err = ubifs_leb_read(c, lnum, (void *)cs_node, offs,
  751. UBIFS_CS_NODE_SZ, 0);
  752. if (err && err != -EBADMSG)
  753. goto out_free;
  754. ret = ubifs_scan_a_node(c, cs_node, UBIFS_CS_NODE_SZ, lnum, offs, 0);
  755. if (ret != SCANNED_A_NODE) {
  756. ubifs_err(c, "Not a valid node");
  757. goto out_err;
  758. }
  759. if (cs_node->ch.node_type != UBIFS_CS_NODE) {
  760. ubifs_err(c, "Node a CS node, type is %d", cs_node->ch.node_type);
  761. goto out_err;
  762. }
  763. if (le64_to_cpu(cs_node->cmt_no) != c->cmt_no) {
  764. ubifs_err(c, "CS node cmt_no %llu != current cmt_no %llu",
  765. (unsigned long long)le64_to_cpu(cs_node->cmt_no),
  766. c->cmt_no);
  767. goto out_err;
  768. }
  769. *cs_sqnum = le64_to_cpu(cs_node->ch.sqnum);
  770. dbg_rcvry("commit start sqnum %llu", *cs_sqnum);
  771. kfree(cs_node);
  772. return 0;
  773. out_err:
  774. err = -EINVAL;
  775. out_free:
  776. ubifs_err(c, "failed to get CS sqnum");
  777. kfree(cs_node);
  778. return err;
  779. }
  780. /**
  781. * ubifs_recover_log_leb - scan and recover a log LEB.
  782. * @c: UBIFS file-system description object
  783. * @lnum: LEB number
  784. * @offs: offset
  785. * @sbuf: LEB-sized buffer to use
  786. *
  787. * This function does a scan of a LEB, but caters for errors that might have
  788. * been caused by unclean reboots from which we are attempting to recover
  789. * (assume that only the last log LEB can be corrupted by an unclean reboot).
  790. *
  791. * This function returns %0 on success and a negative error code on failure.
  792. */
  793. struct ubifs_scan_leb *ubifs_recover_log_leb(struct ubifs_info *c, int lnum,
  794. int offs, void *sbuf)
  795. {
  796. struct ubifs_scan_leb *sleb;
  797. int next_lnum;
  798. dbg_rcvry("LEB %d", lnum);
  799. next_lnum = lnum + 1;
  800. if (next_lnum >= UBIFS_LOG_LNUM + c->log_lebs)
  801. next_lnum = UBIFS_LOG_LNUM;
  802. if (next_lnum != c->ltail_lnum) {
  803. /*
  804. * We can only recover at the end of the log, so check that the
  805. * next log LEB is empty or out of date.
  806. */
  807. sleb = ubifs_scan(c, next_lnum, 0, sbuf, 0);
  808. if (IS_ERR(sleb))
  809. return sleb;
  810. if (sleb->nodes_cnt) {
  811. struct ubifs_scan_node *snod;
  812. unsigned long long cs_sqnum = c->cs_sqnum;
  813. snod = list_entry(sleb->nodes.next,
  814. struct ubifs_scan_node, list);
  815. if (cs_sqnum == 0) {
  816. int err;
  817. err = get_cs_sqnum(c, lnum, offs, &cs_sqnum);
  818. if (err) {
  819. ubifs_scan_destroy(sleb);
  820. return ERR_PTR(err);
  821. }
  822. }
  823. if (snod->sqnum > cs_sqnum) {
  824. ubifs_err(c, "unrecoverable log corruption in LEB %d",
  825. lnum);
  826. ubifs_scan_destroy(sleb);
  827. return ERR_PTR(-EUCLEAN);
  828. }
  829. }
  830. ubifs_scan_destroy(sleb);
  831. }
  832. return ubifs_recover_leb(c, lnum, offs, sbuf, -1);
  833. }
  834. /**
  835. * recover_head - recover a head.
  836. * @c: UBIFS file-system description object
  837. * @lnum: LEB number of head to recover
  838. * @offs: offset of head to recover
  839. * @sbuf: LEB-sized buffer to use
  840. *
  841. * This function ensures that there is no data on the flash at a head location.
  842. *
  843. * This function returns %0 on success and a negative error code on failure.
  844. */
  845. static int recover_head(struct ubifs_info *c, int lnum, int offs, void *sbuf)
  846. {
  847. int len = c->max_write_size, err;
  848. if (offs + len > c->leb_size)
  849. len = c->leb_size - offs;
  850. if (!len)
  851. return 0;
  852. /* Read at the head location and check it is empty flash */
  853. err = ubifs_leb_read(c, lnum, sbuf, offs, len, 1);
  854. if (err || !is_empty(sbuf, len)) {
  855. dbg_rcvry("cleaning head at %d:%d", lnum, offs);
  856. if (offs == 0)
  857. return ubifs_leb_unmap(c, lnum);
  858. err = ubifs_leb_read(c, lnum, sbuf, 0, offs, 1);
  859. if (err)
  860. return err;
  861. return ubifs_leb_change(c, lnum, sbuf, offs);
  862. }
  863. return 0;
  864. }
  865. /**
  866. * ubifs_recover_inl_heads - recover index and LPT heads.
  867. * @c: UBIFS file-system description object
  868. * @sbuf: LEB-sized buffer to use
  869. *
  870. * This function ensures that there is no data on the flash at the index and
  871. * LPT head locations.
  872. *
  873. * This deals with the recovery of a half-completed journal commit. UBIFS is
  874. * careful never to overwrite the last version of the index or the LPT. Because
  875. * the index and LPT are wandering trees, data from a half-completed commit will
  876. * not be referenced anywhere in UBIFS. The data will be either in LEBs that are
  877. * assumed to be empty and will be unmapped anyway before use, or in the index
  878. * and LPT heads.
  879. *
  880. * This function returns %0 on success and a negative error code on failure.
  881. */
  882. int ubifs_recover_inl_heads(struct ubifs_info *c, void *sbuf)
  883. {
  884. int err;
  885. ubifs_assert(!c->ro_mount || c->remounting_rw);
  886. dbg_rcvry("checking index head at %d:%d", c->ihead_lnum, c->ihead_offs);
  887. err = recover_head(c, c->ihead_lnum, c->ihead_offs, sbuf);
  888. if (err)
  889. return err;
  890. dbg_rcvry("checking LPT head at %d:%d", c->nhead_lnum, c->nhead_offs);
  891. return recover_head(c, c->nhead_lnum, c->nhead_offs, sbuf);
  892. }
  893. /**
  894. * clean_an_unclean_leb - read and write a LEB to remove corruption.
  895. * @c: UBIFS file-system description object
  896. * @ucleb: unclean LEB information
  897. * @sbuf: LEB-sized buffer to use
  898. *
  899. * This function reads a LEB up to a point pre-determined by the mount recovery,
  900. * checks the nodes, and writes the result back to the flash, thereby cleaning
  901. * off any following corruption, or non-fatal ECC errors.
  902. *
  903. * This function returns %0 on success and a negative error code on failure.
  904. */
  905. static int clean_an_unclean_leb(struct ubifs_info *c,
  906. struct ubifs_unclean_leb *ucleb, void *sbuf)
  907. {
  908. int err, lnum = ucleb->lnum, offs = 0, len = ucleb->endpt, quiet = 1;
  909. void *buf = sbuf;
  910. dbg_rcvry("LEB %d len %d", lnum, len);
  911. if (len == 0) {
  912. /* Nothing to read, just unmap it */
  913. return ubifs_leb_unmap(c, lnum);
  914. }
  915. err = ubifs_leb_read(c, lnum, buf, offs, len, 0);
  916. if (err && err != -EBADMSG)
  917. return err;
  918. while (len >= 8) {
  919. int ret;
  920. cond_resched();
  921. /* Scan quietly until there is an error */
  922. ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet);
  923. if (ret == SCANNED_A_NODE) {
  924. /* A valid node, and not a padding node */
  925. struct ubifs_ch *ch = buf;
  926. int node_len;
  927. node_len = ALIGN(le32_to_cpu(ch->len), 8);
  928. offs += node_len;
  929. buf += node_len;
  930. len -= node_len;
  931. continue;
  932. }
  933. if (ret > 0) {
  934. /* Padding bytes or a valid padding node */
  935. offs += ret;
  936. buf += ret;
  937. len -= ret;
  938. continue;
  939. }
  940. if (ret == SCANNED_EMPTY_SPACE) {
  941. ubifs_err(c, "unexpected empty space at %d:%d",
  942. lnum, offs);
  943. return -EUCLEAN;
  944. }
  945. if (quiet) {
  946. /* Redo the last scan but noisily */
  947. quiet = 0;
  948. continue;
  949. }
  950. ubifs_scanned_corruption(c, lnum, offs, buf);
  951. return -EUCLEAN;
  952. }
  953. /* Pad to min_io_size */
  954. len = ALIGN(ucleb->endpt, c->min_io_size);
  955. if (len > ucleb->endpt) {
  956. int pad_len = len - ALIGN(ucleb->endpt, 8);
  957. if (pad_len > 0) {
  958. buf = c->sbuf + len - pad_len;
  959. ubifs_pad(c, buf, pad_len);
  960. }
  961. }
  962. /* Write back the LEB atomically */
  963. err = ubifs_leb_change(c, lnum, sbuf, len);
  964. if (err)
  965. return err;
  966. dbg_rcvry("cleaned LEB %d", lnum);
  967. return 0;
  968. }
  969. /**
  970. * ubifs_clean_lebs - clean LEBs recovered during read-only mount.
  971. * @c: UBIFS file-system description object
  972. * @sbuf: LEB-sized buffer to use
  973. *
  974. * This function cleans a LEB identified during recovery that needs to be
  975. * written but was not because UBIFS was mounted read-only. This happens when
  976. * remounting to read-write mode.
  977. *
  978. * This function returns %0 on success and a negative error code on failure.
  979. */
  980. int ubifs_clean_lebs(struct ubifs_info *c, void *sbuf)
  981. {
  982. dbg_rcvry("recovery");
  983. while (!list_empty(&c->unclean_leb_list)) {
  984. struct ubifs_unclean_leb *ucleb;
  985. int err;
  986. ucleb = list_entry(c->unclean_leb_list.next,
  987. struct ubifs_unclean_leb, list);
  988. err = clean_an_unclean_leb(c, ucleb, sbuf);
  989. if (err)
  990. return err;
  991. list_del(&ucleb->list);
  992. kfree(ucleb);
  993. }
  994. return 0;
  995. }
  996. #ifndef __UBOOT__
  997. /**
  998. * grab_empty_leb - grab an empty LEB to use as GC LEB and run commit.
  999. * @c: UBIFS file-system description object
  1000. *
  1001. * This is a helper function for 'ubifs_rcvry_gc_commit()' which grabs an empty
  1002. * LEB to be used as GC LEB (@c->gc_lnum), and then runs the commit. Returns
  1003. * zero in case of success and a negative error code in case of failure.
  1004. */
  1005. static int grab_empty_leb(struct ubifs_info *c)
  1006. {
  1007. int lnum, err;
  1008. /*
  1009. * Note, it is very important to first search for an empty LEB and then
  1010. * run the commit, not vice-versa. The reason is that there might be
  1011. * only one empty LEB at the moment, the one which has been the
  1012. * @c->gc_lnum just before the power cut happened. During the regular
  1013. * UBIFS operation (not now) @c->gc_lnum is marked as "taken", so no
  1014. * one but GC can grab it. But at this moment this single empty LEB is
  1015. * not marked as taken, so if we run commit - what happens? Right, the
  1016. * commit will grab it and write the index there. Remember that the
  1017. * index always expands as long as there is free space, and it only
  1018. * starts consolidating when we run out of space.
  1019. *
  1020. * IOW, if we run commit now, we might not be able to find a free LEB
  1021. * after this.
  1022. */
  1023. lnum = ubifs_find_free_leb_for_idx(c);
  1024. if (lnum < 0) {
  1025. ubifs_err(c, "could not find an empty LEB");
  1026. ubifs_dump_lprops(c);
  1027. ubifs_dump_budg(c, &c->bi);
  1028. return lnum;
  1029. }
  1030. /* Reset the index flag */
  1031. err = ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
  1032. LPROPS_INDEX, 0);
  1033. if (err)
  1034. return err;
  1035. c->gc_lnum = lnum;
  1036. dbg_rcvry("found empty LEB %d, run commit", lnum);
  1037. return ubifs_run_commit(c);
  1038. }
  1039. /**
  1040. * ubifs_rcvry_gc_commit - recover the GC LEB number and run the commit.
  1041. * @c: UBIFS file-system description object
  1042. *
  1043. * Out-of-place garbage collection requires always one empty LEB with which to
  1044. * start garbage collection. The LEB number is recorded in c->gc_lnum and is
  1045. * written to the master node on unmounting. In the case of an unclean unmount
  1046. * the value of gc_lnum recorded in the master node is out of date and cannot
  1047. * be used. Instead, recovery must allocate an empty LEB for this purpose.
  1048. * However, there may not be enough empty space, in which case it must be
  1049. * possible to GC the dirtiest LEB into the GC head LEB.
  1050. *
  1051. * This function also runs the commit which causes the TNC updates from
  1052. * size-recovery and orphans to be written to the flash. That is important to
  1053. * ensure correct replay order for subsequent mounts.
  1054. *
  1055. * This function returns %0 on success and a negative error code on failure.
  1056. */
  1057. int ubifs_rcvry_gc_commit(struct ubifs_info *c)
  1058. {
  1059. struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
  1060. struct ubifs_lprops lp;
  1061. int err;
  1062. dbg_rcvry("GC head LEB %d, offs %d", wbuf->lnum, wbuf->offs);
  1063. c->gc_lnum = -1;
  1064. if (wbuf->lnum == -1 || wbuf->offs == c->leb_size)
  1065. return grab_empty_leb(c);
  1066. err = ubifs_find_dirty_leb(c, &lp, wbuf->offs, 2);
  1067. if (err) {
  1068. if (err != -ENOSPC)
  1069. return err;
  1070. dbg_rcvry("could not find a dirty LEB");
  1071. return grab_empty_leb(c);
  1072. }
  1073. ubifs_assert(!(lp.flags & LPROPS_INDEX));
  1074. ubifs_assert(lp.free + lp.dirty >= wbuf->offs);
  1075. /*
  1076. * We run the commit before garbage collection otherwise subsequent
  1077. * mounts will see the GC and orphan deletion in a different order.
  1078. */
  1079. dbg_rcvry("committing");
  1080. err = ubifs_run_commit(c);
  1081. if (err)
  1082. return err;
  1083. dbg_rcvry("GC'ing LEB %d", lp.lnum);
  1084. mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
  1085. err = ubifs_garbage_collect_leb(c, &lp);
  1086. if (err >= 0) {
  1087. int err2 = ubifs_wbuf_sync_nolock(wbuf);
  1088. if (err2)
  1089. err = err2;
  1090. }
  1091. mutex_unlock(&wbuf->io_mutex);
  1092. if (err < 0) {
  1093. ubifs_err(c, "GC failed, error %d", err);
  1094. if (err == -EAGAIN)
  1095. err = -EINVAL;
  1096. return err;
  1097. }
  1098. ubifs_assert(err == LEB_RETAINED);
  1099. if (err != LEB_RETAINED)
  1100. return -EINVAL;
  1101. err = ubifs_leb_unmap(c, c->gc_lnum);
  1102. if (err)
  1103. return err;
  1104. dbg_rcvry("allocated LEB %d for GC", lp.lnum);
  1105. return 0;
  1106. }
  1107. #else
  1108. int ubifs_rcvry_gc_commit(struct ubifs_info *c)
  1109. {
  1110. return 0;
  1111. }
  1112. #endif
  1113. /**
  1114. * struct size_entry - inode size information for recovery.
  1115. * @rb: link in the RB-tree of sizes
  1116. * @inum: inode number
  1117. * @i_size: size on inode
  1118. * @d_size: maximum size based on data nodes
  1119. * @exists: indicates whether the inode exists
  1120. * @inode: inode if pinned in memory awaiting rw mode to fix it
  1121. */
  1122. struct size_entry {
  1123. struct rb_node rb;
  1124. ino_t inum;
  1125. loff_t i_size;
  1126. loff_t d_size;
  1127. int exists;
  1128. struct inode *inode;
  1129. };
  1130. /**
  1131. * add_ino - add an entry to the size tree.
  1132. * @c: UBIFS file-system description object
  1133. * @inum: inode number
  1134. * @i_size: size on inode
  1135. * @d_size: maximum size based on data nodes
  1136. * @exists: indicates whether the inode exists
  1137. */
  1138. static int add_ino(struct ubifs_info *c, ino_t inum, loff_t i_size,
  1139. loff_t d_size, int exists)
  1140. {
  1141. struct rb_node **p = &c->size_tree.rb_node, *parent = NULL;
  1142. struct size_entry *e;
  1143. while (*p) {
  1144. parent = *p;
  1145. e = rb_entry(parent, struct size_entry, rb);
  1146. if (inum < e->inum)
  1147. p = &(*p)->rb_left;
  1148. else
  1149. p = &(*p)->rb_right;
  1150. }
  1151. e = kzalloc(sizeof(struct size_entry), GFP_KERNEL);
  1152. if (!e)
  1153. return -ENOMEM;
  1154. e->inum = inum;
  1155. e->i_size = i_size;
  1156. e->d_size = d_size;
  1157. e->exists = exists;
  1158. rb_link_node(&e->rb, parent, p);
  1159. rb_insert_color(&e->rb, &c->size_tree);
  1160. return 0;
  1161. }
  1162. /**
  1163. * find_ino - find an entry on the size tree.
  1164. * @c: UBIFS file-system description object
  1165. * @inum: inode number
  1166. */
  1167. static struct size_entry *find_ino(struct ubifs_info *c, ino_t inum)
  1168. {
  1169. struct rb_node *p = c->size_tree.rb_node;
  1170. struct size_entry *e;
  1171. while (p) {
  1172. e = rb_entry(p, struct size_entry, rb);
  1173. if (inum < e->inum)
  1174. p = p->rb_left;
  1175. else if (inum > e->inum)
  1176. p = p->rb_right;
  1177. else
  1178. return e;
  1179. }
  1180. return NULL;
  1181. }
  1182. /**
  1183. * remove_ino - remove an entry from the size tree.
  1184. * @c: UBIFS file-system description object
  1185. * @inum: inode number
  1186. */
  1187. static void remove_ino(struct ubifs_info *c, ino_t inum)
  1188. {
  1189. struct size_entry *e = find_ino(c, inum);
  1190. if (!e)
  1191. return;
  1192. rb_erase(&e->rb, &c->size_tree);
  1193. kfree(e);
  1194. }
  1195. /**
  1196. * ubifs_destroy_size_tree - free resources related to the size tree.
  1197. * @c: UBIFS file-system description object
  1198. */
  1199. void ubifs_destroy_size_tree(struct ubifs_info *c)
  1200. {
  1201. struct size_entry *e, *n;
  1202. rbtree_postorder_for_each_entry_safe(e, n, &c->size_tree, rb) {
  1203. if (e->inode)
  1204. iput(e->inode);
  1205. kfree(e);
  1206. }
  1207. c->size_tree = RB_ROOT;
  1208. }
  1209. /**
  1210. * ubifs_recover_size_accum - accumulate inode sizes for recovery.
  1211. * @c: UBIFS file-system description object
  1212. * @key: node key
  1213. * @deletion: node is for a deletion
  1214. * @new_size: inode size
  1215. *
  1216. * This function has two purposes:
  1217. * 1) to ensure there are no data nodes that fall outside the inode size
  1218. * 2) to ensure there are no data nodes for inodes that do not exist
  1219. * To accomplish those purposes, a rb-tree is constructed containing an entry
  1220. * for each inode number in the journal that has not been deleted, and recording
  1221. * the size from the inode node, the maximum size of any data node (also altered
  1222. * by truncations) and a flag indicating a inode number for which no inode node
  1223. * was present in the journal.
  1224. *
  1225. * Note that there is still the possibility that there are data nodes that have
  1226. * been committed that are beyond the inode size, however the only way to find
  1227. * them would be to scan the entire index. Alternatively, some provision could
  1228. * be made to record the size of inodes at the start of commit, which would seem
  1229. * very cumbersome for a scenario that is quite unlikely and the only negative
  1230. * consequence of which is wasted space.
  1231. *
  1232. * This functions returns %0 on success and a negative error code on failure.
  1233. */
  1234. int ubifs_recover_size_accum(struct ubifs_info *c, union ubifs_key *key,
  1235. int deletion, loff_t new_size)
  1236. {
  1237. ino_t inum = key_inum(c, key);
  1238. struct size_entry *e;
  1239. int err;
  1240. switch (key_type(c, key)) {
  1241. case UBIFS_INO_KEY:
  1242. if (deletion)
  1243. remove_ino(c, inum);
  1244. else {
  1245. e = find_ino(c, inum);
  1246. if (e) {
  1247. e->i_size = new_size;
  1248. e->exists = 1;
  1249. } else {
  1250. err = add_ino(c, inum, new_size, 0, 1);
  1251. if (err)
  1252. return err;
  1253. }
  1254. }
  1255. break;
  1256. case UBIFS_DATA_KEY:
  1257. e = find_ino(c, inum);
  1258. if (e) {
  1259. if (new_size > e->d_size)
  1260. e->d_size = new_size;
  1261. } else {
  1262. err = add_ino(c, inum, 0, new_size, 0);
  1263. if (err)
  1264. return err;
  1265. }
  1266. break;
  1267. case UBIFS_TRUN_KEY:
  1268. e = find_ino(c, inum);
  1269. if (e)
  1270. e->d_size = new_size;
  1271. break;
  1272. }
  1273. return 0;
  1274. }
  1275. #ifndef __UBOOT__
  1276. /**
  1277. * fix_size_in_place - fix inode size in place on flash.
  1278. * @c: UBIFS file-system description object
  1279. * @e: inode size information for recovery
  1280. */
  1281. static int fix_size_in_place(struct ubifs_info *c, struct size_entry *e)
  1282. {
  1283. struct ubifs_ino_node *ino = c->sbuf;
  1284. unsigned char *p;
  1285. union ubifs_key key;
  1286. int err, lnum, offs, len;
  1287. loff_t i_size;
  1288. uint32_t crc;
  1289. /* Locate the inode node LEB number and offset */
  1290. ino_key_init(c, &key, e->inum);
  1291. err = ubifs_tnc_locate(c, &key, ino, &lnum, &offs);
  1292. if (err)
  1293. goto out;
  1294. /*
  1295. * If the size recorded on the inode node is greater than the size that
  1296. * was calculated from nodes in the journal then don't change the inode.
  1297. */
  1298. i_size = le64_to_cpu(ino->size);
  1299. if (i_size >= e->d_size)
  1300. return 0;
  1301. /* Read the LEB */
  1302. err = ubifs_leb_read(c, lnum, c->sbuf, 0, c->leb_size, 1);
  1303. if (err)
  1304. goto out;
  1305. /* Change the size field and recalculate the CRC */
  1306. ino = c->sbuf + offs;
  1307. ino->size = cpu_to_le64(e->d_size);
  1308. len = le32_to_cpu(ino->ch.len);
  1309. crc = crc32(UBIFS_CRC32_INIT, (void *)ino + 8, len - 8);
  1310. ino->ch.crc = cpu_to_le32(crc);
  1311. /* Work out where data in the LEB ends and free space begins */
  1312. p = c->sbuf;
  1313. len = c->leb_size - 1;
  1314. while (p[len] == 0xff)
  1315. len -= 1;
  1316. len = ALIGN(len + 1, c->min_io_size);
  1317. /* Atomically write the fixed LEB back again */
  1318. err = ubifs_leb_change(c, lnum, c->sbuf, len);
  1319. if (err)
  1320. goto out;
  1321. dbg_rcvry("inode %lu at %d:%d size %lld -> %lld",
  1322. (unsigned long)e->inum, lnum, offs, i_size, e->d_size);
  1323. return 0;
  1324. out:
  1325. ubifs_warn(c, "inode %lu failed to fix size %lld -> %lld error %d",
  1326. (unsigned long)e->inum, e->i_size, e->d_size, err);
  1327. return err;
  1328. }
  1329. #endif
  1330. /**
  1331. * ubifs_recover_size - recover inode size.
  1332. * @c: UBIFS file-system description object
  1333. *
  1334. * This function attempts to fix inode size discrepancies identified by the
  1335. * 'ubifs_recover_size_accum()' function.
  1336. *
  1337. * This functions returns %0 on success and a negative error code on failure.
  1338. */
  1339. int ubifs_recover_size(struct ubifs_info *c)
  1340. {
  1341. struct rb_node *this = rb_first(&c->size_tree);
  1342. while (this) {
  1343. struct size_entry *e;
  1344. int err;
  1345. e = rb_entry(this, struct size_entry, rb);
  1346. if (!e->exists) {
  1347. union ubifs_key key;
  1348. ino_key_init(c, &key, e->inum);
  1349. err = ubifs_tnc_lookup(c, &key, c->sbuf);
  1350. if (err && err != -ENOENT)
  1351. return err;
  1352. if (err == -ENOENT) {
  1353. /* Remove data nodes that have no inode */
  1354. dbg_rcvry("removing ino %lu",
  1355. (unsigned long)e->inum);
  1356. err = ubifs_tnc_remove_ino(c, e->inum);
  1357. if (err)
  1358. return err;
  1359. } else {
  1360. struct ubifs_ino_node *ino = c->sbuf;
  1361. e->exists = 1;
  1362. e->i_size = le64_to_cpu(ino->size);
  1363. }
  1364. }
  1365. if (e->exists && e->i_size < e->d_size) {
  1366. if (c->ro_mount) {
  1367. /* Fix the inode size and pin it in memory */
  1368. struct inode *inode;
  1369. struct ubifs_inode *ui;
  1370. ubifs_assert(!e->inode);
  1371. inode = ubifs_iget(c->vfs_sb, e->inum);
  1372. if (IS_ERR(inode))
  1373. return PTR_ERR(inode);
  1374. ui = ubifs_inode(inode);
  1375. if (inode->i_size < e->d_size) {
  1376. dbg_rcvry("ino %lu size %lld -> %lld",
  1377. (unsigned long)e->inum,
  1378. inode->i_size, e->d_size);
  1379. inode->i_size = e->d_size;
  1380. ui->ui_size = e->d_size;
  1381. ui->synced_i_size = e->d_size;
  1382. e->inode = inode;
  1383. this = rb_next(this);
  1384. continue;
  1385. }
  1386. iput(inode);
  1387. #ifndef __UBOOT__
  1388. } else {
  1389. /* Fix the size in place */
  1390. err = fix_size_in_place(c, e);
  1391. if (err)
  1392. return err;
  1393. if (e->inode)
  1394. iput(e->inode);
  1395. #endif
  1396. }
  1397. }
  1398. this = rb_next(this);
  1399. rb_erase(&e->rb, &c->size_tree);
  1400. kfree(e);
  1401. }
  1402. return 0;
  1403. }