1/*
2 * Copyright (c) 2002-2009 pinc Software. All Rights Reserved.
3 * Released under the terms of the MIT license.
4 */
5
6//!	Finds out to which file(s) a particular block belongs
7
8
9#include "Bitmap.h"
10#include "Disk.h"
11#include "Inode.h"
12#include "Hashtable.h"
13#include "BPlusTree.h"
14#include "dump.h"
15
16#include <fs_info.h>
17
18#include <stdlib.h>
19#include <stdio.h>
20#include <string.h>
21#include <unistd.h>
22#include <ctype.h>
23#include <errno.h>
24
25
26void scanNodes(Disk& disk, Directory* directory, const char* name,
27	const block_run& checkForRun);
28
29
30char gEscape[3] = {0x1b, '[', 0};
31off_t gCount = 1;
32
33
34bool
35checkForBlockRunIntersection(const block_run& check, const block_run& against)
36{
37	if (check.allocation_group == against.allocation_group
38		&& check.start + check.length > against.start
39		&& check.start < against.start + against.length)
40		return true;
41
42	return false;
43}
44
45
46bool
47checkNode(Disk &disk, Inode *inode, block_run checkForRun)
48{
49	// check the inode space itself
50	if (checkForBlockRunIntersection(inode->BlockRun(), checkForRun))
51		return true;
52
53	// the data stream of symlinks is no real data stream
54	if (inode->IsSymlink() && (inode->Flags() & INODE_LONG_SYMLINK) == 0)
55		return false;
56
57	// direct blocks
58
59	const data_stream* data = &inode->InodeBuffer()->data;
60
61	if (data->max_direct_range == 0)
62		return false;
63
64	for (int32 i = 0; i < NUM_DIRECT_BLOCKS; i++) {
65		if (data->direct[i].IsZero())
66			break;
67
68		if (checkForBlockRunIntersection(data->direct[i], checkForRun))
69			return true;
70	}
71
72	// indirect blocks
73
74	if (data->max_indirect_range == 0 || data->indirect.IsZero())
75		return false;
76
77	if (checkForBlockRunIntersection(data->indirect, checkForRun))
78		return true;
79
80	DataStream *stream = dynamic_cast<DataStream *>(inode);
81	if (stream == NULL)
82		return false;
83
84	// load indirect blocks
85	int32 bytes = data->indirect.length << disk.BlockShift();
86	block_run* indirect = (block_run*)malloc(bytes);
87	if (indirect == NULL)
88		return false;
89	if (disk.ReadAt(disk.ToOffset(data->indirect), indirect, bytes) <= 0)
90		return false;
91
92	int32 runs = bytes / sizeof(block_run);
93	for (int32 i = 0; i < runs; i++) {
94		if (indirect[i].IsZero())
95			break;
96
97		if (checkForBlockRunIntersection(indirect[i], checkForRun))
98			return true;
99	}
100	free(indirect);
101
102	// double indirect blocks
103
104	if (data->max_double_indirect_range == 0 || data->double_indirect.IsZero())
105		return false;
106
107	if (checkForBlockRunIntersection(data->double_indirect, checkForRun))
108		return true;
109
110	// TODO: to be implemented...
111
112	return false;
113}
114
115
116void
117scanNode(Disk& disk, Inode* inode, const char* name,
118	const block_run& checkForRun)
119{
120	if (checkNode(disk, inode, checkForRun)) {
121		printf("Inode at (%ld, %u, %u) \"%s\" intersects\n",
122			inode->BlockRun().allocation_group, inode->BlockRun().start,
123			inode->BlockRun().length, name);
124	}
125
126	if (!inode->Attributes().IsZero()) {
127		Inode *attributeDirectory = Inode::Factory(&disk,
128			inode->Attributes());
129		if (attributeDirectory != NULL) {
130			scanNodes(disk,
131				dynamic_cast<Directory *>(attributeDirectory), "(attr-dir)",
132				checkForRun);
133		}
134
135		delete attributeDirectory;
136	}
137}
138
139
140void
141scanNodes(Disk& disk, Directory* directory, const char* directoryName,
142	const block_run& checkForRun)
143{
144	if (directory == NULL)
145		return;
146
147	scanNode(disk, directory, directoryName, checkForRun);
148
149	directory->Rewind();
150	char name[B_FILE_NAME_LENGTH];
151	block_run run;
152	while (directory->GetNextEntry(name, &run) == B_OK) {
153		if (!strcmp(name, ".") || !strcmp(name, ".."))
154			continue;
155
156		if (++gCount % 50 == 0)
157			printf("  %7Ld%s1A\n", gCount, gEscape);
158
159		Inode *inode = Inode::Factory(&disk, run);
160		if (inode != NULL) {
161
162			if (inode->IsDirectory()) {
163				scanNodes(disk, static_cast<Directory *>(inode), name,
164					checkForRun);
165			} else
166				scanNode(disk, inode, name, checkForRun);
167
168			delete inode;
169		} else {
170			printf("  Directory \"%s\" (%ld, %d) points to corrupt inode \"%s\" "
171				"(%ld, %d)\n", directory->Name(),
172				directory->BlockRun().allocation_group,directory
173					->BlockRun().start,
174				name, run.allocation_group, run.start);
175		}
176	}
177}
178
179
180void
181scanNodes(Disk& disk, const block_run& checkForRun, bool scanAll)
182{
183	Directory* root = (Directory*)Inode::Factory(&disk, disk.Root());
184
185	puts("Scanning nodes (this will take some time)...");
186
187	if (root == NULL || root->InitCheck() != B_OK) {
188		fprintf(stderr,"  Could not open root directory!\n");
189		return;
190	}
191
192	scanNodes(disk, root, "(root)", checkForRun);
193
194	delete root;
195
196	if (scanAll) {
197		Directory* indices = (Directory*)Inode::Factory(&disk, disk.Indices());
198
199		puts("Scanning index nodes (this will take some time)...");
200
201		scanNodes(disk, indices, "(indices)", checkForRun);
202
203		delete indices;
204	}
205
206	printf("  %7Ld nodes found.\n", gCount);
207}
208
209
210void
211testBitmap(Disk& disk, const block_run& run)
212{
213	Bitmap bitmap;
214	status_t status = bitmap.SetTo(&disk);
215	if (status != B_OK) {
216		fprintf(stderr, "Bitmap initialization failed: %s\n", strerror(status));
217		return;
218	}
219
220	printf("Block bitmap sees block %lld as %s.\n", disk.ToBlock(run),
221		bitmap.UsedAt(disk.ToBlock(run)) ? "used" : "free");
222}
223
224
225block_run
226parseBlockRun(Disk& disk, char* first, char* last)
227{
228	char* comma;
229
230	if (last != NULL)
231		return block_run::Run(atol(first), atol(last), 1);
232
233	if ((comma = strchr(first, ',')) != NULL) {
234		*comma++ = '\0';
235		return block_run::Run(atol(first), atol(comma));
236	}
237
238	return disk.ToBlockRun(atoll(first));
239}
240
241
242void
243printUsage(char* tool)
244{
245	char* filename = strrchr(tool, '/');
246	fprintf(stderr, "usage: %s <device> <allocation_group> <start>\n",
247		filename ? filename + 1 : tool);
248}
249
250
251int
252main(int argc, char** argv)
253{
254	puts("Copyright (c) 2001-2009 pinc Software.");
255
256	char* toolName = argv[0];
257	if (argc < 2 || !strcmp(argv[1], "--help")) {
258		printUsage(toolName);
259		return -1;
260	}
261
262	bool scanAll = false;
263
264	while (*++argv) {
265		char *arg = *argv;
266		if (*arg == '-') {
267			while (*++arg && isalpha(*arg)) {
268				switch (*arg) {
269					case 'a':
270						scanAll = true;
271						break;
272					default:
273						printUsage(toolName);
274						return -1;
275				}
276			}
277		} else
278			break;
279	}
280
281	Disk disk(argv[0]);
282	status_t status = disk.InitCheck();
283	if (status < B_OK) {
284		fprintf(stderr, "Could not open device or file \"%s\": %s\n",
285			argv[0], strerror(status));
286		return -1;
287	}
288
289	if (disk.ValidateSuperBlock() != B_OK) {
290		fprintf(stderr, "The disk's superblock is corrupt!\n");
291		return -1;
292	}
293
294	// Set the block_run to the right value (as specified on the command line)
295	if (!argv[1]) {
296		fprintf(stderr, "Need the allocation group and starting offset (or the "
297			"block number) of the block to search for!\n");
298		return -1;
299	}
300	block_run run = parseBlockRun(disk, argv[1], argv[2]);
301	off_t block = disk.ToBlock(run);
302
303	putchar('\n');
304	testBitmap(disk, run);
305
306	if (checkForBlockRunIntersection(disk.Log(), run)) {
307		printf("Log area (%lu.%u.%u) intersects\n",
308			disk.Log().allocation_group, disk.Log().start,
309			disk.Log().length);
310	} else if (block < 1) {
311		printf("Superblock intersects\n");
312	} else if (block < 1 + disk.BitmapSize()) {
313		printf("Block bitmap intersects (start %d, end %lu)\n", 1,
314			disk.BitmapSize());
315	} else
316		scanNodes(disk, run, scanAll);
317
318	return 0;
319}
320
321