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