src/bin/bfs_tools/chkindex.cpp

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