Flex_BG ialloc awareness.

Hi folk,

Im preparing to clean up the FLEX_BG ialloc patch for inclusion into the patch queue and decided that might as well send the current version of the patch to the mailing list to get any early feedback from folks.

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 the use of FLEX_BG is detected. 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, I 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 begging to end unlike the Orlov algorithm that places a new inode anywhere on the disk where more free inodes and blocks are available. 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.

I've done testing on both SCSI and Fiber Channel attached storage sub-systems and the performance seems to be mostly equal or better than with the regular meta-data allocation. Multi-threaded results on Fiber Channel disk are very impresive though...

FFSB multi-threaded IO workload with no flexbg, flexbg with 64 groups and flexbg with 128 groups:

ext4-normal-profile-crt-delete-append-read-small-threads_64 read :
89490 ops (5.456950%) write : 130001 ops (7.927243%) create : 1116427 ops (68.077847%)
append : 217196 ops (13.244248%)
delete : 86813 ops (5.293711%)
5437.50 Transactions per Second
5.5% User Time
599.9% System Time
605.4% CPU Utilization

ext4-flexbg-64-profile-crt-delete-append-read-small-threads_64 read : 124273 ops (5.462826%)
write : 181257 ops (7.967743%)
create : 1547156 ops (68.010295%)
append : 301872 ops (13.269770%)
delete : 120327 ops (5.289366%)
7559.41 Transactions per Second
7.5% User Time
281.7% System Time
289.2% CPU Utilization

ext4-flexbg-128-profile-crt-delete-append-read-small-threads_64 read : 115689 ops (5.460529%)
write : 168328 ops (7.945093%)
create : 1441175 ops (68.023558%)
append : 280600 ops (13.244339%)
delete : 112849 ops (5.326481%)
7024.59 Transactions per Second
6.6% User Time
296.1% System Time
302.7% CPU Utilization

Also tried Compilebench with 300 initial dirs to see if the improvements seen in FFSB could also be seen in other benchmarks and the results are encouraging.

Normal:
intial create total runs 50 avg 55.74 MB/s (user 1.87s sys 3.68s) create total runs 5 avg 60.24 MB/s (user 1.91s sys 3.37s) patch total runs 4 avg 19.33 MB/s (user 0.77s sys 3.07s) compile total runs 7 avg 110.79 MB/s (user 0.39s sys 4.12s) clean total runs 4 avg 633.64 MB/s (user 0.08s sys 0.64s) read tree total runs 2 avg 11.26 MB/s (user 1.92s sys 2.70s) read compiled tree total runs 1 avg 30.98 MB/s (user 2.44s sys 4.80s) delete tree total runs 2 avg 4.05 seconds (user 1.31s sys 2.78s) no runs for delete compiled tree
stat tree total runs 4 avg 3.78 seconds (user 1.35s sys 0.89s) stat compiled tree total runs 1 avg 4.15 seconds (user 1.45s sys 1.07s)

FLEX_BG 64 groups:
intial create total runs 50 avg 71.97 MB/s (user 1.89s sys 3.82s) create total runs 5 avg 57.35 MB/s (user 1.89s sys 4.85s) patch total runs 4 avg 19.89 MB/s (user 0.76s sys 2.99s) compile total runs 7 avg 116.79 MB/s (user 0.39s sys 4.17s) clean total runs 4 avg 736.80 MB/s (user 0.07s sys 0.62s) read tree total runs 2 avg 15.53 MB/s (user 1.97s sys 2.80s) read compiled tree total runs 1 avg 31.59 MB/s (user 2.48s sys 5.02s) delete tree total runs 2 avg 3.15 seconds (user 1.18s sys 2.50s) no runs for delete compiled tree
stat tree total runs 4 avg 2.43 seconds (user 1.25s sys 0.90s) stat compiled tree total runs 1 avg 3.13 seconds (user 1.48s sys 1.03s)

There are still a couple of things that need fixing in the patch but I would to get some opinions as well.

--

index b102b0e..4ece12d 100644
@@ -600,6 +600,7 @@ void ext4_free_blocks_sb(handle_t *handle, struct super_block *sb,
 	struct ext4_sb_info *sbi;
 	int err = 0, ret;
 	ext4_grpblk_t group_freed;
+	ext4_group_t meta_group;
 
 	*pdquot_freed_blocks = 0;
 	sbi = EXT4_SB(sb);

@@ -745,6 +746,11 @@ do_more:
 	spin_unlock(sb_bgl_lock(sbi, block_group));
 	percpu_counter_add(&sbi->s_freeblocks_counter, count);
 
+	meta_group = ext4_meta_group(sbi, block_group);
+	spin_lock(&sbi->s_meta_groups[meta_group].meta_group_lock);
+	sbi->s_meta_groups[meta_group].free_blocks += count;
+	spin_unlock(&sbi->s_meta_groups[meta_group].meta_group_lock);
+
 	/* We dirtied the bitmap block */
 	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
 	err = ext4_journal_dirty_metadata(handle, bitmap_bh);

@@ -1610,6 +1616,7 @@ ext4_fsblk_t ext4_new_blocks_old(handle_t *handle, struct inode *inode,
 	unsigned short windowsz = 0;
 	ext4_group_t ngroups;
 	unsigned long num = *count;
+	ext4_group_t meta_group;
 
 	*errp = -ENOSPC;
 	sb = inode->i_sb;

@@ -1815,6 +1822,11 @@ allocated:
 	spin_unlock(sb_bgl_lock(sbi, group_no));
 	percpu_counter_sub(&sbi->s_freeblocks_counter, num);
 
+	meta_group = ext4_meta_group(sbi, group_no);
+	spin_lock(&sbi->s_meta_groups[meta_group].meta_group_lock);
+	sbi->s_meta_groups[meta_group].free_blocks -= num;
+	spin_unlock(&sbi->s_meta_groups[meta_group].meta_group_lock);
+
 	BUFFER_TRACE(gdp_bh, "journal_dirty_metadata for group descriptor");
 	err = ext4_journal_dirty_metadata(handle, gdp_bh);
 	if (!fatal)

index bcdb59d..9aaae0a 100644
@@ -152,6 +152,17 @@ struct ext4_group_desc
 	__u32	bg_reserved2[3];
 };
 
+/*
+ * Structure of a meta block group info
+ */
+
+struct meta_groups {
+	__u32 free_inodes;
+	__u32 free_blocks;
+	__u32 num_dirs;
+	spinlock_t meta_group_lock;
+};
+
 #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 */

@@ -1120,6 +1131,12 @@ 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_meta_group(struct ext4_sb_info *sbi,
+					     ext4_group_t block_group)
+{
+	return block_group/sbi->s_groups_per_meta;
+}
+
 #define ext4_std_error(sb, errno)				\
 do {								\
 	if ((errno))						\

index 744e746..6ed33b9 100644
@@ -147,6 +147,9 @@ struct ext4_sb_info {
 
 	/* locality groups */
 	struct ext4_locality_group *s_locality_groups;
+
+	unsigned int s_groups_per_meta;
+	struct meta_groups *s_meta_groups;
 };
 #define EXT4_GROUP_INFO(sb, group)					   \
 	EXT4_SB(sb)->s_group_info[(group) >> EXT4_DESC_PER_BLOCK_BITS(sb)] \

Yes, need to clean the naming on some of these. I also need to look into the mballoc code to see if there is anything I can reuse.

Excellent. I was thinking that one spinlock per flex_bg was overkill as well but I did not know the existence of blockgroup_lock.h.

Yes, thanks for catching.

Seems like I always fall into the same trap. I'll change this.

Thanks.

-JRS