2 * Copyright (c) 2001-2008 pinc Software. All Rights Reserved.
5 //! recovers corrupt BFS disks
12 #include "Hashtable.h"
13 #include "BPlusTree.h"
26 extern const char *__progname
;
27 static const char *kProgramName
= __progname
;
29 bool gCreateIndices
= false;
30 bool gDumpMissingInodes
= false;
31 bool gRawMode
= false;
32 bool gVerbose
= false;
35 // TODO: add a cache for all inodes
36 typedef std::set
<block_run
> RunSet
;
39 class InodeHashtable
{
41 InodeHashtable(int capacity
)
46 fHashtable
.SetHashFunction((uint32 (*)(const void *))BlockRunHash
);
47 fHashtable
.SetCompareFunction((bool (*)(const void *, const void *))
51 Inode
* Acquire(Inode
* inode
)
56 status_t status
= inode
->AcquireBuffer();
58 fprintf(stderr
, "Could not retrieve buffer for inode %"
59 B_PRIdOFF
": %s\n", inode
->Offset(), strerror(status
));
65 void Release(Inode
* inode
)
67 inode
->ReleaseBuffer();
70 Inode
* Get(block_run run
)
72 return Acquire((Inode
*)fHashtable
.GetValue(&run
));
75 bool Insert(Inode
* inode
)
77 bool success
= fHashtable
.Put(&inode
->BlockRun(), inode
);
79 inode
->ReleaseBuffer();
84 bool Contains(block_run
*key
)
86 return fHashtable
.ContainsKey(key
);
89 Inode
* Remove(block_run
*key
)
91 return Acquire((Inode
*)fHashtable
.Remove(key
));
94 status_t
GetNextEntry(Inode
**_inode
)
96 status_t status
= fHashtable
.GetNextEntry((void**)_inode
);
98 if (Acquire(*_inode
) == NULL
)
112 return fHashtable
.IsEmpty();
117 fHashtable
.MakeEmpty(HASH_EMPTY_NONE
, HASH_EMPTY_DELETE
);
120 static uint32
BlockRunHash(const block_run
*run
)
122 return (run
->allocation_group
<< 16) | run
->start
;
125 static bool BlockRunCompare(const block_run
*runA
, const block_run
*runB
)
127 return *runA
== *runB
;
131 Hashtable fHashtable
;
132 bigtime_t fLastChecked
;
139 InodeGetter(Disk
& disk
, block_run run
)
141 fInode
= Inode::Factory(&disk
, run
);
143 fInode
->AcquireBuffer();
149 fInode
->ReleaseBuffer();
168 // contains all inodes found on disk in the general data area
169 InodeHashtable
gLogged(50);
170 // contains all inodes found in the log area
171 InodeHashtable
gMissing(50);
172 InodeHashtable
gMissingEmpty(25);
175 class HashtableInodeSource
: public Inode::Source
{
177 HashtableInodeSource(Disk
& disk
)
183 virtual Inode
*InodeAt(block_run run
)
186 if ((inode
= gLogged
.Get(run
)) != NULL
)
189 if ((inode
= gMissing
.Get(run
)) != NULL
)
192 if (gMainInodes
.find(run
) == gMainInodes
.end())
195 return Inode::Factory(&fDisk
, run
);
204 operator<(const block_run
& a
, const block_run
& b
)
206 return a
.allocation_group
< b
.allocation_group
207 || (a
.allocation_group
== b
.allocation_group
&& a
.start
< b
.start
);
212 collectInodes(Disk
& disk
, RunSet
* set
, InodeHashtable
* hashTable
, off_t start
,
216 Inode
inode(&disk
, (bfs_inode
*)buffer
, false);
218 off_t directories
= 0LL;
219 off_t directorySize
= 0LL;
221 off_t fileSize
= 0LL;
222 off_t symlinks
= 0LL;
225 off_t position
= start
;
226 bigtime_t lastUpdate
= system_time();
228 for (off_t offset
= start
; offset
< end
; offset
+= sizeof(buffer
)) {
229 if (disk
.ReadAt(offset
, buffer
, sizeof(buffer
)) < B_OK
) {
230 fprintf(stderr
, "could not read from device!\n");
234 //if ((offset % (disk.BlockSize() << disk.SuperBlock()->ag_shift)) == 0)
235 // printf("reading block %Ld, allocation group %Ld, %Ld inodes...\33[1A\n", offset / disk.BlockSize(),offset / (disk.BlockSize() << disk.SuperBlock()->ag_shift), count);
237 for (uint32 i
= 0; i
< sizeof(buffer
); i
+= disk
.BlockSize()) {
238 inode
.SetTo((bfs_inode
*)(buffer
+ i
));
239 if (inode
.InitCheck() == B_OK
) {
240 if (inode
.Flags() & INODE_DELETED
)
243 Inode
*node
= Inode::Factory(&disk
, &inode
);
246 printf(" node: %" B_PRIdOFF
" \"%s\"\n", position
,
250 set
->insert(node
->BlockRun());
252 hashTable
->Insert(node
);
254 if (node
->IsDirectory()) {
256 directorySize
+= node
->Size();
257 } else if (node
->IsFile()) {
259 fileSize
+= node
->Size();
260 } else if (node
->IsSymlink()) {
264 } else if (gVerbose
) {
265 printf("\nunrecognized inode:");
266 dump_inode(&inode
, inode
.InodeBuffer());
269 position
+= disk
.BlockSize();
271 if (system_time() - lastUpdate
> 500000) {
272 printf(" block %" B_PRIdOFF
" (%" B_PRIdOFF
"%%), %" B_PRIdOFF
273 " inodes\33[1A\n", offset
,
274 100 * (offset
- start
) / (end
- start
), count
);
275 lastUpdate
= system_time();
278 printf("\n%" B_PRIdOFF
" inodes found.\n", count
);
280 printf("\n%20" B_PRIdOFF
" directories found (total of %" B_PRIdOFF
281 " bytes)\n%20" B_PRIdOFF
" files found (total of %" B_PRIdOFF
282 " bytes)\n%20" B_PRIdOFF
" symlinks found\n"
283 "--------------------\n"
284 "%20" B_PRIdOFF
" inodes total found.\n",
285 directories
, directorySize
, files
, fileSize
, symlinks
, count
);
290 collectLogInodes(Disk
&disk
)
293 off_t offset
= disk
.ToOffset(disk
.Log());
294 off_t end
= offset
+ (disk
.Log().length
<< disk
.BlockShift());
296 printf("\nsearching from %" B_PRIdOFF
" to %" B_PRIdOFF
" (log area)\n",
299 collectInodes(disk
, NULL
, &gLogged
, offset
, end
);
304 collectRealInodes(Disk
&disk
)
306 // first block after bootblock, bitmap, and log
307 off_t offset
= disk
.ToOffset(disk
.Log()) + (disk
.Log().length
308 << disk
.BlockShift());
309 off_t end
= (off_t
)disk
.NumBlocks() << disk
.BlockShift();
311 printf("\nsearching from %" B_PRIdOFF
" to %" B_PRIdOFF
" (main area)\n",
314 collectInodes(disk
, &gMainInodes
, NULL
, offset
, end
);
319 getNameIndex(Disk
&disk
)
321 InodeGetter
getter(disk
, disk
.Indices());
322 Directory
*indices
= dynamic_cast<Directory
*>(getter
.Node());
325 if (indices
!= NULL
&& indices
->FindEntry("name", &run
) == B_OK
) {
326 InodeGetter
getter(disk
, run
);
327 Inode
* node
= getter
.Node();
329 return dynamic_cast<Directory
*>(node
);
334 RunSet::iterator iterator
= gMainInodes
.begin();
335 for (; iterator
!= gMainInodes
.end(); iterator
++) {
336 InodeGetter
getter(disk
, *iterator
);
337 Inode
* node
= getter
.Node();
339 if (!node
|| !node
->IsIndex() || node
->Name() == NULL
)
341 if (!strcmp(node
->Name(), "name") && node
->Mode() & S_STR_INDEX
)
342 return dynamic_cast<Directory
*>(node
);
350 checkDirectoryContents(Disk
& disk
, Directory
*dir
)
354 char name
[B_FILE_NAME_LENGTH
];
357 while (dir
->GetNextEntry(name
, &run
) == B_OK
) {
358 if (run
== dir
->BlockRun() || run
== dir
->Parent()
359 || gMainInodes
.find(run
) != gMainInodes
.end())
362 Inode
*missing
= gMissing
.Get(run
);
363 if (missing
!= NULL
) {
364 if (missing
->SetName(name
) < B_OK
) {
365 fprintf(stderr
, "setting name of missing node to "
366 "\"%s\" failed!", name
);
369 printf("Set name of missing node (%" B_PRId32
370 ", %d) to \"%s\" (%s)\n",
371 run
.allocation_group
, run
.start
, missing
->Name(), name
);
374 missing
->SetParent(dir
->BlockRun());
376 // if (node->Mode() & S_INDEX_DIR)
378 // if (node->Mode() & S_STR_INDEX)
379 // printf("index directory (%ld, %d): \"%s\" is missing (%ld, %d, %d)\n",node->BlockRun().allocation_group,node->BlockRun().start,name,run.allocation_group,run.start,run.length);
381 // printf("index directory (%ld, %d): key is missing (%ld, %d, %d)\n",node->BlockRun().allocation_group,node->BlockRun().start,run.allocation_group,run.start,run.length);
384 // missing inode has not been found
386 printf("directory \"%s\" (%" B_PRId32
", %d): node \"%s\" is "
387 "missing (%" B_PRId32
", %d, %d)\n", dir
->Name(),
388 dir
->BlockRun().allocation_group
,
389 dir
->BlockRun().start
, name
,
390 run
.allocation_group
, run
.start
, run
.length
);
393 if ((missing
= (Inode
*)gLogged
.Remove(&run
)) != NULL
) {
394 // missing inode is in the log
396 printf("found missing entry in log!\n");
397 if (missing
->InodeBuffer()->parent
!= dir
->BlockRun()) {
399 puts("\tparent directories differ (may be an old "
400 "version of it), reseting parent.");
401 missing
->SetParent(dir
->BlockRun());
403 if (!gMissing
.Insert(missing
))
405 } else if (!gMissingEmpty
.Contains(&run
)) {
406 // not known at all yet
407 Inode
*empty
= Inode::EmptyInode(&disk
, name
, 0);
409 empty
->SetBlockRun(run
);
410 empty
->SetParent(dir
->BlockRun());
412 printf("\tname = %s\n", empty
->Name());
414 if (!gMissingEmpty
.Insert(empty
))
424 checkStructure(Disk
&disk
)
429 RunSet::iterator iterator
= gMainInodes
.begin();
430 for (; iterator
!= gMainInodes
.end(); iterator
++) {
431 InodeGetter
getter(disk
, *iterator
);
432 node
= getter
.Node();
435 if ((count
% 50) == 0)
436 fprintf(stderr
, "%" B_PRIdOFF
" inodes processed...\33[1A\n", count
);
441 if (node
->IsDirectory() && !node
->IsIndex()) {
442 // check if all entries are in the hashtable
443 Directory
* directory
= dynamic_cast<Directory
*>(node
);
444 if (directory
!= NULL
)
445 checkDirectoryContents(disk
, directory
);
447 printf("Node \"%s\" at %" B_PRId32
448 ",%d looks like a directory, but isn't.\n",
449 node
->Name(), node
->BlockRun().allocation_group
,
450 node
->BlockRun().start
);
454 // check for the parent directory
456 block_run run
= node
->Parent();
457 InodeGetter
parentGetter(disk
, run
);
458 Inode
*parentNode
= parentGetter
.Node();
460 Directory
*dir
= dynamic_cast<Directory
*>(parentNode
);
461 if (dir
|| (parentNode
&& (node
->Mode() & S_ATTR_DIR
))) {
462 // entry has a valid parent directory, so it's assumed to be a valid entry
463 disk
.BlockBitmap()->BackupSet(node
, true);
464 } else if (node
->Mode() & S_ATTR
) {
466 printf("attribute \"%s\" at %" B_PRId32
",%d misses its parent.\n",
467 node
->Name(), node
->BlockRun().allocation_group
,
468 node
->BlockRun().start
);
469 puts("\thandling not yet implemented...");
471 } else /*if ((node->Flags() & INODE_DELETED) == 0)*/ {
472 Inode
* missing
= gMissing
.Get(run
);
473 dir
= dynamic_cast<Directory
*>(missing
);
475 if (missing
== NULL
) {
477 printf("%s \"%s\" (%" B_PRId32
", %d, mode = %10" B_PRIo32
478 "): parent directory is missing (%" B_PRId32
479 ", %d, %d), may be deleted!\n",
480 node
->IsFile() ? "file" : "node", node
->Name(),
481 node
->BlockRun().allocation_group
,
482 node
->BlockRun().start
,
483 node
->Mode(), run
.allocation_group
, run
.start
,
487 if ((dir
= dynamic_cast<Directory
*>((Inode
*)gLogged
.Remove(
490 printf("found directory \"%s\" in log:\n", dir
->Name());
492 dump_inode(dir
, dir
->InodeBuffer());
494 puts("\tempty inode.");
498 puts("\tcreate parent missing entry");
500 Inode
*nameNode
= (Inode
*)gMissingEmpty
.Remove(&run
);
501 if (nameNode
!= NULL
) {
502 nameNode
->SetMode(S_IFDIR
);
504 printf("found missing name!\n");
507 parentName
<< "__directory " << run
.allocation_group
508 << ":" << (int32
)run
.start
;
510 nameNode
= Inode::EmptyInode(&disk
, parentName
.String(),
513 nameNode
->SetBlockRun(run
);
514 nameNode
->SetParent(disk
.Root());
519 dir
= new Directory(*nameNode
);
520 if (dir
->CopyBuffer() < B_OK
)
521 puts("could not copy buffer!");
527 dir
->AcquireBuffer();
529 if (!gMissing
.Insert(dir
)) {
530 printf("could not add dir!!\n");
535 } else if (missing
!= NULL
&& dir
== NULL
&& gVerbose
) {
536 printf("%s \"%s\" (%" B_PRId32
", %d, mode = %10" B_PRIo32
537 "): parent directory found in missing list (%" B_PRId32
538 ", %d, %d), but it's not a dir!\n",
539 node
->IsFile() ? "file" : "node", node
->Name(),
540 node
->BlockRun().allocation_group
, node
->BlockRun().start
,
541 node
->Mode(), run
.allocation_group
, run
.start
, run
.length
);
542 } else if (gVerbose
) {
543 printf("%s \"%s\" (%" B_PRId32
", %d, mode = %10" B_PRIo32
544 "): parent directory found in missing list (%" B_PRId32
546 node
->IsFile() ? "file" : "node", node
->Name(),
547 node
->BlockRun().allocation_group
, node
->BlockRun().start
,
548 node
->Mode(), run
.allocation_group
, run
.start
, run
.length
);
553 dir
->ReleaseBuffer();
558 // printf("node %s\n", node->Name());
559 // status_t status = dir->Contains(node);
560 // if (status == B_ENTRY_NOT_FOUND)
561 // printf("node \"%s\": parent directory \"%s\" contains no link to this node!\n",node->Name(),dir->Name());
562 // else if (status != B_OK)
563 // printf("node \"%s\": parent directory \"%s\" error: %s\n",node->Name(),dir->Name(),strerror(status));
566 // check for attributes
568 run
= node
->Attributes();
570 //printf("node \"%s\" (%ld, %d, mode = %010lo): has attribute dir!\n",node->Name(),node->BlockRun().allocation_group,node->BlockRun().start,node->Mode());
572 if (gMainInodes
.find(run
) == gMainInodes
.end()) {
574 printf("node \"%s\": attributes are missing (%" B_PRId32
575 ", %d, %d)\n", node
->Name(), run
.allocation_group
,
576 run
.start
, run
.length
);
579 if ((dir
= (Directory
*)gMissing
.Get(run
)) != NULL
) {
581 puts("\tfound in missing");
582 dir
->SetMode(dir
->Mode() | S_ATTR_DIR
);
583 dir
->SetParent(node
->BlockRun());
586 puts("\tcreate new!");
588 Inode
*empty
= Inode::EmptyInode(&disk
, NULL
,
589 S_IFDIR
| S_ATTR_DIR
);
591 empty
->SetBlockRun(run
);
592 empty
->SetParent(node
->BlockRun());
594 dir
= new Directory(*empty
);
595 if (dir
->CopyBuffer() < B_OK
)
596 puts("could not copy buffer!");
600 if (!gMissing
.Insert(dir
)) {
601 puts("\tcould not add attribute dir");
609 printf("%" B_PRIdOFF
" inodes processed.\n", count
);
611 Directory
*directory
= getNameIndex(disk
);
612 if (directory
!= NULL
) {
613 puts("\n*** Search names of missing inodes in the name index");
616 if (directory
->GetTree(&tree
) == B_OK
&& tree
->Validate(gVerbose
) == B_OK
) {
617 char name
[B_FILE_NAME_LENGTH
];
620 while (directory
->GetNextEntry(name
, &run
) >= B_OK
) {
621 if ((node
= gMissing
.Get(run
)) == NULL
)
625 printf(" Node found: %" B_PRId32
":%d\n",
626 run
.allocation_group
, run
.start
);
628 if (node
->Name() == NULL
|| strcmp(node
->Name(), name
)) {
630 printf("\tnames differ: %s -> %s (indices)\n",
637 printf("\tname index is corrupt!\n");
639 directory
->ReleaseBuffer();
641 printf("*** Name index corrupt or not existent!\n");
646 if (!gMissing
.IsEmpty())
647 puts("\n*** Missing inodes:");
650 while (gMissing
.GetNextEntry(&node
) == B_OK
) {
651 if (gDumpMissingInodes
)
652 dump_inode(node
, node
->InodeBuffer());
654 Directory
*dir
= dynamic_cast<Directory
*>(node
);
656 printf("\ndirectory \"%s\" (%" B_PRId32
", %d) contents:\n",
657 node
->Name(), node
->BlockRun().allocation_group
,
658 node
->BlockRun().start
);
662 char name
[B_FILE_NAME_LENGTH
];
664 while (dir
->GetNextEntry(name
, &run
) == B_OK
) {
665 printf("\t\"%s\" (%" B_PRId32
", %d, %d)\n", name
,
666 run
.allocation_group
, run
.start
, run
.length
);
670 if (dir
->GetTree(&tree
) < B_OK
)
676 while (tree
->GetNextEntry(name
, &length
, B_FILE_NAME_LENGTH
,
680 run
= disk
.ToBlockRun(offset
);
681 printf("%s: block_run == (%5" B_PRId32
",%5d,%5d), \"%s\"\n",
682 dir
->Name(), run
.allocation_group
, run
.start
, run
.length
,
686 //tree->WriteTo(dir);
687 //disk.WriteAt(dir->Offset(),dir->InodeBuffer(),disk.BlockSize());
690 gMissing
.Release(node
);
696 copyInodes(Disk
& disk
, const char* copyTo
)
701 HashtableInodeSource
source(disk
);
706 RunSet::iterator iterator
= gMainInodes
.begin();
707 for (; iterator
!= gMainInodes
.end(); iterator
++) {
708 InodeGetter
getter(disk
, *iterator
);
709 Inode
* node
= getter
.Node();
711 if (node
&& !node
->IsIndex() && !node
->IsAttributeDirectory())
712 node
->CopyTo(copyTo
, true, &source
);
714 if ((++count
% 500) == 0)
715 fprintf(stderr
, "copied %" B_PRId32
" files...\n", count
);
719 while (gMissing
.GetNextEntry(&node
) == B_OK
) {
720 if (!node
->IsIndex() && !node
->IsAttributeDirectory())
721 node
->CopyTo(copyTo
, true, &source
);
723 gMissing
.Release(node
);
731 fprintf(stderr
,"usage: %s [-idv] [-r [start-offset] [end-offset]] <device> [recover-to-path]\n"
732 "\t-i\trecreate indices on target disk\n"
733 "\t-d\tdump missing and recreated i-nodes\n"
734 "\t-r\tdisk access in raw mode (use only if the partition table is invalid)\n"
735 "\t-s\trecreate superblock and exit (for experts only, don't use this\n"
736 "\t\tif you don't know what you're doing)\n"
737 "\t-v\tverbose output\n", name
);
743 main(int argc
, char **argv
)
745 char *fileName
= strrchr(argv
[0], '/');
746 fileName
= fileName
? fileName
+ 1 : argv
[0];
747 bool recreateSuperBlockOnly
= false;
749 off_t startOffset
= 0, endOffset
= -1;
751 puts("Copyright (c) 2001-2008 pinc Software.");
753 if (argc
< 2 || !strcmp(argv
[1], "--help"))
759 while (*++arg
&& isalpha(*arg
)) {
765 if (argv
[1] && isdigit((argv
[1])[0])) {
769 startOffset
= atoll(arg
);
771 if (argv
[1] && isdigit((argv
[1])[0])) {
775 endOffset
= atoll(arg
);
777 if (endOffset
!= -1 && endOffset
< startOffset
)
785 gCreateIndices
= true;
788 gDumpMissingInodes
= true;
791 recreateSuperBlockOnly
= true;
799 Disk
disk(argv
[0], gRawMode
, startOffset
, endOffset
);
800 if (disk
.InitCheck() < B_OK
) {
801 fprintf(stderr
,"Could not open device or file: %s\n",
802 strerror(disk
.InitCheck()));
806 if (argv
[1] != NULL
) {
807 dev_t device
= dev_for_path(argv
[1]);
809 if (fs_stat_dev(device
, &info
) == B_OK
) {
810 if (!strcmp(info
.device_name
, disk
.Path().Path())) {
811 fprintf(stderr
,"The source and target device are identical, "
812 "you currently need\n"
813 "to have another disk to recover to, sorry!\n");
816 if ((info
.flags
& (B_FS_IS_PERSISTENT
| B_FS_HAS_ATTR
))
817 != (B_FS_IS_PERSISTENT
| B_FS_HAS_ATTR
)) {
818 fprintf(stderr
, "%s: The target file system (%s) does not have "
820 "\tfunctionality in order to restore all information.\n",
821 kProgramName
, info
.fsh_name
);
827 bool recreatedSuperBlock
= false;
829 if (disk
.ValidateSuperBlock() < B_OK
) {
830 fprintf(stderr
, "The disk's superblock is corrupt!\n");
831 if (disk
.RecreateSuperBlock() < B_OK
) {
832 fprintf(stderr
, "Can't recreate the disk's superblock, sorry!\n");
835 recreatedSuperBlock
= true;
838 puts("\n*** The superblock:\n");
839 dump_super_block(disk
.SuperBlock());
842 if (recreateSuperBlockOnly
) {
843 if (!recreatedSuperBlock
) {
844 printf("Superblock was valid, no changes made.\n");
848 status_t status
= disk
.WriteAt(512, disk
.SuperBlock(),
849 sizeof(disk_super_block
));
851 fprintf(stderr
, "Could not write superblock: %s!\n",
858 puts("\n*** Collecting inodes...");
860 collectLogInodes(disk
);
861 collectRealInodes(disk
);
863 puts("\n*** Checking Disk Structure Integrity...");
865 checkStructure(disk
);
868 copyInodes(disk
, argv
[1]);
870 //disk.WriteBootBlock();
871 //disk.BlockBitmap()->CompareWithBackup();
873 gMissing
.MakeEmpty();