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