scan.c 9.5 KB

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