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 21 extern int optind; 22 extern char *optarg; 23 #endif 24 25 #include "debugfs.h" 26 #include "uuid/uuid.h" 27 #include "e2p/e2p.h" 28 29 static FILE *pager; 30 31 static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino, 32 struct ext2_inode *inode, 33 struct ext2_dx_root_info * rootnode, 34 blk_t blk, char *buf) 35 { 36 errcode_t errcode; 37 struct ext2_dir_entry *dirent; 38 int thislen, col = 0; 39 unsigned int offset = 0; 40 char name[EXT2_NAME_LEN + 1]; 41 char tmp[EXT2_NAME_LEN + 16]; 42 blk_t pblk; 43 ext2_dirhash_t hash, minor_hash; 44 unsigned int rec_len; 45 int hash_alg; 46 47 errcode = ext2fs_bmap(fs, ino, inode, buf, 0, blk, &pblk); 48 if (errcode) { 49 com_err("htree_dump_leaf_node", errcode, 50 "while mapping logical block %u\n", blk); 51 return; 52 } 53 54 printf("Reading directory block %lu, phys %lu\n", 55 (unsigned long) blk, (unsigned long) 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 %lu (%lu)\n", 60 (unsigned long) blk, (unsigned long) 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 (%u)!\n", blk); 82 break; 83 } 84 thislen = ((dirent->name_len & 0xFF) < EXT2_NAME_LEN) ? 85 (dirent->name_len & 0xFF) : EXT2_NAME_LEN; 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 sprintf(tmp, "%u 0x%08x-%08x (%d) %s ", dirent->inode, 95 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 109 static 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 blk_t blk, char *buf, int level); 113 114 115 static 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 158 static 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 blk_t blk, char *buf, int level) 162 { 163 char *cbuf; 164 errcode_t errcode; 165 blk_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_bmap(fs, ino, inode, buf, 0, blk, &pblk); 174 if (errcode) { 175 com_err("htree_dump_int_block", errcode, 176 "while mapping logical block %u\n", blk); 177 goto errout; 178 } 179 180 errcode = io_channel_read_blk(current_fs->io, pblk, 1, buf); 181 if (errcode) { 182 com_err("htree_dump_int_block", errcode, 183 "while reading block %u\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); 190 errout: 191 free(cbuf); 192 } 193 194 195 196 void do_htree_dump(int argc, char *argv[]) 197 { 198 ext2_ino_t ino; 199 struct ext2_inode inode; 200 int c; 201 int long_opt = 0; 202 blk_t blk; 203 char *buf = NULL; 204 struct ext2_dx_root_info *rootnode; 205 struct ext2_dx_entry *ent; 206 struct ext2_dx_countlimit *limit; 207 errcode_t errcode; 208 209 if (check_fs_open(argv[0])) 210 return; 211 212 pager = open_pager(); 213 214 reset_getopt(); 215 while ((c = getopt (argc, argv, "l")) != EOF) { 216 switch (c) { 217 case 'l': 218 long_opt++; 219 break; 220 default: 221 goto print_usage; 222 } 223 } 224 225 if (argc > optind+1) { 226 print_usage: 227 com_err(0, 0, "Usage: htree_dump [-l] file"); 228 goto errout; 229 } 230 231 if (argc == optind) 232 ino = cwd; 233 else 234 ino = string_to_inode(argv[optind]); 235 if (!ino) 236 goto errout; 237 238 if (debugfs_read_inode(ino, &inode, argv[1])) 239 goto errout; 240 241 if (!LINUX_S_ISDIR(inode.i_mode)) { 242 com_err(argv[0], 0, "Not a directory"); 243 goto errout; 244 } 245 246 if ((inode.i_flags & EXT2_BTREE_FL) == 0) { 247 com_err(argv[0], 0, "Not a hash-indexed directory"); 248 goto errout; 249 } 250 251 buf = malloc(2*current_fs->blocksize); 252 if (!buf) { 253 com_err(argv[0], 0, "Couldn't allocate htree buffer"); 254 goto errout; 255 } 256 257 errcode = ext2fs_bmap(current_fs, ino, &inode, buf, 0, 0, &blk); 258 if (errcode) { 259 com_err("do_htree_block", errcode, 260 "while mapping logical block 0\n"); 261 goto errout; 262 } 263 264 errcode = io_channel_read_blk(current_fs->io, blk, 265 1, buf); 266 if (errcode) { 267 com_err(argv[0], errcode, "Error reading root node"); 268 goto errout; 269 } 270 271 rootnode = (struct ext2_dx_root_info *) (buf + 24); 272 273 fprintf(pager, "Root node dump:\n"); 274 fprintf(pager, "\t Reserved zero: %u\n", rootnode->reserved_zero); 275 fprintf(pager, "\t Hash Version: %d\n", rootnode->hash_version); 276 fprintf(pager, "\t Info length: %d\n", rootnode->info_length); 277 fprintf(pager, "\t Indirect levels: %d\n", rootnode->indirect_levels); 278 fprintf(pager, "\t Flags: %d\n", rootnode->unused_flags); 279 280 ent = (struct ext2_dx_entry *) (buf + 24 + rootnode->info_length); 281 limit = (struct ext2_dx_countlimit *) ent; 282 283 htree_dump_int_node(current_fs, ino, &inode, rootnode, ent, 284 buf + current_fs->blocksize, 285 rootnode->indirect_levels); 286 287 errout: 288 free(buf); 289 close_pager(pager); 290 } 291 292 /* 293 * This function prints the hash of a given file. 294 */ 295 void do_dx_hash(int argc, char *argv[]) 296 { 297 ext2_dirhash_t hash, minor_hash; 298 errcode_t err; 299 int c; 300 int hash_version = 0; 301 __u32 hash_seed[4]; 302 303 hash_seed[0] = hash_seed[1] = hash_seed[2] = hash_seed[3] = 0; 304 305 reset_getopt(); 306 while ((c = getopt (argc, argv, "h:s:")) != EOF) { 307 switch (c) { 308 case 'h': 309 hash_version = e2p_string2hash(optarg); 310 if (hash_version < 0) 311 hash_version = atoi(optarg); 312 break; 313 case 's': 314 if (uuid_parse(optarg, (unsigned char *) hash_seed)) { 315 fprintf(stderr, "Invalid UUID format: %s\n", 316 optarg); 317 return; 318 } 319 break; 320 default: 321 goto print_usage; 322 } 323 } 324 if (optind != argc-1) { 325 print_usage: 326 com_err(argv[0], 0, "usage: dx_hash [-h hash_alg] " 327 "[-s hash_seed] filename"); 328 return; 329 } 330 err = ext2fs_dirhash(hash_version, argv[optind], strlen(argv[optind]), 331 hash_seed, &hash, &minor_hash); 332 if (err) { 333 com_err(argv[0], err, "while caclulating hash"); 334 return; 335 } 336 printf("Hash of %s is 0x%0x (minor 0x%0x)\n", argv[optind], 337 hash, minor_hash); 338 } 339 340 /* 341 * Search for particular directory entry (useful for debugging very 342 * large hash tree directories that have lost some blocks from the 343 * btree index). 344 */ 345 struct process_block_struct { 346 char *search_name; 347 char *buf; 348 int len; 349 }; 350 351 static int search_dir_block(ext2_filsys fs, blk_t *blocknr, 352 e2_blkcnt_t blockcnt, blk_t ref_blk, 353 int ref_offset, void *priv_data); 354 355 void do_dirsearch(int argc, char *argv[]) 356 { 357 ext2_ino_t inode; 358 struct process_block_struct pb; 359 360 if (check_fs_open(argv[0])) 361 return; 362 363 if (argc != 3) { 364 com_err(0, 0, "Usage: dirsearch dir filename"); 365 return; 366 } 367 368 inode = string_to_inode(argv[1]); 369 if (!inode) 370 return; 371 372 pb.buf = malloc(current_fs->blocksize); 373 if (!pb.buf) { 374 com_err("dirsearch", 0, "Couldn't allocate buffer"); 375 return; 376 } 377 pb.search_name = argv[2]; 378 pb.len = strlen(pb.search_name); 379 380 ext2fs_block_iterate2(current_fs, inode, BLOCK_FLAG_READ_ONLY, 0, 381 search_dir_block, &pb); 382 383 free(pb.buf); 384 } 385 386 387 static int search_dir_block(ext2_filsys fs, blk_t *blocknr, 388 e2_blkcnt_t blockcnt, 389 blk_t ref_blk EXT2FS_ATTR((unused)), 390 int ref_offset EXT2FS_ATTR((unused)), 391 void *priv_data) 392 { 393 struct process_block_struct *p; 394 struct ext2_dir_entry *dirent; 395 errcode_t errcode; 396 unsigned int offset = 0; 397 unsigned int rec_len; 398 399 if (blockcnt < 0) 400 return 0; 401 402 p = (struct process_block_struct *) priv_data; 403 404 errcode = io_channel_read_blk(current_fs->io, *blocknr, 1, p->buf); 405 if (errcode) { 406 com_err("search_dir_block", errcode, 407 "while reading block %lu", (unsigned long) *blocknr); 408 return BLOCK_ABORT; 409 } 410 411 while (offset < fs->blocksize) { 412 dirent = (struct ext2_dir_entry *) (p->buf + offset); 413 errcode = ext2fs_get_rec_len(fs, dirent, &rec_len); 414 if (errcode) { 415 com_err("htree_dump_leaf_inode", errcode, 416 "while getting rec_len for block %lu", 417 (unsigned long) *blocknr); 418 return BLOCK_ABORT; 419 } 420 if (dirent->inode && 421 p->len == (dirent->name_len & 0xFF) && 422 strncmp(p->search_name, dirent->name, 423 p->len) == 0) { 424 printf("Entry found at logical block %lld, " 425 "phys %u, offset %u\n", (long long)blockcnt, 426 *blocknr, offset); 427 printf("offset %u\n", offset); 428 return BLOCK_ABORT; 429 } 430 offset += rec_len; 431 } 432 return 0; 433 } 434 435
