On Mon, Feb 13, 2017 at 12:20:15PM +0300, Artem Blagodarenko wrote:
> From: Artem Blagodarenko <[email protected]>
>
> The INCOMPAT_LARGEDIR feature allows larger directories to
> be created, both with directory sizes over 2GB and and a
> maximum htree depth of 3 instead of the current limit of 2.
> These features are needed in order to exceed the currently
> limit of approximately 10M entries in a single directory.
>
> debugfs, e2fsck, ext2fs, mke2fs and tune2fs support is
> added.
>
> Signed-off-by: Alexey Lyashkov <[email protected]>
> Signed-off-by: Artem Blagodarenko <[email protected]>
> ---
> e2fsck/pass1.c | 5 +++--
> e2fsck/pass2.c | 5 +++--
> lib/ext2fs/ext2_fs.h | 3 ++-
> lib/ext2fs/ext2fs.h | 21 ++++++++++++++++++++-
> misc/mke2fs.c | 3 ++-
> misc/tune2fs.c | 3 ++-
> 6 files changed, 32 insertions(+), 8 deletions(-)
>
> diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
> index ce37176..fff7dcf 100644
> --- a/e2fsck/pass1.c
> +++ b/e2fsck/pass1.c
> @@ -1716,7 +1716,8 @@ void e2fsck_pass1(e2fsck_t ctx)
> }
>
> if (inode->i_faddr || frag || fsize ||
> - (LINUX_S_ISDIR(inode->i_mode) && inode->i_size_high))
> + (!ext2fs_has_feature_large_dir(fs) &&
> + (LINUX_S_ISDIR(inode->i_mode) && inode->i_size_high)))
> mark_inode_bad(ctx, ino);
> if ((fs->super->s_creator_os != EXT2_OS_HURD) &&
> !ext2fs_has_feature_64bit(fs->super) &&
> @@ -2469,7 +2470,7 @@ static int handle_htree(e2fsck_t ctx, struct problem_context *pctx,
> return 1;
>
> pctx->num = root->indirect_levels;
> - if ((root->indirect_levels > 1) &&
> + if ((root->indirect_levels > ext2_dir_htree_level(fs)) &&
> fix_problem(ctx, PR_1_HTREE_DEPTH, pctx))
> return 1;
>
> diff --git a/e2fsck/pass2.c b/e2fsck/pass2.c
> index b89ebc9..139d48f 100644
> --- a/e2fsck/pass2.c
> +++ b/e2fsck/pass2.c
> @@ -1058,7 +1058,8 @@ inline_read_fail:
> dx_db->flags |= DX_FLAG_FIRST | DX_FLAG_LAST;
> if ((root->reserved_zero ||
> root->info_length < 8 ||
> - root->indirect_levels > 1) &&
> + root->indirect_levels
> + > ext2_dir_htree_level(fs)) &&
> fix_problem(ctx, PR_2_HTREE_BAD_ROOT, &cd->pctx)) {
> clear_htree(ctx, ino);
> dx_dir->numblocks = 0;
> @@ -1811,7 +1812,7 @@ int e2fsck_process_bad_inode(e2fsck_t ctx, ext2_ino_t dir,
> } else
> not_fixed++;
> }
> - if (inode.i_size_high &&
> + if (inode.i_size_high && !ext2fs_has_feature_large_dir(fs) &&
> LINUX_S_ISDIR(inode.i_mode)) {
> if (fix_problem(ctx, PR_2_DIR_SIZE_HIGH_ZERO, &pctx)) {
> inode.i_size_high = 0;
> diff --git a/lib/ext2fs/ext2_fs.h b/lib/ext2fs/ext2_fs.h
> index 195e366..6d9a5d0 100644
> --- a/lib/ext2fs/ext2_fs.h
> +++ b/lib/ext2fs/ext2_fs.h
> @@ -921,7 +921,8 @@ EXT4_FEATURE_INCOMPAT_FUNCS(encrypt, 4, ENCRYPT)
>
> #define EXT2_FEATURE_COMPAT_SUPP 0
> #define EXT2_FEATURE_INCOMPAT_SUPP (EXT2_FEATURE_INCOMPAT_FILETYPE| \
> - EXT4_FEATURE_INCOMPAT_MMP)
> + EXT4_FEATURE_INCOMPAT_MMP|\
> + EXT4_FEATURE_INCOMPAT_LARGEDIR)
> #define EXT2_FEATURE_RO_COMPAT_SUPP (EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER| \
> EXT2_FEATURE_RO_COMPAT_LARGE_FILE| \
> EXT4_FEATURE_RO_COMPAT_DIR_NLINK| \
> diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
> index 786ded8..d714b44 100644
> --- a/lib/ext2fs/ext2fs.h
> +++ b/lib/ext2fs/ext2fs.h
> @@ -588,7 +588,8 @@ typedef struct ext2_icount *ext2_icount_t;
> EXT4_FEATURE_INCOMPAT_64BIT|\
> EXT4_FEATURE_INCOMPAT_INLINE_DATA|\
> EXT4_FEATURE_INCOMPAT_ENCRYPT|\
> - EXT4_FEATURE_INCOMPAT_CSUM_SEED)
> + EXT4_FEATURE_INCOMPAT_CSUM_SEED|\
> + EXT4_FEATURE_INCOMPAT_LARGEDIR)
>
> #define EXT2_LIB_FEATURE_RO_COMPAT_SUPP (EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER|\
> EXT4_FEATURE_RO_COMPAT_HUGE_FILE|\
> @@ -1924,6 +1925,24 @@ _INLINE_ blk_t ext2fs_inode_data_blocks(ext2_filsys fs,
> return (blk_t) ext2fs_inode_data_blocks2(fs, inode);
> }
>
> +/* htree levels for ext4 */
> +#define EXT4_HTREE_LEVEL_COMPAT 1
> +#define EXT4_HTREE_LEVEL 3
> +
> +_INLINE_ int ext2fs_has_feature_large_dir(ext2_filsys fs)
> +{
> + return EXT2_HAS_INCOMPAT_FEATURE(fs->super,
> + EXT4_FEATURE_INCOMPAT_LARGEDIR);
> +}

Already provided, see line 955:

EXT4_FEATURE_INCOMPAT_FUNCS(largedir, 4, LARGEDIR)

defines ext2fs_has_feature_largedir().

The rest looks ok.

--D

> +
> +_INLINE_ unsigned int ext2_dir_htree_level(ext2_filsys fs)
> +{
> + if (ext2fs_has_feature_large_dir(fs))
> + return EXT4_HTREE_LEVEL;
> +
> + return EXT4_HTREE_LEVEL_COMPAT;
> +}
> +
> /*
> * This is an efficient, overflow safe way of calculating ceil((1.0 * a) / b)
> */
> diff --git a/misc/mke2fs.c b/misc/mke2fs.c
> index 9f18c83..b2bf461 100644
> --- a/misc/mke2fs.c
> +++ b/misc/mke2fs.c
> @@ -1081,7 +1081,8 @@ static __u32 ok_features[3] = {
> EXT4_FEATURE_INCOMPAT_64BIT|
> EXT4_FEATURE_INCOMPAT_INLINE_DATA|
> EXT4_FEATURE_INCOMPAT_ENCRYPT |
> - EXT4_FEATURE_INCOMPAT_CSUM_SEED,
> + EXT4_FEATURE_INCOMPAT_CSUM_SEED |
> + EXT4_FEATURE_INCOMPAT_LARGEDIR,
> /* R/O compat */
> EXT2_FEATURE_RO_COMPAT_LARGE_FILE|
> EXT4_FEATURE_RO_COMPAT_HUGE_FILE|
> diff --git a/misc/tune2fs.c b/misc/tune2fs.c
> index 6239577..f78d105 100644
> --- a/misc/tune2fs.c
> +++ b/misc/tune2fs.c
> @@ -156,7 +156,8 @@ static __u32 ok_features[3] = {
> EXT4_FEATURE_INCOMPAT_MMP |
> EXT4_FEATURE_INCOMPAT_64BIT |
> EXT4_FEATURE_INCOMPAT_ENCRYPT |
> - EXT4_FEATURE_INCOMPAT_CSUM_SEED,
> + EXT4_FEATURE_INCOMPAT_CSUM_SEED |
> + EXT4_FEATURE_INCOMPAT_LARGEDIR,
> /* R/O compat */
> EXT2_FEATURE_RO_COMPAT_LARGE_FILE |
> EXT4_FEATURE_RO_COMPAT_HUGE_FILE|
> --
> 1.7.1
>

2017-02-15 13:54:48

by Artem Blagodarenko

[permalink] [raw]

Subject: [PATCH v3 3/4] e2fsck: 3 level hash tree directory optimization

From: Artem Blagodarenko <[email protected]>

e2fsck fix for partitions with 3 level hash directries.
Additional level is added to e2fsck -D codepath.

Signed-off-by: Artem Blagodarenko <[email protected]>
---
debugfs/htree.c | 3 +-
e2fsck/e2fsck.h | 1 +
e2fsck/pass2.c | 68 ++++++++++++++++++++++--------
e2fsck/rehash.c | 115 ++++++++++++++++++++++++++++++++++++++++-----------
lib/ext2fs/ext2fs.h | 5 ++
5 files changed, 148 insertions(+), 44 deletions(-)

diff --git a/debugfs/htree.c b/debugfs/htree.c
index 54e55e2..8c18666 100644
--- a/debugfs/htree.c
+++ b/debugfs/htree.c
@@ -287,7 +287,8 @@ void do_htree_dump(int argc, char *argv[])
fprintf(pager, "\t Indirect levels: %d\n", rootnode->indirect_levels);
fprintf(pager, "\t Flags: %d\n", rootnode->unused_flags);

- ent = (struct ext2_dx_entry *) (buf + 24 + rootnode->info_length);
+ ent = (struct ext2_dx_entry *)
+ ((char *)rootnode + rootnode->info_length);

htree_dump_int_node(current_fs, ino, &inode, rootnode, ent,
buf + current_fs->blocksize,
diff --git a/e2fsck/e2fsck.h b/e2fsck/e2fsck.h
index f356810..a4efbdf 100644
--- a/e2fsck/e2fsck.h
+++ b/e2fsck/e2fsck.h
@@ -122,6 +122,7 @@ struct dx_dirblock_info {
blk64_t phys;
int flags;
blk64_t parent;
+ blk64_t previous;
ext2_dirhash_t min_hash;
ext2_dirhash_t max_hash;
ext2_dirhash_t node_min_hash;
diff --git a/e2fsck/pass2.c b/e2fsck/pass2.c
index 139d48f..2e2c721 100644
--- a/e2fsck/pass2.c
+++ b/e2fsck/pass2.c
@@ -85,6 +85,39 @@ struct check_dir_struct {
unsigned long long next_ra_off;
};

+static void update_parents(struct dx_dir_info *dx_dir, int type)
+{
+ struct dx_dirblock_info *dx_db, *dx_parent, *dx_previous;
+ int b;
+
+ for (b = 0, dx_db = dx_dir->dx_block;
+ b < dx_dir->numblocks;
+ b++, dx_db++) {
+ dx_parent = &dx_dir->dx_block[dx_db->parent];
+ if (dx_db->type != type)
+ continue;
+
+ /*
+ * XXX Make sure dx_parent->min_hash > dx_db->min_hash
+ */
+ if (dx_db->flags & DX_FLAG_FIRST) {
+ dx_parent->min_hash = dx_db->min_hash;
+ if (dx_parent->previous) {
+ dx_previous =
+ &dx_dir->dx_block[dx_parent->previous];
+ dx_previous->node_max_hash =
+ dx_parent->min_hash;
+ }
+ }
+ /*
+ * XXX Make sure dx_parent->max_hash < dx_db->max_hash
+ */
+ if (dx_db->flags & DX_FLAG_LAST) {
+ dx_parent->max_hash = dx_db->max_hash;
+ }
+ }
+}
+
void e2fsck_pass2(e2fsck_t ctx)
{
struct ext2_super_block *sb = ctx->fs->super;
@@ -182,24 +215,11 @@ void e2fsck_pass2(e2fsck_t ctx)
* Find all of the first and last leaf blocks, and
* update their parent's min and max hash values
*/
- for (b=0, dx_db = dx_dir->dx_block;
- b < dx_dir->numblocks;
- b++, dx_db++) {
- if ((dx_db->type != DX_DIRBLOCK_LEAF) ||
- !(dx_db->flags & (DX_FLAG_FIRST | DX_FLAG_LAST)))
- continue;
- dx_parent = &dx_dir->dx_block[dx_db->parent];
- /*
- * XXX Make sure dx_parent->min_hash > dx_db->min_hash
- */
- if (dx_db->flags & DX_FLAG_FIRST)
- dx_parent->min_hash = dx_db->min_hash;
- /*
- * XXX Make sure dx_parent->max_hash < dx_db->max_hash
- */
- if (dx_db->flags & DX_FLAG_LAST)
- dx_parent->max_hash = dx_db->max_hash;
- }
+ update_parents(dx_dir, DX_DIRBLOCK_LEAF);
+
+ /* for 3 level htree: update 2 level parent's min
+ * and max hash values */
+ update_parents(dx_dir, DX_DIRBLOCK_NODE);

for (b=0, dx_db = dx_dir->dx_block;
b < dx_dir->numblocks;
@@ -642,6 +662,10 @@ static void parse_int_node(ext2_filsys fs,
dx_db->flags |= DX_FLAG_REFERENCED;
dx_db->parent = db->blockcnt;
}
+
+ dx_db->previous =
+ i ? ext2fs_le32_to_cpu(ent[i-1].block & 0x0ffffff) : 0;
+
if (hash < min_hash)
min_hash = hash;
if (hash > max_hash)
@@ -949,6 +973,14 @@ static int check_dir_block(ext2_filsys fs,
return DIRENT_ABORT;
}

+ /* This will allow (at some point in the future) to punch out empty
+ * directory blocks and reduce the space used by a directory that grows
+ * very large and then the files are deleted. For now, all that is
+ * needed is to avoid e2fsck filling in these holes as part of
+ * feature flag. */
+ if (db->blk == 0 && ext2fs_has_feature_large_dir(fs))
+ return 0;
+
if (db->blk == 0 && !inline_data_size) {
if (allocate_dir_block(ctx, db, buf, &cd->pctx))
return 0;
diff --git a/e2fsck/rehash.c b/e2fsck/rehash.c
index 22a58f3..7dcb386 100644
--- a/e2fsck/rehash.c
+++ b/e2fsck/rehash.c
@@ -603,6 +603,43 @@ static struct ext2_dx_entry *set_int_node(ext2_filsys fs, char *buf)
return (struct ext2_dx_entry *) limits;
}

+static int alloc_blocks(ext2_filsys fs,
+ struct ext2_dx_countlimit **limit,
+ struct ext2_dx_entry **prev_ent,
+ struct ext2_dx_entry **next_ent,
+ int *prev_offset, int *next_offset,
+ struct out_dir *outdir, int i,
+ int *prev_count, int *next_count)
+{
+ errcode_t retval;
+ char *block_start;
+
+ if (*limit)
+ (*limit)->limit = (*limit)->count =
+ ext2fs_cpu_to_le16((*limit)->limit);
+ *prev_ent = (struct ext2_dx_entry *) (outdir->buf + *prev_offset);
+ (*prev_ent)->block = ext2fs_cpu_to_le32(outdir->num);
+
+ if (i != 1)
+ (*prev_ent)->hash =
+ ext2fs_cpu_to_le32(outdir->hashes[i]);
+
+ retval = get_next_block(fs, outdir, &block_start);
+ if (retval)
+ return retval;
+
+ *next_ent = set_int_node(fs, block_start);
+ *limit = (struct ext2_dx_countlimit *)(*next_ent);
+ if (next_offset)
+ *next_offset = ((char *) *next_ent - outdir->buf);
+
+ *next_count = (*limit)->limit;
+ (*prev_offset) += sizeof(struct ext2_dx_entry);
+ (*prev_count)--;
+
+ return 0;
+}
+
/*
* This function takes the leaf nodes which have been written in
* outdir, and populates the root node and any necessary interior nodes.
@@ -612,13 +649,13 @@ static errcode_t calculate_tree(ext2_filsys fs,
ext2_ino_t ino,
ext2_ino_t parent)
{
- struct ext2_dx_root_info *root_info;
- struct ext2_dx_entry *root, *dx_ent = 0;
- struct ext2_dx_countlimit *root_limit, *limit;
+ struct ext2_dx_root_info *root_info;
+ struct ext2_dx_entry *root, *int_ent, *dx_ent = 0;
+ struct ext2_dx_countlimit *root_limit, *int_limit, *limit;
errcode_t retval;
char * block_start;
- int i, c1, c2, nblks;
- int limit_offset, root_offset;
+ int i, c1, c2, c3, nblks;
+ int limit_offset, int_offset, root_offset;

root_info = set_root_node(fs, outdir->buf, ino, parent);
root_offset = limit_offset = ((char *) root_info - outdir->buf) +
@@ -628,7 +665,7 @@ static errcode_t calculate_tree(ext2_filsys fs,
nblks = outdir->num;

/* Write out the pointer blocks */
- if (nblks-1 <= c1) {
+ if (nblks - 1 <= c1) {
/* Just write out the root block, and we're done */
root = (struct ext2_dx_entry *) (outdir->buf + root_offset);
for (i=1; i < nblks; i++) {
@@ -639,31 +676,20 @@ static errcode_t calculate_tree(ext2_filsys fs,
root++;
c1--;
}
- } else {
+ } else if (nblks - 1 <= ext2fs_htree_intnode_maxrecs(fs, c1)) {
c2 = 0;
- limit = 0;
+ limit = NULL;
root_info->indirect_levels = 1;
for (i=1; i < nblks; i++) {
- if (c1 == 0)
+ if (c2 == 0 && c1 == 0)
return ENOSPC;
if (c2 == 0) {
- if (limit)
- limit->limit = limit->count =
- ext2fs_cpu_to_le16(limit->limit);
- root = (struct ext2_dx_entry *)
- (outdir->buf + root_offset);
- root->block = ext2fs_cpu_to_le32(outdir->num);
- if (i != 1)
- root->hash =
- ext2fs_cpu_to_le32(outdir->hashes[i]);
- if ((retval = get_next_block(fs, outdir,
- &block_start)))
+ retval = alloc_blocks(fs, &limit, &root,
+ &dx_ent, &root_offset,
+ NULL, outdir, i, &c1,
+ &c2);
+ if (retval)
return retval;
- dx_ent = set_int_node(fs, block_start);
- limit = (struct ext2_dx_countlimit *) dx_ent;
- c2 = limit->limit;
- root_offset += sizeof(struct ext2_dx_entry);
- c1--;
}
dx_ent->block = ext2fs_cpu_to_le32(i);
if (c2 != limit->limit)
@@ -674,6 +700,45 @@ static errcode_t calculate_tree(ext2_filsys fs,
}
limit->count = ext2fs_cpu_to_le16(limit->limit - c2);
limit->limit = ext2fs_cpu_to_le16(limit->limit);
+ } else {
+ c2 = 0;
+ c3 = 0;
+ limit = NULL;
+ int_limit = 0;
+ root_info->indirect_levels = 2;
+ for (i = 1; i < nblks; i++) {
+ if (c3 == 0 && c2 == 0 && c1 == 0)
+ return ENOSPC;
+ if (c3 == 0 && c2 == 0) {
+ retval = alloc_blocks(fs, &int_limit, &root,
+ &int_ent, &root_offset,
+ &int_offset, outdir, i,
+ &c1, &c2);
+ if (retval)
+ return retval;
+ }
+ if (c3 == 0) {
+ retval = alloc_blocks(fs, &limit, &int_ent,
+ &dx_ent, &int_offset,
+ NULL, outdir, i, &c2,
+ &c3);
+ if (retval)
+ return retval;
+
+ }
+ dx_ent->block = ext2fs_cpu_to_le32(i);
+ if (c3 != limit->limit)
+ dx_ent->hash =
+ ext2fs_cpu_to_le32(outdir->hashes[i]);
+ dx_ent++;
+ c3--;
+ }
+ int_limit->count = ext2fs_cpu_to_le16(limit->limit - c2);
+ int_limit->limit = ext2fs_cpu_to_le16(limit->limit);
+
+ limit->count = ext2fs_cpu_to_le16(limit->limit - c3);
+ limit->limit = ext2fs_cpu_to_le16(limit->limit);
+
}
root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset);
root_limit->count = ext2fs_cpu_to_le16(root_limit->limit - c1);
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index d714b44..79698ce 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -1943,6 +1943,11 @@ _INLINE_ unsigned int ext2_dir_htree_level(ext2_filsys fs)
return EXT4_HTREE_LEVEL_COMPAT;
}

+_INLINE_ int ext2fs_htree_intnode_maxrecs(ext2_filsys fs, int blocks)
+{
+ return blocks * ((fs->blocksize - 8) / sizeof(struct ext2_dx_entry));
+}
+
/*
* This is an efficient, overflow safe way of calculating ceil((1.0 * a) / b)
*/
--
1.7.1

2017-02-15 15:45:53

by Artem Blagodarenko

[permalink] [raw]

Subject: [PATCH v3 4/4] tests: 3 level hash tree test

From: Artem Blagodarenko <[email protected]>

Test is added that recreate directory (-fD fsck option)
with 47.5k of 255-symbol name files. This amount of files
can not be stored only in 2 hevel htree, so 3 levels are used.

Signed-off-by: Artem Blagodarenko <[email protected]>
---
tests/f_large_dir/expect | 12 +++++++++++
tests/f_large_dir/name | 1 +
tests/f_large_dir/script | 47 ++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 60 insertions(+), 0 deletions(-)

diff --git a/tests/f_large_dir/expect b/tests/f_large_dir/expect
new file mode 100644
index 0000000..b099460
--- /dev/null
+++ b/tests/f_large_dir/expect
@@ -0,0 +1,12 @@
+Pass 1: Checking inodes, blocks, and sizes
+Pass 2: Checking directory structure
+Pass 3: Checking directory connectivity
+Pass 3A: Optimizing directories
+Pass 4: Checking reference counts
+Inode 13 ref count is 1, should be 47245. Fix? yes
+
+Pass 5: Checking group summary information
+
+test.img: ***** FILE SYSTEM WAS MODIFIED *****
+test.img: 13/115368 files (0.0% non-contiguous), 32817/460800 blocks
+Exit status is 1
diff --git a/tests/f_large_dir/name b/tests/f_large_dir/name
new file mode 100644
index 0000000..4b96890
--- /dev/null
+++ b/tests/f_large_dir/name
@@ -0,0 +1 @@
+optimize 3 level htree directories
diff --git a/tests/f_large_dir/script b/tests/f_large_dir/script
new file mode 100644
index 0000000..e68576d
--- /dev/null
+++ b/tests/f_large_dir/script
@@ -0,0 +1,47 @@
+OUT=$test_name.log
+EXP=$test_dir/expect
+E2FSCK=../e2fsck/e2fsck
+
+NAMELEN=255
+DIRENT_SZ=8
+BLOCKSZ=1024
+DIRENT_PER_LEAF=$((BLOCKSZ / (NAMELEN + DIRENT_SZ)))
+HEADER=32
+INDEX_SZ=8
+INDEX_L1=$(((BLOCKSZ - HEADER) / INDEX_SZ))
+INDEX_L2=$(((BLOCKSZ - DIRENT_SZ) / INDEX_SZ))
+ENTRIES=$((INDEX_L1 * INDEX_L2 * DIRENT_PER_LEAF))
+
+cp /dev/null $OUT
+$MKE2FS -b 1024 -O large_dir,uninit_bg,dir_nlink -F $TMPFILE 460800 > /dev/null
+{
+ echo "feature large_dir"
+ echo "mkdir /foo"
+ echo "cd /foo"
+ touch foofile
+ echo "write foofile foofile"
+ for ((i = 0; i < $ENTRIES; i++)); do
+ [[ $(( i % DIRENT_PER_LEAF )) -eq 0 ]] && echo "expand ./"
+ [[ $(( i % 5000 )) -eq 0 ]] && >&2 echo "$i processed"
+ printf "ln foofile %0255X\n" $i
+ done
+} | $DEBUGFS -w -f /dev/stdin $TMPFILE > /dev/null
+
+$E2FSCK -yfD $TMPFILE > $OUT.new 2>&1
+status=$?
+echo Exit status is $status >> $OUT.new
+sed -f $cmd_dir/filter.sed -e "s;$TMPFILE;test.img;" $OUT.new >> $OUT
+rm -f $OUT.new
+
+cmp -s $OUT $EXP
+RC=$?
+if [ $RC -eq 0 ]; then
+ echo "$test_name: $test_description: ok"
+ touch $test_name.ok
+else
+ echo "$test_name: $test_description: failed"
+ diff -u $EXP $OUT > $test_name.failed
+fi
+
+
+
--
1.7.1

2017-02-15 17:43:21

by Artem Blagodarenko

[permalink] [raw]

Subject: [PATCH v3 2/4] e2fsprogs: add support for 3-level htree

From: Artem Blagodarenko <[email protected]>

The INCOMPAT_LARGEDIR feature allows larger directories to
be created, both with directory sizes over 2GB and and a
maximum htree depth of 3 instead of the current limit of 2.
These features are needed in order to exceed the currently
limit of approximately 10M entries in a single directory
for 4KB blocksize (~100k for 1KB).

debugfs, e2fsck, ext2fs, mke2fs and tune2fs support is
added.

Signed-off-by: Alexey Lyashkov <[email protected]>
Signed-off-by: Artem Blagodarenko <[email protected]>
---
e2fsck/pass1.c | 5 +++--
e2fsck/pass2.c | 5 +++--
lib/ext2fs/ext2_fs.h | 3 ++-
lib/ext2fs/ext2fs.h | 15 ++++++++++++++-
misc/mke2fs.c | 3 ++-
misc/tune2fs.c | 3 ++-
6 files changed, 26 insertions(+), 8 deletions(-)

diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
index ce37176..11546d7 100644
--- a/e2fsck/pass1.c
+++ b/e2fsck/pass1.c
@@ -1716,7 +1716,8 @@ void e2fsck_pass1(e2fsck_t ctx)
}

if (inode->i_faddr || frag || fsize ||
- (LINUX_S_ISDIR(inode->i_mode) && inode->i_size_high))
+ (!ext2fs_has_feature_largedir(fs->super) &&
+ (LINUX_S_ISDIR(inode->i_mode) && inode->i_size_high)))
mark_inode_bad(ctx, ino);
if ((fs->super->s_creator_os != EXT2_OS_HURD) &&
!ext2fs_has_feature_64bit(fs->super) &&
@@ -2469,7 +2470,7 @@ static int handle_htree(e2fsck_t ctx, struct problem_context *pctx,
return 1;

pctx->num = root->indirect_levels;
- if ((root->indirect_levels > 1) &&
+ if ((root->indirect_levels > ext2_dir_htree_level(fs)) &&
fix_problem(ctx, PR_1_HTREE_DEPTH, pctx))
return 1;

diff --git a/e2fsck/pass2.c b/e2fsck/pass2.c
index b89ebc9..2f41fc4 100644
--- a/e2fsck/pass2.c
+++ b/e2fsck/pass2.c
@@ -1058,7 +1058,8 @@ inline_read_fail:
dx_db->flags |= DX_FLAG_FIRST | DX_FLAG_LAST;
if ((root->reserved_zero ||
root->info_length < 8 ||
- root->indirect_levels > 1) &&
+ root->indirect_levels >=
+ ext2_dir_htree_level(fs)) &&
fix_problem(ctx, PR_2_HTREE_BAD_ROOT, &cd->pctx)) {
clear_htree(ctx, ino);
dx_dir->numblocks = 0;
@@ -1811,7 +1812,7 @@ int e2fsck_process_bad_inode(e2fsck_t ctx, ext2_ino_t dir,
} else
not_fixed++;
}
- if (inode.i_size_high &&
+ if (inode.i_size_high && !ext2fs_has_feature_largedir(fs->super) &&
LINUX_S_ISDIR(inode.i_mode)) {
if (fix_problem(ctx, PR_2_DIR_SIZE_HIGH_ZERO, &pctx)) {
inode.i_size_high = 0;
diff --git a/lib/ext2fs/ext2_fs.h b/lib/ext2fs/ext2_fs.h
index 195e366..66b7058 100644
--- a/lib/ext2fs/ext2_fs.h
+++ b/lib/ext2fs/ext2_fs.h
@@ -921,7 +921,8 @@ EXT4_FEATURE_INCOMPAT_FUNCS(encrypt, 4, ENCRYPT)

#define EXT2_FEATURE_COMPAT_SUPP 0
#define EXT2_FEATURE_INCOMPAT_SUPP (EXT2_FEATURE_INCOMPAT_FILETYPE| \
- EXT4_FEATURE_INCOMPAT_MMP)
+ EXT4_FEATURE_INCOMPAT_MMP| \
+ EXT4_FEATURE_INCOMPAT_LARGEDIR)
#define EXT2_FEATURE_RO_COMPAT_SUPP (EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER| \
EXT2_FEATURE_RO_COMPAT_LARGE_FILE| \
EXT4_FEATURE_RO_COMPAT_DIR_NLINK| \
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 786ded8..c68be50 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -588,7 +588,8 @@ typedef struct ext2_icount *ext2_icount_t;
EXT4_FEATURE_INCOMPAT_64BIT|\
EXT4_FEATURE_INCOMPAT_INLINE_DATA|\
EXT4_FEATURE_INCOMPAT_ENCRYPT|\
- EXT4_FEATURE_INCOMPAT_CSUM_SEED)
+ EXT4_FEATURE_INCOMPAT_CSUM_SEED|\
+ EXT4_FEATURE_INCOMPAT_LARGEDIR)

#define EXT2_LIB_FEATURE_RO_COMPAT_SUPP (EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER|\
EXT4_FEATURE_RO_COMPAT_HUGE_FILE|\
@@ -1924,6 +1925,18 @@ _INLINE_ blk_t ext2fs_inode_data_blocks(ext2_filsys fs,
return (blk_t) ext2fs_inode_data_blocks2(fs, inode);
}

+/* htree levels for ext4 */
+#define EXT4_HTREE_LEVEL_COMPAT 2
+#define EXT4_HTREE_LEVEL 3
+
+static inline unsigned int ext2_dir_htree_level(ext2_filsys fs)
+{
+ if (ext2fs_has_feature_largedir(fs->super))
+ return EXT4_HTREE_LEVEL;
+
+ return EXT4_HTREE_LEVEL_COMPAT;
+}
+
/*
* This is an efficient, overflow safe way of calculating ceil((1.0 * a) / b)
*/
diff --git a/misc/mke2fs.c b/misc/mke2fs.c
index 9f18c83..b2bf461 100644
--- a/misc/mke2fs.c
+++ b/misc/mke2fs.c
@@ -1081,7 +1081,8 @@ static __u32 ok_features[3] = {
EXT4_FEATURE_INCOMPAT_64BIT|
EXT4_FEATURE_INCOMPAT_INLINE_DATA|
EXT4_FEATURE_INCOMPAT_ENCRYPT |
- EXT4_FEATURE_INCOMPAT_CSUM_SEED,
+ EXT4_FEATURE_INCOMPAT_CSUM_SEED |
+ EXT4_FEATURE_INCOMPAT_LARGEDIR,
/* R/O compat */
EXT2_FEATURE_RO_COMPAT_LARGE_FILE|
EXT4_FEATURE_RO_COMPAT_HUGE_FILE|
diff --git a/misc/tune2fs.c b/misc/tune2fs.c
index 6239577..f78d105 100644
--- a/misc/tune2fs.c
+++ b/misc/tune2fs.c
@@ -156,7 +156,8 @@ static __u32 ok_features[3] = {
EXT4_FEATURE_INCOMPAT_MMP |
EXT4_FEATURE_INCOMPAT_64BIT |
EXT4_FEATURE_INCOMPAT_ENCRYPT |
- EXT4_FEATURE_INCOMPAT_CSUM_SEED,
+ EXT4_FEATURE_INCOMPAT_CSUM_SEED |
+ EXT4_FEATURE_INCOMPAT_LARGEDIR,
/* R/O compat */
EXT2_FEATURE_RO_COMPAT_LARGE_FILE |
EXT4_FEATURE_RO_COMPAT_HUGE_FILE|
--
1.7.1

2017-02-15 17:45:05

by Artem Blagodarenko

I've applied the latest version of these patches to the next branch.
My plan is to release 1.43.5 on the maint branch, and the 3-level
htree will be for an eventual 1.44 release (as it is a new feature).

Cheers,

- Ted