scan.c 9.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373
  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 the scan which is a general-purpose function for
  12. * determining what nodes are in an eraseblock. The scan is used to replay the
  13. * journal, to do garbage collection. for the TNC in-the-gaps method, and by
  14. * debugging functions.
  15. */
  16. #ifdef __UBOOT__
  17. #include <hexdump.h>
  18. #include <log.h>
  19. #include <dm/devres.h>
  20. #include <linux/err.h>
  21. #endif
  22. #include "ubifs.h"
  23. /**
  24. * scan_padding_bytes - scan for padding bytes.
  25. * @buf: buffer to scan
  26. * @len: length of buffer
  27. *
  28. * This function returns the number of padding bytes on success and
  29. * %SCANNED_GARBAGE on failure.
  30. */
  31. static int scan_padding_bytes(void *buf, int len)
  32. {
  33. int pad_len = 0, max_pad_len = min_t(int, UBIFS_PAD_NODE_SZ, len);
  34. uint8_t *p = buf;
  35. dbg_scan("not a node");
  36. while (pad_len < max_pad_len && *p++ == UBIFS_PADDING_BYTE)
  37. pad_len += 1;
  38. if (!pad_len || (pad_len & 7))
  39. return SCANNED_GARBAGE;
  40. dbg_scan("%d padding bytes", pad_len);
  41. return pad_len;
  42. }
  43. /**
  44. * ubifs_scan_a_node - scan for a node or padding.
  45. * @c: UBIFS file-system description object
  46. * @buf: buffer to scan
  47. * @len: length of buffer
  48. * @lnum: logical eraseblock number
  49. * @offs: offset within the logical eraseblock
  50. * @quiet: print no messages
  51. *
  52. * This function returns a scanning code to indicate what was scanned.
  53. */
  54. int ubifs_scan_a_node(const struct ubifs_info *c, void *buf, int len, int lnum,
  55. int offs, int quiet)
  56. {
  57. struct ubifs_ch *ch = buf;
  58. uint32_t magic;
  59. magic = le32_to_cpu(ch->magic);
  60. if (magic == 0xFFFFFFFF) {
  61. dbg_scan("hit empty space at LEB %d:%d", lnum, offs);
  62. return SCANNED_EMPTY_SPACE;
  63. }
  64. if (magic != UBIFS_NODE_MAGIC)
  65. return scan_padding_bytes(buf, len);
  66. if (len < UBIFS_CH_SZ)
  67. return SCANNED_GARBAGE;
  68. dbg_scan("scanning %s at LEB %d:%d",
  69. dbg_ntype(ch->node_type), lnum, offs);
  70. if (ubifs_check_node(c, buf, lnum, offs, quiet, 1))
  71. return SCANNED_A_CORRUPT_NODE;
  72. if (ch->node_type == UBIFS_PAD_NODE) {
  73. struct ubifs_pad_node *pad = buf;
  74. int pad_len = le32_to_cpu(pad->pad_len);
  75. int node_len = le32_to_cpu(ch->len);
  76. /* Validate the padding node */
  77. if (pad_len < 0 ||
  78. offs + node_len + pad_len > c->leb_size) {
  79. if (!quiet) {
  80. ubifs_err(c, "bad pad node at LEB %d:%d",
  81. lnum, offs);
  82. ubifs_dump_node(c, pad);
  83. }
  84. return SCANNED_A_BAD_PAD_NODE;
  85. }
  86. /* Make the node pads to 8-byte boundary */
  87. if ((node_len + pad_len) & 7) {
  88. if (!quiet)
  89. ubifs_err(c, "bad padding length %d - %d",
  90. offs, offs + node_len + pad_len);
  91. return SCANNED_A_BAD_PAD_NODE;
  92. }
  93. dbg_scan("%d bytes padded at LEB %d:%d, offset now %d", pad_len,
  94. lnum, offs, ALIGN(offs + node_len + pad_len, 8));
  95. return node_len + pad_len;
  96. }
  97. return SCANNED_A_NODE;
  98. }
  99. /**
  100. * ubifs_start_scan - create LEB scanning information at start of scan.
  101. * @c: UBIFS file-system description object
  102. * @lnum: logical eraseblock number
  103. * @offs: offset to start at (usually zero)
  104. * @sbuf: scan buffer (must be c->leb_size)
  105. *
  106. * This function returns the scanned information on success and a negative error
  107. * code on failure.
  108. */
  109. struct ubifs_scan_leb *ubifs_start_scan(const struct ubifs_info *c, int lnum,
  110. int offs, void *sbuf)
  111. {
  112. struct ubifs_scan_leb *sleb;
  113. int err;
  114. dbg_scan("scan LEB %d:%d", lnum, offs);
  115. sleb = kzalloc(sizeof(struct ubifs_scan_leb), GFP_NOFS);
  116. if (!sleb)
  117. return ERR_PTR(-ENOMEM);
  118. sleb->lnum = lnum;
  119. INIT_LIST_HEAD(&sleb->nodes);
  120. sleb->buf = sbuf;
  121. err = ubifs_leb_read(c, lnum, sbuf + offs, offs, c->leb_size - offs, 0);
  122. if (err && err != -EBADMSG) {
  123. ubifs_err(c, "cannot read %d bytes from LEB %d:%d, error %d",
  124. c->leb_size - offs, lnum, offs, err);
  125. kfree(sleb);
  126. return ERR_PTR(err);
  127. }
  128. /*
  129. * Note, we ignore integrity errors (EBASMSG) because all the nodes are
  130. * protected by CRC checksums.
  131. */
  132. return sleb;
  133. }
  134. /**
  135. * ubifs_end_scan - update LEB scanning information at end of scan.
  136. * @c: UBIFS file-system description object
  137. * @sleb: scanning information
  138. * @lnum: logical eraseblock number
  139. * @offs: offset to start at (usually zero)
  140. */
  141. void ubifs_end_scan(const struct ubifs_info *c, struct ubifs_scan_leb *sleb,
  142. int lnum, int offs)
  143. {
  144. lnum = lnum;
  145. dbg_scan("stop scanning LEB %d at offset %d", lnum, offs);
  146. ubifs_assert(offs % c->min_io_size == 0);
  147. sleb->endpt = ALIGN(offs, c->min_io_size);
  148. }
  149. /**
  150. * ubifs_add_snod - add a scanned node to LEB scanning information.
  151. * @c: UBIFS file-system description object
  152. * @sleb: scanning information
  153. * @buf: buffer containing node
  154. * @offs: offset of node on flash
  155. *
  156. * This function returns %0 on success and a negative error code on failure.
  157. */
  158. int ubifs_add_snod(const struct ubifs_info *c, struct ubifs_scan_leb *sleb,
  159. void *buf, int offs)
  160. {
  161. struct ubifs_ch *ch = buf;
  162. struct ubifs_ino_node *ino = buf;
  163. struct ubifs_scan_node *snod;
  164. snod = kmalloc(sizeof(struct ubifs_scan_node), GFP_NOFS);
  165. if (!snod)
  166. return -ENOMEM;
  167. snod->sqnum = le64_to_cpu(ch->sqnum);
  168. snod->type = ch->node_type;
  169. snod->offs = offs;
  170. snod->len = le32_to_cpu(ch->len);
  171. snod->node = buf;
  172. switch (ch->node_type) {
  173. case UBIFS_INO_NODE:
  174. case UBIFS_DENT_NODE:
  175. case UBIFS_XENT_NODE:
  176. case UBIFS_DATA_NODE:
  177. /*
  178. * The key is in the same place in all keyed
  179. * nodes.
  180. */
  181. key_read(c, &ino->key, &snod->key);
  182. break;
  183. default:
  184. invalid_key_init(c, &snod->key);
  185. break;
  186. }
  187. list_add_tail(&snod->list, &sleb->nodes);
  188. sleb->nodes_cnt += 1;
  189. return 0;
  190. }
  191. /**
  192. * ubifs_scanned_corruption - print information after UBIFS scanned corruption.
  193. * @c: UBIFS file-system description object
  194. * @lnum: LEB number of corruption
  195. * @offs: offset of corruption
  196. * @buf: buffer containing corruption
  197. */
  198. void ubifs_scanned_corruption(const struct ubifs_info *c, int lnum, int offs,
  199. void *buf)
  200. {
  201. int len;
  202. ubifs_err(c, "corruption at LEB %d:%d", lnum, offs);
  203. len = c->leb_size - offs;
  204. if (len > 8192)
  205. len = 8192;
  206. ubifs_err(c, "first %d bytes from LEB %d:%d", len, lnum, offs);
  207. print_hex_dump("", DUMP_PREFIX_OFFSET, 32, 4, buf, len, 1);
  208. }
  209. /**
  210. * ubifs_scan - scan a logical eraseblock.
  211. * @c: UBIFS file-system description object
  212. * @lnum: logical eraseblock number
  213. * @offs: offset to start at (usually zero)
  214. * @sbuf: scan buffer (must be of @c->leb_size bytes in size)
  215. * @quiet: print no messages
  216. *
  217. * This function scans LEB number @lnum and returns complete information about
  218. * its contents. Returns the scanned information in case of success and,
  219. * %-EUCLEAN if the LEB neads recovery, and other negative error codes in case
  220. * of failure.
  221. *
  222. * If @quiet is non-zero, this function does not print large and scary
  223. * error messages and flash dumps in case of errors.
  224. */
  225. struct ubifs_scan_leb *ubifs_scan(const struct ubifs_info *c, int lnum,
  226. int offs, void *sbuf, int quiet)
  227. {
  228. void *buf = sbuf + offs;
  229. int err, len = c->leb_size - offs;
  230. struct ubifs_scan_leb *sleb;
  231. sleb = ubifs_start_scan(c, lnum, offs, sbuf);
  232. if (IS_ERR(sleb))
  233. return sleb;
  234. while (len >= 8) {
  235. struct ubifs_ch *ch = buf;
  236. int node_len, ret;
  237. dbg_scan("look at LEB %d:%d (%d bytes left)",
  238. lnum, offs, len);
  239. cond_resched();
  240. ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet);
  241. if (ret > 0) {
  242. /* Padding bytes or a valid padding node */
  243. offs += ret;
  244. buf += ret;
  245. len -= ret;
  246. continue;
  247. }
  248. if (ret == SCANNED_EMPTY_SPACE)
  249. /* Empty space is checked later */
  250. break;
  251. switch (ret) {
  252. case SCANNED_GARBAGE:
  253. ubifs_err(c, "garbage");
  254. goto corrupted;
  255. case SCANNED_A_NODE:
  256. break;
  257. case SCANNED_A_CORRUPT_NODE:
  258. case SCANNED_A_BAD_PAD_NODE:
  259. ubifs_err(c, "bad node");
  260. goto corrupted;
  261. default:
  262. ubifs_err(c, "unknown");
  263. err = -EINVAL;
  264. goto error;
  265. }
  266. err = ubifs_add_snod(c, sleb, buf, offs);
  267. if (err)
  268. goto error;
  269. node_len = ALIGN(le32_to_cpu(ch->len), 8);
  270. offs += node_len;
  271. buf += node_len;
  272. len -= node_len;
  273. }
  274. if (offs % c->min_io_size) {
  275. if (!quiet)
  276. ubifs_err(c, "empty space starts at non-aligned offset %d",
  277. offs);
  278. goto corrupted;
  279. }
  280. ubifs_end_scan(c, sleb, lnum, offs);
  281. for (; len > 4; offs += 4, buf = buf + 4, len -= 4)
  282. if (*(uint32_t *)buf != 0xffffffff)
  283. break;
  284. for (; len; offs++, buf++, len--)
  285. if (*(uint8_t *)buf != 0xff) {
  286. if (!quiet)
  287. ubifs_err(c, "corrupt empty space at LEB %d:%d",
  288. lnum, offs);
  289. goto corrupted;
  290. }
  291. return sleb;
  292. corrupted:
  293. if (!quiet) {
  294. ubifs_scanned_corruption(c, lnum, offs, buf);
  295. ubifs_err(c, "LEB %d scanning failed", lnum);
  296. }
  297. err = -EUCLEAN;
  298. ubifs_scan_destroy(sleb);
  299. return ERR_PTR(err);
  300. error:
  301. ubifs_err(c, "LEB %d scanning failed, error %d", lnum, err);
  302. ubifs_scan_destroy(sleb);
  303. return ERR_PTR(err);
  304. }
  305. /**
  306. * ubifs_scan_destroy - destroy LEB scanning information.
  307. * @sleb: scanning information to free
  308. */
  309. void ubifs_scan_destroy(struct ubifs_scan_leb *sleb)
  310. {
  311. struct ubifs_scan_node *node;
  312. struct list_head *head;
  313. head = &sleb->nodes;
  314. while (!list_empty(head)) {
  315. node = list_entry(head->next, struct ubifs_scan_node, list);
  316. list_del(&node->list);
  317. kfree(node);
  318. }
  319. kfree(sleb);
  320. }