haiku.git

/*
 * Copyright (c) 2001-2008 pinc Software. All Rights Reserved.
 * Released under the terms of the MIT license.
 */

//!	sanity and completeness check for indices

#include "Disk.h"
#include "Inode.h"
#include "Hashtable.h"
#include "BPlusTree.h"
#include "dump.h"

#include <fs_info.h>

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <ctype.h>
#include <errno.h>


char gEscape[3] = {0x1b, '[', 0};
off_t gCount = 1;
bool gDoNotCheckForFiles = false;
bool gDoNotCheckIndex = false;
bool gCheckAll = false;


// we just want to know which inodes exist, so don't remember anything
// along the position of the inode.

class BlockRunHashtable : public Hashtable
{
	public:
		BlockRunHashtable(int capacity)
			: Hashtable(capacity)
		{
			SetHashFunction((uint32 (*)(const void *))BlockRunHash);
			SetCompareFunction((bool (*)(const void *, const void *))BlockRunCompare);
		}

		bool Contains(block_run *run)
		{
			return ContainsKey((void *)run);
		}

		bool Put(block_run &run)
		{
			block_run *value = (block_run *)malloc(sizeof(block_run));
			if (!value)
				return false;

			memcpy(value,&run,sizeof(block_run));

			if (Hashtable::Put(value,value))
				return true;

			free(value);
			return false;
		}

		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;
		}
};


BlockRunHashtable gHashtable(1000);


int
compareBlockRuns(const block_run *a, const block_run *b)
{
	int cmp = (int)a->allocation_group - (int)b->allocation_group;
	if (cmp == 0)
		cmp = (int)a->start - (int)b->start;
	return cmp;
}


void
collectFiles(Disk &disk,Directory *directory)
{
	if (directory == NULL)
		return;

	directory->Rewind();
	char name[B_FILE_NAME_LENGTH];
	block_run run;
	while (directory->GetNextEntry(name,&run) >= B_OK)
	{
		if (!strcmp(name,".") || !strcmp(name,".."))
			continue;

		gHashtable.Put(run);

		if (++gCount % 50 == 0)
			printf("  %7Ld%s1A\n",gCount,gEscape);

		Inode *inode = Inode::Factory(&disk,run);
		if (inode != NULL)
		{
			if (inode->IsDirectory())
				collectFiles(disk,static_cast<Directory *>(inode));

			delete inode;
		}
		else
			printf("  Directory \"%s\" (%ld, %d) points to corrupt inode \"%s\" (%ld, %d)\n",
				directory->Name(),directory->BlockRun().allocation_group,directory->BlockRun().start,
				name,run.allocation_group,run.start);
	}
}


void
collectFiles(Disk &disk)
{
	Directory *root = (Directory *)Inode::Factory(&disk,disk.Root());

	puts("Collecting files (this will take some time)...");

	if (root == NULL || root->InitCheck() < B_OK)
	{
		fprintf(stderr,"  Could not open root directory!\n");
		return;
	}
	collectFiles(disk,root);

	printf("  %7Ld files found.\n",gCount);

	delete root;
}


void
checkIndexForNonExistingFiles(Disk &disk,BPlusTree &tree)
{
	char name[B_FILE_NAME_LENGTH];
	uint16 length;
	off_t offset;

	while (tree.GetNextEntry(name,&length,B_FILE_NAME_LENGTH,&offset) == B_OK)
	{
		name[length] = 0;
		block_run run = disk.ToBlockRun(offset);
		if (!gHashtable.Contains(&run))
		{
			printf("  inode at (%ld, %d), offset %lld, doesn't exist!",run.allocation_group,run.start,offset);
			switch (tree.Type())
			{
				case BPLUSTREE_STRING_TYPE:
					printf(" (string = \"%s\")",name);
					break;
				case BPLUSTREE_INT32_TYPE:
					printf(" (int32 = %ld)",*(int32 *)&name);
					break;
				case BPLUSTREE_UINT32_TYPE:
					printf(" (uint32 = %lu)",*(uint32 *)&name);
					break;
				case BPLUSTREE_INT64_TYPE:
					printf(" (int64 = %lld)",*(int64 *)&name);
					break;
				case BPLUSTREE_UINT64_TYPE:
					printf(" (uint64 = %Lu)",*(uint64 *)&name);
					break;
				case BPLUSTREE_FLOAT_TYPE:
					printf(" (float = %g)",*(float *)&name);
					break;
				case BPLUSTREE_DOUBLE_TYPE:
					printf(" (double = %g)",*(double *)&name);
					break;
			}
			putchar('\n');
		}
	}
}


void
checkFiles(Disk &disk,BPlusTree &tree,char *attribute)
{
	block_run *runs = (block_run *)malloc(gCount * sizeof(block_run));
	if (runs == NULL)
	{
		fprintf(stderr,"  Not enough memory!\n");
		return;
	}
	// copy hashtable to array
	block_run *run = NULL;
	int32 index = 0;
	gHashtable.Rewind();
	while (gHashtable.GetNextEntry((void **)&run) == B_OK)
	{
		runs[index++] = *run;
	}

	// sort array to speed up disk access
	qsort(runs,index,sizeof(block_run),(int (*)(const void *,const void *))compareBlockRuns);

	bool sizeIndex = !strcmp(attribute,"size");
	bool nameIndex = !strcmp(attribute,"name");
	bool modifiedIndex = !strcmp(attribute,"last_modified");

	char key[B_FILE_NAME_LENGTH];
	uint16 keyLength = 0;

	Inode *inode = NULL;

	for (int32 i = 0;i < index;i++)
	{
		if (i % 50 == 0)
			printf("  %7ld%s1A\n",i,gEscape);

		delete inode;
		inode = Inode::Factory(&disk,runs[i]);
		if (inode == NULL || inode->InitCheck() < B_OK)
		{
			fprintf(stderr,"  inode at (%ld, %d) is corrupt!\n",runs[i].allocation_group,runs[i].start);
			delete inode;
			continue;
		}

		// check indices not based on standard attributes
		if (sizeIndex)
		{
			if (inode->IsDirectory())
				continue;

			memcpy(key,&inode->InodeBuffer()->data.size,sizeof(off_t));
			keyLength = sizeof(off_t);
		}
		else if (nameIndex)
		{
			strcpy(key,inode->Name());
			keyLength = strlen(key);
		}
		else if (modifiedIndex)
		{
			if (inode->IsDirectory())
				continue;

			memcpy(key,&inode->InodeBuffer()->last_modified_time,sizeof(off_t));
			keyLength = sizeof(off_t);
		}
		else	// iterate through all attributes to find the right one (damn slow, sorry...)
		{
			inode->RewindAttributes();
			char name[B_FILE_NAME_LENGTH];
			uint32 type;
			void *data;
			size_t length;
			bool found = false;
			while (inode->GetNextAttribute(name,&type,&data,&length) == B_OK)
			{
				if (!strcmp(name,attribute))
				{
					strncpy(key,(char *)data,B_FILE_NAME_LENGTH - 1);
					key[B_FILE_NAME_LENGTH - 1] = '\0';
					keyLength = length > B_FILE_NAME_LENGTH ? B_FILE_NAME_LENGTH : length;
					found = true;
					break;
				}
			}
			if (!found)
				continue;
		}

		off_t value;
		if (tree.Find((uint8 *)key,keyLength,&value) < B_OK)
		{
			if (*inode->Name())
				fprintf(stderr,"  inode at (%ld, %d) name \"%s\" is not in index!\n",runs[i].allocation_group,runs[i].start,inode->Name());
			else
			{
				// inode is obviously deleted!
				block_run parent = inode->Parent();
				Directory *directory = (Directory *)Inode::Factory(&disk,parent);
				if (directory != NULL && directory->InitCheck() == B_OK)
				{
					BPlusTree *parentTree;
					if (directory->GetTree(&parentTree) == B_OK)
					{
						char name[B_FILE_NAME_LENGTH];
						uint16 length;
						off_t offset,searchOffset = disk.ToBlock(runs[i]);
						bool found = false;

						while (parentTree->GetNextEntry(name,&length,B_FILE_NAME_LENGTH,&offset) == B_OK)
						{
							if (offset == searchOffset)
							{
								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());
								found = true;
								break;
							}
						}
						if (!found)
							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());
					}
					else
						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());
				}
				else
				{
					// not that this would be really possible... - but who knows
					fprintf(stderr,"  inode at (%ld, %d) is not in index and has invalid parent!\n",runs[i].allocation_group,runs[i].start);
				}
				delete directory;
			}
		}
		else
		{
			if (bplustree_node::LinkType(value) == BPLUSTREE_NODE)
			{
				if (disk.ToBlockRun(value) != runs[i])
					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);
			}
			else
			{
				// search duplicates
				char name[B_FILE_NAME_LENGTH];
				uint16 length;
				off_t offset;
				bool found = false,duplicates = false;
//puts("++");
				tree.Rewind();
				while (tree.GetNextEntry(name,&length,B_FILE_NAME_LENGTH,&offset) == B_OK)
				{
					//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);
					if (keyLength == length && !memcmp(key,name,keyLength))
					{
						duplicates = true;
						if (disk.ToBlockRun(offset) == runs[i])
						{
							found = true;
							break;
						}
					}
					//else if (duplicates)
					//	break;
				}
				if (!found)
				{
					printf("  inode \"%s\" at (%ld, %d) not found in duplicates!\n",inode->Name(),runs[i].allocation_group,runs[i].start);
//					return;
				}
			}
		}
	}
	delete inode;
	printf("  %7Ld files processed.\n",gCount);
}


int
checkIndex(Disk &disk,char *attribute,block_run &run,bool collect)
{
	Directory *index = (Directory *)Inode::Factory(&disk,run);
	status_t status;
	if (index == NULL || (status = index->InitCheck()) < B_OK)
	{
		fprintf(stderr,"  Could not get index directory for \"%s\": %s!\n",attribute,index ? strerror(status) : "not found/corrupted");
		return -1;
	}

	printf("\nCheck \"%s\" index's on-disk structure...\n",attribute);
	//dump_inode(index->InodeBuffer());

	BPlusTree *tree;
	if (index->GetTree(&tree) < B_OK || tree->Validate(true) < B_OK)
	{
		fprintf(stderr,"  B+Tree of index \"%s\" seems to be corrupt!\n",attribute);
		//return -1;
	}

	if (collect && (!gDoNotCheckIndex || !gDoNotCheckForFiles))
		collectFiles(disk);

	if (!gDoNotCheckIndex)
	{
		printf("Check for non-existing files in index \"%s\"...\n",attribute);
		checkIndexForNonExistingFiles(disk,*tree);
	}

	if (!gDoNotCheckForFiles)
	{
		printf("Check for files not in index \"%s\" (this may take even more time)...\n",attribute);
		checkFiles(disk,*tree,attribute);
	}
	return 0;
}


void
printUsage(char *tool)
{
	char *filename = strrchr(tool,'/');
	fprintf(stderr,"usage: %s [-ifa] index-name\n"
			"\t-i\tdo not check for non-existing files in the index\n"
			"\t-f\tdo not check if all the files are in the index\n"
			"\t-a\tcheck all indices (could take some weeks...)\n"
			,filename ? filename + 1 : tool);
}


int
main(int argc,char **argv)
{
	puts("Copyright (c) 2001-2008 pinc Software.");

	char *toolName = argv[0];
	if (argc < 2 || !strcmp(argv[1],"--help"))
	{
		printUsage(toolName);
		return -1;
	}

	while (*++argv)
	{
		char *arg = *argv;
		if (*arg == '-')
		{
			while (*++arg && isalpha(*arg))
			{
				switch (*arg)
				{
					case 'i':
						gDoNotCheckIndex = true;
						break;
					case 'f':
						gDoNotCheckForFiles = true;
						break;
					case 'a':
						gCheckAll = true;
						break;
				}
			}
		}
		else
			break;
	}

	char *attribute = argv[0];
	if (!gCheckAll && attribute == NULL)
	{
		printUsage(toolName);
		return -1;
	}

	dev_t device = dev_for_path(".");
	if (device < B_OK)
	{
		fprintf(stderr,"Could not find device for current location: %s\n",strerror(device));
		return -1;
	}

	fs_info info;
	if (fs_stat_dev(device,&info) < B_OK)
	{
		fprintf(stderr,"Could not get stats for device: %s\n",strerror(errno));
		return -1;
	}

	Disk disk(info.device_name);
	status_t status;
	if ((status = disk.InitCheck()) < B_OK)
	{
		fprintf(stderr,"Could not open device or file \"%s\": %s\n",info.device_name,strerror(status));
		return -1;
	}

	if (disk.ValidateSuperBlock() < B_OK)
	{
		fprintf(stderr,"The disk's superblock is corrupt!\n");
		return -1;
	}

	Directory *indices = (Directory *)Inode::Factory(&disk,disk.Indices());
	if (indices == NULL || (status = indices->InitCheck()) < B_OK)
	{
		fprintf(stderr,"  Could not get indices directory: %s!\n",indices ? strerror(status) : "not found/corrupted");
		delete indices;
		return -1;
	}
	BPlusTree *tree;
	if (indices->GetTree(&tree) < B_OK || tree->Validate() < B_OK)
	{
		fprintf(stderr,"  Indices B+Tree seems to be corrupt!\n");
		delete indices;
		return -1;
	}

	block_run run;

	if (gCheckAll)
	{
		putchar('\n');
		collectFiles(disk);

		char name[B_FILE_NAME_LENGTH];
		while (indices->GetNextEntry(name,&run) >= B_OK)
			checkIndex(disk,name,run,false);
	}
	else if (indices->FindEntry(attribute,&run) == B_OK)
		checkIndex(disk,attribute,run,true);
	else
		fprintf(stderr,"  Could not find index directory for \"%s\"!\n",attribute);

	delete indices;

	gHashtable.MakeEmpty(HASH_EMPTY_NONE,HASH_EMPTY_FREE);

	return 0;
}