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 524