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
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)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
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)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
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)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
do_htree_dump(int argc,char * argv[])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 */
do_dx_hash(int argc,char * argv[])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
do_dirsearch(int argc,char * argv[])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
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)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