src/bin/bfs_tools/chkindex.cpp

   1 /*
   2  * Copyright (c) 2001-2008 pinc Software. All Rights Reserved.
   3  * Released under the terms of the MIT license.
   4  */
   5
   6 //!     sanity and completeness check for indices
   7
   8 #include "Disk.h"
   9 #include "Inode.h"
  10 #include "Hashtable.h"
  11 #include "BPlusTree.h"
  12 #include "dump.h"
  13
  14 #include <fs_info.h>
  15
  16 #include <stdlib.h>
  17 #include <stdio.h>
  18 #include <string.h>
  19 #include <unistd.h>
  20 #include <ctype.h>
  21 #include <errno.h>
  22
  23
  24 char gEscape[3] = {0x1b, '[', 0};
  25 off_t gCount = 1;
  26 bool gDoNotCheckForFiles = false;
  27 bool gDoNotCheckIndex = false;
  28 bool gCheckAll = false;
  29
  30
  31 // we just want to know which inodes exist, so don't remember anything
  32 // along the position of the inode.
  33
  34 class BlockRunHashtable : public Hashtable
  35 {
  36         public:
  37                 BlockRunHashtable(int capacity)
  38                         : Hashtable(capacity)
  39                 {
  40                         SetHashFunction((uint32 (*)(const void *))BlockRunHash);
  41                         SetCompareFunction((bool (*)(const void *, const void *))BlockRunCompare);
  42                 }
  43
  44                 bool Contains(block_run *run)
  45                 {
  46                         return ContainsKey((void *)run);
  47                 }
  48
  49                 bool Put(block_run &run)
  50                 {
  51                         block_run *value = (block_run *)malloc(sizeof(block_run));
  52                         if (!value)
  53                                 return false;
  54
  55                         memcpy(value,&run,sizeof(block_run));
  56
  57                         if (Hashtable::Put(value,value))
  58                                 return true;
  59
  60                         free(value);
  61                         return false;
  62                 }
  63
  64                 static uint32 BlockRunHash(const block_run *run)
  65                 {
  66                         return run->allocation_group << 16 | run->start;
  67                 }
  68
  69                 static bool BlockRunCompare(const block_run *runA, const block_run *runB)
  70                 {
  71                         return *runA == *runB;
  72                 }
  73 };
  74
  75
  76 BlockRunHashtable gHashtable(1000);
  77
  78
  79 int
  80 compareBlockRuns(const block_run *a, const block_run *b)
  81 {
  82         int cmp = (int)a->allocation_group - (int)b->allocation_group;
  83         if (cmp == 0)
  84                 cmp = (int)a->start - (int)b->start;
  85         return cmp;
  86 }
  87
  88
  89 void
  90 collectFiles(Disk &disk,Directory *directory)
  91 {
  92         if (directory == NULL)
  93                 return;
  94
  95         directory->Rewind();
  96         char name[B_FILE_NAME_LENGTH];
  97         block_run run;
  98         while (directory->GetNextEntry(name,&run) >= B_OK)
  99         {
 100                 if (!strcmp(name,".") || !strcmp(name,".."))
 101                         continue;
 102
 103                 gHashtable.Put(run);
 104
 105                 if (++gCount % 50 == 0)
 106                         printf("  %7Ld%s1A\n",gCount,gEscape);
 107
 108                 Inode *inode = Inode::Factory(&disk,run);
 109                 if (inode != NULL)
 110                 {
 111                         if (inode->IsDirectory())
 112                                 collectFiles(disk,static_cast<Directory *>(inode));
 113
 114                         delete inode;
 115                 }
 116                 else
 117                         printf("  Directory \"%s\" (%ld, %d) points to corrupt inode \"%s\" (%ld, %d)\n",
 118                                 directory->Name(),directory->BlockRun().allocation_group,directory->BlockRun().start,
 119                                 name,run.allocation_group,run.start);
 120         }
 121 }
 122
 123
 124 void
 125 collectFiles(Disk &disk)
 126 {
 127         Directory *root = (Directory *)Inode::Factory(&disk,disk.Root());
 128
 129         puts("Collecting files (this will take some time)...");
 130
 131         if (root == NULL || root->InitCheck() < B_OK)
 132         {
 133                 fprintf(stderr,"  Could not open root directory!\n");
 134                 return;
 135         }
 136         collectFiles(disk,root);
 137
 138         printf("  %7Ld files found.\n",gCount);
 139
 140         delete root;
 141 }
 142
 143
 144 void
 145 checkIndexForNonExistingFiles(Disk &disk,BPlusTree &tree)
 146 {
 147         char name[B_FILE_NAME_LENGTH];
 148         uint16 length;
 149         off_t offset;
 150
 151         while (tree.GetNextEntry(name,&length,B_FILE_NAME_LENGTH,&offset) == B_OK)
 152         {
 153                 name[length] = 0;
 154                 block_run run = disk.ToBlockRun(offset);
 155                 if (!gHashtable.Contains(&run))
 156                 {
 157                         printf("  inode at (%ld, %d), offset %Ld, doesn't exist!",run.allocation_group,run.start,offset);
 158                         switch (tree.Type())
 159                         {
 160                                 case BPLUSTREE_STRING_TYPE:
 161                                         printf(" (string = \"%s\")",name);
 162                                         break;
 163                                 case BPLUSTREE_INT32_TYPE:
 164                                         printf(" (int32 = %ld)",*(int32 *)&name);
 165                                         break;
 166                                 case BPLUSTREE_UINT32_TYPE:
 167                                         printf(" (uint32 = %lu)",*(uint32 *)&name);
 168                                         break;
 169                                 case BPLUSTREE_INT64_TYPE:
 170                                         printf(" (int64 = %Ld)",*(int64 *)&name);
 171                                         break;
 172                                 case BPLUSTREE_UINT64_TYPE:
 173                                         printf(" (uint64 = %Lu)",*(uint64 *)&name);
 174                                         break;
 175                                 case BPLUSTREE_FLOAT_TYPE:
 176                                         printf(" (float = %g)",*(float *)&name);
 177                                         break;
 178                                 case BPLUSTREE_DOUBLE_TYPE:
 179                                         printf(" (double = %g)",*(double *)&name);
 180                                         break;
 181                         }
 182                         putchar('\n');
 183                 }
 184         }
 185 }
 186
 187
 188 void
 189 checkFiles(Disk &disk,BPlusTree &tree,char *attribute)
 190 {
 191         block_run *runs = (block_run *)malloc(gCount * sizeof(block_run));
 192         if (runs == NULL)
 193         {
 194                 fprintf(stderr,"  Not enough memory!\n");
 195                 return;
 196         }
 197         // copy hashtable to array
 198         block_run *run = NULL;
 199         int32 index = 0;
 200         gHashtable.Rewind();
 201         while (gHashtable.GetNextEntry((void **)&run) == B_OK)
 202         {
 203                 runs[index++] = *run;
 204         }
 205
 206         // sort array to speed up disk access
 207         qsort(runs,index,sizeof(block_run),(int (*)(const void *,const void *))compareBlockRuns);
 208
 209         bool sizeIndex = !strcmp(attribute,"size");
 210         bool nameIndex = !strcmp(attribute,"name");
 211         bool modifiedIndex = !strcmp(attribute,"last_modified");
 212
 213         char key[B_FILE_NAME_LENGTH];
 214         uint16 keyLength = 0;
 215
 216         Inode *inode = NULL;
 217
 218         for (int32 i = 0;i < index;i++)
 219         {
 220                 if (i % 50 == 0)
 221                         printf("  %7ld%s1A\n",i,gEscape);
 222
 223                 delete inode;
 224                 inode = Inode::Factory(&disk,runs[i]);
 225                 if (inode == NULL || inode->InitCheck() < B_OK)
 226                 {
 227                         fprintf(stderr,"  inode at (%ld, %d) is corrupt!\n",runs[i].allocation_group,runs[i].start);
 228                         delete inode;
 229                         continue;
 230                 }
 231
 232                 // check indices not based on standard attributes
 233                 if (sizeIndex)
 234                 {
 235                         if (inode->IsDirectory())
 236                                 continue;
 237
 238                         memcpy(key,&inode->InodeBuffer()->data.size,sizeof(off_t));
 239                         keyLength = sizeof(off_t);
 240                 }
 241                 else if (nameIndex)
 242                 {
 243                         strcpy(key,inode->Name());
 244                         keyLength = strlen(key);
 245                 }
 246                 else if (modifiedIndex)
 247                 {
 248                         if (inode->IsDirectory())
 249                                 continue;
 250
 251                         memcpy(key,&inode->InodeBuffer()->last_modified_time,sizeof(off_t));
 252                         keyLength = sizeof(off_t);
 253                 }
 254                 else    // iterate through all attributes to find the right one (damn slow, sorry...)
 255                 {
 256                         inode->RewindAttributes();
 257                         char name[B_FILE_NAME_LENGTH];
 258                         uint32 type;
 259                         void *data;
 260                         size_t length;
 261                         bool found = false;
 262                         while (inode->GetNextAttribute(name,&type,&data,&length) == B_OK)
 263                         {
 264                                 if (!strcmp(name,attribute))
 265                                 {
 266                                         strncpy(key,(char *)data,B_FILE_NAME_LENGTH - 1);
 267                                         key[B_FILE_NAME_LENGTH - 1] = '\0';
 268                                         keyLength = length > B_FILE_NAME_LENGTH ? B_FILE_NAME_LENGTH : length;
 269                                         found = true;
 270                                         break;
 271                                 }
 272                         }
 273                         if (!found)
 274                                 continue;
 275                 }
 276
 277                 off_t value;
 278                 if (tree.Find((uint8 *)key,keyLength,&value) < B_OK)
 279                 {
 280                         if (*inode->Name())
 281                                 fprintf(stderr,"  inode at (%ld, %d) name \"%s\" is not in index!\n",runs[i].allocation_group,runs[i].start,inode->Name());
 282                         else
 283                         {
 284                                 // inode is obviously deleted!
 285                                 block_run parent = inode->Parent();
 286                                 Directory *directory = (Directory *)Inode::Factory(&disk,parent);
 287                                 if (directory != NULL && directory->InitCheck() == B_OK)
 288                                 {
 289                                         BPlusTree *parentTree;
 290                                         if (directory->GetTree(&parentTree) == B_OK)
 291                                         {
 292                                                 char name[B_FILE_NAME_LENGTH];
 293                                                 uint16 length;
 294                                                 off_t offset,searchOffset = disk.ToBlock(runs[i]);
 295                                                 bool found = false;
 296
 297                                                 while (parentTree->GetNextEntry(name,&length,B_FILE_NAME_LENGTH,&offset) == B_OK)
 298                                                 {
 299                                                         if (offset == searchOffset)
 300                                                         {
 301                                                                 fprintf(stderr,"  inode at (%ld, %d) name \"%s\" was obviously deleted, but the parent \"%s\" still contains it!\n",runs[i].allocation_group,runs[i].start,name,directory->Name());
 302                                                                 found = true;
 303                                                                 break;
 304                                                         }
 305                                                 }
 306                                                 if (!found)
 307                                                         fprintf(stderr,"  inode at (%ld, %d) was obviously deleted, and the parent \"%s\" obviously doesn't contain it anymore!\n",runs[i].allocation_group,runs[i].start,directory->Name());
 308                                         }
 309                                         else
 310                                                 fprintf(stderr,"  inode at (%ld, %d) was obviously deleted, but the parent \"%s\" is invalid and still contains it!\n",runs[i].allocation_group,runs[i].start,directory->Name());
 311                                 }
 312                                 else
 313                                 {
 314                                         // not that this would be really possible... - but who knows
 315                                         fprintf(stderr,"  inode at (%ld, %d) is not in index and has invalid parent!\n",runs[i].allocation_group,runs[i].start);
 316                                 }
 317                                 delete directory;
 318                         }
 319                 }
 320                 else
 321                 {
 322                         if (bplustree_node::LinkType(value) == BPLUSTREE_NODE)
 323                         {
 324                                 if (disk.ToBlockRun(value) != runs[i])
 325                                         fprintf(stderr,"  offset in index and inode offset doesn't match for inode \"%s\" at (%ld, %d)\n",inode->Name(),runs[i].allocation_group,runs[i].start);
 326                         }
 327                         else
 328                         {
 329                                 // search duplicates
 330                                 char name[B_FILE_NAME_LENGTH];
 331                                 uint16 length;
 332                                 off_t offset;
 333                                 bool found = false,duplicates = false;
 334 //puts("++");
 335                                 tree.Rewind();
 336                                 while (tree.GetNextEntry(name,&length,B_FILE_NAME_LENGTH,&offset) == B_OK)
 337                                 {
 338                                         //printf("search for = %ld, key = %ld -> value = %Ld (%ld, %d)\n",*(int32 *)&key,*(int32 *)&name,offset,disk.ToBlockRun(offset).allocation_group,disk.ToBlockRun(offset).start);
 339                                         if (keyLength == length && !memcmp(key,name,keyLength))
 340                                         {
 341                                                 duplicates = true;
 342                                                 if (disk.ToBlockRun(offset) == runs[i])
 343                                                 {
 344                                                         found = true;
 345                                                         break;
 346                                                 }
 347                                         }
 348                                         //else if (duplicates)
 349                                         //      break;
 350                                 }
 351                                 if (!found)
 352                                 {
 353                                         printf("  inode \"%s\" at (%ld, %d) not found in duplicates!\n",inode->Name(),runs[i].allocation_group,runs[i].start);
 354 //                                      return;
 355                                 }
 356                         }
 357                 }
 358         }
 359         delete inode;
 360         printf("  %7Ld files processed.\n",gCount);
 361 }
 362
 363
 364 int
 365 checkIndex(Disk &disk,char *attribute,block_run &run,bool collect)
 366 {
 367         Directory *index = (Directory *)Inode::Factory(&disk,run);
 368         status_t status;
 369         if (index == NULL || (status = index->InitCheck()) < B_OK)
 370         {
 371                 fprintf(stderr,"  Could not get index directory for \"%s\": %s!\n",attribute,index ? strerror(status) : "not found/corrupted");
 372                 return -1;
 373         }
 374
 375         printf("\nCheck \"%s\" index's on-disk structure...\n",attribute);
 376         //dump_inode(index->InodeBuffer());
 377
 378         BPlusTree *tree;
 379         if (index->GetTree(&tree) < B_OK || tree->Validate(true) < B_OK)
 380         {
 381                 fprintf(stderr,"  B+Tree of index \"%s\" seems to be corrupt!\n",attribute);
 382                 //return -1;
 383         }
 384
 385         if (collect && (!gDoNotCheckIndex || !gDoNotCheckForFiles))
 386                 collectFiles(disk);
 387
 388         if (!gDoNotCheckIndex)
 389         {
 390                 printf("Check for non-existing files in index \"%s\"...\n",attribute);
 391                 checkIndexForNonExistingFiles(disk,*tree);
 392         }
 393
 394         if (!gDoNotCheckForFiles)
 395         {
 396                 printf("Check for files not in index \"%s\" (this may take even more time)...\n",attribute);
 397                 checkFiles(disk,*tree,attribute);
 398         }
 399         return 0;
 400 }
 401
 402
 403 void
 404 printUsage(char *tool)
 405 {
 406         char *filename = strrchr(tool,'/');
 407         fprintf(stderr,"usage: %s [-ifa] index-name\n"
 408                         "\t-i\tdo not check for non-existing files in the index\n"
 409                         "\t-f\tdo not check if all the files are in the index\n"
 410                         "\t-a\tcheck all indices (could take some weeks...)\n"
 411                         ,filename ? filename + 1 : tool);
 412 }
 413
 414
 415 int
 416 main(int argc,char **argv)
 417 {
 418         puts("Copyright (c) 2001-2008 pinc Software.");
 419
 420         char *toolName = argv[0];
 421         if (argc < 2 || !strcmp(argv[1],"--help"))
 422         {
 423                 printUsage(toolName);
 424                 return -1;
 425         }
 426
 427         while (*++argv)
 428         {
 429                 char *arg = *argv;
 430                 if (*arg == '-')
 431                 {
 432                         while (*++arg && isalpha(*arg))
 433                         {
 434                                 switch (*arg)
 435                                 {
 436                                         case 'i':
 437                                                 gDoNotCheckIndex = true;
 438                                                 break;
 439                                         case 'f':
 440                                                 gDoNotCheckForFiles = true;
 441                                                 break;
 442                                         case 'a':
 443                                                 gCheckAll = true;
 444                                                 break;
 445                                 }
 446                         }
 447                 }
 448                 else
 449                         break;
 450         }
 451
 452         char *attribute = argv[0];
 453         if (!gCheckAll && attribute == NULL)
 454         {
 455                 printUsage(toolName);
 456                 return -1;
 457         }
 458
 459         dev_t device = dev_for_path(".");
 460         if (device < B_OK)
 461         {
 462                 fprintf(stderr,"Could not find device for current location: %s\n",strerror(device));
 463                 return -1;
 464         }
 465
 466         fs_info info;
 467         if (fs_stat_dev(device,&info) < B_OK)
 468         {
 469                 fprintf(stderr,"Could not get stats for device: %s\n",strerror(errno));
 470                 return -1;
 471         }
 472
 473         Disk disk(info.device_name);
 474         status_t status;
 475         if ((status = disk.InitCheck()) < B_OK)
 476         {
 477                 fprintf(stderr,"Could not open device or file \"%s\": %s\n",info.device_name,strerror(status));
 478                 return -1;
 479         }
 480
 481         if (disk.ValidateSuperBlock() < B_OK)
 482         {
 483                 fprintf(stderr,"The disk's superblock is corrupt!\n");
 484                 return -1;
 485         }
 486
 487         Directory *indices = (Directory *)Inode::Factory(&disk,disk.Indices());
 488         if (indices == NULL || (status = indices->InitCheck()) < B_OK)
 489         {
 490                 fprintf(stderr,"  Could not get indices directory: %s!\n",indices ? strerror(status) : "not found/corrupted");
 491                 delete indices;
 492                 return -1;
 493         }
 494         BPlusTree *tree;
 495         if (indices->GetTree(&tree) < B_OK || tree->Validate() < B_OK)
 496         {
 497                 fprintf(stderr,"  Indices B+Tree seems to be corrupt!\n");
 498                 delete indices;
 499                 return -1;
 500         }
 501
 502         block_run run;
 503
 504         if (gCheckAll)
 505         {
 506                 putchar('\n');
 507                 collectFiles(disk);
 508
 509                 char name[B_FILE_NAME_LENGTH];
 510                 while (indices->GetNextEntry(name,&run) >= B_OK)
 511                         checkIndex(disk,name,run,false);
 512         }
 513         else if (indices->FindEntry(attribute,&run) == B_OK)
 514                 checkIndex(disk,attribute,run,true);
 515         else
 516                 fprintf(stderr,"  Could not find index directory for \"%s\"!\n",attribute);
 517
 518         delete indices;
 519
 520         gHashtable.MakeEmpty(HASH_EMPTY_NONE,HASH_EMPTY_FREE);
 521
 522         return 0;
 523 }
 524