]> git.ipfire.org Git - thirdparty/e2fsprogs.git/commitdiff
Add support for the half-MD4 HTREE hash.
authorTheodore Ts'o <tytso@mit.edu>
Wed, 26 Jun 2002 20:52:10 +0000 (16:52 -0400)
committerTheodore Ts'o <tytso@mit.edu>
Wed, 26 Jun 2002 20:52:10 +0000 (16:52 -0400)
Add HTREE root node tests.

18 files changed:
debugfs/ChangeLog
debugfs/htree.c
e2fsck/ChangeLog
e2fsck/pass1.c
e2fsck/pass2.c
e2fsck/problem.c
e2fsck/problem.h
lib/ext2fs/ChangeLog
lib/ext2fs/dirhash.c
lib/ext2fs/ext2_fs.h
lib/ext2fs/ext2fs.h
tests/ChangeLog
tests/f_h_badroot/expect.1 [new file with mode: 0644]
tests/f_h_badroot/expect.2 [new file with mode: 0644]
tests/f_h_badroot/image.gz [new file with mode: 0644]
tests/f_h_badroot/name [new file with mode: 0644]
tests/f_h_badroot/script [new file with mode: 0644]
tests/f_h_normal/script~ [deleted file]

index 360b5452a8572656228e2fb8bc79c37b0967d149..c8768ec8160099a4a5ae01b5ebc81c339924e1f9 100644 (file)
@@ -1,3 +1,8 @@
+2002-06-26  Theodore Ts'o  <tytso@mit.edu>
+
+       * htree.c (do_dx_hash): Use new ext2fs_dirhash function signature.
+               Add getopt support so user can specify the hash version.
+
 2002-05-11    <tytso@snap.thunk.org>
 
        * debug_cmds.ct, debugfs.c (do_bmap): Add new command "bmap" which
index a6d4eef27da4bcce06e6bb48f40917076b9033e8..0da7c55d33620b43389a33614a3539944273b7d7 100644 (file)
@@ -31,6 +31,7 @@ static FILE *pager;
 
 static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino,
                                 struct ext2_inode *inode,
+                                struct ext2_dx_root_info * root,
                                 blk_t blk, char *buf)
 {
        errcode_t       errcode;
@@ -68,7 +69,9 @@ static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino,
                        (dirent->name_len & 0xFF) : EXT2_NAME_LEN;
                strncpy(name, dirent->name, thislen);
                name[thislen] = '\0';
-               errcode = ext2fs_dirhash(0, name, thislen, &hash);
+               errcode = ext2fs_dirhash(root->hash_version, name, thislen, 
+                                        fs->super->s_hash_seed,
+                                        &hash, 0);
                if (errcode)
                        com_err("htree_dump_leaf_node", errcode,
                                "while calculating hash");
@@ -89,11 +92,13 @@ static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino,
 
 static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino,
                                 struct ext2_inode *inode,
+                                struct ext2_dx_root_info * root,
                                 blk_t blk, char *buf, int level);
 
 
 static void htree_dump_int_node(ext2_filsys fs, ext2_ino_t ino,
                                struct ext2_inode *inode,
+                               struct ext2_dx_root_info * root,
                                struct ext2_dx_entry *ent, 
                                char *buf, int level)
 {
@@ -115,10 +120,10 @@ static void htree_dump_int_node(ext2_filsys fs, ext2_ino_t ino,
                fprintf(pager, "Entry #%d: Hash 0x%08x, block %d\n", i,
                       i ? ent[i].hash : 0, ent[i].block);
                if (level)
-                       htree_dump_int_block(fs, ino, inode,
+                       htree_dump_int_block(fs, ino, inode, root,
                                             ent[i].block, buf, level-1);
                else
-                       htree_dump_leaf_node(fs, ino, inode,
+                       htree_dump_leaf_node(fs, ino, inode, root,
                                             ent[i].block, buf);
        }
 
@@ -127,6 +132,7 @@ static void htree_dump_int_node(ext2_filsys fs, ext2_ino_t ino,
 
 static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino,
                                 struct ext2_inode *inode,
+                                struct ext2_dx_root_info * root,
                                 blk_t blk, char *buf, int level)
 {
        char            *cbuf;
@@ -153,7 +159,8 @@ static void htree_dump_int_block(ext2_filsys fs, ext2_ino_t ino,
                return;
        }
 
-       htree_dump_int_node(fs, ino, inode, (struct ext2_dx_entry *) (buf+8),
+       htree_dump_int_node(fs, ino, inode, root,
+                           (struct ext2_dx_entry *) (buf+8),
                            cbuf, level);
        free(cbuf);
 }
@@ -241,7 +248,7 @@ void do_htree_dump(int argc, char *argv[])
        ent = (struct ext2_dx_entry *) (buf + 24 + root->info_length);
        limit = (struct ext2_dx_countlimit *) ent;
 
-       htree_dump_int_node(current_fs, ino, &inode, ent,
+       htree_dump_int_node(current_fs, ino, &inode, root, ent,
                            buf + current_fs->blocksize,
                            root->indirect_levels);
 
@@ -256,19 +263,36 @@ errout:
  */
 void do_dx_hash(int argc, char *argv[])
 {
-       ext2_dirhash_t hash;
+       ext2_dirhash_t hash, minor_hash;
        errcode_t       err;
+       int             c;
+       int             hash_version = 0;
+       __u32           hash_seed[4];
        
-       if (argc != 2) {
+       hash_seed[0] = hash_seed[1] = hash_seed[2] = hash_seed[3] = 0;
+       optind = 0;
+#ifdef HAVE_OPTRESET
+       optreset = 1;           /* Makes BSD getopt happy */
+#endif
+       while ((c = getopt (argc, argv, "h:")) != EOF) {
+               switch (c) {
+               case 'h':
+                       hash_version = atoi(optarg);
+                       break;
+               }
+       }
+       if (optind != argc-1) {
                com_err(argv[0], 0, "usage: dx_hash filename");
                return;
        }
-       err = ext2fs_dirhash(0, argv[1], strlen(argv[1]), &hash);
+       err = ext2fs_dirhash(hash_version, argv[optind], strlen(argv[optind]),
+                            hash_seed, &hash, &minor_hash);
        if (err) {
                com_err(argv[0], err, "while caclulating hash");
                return;
        }
-       printf("Hash of %s is 0x%0x\n", argv[1], hash);
+       printf("Hash of %s is 0x%0x (minor 0x%0x)\n", argv[optind],
+              hash, minor_hash);
 }
 
 /*
index ca623e95e8813185ef10ed347a779841d377d687..198d6f5bc973875de5724820fae52112b6b09d61 100644 (file)
@@ -1,3 +1,23 @@
+2002-06-26  Theodore Ts'o  <tytso@mit.edu>
+
+       * pass1.c (check_blocks): Move htree handling to handle_htree().
+               Factor out calls to ext2fs_write_inode so that it happens
+               if dirty_inode is non-zero.
+               (handle_htree): Add checks for invalid htree root, invalid
+               hash version, invalid hash version, and htree depth too deep.
+
+       * problem.h, problem.c (PR_1_HTREE_NODIR, PR_1_HTREE_BADROOT,
+               PR_1_HTREE_HASHV, PR_1_HTREE_INCOMPAT, PR_1_HTREE_DEPTH): 
+               Add new problem codes.
+
+       * pass2.c (parse_int_node): Fix silly typo.
+               (check_dir_block): Change to use new ext2fs_dirhash()
+               function prototype.
+               (pass2): Fixed two minor bugs discovered by the test case:
+               Don't stop checking dxdir's after clearing a bad inode.  
+               If there is a bad max hash, make sure the bad_dir flag
+               is set to make sure we try to clear inode.
+
 2002-06-25  Theodore Ts'o  <tytso@mit.edu>
 
        * e2fsck.c (e2fsck_reset_context): Free the dx_dirinfo structure.
index 5bb99bcc0e09aa88cf38a09fc1278f500a82da20..8bc35a2cc30314bc4ba05ddc96cb507858329fda 100644 (file)
@@ -1132,6 +1132,57 @@ clear_extattr:
        return 0;
 }
 
+/* Returns 1 if bad htree, 0 if OK */
+static int handle_htree(e2fsck_t ctx, struct problem_context *pctx,
+                       ext2_ino_t ino, struct ext2_inode *inode,
+                       char *block_buf)
+{
+       struct ext2_dx_root_info        *root;
+       ext2_filsys                     fs = ctx->fs;
+       errcode_t                       retval;
+       blk_t                           blk;
+
+       if ((!LINUX_S_ISDIR(inode->i_mode) &&
+            fix_problem(ctx, PR_1_HTREE_NODIR, pctx)) ||
+           (!(fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) &&
+            fix_problem(ctx, PR_1_HTREE_SET, pctx)))
+               return 1;
+
+       blk = inode->i_block[0];
+       if (((blk == 0) ||
+            (blk < fs->super->s_first_data_block) ||
+            (blk >= fs->super->s_blocks_count)) &&
+           fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
+               return 1;
+
+       retval = io_channel_read_blk(fs->io, blk, 1, block_buf);
+       if (retval && fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
+               return 1;
+       
+       /* XXX should check that beginning matches a directory */
+       root = (struct ext2_dx_root_info *) (block_buf + 24);
+
+       if ((root->reserved_zero || root->info_length < 8) &&
+           fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
+               return 1;
+
+       pctx->num = root->hash_version;
+       if ((root->hash_version != EXT2_HASH_LEGACY) &&
+           (root->hash_version != EXT2_HASH_HALF_MD4) &&
+           fix_problem(ctx, PR_1_HTREE_HASHV, pctx))
+               return 1;
+               
+       if ((root->unused_flags & EXT2_HASH_FLAG_INCOMPAT) &&
+           fix_problem(ctx, PR_1_HTREE_INCOMPAT, pctx))
+               return 1;
+
+       pctx->num = root->indirect_levels;
+       if ((root->indirect_levels > 1) &&
+           fix_problem(ctx, PR_1_HTREE_DEPTH, pctx))
+               return 1;
+       
+       return 0;
+}
 
 /*
  * This subroutine is called on each inode to account for all of the
@@ -1145,6 +1196,7 @@ static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
        ext2_ino_t      ino = pctx->ino;
        struct ext2_inode *inode = pctx->inode;
        int             bad_size = 0;
+       int             dirty_inode = 0;
        __u64           size;
        
        if (!ext2fs_inode_has_valid_blocks(inode))
@@ -1172,8 +1224,7 @@ static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
                else {
                        if (fix_problem(ctx, PR_1_COMPR_SET, pctx)) {
                                inode->i_flags &= ~EXT2_COMPRBLK_FL;
-                               e2fsck_write_inode(ctx, ino, inode,
-                                                  "check_blocks");
+                               dirty_inode++;
                        }
                }
        }
@@ -1182,7 +1233,7 @@ static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
                                       pb.is_dir ? BLOCK_FLAG_HOLE : 0,
                                       block_buf, process_block, &pb);
        if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
-               return;
+               goto out;
        end_problem_latch(ctx, PR_LATCH_BLOCK);
        end_problem_latch(ctx, PR_LATCH_TOOBIG);
        if (pctx->errcode)
@@ -1192,11 +1243,10 @@ static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
                ctx->fs_fragmented++;
 
        if (pb.clear) {
-               e2fsck_read_inode(ctx, ino, inode, "check_blocks");
                inode->i_links_count = 0;
                ext2fs_icount_store(ctx->inode_link_info, ino, 0);
                inode->i_dtime = time(0);
-               e2fsck_write_inode(ctx, ino, inode, "check_blocks");
+               dirty_inode++;
                ext2fs_unmark_inode_bitmap(ctx->inode_dir_map, ino);
                ext2fs_unmark_inode_bitmap(ctx->inode_reg_map, ino);
                ext2fs_unmark_inode_bitmap(ctx->inode_used_map, ino);
@@ -1206,24 +1256,20 @@ static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
                 * restart the pass 1 scan.
                 */
                ctx->flags |= E2F_FLAG_RESTART;
-               return;
+               goto out;
        }
        
        if (inode->i_flags & EXT2_INDEX_FL) {
-               if (fs->super->s_feature_compat &
-                   EXT2_FEATURE_COMPAT_DIR_INDEX) {
+               if (handle_htree(ctx, pctx, ino, inode, block_buf)) {
+                       inode->i_flags &= ~EXT2_INDEX_FL;
+                       dirty_inode++;
+               } else {
 #ifdef ENABLE_HTREE
                        e2fsck_add_dx_dir(ctx, ino, pb.last_block+1);
 #endif
-               } else {
-                       if (fix_problem(ctx, PR_1_HTREE_SET, pctx)) {
-                               inode->i_flags &= ~EXT2_INDEX_FL;
-                               e2fsck_write_inode(ctx, ino, inode,
-                                                  "check_blocks");
-                       }
-               } 
+               }
        }
-
+       
        if (inode->i_file_acl && check_ext_attr(ctx, pctx, block_buf))
                pb.num_blocks++;
 
@@ -1238,7 +1284,7 @@ static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
                        inode->i_links_count = 0;
                        ext2fs_icount_store(ctx->inode_link_info, ino, 0);
                        inode->i_dtime = time(0);
-                       e2fsck_write_inode(ctx, ino, inode, "check_blocks");
+                       dirty_inode++;
                        ext2fs_unmark_inode_bitmap(ctx->inode_dir_map, ino);
                        ext2fs_unmark_inode_bitmap(ctx->inode_reg_map, ino);
                        ext2fs_unmark_inode_bitmap(ctx->inode_used_map, ino);
@@ -1270,7 +1316,7 @@ static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
                        inode->i_size = pctx->num;
                        if (LINUX_S_ISREG(inode->i_mode))
                                inode->i_size_high = pctx->num >> 32;
-                       e2fsck_write_inode(ctx, ino, inode, "check_blocks");
+                       dirty_inode++;
                }
                pctx->num = 0;
        }
@@ -1281,10 +1327,13 @@ static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
                pctx->num = pb.num_blocks;
                if (fix_problem(ctx, PR_1_BAD_I_BLOCKS, pctx)) {
                        inode->i_blocks = pb.num_blocks;
-                       e2fsck_write_inode(ctx, ino, inode, "check_blocks");
+                       dirty_inode++;
                }
                pctx->num = 0;
        }
+out:
+       if (dirty_inode)
+               e2fsck_write_inode(ctx, ino, inode, "check_blocks");
 }
 
 #if 0
@@ -1422,8 +1471,8 @@ static int process_block(ext2_filsys fs,
                        p->fragmented = 1;
        }
        p->previous_block = blk;
-       
-       if (p->is_dir && blockcnt > 2*1024*1024/fs->blocksize)
+
+       if (p->is_dir && blockcnt > (1 << (15 - fs->super->s_log_block_size)))
                problem = PR_1_TOOBIG_DIR;
        if (p->is_reg && p->num_blocks+1 >= p->max_blocks)
                problem = PR_1_TOOBIG_REG;
index 5ad529681b6af5ff7f39a94835f0befe886e52d7..4ea55942f37d23d891c875e00e1468001020698a 100644 (file)
@@ -205,6 +205,7 @@ void e2fsck_pass2(e2fsck_t ctx)
                                pctx.blk2 = dx_db->node_max_hash;
                                code = PR_2_HTREE_MAX_HASH;
                                fix_problem(ctx, code, &pctx);
+                               bad_dir++;
                        }
                        if (!(dx_db->flags & DX_FLAG_REFERENCED)) {
                                code = PR_2_HTREE_NOTREF;
@@ -221,7 +222,6 @@ void e2fsck_pass2(e2fsck_t ctx)
                if (bad_dir && fix_problem(ctx, PR_2_HTREE_CLEAR, &pctx)) {
                        clear_htree(ctx, dx_dir->ino);
                        dx_dir->ino = 0;
-                       break;
                }
 #ifdef ENABLE_HTREE_CLEAR
                if (dx_dir->ino) {
@@ -501,7 +501,7 @@ static void parse_int_node(ext2_filsys fs,
                /* Check to make sure the block is valid */
                if (blk > dx_dir->numblocks) {
                        if (fix_problem(cd->ctx, PR_2_HTREE_BADBLK,
-                                       cd->pctx)) {
+                                       &cd->pctx)) {
                                clear_htree(cd->ctx, cd->pctx.ino);
                                dx_dir->ino = 0;
                                return;
@@ -781,7 +781,8 @@ static int check_dir_block(ext2_filsys fs,
 #ifdef ENABLE_HTREE
                if (dx_db) {
                        ext2fs_dirhash(dx_dir->hashversion, dirent->name,
-                                      (dirent->name_len & 0xFF), &hash);
+                                      (dirent->name_len & 0xFF),
+                                      fs->super->s_hash_seed, &hash, 0);
                        if (hash < dx_db->min_hash)
                                dx_db->min_hash = hash;
                        if (hash > dx_db->max_hash)
index 1d4ffb1661b3a7f611792b5fd49c863724a8d09d..7f019a766bbc23f6fabefabd7e30b5edf6abea91 100644 (file)
@@ -38,7 +38,8 @@
 #define PROMPT_DELETE  15
 #define PROMPT_SUPPRESS 16
 #define PROMPT_UNLINK  17
-#define PROMPT_NULL    18
+#define PROMPT_CLEAR_HTREE 18
+#define PROMPT_NULL    19
 
 /*
  * These are the prompts which are used to ask the user if they want
@@ -63,7 +64,8 @@ static const char *prompt[] = {
        N_("Delete file"),      /* 15 */
        N_("Suppress messages"),/* 16 */
        N_("Unlink"),           /* 17 */
-       "",                     /* 18 */
+       N_("Clear HTree index"),/* 18 */
+       "",                     /* 19 */
 };
 
 /*
@@ -89,7 +91,8 @@ static const char *preen_msg[] = {
        N_("FILE DELETED"),     /* 15 */
        N_("SUPPRESSED"),       /* 16 */
        N_("UNLINKED"),         /* 17 */
-       "",                     /* 18 */
+       N_("HTREE INDEX CLEARED"),/* 18 */
+       "",                     /* 19 */
 };
 
 static const struct e2fsck_problem problem_table[] = {
@@ -668,8 +671,33 @@ static const struct e2fsck_problem problem_table[] = {
        /* INDEX_FL flag set on a non-HTREE filesystem */
        { PR_1_HTREE_SET,
          N_("@i %i has INDEX_FL flag set on @f without htree support.\n"),
-         PROMPT_CLEAR, 0 },
-
+         PROMPT_CLEAR_HTREE, 0 },
+
+       /* INDEX_FL flag set on a non-directory */      
+       { PR_1_HTREE_NODIR,
+         N_("@i %i has INDEX_FL flag set but is not a @d.\n"),
+         PROMPT_CLEAR_HTREE, 0 },
+
+       /* Invalid root node in HTREE directory */      
+       { PR_1_HTREE_BADROOT,
+         N_("@h %i has an invalid root node.\n"),
+         PROMPT_CLEAR_HTREE, 0 },
+
+       /* Unsupported hash version in HTREE directory */       
+       { PR_1_HTREE_HASHV,
+         N_("@h %i has an unsupported hash version (%N)\n"),
+         PROMPT_CLEAR_HTREE, 0 },
+
+       /* Incompatible flag in HTREE root node */      
+       { PR_1_HTREE_INCOMPAT,
+         N_("@h %i uses an incompatible htree root node flag.\n"),
+         PROMPT_CLEAR_HTREE, 0 },
+
+       /* HTREE too deep */    
+       { PR_1_HTREE_DEPTH,
+         N_("@h %i has a tree depth (%N) which is too big\n"),
+         PROMPT_CLEAR_HTREE, 0 },
+                 
        /* Pass 1b errors */
 
        /* Pass 1B: Rescan for duplicate/bad blocks */
@@ -1021,7 +1049,7 @@ static const struct e2fsck_problem problem_table[] = {
        /* Bad block in htree interior node */
        { PR_2_HTREE_BADBLK,
          N_("@p @h %d (%q): bad @b number %B.\n"),
-         PROMPT_CLEAR, 0 },
+         PROMPT_CLEAR_HTREE, 0 },
 
        /* Pass 3 errors */
 
index 1e511a3af52906575c235ab14ba500c3da1d4844..91c0bd0ccf5e033bc0f0afa7b653a4c60062cf9d 100644 (file)
@@ -388,6 +388,21 @@ struct problem_context {
 /* INDEX_FL flag set on a non-HTREE filesystem */
 #define PR_1_HTREE_SET                 0x010047
 
+/* INDEX_FL flag set on a non-directory */     
+#define PR_1_HTREE_NODIR               0x010048
+
+/* Invalid root node in HTREE directory */     
+#define PR_1_HTREE_BADROOT             0x010049
+
+/* Unsupported hash version in HTREE directory */      
+#define PR_1_HTREE_HASHV               0x01004A
+
+/* Incompatible flag in HTREE root node */     
+#define PR_1_HTREE_INCOMPAT            0x01004B
+
+/* HTREE too deep */   
+#define PR_1_HTREE_DEPTH               0x01004C
+
 /*
  * Pass 1b errors
  */
index b84275a517fa9c16a6fcbb2294f1079793f408a9..afe6f95b9e8e9a4f14d60a2890580da36f5e332f 100644 (file)
@@ -1,3 +1,10 @@
+2002-06-26  Theodore Ts'o  <tytso@mit.edu>
+
+       * dirhash.c (ext2fs_dirhash): Change function signature to support
+               a hash seed, and to return the minor hash (for 64-bit hash
+               support).   Add support for the half MD4, half MD4 with
+               seed, and half MD4 with seed and 64 bits.
+
 2002-06-15  Theodore Ts'o  <tytso@mit.edu>
 
        * ext2_fs.h (EXT2_DIRSYNC_FL): Add new file.
index 87e86d9474f468341218c0e73c1092a595d7b088..113d182ebe606fac5f7445febc58484786f48500 100644 (file)
 #include "ext2_fs.h"
 #include "ext2fs.h"
 
+/* F, G and H are basic MD4 functions: selection, majority, parity */
+#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
+#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
+#define H(x, y, z) ((x) ^ (y) ^ (z))
+
+/*
+ * The generic round function.  The application is so specific that
+ * we don't bother protecting all the arguments with parens, as is generally
+ * good macro practice, in favor of extra legibility.
+ * Rotation is separate from addition to prevent recomputation
+ */
+#define ROUND(f, a, b, c, d, x, s)     \
+       (a += f(b, c, d) + x, a = (a << s) | (a >> (32-s)))
+#define K1 0
+#define K2 013240474631UL
+#define K3 015666365641UL
+
+/*
+ * Basic cut-down MD4 transform.  Returns only 32 bits of result.
+ */
+static __u32 halfMD4Transform (__u32 buf[4], __u32 const in[])
+{
+       __u32   a = buf[0], b = buf[1], c = buf[2], d = buf[3];
+
+       /* Round 1 */
+       ROUND(F, a, b, c, d, in[0] + K1,  3);
+       ROUND(F, d, a, b, c, in[1] + K1,  7);
+       ROUND(F, c, d, a, b, in[2] + K1, 11);
+       ROUND(F, b, c, d, a, in[3] + K1, 19);
+       ROUND(F, a, b, c, d, in[4] + K1,  3);
+       ROUND(F, d, a, b, c, in[5] + K1,  7);
+       ROUND(F, c, d, a, b, in[6] + K1, 11);
+       ROUND(F, b, c, d, a, in[7] + K1, 19);
+
+       /* Round 2 */
+       ROUND(G, a, b, c, d, in[1] + K2,  3);
+       ROUND(G, d, a, b, c, in[3] + K2,  5);
+       ROUND(G, c, d, a, b, in[5] + K2,  9);
+       ROUND(G, b, c, d, a, in[7] + K2, 13);
+       ROUND(G, a, b, c, d, in[0] + K2,  3);
+       ROUND(G, d, a, b, c, in[2] + K2,  5);
+       ROUND(G, c, d, a, b, in[4] + K2,  9);
+       ROUND(G, b, c, d, a, in[6] + K2, 13);
+
+       /* Round 3 */
+       ROUND(H, a, b, c, d, in[3] + K3,  3);
+       ROUND(H, d, a, b, c, in[7] + K3,  9);
+       ROUND(H, c, d, a, b, in[2] + K3, 11);
+       ROUND(H, b, c, d, a, in[6] + K3, 15);
+       ROUND(H, a, b, c, d, in[1] + K3,  3);
+       ROUND(H, d, a, b, c, in[5] + K3,  9);
+       ROUND(H, c, d, a, b, in[0] + K3, 11);
+       ROUND(H, b, c, d, a, in[4] + K3, 15);
+
+       buf[0] += a;
+       buf[1] += b;
+       buf[2] += c;
+       buf[3] += d;
+
+       return buf[1];  /* "most hashed" word */
+       /* Alternative: return sum of all words? */
+}
+
+#undef ROUND
+#undef F
+#undef G
+#undef H
+#undef K1
+#undef K2
+#undef K3
+
+/* The old legacy hash */
 static ext2_dirhash_t dx_hack_hash (const char *name, int len)
 {
        __u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
@@ -33,19 +105,69 @@ static ext2_dirhash_t dx_hack_hash (const char *name, int len)
  * Returns the hash of a filename.  If len is 0 and name is NULL, then
  * this function can be used to test whether or not a hash version is
  * supported.
+ * 
+ * The seed is an 4 longword (32 bits) "secret" which can be used to
+ * uniquify a hash.  If the seed is all zero's, then some default seed
+ * may be used.
+ * 
+ * A particular hash version specifies whether or not the seed is
+ * represented, and whether or not the returned hash is 32 bits or 64
+ * bits.  32 bit hashes will return 0 for the minor hash.
  */
 errcode_t ext2fs_dirhash(int version, const char *name, int len,
-                        ext2_dirhash_t *ret_hash)
+                        const __u32 seed[4],
+                        ext2_dirhash_t *ret_hash,
+                        ext2_dirhash_t *ret_minor_hash)
 {
        __u32   hash;
+       __u32   minor_hash = 0;
+       char    *p;
+       int     i;
 
-       if (version == 0)
+       /* Check to see if the seed is all zero's */
+       for (i=0; i < 4; i++) {
+               if (seed[i])
+                       break;
+       }
+       
+       if (version == EXT2_HASH_LEGACY)
                hash = dx_hack_hash(name, len);
-       else {
+       else if ((version == EXT2_HASH_HALF_MD4) ||
+                (version == EXT2_HASH_HALF_MD4_SEED) ||
+                (version == EXT2_HASH_HALF_MD4_64)) {
+               char in[32];
+               __u32 buf[4];
+
+               if ((i == 4) || (version == EXT2_HASH_HALF_MD4)) {
+                       buf[0] = 0x67452301;
+                       buf[1] = 0xefcdab89;
+                       buf[2] = 0x98badcfe;
+                       buf[3] = 0x10325476;
+               } else
+                       memcpy(buf, in, sizeof(buf));
+               while (len) {
+                       if (len < 32) {
+                               memcpy(in, name, len);
+                               memset(in+len, 0, 32-len);
+                               hash = halfMD4Transform(buf, (__u32 *) in);
+                               break;
+                       }
+                       hash = halfMD4Transform(buf, (__u32 *) p);
+                       len -= 32;
+                       p += 32;
+               }
+               if (version == EXT2_HASH_HALF_MD4_64)
+                       minor_hash = buf[2];
+       } else {
                *ret_hash = 0;
                return EXT2_ET_DIRHASH_UNSUPP;
        }
        *ret_hash = hash;
+       if (ret_minor_hash)
+               *ret_minor_hash = minor_hash;
        return 0;
                
 }
+
+
+
index c47b59b4eb050ab4e3c2bdcdbb3187472be52a84..9e6a9753ed7b39bee09ec9b811185c3dc0ff33dc 100644 (file)
@@ -167,6 +167,13 @@ struct ext2_dx_root_info {
        __u8 unused_flags;
 };
 
+#define EXT2_HASH_LEGACY       0
+#define EXT2_HASH_HALF_MD4     1
+#define EXT2_HASH_HALF_MD4_SEED        2
+#define EXT2_HASH_HALF_MD4_64  3       /* SEED & 64 */
+
+#define EXT2_HASH_FLAG_INCOMPAT        0x1
+
 struct ext2_dx_entry {
        __u32 hash;
        __u32 block;
@@ -428,8 +435,8 @@ struct ext2_super_block {
        __u32   s_journal_inum;         /* inode number of journal file */
        __u32   s_journal_dev;          /* device number of journal file */
        __u32   s_last_orphan;          /* start of list of inodes to delete */
-
-       __u32   s_reserved[197];        /* Padding to the end of the block */
+       __u32   s_hash_seed[4];         /* HTREE hash */
+       __u32   s_reserved[193];        /* Padding to the end of the block */
 };
 
 /*
index d6e91947f6e4ac7d1f865866f5f4385b052dcb75..2763e6824d21afdaffb13a47c7eaf84baf7a4b45 100644 (file)
@@ -612,7 +612,9 @@ extern errcode_t ext2fs_write_dir_block2(ext2_filsys fs, blk_t block,
 
 /* dirhash.c */
 extern errcode_t ext2fs_dirhash(int version, const char *name, int len,
-                               ext2_dirhash_t *ret_hash);
+                               const __u32 seed[4],
+                               ext2_dirhash_t *ret_hash,
+                               ext2_dirhash_t *ret_minor_hash);
 
 
 /* dir_iterate.c */
index ea83ad5be05e5971c83aa2660f6c89da0865b624..c960c76c38f341af35f21f25beb5e26fb0320829 100644 (file)
@@ -1,3 +1,7 @@
+2002-06-26  Theodore Ts'o  <tytso@mit.edu>
+
+       * f_h_badroot: New test cases to test bogus HTREE node values
+
 2002-06-25  Theodore Ts'o  <tytso@mit.edu>
 
        * Makefile.in (test_script): Add pass in the state of
diff --git a/tests/f_h_badroot/expect.1 b/tests/f_h_badroot/expect.1
new file mode 100644 (file)
index 0000000..d901967
--- /dev/null
@@ -0,0 +1,33 @@
+Pass 1: Checking inodes, blocks, and sizes
+HTREE directory inode 13345 has an invalid root node.
+Clear HTree index? yes
+
+HTREE directory inode 26689 has an unsupported hash version (240)
+Clear HTree index? yes
+
+HTREE directory inode 40033 has an invalid root node.
+Clear HTree index? yes
+
+HTREE directory inode 53377 has a tree depth (8) which is too big
+Clear HTree index? yes
+
+HTREE directory inode 66721 uses an incompatible htree root node flag.
+Clear HTree index? yes
+
+Pass 2: Checking directory structure
+Problem in HTREE directory inode 73393: node (1) has bad min hash
+Problem in HTREE directory inode 73393: node (2) has bad max hash
+Invalid HTREE directory inode 73393 (/test6).  Clear? yes
+
+Problem in HTREE directory inode 80065: node (2) has bad max hash
+Problem in HTREE directory inode 80065: node (7) has bad max hash
+Problem in HTREE directory inode 80065: node (21) has bad max hash
+Invalid HTREE directory inode 80065 (/test7).  Clear? yes
+
+Pass 3: Checking directory connectivity
+Pass 4: Checking reference counts
+Pass 5: Checking group summary information
+
+test_filesys: ***** FILE SYSTEM WAS MODIFIED *****
+test_filesys: 1719/100080 files (0.0% non-contiguous), 12611/15361 blocks
+Exit status is 1
diff --git a/tests/f_h_badroot/expect.2 b/tests/f_h_badroot/expect.2
new file mode 100644 (file)
index 0000000..82d7208
--- /dev/null
@@ -0,0 +1,7 @@
+Pass 1: Checking inodes, blocks, and sizes
+Pass 2: Checking directory structure
+Pass 3: Checking directory connectivity
+Pass 4: Checking reference counts
+Pass 5: Checking group summary information
+test_filesys: 1719/100080 files (0.0% non-contiguous), 12611/15361 blocks
+Exit status is 0
diff --git a/tests/f_h_badroot/image.gz b/tests/f_h_badroot/image.gz
new file mode 100644 (file)
index 0000000..9038f1a
Binary files /dev/null and b/tests/f_h_badroot/image.gz differ
diff --git a/tests/f_h_badroot/name b/tests/f_h_badroot/name
new file mode 100644 (file)
index 0000000..b2ac7ff
--- /dev/null
@@ -0,0 +1 @@
+bad htree root nodes
diff --git a/tests/f_h_badroot/script b/tests/f_h_badroot/script
new file mode 100644 (file)
index 0000000..9353ec7
--- /dev/null
@@ -0,0 +1,6 @@
+if test "$HTREE"x = yx -a "$HTREE_CLR"x = x; then
+. $cmd_dir/run_e2fsck
+else
+       rm -f $test_name.ok $test_name.failed
+       echo "skipped"
+fi
diff --git a/tests/f_h_normal/script~ b/tests/f_h_normal/script~
deleted file mode 100644 (file)
index 3024b04..0000000
+++ /dev/null
@@ -1,3 +0,0 @@
-if test "$HTREE"x = yx ; then
-. $cmd_dir/run_e2fsck
-fi