#include <set>
#include "Disk.h"
#include "Inode.h"
#include "Hashtable.h"
#include "BPlusTree.h"
#include "dump.h"
#include <String.h>
#include <fs_info.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <ctype.h>
extern const char *__progname;
static const char *kProgramName = __progname;
bool gCreateIndices = false;
bool gDumpMissingInodes = false;
bool gRawMode = false;
bool gVerbose = false;
typedef std::set<block_run> RunSet;
class InodeHashtable {
public:
InodeHashtable(int capacity)
:
fHashtable(capacity),
fLastChecked(0)
{
fHashtable.SetHashFunction((uint32 (*)(const void *))BlockRunHash);
fHashtable.SetCompareFunction((bool (*)(const void *, const void *))
BlockRunCompare);
}
Inode* Acquire(Inode* inode)
{
if (inode == NULL)
return NULL;
status_t status = inode->AcquireBuffer();
if (status != B_OK) {
fprintf(stderr, "Could not retrieve buffer for inode %"
B_PRIdOFF ": %s\n", inode->Offset(), strerror(status));
return NULL;
}
return inode;
}
void Release(Inode* inode)
{
inode->ReleaseBuffer();
}
Inode* Get(block_run run)
{
return Acquire((Inode *)fHashtable.GetValue(&run));
}
bool Insert(Inode* inode)
{
bool success = fHashtable.Put(&inode->BlockRun(), inode);
if (success)
inode->ReleaseBuffer();
return success;
}
bool Contains(block_run *key)
{
return fHashtable.ContainsKey(key);
}
Inode* Remove(block_run *key)
{
return Acquire((Inode*)fHashtable.Remove(key));
}
status_t GetNextEntry(Inode **_inode)
{
status_t status = fHashtable.GetNextEntry((void**)_inode);
if (status == B_OK) {
if (Acquire(*_inode) == NULL)
return B_NO_MEMORY;
}
return status;
}
void Rewind()
{
fHashtable.Rewind();
}
bool IsEmpty() const
{
return fHashtable.IsEmpty();
}
void MakeEmpty()
{
fHashtable.MakeEmpty(HASH_EMPTY_NONE, HASH_EMPTY_DELETE);
}
static uint32 BlockRunHash(const block_run *run)
{
return (run->allocation_group << 16) | run->start;
}
static bool BlockRunCompare(const block_run *runA, const block_run *runB)
{
return *runA == *runB;
}
private:
Hashtable fHashtable;
bigtime_t fLastChecked;
uint32 fPercentUsed;
};
class InodeGetter {
public:
InodeGetter(Disk& disk, block_run run)
{
fInode = Inode::Factory(&disk, run);
if (fInode != NULL)
fInode->AcquireBuffer();
}
~InodeGetter()
{
if (fInode != NULL)
fInode->ReleaseBuffer();
}
Inode* Node() const
{
return fInode;
}
void Detach()
{
fInode = NULL;
}
private:
Inode* fInode;
};
RunSet gMainInodes;
InodeHashtable gLogged(50);
InodeHashtable gMissing(50);
InodeHashtable gMissingEmpty(25);
class HashtableInodeSource : public Inode::Source {
public:
HashtableInodeSource(Disk& disk)
:
fDisk(disk)
{
}
virtual Inode *InodeAt(block_run run)
{
Inode *inode;
if ((inode = gLogged.Get(run)) != NULL)
return Inode::Factory(&fDisk, inode, false);
if ((inode = gMissing.Get(run)) != NULL)
return Inode::Factory(&fDisk, inode, false);
if (gMainInodes.find(run) == gMainInodes.end())
return NULL;
return Inode::Factory(&fDisk, run);
}
private:
Disk& fDisk;
};
bool
operator<(const block_run& a, const block_run& b)
{
return a.allocation_group < b.allocation_group
|| (a.allocation_group == b.allocation_group && a.start < b.start);
}
void
collectInodes(Disk& disk, RunSet* set, InodeHashtable* hashTable, off_t start,
off_t end)
{
char buffer[8192];
Inode inode(&disk, (bfs_inode *)buffer, false);
off_t directories = 0LL;
off_t directorySize = 0LL;
off_t files = 0LL;
off_t fileSize = 0LL;
off_t symlinks = 0LL;
off_t count = 0LL;
off_t position = start;
bigtime_t lastUpdate = system_time();
for (off_t offset = start; offset < end; offset += sizeof(buffer)) {
if (disk.ReadAt(offset, buffer, sizeof(buffer)) < B_OK) {
fprintf(stderr, "could not read from device!\n");
break;
}
for (uint32 i = 0; i < sizeof(buffer); i += disk.BlockSize()) {
inode.SetTo((bfs_inode *)(buffer + i));
if (inode.InitCheck() == B_OK) {
if (inode.Flags() & INODE_DELETED)
continue;
Inode *node = Inode::Factory(&disk, &inode);
if (node != NULL) {
if (gVerbose)
printf(" node: %" B_PRIdOFF " \"%s\"\n", position,
node->Name());
if (set != NULL)
set->insert(node->BlockRun());
else
hashTable->Insert(node);
if (node->IsDirectory()) {
directories++;
directorySize += node->Size();
} else if (node->IsFile()) {
files++;
fileSize += node->Size();
} else if (node->IsSymlink()) {
symlinks++;
}
count++;
} else if (gVerbose) {
printf("\nunrecognized inode:");
dump_inode(&inode, inode.InodeBuffer());
}
}
position += disk.BlockSize();
}
if (system_time() - lastUpdate > 500000) {
printf(" block %" B_PRIdOFF " (%" B_PRIdOFF "%%), %" B_PRIdOFF
" inodes\33[1A\n", offset,
100 * (offset - start) / (end - start), count);
lastUpdate = system_time();
}
}
printf("\n%" B_PRIdOFF " inodes found.\n", count);
printf("\n%20" B_PRIdOFF " directories found (total of %" B_PRIdOFF
" bytes)\n%20" B_PRIdOFF " files found (total of %" B_PRIdOFF
" bytes)\n%20" B_PRIdOFF " symlinks found\n"
"--------------------\n"
"%20" B_PRIdOFF " inodes total found.\n",
directories, directorySize, files, fileSize, symlinks, count);
}
void
collectLogInodes(Disk &disk)
{
off_t offset = disk.ToOffset(disk.Log());
off_t end = offset + (disk.Log().length << disk.BlockShift());
printf("\nsearching from %" B_PRIdOFF " to %" B_PRIdOFF " (log area)\n",
offset, end);
collectInodes(disk, NULL, &gLogged, offset, end);
}
void
collectRealInodes(Disk &disk)
{
off_t offset = disk.ToOffset(disk.Log()) + (disk.Log().length
<< disk.BlockShift());
off_t end = (off_t)disk.NumBlocks() << disk.BlockShift();
printf("\nsearching from %" B_PRIdOFF " to %" B_PRIdOFF " (main area)\n",
offset, end);
collectInodes(disk, &gMainInodes, NULL, offset, end);
}
Directory *
getNameIndex(Disk &disk)
{
InodeGetter getter(disk, disk.Indices());
Directory *indices = dynamic_cast<Directory *>(getter.Node());
block_run run;
if (indices != NULL && indices->FindEntry("name", &run) == B_OK) {
InodeGetter getter(disk, run);
Inode* node = getter.Node();
getter.Detach();
return dynamic_cast<Directory *>(node);
}
RunSet::iterator iterator = gMainInodes.begin();
for (; iterator != gMainInodes.end(); iterator++) {
InodeGetter getter(disk, *iterator);
Inode* node = getter.Node();
if (!node || !node->IsIndex() || node->Name() == NULL)
continue;
if (!strcmp(node->Name(), "name") && node->Mode() & BFS_S_STR_INDEX)
return dynamic_cast<Directory *>(node);
}
return NULL;
}
void
checkDirectoryContents(Disk& disk, Directory *dir)
{
dir->Rewind();
char name[B_FILE_NAME_LENGTH];
block_run run;
while (dir->GetNextEntry(name, &run) == B_OK) {
if (run == dir->BlockRun() || run == dir->Parent()
|| gMainInodes.find(run) != gMainInodes.end())
continue;
Inode *missing = gMissing.Get(run);
if (missing != NULL) {
if (missing->SetName(name) < B_OK) {
fprintf(stderr, "setting name of missing node to "
"\"%s\" failed!", name);
}
if (gVerbose) {
printf("Set name of missing node (%" B_PRId32
", %d) to \"%s\" (%s)\n",
run.allocation_group, run.start, missing->Name(), name);
}
missing->SetParent(dir->BlockRun());
}
else {
if (gVerbose) {
printf("directory \"%s\" (%" B_PRId32 ", %d): node \"%s\" is "
"missing (%" B_PRId32 ", %d, %d)\n", dir->Name(),
dir->BlockRun().allocation_group,
dir->BlockRun().start, name,
run.allocation_group, run.start, run.length);
}
if ((missing = (Inode *)gLogged.Remove(&run)) != NULL) {
if (gVerbose)
printf("found missing entry in log!\n");
if (missing->InodeBuffer()->parent != dir->BlockRun()) {
if (gVerbose)
puts("\tparent directories differ (may be an old "
"version of it), reseting parent.");
missing->SetParent(dir->BlockRun());
}
if (!gMissing.Insert(missing))
delete missing;
} else if (!gMissingEmpty.Contains(&run)) {
Inode *empty = Inode::EmptyInode(&disk, name, 0);
if (empty) {
empty->SetBlockRun(run);
empty->SetParent(dir->BlockRun());
if (gVerbose)
printf("\tname = %s\n", empty->Name());
if (!gMissingEmpty.Insert(empty))
delete empty;
}
}
}
}
}
void
checkStructure(Disk &disk)
{
off_t count = 0;
Inode* node;
RunSet::iterator iterator = gMainInodes.begin();
for (; iterator != gMainInodes.end(); iterator++) {
InodeGetter getter(disk, *iterator);
node = getter.Node();
count++;
if ((count % 50) == 0)
fprintf(stderr, "%" B_PRIdOFF " inodes processed...\33[1A\n", count);
if (node == NULL)
continue;
if (node->IsDirectory() && !node->IsIndex()) {
Directory* directory = dynamic_cast<Directory*>(node);
if (directory != NULL)
checkDirectoryContents(disk, directory);
else {
printf("Node \"%s\" at %" B_PRId32
",%d looks like a directory, but isn't.\n",
node->Name(), node->BlockRun().allocation_group,
node->BlockRun().start);
}
}
block_run run = node->Parent();
InodeGetter parentGetter(disk, run);
Inode *parentNode = parentGetter.Node();
Directory *dir = dynamic_cast<Directory *>(parentNode);
if (dir || (parentNode && (node->Mode() & BFS_S_ATTR_DIR))) {
disk.BlockBitmap()->BackupSet(node, true);
} else if (node->Mode() & BFS_S_ATTR) {
if (gVerbose) {
printf("attribute \"%s\" at %" B_PRId32 ",%d misses its parent.\n",
node->Name(), node->BlockRun().allocation_group,
node->BlockRun().start);
puts("\thandling not yet implemented...");
}
} else {
Inode* missing = gMissing.Get(run);
dir = dynamic_cast<Directory *>(missing);
if (missing == NULL) {
if (gVerbose) {
printf("%s \"%s\" (%" B_PRId32 ", %d, mode = %10" B_PRIo32
"): parent directory is missing (%" B_PRId32
", %d, %d), may be deleted!\n",
node->IsFile() ? "file" : "node", node->Name(),
node->BlockRun().allocation_group,
node->BlockRun().start,
node->Mode(), run.allocation_group, run.start,
run.length);
}
if ((dir = dynamic_cast<Directory *>((Inode *)gLogged.Remove(
&run))) != NULL) {
if (gVerbose) {
printf("found directory \"%s\" in log:\n", dir->Name());
if (dir->Size() > 0)
dump_inode(dir, dir->InodeBuffer());
else
puts("\tempty inode.");
}
} else {
if (gVerbose)
puts("\tcreate parent missing entry");
Inode *nameNode = (Inode *)gMissingEmpty.Remove(&run);
if (nameNode != NULL) {
nameNode->SetMode(BFS_S_IFDIR);
if (gVerbose)
printf("found missing name!\n");
} else {
BString parentName;
parentName << "__directory " << run.allocation_group
<< ":" << (int32)run.start;
nameNode = Inode::EmptyInode(&disk, parentName.String(),
BFS_S_IFDIR);
if (nameNode) {
nameNode->SetBlockRun(run);
nameNode->SetParent(disk.Root());
}
}
if (nameNode) {
dir = new Directory(*nameNode);
if (dir->CopyBuffer() < B_OK)
puts("could not copy buffer!");
else
delete nameNode;
}
}
if (dir) {
dir->AcquireBuffer();
if (!gMissing.Insert(dir)) {
printf("could not add dir!!\n");
delete dir;
dir = NULL;
}
}
} else if (missing != NULL && dir == NULL && gVerbose) {
printf("%s \"%s\" (%" B_PRId32 ", %d, mode = %10" B_PRIo32
"): parent directory found in missing list (%" B_PRId32
", %d, %d), but it's not a dir!\n",
node->IsFile() ? "file" : "node", node->Name(),
node->BlockRun().allocation_group, node->BlockRun().start,
node->Mode(), run.allocation_group, run.start, run.length);
} else if (gVerbose) {
printf("%s \"%s\" (%" B_PRId32 ", %d, mode = %10" B_PRIo32
"): parent directory found in missing list (%" B_PRId32
", %d, %d)!\n",
node->IsFile() ? "file" : "node", node->Name(),
node->BlockRun().allocation_group, node->BlockRun().start,
node->Mode(), run.allocation_group, run.start, run.length);
}
if (dir) {
dir->AddEntry(node);
dir->ReleaseBuffer();
}
}
run = node->Attributes();
if (!run.IsZero()) {
if (gMainInodes.find(run) == gMainInodes.end()) {
if (gVerbose) {
printf("node \"%s\": attributes are missing (%" B_PRId32
", %d, %d)\n", node->Name(), run.allocation_group,
run.start, run.length);
}
if ((dir = (Directory *)gMissing.Get(run)) != NULL) {
if (gVerbose)
puts("\tfound in missing");
dir->SetMode(dir->Mode() | BFS_S_ATTR_DIR);
dir->SetParent(node->BlockRun());
} else {
if (gVerbose)
puts("\tcreate new!");
Inode *empty = Inode::EmptyInode(&disk, NULL,
BFS_S_IFDIR | BFS_S_ATTR_DIR);
if (empty) {
empty->SetBlockRun(run);
empty->SetParent(node->BlockRun());
dir = new Directory(*empty);
if (dir->CopyBuffer() < B_OK)
puts("could not copy buffer!");
else
delete empty;
if (!gMissing.Insert(dir)) {
puts("\tcould not add attribute dir");
delete dir;
}
}
}
}
}
}
printf("%" B_PRIdOFF " inodes processed.\n", count);
Directory *directory = getNameIndex(disk);
if (directory != NULL) {
puts("\n*** Search names of missing inodes in the name index");
BPlusTree *tree;
if (directory->GetTree(&tree) == B_OK && tree->Validate(gVerbose) == B_OK) {
char name[B_FILE_NAME_LENGTH];
block_run run;
directory->Rewind();
while (directory->GetNextEntry(name, &run) >= B_OK) {
if ((node = gMissing.Get(run)) == NULL)
continue;
if (gVerbose) {
printf(" Node found: %" B_PRId32 ":%d\n",
run.allocation_group, run.start);
}
if (node->Name() == NULL || strcmp(node->Name(), name)) {
if (gVerbose) {
printf("\tnames differ: %s -> %s (indices)\n",
node->Name(), name);
}
node->SetName(name);
}
}
} else
printf("\tname index is corrupt!\n");
directory->ReleaseBuffer();
} else
printf("*** Name index corrupt or not existent!\n");
if (!gVerbose)
return;
if (!gMissing.IsEmpty())
puts("\n*** Missing inodes:");
gMissing.Rewind();
while (gMissing.GetNextEntry(&node) == B_OK) {
if (gDumpMissingInodes)
dump_inode(node, node->InodeBuffer());
Directory *dir = dynamic_cast<Directory *>(node);
if (dir) {
printf("\ndirectory \"%s\" (%" B_PRId32 ", %d) contents:\n",
node->Name(), node->BlockRun().allocation_group,
node->BlockRun().start);
dir->Rewind();
char name[B_FILE_NAME_LENGTH];
block_run run;
while (dir->GetNextEntry(name, &run) == B_OK) {
printf("\t\"%s\" (%" B_PRId32 ", %d, %d)\n", name,
run.allocation_group, run.start, run.length);
}
BPlusTree *tree;
if (dir->GetTree(&tree) < B_OK)
continue;
uint16 length;
off_t offset;
while (tree->GetNextEntry(name, &length, B_FILE_NAME_LENGTH,
&offset) == B_OK) {
name[length] = 0;
run = disk.ToBlockRun(offset);
printf("%s: block_run == (%5" B_PRId32 ",%5d,%5d), \"%s\"\n",
dir->Name(), run.allocation_group, run.start, run.length,
name);
}
}
gMissing.Release(node);
}
}
void
copyInodes(Disk& disk, const char* copyTo)
{
if (copyTo == NULL)
return;
HashtableInodeSource source(disk);
Inode *node;
int32 count = 0;
RunSet::iterator iterator = gMainInodes.begin();
for (; iterator != gMainInodes.end(); iterator++) {
InodeGetter getter(disk, *iterator);
Inode* node = getter.Node();
if (node && !node->IsIndex() && !node->IsAttributeDirectory())
node->CopyTo(copyTo, true, &source);
if ((++count % 500) == 0)
fprintf(stderr, "copied %" B_PRId32 " files...\n", count);
}
gMissing.Rewind();
while (gMissing.GetNextEntry(&node) == B_OK) {
if (!node->IsIndex() && !node->IsAttributeDirectory())
node->CopyTo(copyTo, true, &source);
gMissing.Release(node);
}
}
void
usage(char *name)
{
fprintf(stderr,"usage: %s [-idv] [-r [start-offset] [end-offset]] <device> [recover-to-path]\n"
"\t-i\trecreate indices on target disk\n"
"\t-d\tdump missing and recreated i-nodes\n"
"\t-r\tdisk access in raw mode (use only if the partition table is invalid)\n"
"\t-s\trecreate superblock and exit (for experts only, don't use this\n"
"\t\tif you don't know what you're doing)\n"
"\t-v\tverbose output\n", name);
exit(-1);
}
int
main(int argc, char **argv)
{
char *fileName = strrchr(argv[0], '/');
fileName = fileName ? fileName + 1 : argv[0];
bool recreateSuperBlockOnly = false;
off_t startOffset = 0, endOffset = -1;
puts("Copyright (c) 2001-2008 pinc Software.");
if (argc < 2 || !strcmp(argv[1], "--help"))
usage(fileName);
while (*++argv) {
char *arg = *argv;
if (*arg == '-') {
while (*++arg && isalpha(*arg)) {
switch (arg[0]) {
case 'r':
{
gRawMode = true;
if (argv[1] && isdigit((argv[1])[0])) {
argv++;
arg = *argv;
startOffset = atoll(arg);
}
if (argv[1] && isdigit((argv[1])[0])) {
argv++;
arg = *argv;
endOffset = atoll(arg);
}
if (endOffset != -1 && endOffset < startOffset)
usage(fileName);
break;
}
case 'v':
gVerbose = true;
break;
case 'i':
gCreateIndices = true;
break;
case 'd':
gDumpMissingInodes = true;
break;
case 's':
recreateSuperBlockOnly = true;
break;
}
}
} else
break;
}
Disk disk(argv[0], gRawMode, startOffset, endOffset);
if (disk.InitCheck() < B_OK) {
fprintf(stderr,"Could not open device or file: %s\n",
strerror(disk.InitCheck()));
return -1;
}
#ifdef __HAIKU__
if (argv[1] != NULL) {
dev_t device = dev_for_path(argv[1]);
fs_info info;
if (fs_stat_dev(device, &info) == B_OK) {
if (!strcmp(info.device_name, disk.Path().Path())) {
fprintf(stderr,"The source and target device are identical, "
"you currently need\n"
"to have another disk to recover to, sorry!\n");
return -1;
}
if ((info.flags & (B_FS_IS_PERSISTENT | B_FS_HAS_ATTR))
!= (B_FS_IS_PERSISTENT | B_FS_HAS_ATTR)) {
fprintf(stderr, "%s: The target file system (%s) does not have "
"the required\n"
"\tfunctionality in order to restore all information.\n",
kProgramName, info.fsh_name);
return -1;
}
}
}
#endif
bool recreatedSuperBlock = false;
if (disk.ValidateSuperBlock() < B_OK) {
fprintf(stderr, "The disk's superblock is corrupt!\n");
if (disk.RecreateSuperBlock() < B_OK) {
fprintf(stderr, "Can't recreate the disk's superblock, sorry!\n");
return -1;
}
recreatedSuperBlock = true;
}
if (gVerbose) {
puts("\n*** The superblock:\n");
dump_super_block(disk.SuperBlock());
}
if (recreateSuperBlockOnly) {
if (!recreatedSuperBlock) {
printf("Superblock was valid, no changes made.\n");
return 0;
}
status_t status = disk.WriteAt(512, disk.SuperBlock(),
sizeof(disk_super_block));
if (status < B_OK) {
fprintf(stderr, "Could not write superblock: %s!\n",
strerror(status));
return 1;
}
return 0;
}
puts("\n*** Collecting inodes...");
collectLogInodes(disk);
collectRealInodes(disk);
puts("\n*** Checking Disk Structure Integrity...");
checkStructure(disk);
if (argv[1])
copyInodes(disk, argv[1]);
gMissing.MakeEmpty();
gLogged.MakeEmpty();
return 0;
}
