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