ocfs2: Inode Allocation Strategy Improvement

In ocfs2, the inode block search looks for the "emptiest" inode group to allocate from. So if an inode alloc file has many equally (or almost equally) empty groups, new inodes will tend to get spread out amongst them, which in turn can put them all over the disk. This is undesirable because directory operations on conceptually "nearby" inodes force a large number of seeks.

The good thing is that in ocfs2_alloc_context, there is a field named ac_last_group which will record the last group we allocate from. So we can only pass the right group to it and the following allocation will do as what we expect.

So we add ip_last_used_group in core directory inodes which records the last used allocation group. Another field named ip_last_used_slot is also added in case inode stealing happens. When claiming new inode, we passed in directory's inode so that the allocation can use this information.
For more details, please see
http://oss.oracle.com/osswiki/OCFS2/DesignDocs/InodeAllocationStrategy.

Signed-off-by Tao Ma <[email protected]>

---
 fs/ocfs2/inode.c    |    2 ++
 fs/ocfs2/inode.h    |    4 ++++
 fs/ocfs2/namei.c    |    4 ++--
 fs/ocfs2/suballoc.c |   21 +++++++++++++++++++++
 fs/ocfs2/suballoc.h |    2 ++
 5 files changed, 31 insertions(+), 2 deletions(-)

fs/ocfs2/inode.c +2 -0

index 288512c..c3463c1 100644
@@ -350,6 +350,8 @@ void ocfs2_populate_inode(struct inode *inode, struct ocfs2_dinode *fe,
 
 	ocfs2_set_inode_flags(inode);
 
+	OCFS2_I(inode)->ip_last_used_slot = 0;
+	OCFS2_I(inode)->ip_last_used_group = 0;
 	mlog_exit_void();
 }
 

fs/ocfs2/inode.h +4 -0

index eb3c302..e1978ac 100644
@@ -72,6 +72,10 @@ struct ocfs2_inode_info
 
 	struct inode			vfs_inode;
 	struct jbd2_inode		ip_jinode;
+
+	/* Only valid if the inode is the dir. */
+	u32				ip_last_used_slot;
+	u64				ip_last_used_group;
 };
 
 /*

fs/ocfs2/namei.c +2 -2

index 02c8026..a601dd5 100644
@@ -469,8 +469,8 @@ static int ocfs2_mknod_locked(struct ocfs2_super *osb,
 
 	*new_fe_bh = NULL;
 
-	status = ocfs2_claim_new_inode(osb, handle, inode_ac, &suballoc_bit,
-				       &fe_blkno);
+	status = ocfs2_claim_new_inode(osb, handle, dir, parent_fe_bh,
+				       inode_ac, &suballoc_bit, &fe_blkno);
 	if (status < 0) {
 		mlog_errno(status);
 		goto leave;

fs/ocfs2/suballoc.c +8 -0

index 226fe21..f75782f 100644
@@ -1587,6 +1587,8 @@ bail:
 
 int ocfs2_claim_new_inode(struct ocfs2_super *osb,
 			  handle_t *handle,
+			  struct inode *dir,
+			  struct buffer_head *parent_fe_bh,
 			  struct ocfs2_alloc_context *ac,
 			  u16 *suballoc_bit,
 			  u64 *fe_blkno)

@@ -1594,6 +1596,8 @@ int ocfs2_claim_new_inode(struct ocfs2_super *osb,
 	int status;
 	unsigned int num_bits;
 	u64 bg_blkno;
+	struct ocfs2_dinode *parent_fe =
+			(struct ocfs2_dinode *)parent_fe_bh->b_data;
 
 	mlog_entry_void();
 

@@ -1602,6 +1606,21 @@ int ocfs2_claim_new_inode(struct ocfs2_super *osb,
 	BUG_ON(ac->ac_bits_wanted != 1);
 	BUG_ON(ac->ac_which != OCFS2_AC_USE_INODE);
 
+	/*
+	 * Try to allocate inodes from some specific group.
+	 *
+	 * If the parent dir has recorded the last group used in allocation,

Quoted 13 lines

fs/ocfs2/suballoc.c +9 -0

@@ -1602,6 +1606,21 @@ int ocfs2_claim_new_inode(struct ocfs2_super *osb,
 	BUG_ON(ac->ac_bits_wanted != 1);
 	BUG_ON(ac->ac_which != OCFS2_AC_USE_INODE);
 
+	/*
+	 * Try to allocate inodes from some specific group.
+	 *
+	 * If the parent dir has recorded the last group used in allocation,
+	 * cool, use it. Otherwise if we try to allocate new inode from the
+	 * same slot the parent dir belongs to, use the same chunk.
+	 */
+	if (OCFS2_I(dir)->ip_last_used_group &&
+	    OCFS2_I(dir)->ip_last_used_slot == ac->ac_alloc_slot)

fs/ocfs2/suballoc.c int ocfs2_claim_new_inode(struct ocfs2_super *osb, · line 1622

Quoted 5 lines

fs/ocfs2/suballoc.c +5 -0

+		ac->ac_last_group = OCFS2_I(dir)->ip_last_used_group;
+	else if (le16_to_cpu(parent_fe->i_suballoc_slot) ==
+		 ac->ac_alloc_slot)
+		ac->ac_last_group = le64_to_cpu(parent_fe->i_blkno) -
+				    le16_to_cpu(parent_fe->i_suballoc_bit);

You should use ocfs2_which_suballoc_group() here, instead of open coding the math to get ac_last_group.

Also, would it be possible for us to put this block in it's own function so that it's easier to play with the logic in the future?

One last thing - can you add to the comment:

*
* We are very careful here to avoid the mistake of setting ac_last_group to
* a group descriptor from a different (unlocked) slot.
*/

Inode groups used to be allocated from local alloc file, but since we want all inodes to be contiguous enough, we will try to allocate them directly from global_bitmap.

Add a new flag named "ALLOC_NEW_GROUP_FROM_GLOBAL", if we pass this flag into allocation, don't try local alloc.

Signed-off-by Tao Ma <[email protected]>

---
 fs/ocfs2/suballoc.c |   33 +++++++++++++++++++++------------
 1 files changed, 21 insertions(+), 12 deletions(-)

fs/ocfs2/suballoc.c +0 -0

index f75782f..98e32b2 100644

fs/ocfs2/suballoc.c +2 -1

 #define OCFS2_MAX_INODES_TO_STEAL	1024
 

@@ -63,7 +64,8 @@ static int ocfs2_block_group_fill(handle_t *handle,
 static int ocfs2_block_group_alloc(struct ocfs2_super *osb,
 				   struct inode *alloc_inode,
 				   struct buffer_head *bh,
-				   u64 max_block);
+				   u64 max_block,
+				   int flags);
 
 static int ocfs2_cluster_group_search(struct inode *inode,
 				      struct buffer_head *group_bh,

In ocfs2, the block group search looks for the "emptiest" group to allocate from. So if the allocator has many equally(or almost equally) empty groups, new block group will tend to get spread out amongst them.

We add osb_last_alloc_group in ocfs2_super to record the last used allocation group so that next time we can allocate inode group directly from it.
For more details, please see
http://oss.oracle.com/osswiki/OCFS2/DesignDocs/InodeAllocationStrategy.

Signed-off-by Tao Ma <[email protected]>

---
 fs/ocfs2/ocfs2.h    |    3 +++
 fs/ocfs2/suballoc.c |   18 +++++++++++++++++-
 fs/ocfs2/super.c    |    1 +
 3 files changed, 21 insertions(+), 1 deletions(-)

fs/ocfs2/ocfs2.h +0 -0

index 5c77798..a99b53e 100644

fs/ocfs2/ocfs2.h +0 -0

 };
 
 #define OCFS2_SB(sb)	    ((struct ocfs2_super *)(sb)->s_fs_info)

fs/ocfs2/suballoc.c +6 -0

index 98e32b2..3ab1135 100644
@@ -49,6 +49,7 @@
 #define NOT_ALLOC_NEW_GROUP		0
 #define ALLOC_NEW_GROUP			0x1
 #define ALLOC_NEW_GROUP_FROM_GLOBAL	0x2
+#define ALLOC_USE_RECORD_GROUP		0x4
 
 #define OCFS2_MAX_INODES_TO_STEAL	1024
 

@@ -411,6 +412,11 @@ static int ocfs2_block_group_alloc(struct ocfs2_super *osb,
 		goto bail;
 	}
 
+	if (flags & ALLOC_USE_RECORD_GROUP && osb->osb_last_alloc_group) {
+		mlog(0, "use old allocation group %llu\n",
+		     (unsigned long long)osb->osb_last_alloc_group);
+		ac->ac_last_group = osb->osb_last_alloc_group;
+	}
 	status = ocfs2_claim_clusters(osb,
 				      handle,
 				      ac,

@@ -485,6 +491,15 @@ static int ocfs2_block_group_alloc(struct ocfs2_super *osb,
 	alloc_inode->i_blocks = ocfs2_inode_sector_count(alloc_inode);
 

Quoted 18 lines · Tao Ma

In ocfs2, the block group search looks for the "emptiest" group to allocate from. So if the allocator has many equally(or almost equally) empty groups, new block group will tend to get spread out amongst them.

We add osb_last_alloc_group in ocfs2_super to record the last used allocation group so that next time we can allocate inode group directly from it.
For more details, please see
http://oss.oracle.com/osswiki/OCFS2/DesignDocs/InodeAllocationStrategy.

Signed-off-by Tao Ma <[email protected]>

---
 fs/ocfs2/ocfs2.h    |    3 +++
 fs/ocfs2/suballoc.c |   18 +++++++++++++++++-
 fs/ocfs2/super.c    |    1 +
 3 files changed, 21 insertions(+), 1 deletions(-)

fs/ocfs2/ocfs2.h struct ocfs2_super · line 340

Quoted 11 lines

fs/ocfs2/ocfs2.h +3 -0

index 5c77798..a99b53e 100644
@@ -335,6 +335,9 @@ struct ocfs2_super
 	struct ocfs2_node_map		osb_recovering_orphan_dirs;
 	unsigned int			*osb_orphan_wipes;
 	wait_queue_head_t		osb_wipe_event;
+
+	/* the group we used to allocate inodes. */
+	u64				osb_last_alloc_group;

Can you give this a name which is more specific to the inode allocators? That way we can just add another u64 later for the metadata allocators, should we decide to do the same for them.

Quoted 32 lines

fs/ocfs2/ocfs2.h +0 -0

 };
 
 #define OCFS2_SB(sb)	    ((struct ocfs2_super *)(sb)->s_fs_info)

fs/ocfs2/suballoc.c +6 -0

index 98e32b2..3ab1135 100644
@@ -49,6 +49,7 @@
 #define NOT_ALLOC_NEW_GROUP		0
 #define ALLOC_NEW_GROUP			0x1
 #define ALLOC_NEW_GROUP_FROM_GLOBAL	0x2
+#define ALLOC_USE_RECORD_GROUP		0x4
 
 #define OCFS2_MAX_INODES_TO_STEAL	1024
 

@@ -411,6 +412,11 @@ static int ocfs2_block_group_alloc(struct ocfs2_super *osb,
 		goto bail;
 	}
 
+	if (flags & ALLOC_USE_RECORD_GROUP && osb->osb_last_alloc_group) {
+		mlog(0, "use old allocation group %llu\n",
+		     (unsigned long long)osb->osb_last_alloc_group);
+		ac->ac_last_group = osb->osb_last_alloc_group;
+	}
 	status = ocfs2_claim_clusters(osb,
 				      handle,
 				      ac,

@@ -485,6 +491,15 @@ static int ocfs2_block_group_alloc(struct ocfs2_super *osb,
 	alloc_inode->i_blocks = ocfs2_inode_sector_count(alloc_inode);
 

fs/ocfs2/suballoc.c static int ocfs2_block_group_alloc(struct ocfs2_super *osb, · line 502

Quoted 10 lines

fs/ocfs2/suballoc.c +9 -0

 	status = 0;
+
+	if (flags & ALLOC_USE_RECORD_GROUP) {
+		spin_lock(&osb->osb_lock);
+		osb->osb_last_alloc_group = ac->ac_last_group;
+		spin_unlock(&osb->osb_lock);
+		mlog(0, "after reservation, new allocation group is "
+		     "%llu\n", (unsigned long long)osb->osb_last_alloc_group);
+	}
+

How about we instead add a u64 * argument to ocfs2_block_group_alloc() and ocfs2_reserve_suballoc_bits(). Inside ocfs2_block_group_alloc, we'd test for it to be non-null before using it. That way, any other allocator code which wants to use this mechanism only has to modify a function parameter. If you'd rather test for the flag instead of non-null, that's ok too so long as the end result is the same - new users just have to modify their parameters to ocfs2_reserve_suballoc_bits().

fs/ocfs2/super.c static int ocfs2_fill_super(struct super_block *sb, void *data, int silent) · line 846

Quoted 11 lines

fs/ocfs2/super.c +1 -0

index bc43138..3593759 100644
@@ -843,6 +843,7 @@ static int ocfs2_fill_super(struct super_block *sb, void *data, int silent)
 	osb->osb_commit_interval = parsed_options.commit_interval;
 	osb->local_alloc_default_bits = ocfs2_megabytes_to_clusters(sb, parsed_options.localalloc_opt);
 	osb->local_alloc_bits = osb->local_alloc_default_bits;
+	osb->osb_last_alloc_group = 0;

Won't this already be zero'd for us by ocfs2_initialize_super()?

Quoted 10 lines

fs/ocfs2/ocfs2.h struct ocfs2_super · line 340

Quoted 6 lines

	struct ocfs2_node_map		osb_recovering_orphan_dirs;
	unsigned int			*osb_orphan_wipes;
	wait_queue_head_t		osb_wipe_event;

fs/ocfs2/ocfs2.h +3 -0

+
+	/* the group we used to allocate inodes. */
+	u64				osb_last_alloc_group;

Can you give this a name which is more specific to the inode allocators? That way we can just add another u64 later for the metadata allocators, should we decide to do the same for them.

How about osb_inode_alloc_group?

Hi all,
In ocfs2, when we create a fresh file system and create inodes in it, they are contiguous and good for readdir+stat. While if we delete all
the inodes and created again, the new inodes will get spread out and that isn't what we need. The core problem here is that the inode block search looks for the "emptiest" inode group to allocate from. So if an

inode alloc file has many equally (or almost equally) empty groups, new inodes will tend to get spread out amongst them, which in turn can put them all over the disk. This is undesirable because directory operations on conceptually "nearby" inodes force a large number of seeks. For more details, please see
http://oss.oracle.com/osswiki/OCFS2/DesignDocs/InodeAllocationStrategy.(I
have modified it a little, Mark, if you are interested, please look at it. They are underlined.)

So this patch set try to fix this problem.
patch 1: Optimize inode allocation by remembering last group. We add ip_last_used_group in core directory inodes which records the last used allocation group. Another field named ip_last_used_slot is also added in case inode stealing happens. When claiming new inode, we passed in directory's inode so that the allocation can use this information.

patch 2: let the Inode group allocs use the global bitmap directly.

patch 3: we add osb_last_alloc_group in ocfs2_super to record the last used allocation group so that we can make inode groups contiguous enough.

Quoted 6 lines · Tao Ma

Hi all,
In ocfs2, when we create a fresh file system and create inodes in it, they are contiguous and good for readdir+stat. While if we delete all
the inodes and created again, the new inodes will get spread out and that isn't what we need. The core problem here is that the inode block search looks for the "emptiest" inode group to allocate from. So if an

Quoted 8 lines

inode alloc file has many equally (or almost equally) empty groups, new inodes will tend to get spread out amongst them, which in turn can put them all over the disk. This is undesirable because directory operations on conceptually "nearby" inodes force a large number of seeks. For more details, please see
http://oss.oracle.com/osswiki/OCFS2/DesignDocs/InodeAllocationStrategy.(I
have modified it a little, Mark, if you are interested, please look at it. They are underlined.)

Your edits look fine. Thanks for updating the design doc.

Quoted 10 lines

So this patch set try to fix this problem.
patch 1: Optimize inode allocation by remembering last group. We add ip_last_used_group in core directory inodes which records the last used allocation group. Another field named ip_last_used_slot is also added in case inode stealing happens. When claiming new inode, we passed in directory's inode so that the allocation can use this information.

Quoted 4 lines

patch 2: let the Inode group allocs use the global bitmap directly.

patch 3: we add osb_last_alloc_group in ocfs2_super to record the last used allocation group so that we can make inode groups contiguous enough.

So, the logic in your patches is correct. As you can see, most of my comments were more about code flow or trivial cleanups. Assuming this all works as we expect, there shouldn't be much code for you to modify before the patches can be put in the merge_window branch.

One things though - would you mind providing a small amount of data to show what sort of improvement (if any) we're getting from these patches? I don't think we need anything fancy - just enough to answer the following two questions:

- How much does this improve our inode fragmentation level?

Any test that fragments the inode space would be appropriate for this.

We could then simply express fragmentation as some value - maybe a ratio of adjacent inodes as compared to total # of inodes, expressed as a percentage value. It would be nice for future testing if we had a small tool to calculate this (maybe by libocfs2, or by just making readdir calls and looking at inode number),

- Does the 2nd patch impact overall inode creation times in a cluster, since we're now using the cluster bitmap instead of local alloc.