1/*
2 * Copyright (c) 2001-2008 pinc Software. All Rights Reserved.
3 * Released under the terms of the MIT license.
4 */
5
6//!	sanity and completeness check for indices
7
8#include "Disk.h"
9#include "Inode.h"
10#include "Hashtable.h"
11#include "BPlusTree.h"
12#include "dump.h"
13
14#include <fs_info.h>
15
16#include <stdlib.h>
17#include <stdio.h>
18#include <string.h>
19#include <unistd.h>
20#include <ctype.h>
21#include <errno.h>
22
23
24char gEscape[3] = {0x1b, '[', 0};
25off_t gCount = 1;
26bool gDoNotCheckForFiles = false;
27bool gDoNotCheckIndex = false;
28bool gCheckAll = false;
29
30
31// we just want to know which inodes exist, so don't remember anything
32// along the position of the inode.
33
34class BlockRunHashtable : public Hashtable
35{
36	public:
37		BlockRunHashtable(int capacity)
38			: Hashtable(capacity)
39		{
40			SetHashFunction((uint32 (*)(const void *))BlockRunHash);
41			SetCompareFunction((bool (*)(const void *, const void *))BlockRunCompare);
42		}
43
44		bool Contains(block_run *run)
45		{
46			return ContainsKey((void *)run);
47		}
48
49		bool Put(block_run &run)
50		{
51			block_run *value = (block_run *)malloc(sizeof(block_run));
52			if (!value)
53				return false;
54
55			memcpy(value,&run,sizeof(block_run));
56
57			if (Hashtable::Put(value,value))
58				return true;
59
60			free(value);
61			return false;
62		}
63
64		static uint32 BlockRunHash(const block_run *run)
65		{
66			return run->allocation_group << 16 | run->start;
67		}
68
69		static bool BlockRunCompare(const block_run *runA, const block_run *runB)
70		{
71			return *runA == *runB;
72		}
73};
74
75
76BlockRunHashtable gHashtable(1000);
77
78
79int
80compareBlockRuns(const block_run *a, const block_run *b)
81{
82	int cmp = (int)a->allocation_group - (int)b->allocation_group;
83	if (cmp == 0)
84		cmp = (int)a->start - (int)b->start;
85	return cmp;
86}
87
88
89void
90collectFiles(Disk &disk,Directory *directory)
91{
92	if (directory == NULL)
93		return;
94
95	directory->Rewind();
96	char name[B_FILE_NAME_LENGTH];
97	block_run run;
98	while (directory->GetNextEntry(name,&run) >= B_OK)
99	{
100		if (!strcmp(name,".") || !strcmp(name,".."))
101			continue;
102
103		gHashtable.Put(run);
104
105		if (++gCount % 50 == 0)
106			printf("  %7Ld%s1A\n",gCount,gEscape);
107
108		Inode *inode = Inode::Factory(&disk,run);
109		if (inode != NULL)
110		{
111			if (inode->IsDirectory())
112				collectFiles(disk,static_cast<Directory *>(inode));
113
114			delete inode;
115		}
116		else
117			printf("  Directory \"%s\" (%ld, %d) points to corrupt inode \"%s\" (%ld, %d)\n",
118				directory->Name(),directory->BlockRun().allocation_group,directory->BlockRun().start,
119				name,run.allocation_group,run.start);
120	}
121}
122
123
124void
125collectFiles(Disk &disk)
126{
127	Directory *root = (Directory *)Inode::Factory(&disk,disk.Root());
128
129	puts("Collecting files (this will take some time)...");
130
131	if (root == NULL || root->InitCheck() < B_OK)
132	{
133		fprintf(stderr,"  Could not open root directory!\n");
134		return;
135	}
136	collectFiles(disk,root);
137
138	printf("  %7Ld files found.\n",gCount);
139
140	delete root;
141}
142
143
144void
145checkIndexForNonExistingFiles(Disk &disk,BPlusTree &tree)
146{
147	char name[B_FILE_NAME_LENGTH];
148	uint16 length;
149	off_t offset;
150
151	while (tree.GetNextEntry(name,&length,B_FILE_NAME_LENGTH,&offset) == B_OK)
152	{
153		name[length] = 0;
154		block_run run = disk.ToBlockRun(offset);
155		if (!gHashtable.Contains(&run))
156		{
157			printf("  inode at (%ld, %d), offset %lld, doesn't exist!",run.allocation_group,run.start,offset);
158			switch (tree.Type())
159			{
160				case BPLUSTREE_STRING_TYPE:
161					printf(" (string = \"%s\")",name);
162					break;
163				case BPLUSTREE_INT32_TYPE:
164					printf(" (int32 = %ld)",*(int32 *)&name);
165					break;
166				case BPLUSTREE_UINT32_TYPE:
167					printf(" (uint32 = %lu)",*(uint32 *)&name);
168					break;
169				case BPLUSTREE_INT64_TYPE:
170					printf(" (int64 = %lld)",*(int64 *)&name);
171					break;
172				case BPLUSTREE_UINT64_TYPE:
173					printf(" (uint64 = %Lu)",*(uint64 *)&name);
174					break;
175				case BPLUSTREE_FLOAT_TYPE:
176					printf(" (float = %g)",*(float *)&name);
177					break;
178				case BPLUSTREE_DOUBLE_TYPE:
179					printf(" (double = %g)",*(double *)&name);
180					break;
181			}
182			putchar('\n');
183		}
184	}
185}
186
187
188void
189checkFiles(Disk &disk,BPlusTree &tree,char *attribute)
190{
191	block_run *runs = (block_run *)malloc(gCount * sizeof(block_run));
192	if (runs == NULL)
193	{
194		fprintf(stderr,"  Not enough memory!\n");
195		return;
196	}
197	// copy hashtable to array
198	block_run *run = NULL;
199	int32 index = 0;
200	gHashtable.Rewind();
201	while (gHashtable.GetNextEntry((void **)&run) == B_OK)
202	{
203		runs[index++] = *run;
204	}
205
206	// sort array to speed up disk access
207	qsort(runs,index,sizeof(block_run),(int (*)(const void *,const void *))compareBlockRuns);
208
209	bool sizeIndex = !strcmp(attribute,"size");
210	bool nameIndex = !strcmp(attribute,"name");
211	bool modifiedIndex = !strcmp(attribute,"last_modified");
212
213	char key[B_FILE_NAME_LENGTH];
214	uint16 keyLength = 0;
215
216	Inode *inode = NULL;
217
218	for (int32 i = 0;i < index;i++)
219	{
220		if (i % 50 == 0)
221			printf("  %7ld%s1A\n",i,gEscape);
222
223		delete inode;
224		inode = Inode::Factory(&disk,runs[i]);
225		if (inode == NULL || inode->InitCheck() < B_OK)
226		{
227			fprintf(stderr,"  inode at (%ld, %d) is corrupt!\n",runs[i].allocation_group,runs[i].start);
228			delete inode;
229			continue;
230		}
231
232		// check indices not based on standard attributes
233		if (sizeIndex)
234		{
235			if (inode->IsDirectory())
236				continue;
237
238			memcpy(key,&inode->InodeBuffer()->data.size,sizeof(off_t));
239			keyLength = sizeof(off_t);
240		}
241		else if (nameIndex)
242		{
243			strcpy(key,inode->Name());
244			keyLength = strlen(key);
245		}
246		else if (modifiedIndex)
247		{
248			if (inode->IsDirectory())
249				continue;
250
251			memcpy(key,&inode->InodeBuffer()->last_modified_time,sizeof(off_t));
252			keyLength = sizeof(off_t);
253		}
254		else	// iterate through all attributes to find the right one (damn slow, sorry...)
255		{
256			inode->RewindAttributes();
257			char name[B_FILE_NAME_LENGTH];
258			uint32 type;
259			void *data;
260			size_t length;
261			bool found = false;
262			while (inode->GetNextAttribute(name,&type,&data,&length) == B_OK)
263			{
264				if (!strcmp(name,attribute))
265				{
266					strncpy(key,(char *)data,B_FILE_NAME_LENGTH - 1);
267					key[B_FILE_NAME_LENGTH - 1] = '\0';
268					keyLength = length > B_FILE_NAME_LENGTH ? B_FILE_NAME_LENGTH : length;
269					found = true;
270					break;
271				}
272			}
273			if (!found)
274				continue;
275		}
276
277		off_t value;
278		if (tree.Find((uint8 *)key,keyLength,&value) < B_OK)
279		{
280			if (*inode->Name())
281				fprintf(stderr,"  inode at (%ld, %d) name \"%s\" is not in index!\n",runs[i].allocation_group,runs[i].start,inode->Name());
282			else
283			{
284				// inode is obviously deleted!
285				block_run parent = inode->Parent();
286				Directory *directory = (Directory *)Inode::Factory(&disk,parent);
287				if (directory != NULL && directory->InitCheck() == B_OK)
288				{
289					BPlusTree *parentTree;
290					if (directory->GetTree(&parentTree) == B_OK)
291					{
292						char name[B_FILE_NAME_LENGTH];
293						uint16 length;
294						off_t offset,searchOffset = disk.ToBlock(runs[i]);
295						bool found = false;
296
297						while (parentTree->GetNextEntry(name,&length,B_FILE_NAME_LENGTH,&offset) == B_OK)
298						{
299							if (offset == searchOffset)
300							{
301								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());
302								found = true;
303								break;
304							}
305						}
306						if (!found)
307							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());
308					}
309					else
310						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());
311				}
312				else
313				{
314					// not that this would be really possible... - but who knows
315					fprintf(stderr,"  inode at (%ld, %d) is not in index and has invalid parent!\n",runs[i].allocation_group,runs[i].start);
316				}
317				delete directory;
318			}
319		}
320		else
321		{
322			if (bplustree_node::LinkType(value) == BPLUSTREE_NODE)
323			{
324				if (disk.ToBlockRun(value) != runs[i])
325					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);
326			}
327			else
328			{
329				// search duplicates
330				char name[B_FILE_NAME_LENGTH];
331				uint16 length;
332				off_t offset;
333				bool found = false,duplicates = false;
334//puts("++");
335				tree.Rewind();
336				while (tree.GetNextEntry(name,&length,B_FILE_NAME_LENGTH,&offset) == B_OK)
337				{
338					//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);
339					if (keyLength == length && !memcmp(key,name,keyLength))
340					{
341						duplicates = true;
342						if (disk.ToBlockRun(offset) == runs[i])
343						{
344							found = true;
345							break;
346						}
347					}
348					//else if (duplicates)
349					//	break;
350				}
351				if (!found)
352				{
353					printf("  inode \"%s\" at (%ld, %d) not found in duplicates!\n",inode->Name(),runs[i].allocation_group,runs[i].start);
354//					return;
355				}
356			}
357		}
358	}
359	delete inode;
360	printf("  %7Ld files processed.\n",gCount);
361}
362
363
364int
365checkIndex(Disk &disk,char *attribute,block_run &run,bool collect)
366{
367	Directory *index = (Directory *)Inode::Factory(&disk,run);
368	status_t status;
369	if (index == NULL || (status = index->InitCheck()) < B_OK)
370	{
371		fprintf(stderr,"  Could not get index directory for \"%s\": %s!\n",attribute,index ? strerror(status) : "not found/corrupted");
372		return -1;
373	}
374
375	printf("\nCheck \"%s\" index's on-disk structure...\n",attribute);
376	//dump_inode(index->InodeBuffer());
377
378	BPlusTree *tree;
379	if (index->GetTree(&tree) < B_OK || tree->Validate(true) < B_OK)
380	{
381		fprintf(stderr,"  B+Tree of index \"%s\" seems to be corrupt!\n",attribute);
382		//return -1;
383	}
384
385	if (collect && (!gDoNotCheckIndex || !gDoNotCheckForFiles))
386		collectFiles(disk);
387
388	if (!gDoNotCheckIndex)
389	{
390		printf("Check for non-existing files in index \"%s\"...\n",attribute);
391		checkIndexForNonExistingFiles(disk,*tree);
392	}
393
394	if (!gDoNotCheckForFiles)
395	{
396		printf("Check for files not in index \"%s\" (this may take even more time)...\n",attribute);
397		checkFiles(disk,*tree,attribute);
398	}
399	return 0;
400}
401
402
403void
404printUsage(char *tool)
405{
406	char *filename = strrchr(tool,'/');
407	fprintf(stderr,"usage: %s [-ifa] index-name\n"
408			"\t-i\tdo not check for non-existing files in the index\n"
409			"\t-f\tdo not check if all the files are in the index\n"
410			"\t-a\tcheck all indices (could take some weeks...)\n"
411			,filename ? filename + 1 : tool);
412}
413
414
415int
416main(int argc,char **argv)
417{
418	puts("Copyright (c) 2001-2008 pinc Software.");
419
420	char *toolName = argv[0];
421	if (argc < 2 || !strcmp(argv[1],"--help"))
422	{
423		printUsage(toolName);
424		return -1;
425	}
426
427	while (*++argv)
428	{
429		char *arg = *argv;
430		if (*arg == '-')
431		{
432			while (*++arg && isalpha(*arg))
433			{
434				switch (*arg)
435				{
436					case 'i':
437						gDoNotCheckIndex = true;
438						break;
439					case 'f':
440						gDoNotCheckForFiles = true;
441						break;
442					case 'a':
443						gCheckAll = true;
444						break;
445				}
446			}
447		}
448		else
449			break;
450	}
451
452	char *attribute = argv[0];
453	if (!gCheckAll && attribute == NULL)
454	{
455		printUsage(toolName);
456		return -1;
457	}
458
459	dev_t device = dev_for_path(".");
460	if (device < B_OK)
461	{
462		fprintf(stderr,"Could not find device for current location: %s\n",strerror(device));
463		return -1;
464	}
465
466	fs_info info;
467	if (fs_stat_dev(device,&info) < B_OK)
468	{
469		fprintf(stderr,"Could not get stats for device: %s\n",strerror(errno));
470		return -1;
471	}
472
473	Disk disk(info.device_name);
474	status_t status;
475	if ((status = disk.InitCheck()) < B_OK)
476	{
477		fprintf(stderr,"Could not open device or file \"%s\": %s\n",info.device_name,strerror(status));
478		return -1;
479	}
480
481	if (disk.ValidateSuperBlock() < B_OK)
482	{
483		fprintf(stderr,"The disk's superblock is corrupt!\n");
484		return -1;
485	}
486
487	Directory *indices = (Directory *)Inode::Factory(&disk,disk.Indices());
488	if (indices == NULL || (status = indices->InitCheck()) < B_OK)
489	{
490		fprintf(stderr,"  Could not get indices directory: %s!\n",indices ? strerror(status) : "not found/corrupted");
491		delete indices;
492		return -1;
493	}
494	BPlusTree *tree;
495	if (indices->GetTree(&tree) < B_OK || tree->Validate() < B_OK)
496	{
497		fprintf(stderr,"  Indices B+Tree seems to be corrupt!\n");
498		delete indices;
499		return -1;
500	}
501
502	block_run run;
503
504	if (gCheckAll)
505	{
506		putchar('\n');
507		collectFiles(disk);
508
509		char name[B_FILE_NAME_LENGTH];
510		while (indices->GetNextEntry(name,&run) >= B_OK)
511			checkIndex(disk,name,run,false);
512	}
513	else if (indices->FindEntry(attribute,&run) == B_OK)
514		checkIndex(disk,attribute,run,true);
515	else
516		fprintf(stderr,"  Could not find index directory for \"%s\"!\n",attribute);
517
518	delete indices;
519
520	gHashtable.MakeEmpty(HASH_EMPTY_NONE,HASH_EMPTY_FREE);
521
522	return 0;
523}
524
525