Skip to contentSkip to conversation

New inode allocation for FLEX_BG meta-data groups.

PATCH In review Jose R. Santos 2 participants 3 messages Jan 11, 2008 ext4 file system

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 New inode allocation for FLEX_BG meta-data groups.

commit 8eef19455beb97319a78511b35b1da42a1d48eb2

Author: Jose R. Santos <[email protected]>
Date:   Fri Jan 11 11:04:25 2008 -0600

New inode allocation for FLEX_BG meta-data groups.

This patch mostly controls the way inode are allocated in order to make ialloc aware of flex_bg block group grouping. It achieves this by bypassing the Orlov allocator when block group meta-data are packed toghether through mke2fs. Since the impact on the block allocator is minimal, this patch should have little or no effect on other block allocation algorithms. By controlling the inode allocation, it can basically control where the initial search for new block begins and thus indirectly manipulate the block allocator.

This allocator favors data and meta-data locality so the disk will gradually be filled from block group zero upward. This helps improve performance by reducing seek time. Since the group of inode tables within one flex_bg are treated as one giant inode table, uninitialized block groups would not need to partially initialize as many inode table as with Orlov which would help fsck time as the filesystem usage goes up.

fs/ext4/balloc.c +16 -0
index 643046b..aed3456 100644
@@ -127,6 +127,8 @@ unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh,
 		mark_bitmap_end(group_blocks, sb->s_blocksize * 8, bh->b_data);
 	}
 
+	if (sbi->s_log_groups_per_flex)
+		return free_blocks;
 	return free_blocks - sbi->s_itb_per_group - 2;
 }
 
@@ -759,6 +761,13 @@ do_more:
 	spin_unlock(sb_bgl_lock(sbi, block_group));
 	percpu_counter_add(&sbi->s_freeblocks_counter, count);
 
+	if (sbi->s_log_groups_per_flex) {
+		ext4_group_t flex_group = ext4_flex_group(sbi, block_group);
+		spin_lock(sb_bgl_lock(sbi, flex_group));
+		sbi->s_flex_groups[flex_group].free_blocks += count;
+		spin_unlock(sb_bgl_lock(sbi, flex_group));
+	}
+
 	/* We dirtied the bitmap block */
 	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
 	err = ext4_journal_dirty_metadata(handle, bitmap_bh);
@@ -1829,6 +1838,13 @@ allocated:
 	spin_unlock(sb_bgl_lock(sbi, group_no));
 	percpu_counter_sub(&sbi->s_freeblocks_counter, num);
 
+	if (sbi->s_log_groups_per_flex) {
+		ext4_group_t flex_group = ext4_flex_group(sbi, group_no);
+		spin_lock(sb_bgl_lock(sbi, flex_group));
+		sbi->s_flex_groups[flex_group].free_blocks -= num;
+		spin_unlock(sb_bgl_lock(sbi, flex_group));
+	}
+
 	BUFFER_TRACE(gdp_bh, "journal_dirty_metadata for group descriptor");
 	err = ext4_journal_dirty_metadata(handle, gdp_bh);
 	if (!fatal)
fs/ext4/ialloc.c +91 -0

133 lines not on this page · raw message

fs/ext4/super.c +56 -0

74 lines not on this page · raw message

include/linux/ext4_fs.h +24 -1
index 7c7c6b5..9160db3 100644
@@ -152,6 +152,15 @@ struct ext4_group_desc
 	__u32	bg_reserved2[3];
 };
 
+/*
+ * Structure of a flex block group info
+ */
+
+struct flex_groups {
+	__u32 free_inodes;
+	__u32 free_blocks;
+};
+
 #define EXT4_BG_INODE_UNINIT	0x0001 /* Inode table/bitmap not in use */
 #define EXT4_BG_BLOCK_UNINIT	0x0002 /* Block bitmap not in use */
 #define EXT4_BG_INODE_ZEROED	0x0004 /* On-disk itable initialized to zero */
@@ -623,7 +632,10 @@ struct ext4_super_block {
 	__le16  s_mmp_interval;         /* # seconds to wait in MMP checking */
 	__le64  s_mmp_block;            /* Block for multi-mount protection */
 	__le32  s_raid_stripe_width;    /* blocks on all data disks (N*stride)*/
-	__u32   s_reserved[163];        /* Padding to the end of the block */
+	__u8	s_log_groups_per_flex;  /* FLEX_BG group size */
+	__u8	s_reserved_char_pad2;
+	__le16  s_reserved_pad;
+	__u32   s_reserved[162];        /* Padding to the end of the block */
 };
 
 #ifdef __KERNEL__
@@ -1121,6 +1133,17 @@ static inline void ext4_isize_set(struct ext4_inode *raw_inode, loff_t i_size)
 	raw_inode->i_size_high = cpu_to_le32(i_size >> 32);
 }
 
+static inline ext4_group_t ext4_flex_group(struct ext4_sb_info *sbi,
+					     ext4_group_t block_group)
+{
+	return block_group >> sbi->s_log_groups_per_flex;
+}
+
+static inline unsigned int ext4_flex_bg_size(struct ext4_sb_info *sbi)
+{
+	return 1 << sbi->s_log_groups_per_flex;
+}
+
 #define ext4_std_error(sb, errno)				\
 do {								\
 	if ((errno))						\
include/linux/ext4_fs_sb.h +3 -0
index 3bc6583..d750d2c 100644
@@ -143,6 +143,9 @@ struct ext4_sb_info {
 
 	/* locality groups */
 	struct ext4_locality_group *s_locality_groups;
+
+	unsigned int s_log_groups_per_flex;
+	struct flex_groups *s_flex_groups;
 };
 #define EXT4_GROUP_INFO(sb, group)					   \
 	EXT4_SB(sb)->s_group_info[(group) >> EXT4_DESC_PER_BLOCK_BITS(sb)] \
#1 lore raw

fs/ext4/balloc.c unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh, · line 132

Quoted 7 lines · Jose R. Santos
fs/ext4/balloc.c +2 -0
@@ -127,6 +127,8 @@ unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh,
 		mark_bitmap_end(group_blocks, sb->s_blocksize * 8, bh->b_data);
 	}
 
+	if (sbi->s_log_groups_per_flex)
+		return free_blocks;
 	return free_blocks - sbi->s_itb_per_group - 2;

To be honest, I think this is a wart in ext4_init_block_bitmap() that it returns the number of free blocks in the group. That value should really be set at mke2fs or e2fsck time, and if the last group is marked BLOCK_UNINIT it gets the free blocks count wrong because it always starts with EXT4_BLOCKS_PER_GROUP().

The above patch may also be incorrect since there may be inode tables or bitmaps in the above group even in the case of FLEX_BG filesystems.

fs/ext4/ialloc.c static int find_group_dir(struct super_block *sb, struct inode *parent, · line 317

Quoted 5 lines
fs/ext4/ialloc.c +5 -0
+#define free_block_ratio 10
+
+static int find_group_flex(struct super_block *sb, struct inode *parent, ext4_group_t *best_group)
+{
+	n_fbg_groups = (sbi->s_groups_count + flex_size - 1) / flex_size;

Can be a shift?

I would suggest doing some kind of testing to see how well this allocation policy is working. We don't want to force all allocations contiguously at the start of the filesystem, or we end up with FAT...

fs/ext4/super.c static int ext4_setup_super(struct super_block *sb, struct ext4_super_block *es, · line 1449

Quoted 3 lines
fs/ext4/super.c +3 -0
+static int ext4_fill_flex_info(struct super_block *sb)
+{
+	sbi->s_log_groups_per_flex = sbi->s_es->s_log_groups_per_flex;

Hmm, I guess no le*_to_cpu() because this is 8 bits?

fs/ext4/super.c static int ext4_setup_super(struct super_block *sb, struct ext4_super_block *es, · line 1457

Quoted 7 lines
fs/ext4/super.c +7 -0
+
+	flex_group_count = (sbi->s_groups_count + groups_per_flex - 1) /
+		groups_per_flex;
+	sbi->s_flex_groups = kmalloc(flex_group_count *
+				     sizeof(struct flex_groups), GFP_KERNEL);
+	if (sbi->s_flex_groups == NULL) {
+		printk(KERN_ERR "EXT4-fs: not enough memory\n");

This should report "not enough memory for N flex groups" or something.

fs/ext4/super.c static int ext4_fill_super (struct super_block *sb, · line 2158

Quoted 6 lines
fs/ext4/super.c +5 -0
@@ -2105,6 +2154,13 @@ static int ext4_fill_super (struct super_block *sb,
+	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_FLEX_BG))
+		if (!ext4_fill_flex_info(sb)) {
+			printk(KERN_ERR
+			       "EXT4-fs: unable to initialize flex_bg meta info!\n");
+			goto failed_mount2;

Should this be considered a fatal error, or could sbi->s_log_groups_per_flex just be set to 0 and the filesystem be used as-is (maybe with sub-optimal allocations or something)? Otherwise this renders the filesystem unusable.

Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.

#2 lore raw
Quoted 18 lines · On Fri, 11 Jan 2008 14:46:58 -0700 Andreas Dilger <[email protected]> wrote:

fs/ext4/balloc.c unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh, · line 132

Quoted 7 lines · Jose R. Santos
fs/ext4/balloc.c +2 -0
@@ -127,6 +127,8 @@ unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh,
 		mark_bitmap_end(group_blocks, sb->s_blocksize * 8, bh->b_data);
 	}
 
+	if (sbi->s_log_groups_per_flex)
+		return free_blocks;
 	return free_blocks - sbi->s_itb_per_group - 2;

To be honest, I think this is a wart in ext4_init_block_bitmap() that it returns the number of free blocks in the group. That value should really be set at mke2fs or e2fsck time, and if the last group is marked BLOCK_UNINIT it gets the free blocks count wrong because it always starts with EXT4_BLOCKS_PER_GROUP().

The above patch may also be incorrect since there may be inode tables or bitmaps in the above group even in the case of FLEX_BG filesystems.

Quoted 7 lines

fs/ext4/ialloc.c static int find_group_dir(struct super_block *sb, struct inode *parent, · line 317

Quoted 5 lines
fs/ext4/ialloc.c +5 -0
+#define free_block_ratio 10
+
+static int find_group_flex(struct super_block *sb, struct inode *parent, ext4_group_t *best_group)
+{
+	n_fbg_groups = (sbi->s_groups_count + flex_size - 1) / flex_size;

Can be a shift?

You're right. This should be:

n_fbg_groups = (sbi->s_groups_count + flex_size - 1) >> sbi->s_log_groups_per_flex;

Quoted 3 lines

I would suggest doing some kind of testing to see how well this allocation policy is working. We don't want to force all allocations contiguously at the start of the filesystem, or we end up with FAT...

I've done several IO patterns with multiple threads and all of my test are either same or faster performance than with the regular allocator. Im hopping that moving this to the patch queue will expose the allocator to more tests.

Quoted 5 lines

fs/ext4/super.c static int ext4_setup_super(struct super_block *sb, struct ext4_super_block *es, · line 1449

Quoted 3 lines
fs/ext4/super.c +3 -0
+static int ext4_fill_flex_info(struct super_block *sb)
+{
+	sbi->s_log_groups_per_flex = sbi->s_es->s_log_groups_per_flex;

Hmm, I guess no le*_to_cpu() because this is 8 bits?

Correct.

Quoted 9 lines

fs/ext4/super.c static int ext4_setup_super(struct super_block *sb, struct ext4_super_block *es, · line 1457

Quoted 7 lines
fs/ext4/super.c +7 -0
+
+	flex_group_count = (sbi->s_groups_count + groups_per_flex - 1) /
+		groups_per_flex;
+	sbi->s_flex_groups = kmalloc(flex_group_count *
+				     sizeof(struct flex_groups), GFP_KERNEL);
+	if (sbi->s_flex_groups == NULL) {
+		printk(KERN_ERR "EXT4-fs: not enough memory\n");

This should report "not enough memory for N flex groups" or something.

OK.

Quoted 10 lines

fs/ext4/super.c static int ext4_fill_super (struct super_block *sb, · line 2158

Quoted 6 lines
fs/ext4/super.c +5 -0
@@ -2105,6 +2154,13 @@ static int ext4_fill_super (struct super_block *sb,
+	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_FLEX_BG))
+		if (!ext4_fill_flex_info(sb)) {
+			printk(KERN_ERR
+			       "EXT4-fs: unable to initialize flex_bg meta info!\n");
+			goto failed_mount2;

Should this be considered a fatal error, or could sbi->s_log_groups_per_flex just be set to 0 and the filesystem be used as-is (maybe with sub-optimal allocations or something)? Otherwise this renders the filesystem unusable.

I thought about doing that but using a sub-optimal allocator would permanently screw up the ondisk data locality. Maybe mounting the filesystem read-only would be more appropriate.

Quoted 6 lines

Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.

-JRS