htree.c revision 5dd77dbe5a0ac6d78c1c6441fae4087be56d9088 
1/*
2 * htree.c --- hash tree routines
3 *
4 * Copyright (C) 2002 Theodore Ts'o.  This file may be redistributed
5 * under the terms of the GNU Public License.
6 */
7
8#include <stdio.h>
9#include <unistd.h>
10#include <stdlib.h>
11#include <ctype.h>
12#include <string.h>
13#include <time.h>
14#ifdef HAVE_ERRNO_H
15#include <errno.h>
16#endif
17#include <sys/types.h>
18#ifdef HAVE_GETOPT_H
19#include <getopt.h>
20#else
21extern int optind;
22extern char *optarg;
23#endif
24
25#include "debugfs.h"
26
27static FILE *pager;
28
29static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino,
30				 struct ext2_inode *inode,
31				 struct ext2_dx_root_info * rootnode,
32				 blk_t blk, char *buf)
33{
34	errcode_t	errcode;
35	struct ext2_dir_entry *dirent;
36	int		thislen, col = 0;
37	unsigned int	offset = 0;
38	char		name[EXT2_NAME_LEN + 1];
39	char		tmp[EXT2_NAME_LEN + 16];
40	blk_t		pblk;
41	ext2_dirhash_t 	hash, minor_hash;
42	int		rec_len, hash_alg;
43
44	errcode = ext2fs_bmap(fs, ino, inode, buf, 0, blk, &pblk);
45	if (errcode) {
46		com_err("htree_dump_leaf_node", errcode,
47			"while mapping logical block %u\n", blk);
48		return;
49	}
50
51	printf("Reading directory block %lu, phys %lu\n", blk, pblk);
52	errcode = ext2fs_read_dir_block2(current_fs, pblk, buf, 0);
53	if (errcode) {
54		com_err("htree_dump_leaf_node", errcode,
55			"while reading block %lu (%lu)\n", blk, pblk);
56		return;
57	}
58	hash_alg = rootnode->hash_version;
59	if ((hash_alg <= EXT2_HASH_TEA) &&
60	    (fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
61		hash_alg += 3;
62
63	while (offset < fs->blocksize) {
64		dirent = (struct ext2_dir_entry *) (buf + offset);
65		rec_len = (dirent->rec_len || fs->blocksize < 65536) ?
66			dirent->rec_len : 65536;
67		if (((offset + rec_len) > fs->blocksize) ||
68		    (rec_len < 8) ||
69		    ((rec_len % 4) != 0) ||
70		    (((dirent->name_len & 0xFF)+8) > rec_len)) {
71			fprintf(pager, "Corrupted directory block (%u)!\n", blk);
72			break;
73		}
74		thislen = ((dirent->name_len & 0xFF) < EXT2_NAME_LEN) ?
75			(dirent->name_len & 0xFF) : EXT2_NAME_LEN;
76		strncpy(name, dirent->name, thislen);
77		name[thislen] = '\0';
78		errcode = ext2fs_dirhash(hash_alg, name,
79					 thislen, fs->super->s_hash_seed,
80					 &hash, &minor_hash);
81		if (errcode)
82			com_err("htree_dump_leaf_node", errcode,
83				"while calculating hash");
84		sprintf(tmp, "%u 0x%08x-%08x (%d) %s   ", dirent->inode,
85			hash, minor_hash, rec_len, name);
86		thislen = strlen(tmp);
87		if (col + thislen > 80) {
88			fprintf(pager, "\n");
89			col = 0;
90		}
91		fprintf(pager, "%s", tmp);
92		col += thislen;
93		offset += rec_len;
94	}
95	fprintf(pager, "\n");
96}
97
98
99static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino,
100				 struct ext2_inode *inode,
101				 struct ext2_dx_root_info * rootnode,
102				 blk_t blk, char *buf, int level);
103
104
105static void htree_dump_int_node(ext2_filsys fs, ext2_ino_t ino,
106				struct ext2_inode *inode,
107				struct ext2_dx_root_info * rootnode,
108				struct ext2_dx_entry *ent,
109				char *buf, int level)
110{
111	struct ext2_dx_countlimit	limit;
112	struct ext2_dx_entry		e;
113	int				hash, i;
114
115
116	limit = *((struct ext2_dx_countlimit *) ent);
117	limit.count = ext2fs_le16_to_cpu(limit.count);
118	limit.limit = ext2fs_le16_to_cpu(limit.limit);
119
120	fprintf(pager, "Number of entries (count): %d\n", limit.count);
121	fprintf(pager, "Number of entries (limit): %d\n", limit.limit);
122
123	for (i=0; i < limit.count; i++) {
124		hash = i ? ext2fs_le32_to_cpu(ent[i].hash) : 0;
125		fprintf(pager, "Entry #%d: Hash 0x%08x%s, block %u\n", i,
126			hash, (hash & 1) ? " (**)" : "",
127			ext2fs_le32_to_cpu(ent[i].block));
128		}
129
130	fprintf(pager, "\n");
131
132	for (i=0; i < limit.count; i++) {
133		e.hash = ext2fs_le32_to_cpu(ent[i].hash);
134		e.block = ext2fs_le32_to_cpu(ent[i].block);
135		fprintf(pager, "Entry #%d: Hash 0x%08x, block %u\n", i,
136		       i ? e.hash : 0, e.block);
137		if (level)
138			htree_dump_int_block(fs, ino, inode, rootnode,
139					     e.block, buf, level-1);
140		else
141			htree_dump_leaf_node(fs, ino, inode, rootnode,
142					     e.block, buf);
143	}
144
145	fprintf(pager, "---------------------\n");
146}
147
148static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino,
149				 struct ext2_inode *inode,
150				 struct ext2_dx_root_info * rootnode,
151				 blk_t blk, char *buf, int level)
152{
153	char		*cbuf;
154	errcode_t	errcode;
155	blk_t		pblk;
156
157	cbuf = malloc(fs->blocksize);
158	if (!cbuf) {
159		fprintf(pager, "Couldn't allocate child block.\n");
160		return;
161	}
162
163	errcode = ext2fs_bmap(fs, ino, inode, buf, 0, blk, &pblk);
164	if (errcode) {
165		com_err("htree_dump_int_block", errcode,
166			"while mapping logical block %u\n", blk);
167		goto errout;
168	}
169
170	errcode = io_channel_read_blk(current_fs->io, pblk, 1, buf);
171	if (errcode) {
172		com_err("htree_dump_int_block", errcode,
173			"while 	reading block %u\n", blk);
174		goto errout;
175	}
176
177	htree_dump_int_node(fs, ino, inode, rootnode,
178			    (struct ext2_dx_entry *) (buf+8),
179			    cbuf, level);
180errout:
181	free(cbuf);
182}
183
184
185
186void do_htree_dump(int argc, char *argv[])
187{
188	ext2_ino_t	ino;
189	struct ext2_inode inode;
190	int		c;
191	int		long_opt = 0;
192	blk_t		blk;
193	char		*buf = NULL;
194	struct 		ext2_dx_root_info  *rootnode;
195	struct 		ext2_dx_entry *ent;
196	struct		ext2_dx_countlimit *limit;
197	errcode_t	errcode;
198
199	if (check_fs_open(argv[0]))
200		return;
201
202	pager = open_pager();
203
204	reset_getopt();
205	while ((c = getopt (argc, argv, "l")) != EOF) {
206		switch (c) {
207		case 'l':
208			long_opt++;
209			break;
210		default:
211			goto print_usage;
212		}
213	}
214
215	if (argc > optind+1) {
216	print_usage:
217		com_err(0, 0, "Usage: htree_dump [-l] file");
218		goto errout;
219	}
220
221	if (argc == optind)
222		ino = cwd;
223	else
224		ino = string_to_inode(argv[optind]);
225	if (!ino)
226		goto errout;
227
228	if (debugfs_read_inode(ino, &inode, argv[1]))
229		goto errout;
230
231	if (!LINUX_S_ISDIR(inode.i_mode)) {
232		com_err(argv[0], 0, "Not a directory");
233		goto errout;
234	}
235
236	if ((inode.i_flags & EXT2_BTREE_FL) == 0) {
237		com_err(argv[0], 0, "Not a hash-indexed directory");
238		goto errout;
239	}
240
241	buf = malloc(2*current_fs->blocksize);
242	if (!buf) {
243		com_err(argv[0], 0, "Couldn't allocate htree buffer");
244		goto errout;
245	}
246
247	errcode = ext2fs_bmap(current_fs, ino, &inode, buf, 0, 0, &blk);
248	if (errcode) {
249		com_err("do_htree_block", errcode,
250			"while mapping logical block 0\n");
251		goto errout;
252	}
253
254	errcode = io_channel_read_blk(current_fs->io, blk,
255				      1, buf);
256	if (errcode) {
257		com_err(argv[0], errcode, "Error reading root node");
258		goto errout;
259	}
260
261	rootnode = (struct ext2_dx_root_info *) (buf + 24);
262
263	fprintf(pager, "Root node dump:\n");
264	fprintf(pager, "\t Reserved zero: %u\n", rootnode->reserved_zero);
265	fprintf(pager, "\t Hash Version: %d\n", rootnode->hash_version);
266	fprintf(pager, "\t Info length: %d\n", rootnode->info_length);
267	fprintf(pager, "\t Indirect levels: %d\n", rootnode->indirect_levels);
268	fprintf(pager, "\t Flags: %d\n", rootnode->unused_flags);
269
270	ent = (struct ext2_dx_entry *) (buf + 24 + rootnode->info_length);
271	limit = (struct ext2_dx_countlimit *) ent;
272
273	htree_dump_int_node(current_fs, ino, &inode, rootnode, ent,
274			    buf + current_fs->blocksize,
275			    rootnode->indirect_levels);
276
277errout:
278	if (buf)
279		free(buf);
280	close_pager(pager);
281}
282
283/*
284 * This function prints the hash of a given file.
285 */
286void do_dx_hash(int argc, char *argv[])
287{
288	ext2_dirhash_t hash, minor_hash;
289	errcode_t	err;
290	int		c;
291	int		hash_version = 0;
292	__u32		hash_seed[4];
293
294	hash_seed[0] = hash_seed[1] = hash_seed[2] = hash_seed[3] = 0;
295
296	reset_getopt();
297	while ((c = getopt (argc, argv, "h:")) != EOF) {
298		switch (c) {
299		case 'h':
300			hash_version = atoi(optarg);
301			break;
302		default:
303			goto print_usage;
304		}
305	}
306	if (optind != argc-1) {
307	print_usage:
308		com_err(argv[0], 0, "usage: dx_hash filename");
309		return;
310	}
311	err = ext2fs_dirhash(hash_version, argv[optind], strlen(argv[optind]),
312			     hash_seed, &hash, &minor_hash);
313	if (err) {
314		com_err(argv[0], err, "while caclulating hash");
315		return;
316	}
317	printf("Hash of %s is 0x%0x (minor 0x%0x)\n", argv[optind],
318	       hash, minor_hash);
319}
320
321/*
322 * Search for particular directory entry (useful for debugging very
323 * large hash tree directories that have lost some blocks from the
324 * btree index).
325 */
326struct process_block_struct {
327	char	*search_name;
328	char	*buf;
329	int	len;
330};
331
332static int search_dir_block(ext2_filsys fs, blk_t *blocknr,
333			    e2_blkcnt_t blockcnt, blk_t ref_blk,
334			    int ref_offset, void *priv_data);
335
336void do_dirsearch(int argc, char *argv[])
337{
338	ext2_ino_t	inode;
339	struct process_block_struct pb;
340
341	if (check_fs_open(argv[0]))
342		return;
343
344	if (argc != 3) {
345		com_err(0, 0, "Usage: dirsearch dir filename");
346		return;
347	}
348
349	inode = string_to_inode(argv[1]);
350	if (!inode)
351		return;
352
353	pb.buf = malloc(current_fs->blocksize);
354	if (!pb.buf) {
355		com_err("dirsearch", 0, "Couldn't allocate buffer");
356		return;
357	}
358	pb.search_name = argv[2];
359	pb.len = strlen(pb.search_name);
360
361	ext2fs_block_iterate2(current_fs, inode, BLOCK_FLAG_READ_ONLY, 0,
362			      search_dir_block, &pb);
363
364	free(pb.buf);
365}
366
367
368static int search_dir_block(ext2_filsys fs, blk_t *blocknr,
369			    e2_blkcnt_t blockcnt,
370			    blk_t ref_blk EXT2FS_ATTR((unused)),
371			    int ref_offset EXT2FS_ATTR((unused)),
372			    void *priv_data)
373{
374	struct process_block_struct *p;
375	struct ext2_dir_entry *dirent;
376	errcode_t	       	errcode;
377	unsigned int		offset = 0;
378	int			rec_len;
379
380	if (blockcnt < 0)
381		return 0;
382
383	p = (struct process_block_struct *) priv_data;
384
385	errcode = io_channel_read_blk(current_fs->io, *blocknr, 1, p->buf);
386	if (errcode) {
387		com_err("search_dir_block", errcode,
388			"while reading block %lu", (unsigned long) *blocknr);
389		return BLOCK_ABORT;
390	}
391
392	while (offset < fs->blocksize) {
393		dirent = (struct ext2_dir_entry *) (p->buf + offset);
394		rec_len = (dirent->rec_len || fs->blocksize < 65536) ?
395			dirent->rec_len : 65536;
396		if (dirent->inode &&
397		    p->len == (dirent->name_len & 0xFF) &&
398		    strncmp(p->search_name, dirent->name,
399			    p->len) == 0) {
400			printf("Entry found at logical block %lld, "
401			       "phys %u, offset %u\n", (long long)blockcnt,
402			       *blocknr, offset);
403			printf("offset %u\n", offset);
404			return BLOCK_ABORT;
405		}
406		offset += rec_len;
407	}
408	return 0;
409}
410
411