1/* 2 * YAFFS: Yet Another Flash File System. A NAND-flash specific file system. 3 * 4 * Copyright (C) 2002-2010 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 15#include "yaffs_verify.h" 16#include "yaffs_trace.h" 17#include "yaffs_bitmap.h" 18#include "yaffs_getblockinfo.h" 19#include "yaffs_nand.h" 20 21int yaffs_skip_verification(yaffs_dev_t *dev) 22{ 23 dev=dev; 24 return !(yaffs_trace_mask & (YAFFS_TRACE_VERIFY | YAFFS_TRACE_VERIFY_FULL)); 25} 26 27static int yaffs_skip_full_verification(yaffs_dev_t *dev) 28{ 29 dev=dev; 30 return !(yaffs_trace_mask & (YAFFS_TRACE_VERIFY_FULL)); 31} 32 33static int yaffs_skip_nand_verification(yaffs_dev_t *dev) 34{ 35 dev=dev; 36 return !(yaffs_trace_mask & (YAFFS_TRACE_VERIFY_NAND)); 37} 38 39 40static const char *block_stateName[] = { 41"Unknown", 42"Needs scanning", 43"Scanning", 44"Empty", 45"Allocating", 46"Full", 47"Dirty", 48"Checkpoint", 49"Collecting", 50"Dead" 51}; 52 53 54void yaffs_verify_blk(yaffs_dev_t *dev, yaffs_block_info_t *bi, int n) 55{ 56 int actuallyUsed; 57 int inUse; 58 59 if (yaffs_skip_verification(dev)) 60 return; 61 62 /* Report illegal runtime states */ 63 if (bi->block_state >= YAFFS_NUMBER_OF_BLOCK_STATES) 64 T(YAFFS_TRACE_VERIFY, (TSTR("Block %d has undefined state %d"TENDSTR), 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_SCANNING: 70 T(YAFFS_TRACE_VERIFY, (TSTR("Block %d has bad run-state %s"TENDSTR), 71 n, block_stateName[bi->block_state])); 72 } 73 74 /* Check pages in use and soft deletions are legal */ 75 76 actuallyUsed = bi->pages_in_use - bi->soft_del_pages; 77 78 if (bi->pages_in_use < 0 || bi->pages_in_use > dev->param.chunks_per_block || 79 bi->soft_del_pages < 0 || bi->soft_del_pages > dev->param.chunks_per_block || 80 actuallyUsed < 0 || actuallyUsed > dev->param.chunks_per_block) 81 T(YAFFS_TRACE_VERIFY, (TSTR("Block %d has illegal values pages_in_used %d soft_del_pages %d"TENDSTR), 82 n, bi->pages_in_use, bi->soft_del_pages)); 83 84 85 /* Check chunk bitmap legal */ 86 inUse = yaffs_count_chunk_bits(dev, n); 87 if (inUse != bi->pages_in_use) 88 T(YAFFS_TRACE_VERIFY, (TSTR("Block %d has inconsistent values pages_in_use %d counted chunk bits %d"TENDSTR), 89 n, bi->pages_in_use, inUse)); 90 91} 92 93 94 95void yaffs_verify_collected_blk(yaffs_dev_t *dev, yaffs_block_info_t *bi, int n) 96{ 97 yaffs_verify_blk(dev, bi, n); 98 99 /* After collection the block should be in the erased state */ 100 101 if (bi->block_state != YAFFS_BLOCK_STATE_COLLECTING && 102 bi->block_state != YAFFS_BLOCK_STATE_EMPTY) { 103 T(YAFFS_TRACE_ERROR, (TSTR("Block %d is in state %d after gc, should be erased"TENDSTR), 104 n, bi->block_state)); 105 } 106} 107 108void yaffs_verify_blocks(yaffs_dev_t *dev) 109{ 110 int i; 111 int nBlocksPerState[YAFFS_NUMBER_OF_BLOCK_STATES]; 112 int nIllegalBlockStates = 0; 113 114 if (yaffs_skip_verification(dev)) 115 return; 116 117 memset(nBlocksPerState, 0, sizeof(nBlocksPerState)); 118 119 for (i = dev->internal_start_block; i <= dev->internal_end_block; i++) { 120 yaffs_block_info_t *bi = yaffs_get_block_info(dev, i); 121 yaffs_verify_blk(dev, bi, i); 122 123 if (bi->block_state < YAFFS_NUMBER_OF_BLOCK_STATES) 124 nBlocksPerState[bi->block_state]++; 125 else 126 nIllegalBlockStates++; 127 } 128 129 T(YAFFS_TRACE_VERIFY, (TSTR(""TENDSTR))); 130 T(YAFFS_TRACE_VERIFY, (TSTR("Block summary"TENDSTR))); 131 132 T(YAFFS_TRACE_VERIFY, (TSTR("%d blocks have illegal states"TENDSTR), nIllegalBlockStates)); 133 if (nBlocksPerState[YAFFS_BLOCK_STATE_ALLOCATING] > 1) 134 T(YAFFS_TRACE_VERIFY, (TSTR("Too many allocating blocks"TENDSTR))); 135 136 for (i = 0; i < YAFFS_NUMBER_OF_BLOCK_STATES; i++) 137 T(YAFFS_TRACE_VERIFY, 138 (TSTR("%s %d blocks"TENDSTR), 139 block_stateName[i], nBlocksPerState[i])); 140 141 if (dev->blocks_in_checkpt != nBlocksPerState[YAFFS_BLOCK_STATE_CHECKPOINT]) 142 T(YAFFS_TRACE_VERIFY, 143 (TSTR("Checkpoint block count wrong dev %d count %d"TENDSTR), 144 dev->blocks_in_checkpt, nBlocksPerState[YAFFS_BLOCK_STATE_CHECKPOINT])); 145 146 if (dev->n_erased_blocks != nBlocksPerState[YAFFS_BLOCK_STATE_EMPTY]) 147 T(YAFFS_TRACE_VERIFY, 148 (TSTR("Erased block count wrong dev %d count %d"TENDSTR), 149 dev->n_erased_blocks, nBlocksPerState[YAFFS_BLOCK_STATE_EMPTY])); 150 151 if (nBlocksPerState[YAFFS_BLOCK_STATE_COLLECTING] > 1) 152 T(YAFFS_TRACE_VERIFY, 153 (TSTR("Too many collecting blocks %d (max is 1)"TENDSTR), 154 nBlocksPerState[YAFFS_BLOCK_STATE_COLLECTING])); 155 156 T(YAFFS_TRACE_VERIFY, (TSTR(""TENDSTR))); 157 158} 159 160/* 161 * Verify the object header. oh must be valid, but obj and tags may be NULL in which 162 * case those tests will not be performed. 163 */ 164void yaffs_verify_oh(yaffs_obj_t *obj, yaffs_obj_header *oh, yaffs_ext_tags *tags, int parentCheck) 165{ 166 if (obj && yaffs_skip_verification(obj->my_dev)) 167 return; 168 169 if (!(tags && obj && oh)) { 170 T(YAFFS_TRACE_VERIFY, 171 (TSTR("Verifying object header tags %p obj %p oh %p"TENDSTR), 172 tags, obj, oh)); 173 return; 174 } 175 176 if (oh->type <= YAFFS_OBJECT_TYPE_UNKNOWN || 177 oh->type > YAFFS_OBJECT_TYPE_MAX) 178 T(YAFFS_TRACE_VERIFY, 179 (TSTR("Obj %d header type is illegal value 0x%x"TENDSTR), 180 tags->obj_id, oh->type)); 181 182 if (tags->obj_id != obj->obj_id) 183 T(YAFFS_TRACE_VERIFY, 184 (TSTR("Obj %d header mismatch obj_id %d"TENDSTR), 185 tags->obj_id, obj->obj_id)); 186 187 188 /* 189 * Check that the object's parent ids match if parentCheck requested. 190 * 191 * Tests do not apply to the root object. 192 */ 193 194 if (parentCheck && tags->obj_id > 1 && !obj->parent) 195 T(YAFFS_TRACE_VERIFY, 196 (TSTR("Obj %d header mismatch parent_id %d obj->parent is NULL"TENDSTR), 197 tags->obj_id, oh->parent_obj_id)); 198 199 if (parentCheck && obj->parent && 200 oh->parent_obj_id != obj->parent->obj_id && 201 (oh->parent_obj_id != YAFFS_OBJECTID_UNLINKED || 202 obj->parent->obj_id != YAFFS_OBJECTID_DELETED)) 203 T(YAFFS_TRACE_VERIFY, 204 (TSTR("Obj %d header mismatch parent_id %d parent_obj_id %d"TENDSTR), 205 tags->obj_id, oh->parent_obj_id, obj->parent->obj_id)); 206 207 if (tags->obj_id > 1 && oh->name[0] == 0) /* Null name */ 208 T(YAFFS_TRACE_VERIFY, 209 (TSTR("Obj %d header name is NULL"TENDSTR), 210 obj->obj_id)); 211 212 if (tags->obj_id > 1 && ((__u8)(oh->name[0])) == 0xff) /* Trashed name */ 213 T(YAFFS_TRACE_VERIFY, 214 (TSTR("Obj %d header name is 0xFF"TENDSTR), 215 obj->obj_id)); 216} 217 218 219#if 0 220/* Not being used, but don't want to throw away yet */ 221int yaffs_verify_tnode_worker(yaffs_obj_t *obj, yaffs_tnode_t *tn, 222 __u32 level, int chunk_offset) 223{ 224 int i; 225 yaffs_dev_t *dev = obj->my_dev; 226 int ok = 1; 227 228 if (tn) { 229 if (level > 0) { 230 231 for (i = 0; i < YAFFS_NTNODES_INTERNAL && ok; i++) { 232 if (tn->internal[i]) { 233 ok = yaffs_verify_tnode_worker(obj, 234 tn->internal[i], 235 level - 1, 236 (chunk_offset<<YAFFS_TNODES_INTERNAL_BITS) + i); 237 } 238 } 239 } else if (level == 0) { 240 yaffs_ext_tags tags; 241 __u32 obj_id = obj->obj_id; 242 243 chunk_offset <<= YAFFS_TNODES_LEVEL0_BITS; 244 245 for (i = 0; i < YAFFS_NTNODES_LEVEL0; i++) { 246 __u32 theChunk = yaffs_get_group_base(dev, tn, i); 247 248 if (theChunk > 0) { 249 /* T(~0,(TSTR("verifying (%d:%d) %d"TENDSTR),tags.obj_id,tags.chunk_id,theChunk)); */ 250 yaffs_rd_chunk_tags_nand(dev, theChunk, NULL, &tags); 251 if (tags.obj_id != obj_id || tags.chunk_id != chunk_offset) { 252 T(~0, (TSTR("Object %d chunk_id %d NAND mismatch chunk %d tags (%d:%d)"TENDSTR), 253 obj_id, chunk_offset, theChunk, 254 tags.obj_id, tags.chunk_id)); 255 } 256 } 257 chunk_offset++; 258 } 259 } 260 } 261 262 return ok; 263 264} 265 266#endif 267 268void yaffs_verify_file(yaffs_obj_t *obj) 269{ 270 int requiredTallness; 271 int actualTallness; 272 __u32 lastChunk; 273 __u32 x; 274 __u32 i; 275 yaffs_dev_t *dev; 276 yaffs_ext_tags tags; 277 yaffs_tnode_t *tn; 278 __u32 obj_id; 279 280 if (!obj) 281 return; 282 283 if (yaffs_skip_verification(obj->my_dev)) 284 return; 285 286 dev = obj->my_dev; 287 obj_id = obj->obj_id; 288 289 /* Check file size is consistent with tnode depth */ 290 lastChunk = obj->variant.file_variant.file_size / dev->data_bytes_per_chunk + 1; 291 x = lastChunk >> YAFFS_TNODES_LEVEL0_BITS; 292 requiredTallness = 0; 293 while (x > 0) { 294 x >>= YAFFS_TNODES_INTERNAL_BITS; 295 requiredTallness++; 296 } 297 298 actualTallness = obj->variant.file_variant.top_level; 299 300 /* Check that the chunks in the tnode tree are all correct. 301 * We do this by scanning through the tnode tree and 302 * checking the tags for every chunk match. 303 */ 304 305 if (yaffs_skip_nand_verification(dev)) 306 return; 307 308 for (i = 1; i <= lastChunk; i++) { 309 tn = yaffs_find_tnode_0(dev, &obj->variant.file_variant, i); 310 311 if (tn) { 312 __u32 theChunk = yaffs_get_group_base(dev, tn, i); 313 if (theChunk > 0) { 314 /* T(~0,(TSTR("verifying (%d:%d) %d"TENDSTR),obj_id,i,theChunk)); */ 315 yaffs_rd_chunk_tags_nand(dev, theChunk, NULL, &tags); 316 if (tags.obj_id != obj_id || tags.chunk_id != i) { 317 T(~0, (TSTR("Object %d chunk_id %d NAND mismatch chunk %d tags (%d:%d)"TENDSTR), 318 obj_id, i, theChunk, 319 tags.obj_id, tags.chunk_id)); 320 } 321 } 322 } 323 } 324} 325 326 327void yaffs_verify_link(yaffs_obj_t *obj) 328{ 329 if (obj && yaffs_skip_verification(obj->my_dev)) 330 return; 331 332 /* Verify sane equivalent object */ 333} 334 335void yaffs_verify_symlink(yaffs_obj_t *obj) 336{ 337 if (obj && yaffs_skip_verification(obj->my_dev)) 338 return; 339 340 /* Verify symlink string */ 341} 342 343void yaffs_verify_special(yaffs_obj_t *obj) 344{ 345 if (obj && yaffs_skip_verification(obj->my_dev)) 346 return; 347} 348 349void yaffs_verify_obj(yaffs_obj_t *obj) 350{ 351 yaffs_dev_t *dev; 352 353 __u32 chunkMin; 354 __u32 chunkMax; 355 356 __u32 chunk_idOk; 357 __u32 chunkInRange; 358 __u32 chunkShouldNotBeDeleted; 359 __u32 chunkValid; 360 361 if (!obj) 362 return; 363 364 if (obj->being_created) 365 return; 366 367 dev = obj->my_dev; 368 369 if (yaffs_skip_verification(dev)) 370 return; 371 372 /* Check sane object header chunk */ 373 374 chunkMin = dev->internal_start_block * dev->param.chunks_per_block; 375 chunkMax = (dev->internal_end_block+1) * dev->param.chunks_per_block - 1; 376 377 chunkInRange = (((unsigned)(obj->hdr_chunk)) >= chunkMin && ((unsigned)(obj->hdr_chunk)) <= chunkMax); 378 chunk_idOk = chunkInRange || (obj->hdr_chunk == 0); 379 chunkValid = chunkInRange && 380 yaffs_check_chunk_bit(dev, 381 obj->hdr_chunk / dev->param.chunks_per_block, 382 obj->hdr_chunk % dev->param.chunks_per_block); 383 chunkShouldNotBeDeleted = chunkInRange && !chunkValid; 384 385 if (!obj->fake && 386 (!chunk_idOk || chunkShouldNotBeDeleted)) { 387 T(YAFFS_TRACE_VERIFY, 388 (TSTR("Obj %d has chunk_id %d %s %s"TENDSTR), 389 obj->obj_id, obj->hdr_chunk, 390 chunk_idOk ? "" : ",out of range", 391 chunkShouldNotBeDeleted ? ",marked as deleted" : "")); 392 } 393 394 if (chunkValid && !yaffs_skip_nand_verification(dev)) { 395 yaffs_ext_tags tags; 396 yaffs_obj_header *oh; 397 __u8 *buffer = yaffs_get_temp_buffer(dev, __LINE__); 398 399 oh = (yaffs_obj_header *)buffer; 400 401 yaffs_rd_chunk_tags_nand(dev, obj->hdr_chunk, buffer, 402 &tags); 403 404 yaffs_verify_oh(obj, oh, &tags, 1); 405 406 yaffs_release_temp_buffer(dev, buffer, __LINE__); 407 } 408 409 /* Verify it has a parent */ 410 if (obj && !obj->fake && 411 (!obj->parent || obj->parent->my_dev != dev)) { 412 T(YAFFS_TRACE_VERIFY, 413 (TSTR("Obj %d has parent pointer %p which does not look like an object"TENDSTR), 414 obj->obj_id, obj->parent)); 415 } 416 417 /* Verify parent is a directory */ 418 if (obj->parent && obj->parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) { 419 T(YAFFS_TRACE_VERIFY, 420 (TSTR("Obj %d's parent is not a directory (type %d)"TENDSTR), 421 obj->obj_id, obj->parent->variant_type)); 422 } 423 424 switch (obj->variant_type) { 425 case YAFFS_OBJECT_TYPE_FILE: 426 yaffs_verify_file(obj); 427 break; 428 case YAFFS_OBJECT_TYPE_SYMLINK: 429 yaffs_verify_symlink(obj); 430 break; 431 case YAFFS_OBJECT_TYPE_DIRECTORY: 432 yaffs_verify_dir(obj); 433 break; 434 case YAFFS_OBJECT_TYPE_HARDLINK: 435 yaffs_verify_link(obj); 436 break; 437 case YAFFS_OBJECT_TYPE_SPECIAL: 438 yaffs_verify_special(obj); 439 break; 440 case YAFFS_OBJECT_TYPE_UNKNOWN: 441 default: 442 T(YAFFS_TRACE_VERIFY, 443 (TSTR("Obj %d has illegaltype %d"TENDSTR), 444 obj->obj_id, obj->variant_type)); 445 break; 446 } 447} 448 449void yaffs_verify_objects(yaffs_dev_t *dev) 450{ 451 yaffs_obj_t *obj; 452 int i; 453 struct ylist_head *lh; 454 455 if (yaffs_skip_verification(dev)) 456 return; 457 458 /* Iterate through the objects in each hash entry */ 459 460 for (i = 0; i < YAFFS_NOBJECT_BUCKETS; i++) { 461 ylist_for_each(lh, &dev->obj_bucket[i].list) { 462 if (lh) { 463 obj = ylist_entry(lh, yaffs_obj_t, hash_link); 464 yaffs_verify_obj(obj); 465 } 466 } 467 } 468} 469 470 471void yaffs_verify_obj_in_dir(yaffs_obj_t *obj) 472{ 473 struct ylist_head *lh; 474 yaffs_obj_t *listObj; 475 476 int count = 0; 477 478 if (!obj) { 479 T(YAFFS_TRACE_ALWAYS, (TSTR("No object to verify" TENDSTR))); 480 YBUG(); 481 return; 482 } 483 484 if (yaffs_skip_verification(obj->my_dev)) 485 return; 486 487 if (!obj->parent) { 488 T(YAFFS_TRACE_ALWAYS, (TSTR("Object does not have parent" TENDSTR))); 489 YBUG(); 490 return; 491 } 492 493 if (obj->parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) { 494 T(YAFFS_TRACE_ALWAYS, (TSTR("Parent is not directory" TENDSTR))); 495 YBUG(); 496 } 497 498 /* Iterate through the objects in each hash entry */ 499 500 ylist_for_each(lh, &obj->parent->variant.dir_variant.children) { 501 if (lh) { 502 listObj = ylist_entry(lh, yaffs_obj_t, siblings); 503 yaffs_verify_obj(listObj); 504 if (obj == listObj) 505 count++; 506 } 507 } 508 509 if (count != 1) { 510 T(YAFFS_TRACE_ALWAYS, (TSTR("Object in directory %d times" TENDSTR), count)); 511 YBUG(); 512 } 513} 514 515void yaffs_verify_dir(yaffs_obj_t *directory) 516{ 517 struct ylist_head *lh; 518 yaffs_obj_t *listObj; 519 520 if (!directory) { 521 YBUG(); 522 return; 523 } 524 525 if (yaffs_skip_full_verification(directory->my_dev)) 526 return; 527 528 if (directory->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) { 529 T(YAFFS_TRACE_ALWAYS, (TSTR("Directory has wrong type: %d" TENDSTR), directory->variant_type)); 530 YBUG(); 531 } 532 533 /* Iterate through the objects in each hash entry */ 534 535 ylist_for_each(lh, &directory->variant.dir_variant.children) { 536 if (lh) { 537 listObj = ylist_entry(lh, yaffs_obj_t, siblings); 538 if (listObj->parent != directory) { 539 T(YAFFS_TRACE_ALWAYS, (TSTR("Object in directory list has wrong parent %p" TENDSTR), listObj->parent)); 540 YBUG(); 541 } 542 yaffs_verify_obj_in_dir(listObj); 543 } 544 } 545} 546 547static int yaffs_free_verification_failures; 548 549void yaffs_verify_free_chunks(yaffs_dev_t *dev) 550{ 551 int counted; 552 int difference; 553 554 if (yaffs_skip_verification(dev)) 555 return; 556 557 counted = yaffs_count_free_chunks(dev); 558 559 difference = dev->n_free_chunks - counted; 560 561 if (difference) { 562 T(YAFFS_TRACE_ALWAYS, 563 (TSTR("Freechunks verification failure %d %d %d" TENDSTR), 564 dev->n_free_chunks, counted, difference)); 565 yaffs_free_verification_failures++; 566 } 567} 568 569int yaffs_verify_file_sane(yaffs_obj_t *in) 570{ 571#if 0 572 int chunk; 573 int n_chunks; 574 int fSize; 575 int failed = 0; 576 int obj_id; 577 yaffs_tnode_t *tn; 578 yaffs_tags_t localTags; 579 yaffs_tags_t *tags = &localTags; 580 int theChunk; 581 int is_deleted; 582 583 if (in->variant_type != YAFFS_OBJECT_TYPE_FILE) 584 return YAFFS_FAIL; 585 586 obj_id = in->obj_id; 587 fSize = in->variant.file_variant.file_size; 588 n_chunks = 589 (fSize + in->my_dev->data_bytes_per_chunk - 1) / in->my_dev->data_bytes_per_chunk; 590 591 for (chunk = 1; chunk <= n_chunks; chunk++) { 592 tn = yaffs_find_tnode_0(in->my_dev, &in->variant.file_variant, 593 chunk); 594 595 if (tn) { 596 597 theChunk = yaffs_get_group_base(dev, tn, chunk); 598 599 if (yaffs_check_chunk_bits 600 (dev, theChunk / dev->param.chunks_per_block, 601 theChunk % dev->param.chunks_per_block)) { 602 603 yaffs_rd_chunk_tags_nand(in->my_dev, theChunk, 604 tags, 605 &is_deleted); 606 if (yaffs_tags_match 607 (tags, in->obj_id, chunk, is_deleted)) { 608 /* found it; */ 609 610 } 611 } else { 612 613 failed = 1; 614 } 615 616 } else { 617 /* T(("No level 0 found for %d\n", chunk)); */ 618 } 619 } 620 621 return failed ? YAFFS_FAIL : YAFFS_OK; 622#else 623 in=in; 624 return YAFFS_OK; 625#endif 626} 627