1 /* 2 * YAFFS: Yet Another Flash File System. A NAND-flash specific file system. 3 * 4 * Copyright (C) 2002-2011 Aleph One Ltd. 5 * for Toby Churchill Ltd and Brightstar Engineering 6 * 7 * Created by Charles Manning <charles@aleph1.co.uk> 8 * 9 * This program is free software; you can redistribute it and/or modify 10 * it under the terms of the GNU General Public License version 2 as 11 * published by the Free Software Foundation. 12 */ 13 14 #include "yaffs_verify.h" 15 #include "yaffs_trace.h" 16 #include "yaffs_bitmap.h" 17 #include "yaffs_getblockinfo.h" 18 #include "yaffs_nand.h" 19 20 int yaffs_skip_verification(struct yaffs_dev *dev) 21 { 22 dev = dev; 23 return !(yaffs_trace_mask & 24 (YAFFS_TRACE_VERIFY | YAFFS_TRACE_VERIFY_FULL)); 25 } 26 27 static int yaffs_skip_full_verification(struct yaffs_dev *dev) 28 { 29 dev = dev; 30 return !(yaffs_trace_mask & (YAFFS_TRACE_VERIFY_FULL)); 31 } 32 33 static int yaffs_skip_nand_verification(struct yaffs_dev *dev) 34 { 35 dev = dev; 36 return !(yaffs_trace_mask & (YAFFS_TRACE_VERIFY_NAND)); 37 } 38 39 static const char * const block_state_name[] = { 40 "Unknown", 41 "Needs scan", 42 "Scanning", 43 "Empty", 44 "Allocating", 45 "Full", 46 "Dirty", 47 "Checkpoint", 48 "Collecting", 49 "Dead" 50 }; 51 52 void yaffs_verify_blk(struct yaffs_dev *dev, struct yaffs_block_info *bi, int n) 53 { 54 int actually_used; 55 int in_use; 56 57 if (yaffs_skip_verification(dev)) 58 return; 59 60 /* Report illegal runtime states */ 61 if (bi->block_state >= YAFFS_NUMBER_OF_BLOCK_STATES) 62 yaffs_trace(YAFFS_TRACE_VERIFY, 63 "Block %d has undefined state %d", 64 n, bi->block_state); 65 66 switch (bi->block_state) { 67 case YAFFS_BLOCK_STATE_UNKNOWN: 68 case YAFFS_BLOCK_STATE_SCANNING: 69 case YAFFS_BLOCK_STATE_NEEDS_SCAN: 70 yaffs_trace(YAFFS_TRACE_VERIFY, 71 "Block %d has bad run-state %s", 72 n, block_state_name[bi->block_state]); 73 } 74 75 /* Check pages in use and soft deletions are legal */ 76 77 actually_used = bi->pages_in_use - bi->soft_del_pages; 78 79 if (bi->pages_in_use < 0 || 80 bi->pages_in_use > dev->param.chunks_per_block || 81 bi->soft_del_pages < 0 || 82 bi->soft_del_pages > dev->param.chunks_per_block || 83 actually_used < 0 || actually_used > dev->param.chunks_per_block) 84 yaffs_trace(YAFFS_TRACE_VERIFY, 85 "Block %d has illegal values pages_in_used %d soft_del_pages %d", 86 n, bi->pages_in_use, bi->soft_del_pages); 87 88 /* Check chunk bitmap legal */ 89 in_use = yaffs_count_chunk_bits(dev, n); 90 if (in_use != bi->pages_in_use) 91 yaffs_trace(YAFFS_TRACE_VERIFY, 92 "Block %d has inconsistent values pages_in_use %d counted chunk bits %d", 93 n, bi->pages_in_use, in_use); 94 } 95 96 void yaffs_verify_collected_blk(struct yaffs_dev *dev, 97 struct yaffs_block_info *bi, int n) 98 { 99 yaffs_verify_blk(dev, bi, n); 100 101 /* After collection the block should be in the erased state */ 102 103 if (bi->block_state != YAFFS_BLOCK_STATE_COLLECTING && 104 bi->block_state != YAFFS_BLOCK_STATE_EMPTY) { 105 yaffs_trace(YAFFS_TRACE_ERROR, 106 "Block %d is in state %d after gc, should be erased", 107 n, bi->block_state); 108 } 109 } 110 111 void yaffs_verify_blocks(struct yaffs_dev *dev) 112 { 113 int i; 114 int state_count[YAFFS_NUMBER_OF_BLOCK_STATES]; 115 int illegal_states = 0; 116 117 if (yaffs_skip_verification(dev)) 118 return; 119 120 memset(state_count, 0, sizeof(state_count)); 121 122 for (i = dev->internal_start_block; i <= dev->internal_end_block; i++) { 123 struct yaffs_block_info *bi = yaffs_get_block_info(dev, i); 124 yaffs_verify_blk(dev, bi, i); 125 126 if (bi->block_state < YAFFS_NUMBER_OF_BLOCK_STATES) 127 state_count[bi->block_state]++; 128 else 129 illegal_states++; 130 } 131 132 yaffs_trace(YAFFS_TRACE_VERIFY, "Block summary"); 133 134 yaffs_trace(YAFFS_TRACE_VERIFY, 135 "%d blocks have illegal states", 136 illegal_states); 137 if (state_count[YAFFS_BLOCK_STATE_ALLOCATING] > 1) 138 yaffs_trace(YAFFS_TRACE_VERIFY, 139 "Too many allocating blocks"); 140 141 for (i = 0; i < YAFFS_NUMBER_OF_BLOCK_STATES; i++) 142 yaffs_trace(YAFFS_TRACE_VERIFY, 143 "%s %d blocks", 144 block_state_name[i], state_count[i]); 145 146 if (dev->blocks_in_checkpt != state_count[YAFFS_BLOCK_STATE_CHECKPOINT]) 147 yaffs_trace(YAFFS_TRACE_VERIFY, 148 "Checkpoint block count wrong dev %d count %d", 149 dev->blocks_in_checkpt, 150 state_count[YAFFS_BLOCK_STATE_CHECKPOINT]); 151 152 if (dev->n_erased_blocks != state_count[YAFFS_BLOCK_STATE_EMPTY]) 153 yaffs_trace(YAFFS_TRACE_VERIFY, 154 "Erased block count wrong dev %d count %d", 155 dev->n_erased_blocks, 156 state_count[YAFFS_BLOCK_STATE_EMPTY]); 157 158 if (state_count[YAFFS_BLOCK_STATE_COLLECTING] > 1) 159 yaffs_trace(YAFFS_TRACE_VERIFY, 160 "Too many collecting blocks %d (max is 1)", 161 state_count[YAFFS_BLOCK_STATE_COLLECTING]); 162 } 163 164 /* 165 * Verify the object header. oh must be valid, but obj and tags may be NULL in 166 * which case those tests will not be performed. 167 */ 168 void yaffs_verify_oh(struct yaffs_obj *obj, struct yaffs_obj_hdr *oh, 169 struct yaffs_ext_tags *tags, int parent_check) 170 { 171 if (obj && yaffs_skip_verification(obj->my_dev)) 172 return; 173 174 if (!(tags && obj && oh)) { 175 yaffs_trace(YAFFS_TRACE_VERIFY, 176 "Verifying object header tags %p obj %p oh %p", 177 tags, obj, oh); 178 return; 179 } 180 181 if (oh->type <= YAFFS_OBJECT_TYPE_UNKNOWN || 182 oh->type > YAFFS_OBJECT_TYPE_MAX) 183 yaffs_trace(YAFFS_TRACE_VERIFY, 184 "Obj %d header type is illegal value 0x%x", 185 tags->obj_id, oh->type); 186 187 if (tags->obj_id != obj->obj_id) 188 yaffs_trace(YAFFS_TRACE_VERIFY, 189 "Obj %d header mismatch obj_id %d", 190 tags->obj_id, obj->obj_id); 191 192 /* 193 * Check that the object's parent ids match if parent_check requested. 194 * 195 * Tests do not apply to the root object. 196 */ 197 198 if (parent_check && tags->obj_id > 1 && !obj->parent) 199 yaffs_trace(YAFFS_TRACE_VERIFY, 200 "Obj %d header mismatch parent_id %d obj->parent is NULL", 201 tags->obj_id, oh->parent_obj_id); 202 203 if (parent_check && obj->parent && 204 oh->parent_obj_id != obj->parent->obj_id && 205 (oh->parent_obj_id != YAFFS_OBJECTID_UNLINKED || 206 obj->parent->obj_id != YAFFS_OBJECTID_DELETED)) 207 yaffs_trace(YAFFS_TRACE_VERIFY, 208 "Obj %d header mismatch parent_id %d parent_obj_id %d", 209 tags->obj_id, oh->parent_obj_id, 210 obj->parent->obj_id); 211 212 if (tags->obj_id > 1 && oh->name[0] == 0) /* Null name */ 213 yaffs_trace(YAFFS_TRACE_VERIFY, 214 "Obj %d header name is NULL", 215 obj->obj_id); 216 217 if (tags->obj_id > 1 && ((u8) (oh->name[0])) == 0xff) /* Junk name */ 218 yaffs_trace(YAFFS_TRACE_VERIFY, 219 "Obj %d header name is 0xff", 220 obj->obj_id); 221 } 222 223 void yaffs_verify_file(struct yaffs_obj *obj) 224 { 225 u32 x; 226 int required_depth; 227 int last_chunk; 228 u32 offset_in_chunk; 229 u32 the_chunk; 230 231 u32 i; 232 struct yaffs_dev *dev; 233 struct yaffs_ext_tags tags; 234 struct yaffs_tnode *tn; 235 u32 obj_id; 236 237 if (!obj) 238 return; 239 240 if (yaffs_skip_verification(obj->my_dev)) 241 return; 242 243 dev = obj->my_dev; 244 obj_id = obj->obj_id; 245 246 247 /* Check file size is consistent with tnode depth */ 248 yaffs_addr_to_chunk(dev, obj->variant.file_variant.file_size, 249 &last_chunk, &offset_in_chunk); 250 last_chunk++; 251 x = last_chunk >> YAFFS_TNODES_LEVEL0_BITS; 252 required_depth = 0; 253 while (x > 0) { 254 x >>= YAFFS_TNODES_INTERNAL_BITS; 255 required_depth++; 256 } 257 258 /* Check that the chunks in the tnode tree are all correct. 259 * We do this by scanning through the tnode tree and 260 * checking the tags for every chunk match. 261 */ 262 263 if (yaffs_skip_nand_verification(dev)) 264 return; 265 266 for (i = 1; i <= last_chunk; i++) { 267 tn = yaffs_find_tnode_0(dev, &obj->variant.file_variant, i); 268 269 if (!tn) 270 continue; 271 272 the_chunk = yaffs_get_group_base(dev, tn, i); 273 if (the_chunk > 0) { 274 yaffs_rd_chunk_tags_nand(dev, the_chunk, NULL, 275 &tags); 276 if (tags.obj_id != obj_id || tags.chunk_id != i) 277 yaffs_trace(YAFFS_TRACE_VERIFY, 278 "Object %d chunk_id %d NAND mismatch chunk %d tags (%d:%d)", 279 obj_id, i, the_chunk, 280 tags.obj_id, tags.chunk_id); 281 } 282 } 283 } 284 285 void yaffs_verify_link(struct yaffs_obj *obj) 286 { 287 if (obj && yaffs_skip_verification(obj->my_dev)) 288 return; 289 290 /* Verify sane equivalent object */ 291 } 292 293 void yaffs_verify_symlink(struct yaffs_obj *obj) 294 { 295 if (obj && yaffs_skip_verification(obj->my_dev)) 296 return; 297 298 /* Verify symlink string */ 299 } 300 301 void yaffs_verify_special(struct yaffs_obj *obj) 302 { 303 if (obj && yaffs_skip_verification(obj->my_dev)) 304 return; 305 } 306 307 void yaffs_verify_obj(struct yaffs_obj *obj) 308 { 309 struct yaffs_dev *dev; 310 u32 chunk_min; 311 u32 chunk_max; 312 u32 chunk_id_ok; 313 u32 chunk_in_range; 314 u32 chunk_wrongly_deleted; 315 u32 chunk_valid; 316 317 if (!obj) 318 return; 319 320 if (obj->being_created) 321 return; 322 323 dev = obj->my_dev; 324 325 if (yaffs_skip_verification(dev)) 326 return; 327 328 /* Check sane object header chunk */ 329 330 chunk_min = dev->internal_start_block * dev->param.chunks_per_block; 331 chunk_max = 332 (dev->internal_end_block + 1) * dev->param.chunks_per_block - 1; 333 334 chunk_in_range = (((unsigned)(obj->hdr_chunk)) >= chunk_min && 335 ((unsigned)(obj->hdr_chunk)) <= chunk_max); 336 chunk_id_ok = chunk_in_range || (obj->hdr_chunk == 0); 337 chunk_valid = chunk_in_range && 338 yaffs_check_chunk_bit(dev, 339 obj->hdr_chunk / dev->param.chunks_per_block, 340 obj->hdr_chunk % dev->param.chunks_per_block); 341 chunk_wrongly_deleted = chunk_in_range && !chunk_valid; 342 343 if (!obj->fake && (!chunk_id_ok || chunk_wrongly_deleted)) 344 yaffs_trace(YAFFS_TRACE_VERIFY, 345 "Obj %d has chunk_id %d %s %s", 346 obj->obj_id, obj->hdr_chunk, 347 chunk_id_ok ? "" : ",out of range", 348 chunk_wrongly_deleted ? ",marked as deleted" : ""); 349 350 if (chunk_valid && !yaffs_skip_nand_verification(dev)) { 351 struct yaffs_ext_tags tags; 352 struct yaffs_obj_hdr *oh; 353 u8 *buffer = yaffs_get_temp_buffer(dev); 354 355 oh = (struct yaffs_obj_hdr *)buffer; 356 357 yaffs_rd_chunk_tags_nand(dev, obj->hdr_chunk, buffer, &tags); 358 359 yaffs_verify_oh(obj, oh, &tags, 1); 360 361 yaffs_release_temp_buffer(dev, buffer); 362 } 363 364 /* Verify it has a parent */ 365 if (obj && !obj->fake && (!obj->parent || obj->parent->my_dev != dev)) { 366 yaffs_trace(YAFFS_TRACE_VERIFY, 367 "Obj %d has parent pointer %p which does not look like an object", 368 obj->obj_id, obj->parent); 369 } 370 371 /* Verify parent is a directory */ 372 if (obj->parent && 373 obj->parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) { 374 yaffs_trace(YAFFS_TRACE_VERIFY, 375 "Obj %d's parent is not a directory (type %d)", 376 obj->obj_id, obj->parent->variant_type); 377 } 378 379 switch (obj->variant_type) { 380 case YAFFS_OBJECT_TYPE_FILE: 381 yaffs_verify_file(obj); 382 break; 383 case YAFFS_OBJECT_TYPE_SYMLINK: 384 yaffs_verify_symlink(obj); 385 break; 386 case YAFFS_OBJECT_TYPE_DIRECTORY: 387 yaffs_verify_dir(obj); 388 break; 389 case YAFFS_OBJECT_TYPE_HARDLINK: 390 yaffs_verify_link(obj); 391 break; 392 case YAFFS_OBJECT_TYPE_SPECIAL: 393 yaffs_verify_special(obj); 394 break; 395 case YAFFS_OBJECT_TYPE_UNKNOWN: 396 default: 397 yaffs_trace(YAFFS_TRACE_VERIFY, 398 "Obj %d has illegaltype %d", 399 obj->obj_id, obj->variant_type); 400 break; 401 } 402 } 403 404 void yaffs_verify_objects(struct yaffs_dev *dev) 405 { 406 struct yaffs_obj *obj; 407 int i; 408 struct list_head *lh; 409 410 if (yaffs_skip_verification(dev)) 411 return; 412 413 /* Iterate through the objects in each hash entry */ 414 415 for (i = 0; i < YAFFS_NOBJECT_BUCKETS; i++) { 416 list_for_each(lh, &dev->obj_bucket[i].list) { 417 obj = list_entry(lh, struct yaffs_obj, hash_link); 418 yaffs_verify_obj(obj); 419 } 420 } 421 } 422 423 void yaffs_verify_obj_in_dir(struct yaffs_obj *obj) 424 { 425 struct list_head *lh; 426 struct yaffs_obj *list_obj; 427 int count = 0; 428 429 if (!obj) { 430 yaffs_trace(YAFFS_TRACE_ALWAYS, "No object to verify"); 431 BUG(); 432 return; 433 } 434 435 if (yaffs_skip_verification(obj->my_dev)) 436 return; 437 438 if (!obj->parent) { 439 yaffs_trace(YAFFS_TRACE_ALWAYS, "Object does not have parent"); 440 BUG(); 441 return; 442 } 443 444 if (obj->parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) { 445 yaffs_trace(YAFFS_TRACE_ALWAYS, "Parent is not directory"); 446 BUG(); 447 } 448 449 /* Iterate through the objects in each hash entry */ 450 451 list_for_each(lh, &obj->parent->variant.dir_variant.children) { 452 list_obj = list_entry(lh, struct yaffs_obj, siblings); 453 yaffs_verify_obj(list_obj); 454 if (obj == list_obj) 455 count++; 456 } 457 458 if (count != 1) { 459 yaffs_trace(YAFFS_TRACE_ALWAYS, 460 "Object in directory %d times", 461 count); 462 BUG(); 463 } 464 } 465 466 void yaffs_verify_dir(struct yaffs_obj *directory) 467 { 468 struct list_head *lh; 469 struct yaffs_obj *list_obj; 470 471 if (!directory) { 472 BUG(); 473 return; 474 } 475 476 if (yaffs_skip_full_verification(directory->my_dev)) 477 return; 478 479 if (directory->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) { 480 yaffs_trace(YAFFS_TRACE_ALWAYS, 481 "Directory has wrong type: %d", 482 directory->variant_type); 483 BUG(); 484 } 485 486 /* Iterate through the objects in each hash entry */ 487 488 list_for_each(lh, &directory->variant.dir_variant.children) { 489 list_obj = list_entry(lh, struct yaffs_obj, siblings); 490 if (list_obj->parent != directory) { 491 yaffs_trace(YAFFS_TRACE_ALWAYS, 492 "Object in directory list has wrong parent %p", 493 list_obj->parent); 494 BUG(); 495 } 496 yaffs_verify_obj_in_dir(list_obj); 497 } 498 } 499 500 static int yaffs_free_verification_failures; 501 502 void yaffs_verify_free_chunks(struct yaffs_dev *dev) 503 { 504 int counted; 505 int difference; 506 507 if (yaffs_skip_verification(dev)) 508 return; 509 510 counted = yaffs_count_free_chunks(dev); 511 512 difference = dev->n_free_chunks - counted; 513 514 if (difference) { 515 yaffs_trace(YAFFS_TRACE_ALWAYS, 516 "Freechunks verification failure %d %d %d", 517 dev->n_free_chunks, counted, difference); 518 yaffs_free_verification_failures++; 519 } 520 } 521 522 int yaffs_verify_file_sane(struct yaffs_obj *in) 523 { 524 in = in; 525 return YAFFS_OK; 526 } 527