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 %lld, 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 = %lld)",*(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 = %lld (%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 525