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