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