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