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 actual_depth; 228 int last_chunk; 229 u32 offset_in_chunk; 230 u32 the_chunk; 231 232 u32 i; 233 struct yaffs_dev *dev; 234 struct yaffs_ext_tags tags; 235 struct yaffs_tnode *tn; 236 u32 obj_id; 237 238 if (!obj) 239 return; 240 241 if (yaffs_skip_verification(obj->my_dev)) 242 return; 243 244 dev = obj->my_dev; 245 obj_id = obj->obj_id; 246 247 248 /* Check file size is consistent with tnode depth */ 249 yaffs_addr_to_chunk(dev, obj->variant.file_variant.file_size, 250 &last_chunk, &offset_in_chunk); 251 last_chunk++; 252 x = last_chunk >> YAFFS_TNODES_LEVEL0_BITS; 253 required_depth = 0; 254 while (x > 0) { 255 x >>= YAFFS_TNODES_INTERNAL_BITS; 256 required_depth++; 257 } 258 259 actual_depth = obj->variant.file_variant.top_level; 260 261 /* Check that the chunks in the tnode tree are all correct. 262 * We do this by scanning through the tnode tree and 263 * checking the tags for every chunk match. 264 */ 265 266 if (yaffs_skip_nand_verification(dev)) 267 return; 268 269 for (i = 1; i <= last_chunk; i++) { 270 tn = yaffs_find_tnode_0(dev, &obj->variant.file_variant, i); 271 272 if (!tn) 273 continue; 274 275 the_chunk = yaffs_get_group_base(dev, tn, i); 276 if (the_chunk > 0) { 277 yaffs_rd_chunk_tags_nand(dev, the_chunk, NULL, 278 &tags); 279 if (tags.obj_id != obj_id || tags.chunk_id != i) 280 yaffs_trace(YAFFS_TRACE_VERIFY, 281 "Object %d chunk_id %d NAND mismatch chunk %d tags (%d:%d)", 282 obj_id, i, the_chunk, 283 tags.obj_id, tags.chunk_id); 284 } 285 } 286 } 287 288 void yaffs_verify_link(struct yaffs_obj *obj) 289 { 290 if (obj && yaffs_skip_verification(obj->my_dev)) 291 return; 292 293 /* Verify sane equivalent object */ 294 } 295 296 void yaffs_verify_symlink(struct yaffs_obj *obj) 297 { 298 if (obj && yaffs_skip_verification(obj->my_dev)) 299 return; 300 301 /* Verify symlink string */ 302 } 303 304 void yaffs_verify_special(struct yaffs_obj *obj) 305 { 306 if (obj && yaffs_skip_verification(obj->my_dev)) 307 return; 308 } 309 310 void yaffs_verify_obj(struct yaffs_obj *obj) 311 { 312 struct yaffs_dev *dev; 313 u32 chunk_min; 314 u32 chunk_max; 315 u32 chunk_id_ok; 316 u32 chunk_in_range; 317 u32 chunk_wrongly_deleted; 318 u32 chunk_valid; 319 320 if (!obj) 321 return; 322 323 if (obj->being_created) 324 return; 325 326 dev = obj->my_dev; 327 328 if (yaffs_skip_verification(dev)) 329 return; 330 331 /* Check sane object header chunk */ 332 333 chunk_min = dev->internal_start_block * dev->param.chunks_per_block; 334 chunk_max = 335 (dev->internal_end_block + 1) * dev->param.chunks_per_block - 1; 336 337 chunk_in_range = (((unsigned)(obj->hdr_chunk)) >= chunk_min && 338 ((unsigned)(obj->hdr_chunk)) <= chunk_max); 339 chunk_id_ok = chunk_in_range || (obj->hdr_chunk == 0); 340 chunk_valid = chunk_in_range && 341 yaffs_check_chunk_bit(dev, 342 obj->hdr_chunk / dev->param.chunks_per_block, 343 obj->hdr_chunk % dev->param.chunks_per_block); 344 chunk_wrongly_deleted = chunk_in_range && !chunk_valid; 345 346 if (!obj->fake && (!chunk_id_ok || chunk_wrongly_deleted)) 347 yaffs_trace(YAFFS_TRACE_VERIFY, 348 "Obj %d has chunk_id %d %s %s", 349 obj->obj_id, obj->hdr_chunk, 350 chunk_id_ok ? "" : ",out of range", 351 chunk_wrongly_deleted ? ",marked as deleted" : ""); 352 353 if (chunk_valid && !yaffs_skip_nand_verification(dev)) { 354 struct yaffs_ext_tags tags; 355 struct yaffs_obj_hdr *oh; 356 u8 *buffer = yaffs_get_temp_buffer(dev); 357 358 oh = (struct yaffs_obj_hdr *)buffer; 359 360 yaffs_rd_chunk_tags_nand(dev, obj->hdr_chunk, buffer, &tags); 361 362 yaffs_verify_oh(obj, oh, &tags, 1); 363 364 yaffs_release_temp_buffer(dev, buffer); 365 } 366 367 /* Verify it has a parent */ 368 if (obj && !obj->fake && (!obj->parent || obj->parent->my_dev != dev)) { 369 yaffs_trace(YAFFS_TRACE_VERIFY, 370 "Obj %d has parent pointer %p which does not look like an object", 371 obj->obj_id, obj->parent); 372 } 373 374 /* Verify parent is a directory */ 375 if (obj->parent && 376 obj->parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) { 377 yaffs_trace(YAFFS_TRACE_VERIFY, 378 "Obj %d's parent is not a directory (type %d)", 379 obj->obj_id, obj->parent->variant_type); 380 } 381 382 switch (obj->variant_type) { 383 case YAFFS_OBJECT_TYPE_FILE: 384 yaffs_verify_file(obj); 385 break; 386 case YAFFS_OBJECT_TYPE_SYMLINK: 387 yaffs_verify_symlink(obj); 388 break; 389 case YAFFS_OBJECT_TYPE_DIRECTORY: 390 yaffs_verify_dir(obj); 391 break; 392 case YAFFS_OBJECT_TYPE_HARDLINK: 393 yaffs_verify_link(obj); 394 break; 395 case YAFFS_OBJECT_TYPE_SPECIAL: 396 yaffs_verify_special(obj); 397 break; 398 case YAFFS_OBJECT_TYPE_UNKNOWN: 399 default: 400 yaffs_trace(YAFFS_TRACE_VERIFY, 401 "Obj %d has illegaltype %d", 402 obj->obj_id, obj->variant_type); 403 break; 404 } 405 } 406 407 void yaffs_verify_objects(struct yaffs_dev *dev) 408 { 409 struct yaffs_obj *obj; 410 int i; 411 struct list_head *lh; 412 413 if (yaffs_skip_verification(dev)) 414 return; 415 416 /* Iterate through the objects in each hash entry */ 417 418 for (i = 0; i < YAFFS_NOBJECT_BUCKETS; i++) { 419 list_for_each(lh, &dev->obj_bucket[i].list) { 420 obj = list_entry(lh, struct yaffs_obj, hash_link); 421 yaffs_verify_obj(obj); 422 } 423 } 424 } 425 426 void yaffs_verify_obj_in_dir(struct yaffs_obj *obj) 427 { 428 struct list_head *lh; 429 struct yaffs_obj *list_obj; 430 int count = 0; 431 432 if (!obj) { 433 yaffs_trace(YAFFS_TRACE_ALWAYS, "No object to verify"); 434 BUG(); 435 return; 436 } 437 438 if (yaffs_skip_verification(obj->my_dev)) 439 return; 440 441 if (!obj->parent) { 442 yaffs_trace(YAFFS_TRACE_ALWAYS, "Object does not have parent"); 443 BUG(); 444 return; 445 } 446 447 if (obj->parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) { 448 yaffs_trace(YAFFS_TRACE_ALWAYS, "Parent is not directory"); 449 BUG(); 450 } 451 452 /* Iterate through the objects in each hash entry */ 453 454 list_for_each(lh, &obj->parent->variant.dir_variant.children) { 455 list_obj = list_entry(lh, struct yaffs_obj, siblings); 456 yaffs_verify_obj(list_obj); 457 if (obj == list_obj) 458 count++; 459 } 460 461 if (count != 1) { 462 yaffs_trace(YAFFS_TRACE_ALWAYS, 463 "Object in directory %d times", 464 count); 465 BUG(); 466 } 467 } 468 469 void yaffs_verify_dir(struct yaffs_obj *directory) 470 { 471 struct list_head *lh; 472 struct yaffs_obj *list_obj; 473 474 if (!directory) { 475 BUG(); 476 return; 477 } 478 479 if (yaffs_skip_full_verification(directory->my_dev)) 480 return; 481 482 if (directory->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) { 483 yaffs_trace(YAFFS_TRACE_ALWAYS, 484 "Directory has wrong type: %d", 485 directory->variant_type); 486 BUG(); 487 } 488 489 /* Iterate through the objects in each hash entry */ 490 491 list_for_each(lh, &directory->variant.dir_variant.children) { 492 list_obj = list_entry(lh, struct yaffs_obj, siblings); 493 if (list_obj->parent != directory) { 494 yaffs_trace(YAFFS_TRACE_ALWAYS, 495 "Object in directory list has wrong parent %p", 496 list_obj->parent); 497 BUG(); 498 } 499 yaffs_verify_obj_in_dir(list_obj); 500 } 501 } 502 503 static int yaffs_free_verification_failures; 504 505 void yaffs_verify_free_chunks(struct yaffs_dev *dev) 506 { 507 int counted; 508 int difference; 509 510 if (yaffs_skip_verification(dev)) 511 return; 512 513 counted = yaffs_count_free_chunks(dev); 514 515 difference = dev->n_free_chunks - counted; 516 517 if (difference) { 518 yaffs_trace(YAFFS_TRACE_ALWAYS, 519 "Freechunks verification failure %d %d %d", 520 dev->n_free_chunks, counted, difference); 521 yaffs_free_verification_failures++; 522 } 523 } 524 525 int yaffs_verify_file_sane(struct yaffs_obj *in) 526 { 527 in = in; 528 return YAFFS_OK; 529 } 530