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