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
htree_dump_leaf_node(ext2_filsys fs,ext2_ino_t ino,struct ext2_inode * inode,struct ext2_dx_root_info * rootnode,blk_t blk,char * buf)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
htree_dump_int_node(ext2_filsys fs,ext2_ino_t ino,struct ext2_inode * inode,struct ext2_dx_root_info * rootnode,struct ext2_dx_entry * ent,char * buf,int level)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
htree_dump_int_block(ext2_filsys fs,ext2_ino_t ino,struct ext2_inode * inode,struct ext2_dx_root_info * rootnode,blk_t blk,char * buf,int level)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
do_htree_dump(int argc,char * argv[])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 */
do_dx_hash(int argc,char * argv[])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
do_dirsearch(int argc,char * argv[])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
search_dir_block(ext2_filsys fs,blk_t * blocknr,e2_blkcnt_t blockcnt,blk_t ref_blk EXT2FS_ATTR ((unused)),int ref_offset EXT2FS_ATTR ((unused)),void * priv_data)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