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 27 static FILE *pager; 28 29 static 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 + 1]; 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 96 static 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 102 static 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 145 static 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 goto errout; 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 goto errout; 172 } 173 174 htree_dump_int_node(fs, ino, inode, rootnode, 175 (struct ext2_dx_entry *) (buf+8), 176 cbuf, level); 177 errout: 178 free(cbuf); 179 } 180 181 182 183 void do_htree_dump(int argc, char *argv[]) 184 { 185 ext2_ino_t ino; 186 struct ext2_inode inode; 187 int c; 188 int long_opt = 0; 189 char *buf = NULL; 190 struct ext2_dx_root_info *rootnode; 191 struct ext2_dx_entry *ent; 192 struct ext2_dx_countlimit *limit; 193 errcode_t errcode; 194 195 if (check_fs_open(argv[0])) 196 return; 197 198 pager = open_pager(); 199 200 reset_getopt(); 201 while ((c = getopt (argc, argv, "l")) != EOF) { 202 switch (c) { 203 case 'l': 204 long_opt++; 205 break; 206 default: 207 goto print_usage; 208 } 209 } 210 211 if (argc > optind+1) { 212 print_usage: 213 com_err(0, 0, "Usage: htree_dump [-l] file"); 214 goto errout; 215 } 216 217 if (argc == optind) 218 ino = cwd; 219 else 220 ino = string_to_inode(argv[optind]); 221 if (!ino) 222 goto errout; 223 224 if (debugfs_read_inode(ino, &inode, argv[1])) 225 goto errout; 226 227 if (!LINUX_S_ISDIR(inode.i_mode)) { 228 com_err(argv[0], 0, "Not a directory"); 229 goto errout; 230 } 231 232 if ((inode.i_flags & EXT2_BTREE_FL) == 0) { 233 com_err(argv[0], 0, "Not a hash-indexed directory"); 234 goto errout; 235 } 236 237 buf = malloc(2*current_fs->blocksize); 238 if (!buf) { 239 com_err(argv[0], 0, "Couldn't allocate htree buffer"); 240 goto errout; 241 } 242 243 errcode = io_channel_read_blk(current_fs->io, inode.i_block[0], 244 1, buf); 245 if (errcode) { 246 com_err(argv[0], errcode, "Error reading root node"); 247 goto errout; 248 } 249 250 rootnode = (struct ext2_dx_root_info *) (buf + 24); 251 252 fprintf(pager, "Root node dump:\n"); 253 fprintf(pager, "\t Reserved zero: %u\n", rootnode->reserved_zero); 254 fprintf(pager, "\t Hash Version: %d\n", rootnode->hash_version); 255 fprintf(pager, "\t Info length: %d\n", rootnode->info_length); 256 fprintf(pager, "\t Indirect levels: %d\n", rootnode->indirect_levels); 257 fprintf(pager, "\t Flags: %d\n", rootnode->unused_flags); 258 259 ent = (struct ext2_dx_entry *) (buf + 24 + rootnode->info_length); 260 limit = (struct ext2_dx_countlimit *) ent; 261 262 htree_dump_int_node(current_fs, ino, &inode, rootnode, ent, 263 buf + current_fs->blocksize, 264 rootnode->indirect_levels); 265 266 errout: 267 if (buf) 268 free(buf); 269 close_pager(pager); 270 } 271 272 /* 273 * This function prints the hash of a given file. 274 */ 275 void do_dx_hash(int argc, char *argv[]) 276 { 277 ext2_dirhash_t hash, minor_hash; 278 errcode_t err; 279 int c; 280 int hash_version = 0; 281 __u32 hash_seed[4]; 282 283 hash_seed[0] = hash_seed[1] = hash_seed[2] = hash_seed[3] = 0; 284 285 reset_getopt(); 286 while ((c = getopt (argc, argv, "h:")) != EOF) { 287 switch (c) { 288 case 'h': 289 hash_version = atoi(optarg); 290 break; 291 default: 292 goto print_usage; 293 } 294 } 295 if (optind != argc-1) { 296 print_usage: 297 com_err(argv[0], 0, "usage: dx_hash filename"); 298 return; 299 } 300 err = ext2fs_dirhash(hash_version, argv[optind], strlen(argv[optind]), 301 hash_seed, &hash, &minor_hash); 302 if (err) { 303 com_err(argv[0], err, "while caclulating hash"); 304 return; 305 } 306 printf("Hash of %s is 0x%0x (minor 0x%0x)\n", argv[optind], 307 hash, minor_hash); 308 } 309 310 /* 311 * Search for particular directory entry (useful for debugging very 312 * large hash tree directories that have lost some blocks from the 313 * btree index). 314 */ 315 struct process_block_struct { 316 char *search_name; 317 char *buf; 318 int len; 319 }; 320 321 static int search_dir_block(ext2_filsys fs, blk_t *blocknr, 322 e2_blkcnt_t blockcnt, blk_t ref_blk, 323 int ref_offset, void *priv_data); 324 325 void do_dirsearch(int argc, char *argv[]) 326 { 327 ext2_ino_t inode; 328 struct process_block_struct pb; 329 330 if (check_fs_open(argv[0])) 331 return; 332 333 if (argc != 3) { 334 com_err(0, 0, "Usage: dirsearch dir filename"); 335 return; 336 } 337 338 inode = string_to_inode(argv[1]); 339 if (!inode) 340 return; 341 342 pb.buf = malloc(current_fs->blocksize); 343 if (!pb.buf) { 344 com_err("dirsearch", 0, "Couldn't allocate buffer"); 345 return; 346 } 347 pb.search_name = argv[2]; 348 pb.len = strlen(pb.search_name); 349 350 ext2fs_block_iterate2(current_fs, inode, 0, 0, search_dir_block, &pb); 351 352 free(pb.buf); 353 } 354 355 356 static int search_dir_block(ext2_filsys fs, blk_t *blocknr, 357 e2_blkcnt_t blockcnt, 358 blk_t ref_blk EXT2FS_ATTR((unused)), 359 int ref_offset EXT2FS_ATTR((unused)), 360 void *priv_data) 361 { 362 struct process_block_struct *p; 363 struct ext2_dir_entry *dirent; 364 errcode_t errcode; 365 unsigned int offset = 0; 366 367 if (blockcnt < 0) 368 return 0; 369 370 p = (struct process_block_struct *) priv_data; 371 372 errcode = io_channel_read_blk(current_fs->io, *blocknr, 1, p->buf); 373 if (errcode) { 374 com_err("search_dir_block", errcode, 375 "while reading block %lu", (unsigned long) *blocknr); 376 return BLOCK_ABORT; 377 } 378 379 while (offset < fs->blocksize) { 380 dirent = (struct ext2_dir_entry *) (p->buf + offset); 381 382 if (dirent->inode && 383 p->len == (dirent->name_len & 0xFF) && 384 strncmp(p->search_name, dirent->name, 385 p->len) == 0) { 386 printf("Entry found at logical block %lld, " 387 "phys %u, offset %u\n", (long long)blockcnt, 388 *blocknr, offset); 389 printf("offset %u\n", offset); 390 return BLOCK_ABORT; 391 } 392 offset += dirent->rec_len; 393 } 394 return 0; 395 } 396 397
