From df614db6ef79c767745b8154c26d69398b571605 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Mon, 25 Feb 2002 04:28:45 -0500 Subject: [PATCH] Add initial support in debugfs for examining directory indexing information. --- debugfs/ChangeLog | 9 ++ debugfs/Makefile.in | 5 +- debugfs/debug_cmds.ct | 9 ++ debugfs/htree.c | 364 ++++++++++++++++++++++++++++++++++++++++++++++++++ debugfs/util.c | 10 +- lib/ext2fs/ChangeLog | 5 + lib/ext2fs/ext2_fs.h | 31 +++++ 7 files changed, 427 insertions(+), 6 deletions(-) create mode 100644 debugfs/htree.c diff --git a/debugfs/ChangeLog b/debugfs/ChangeLog index 1cff0b0..4d8a301 100644 --- a/debugfs/ChangeLog +++ b/debugfs/ChangeLog @@ -1,3 +1,12 @@ +2002-02-25 Theodore Tso + + * util.c (open_pager): If the PAGER environment is set to __none__ + then don't use a pager at all, and ship it all to stdout. + + * Makefile.in, debug_cmds.ct, htree.c: Add new file htree.c, which + implements the three new commands, htree_dump, dx_hash, + and dirsearch. + 2002-02-24 Theodore Tso * Makefile.in (install): Remove any compressed man pages before diff --git a/debugfs/Makefile.in b/debugfs/Makefile.in index 79ae78e..b76dec2 100644 --- a/debugfs/Makefile.in +++ b/debugfs/Makefile.in @@ -17,11 +17,12 @@ MANPAGES= debugfs.8 MK_CMDS= _SS_DIR_OVERRIDE=../lib/ss ../lib/ss/mk_cmds DEBUG_OBJS= debug_cmds.o debugfs.o util.o ncheck.o icheck.o ls.o \ - lsdel.o dump.o setsuper.o logdump.o + lsdel.o dump.o setsuper.o logdump.o htree.o SRCS= debug_cmds.c $(srcdir)/debugfs.c $(srcdir)/util.c $(srcdir)/ls.c \ $(srcdir)/ncheck.c $(srcdir)/icheck.c $(srcdir)/lsdel.c \ - $(srcdir)/dump.c $(srcdir)/setsuper.c ${srcdir}/logdump.c + $(srcdir)/dump.c $(srcdir)/setsuper.c ${srcdir}/logdump.c \ + $(srcdir)/htree.c LIBS= $(LIBEXT2FS) $(LIBE2P) $(LIBSS) $(LIBCOM_ERR) $(LIBUUID) DEPLIBS= $(LIBEXT2FS) $(LIBE2P) $(LIBSS) $(LIBCOM_ERR) $(DEPLIBUUID) diff --git a/debugfs/debug_cmds.ct b/debugfs/debug_cmds.ct index 63f9c0a..96d972e 100644 --- a/debugfs/debug_cmds.ct +++ b/debugfs/debug_cmds.ct @@ -127,5 +127,14 @@ request do_set_super, "Set superblock value", request do_logdump, "Dump the contents of the journal", logdump; +request do_htree_dump, "Dump a hash-indexed directory", + htree_dump, htree; + +request do_dx_hash, "Calculate the directory hash of a filename", + dx_hash, hash; + +request do_dirsearch, "Search a directory for a particular filename", + dirsearch; + end; diff --git a/debugfs/htree.c b/debugfs/htree.c new file mode 100644 index 0000000..86909a7 --- /dev/null +++ b/debugfs/htree.c @@ -0,0 +1,364 @@ +/* + * 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 +#include +#include +#include +#include +#include +#ifdef HAVE_ERRNO_H +#include +#endif +#include +#ifdef HAVE_GETOPT_H +#include +#else +extern int optind; +extern char *optarg; +#endif +#ifdef HAVE_OPTRESET +extern int optreset; /* defined by BSD, but not others */ +#endif + +#include "debugfs.h" + +static FILE *pager; + +static unsigned dx_hack_hash (const char *name, int len) +{ + __u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; + while (len--) { + __u32 hash = hash1 + (hash0 ^ (*name++ * 7152373)); + + if (hash & 0x80000000) hash -= 0x7fffffff; + hash1 = hash0; + hash0 = hash; + } + return hash0; +} + +#define dx_hash(s,n) (dx_hack_hash(s,n) << 1) + +static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino, + struct ext2_inode *inode, + blk_t blk, char *buf) +{ + errcode_t errcode; + struct ext2_dir_entry *dirent; + int thislen, col = 0, offset = 0; + char name[EXT2_NAME_LEN]; + char tmp[EXT2_NAME_LEN + 16]; + blk_t pblk; + + errcode = ext2fs_bmap(fs, ino, inode, buf, 0, blk, &pblk); + if (errcode) { + com_err("htree_dump_leaf_node", errcode, + "while mapping logical block %d\n", blk); + return; + } + + errcode = io_channel_read_blk(current_fs->io, pblk, 1, buf); + if (errcode) { + com_err("htree_dump_leaf_node", errcode, + "while reading block %d\n", blk); + return; + } + + while (offset < fs->blocksize) { + dirent = (struct ext2_dir_entry *) (buf + offset); + if (((offset + dirent->rec_len) > fs->blocksize) || + (dirent->rec_len < 8) || + ((dirent->rec_len % 4) != 0) || + (((dirent->name_len & 0xFF)+8) > dirent->rec_len)) { + fprintf(pager, "Corrupted directory block (%d)!\n", blk); + break; + } + thislen = ((dirent->name_len & 0xFF) < EXT2_NAME_LEN) ? + (dirent->name_len & 0xFF) : EXT2_NAME_LEN; + strncpy(name, dirent->name, thislen); + name[thislen] = '\0'; + sprintf(tmp, "%u 0x%08x (%d) %s ", dirent->inode, + dx_hash(name, thislen), dirent->rec_len, name); + thislen = strlen(tmp); + if (col + thislen > 80) { + fprintf(pager, "\n"); + col = 0; + } + fprintf(pager, "%s", tmp); + col += thislen; + offset += dirent->rec_len; + } + fprintf(pager, "\n"); +} + + +static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino, + struct ext2_inode *inode, + blk_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_entry *ent, + char *buf, int level) +{ + struct ext2_dx_countlimit *limit; + int i; + + limit = (struct ext2_dx_countlimit *) ent; + + fprintf(pager, "Number of entries (count): %d\n", limit->count); + fprintf(pager, "Number of entries (limit): %d\n", limit->limit); + + for (i=0; i < limit->count; i++) + fprintf(pager, "Entry #%d: Hash 0x%08x, block %d\n", i, + i ? ent[i].hash : 0, ent[i].block); + + fprintf(pager, "\n"); + + for (i=0; i < limit->count; i++) { + fprintf(pager, "Entry #%d: Hash 0x%08x, block %d\n", i, + i ? ent[i].hash : 0, ent[i].block); + if (level) + htree_dump_int_block(fs, ino, inode, + ent[i].block, buf, level-1); + else + htree_dump_leaf_node(fs, ino, inode, + ent[i].block, buf); + } + + fprintf(pager, "---------------------\n"); +} + +static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino, + struct ext2_inode *inode, + blk_t blk, char *buf, int level) +{ + char *cbuf; + errcode_t errcode; + blk_t pblk; + + cbuf = malloc(fs->blocksize); + if (!cbuf) { + fprintf(pager, "Couldn't allocate child block.\n"); + return; + } + + errcode = ext2fs_bmap(fs, ino, inode, buf, 0, blk, &pblk); + if (errcode) { + com_err("htree_dump_int_block", errcode, + "while mapping logical block %d\n", blk); + return; + } + + errcode = io_channel_read_blk(current_fs->io, pblk, 1, buf); + if (errcode) { + com_err("htree_dump_int_block", errcode, + "while reading block %d\n", blk); + return; + } + + htree_dump_int_node(fs, ino, inode, (struct ext2_dx_entry *) (buf+8), + cbuf, level); + free(cbuf); +} + + + +void do_htree_dump(int argc, char *argv[]) +{ + ext2_ino_t ino; + struct ext2_inode inode; + int retval; + int i, c; + int flags; + int long_opt; + void *buf = NULL; + struct ext2_dx_root_info *root; + struct ext2_dx_entry *ent; + struct ext2_dx_countlimit *limit; + errcode_t errcode; + + if (check_fs_open(argv[0])) + return; + + pager = open_pager(); + + optind = 0; +#ifdef HAVE_OPTRESET + optreset = 1; /* Makes BSD getopt happy */ +#endif + while ((c = getopt (argc, argv, "l")) != EOF) { + switch (c) { + case 'l': + long_opt++; + break; + } + } + + if (argc > optind+1) { + com_err(0, 0, "Usage: htree_dump [-l] file"); + return; + } + + if (argc == optind) + ino = cwd; + else + ino = string_to_inode(argv[optind]); + if (!ino) + return; + + if (debugfs_read_inode(ino, &inode, argv[1])) + return; + + if (!LINUX_S_ISDIR(inode.i_mode)) { + com_err(argv[0], 0, "Not a directory"); + return; + } + + if ((inode.i_flags & EXT2_BTREE_FL) == 0) { + com_err(argv[0], 0, "Not a hash-indexed directory"); + return; + } + + buf = malloc(2*current_fs->blocksize); + if (!buf) { + com_err(argv[0], 0, "Couldn't allocate htree buffer"); + return; + } + + errcode = io_channel_read_blk(current_fs->io, inode.i_block[0], + 1, buf); + if (errcode) { + com_err(argv[0], errcode, "Error reading root node"); + goto errout; + } + + root = (struct ext2_dx_root_info *) (buf + 24); + + fprintf(pager, "Root node dump:\n"); + fprintf(pager, "\t Reserved zero: %d\n", root->reserved_zero); + fprintf(pager, "\t Hash Version: %d\n", root->hash_version); + fprintf(pager, "\t Info length: %d\n", root->info_length); + fprintf(pager, "\t Indirect levels: %d\n", root->indirect_levels); + fprintf(pager, "\t Flags: %d\n", root->unused_flags); + + ent = (struct ext2_dx_entry *) (buf + 24 + root->info_length); + limit = (struct ext2_dx_countlimit *) ent; + + htree_dump_int_node(current_fs, ino, &inode, ent, + buf + current_fs->blocksize, + root->indirect_levels); + +errout: + if (buf) + free(buf); + close_pager(pager); +} + +/* + * This function prints the hash of a given file. + */ +void do_dx_hash(int argc, char *argv[]) +{ + if (argc != 2) { + com_err(argv[0], 0, "usage: dx_hash filename"); + return; + } + printf("Hash of %s is 0x%0x\n", argv[1], + dx_hash(argv[1], strlen(argv[1]))); +} + +/* + * 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, blk_t *blocknr, + e2_blkcnt_t blockcnt, blk_t ref_blk, + int ref_offset, void *priv_data); + +void do_dirsearch(int argc, char *argv[]) +{ + ext2_ino_t inode; + int retval; + int c; + int flags; + 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_iterate2(current_fs, inode, 0, 0, search_dir_block, &pb); + + free(pb.buf); +} + + +static int search_dir_block(ext2_filsys fs, blk_t *blocknr, + e2_blkcnt_t blockcnt, blk_t ref_blk, + int ref_offset, void *priv_data) +{ + struct process_block_struct *p; + struct ext2_dir_entry *dirent; + errcode_t errcode; + int offset = 0; + + if (blockcnt < 0) + return 0; + + p = (struct process_block_struct *) priv_data; + + errcode = io_channel_read_blk(current_fs->io, *blocknr, 1, p->buf); + if (errcode) { + com_err("search_dir_block", errcode, + "while reading block %lu", *blocknr); + return BLOCK_ABORT; + } + + while (offset < fs->blocksize) { + dirent = (struct ext2_dir_entry *) (p->buf + offset); + + if (dirent->inode && + p->len == (dirent->name_len & 0xFF) && + strncmp(p->search_name, dirent->name, + p->len) == 0) { + printf("Entry found at logical block %lld, " + "phys %d, offset %d\n", blockcnt, + *blocknr, offset); + printf("offset %d\n", offset); + return BLOCK_ABORT; + } + offset += dirent->rec_len; + } + return 0; +} + diff --git a/debugfs/util.c b/debugfs/util.c index 183a5f6..fa13da4 100644 --- a/debugfs/util.c +++ b/debugfs/util.c @@ -22,14 +22,16 @@ FILE *open_pager(void) const char *pager = getenv("PAGER"); signal(SIGPIPE, SIG_IGN); - if (!pager) + if (pager) { + if (strcmp(pager, "__none__") == 0) { + return stdout; + } + } else pager = "more"; outfile = popen(pager, "w"); - if (!outfile) - outfile = stdout; - return (outfile); + return (outfile ? outfile : stdout); } void close_pager(FILE *stream) diff --git a/lib/ext2fs/ChangeLog b/lib/ext2fs/ChangeLog index 4ed0472..4d0f646 100644 --- a/lib/ext2fs/ChangeLog +++ b/lib/ext2fs/ChangeLog @@ -1,3 +1,8 @@ +2002-02-25 Theodore Tso + + * ext2_fs.h: Add structure definitions for the directory indexing + extension. + 2002-02-23 Theodore Tso * unix_io.c (unix_open): Fix 2.4 resource limit workaround so that diff --git a/lib/ext2fs/ext2_fs.h b/lib/ext2fs/ext2_fs.h index 38649df..1143965 100644 --- a/lib/ext2fs/ext2_fs.h +++ b/lib/ext2fs/ext2_fs.h @@ -147,6 +147,37 @@ struct ext2_group_desc }; /* + * Data structures used by the directory indexing feature + * + * Note: all of the multibyte integer fields are little endian. + */ + +/* + * Note: dx_root_info is laid out so that if it should somehow get + * overlaid by a dirent the two low bits of the hash version will be + * zero. Therefore, the hash version mod 4 should never be 0. + * Sincerely, the paranoia department. + */ +struct ext2_dx_root_info { + __u32 reserved_zero; + __u8 hash_version; /* 0 now, 1 at release */ + __u8 info_length; /* 8 */ + __u8 indirect_levels; + __u8 unused_flags; +}; + +struct ext2_dx_entry { + __u32 hash; + __u32 block; +}; + +struct ext2_dx_countlimit { + __u16 limit; + __u16 count; +}; + + +/* * Macro-instructions used to manage group descriptors */ #ifdef __KERNEL__ -- 1.8.3.1