[thirdparty/e2fsprogs.git] / debugfs / htree.c

/*
 * htree.c --- hash tree routines
 *
 * Copyright (C) 2002 Theodore Ts'o.  This file may be redistributed
 * under the terms of the GNU Public License.
 */

#include "config.h"
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <time.h>
#ifdef HAVE_ERRNO_H
#include <errno.h>
#endif
#include <sys/types.h>
#ifdef HAVE_GETOPT_H
#include <getopt.h>
#else
extern int optind;
extern char *optarg;
#endif

#include "debugfs.h"
#include "uuid/uuid.h"
#include "e2p/e2p.h"

#include "ext2fs/nls.h"

static FILE *pager;

static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino,
				 struct ext2_inode *inode,
				 struct ext2_dx_root_info * rootnode,
				 blk64_t blk, char *buf)
{
	errcode_t	errcode;
	struct ext2_dir_entry *dirent;
	int		thislen, col = 0;
	unsigned int	offset = 0;
	char		name[EXT2_NAME_LEN + 1];
	char		tmp[EXT2_NAME_LEN + 64];
	blk64_t		pblk;
	ext2_dirhash_t 	hash, minor_hash;
	unsigned int	rec_len;
	int		hash_alg;
	int		hash_flags = inode->i_flags & EXT4_CASEFOLD_FL;
	int		csum_size = 0;

	if (ext2fs_has_feature_metadata_csum(fs->super))
		csum_size = sizeof(struct ext2_dir_entry_tail);

	errcode = ext2fs_bmap2(fs, ino, inode, buf, 0, blk, 0, &pblk);
	if (errcode) {
		com_err("htree_dump_leaf_node", errcode,
			"while mapping logical block %llu\n", blk);
		return;
	}

	fprintf(pager, "Reading directory block %llu, phys %llu\n", blk, pblk);
	errcode = ext2fs_read_dir_block4(current_fs, pblk, buf, 0, ino);
	if (errcode) {
		com_err("htree_dump_leaf_node", errcode,
			"while reading block %llu (%llu)\n",
			blk, pblk);
		return;
	}
	hash_alg = rootnode->hash_version;
	if ((hash_alg <= EXT2_HASH_TEA) &&
	    (fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
		hash_alg += 3;

	while (offset < fs->blocksize) {
		dirent = (struct ext2_dir_entry *) (buf + offset);
		errcode = ext2fs_get_rec_len(fs, dirent, &rec_len);
		if (errcode) {
			com_err("htree_dump_leaf_inode", errcode,
				"while getting rec_len for block %lu",
				(unsigned long) blk);
			return;
		}
		thislen = ext2fs_dirent_name_len(dirent);
		if (((offset + rec_len) > fs->blocksize) ||
		    (rec_len < 8) ||
		    ((rec_len % 4) != 0) ||
		    ((unsigned) thislen + 8 > rec_len)) {
			fprintf(pager, "Corrupted directory block (%llu)!\n",
				blk);
			break;
		}
		strncpy(name, dirent->name, thislen);
		name[thislen] = '\0';
		errcode = ext2fs_dirhash2(hash_alg, name, thislen,
					  fs->encoding, hash_flags,
					  fs->super->s_hash_seed,
					  &hash, &minor_hash);
		if (errcode)
			com_err("htree_dump_leaf_node", errcode,
				"while calculating hash");
		if ((offset == fs->blocksize - csum_size) &&
		    (dirent->inode == 0) &&
		    (dirent->rec_len == csum_size) &&
		    (dirent->name_len == EXT2_DIR_NAME_LEN_CSUM)) {
			struct ext2_dir_entry_tail *t;

			t = (struct ext2_dir_entry_tail *) dirent;

			snprintf(tmp, EXT2_NAME_LEN + 64,
				 "leaf block checksum: 0x%08x  ",
				 t->det_checksum);
		} else {
			snprintf(tmp, EXT2_NAME_LEN + 64,
				 "%u 0x%08x-%08x (%d) %s   ",
				 dirent->inode, hash, minor_hash,
				 rec_len, name);
		}
		thislen = strlen(tmp);
		if (col + thislen > 80) {
			fprintf(pager, "\n");
			col = 0;
		}
		fprintf(pager, "%s", tmp);
		col += thislen;
		offset += rec_len;
	}
	fprintf(pager, "\n");
}


static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino,
				 struct ext2_inode *inode,
				 struct ext2_dx_root_info * rootnode,
				 blk64_t blk, char *buf, int level);


static void htree_dump_int_node(ext2_filsys fs, ext2_ino_t ino,
				struct ext2_inode *inode,
				struct ext2_dx_root_info * rootnode,
				struct ext2_dx_entry *ent,
				char *buf, int level)
{
	struct ext2_dx_countlimit	dx_countlimit;
	struct ext2_dx_tail		*tail;
	int				hash, i;
	int				limit, count;
	int				remainder;

	dx_countlimit = *((struct ext2_dx_countlimit *) ent);
	count = ext2fs_le16_to_cpu(dx_countlimit.count);
	limit = ext2fs_le16_to_cpu(dx_countlimit.limit);

	fprintf(pager, "Number of entries (count): %d\n", count);
	fprintf(pager, "Number of entries (limit): %d\n", limit);

	remainder = fs->blocksize - (limit * sizeof(struct ext2_dx_entry));
	if (ent == (struct ext2_dx_entry *)(rootnode + 1))
		remainder -= sizeof(struct ext2_dx_root_info) + 24;
	else
		remainder -= 8;
	if (ext2fs_has_feature_metadata_csum(fs->super) &&
	    remainder == sizeof(struct ext2_dx_tail)) {
		tail = (struct ext2_dx_tail *)(ent + limit);
		fprintf(pager, "Checksum: 0x%08x\n",
			ext2fs_le32_to_cpu(tail->dt_checksum));
	}

	for (i=0; i < count; i++) {
		hash = i ? ext2fs_le32_to_cpu(ent[i].hash) : 0;
		fprintf(pager, "Entry #%d: Hash 0x%08x%s, block %u\n", i,
			hash, (hash & 1) ? " (**)" : "",
			ext2fs_le32_to_cpu(ent[i].block));
		}

	fprintf(pager, "\n");

	for (i=0; i < count; i++) {
		unsigned int hashval, block;

		hashval = ext2fs_le32_to_cpu(ent[i].hash);
		block = ext2fs_le32_to_cpu(ent[i].block);
		fprintf(pager, "Entry #%d: Hash 0x%08x, block %u\n", i,
		       i ? hashval : 0, block);
		if (level)
			htree_dump_int_block(fs, ino, inode, rootnode,
					     block, buf, level-1);
		else
			htree_dump_leaf_node(fs, ino, inode, rootnode,
					     block, buf);
	}

	fprintf(pager, "---------------------\n");
}

static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino,
				 struct ext2_inode *inode,
				 struct ext2_dx_root_info * rootnode,
				 blk64_t blk, char *buf, int level)
{
	char		*cbuf;
	errcode_t	errcode;
	blk64_t		pblk;

	cbuf = malloc(fs->blocksize);
	if (!cbuf) {
		fprintf(pager, "Couldn't allocate child block.\n");
		return;
	}

	errcode = ext2fs_bmap2(fs, ino, inode, buf, 0, blk, 0, &pblk);
	if (errcode) {
		com_err("htree_dump_int_block", errcode,
			"while mapping logical block %llu\n", blk);
		goto errout;
	}

	errcode = io_channel_read_blk64(current_fs->io, pblk, 1, buf);
	if (errcode) {
		com_err("htree_dump_int_block", errcode,
			"while 	reading block %llu\n", blk);
		goto errout;
	}

	htree_dump_int_node(fs, ino, inode, rootnode,
			    (struct ext2_dx_entry *) (buf+8),
			    cbuf, level);
errout:
	free(cbuf);
}


void do_htree_dump(int argc, char *argv[], int sci_idx EXT2FS_ATTR((unused)),
		   void *infop EXT2FS_ATTR((unused)))
{
	ext2_ino_t	ino;
	struct ext2_inode inode;
	blk64_t		blk;
	char		*buf = NULL;
	struct 		ext2_dx_root_info  *rootnode;
	struct 		ext2_dx_entry *ent;
	errcode_t	errcode;

	if (check_fs_open(argv[0]))
		return;

	pager = open_pager();

	if (common_inode_args_process(argc, argv, &ino, 0))
		goto errout;

	if (debugfs_read_inode(ino, &inode, argv[1]))
		goto errout;

	if (!LINUX_S_ISDIR(inode.i_mode)) {
		com_err(argv[0], 0, "Not a directory");
		goto errout;
	}

	if ((inode.i_flags & EXT2_BTREE_FL) == 0) {
		com_err(argv[0], 0, "Not a hash-indexed directory");
		goto errout;
	}

	buf = malloc(2*current_fs->blocksize);
	if (!buf) {
		com_err(argv[0], 0, "Couldn't allocate htree buffer");
		goto errout;
	}

	errcode = ext2fs_bmap2(current_fs, ino, &inode, buf, 0, 0, 0, &blk);
	if (errcode) {
		com_err("do_htree_block", errcode,
			"while mapping logical block 0\n");
		goto errout;
	}

	errcode = io_channel_read_blk64(current_fs->io, blk,
					1, buf);
	if (errcode) {
		com_err(argv[0], errcode, "Error reading root node");
		goto errout;
	}

	rootnode = (struct ext2_dx_root_info *) (buf + 24);

	fprintf(pager, "Root node dump:\n");
	fprintf(pager, "\t Reserved zero: %u\n", rootnode->reserved_zero);
	fprintf(pager, "\t Hash Version: %d\n", rootnode->hash_version);
	fprintf(pager, "\t Info length: %d\n", rootnode->info_length);
	fprintf(pager, "\t Indirect levels: %d\n", rootnode->indirect_levels);
	fprintf(pager, "\t Flags: %d\n", rootnode->unused_flags);

	ent = (struct ext2_dx_entry *)
		((char *)rootnode + rootnode->info_length);

	htree_dump_int_node(current_fs, ino, &inode, rootnode, ent,
			    buf + current_fs->blocksize,
			    rootnode->indirect_levels);

errout:
	free(buf);
	close_pager(pager);
}

/*
 * This function prints the hash of a given file.
 */
void do_dx_hash(int argc, char *argv[], int sci_idx EXT2FS_ATTR((unused)),
		void *infop EXT2FS_ATTR((unused)))
{
	ext2_dirhash_t hash, minor_hash, hash_flags;
	errcode_t	err;
	int		c;
	int		hash_version = 0;
	__u32		hash_seed[4];
	const struct nls_table *encoding;

	hash_seed[0] = hash_seed[1] = hash_seed[2] = hash_seed[3] = 0;

	reset_getopt();
	while ((c = getopt (argc, argv, "h:s:")) != EOF) {
		switch (c) {
		case 'h':
			hash_version = e2p_string2hash(optarg);
			if (hash_version < 0)
				hash_version = atoi(optarg);
			break;
		case 's':
			if (uuid_parse(optarg, (unsigned char *) hash_seed)) {
				fprintf(stderr, "Invalid UUID format: %s\n",
					optarg);
				return;
			}
			break;
		case 'c':
			hash_flags = EXT4_CASEFOLD_FL;
			break;
		case 'e':
			encoding = nls_load_table(e2p_str2encoding(optarg));
			if (!encoding)
				fprintf(stderr, "Invalid encoding: %s\n",
					optarg);
				return;
		default:
			goto print_usage;
		}
	}
	if (optind != argc-1) {
	print_usage:
		com_err(argv[0], 0, "usage: dx_hash [-h hash_alg] "
			"[-s hash_seed] [-c] [-e encoding] filename");
		return;
	}
	err = ext2fs_dirhash2(hash_version, argv[optind],
			      strlen(argv[optind]), encoding, hash_flags,
			      hash_seed, &hash, &minor_hash);

	if (err) {
		com_err(argv[0], err, "while calculating hash");
		return;
	}
	printf("Hash of %s is 0x%0x (minor 0x%0x)\n", argv[optind],
	       hash, minor_hash);
}

/*
 * Search for particular directory entry (useful for debugging very
 * large hash tree directories that have lost some blocks from the
 * btree index).
 */
struct process_block_struct {
	char	*search_name;
	char	*buf;
	int	len;
};

static int search_dir_block(ext2_filsys fs, blk64_t *blocknr,
			    e2_blkcnt_t blockcnt, blk64_t ref_blk,
			    int ref_offset, void *priv_data);

void do_dirsearch(int argc, char *argv[], int sci_idx EXT2FS_ATTR((unused)),
		  void *infop EXT2FS_ATTR((unused)))
{
	ext2_ino_t	inode;
	struct process_block_struct pb;

	if (check_fs_open(argv[0]))
		return;

	if (argc != 3) {
		com_err(0, 0, "Usage: dirsearch dir filename");
		return;
	}

	inode = string_to_inode(argv[1]);
	if (!inode)
		return;

	pb.buf = malloc(current_fs->blocksize);
	if (!pb.buf) {
		com_err("dirsearch", 0, "Couldn't allocate buffer");
		return;
	}
	pb.search_name = argv[2];
	pb.len = strlen(pb.search_name);

	ext2fs_block_iterate3(current_fs, inode, BLOCK_FLAG_READ_ONLY, 0,
			      search_dir_block, &pb);

	free(pb.buf);
}


static int search_dir_block(ext2_filsys fs, blk64_t *blocknr,
			    e2_blkcnt_t blockcnt,
			    blk64_t ref_blk EXT2FS_ATTR((unused)),
			    int ref_offset EXT2FS_ATTR((unused)),
			    void *priv_data)
{
	struct process_block_struct *p;
	struct ext2_dir_entry *dirent;
	errcode_t	       	errcode;
	unsigned int		offset = 0;
	unsigned int		rec_len;

	if (blockcnt < 0)
		return 0;

	p = (struct process_block_struct *) priv_data;

	errcode = io_channel_read_blk64(current_fs->io, *blocknr, 1, p->buf);
	if (errcode) {
		com_err("search_dir_block", errcode,
			"while reading block %lu", (unsigned long) *blocknr);
		return BLOCK_ABORT;
	}

	while (offset < fs->blocksize) {
		dirent = (struct ext2_dir_entry *) (p->buf + offset);
		errcode = ext2fs_get_rec_len(fs, dirent, &rec_len);
		if (errcode) {
			com_err("htree_dump_leaf_inode", errcode,
				"while getting rec_len for block %lu",
				(unsigned long) *blocknr);
			return BLOCK_ABORT;
		}
		if (dirent->inode &&
		    p->len == ext2fs_dirent_name_len(dirent) &&
		    strncmp(p->search_name, dirent->name,
			    p->len) == 0) {
			printf("Entry found at logical block %lld, "
			       "phys %llu, offset %u\n", (long long)blockcnt,
			       *blocknr, offset);
			printf("offset %u\n", offset);
			return BLOCK_ABORT;
		}
		offset += rec_len;
	}
	return 0;
}
Commit	Line	Data
df614db6 TT	1	/*
df614db6 TT	2	* htree.c --- hash tree routines
efc6f628	3	*
df614db6 TT	4	* Copyright (C) 2002 Theodore Ts'o. This file may be redistributed
	5	* under the terms of the GNU Public License.
	6	*/
	7
d1154eb4	8	#include "config.h"
df614db6 TT	9	#include <stdio.h>
	10	#include <unistd.h>
	11	#include <stdlib.h>
	12	#include <ctype.h>
	13	#include <string.h>
	14	#include <time.h>
	15	#ifdef HAVE_ERRNO_H
	16	#include <errno.h>
	17	#endif
	18	#include <sys/types.h>
	19	#ifdef HAVE_GETOPT_H
	20	#include <getopt.h>
efc6f628	21	#else
df614db6 TT	22	extern int optind;
	23	extern char *optarg;
	24	#endif
df614db6 TT	25
df614db6 TT	26	#include "debugfs.h"
42080a86 TT	27	#include "uuid/uuid.h"
42080a86 TT	28	#include "e2p/e2p.h"
df614db6	29
ef733f1a GKB	30	#include "ext2fs/nls.h"
ef733f1a GKB	31
df614db6 TT	32	static FILE *pager;
df614db6 TT	33
df614db6 TT	34	static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino,
df614db6 TT	35	struct ext2_inode *inode,
3e699064	36	struct ext2_dx_root_info * rootnode,
048786d7	37	blk64_t blk, char *buf)
df614db6 TT	38	{
	39	errcode_t errcode;
	40	struct ext2_dir_entry *dirent;
54434927 TT	41	int thislen, col = 0;
54434927 TT	42	unsigned int offset = 0;
b772900b	43	char name[EXT2_NAME_LEN + 1];
9c23b896	44	char tmp[EXT2_NAME_LEN + 64];
048786d7	45	blk64_t pblk;
226515df	46	ext2_dirhash_t hash, minor_hash;
8a480350 TT	47	unsigned int rec_len;
8a480350 TT	48	int hash_alg;
ef733f1a	49	int hash_flags = inode->i_flags & EXT4_CASEFOLD_FL;
81683c6a DW	50	int csum_size = 0;
81683c6a DW	51
4ee26699	52	if (ext2fs_has_feature_metadata_csum(fs->super))
81683c6a	53	csum_size = sizeof(struct ext2_dir_entry_tail);
efc6f628	54
048786d7	55	errcode = ext2fs_bmap2(fs, ino, inode, buf, 0, blk, 0, &pblk);
df614db6 TT	56	if (errcode) {
df614db6 TT	57	com_err("htree_dump_leaf_node", errcode,
048786d7	58	"while mapping logical block %llu\n", blk);
df614db6 TT	59	return;
	60	}
	61
e6575ce3	62	fprintf(pager, "Reading directory block %llu, phys %llu\n", blk, pblk);
81683c6a	63	errcode = ext2fs_read_dir_block4(current_fs, pblk, buf, 0, ino);
df614db6 TT	64	if (errcode) {
df614db6 TT	65	com_err("htree_dump_leaf_node", errcode,
048786d7 VAH	66	"while reading block %llu (%llu)\n",
048786d7 VAH	67	blk, pblk);
df614db6 TT	68	return;
df614db6 TT	69	}
f77704e4 TT	70	hash_alg = rootnode->hash_version;
	71	if ((hash_alg <= EXT2_HASH_TEA) &&
	72	(fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
	73	hash_alg += 3;
df614db6	74
41bf5993	75	while (offset < fs->blocksize) {
df614db6	76	dirent = (struct ext2_dir_entry *) (buf + offset);
8a480350 TT	77	errcode = ext2fs_get_rec_len(fs, dirent, &rec_len);
	78	if (errcode) {
	79	com_err("htree_dump_leaf_inode", errcode,
	80	"while getting rec_len for block %lu",
	81	(unsigned long) blk);
	82	return;
	83	}
70f4632b	84	thislen = ext2fs_dirent_name_len(dirent);
5dd77dbe TT	85	if (((offset + rec_len) > fs->blocksize) \|\|
	86	(rec_len < 8) \|\|
	87	((rec_len % 4) != 0) \|\|
df0b907e	88	((unsigned) thislen + 8 > rec_len)) {
048786d7 VAH	89	fprintf(pager, "Corrupted directory block (%llu)!\n",
048786d7 VAH	90	blk);
df614db6 TT	91	break;
df614db6 TT	92	}
df614db6 TT	93	strncpy(name, dirent->name, thislen);
df614db6 TT	94	name[thislen] = '\0';
ef733f1a GKB	95	errcode = ext2fs_dirhash2(hash_alg, name, thislen,
	96	fs->encoding, hash_flags,
	97	fs->super->s_hash_seed,
	98	&hash, &minor_hash);
52783e0c TT	99	if (errcode)
	100	com_err("htree_dump_leaf_node", errcode,
	101	"while calculating hash");
41bf5993 TT	102	if ((offset == fs->blocksize - csum_size) &&
	103	(dirent->inode == 0) &&
	104	(dirent->rec_len == csum_size) &&
	105	(dirent->name_len == EXT2_DIR_NAME_LEN_CSUM)) {
	106	struct ext2_dir_entry_tail *t;
	107
	108	t = (struct ext2_dir_entry_tail *) dirent;
	109
	110	snprintf(tmp, EXT2_NAME_LEN + 64,
	111	"leaf block checksum: 0x%08x ",
	112	t->det_checksum);
	113	} else {
	114	snprintf(tmp, EXT2_NAME_LEN + 64,
	115	"%u 0x%08x-%08x (%d) %s ",
	116	dirent->inode, hash, minor_hash,
	117	rec_len, name);
	118	}
df614db6 TT	119	thislen = strlen(tmp);
	120	if (col + thislen > 80) {
	121	fprintf(pager, "\n");
	122	col = 0;
	123	}
	124	fprintf(pager, "%s", tmp);
	125	col += thislen;
5dd77dbe	126	offset += rec_len;
df614db6 TT	127	}
	128	fprintf(pager, "\n");
	129	}
	130
	131
	132	static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino,
	133	struct ext2_inode *inode,
3e699064	134	struct ext2_dx_root_info * rootnode,
048786d7	135	blk64_t blk, char *buf, int level);
df614db6 TT	136
	137
	138	static void htree_dump_int_node(ext2_filsys fs, ext2_ino_t ino,
	139	struct ext2_inode *inode,
3e699064	140	struct ext2_dx_root_info * rootnode,
efc6f628	141	struct ext2_dx_entry *ent,
df614db6 TT	142	char *buf, int level)
df614db6 TT	143	{
77b493e3	144	struct ext2_dx_countlimit dx_countlimit;
a996466d	145	struct ext2_dx_tail *tail;
42e5b5f9	146	int hash, i;
77b493e3	147	int limit, count;
a996466d	148	int remainder;
df614db6	149
77b493e3 ES	150	dx_countlimit = ((struct ext2_dx_countlimit ) ent);
	151	count = ext2fs_le16_to_cpu(dx_countlimit.count);
	152	limit = ext2fs_le16_to_cpu(dx_countlimit.limit);
df614db6	153
77b493e3 ES	154	fprintf(pager, "Number of entries (count): %d\n", count);
77b493e3 ES	155	fprintf(pager, "Number of entries (limit): %d\n", limit);
df614db6	156
77b493e3	157	remainder = fs->blocksize - (limit * sizeof(struct ext2_dx_entry));
a996466d DW	158	if (ent == (struct ext2_dx_entry *)(rootnode + 1))
	159	remainder -= sizeof(struct ext2_dx_root_info) + 24;
	160	else
	161	remainder -= 8;
4ee26699	162	if (ext2fs_has_feature_metadata_csum(fs->super) &&
a996466d	163	remainder == sizeof(struct ext2_dx_tail)) {
77b493e3	164	tail = (struct ext2_dx_tail *)(ent + limit);
a996466d DW	165	fprintf(pager, "Checksum: 0x%08x\n",
	166	ext2fs_le32_to_cpu(tail->dt_checksum));
	167	}
	168
77b493e3	169	for (i=0; i < count; i++) {
42e5b5f9	170	hash = i ? ext2fs_le32_to_cpu(ent[i].hash) : 0;
d0ff90d5	171	fprintf(pager, "Entry #%d: Hash 0x%08x%s, block %u\n", i,
42e5b5f9	172	hash, (hash & 1) ? " (**)" : "",
621732c9	173	ext2fs_le32_to_cpu(ent[i].block));
42e5b5f9	174	}
df614db6 TT	175
	176	fprintf(pager, "\n");
	177
77b493e3	178	for (i=0; i < count; i++) {
df0b907e	179	unsigned int hashval, block;
77b493e3	180
df0b907e	181	hashval = ext2fs_le32_to_cpu(ent[i].hash);
77b493e3	182	block = ext2fs_le32_to_cpu(ent[i].block);
8deb80a5	183	fprintf(pager, "Entry #%d: Hash 0x%08x, block %u\n", i,
df0b907e	184	i ? hashval : 0, block);
df614db6	185	if (level)
3e699064	186	htree_dump_int_block(fs, ino, inode, rootnode,
77b493e3	187	block, buf, level-1);
df614db6	188	else
3e699064	189	htree_dump_leaf_node(fs, ino, inode, rootnode,
77b493e3	190	block, buf);
df614db6 TT	191	}
	192
	193	fprintf(pager, "---------------------\n");
	194	}
	195
	196	static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino,
	197	struct ext2_inode *inode,
3e699064	198	struct ext2_dx_root_info * rootnode,
048786d7	199	blk64_t blk, char *buf, int level)
df614db6 TT	200	{
	201	char *cbuf;
	202	errcode_t errcode;
048786d7	203	blk64_t pblk;
df614db6 TT	204
	205	cbuf = malloc(fs->blocksize);
	206	if (!cbuf) {
	207	fprintf(pager, "Couldn't allocate child block.\n");
	208	return;
	209	}
efc6f628	210
048786d7	211	errcode = ext2fs_bmap2(fs, ino, inode, buf, 0, blk, 0, &pblk);
df614db6 TT	212	if (errcode) {
df614db6 TT	213	com_err("htree_dump_int_block", errcode,
048786d7	214	"while mapping logical block %llu\n", blk);
89456558	215	goto errout;
df614db6 TT	216	}
df614db6 TT	217
24a117ab	218	errcode = io_channel_read_blk64(current_fs->io, pblk, 1, buf);
df614db6 TT	219	if (errcode) {
df614db6 TT	220	com_err("htree_dump_int_block", errcode,
048786d7	221	"while reading block %llu\n", blk);
89456558	222	goto errout;
df614db6 TT	223	}
df614db6 TT	224
3e699064	225	htree_dump_int_node(fs, ino, inode, rootnode,
503f9e7f	226	(struct ext2_dx_entry *) (buf+8),
df614db6	227	cbuf, level);
89456558	228	errout:
df614db6 TT	229	free(cbuf);
	230	}
	231
	232
	233
2fcbcb1b TT	234	void do_htree_dump(int argc, char *argv[], int sci_idx EXT2FS_ATTR((unused)),
2fcbcb1b TT	235	void *infop EXT2FS_ATTR((unused)))
df614db6 TT	236	{
	237	ext2_ino_t ino;
	238	struct ext2_inode inode;
048786d7	239	blk64_t blk;
3e699064 TT	240	char *buf = NULL;
3e699064 TT	241	struct ext2_dx_root_info *rootnode;
df614db6	242	struct ext2_dx_entry *ent;
df614db6 TT	243	errcode_t errcode;
	244
	245	if (check_fs_open(argv[0]))
	246	return;
	247
	248	pager = open_pager();
	249
1ec5d104	250	if (common_inode_args_process(argc, argv, &ino, 0))
155f577b	251	goto errout;
df614db6 TT	252
df614db6 TT	253	if (debugfs_read_inode(ino, &inode, argv[1]))
155f577b	254	goto errout;
df614db6 TT	255
	256	if (!LINUX_S_ISDIR(inode.i_mode)) {
	257	com_err(argv[0], 0, "Not a directory");
155f577b	258	goto errout;
df614db6	259	}
efc6f628	260
df614db6 TT	261	if ((inode.i_flags & EXT2_BTREE_FL) == 0) {
df614db6 TT	262	com_err(argv[0], 0, "Not a hash-indexed directory");
155f577b	263	goto errout;
df614db6 TT	264	}
	265
	266	buf = malloc(2*current_fs->blocksize);
	267	if (!buf) {
	268	com_err(argv[0], 0, "Couldn't allocate htree buffer");
155f577b	269	goto errout;
df614db6 TT	270	}
df614db6 TT	271
048786d7	272	errcode = ext2fs_bmap2(current_fs, ino, &inode, buf, 0, 0, 0, &blk);
226515df TT	273	if (errcode) {
	274	com_err("do_htree_block", errcode,
	275	"while mapping logical block 0\n");
	276	goto errout;
	277	}
	278
24a117ab VAH	279	errcode = io_channel_read_blk64(current_fs->io, blk,
24a117ab VAH	280	1, buf);
df614db6 TT	281	if (errcode) {
	282	com_err(argv[0], errcode, "Error reading root node");
	283	goto errout;
	284	}
	285
3e699064	286	rootnode = (struct ext2_dx_root_info *) (buf + 24);
df614db6 TT	287
df614db6 TT	288	fprintf(pager, "Root node dump:\n");
8deb80a5	289	fprintf(pager, "\t Reserved zero: %u\n", rootnode->reserved_zero);
3e699064 TT	290	fprintf(pager, "\t Hash Version: %d\n", rootnode->hash_version);
	291	fprintf(pager, "\t Info length: %d\n", rootnode->info_length);
	292	fprintf(pager, "\t Indirect levels: %d\n", rootnode->indirect_levels);
	293	fprintf(pager, "\t Flags: %d\n", rootnode->unused_flags);
df614db6	294
ae9efd05 AB	295	ent = (struct ext2_dx_entry *)
ae9efd05 AB	296	((char *)rootnode + rootnode->info_length);
df614db6	297
3e699064	298	htree_dump_int_node(current_fs, ino, &inode, rootnode, ent,
df614db6	299	buf + current_fs->blocksize,
3e699064	300	rootnode->indirect_levels);
df614db6 TT	301
df614db6 TT	302	errout:
45e338f5	303	free(buf);
df614db6 TT	304	close_pager(pager);
	305	}
	306
	307	/*
	308	* This function prints the hash of a given file.
	309	*/
2fcbcb1b TT	310	void do_dx_hash(int argc, char *argv[], int sci_idx EXT2FS_ATTR((unused)),
2fcbcb1b TT	311	void *infop EXT2FS_ATTR((unused)))
df614db6	312	{
ef733f1a	313	ext2_dirhash_t hash, minor_hash, hash_flags;
52783e0c	314	errcode_t err;
503f9e7f TT	315	int c;
	316	int hash_version = 0;
	317	__u32 hash_seed[4];
ef733f1a	318	const struct nls_table *encoding;
efc6f628	319
503f9e7f	320	hash_seed[0] = hash_seed[1] = hash_seed[2] = hash_seed[3] = 0;
88494bb6 TT	321
88494bb6 TT	322	reset_getopt();
f8bd5516	323	while ((c = getopt (argc, argv, "h:s:")) != EOF) {
503f9e7f TT	324	switch (c) {
503f9e7f TT	325	case 'h':
f8bd5516 TT	326	hash_version = e2p_string2hash(optarg);
	327	if (hash_version < 0)
	328	hash_version = atoi(optarg);
	329	break;
	330	case 's':
42080a86	331	if (uuid_parse(optarg, (unsigned char *) hash_seed)) {
f8bd5516 TT	332	fprintf(stderr, "Invalid UUID format: %s\n",
	333	optarg);
	334	return;
	335	}
503f9e7f	336	break;
ef733f1a GKB	337	case 'c':
	338	hash_flags = EXT4_CASEFOLD_FL;
	339	break;
	340	case 'e':
	341	encoding = nls_load_table(e2p_str2encoding(optarg));
	342	if (!encoding)
	343	fprintf(stderr, "Invalid encoding: %s\n",
	344	optarg);
	345	return;
49c6b4e9 TT	346	default:
49c6b4e9 TT	347	goto print_usage;
503f9e7f TT	348	}
	349	}
	350	if (optind != argc-1) {
49c6b4e9	351	print_usage:
f8bd5516	352	com_err(argv[0], 0, "usage: dx_hash [-h hash_alg] "
ef733f1a	353	"[-s hash_seed] [-c] [-e encoding] filename");
df614db6 TT	354	return;
df614db6 TT	355	}
ef733f1a GKB	356	err = ext2fs_dirhash2(hash_version, argv[optind],
	357	strlen(argv[optind]), encoding, hash_flags,
	358	hash_seed, &hash, &minor_hash);
	359
52783e0c	360	if (err) {
ce20096f	361	com_err(argv[0], err, "while calculating hash");
52783e0c TT	362	return;
52783e0c TT	363	}
503f9e7f TT	364	printf("Hash of %s is 0x%0x (minor 0x%0x)\n", argv[optind],
503f9e7f TT	365	hash, minor_hash);
df614db6 TT	366	}
	367
	368	/*
	369	* Search for particular directory entry (useful for debugging very
	370	* large hash tree directories that have lost some blocks from the
	371	* btree index).
	372	*/
	373	struct process_block_struct {
	374	char *search_name;
	375	char *buf;
	376	int len;
	377	};
	378
048786d7 VAH	379	static int search_dir_block(ext2_filsys fs, blk64_t *blocknr,
048786d7 VAH	380	e2_blkcnt_t blockcnt, blk64_t ref_blk,
df614db6 TT	381	int ref_offset, void *priv_data);
df614db6 TT	382
2fcbcb1b TT	383	void do_dirsearch(int argc, char *argv[], int sci_idx EXT2FS_ATTR((unused)),
2fcbcb1b TT	384	void *infop EXT2FS_ATTR((unused)))
df614db6 TT	385	{
df614db6 TT	386	ext2_ino_t inode;
df614db6	387	struct process_block_struct pb;
efc6f628	388
df614db6 TT	389	if (check_fs_open(argv[0]))
	390	return;
	391
	392	if (argc != 3) {
	393	com_err(0, 0, "Usage: dirsearch dir filename");
	394	return;
	395	}
	396
	397	inode = string_to_inode(argv[1]);
	398	if (!inode)
	399	return;
	400
	401	pb.buf = malloc(current_fs->blocksize);
	402	if (!pb.buf) {
	403	com_err("dirsearch", 0, "Couldn't allocate buffer");
	404	return;
	405	}
	406	pb.search_name = argv[2];
	407	pb.len = strlen(pb.search_name);
efc6f628	408
048786d7	409	ext2fs_block_iterate3(current_fs, inode, BLOCK_FLAG_READ_ONLY, 0,
43323be9	410	search_dir_block, &pb);
df614db6 TT	411
	412	free(pb.buf);
	413	}
	414
	415
048786d7	416	static int search_dir_block(ext2_filsys fs, blk64_t *blocknr,
efc6f628	417	e2_blkcnt_t blockcnt,
048786d7	418	blk64_t ref_blk EXT2FS_ATTR((unused)),
54434927 TT	419	int ref_offset EXT2FS_ATTR((unused)),
54434927 TT	420	void *priv_data)
df614db6 TT	421	{
	422	struct process_block_struct *p;
	423	struct ext2_dir_entry *dirent;
	424	errcode_t errcode;
54434927	425	unsigned int offset = 0;
8a480350	426	unsigned int rec_len;
df614db6 TT	427
	428	if (blockcnt < 0)
	429	return 0;
	430
	431	p = (struct process_block_struct *) priv_data;
	432
24a117ab	433	errcode = io_channel_read_blk64(current_fs->io, *blocknr, 1, p->buf);
df614db6 TT	434	if (errcode) {
df614db6 TT	435	com_err("search_dir_block", errcode,
54434927	436	"while reading block %lu", (unsigned long) *blocknr);
df614db6 TT	437	return BLOCK_ABORT;
	438	}
	439
	440	while (offset < fs->blocksize) {
	441	dirent = (struct ext2_dir_entry *) (p->buf + offset);
8a480350 TT	442	errcode = ext2fs_get_rec_len(fs, dirent, &rec_len);
	443	if (errcode) {
	444	com_err("htree_dump_leaf_inode", errcode,
	445	"while getting rec_len for block %lu",
	446	(unsigned long) *blocknr);
42080a86	447	return BLOCK_ABORT;
8a480350	448	}
df614db6	449	if (dirent->inode &&
70f4632b	450	p->len == ext2fs_dirent_name_len(dirent) &&
df614db6 TT	451	strncmp(p->search_name, dirent->name,
	452	p->len) == 0) {
	453	printf("Entry found at logical block %lld, "
048786d7	454	"phys %llu, offset %u\n", (long long)blockcnt,
df614db6	455	*blocknr, offset);
8deb80a5	456	printf("offset %u\n", offset);
df614db6 TT	457	return BLOCK_ABORT;
df614db6 TT	458	}
5dd77dbe	459	offset += rec_len;
df614db6 TT	460	}
	461	return 0;
	462	}
	463