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