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