yaffs_verify.c

   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
  21 int yaffs_skip_verification(struct yaffs_dev *dev)
  22 {
  23         dev=dev;
  24         return !(yaffs_trace_mask & (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
  40 static const char *block_state_name[] = {
  41 "Unknown",
  42 "Needs scanning",
  43 "Scanning",
  44 "Empty",
  45 "Allocating",
  46 "Full",
  47 "Dirty",
  48 "Checkpoint",
  49 "Collecting",
  50 "Dead"
  51 };
  52
  53
  54 void yaffs_verify_blk(struct yaffs_dev *dev, yaffs_block_info_t *bi, int n)
  55 {
  56         int actually_used;
  57         int in_use;
  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_state_name[bi->block_state]));
  72         }
  73
  74         /* Check pages in use and soft deletions are legal */
  75
  76         actually_used = 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            actually_used < 0 || actually_used > 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         in_use = yaffs_count_chunk_bits(dev, n);
  87         if (in_use != 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, in_use));
  90
  91 }
  92
  93
  94
  95 void yaffs_verify_collected_blk(struct yaffs_dev *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
 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                 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                         state_count[bi->block_state]++;
 125                 else
 126                         illegal_states++;
 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), illegal_states));
 133         if (state_count[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_state_name[i], state_count[i]));
 140
 141         if (dev->blocks_in_checkpt != state_count[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, state_count[YAFFS_BLOCK_STATE_CHECKPOINT]));
 145
 146         if (dev->n_erased_blocks != state_count[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, state_count[YAFFS_BLOCK_STATE_EMPTY]));
 150
 151         if (state_count[YAFFS_BLOCK_STATE_COLLECTING] > 1)
 152                 T(YAFFS_TRACE_VERIFY,
 153                  (TSTR("Too many collecting blocks %d (max is 1)"TENDSTR),
 154                  state_count[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  */
 164 void yaffs_verify_oh(struct yaffs_obj *obj, struct yaffs_obj_hdr *oh, struct yaffs_ext_tags *tags, int parent_check)
 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 parent_check requested.
 190          *
 191          * Tests do not apply to the root object.
 192          */
 193
 194         if (parent_check && 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 (parent_check && 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
 220 void yaffs_verify_file(struct yaffs_obj *obj)
 221 {
 222         int required_depth;
 223         int actual_depth;
 224         u32 last_chunk;
 225         u32 x;
 226         u32 i;
 227         struct yaffs_dev *dev;
 228         struct yaffs_ext_tags tags;
 229         yaffs_tnode_t *tn;
 230         u32 obj_id;
 231
 232         if (!obj)
 233                 return;
 234
 235         if (yaffs_skip_verification(obj->my_dev))
 236                 return;
 237
 238         dev = obj->my_dev;
 239         obj_id = obj->obj_id;
 240
 241         /* Check file size is consistent with tnode depth */
 242         last_chunk =  obj->variant.file_variant.file_size / dev->data_bytes_per_chunk + 1;
 243         x = last_chunk >> YAFFS_TNODES_LEVEL0_BITS;
 244         required_depth = 0;
 245         while (x > 0) {
 246                 x >>= YAFFS_TNODES_INTERNAL_BITS;
 247                 required_depth++;
 248         }
 249
 250         actual_depth = obj->variant.file_variant.top_level;
 251
 252         /* Check that the chunks in the tnode tree are all correct.
 253          * We do this by scanning through the tnode tree and
 254          * checking the tags for every chunk match.
 255          */
 256
 257         if (yaffs_skip_nand_verification(dev))
 258                 return;
 259
 260         for (i = 1; i <= last_chunk; i++) {
 261                 tn = yaffs_find_tnode_0(dev, &obj->variant.file_variant, i);
 262
 263                 if (tn) {
 264                         u32 the_chunk = yaffs_get_group_base(dev, tn, i);
 265                         if (the_chunk > 0) {
 266                                 /* T(~0,(TSTR("verifying (%d:%d) %d"TENDSTR),obj_id,i,the_chunk)); */
 267                                 yaffs_rd_chunk_tags_nand(dev, the_chunk, NULL, &tags);
 268                                 if (tags.obj_id != obj_id || tags.chunk_id != i) {
 269                                         T(~0, (TSTR("Object %d chunk_id %d NAND mismatch chunk %d tags (%d:%d)"TENDSTR),
 270                                                 obj_id, i, the_chunk,
 271                                                 tags.obj_id, tags.chunk_id));
 272                                 }
 273                         }
 274                 }
 275         }
 276 }
 277
 278
 279 void yaffs_verify_link(struct yaffs_obj *obj)
 280 {
 281         if (obj && yaffs_skip_verification(obj->my_dev))
 282                 return;
 283
 284         /* Verify sane equivalent object */
 285 }
 286
 287 void yaffs_verify_symlink(struct yaffs_obj *obj)
 288 {
 289         if (obj && yaffs_skip_verification(obj->my_dev))
 290                 return;
 291
 292         /* Verify symlink string */
 293 }
 294
 295 void yaffs_verify_special(struct yaffs_obj *obj)
 296 {
 297         if (obj && yaffs_skip_verification(obj->my_dev))
 298                 return;
 299 }
 300
 301 void yaffs_verify_obj(struct yaffs_obj *obj)
 302 {
 303         struct yaffs_dev *dev;
 304
 305         u32 chunk_min;
 306         u32 chunk_max;
 307
 308         u32 chunk_id_ok;
 309         u32 chunk_in_range;
 310         u32 chunk_wrongly_deleted;
 311         u32 chunk_valid;
 312
 313         if (!obj)
 314                 return;
 315
 316         if (obj->being_created)
 317                 return;
 318
 319         dev = obj->my_dev;
 320
 321         if (yaffs_skip_verification(dev))
 322                 return;
 323
 324         /* Check sane object header chunk */
 325
 326         chunk_min = dev->internal_start_block * dev->param.chunks_per_block;
 327         chunk_max = (dev->internal_end_block+1) * dev->param.chunks_per_block - 1;
 328
 329         chunk_in_range = (((unsigned)(obj->hdr_chunk)) >= chunk_min &&
 330                         ((unsigned)(obj->hdr_chunk)) <= chunk_max);
 331         chunk_id_ok = chunk_in_range || (obj->hdr_chunk == 0);
 332         chunk_valid = chunk_in_range &&
 333                         yaffs_check_chunk_bit(dev,
 334                                         obj->hdr_chunk / dev->param.chunks_per_block,
 335                                         obj->hdr_chunk % dev->param.chunks_per_block);
 336         chunk_wrongly_deleted = chunk_in_range && !chunk_valid;
 337
 338         if (!obj->fake &&
 339                         (!chunk_id_ok || chunk_wrongly_deleted)) {
 340                 T(YAFFS_TRACE_VERIFY,
 341                         (TSTR("Obj %d has chunk_id %d %s %s"TENDSTR),
 342                         obj->obj_id, obj->hdr_chunk,
 343                         chunk_id_ok ? "" : ",out of range",
 344                         chunk_wrongly_deleted ? ",marked as deleted" : ""));
 345         }
 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, __LINE__);
 351
 352                 oh = (struct yaffs_obj_hdr *)buffer;
 353
 354                 yaffs_rd_chunk_tags_nand(dev, obj->hdr_chunk, buffer,
 355                                 &tags);
 356
 357                 yaffs_verify_oh(obj, oh, &tags, 1);
 358
 359                 yaffs_release_temp_buffer(dev, buffer, __LINE__);
 360         }
 361
 362         /* Verify it has a parent */
 363         if (obj && !obj->fake &&
 364                         (!obj->parent || obj->parent->my_dev != dev)) {
 365                 T(YAFFS_TRACE_VERIFY,
 366                         (TSTR("Obj %d has parent pointer %p which does not look like an object"TENDSTR),
 367                         obj->obj_id, obj->parent));
 368         }
 369
 370         /* Verify parent is a directory */
 371         if (obj->parent && obj->parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
 372                 T(YAFFS_TRACE_VERIFY,
 373                         (TSTR("Obj %d's parent is not a directory (type %d)"TENDSTR),
 374                         obj->obj_id, obj->parent->variant_type));
 375         }
 376
 377         switch (obj->variant_type) {
 378         case YAFFS_OBJECT_TYPE_FILE:
 379                 yaffs_verify_file(obj);
 380                 break;
 381         case YAFFS_OBJECT_TYPE_SYMLINK:
 382                 yaffs_verify_symlink(obj);
 383                 break;
 384         case YAFFS_OBJECT_TYPE_DIRECTORY:
 385                 yaffs_verify_dir(obj);
 386                 break;
 387         case YAFFS_OBJECT_TYPE_HARDLINK:
 388                 yaffs_verify_link(obj);
 389                 break;
 390         case YAFFS_OBJECT_TYPE_SPECIAL:
 391                 yaffs_verify_special(obj);
 392                 break;
 393         case YAFFS_OBJECT_TYPE_UNKNOWN:
 394         default:
 395                 T(YAFFS_TRACE_VERIFY,
 396                 (TSTR("Obj %d has illegaltype %d"TENDSTR),
 397                 obj->obj_id, obj->variant_type));
 398                 break;
 399         }
 400 }
 401
 402 void yaffs_verify_objects(struct yaffs_dev *dev)
 403 {
 404         struct yaffs_obj *obj;
 405         int i;
 406         struct ylist_head *lh;
 407
 408         if (yaffs_skip_verification(dev))
 409                 return;
 410
 411         /* Iterate through the objects in each hash entry */
 412
 413         for (i = 0; i <  YAFFS_NOBJECT_BUCKETS; i++) {
 414                 ylist_for_each(lh, &dev->obj_bucket[i].list) {
 415                         if (lh) {
 416                                 obj = ylist_entry(lh, struct yaffs_obj, hash_link);
 417                                 yaffs_verify_obj(obj);
 418                         }
 419                 }
 420         }
 421 }
 422
 423
 424 void yaffs_verify_obj_in_dir(struct yaffs_obj *obj)
 425 {
 426         struct ylist_head *lh;
 427         struct yaffs_obj *list_obj;
 428
 429         int count = 0;
 430
 431         if (!obj) {
 432                 T(YAFFS_TRACE_ALWAYS, (TSTR("No object to verify" TENDSTR)));
 433                 YBUG();
 434                 return;
 435         }
 436
 437         if (yaffs_skip_verification(obj->my_dev))
 438                 return;
 439
 440         if (!obj->parent) {
 441                 T(YAFFS_TRACE_ALWAYS, (TSTR("Object does not have parent" TENDSTR)));
 442                 YBUG();
 443                 return;
 444         }
 445
 446         if (obj->parent->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
 447                 T(YAFFS_TRACE_ALWAYS, (TSTR("Parent is not directory" TENDSTR)));
 448                 YBUG();
 449         }
 450
 451         /* Iterate through the objects in each hash entry */
 452
 453         ylist_for_each(lh, &obj->parent->variant.dir_variant.children) {
 454                 if (lh) {
 455                         list_obj = ylist_entry(lh, struct yaffs_obj, siblings);
 456                         yaffs_verify_obj(list_obj);
 457                         if (obj == list_obj)
 458                                 count++;
 459                 }
 460          }
 461
 462         if (count != 1) {
 463                 T(YAFFS_TRACE_ALWAYS, (TSTR("Object in directory %d times" TENDSTR), count));
 464                 YBUG();
 465         }
 466 }
 467
 468 void yaffs_verify_dir(struct yaffs_obj *directory)
 469 {
 470         struct ylist_head *lh;
 471         struct yaffs_obj *list_obj;
 472
 473         if (!directory) {
 474                 YBUG();
 475                 return;
 476         }
 477
 478         if (yaffs_skip_full_verification(directory->my_dev))
 479                 return;
 480
 481         if (directory->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
 482                 T(YAFFS_TRACE_ALWAYS,
 483                 (TSTR("Directory has wrong type: %d" TENDSTR),
 484                 directory->variant_type));
 485                 YBUG();
 486         }
 487
 488         /* Iterate through the objects in each hash entry */
 489
 490         ylist_for_each(lh, &directory->variant.dir_variant.children) {
 491                 if (lh) {
 492                         list_obj = ylist_entry(lh, struct yaffs_obj, siblings);
 493                         if (list_obj->parent != directory) {
 494                                 T(YAFFS_TRACE_ALWAYS, (
 495                                 TSTR("Object in directory list has wrong parent %p" TENDSTR),
 496                                 list_obj->parent));
 497                                 YBUG();
 498                         }
 499                         yaffs_verify_obj_in_dir(list_obj);
 500                 }
 501         }
 502 }
 503
 504 static int yaffs_free_verification_failures;
 505
 506 void yaffs_verify_free_chunks(struct yaffs_dev *dev)
 507 {
 508         int counted;
 509         int difference;
 510
 511         if (yaffs_skip_verification(dev))
 512                 return;
 513
 514         counted = yaffs_count_free_chunks(dev);
 515
 516         difference = dev->n_free_chunks - counted;
 517
 518         if (difference) {
 519                 T(YAFFS_TRACE_ALWAYS,
 520                   (TSTR("Freechunks verification failure %d %d %d" TENDSTR),
 521                    dev->n_free_chunks, counted, difference));
 522                 yaffs_free_verification_failures++;
 523         }
 524 }
 525
 526 int yaffs_verify_file_sane(struct yaffs_obj *in)
 527 {
 528         in=in;
 529         return YAFFS_OK;
 530 }