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