2 * Copyright (c) 2001-2008 pinc Software. All Rights Reserved.
3 * Released under the terms of the MIT license.
6 //! recovers corrupt BFS disks
13 #include "Hashtable.h"
14 #include "BPlusTree.h"
27 extern const char *__progname
;
28 static const char *kProgramName
= __progname
;
30 bool gCreateIndices
= false;
31 bool gDumpMissingInodes
= false;
32 bool gRawMode
= false;
33 bool gVerbose
= false;
36 // TODO: add a cache for all inodes
37 typedef std::set
<block_run
> RunSet
;
40 class InodeHashtable
{
42 InodeHashtable(int capacity
)
47 fHashtable
.SetHashFunction((uint32 (*)(const void *))BlockRunHash
);
48 fHashtable
.SetCompareFunction((bool (*)(const void *, const void *))
52 Inode
* Acquire(Inode
* inode
)
57 status_t status
= inode
->AcquireBuffer();
59 fprintf(stderr
, "Could not retrieve buffer for inode %"
60 B_PRIdOFF
": %s\n", inode
->Offset(), strerror(status
));
66 void Release(Inode
* inode
)
68 inode
->ReleaseBuffer();
71 Inode
* Get(block_run run
)
73 return Acquire((Inode
*)fHashtable
.GetValue(&run
));
76 bool Insert(Inode
* inode
)
78 bool success
= fHashtable
.Put(&inode
->BlockRun(), inode
);
80 inode
->ReleaseBuffer();
85 bool Contains(block_run
*key
)
87 return fHashtable
.ContainsKey(key
);
90 Inode
* Remove(block_run
*key
)
92 return Acquire((Inode
*)fHashtable
.Remove(key
));
95 status_t
GetNextEntry(Inode
**_inode
)
97 status_t status
= fHashtable
.GetNextEntry((void**)_inode
);
99 if (Acquire(*_inode
) == NULL
)
113 return fHashtable
.IsEmpty();
118 fHashtable
.MakeEmpty(HASH_EMPTY_NONE
, HASH_EMPTY_DELETE
);
121 static uint32
BlockRunHash(const block_run
*run
)
123 return (run
->allocation_group
<< 16) | run
->start
;
126 static bool BlockRunCompare(const block_run
*runA
, const block_run
*runB
)
128 return *runA
== *runB
;
132 Hashtable fHashtable
;
133 bigtime_t fLastChecked
;
140 InodeGetter(Disk
& disk
, block_run run
)
142 fInode
= Inode::Factory(&disk
, run
);
144 fInode
->AcquireBuffer();
150 fInode
->ReleaseBuffer();
169 // contains all inodes found on disk in the general data area
170 InodeHashtable
gLogged(50);
171 // contains all inodes found in the log area
172 InodeHashtable
gMissing(50);
173 InodeHashtable
gMissingEmpty(25);
176 class HashtableInodeSource
: public Inode::Source
{
178 HashtableInodeSource(Disk
& disk
)
184 virtual Inode
*InodeAt(block_run run
)
187 if ((inode
= gLogged
.Get(run
)) != NULL
)
190 if ((inode
= gMissing
.Get(run
)) != NULL
)
193 if (gMainInodes
.find(run
) == gMainInodes
.end())
196 return Inode::Factory(&fDisk
, run
);
205 operator<(const block_run
& a
, const block_run
& b
)
207 return a
.allocation_group
< b
.allocation_group
208 || (a
.allocation_group
== b
.allocation_group
&& a
.start
< b
.start
);
213 collectInodes(Disk
& disk
, RunSet
* set
, InodeHashtable
* hashTable
, off_t start
,
217 Inode
inode(&disk
, (bfs_inode
*)buffer
, false);
219 off_t directories
= 0LL;
220 off_t directorySize
= 0LL;
222 off_t fileSize
= 0LL;
223 off_t symlinks
= 0LL;
226 off_t position
= start
;
227 bigtime_t lastUpdate
= system_time();
229 for (off_t offset
= start
; offset
< end
; offset
+= sizeof(buffer
)) {
230 if (disk
.ReadAt(offset
, buffer
, sizeof(buffer
)) < B_OK
) {
231 fprintf(stderr
, "could not read from device!\n");
235 //if ((offset % (disk.BlockSize() << disk.SuperBlock()->ag_shift)) == 0)
236 // printf("reading block %Ld, allocation group %Ld, %Ld inodes...\33[1A\n", offset / disk.BlockSize(),offset / (disk.BlockSize() << disk.SuperBlock()->ag_shift), count);
238 for (uint32 i
= 0; i
< sizeof(buffer
); i
+= disk
.BlockSize()) {
239 inode
.SetTo((bfs_inode
*)(buffer
+ i
));
240 if (inode
.InitCheck() == B_OK
) {
241 if (inode
.Flags() & INODE_DELETED
)
244 Inode
*node
= Inode::Factory(&disk
, &inode
);
247 printf(" node: %" B_PRIdOFF
" \"%s\"\n", position
,
251 set
->insert(node
->BlockRun());
253 hashTable
->Insert(node
);
255 if (node
->IsDirectory()) {
257 directorySize
+= node
->Size();
258 } else if (node
->IsFile()) {
260 fileSize
+= node
->Size();
261 } else if (node
->IsSymlink()) {
265 } else if (gVerbose
) {
266 printf("\nunrecognized inode:");
267 dump_inode(&inode
, inode
.InodeBuffer());
270 position
+= disk
.BlockSize();
272 if (system_time() - lastUpdate
> 500000) {
273 printf(" block %" B_PRIdOFF
" (%" B_PRIdOFF
"%%), %" B_PRIdOFF
274 " inodes\33[1A\n", offset
,
275 100 * (offset
- start
) / (end
- start
), count
);
276 lastUpdate
= system_time();
279 printf("\n%" B_PRIdOFF
" inodes found.\n", count
);
281 printf("\n%20" B_PRIdOFF
" directories found (total of %" B_PRIdOFF
282 " bytes)\n%20" B_PRIdOFF
" files found (total of %" B_PRIdOFF
283 " bytes)\n%20" B_PRIdOFF
" symlinks found\n"
284 "--------------------\n"
285 "%20" B_PRIdOFF
" inodes total found.\n",
286 directories
, directorySize
, files
, fileSize
, symlinks
, count
);
291 collectLogInodes(Disk
&disk
)
294 off_t offset
= disk
.ToOffset(disk
.Log());
295 off_t end
= offset
+ (disk
.Log().length
<< disk
.BlockShift());
297 printf("\nsearching from %" B_PRIdOFF
" to %" B_PRIdOFF
" (log area)\n",
300 collectInodes(disk
, NULL
, &gLogged
, offset
, end
);
305 collectRealInodes(Disk
&disk
)
307 // first block after bootblock, bitmap, and log
308 off_t offset
= disk
.ToOffset(disk
.Log()) + (disk
.Log().length
309 << disk
.BlockShift());
310 off_t end
= (off_t
)disk
.NumBlocks() << disk
.BlockShift();
312 printf("\nsearching from %" B_PRIdOFF
" to %" B_PRIdOFF
" (main area)\n",
315 collectInodes(disk
, &gMainInodes
, NULL
, offset
, end
);
320 getNameIndex(Disk
&disk
)
322 InodeGetter
getter(disk
, disk
.Indices());
323 Directory
*indices
= dynamic_cast<Directory
*>(getter
.Node());
326 if (indices
!= NULL
&& indices
->FindEntry("name", &run
) == B_OK
) {
327 InodeGetter
getter(disk
, run
);
328 Inode
* node
= getter
.Node();
330 return dynamic_cast<Directory
*>(node
);
335 RunSet::iterator iterator
= gMainInodes
.begin();
336 for (; iterator
!= gMainInodes
.end(); iterator
++) {
337 InodeGetter
getter(disk
, *iterator
);
338 Inode
* node
= getter
.Node();
340 if (!node
|| !node
->IsIndex() || node
->Name() == NULL
)
342 if (!strcmp(node
->Name(), "name") && node
->Mode() & S_STR_INDEX
)
343 return dynamic_cast<Directory
*>(node
);
351 checkDirectoryContents(Disk
& disk
, Directory
*dir
)
355 char name
[B_FILE_NAME_LENGTH
];
358 while (dir
->GetNextEntry(name
, &run
) == B_OK
) {
359 if (run
== dir
->BlockRun() || run
== dir
->Parent()
360 || gMainInodes
.find(run
) != gMainInodes
.end())
363 Inode
*missing
= gMissing
.Get(run
);
364 if (missing
!= NULL
) {
365 if (missing
->SetName(name
) < B_OK
) {
366 fprintf(stderr
, "setting name of missing node to "
367 "\"%s\" failed!", name
);
370 printf("Set name of missing node (%" B_PRId32
371 ", %d) to \"%s\" (%s)\n",
372 run
.allocation_group
, run
.start
, missing
->Name(), name
);
375 missing
->SetParent(dir
->BlockRun());
377 // if (node->Mode() & S_INDEX_DIR)
379 // if (node->Mode() & S_STR_INDEX)
380 // 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);
382 // 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);
385 // missing inode has not been found
387 printf("directory \"%s\" (%" B_PRId32
", %d): node \"%s\" is "
388 "missing (%" B_PRId32
", %d, %d)\n", dir
->Name(),
389 dir
->BlockRun().allocation_group
,
390 dir
->BlockRun().start
, name
,
391 run
.allocation_group
, run
.start
, run
.length
);
394 if ((missing
= (Inode
*)gLogged
.Remove(&run
)) != NULL
) {
395 // missing inode is in the log
397 printf("found missing entry in log!\n");
398 if (missing
->InodeBuffer()->parent
!= dir
->BlockRun()) {
400 puts("\tparent directories differ (may be an old "
401 "version of it), reseting parent.");
402 missing
->SetParent(dir
->BlockRun());
404 if (!gMissing
.Insert(missing
))
406 } else if (!gMissingEmpty
.Contains(&run
)) {
407 // not known at all yet
408 Inode
*empty
= Inode::EmptyInode(&disk
, name
, 0);
410 empty
->SetBlockRun(run
);
411 empty
->SetParent(dir
->BlockRun());
413 printf("\tname = %s\n", empty
->Name());
415 if (!gMissingEmpty
.Insert(empty
))
425 checkStructure(Disk
&disk
)
430 RunSet::iterator iterator
= gMainInodes
.begin();
431 for (; iterator
!= gMainInodes
.end(); iterator
++) {
432 InodeGetter
getter(disk
, *iterator
);
433 node
= getter
.Node();
436 if ((count
% 50) == 0)
437 fprintf(stderr
, "%" B_PRIdOFF
" inodes processed...\33[1A\n", count
);
442 if (node
->IsDirectory() && !node
->IsIndex()) {
443 // check if all entries are in the hashtable
444 Directory
* directory
= dynamic_cast<Directory
*>(node
);
445 if (directory
!= NULL
)
446 checkDirectoryContents(disk
, directory
);
448 printf("Node \"%s\" at %" B_PRId32
449 ",%d looks like a directory, but isn't.\n",
450 node
->Name(), node
->BlockRun().allocation_group
,
451 node
->BlockRun().start
);
455 // check for the parent directory
457 block_run run
= node
->Parent();
458 InodeGetter
parentGetter(disk
, run
);
459 Inode
*parentNode
= parentGetter
.Node();
461 Directory
*dir
= dynamic_cast<Directory
*>(parentNode
);
462 if (dir
|| (parentNode
&& (node
->Mode() & S_ATTR_DIR
))) {
463 // entry has a valid parent directory, so it's assumed to be a valid entry
464 disk
.BlockBitmap()->BackupSet(node
, true);
465 } else if (node
->Mode() & S_ATTR
) {
467 printf("attribute \"%s\" at %" B_PRId32
",%d misses its parent.\n",
468 node
->Name(), node
->BlockRun().allocation_group
,
469 node
->BlockRun().start
);
470 puts("\thandling not yet implemented...");
472 } else /*if ((node->Flags() & INODE_DELETED) == 0)*/ {
473 Inode
* missing
= gMissing
.Get(run
);
474 dir
= dynamic_cast<Directory
*>(missing
);
476 if (missing
== NULL
) {
478 printf("%s \"%s\" (%" B_PRId32
", %d, mode = %10" B_PRIo32
479 "): parent directory is missing (%" B_PRId32
480 ", %d, %d), may be deleted!\n",
481 node
->IsFile() ? "file" : "node", node
->Name(),
482 node
->BlockRun().allocation_group
,
483 node
->BlockRun().start
,
484 node
->Mode(), run
.allocation_group
, run
.start
,
488 if ((dir
= dynamic_cast<Directory
*>((Inode
*)gLogged
.Remove(
491 printf("found directory \"%s\" in log:\n", dir
->Name());
493 dump_inode(dir
, dir
->InodeBuffer());
495 puts("\tempty inode.");
499 puts("\tcreate parent missing entry");
501 Inode
*nameNode
= (Inode
*)gMissingEmpty
.Remove(&run
);
502 if (nameNode
!= NULL
) {
503 nameNode
->SetMode(S_IFDIR
);
505 printf("found missing name!\n");
508 parentName
<< "__directory " << run
.allocation_group
509 << ":" << (int32
)run
.start
;
511 nameNode
= Inode::EmptyInode(&disk
, parentName
.String(),
514 nameNode
->SetBlockRun(run
);
515 nameNode
->SetParent(disk
.Root());
520 dir
= new Directory(*nameNode
);
521 if (dir
->CopyBuffer() < B_OK
)
522 puts("could not copy buffer!");
528 dir
->AcquireBuffer();
530 if (!gMissing
.Insert(dir
)) {
531 printf("could not add dir!!\n");
536 } else if (missing
!= NULL
&& dir
== NULL
&& gVerbose
) {
537 printf("%s \"%s\" (%" B_PRId32
", %d, mode = %10" B_PRIo32
538 "): parent directory found in missing list (%" B_PRId32
539 ", %d, %d), but it's not a dir!\n",
540 node
->IsFile() ? "file" : "node", node
->Name(),
541 node
->BlockRun().allocation_group
, node
->BlockRun().start
,
542 node
->Mode(), run
.allocation_group
, run
.start
, run
.length
);
543 } else if (gVerbose
) {
544 printf("%s \"%s\" (%" B_PRId32
", %d, mode = %10" B_PRIo32
545 "): parent directory found in missing list (%" B_PRId32
547 node
->IsFile() ? "file" : "node", node
->Name(),
548 node
->BlockRun().allocation_group
, node
->BlockRun().start
,
549 node
->Mode(), run
.allocation_group
, run
.start
, run
.length
);
554 dir
->ReleaseBuffer();
559 // printf("node %s\n", node->Name());
560 // status_t status = dir->Contains(node);
561 // if (status == B_ENTRY_NOT_FOUND)
562 // printf("node \"%s\": parent directory \"%s\" contains no link to this node!\n",node->Name(),dir->Name());
563 // else if (status != B_OK)
564 // printf("node \"%s\": parent directory \"%s\" error: %s\n",node->Name(),dir->Name(),strerror(status));
567 // check for attributes
569 run
= node
->Attributes();
571 //printf("node \"%s\" (%ld, %d, mode = %010lo): has attribute dir!\n",node->Name(),node->BlockRun().allocation_group,node->BlockRun().start,node->Mode());
573 if (gMainInodes
.find(run
) == gMainInodes
.end()) {
575 printf("node \"%s\": attributes are missing (%" B_PRId32
576 ", %d, %d)\n", node
->Name(), run
.allocation_group
,
577 run
.start
, run
.length
);
580 if ((dir
= (Directory
*)gMissing
.Get(run
)) != NULL
) {
582 puts("\tfound in missing");
583 dir
->SetMode(dir
->Mode() | S_ATTR_DIR
);
584 dir
->SetParent(node
->BlockRun());
587 puts("\tcreate new!");
589 Inode
*empty
= Inode::EmptyInode(&disk
, NULL
,
590 S_IFDIR
| S_ATTR_DIR
);
592 empty
->SetBlockRun(run
);
593 empty
->SetParent(node
->BlockRun());
595 dir
= new Directory(*empty
);
596 if (dir
->CopyBuffer() < B_OK
)
597 puts("could not copy buffer!");
601 if (!gMissing
.Insert(dir
)) {
602 puts("\tcould not add attribute dir");
610 printf("%" B_PRIdOFF
" inodes processed.\n", count
);
612 Directory
*directory
= getNameIndex(disk
);
613 if (directory
!= NULL
) {
614 puts("\n*** Search names of missing inodes in the name index");
617 if (directory
->GetTree(&tree
) == B_OK
&& tree
->Validate(gVerbose
) == B_OK
) {
618 char name
[B_FILE_NAME_LENGTH
];
621 while (directory
->GetNextEntry(name
, &run
) >= B_OK
) {
622 if ((node
= gMissing
.Get(run
)) == NULL
)
626 printf(" Node found: %" B_PRId32
":%d\n",
627 run
.allocation_group
, run
.start
);
629 if (node
->Name() == NULL
|| strcmp(node
->Name(), name
)) {
631 printf("\tnames differ: %s -> %s (indices)\n",
638 printf("\tname index is corrupt!\n");
640 directory
->ReleaseBuffer();
642 printf("*** Name index corrupt or not existent!\n");
647 if (!gMissing
.IsEmpty())
648 puts("\n*** Missing inodes:");
651 while (gMissing
.GetNextEntry(&node
) == B_OK
) {
652 if (gDumpMissingInodes
)
653 dump_inode(node
, node
->InodeBuffer());
655 Directory
*dir
= dynamic_cast<Directory
*>(node
);
657 printf("\ndirectory \"%s\" (%" B_PRId32
", %d) contents:\n",
658 node
->Name(), node
->BlockRun().allocation_group
,
659 node
->BlockRun().start
);
663 char name
[B_FILE_NAME_LENGTH
];
665 while (dir
->GetNextEntry(name
, &run
) == B_OK
) {
666 printf("\t\"%s\" (%" B_PRId32
", %d, %d)\n", name
,
667 run
.allocation_group
, run
.start
, run
.length
);
671 if (dir
->GetTree(&tree
) < B_OK
)
677 while (tree
->GetNextEntry(name
, &length
, B_FILE_NAME_LENGTH
,
681 run
= disk
.ToBlockRun(offset
);
682 printf("%s: block_run == (%5" B_PRId32
",%5d,%5d), \"%s\"\n",
683 dir
->Name(), run
.allocation_group
, run
.start
, run
.length
,
687 //tree->WriteTo(dir);
688 //disk.WriteAt(dir->Offset(),dir->InodeBuffer(),disk.BlockSize());
691 gMissing
.Release(node
);
697 copyInodes(Disk
& disk
, const char* copyTo
)
702 HashtableInodeSource
source(disk
);
707 RunSet::iterator iterator
= gMainInodes
.begin();
708 for (; iterator
!= gMainInodes
.end(); iterator
++) {
709 InodeGetter
getter(disk
, *iterator
);
710 Inode
* node
= getter
.Node();
712 if (node
&& !node
->IsIndex() && !node
->IsAttributeDirectory())
713 node
->CopyTo(copyTo
, true, &source
);
715 if ((++count
% 500) == 0)
716 fprintf(stderr
, "copied %" B_PRId32
" files...\n", count
);
720 while (gMissing
.GetNextEntry(&node
) == B_OK
) {
721 if (!node
->IsIndex() && !node
->IsAttributeDirectory())
722 node
->CopyTo(copyTo
, true, &source
);
724 gMissing
.Release(node
);
732 fprintf(stderr
,"usage: %s [-idv] [-r [start-offset] [end-offset]] <device> [recover-to-path]\n"
733 "\t-i\trecreate indices on target disk\n"
734 "\t-d\tdump missing and recreated i-nodes\n"
735 "\t-r\tdisk access in raw mode (use only if the partition table is invalid)\n"
736 "\t-s\trecreate superblock and exit (for experts only, don't use this\n"
737 "\t\tif you don't know what you're doing)\n"
738 "\t-v\tverbose output\n", name
);
744 main(int argc
, char **argv
)
746 char *fileName
= strrchr(argv
[0], '/');
747 fileName
= fileName
? fileName
+ 1 : argv
[0];
748 bool recreateSuperBlockOnly
= false;
750 off_t startOffset
= 0, endOffset
= -1;
752 puts("Copyright (c) 2001-2008 pinc Software.");
754 if (argc
< 2 || !strcmp(argv
[1], "--help"))
760 while (*++arg
&& isalpha(*arg
)) {
766 if (argv
[1] && isdigit((argv
[1])[0])) {
770 startOffset
= atoll(arg
);
772 if (argv
[1] && isdigit((argv
[1])[0])) {
776 endOffset
= atoll(arg
);
778 if (endOffset
!= -1 && endOffset
< startOffset
)
786 gCreateIndices
= true;
789 gDumpMissingInodes
= true;
792 recreateSuperBlockOnly
= true;
800 Disk
disk(argv
[0], gRawMode
, startOffset
, endOffset
);
801 if (disk
.InitCheck() < B_OK
) {
802 fprintf(stderr
,"Could not open device or file: %s\n",
803 strerror(disk
.InitCheck()));
807 if (argv
[1] != NULL
) {
808 dev_t device
= dev_for_path(argv
[1]);
810 if (fs_stat_dev(device
, &info
) == B_OK
) {
811 if (!strcmp(info
.device_name
, disk
.Path().Path())) {
812 fprintf(stderr
,"The source and target device are identical, "
813 "you currently need\n"
814 "to have another disk to recover to, sorry!\n");
817 if ((info
.flags
& (B_FS_IS_PERSISTENT
| B_FS_HAS_ATTR
))
818 != (B_FS_IS_PERSISTENT
| B_FS_HAS_ATTR
)) {
819 fprintf(stderr
, "%s: The target file system (%s) does not have "
821 "\tfunctionality in order to restore all information.\n",
822 kProgramName
, info
.fsh_name
);
828 bool recreatedSuperBlock
= false;
830 if (disk
.ValidateSuperBlock() < B_OK
) {
831 fprintf(stderr
, "The disk's superblock is corrupt!\n");
832 if (disk
.RecreateSuperBlock() < B_OK
) {
833 fprintf(stderr
, "Can't recreate the disk's superblock, sorry!\n");
836 recreatedSuperBlock
= true;
839 puts("\n*** The superblock:\n");
840 dump_super_block(disk
.SuperBlock());
843 if (recreateSuperBlockOnly
) {
844 if (!recreatedSuperBlock
) {
845 printf("Superblock was valid, no changes made.\n");
849 status_t status
= disk
.WriteAt(512, disk
.SuperBlock(),
850 sizeof(disk_super_block
));
852 fprintf(stderr
, "Could not write superblock: %s!\n",
859 puts("\n*** Collecting inodes...");
861 collectLogInodes(disk
);
862 collectRealInodes(disk
);
864 puts("\n*** Checking Disk Structure Integrity...");
866 checkStructure(disk
);
869 copyInodes(disk
, argv
[1]);
871 //disk.WriteBootBlock();
872 //disk.BlockBitmap()->CompareWithBackup();
874 gMissing
.MakeEmpty();