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
23char gEscape[3] = {0x1b, '[', 0};
24off_t gCount = 1;
25bool gDoNotCheckForFiles = false;
26bool gDoNotCheckIndex = false;
27bool 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
33class 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
75BlockRunHashtable gHashtable(1000);
76
77
78int
79compareBlockRuns(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
88void
89collectFiles(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
123void
124collectFiles(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
143void
144checkIndexForNonExistingFiles(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
187void
188checkFiles(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
363int
364checkIndex(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
402void
403printUsage(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
414int
415main(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