Re: [RFC v3 7/8] ext4: Use rbtrees to manage PAs instead of inode i_prealloc_list

[Ojaswin Mujoo]

Hi Jan, 

Thank you for the review. I've added some comments inline.

On Thu, Sep 29, 2022 at 02:39:26PM +0200, Jan Kara wrote:
> On Tue 27-09-22 14:46:47, Ojaswin Mujoo wrote:
> 
> I've found couple of smaller issues. See below. 
> 
> > ---
> >  fs/ext4/ext4.h    |   4 +-
> >  fs/ext4/mballoc.c | 192 ++++++++++++++++++++++++++++++++--------------
> >  fs/ext4/mballoc.h |   6 +-
> >  fs/ext4/super.c   |   4 +-
> >  4 files changed, 140 insertions(+), 66 deletions(-)
> > 
> > diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
> > index 3bf9a6926798..d54b972f1f0f 100644
> > --- a/fs/ext4/ext4.h
> > +++ b/fs/ext4/ext4.h
> > @@ -1120,8 +1120,8 @@ struct ext4_inode_info {
> >  
> >  	/* mballoc */
> >  	atomic_t i_prealloc_active;
> > -	struct list_head i_prealloc_list;
> > -	spinlock_t i_prealloc_lock;
> > +	struct rb_root i_prealloc_node;
> > +	rwlock_t i_prealloc_lock;
> >  
> >  	/* extents status tree */
> >  	struct ext4_es_tree i_es_tree;
> > diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
> > index b91710fe881f..cd19b9e84767 100644
> > --- a/fs/ext4/mballoc.c
> > +++ b/fs/ext4/mballoc.c
> > @@ -3985,6 +3985,24 @@ static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac)
> >  	mb_debug(sb, "goal %u blocks for locality group\n", ac->ac_g_ex.fe_len);
> >  }
> >  
> > +/*
> > + * This function returns the next element to look at during inode
> > + * PA rbtree walk. We assume that we have held the inode PA rbtree lock
> > + * (ei->i_prealloc_lock)
> > + *
> > + * new_start	The start of the range we want to compare
> > + * cur_start	The existing start that we are comparing against
> > + * node	The node of the rb_tree
> > + */
> > +static inline struct rb_node*
> > +ext4_mb_pa_rb_next_iter(int new_start, int cur_start, struct rb_node *node)
> 
> These need to be ext4_lblk_t, not int.

Noted. Will fix in next version.
> 
> > +{
> > +	if (new_start < cur_start)
> > +		return node->rb_left;
> > +	else
> > +		return node->rb_right;
> > +}
> > +
> 
> > @@ -4032,19 +4055,29 @@ ext4_mb_pa_adjust_overlap(struct ext4_allocation_context *ac,
> >  	new_end = *end;
> >  
> >  	/* check we don't cross already preallocated blocks */
> > -	rcu_read_lock();
> > -	list_for_each_entry_rcu(tmp_pa, &ei->i_prealloc_list, pa_node.inode_list) {
> > -		if (tmp_pa->pa_deleted)
> > +	read_lock(&ei->i_prealloc_lock);
> > +	iter = ei->i_prealloc_node.rb_node;
> > +	while (iter) {
> 
> Perhaps this would be nicer as a for-cycle? Like:
> 
> 	for (iter = ei->i_prealloc_node.rb_node; iter;
> 	     iter = ext4_mb_pa_rb_next_iter(new_start, tmp_pa_start, iter))
> 

Right, I agree. Will do.
> > +		tmp_pa = rb_entry(iter, struct ext4_prealloc_space,
> > +				  pa_node.inode_node);
> > +		tmp_pa_start = tmp_pa->pa_lstart;
> > +		tmp_pa_end = tmp_pa->pa_lstart + EXT4_C2B(sbi, tmp_pa->pa_len);
> > +
> > +		/*
> > +		 * If pa is deleted, ignore overlaps and just iterate in rbtree
> > +		 * based on tmp_pa_start
> > +		 */
> > +		if (tmp_pa->pa_deleted) {
> > +			iter = ext4_mb_pa_rb_next_iter(new_start, tmp_pa_start, iter);
> >  			continue;
> > +		}
> >  		spin_lock(&tmp_pa->pa_lock);
> >  		if (tmp_pa->pa_deleted) {
> >  			spin_unlock(&tmp_pa->pa_lock);
> > +			iter = ext4_mb_pa_rb_next_iter(new_start, tmp_pa_start, iter);
> >  			continue;
> >  		}
> >  
> > -		tmp_pa_start = tmp_pa->pa_lstart;
> > -		tmp_pa_end = tmp_pa->pa_lstart + EXT4_C2B(sbi, tmp_pa->pa_len);
> > -
> >  		/* PA must not overlap original request */
> >  		BUG_ON(!(ac->ac_o_ex.fe_logical >= tmp_pa_end ||
> >  			ac->ac_o_ex.fe_logical < tmp_pa_start));
> > @@ -4052,6 +4085,7 @@ ext4_mb_pa_adjust_overlap(struct ext4_allocation_context *ac,
> >  		/* skip PAs this normalized request doesn't overlap with */
> >  		if (tmp_pa_start >= new_end || tmp_pa_end <= new_start) {
> >  			spin_unlock(&tmp_pa->pa_lock);
> > +			iter = ext4_mb_pa_rb_next_iter(new_start, tmp_pa_start, iter);
> >  			continue;
> >  		}
> >  		BUG_ON(tmp_pa_start <= new_start && tmp_pa_end >= new_end);
> > @@ -4065,8 +4099,9 @@ ext4_mb_pa_adjust_overlap(struct ext4_allocation_context *ac,
> >  			new_end = tmp_pa_start;
> >  		}
> >  		spin_unlock(&tmp_pa->pa_lock);
> > +		iter = ext4_mb_pa_rb_next_iter(new_start, tmp_pa_start, iter);
> >  	}
> > -	rcu_read_unlock();
> > +	read_unlock(&ei->i_prealloc_lock);
> 
> ....
> 
> > @@ -4409,17 +4444,23 @@ ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
> >  		return false;
> >  
> >  	/* first, try per-file preallocation */
> > -	rcu_read_lock();
> > -	list_for_each_entry_rcu(tmp_pa, &ei->i_prealloc_list, pa_node.inode_list) {
> > +	read_lock(&ei->i_prealloc_lock);
> > +	iter = ei->i_prealloc_node.rb_node;
> > +	while (iter) {
> 
> Again, for-cycle would look more natural here.
> 
> > +		tmp_pa = rb_entry(iter, struct ext4_prealloc_space, pa_node.inode_node);
> >  
> >  		/* all fields in this condition don't change,
> >  		 * so we can skip locking for them */
> >  		tmp_pa_start = tmp_pa->pa_lstart;
> >  		tmp_pa_end = tmp_pa->pa_lstart + EXT4_C2B(sbi, tmp_pa->pa_len);
> >  
> > +		/* original request start doesn't lie in this PA */
> >  		if (ac->ac_o_ex.fe_logical < tmp_pa_start ||
> > -		    ac->ac_o_ex.fe_logical >= tmp_pa_end)
> > +		    ac->ac_o_ex.fe_logical >= tmp_pa_end) {
> > +			iter = ext4_mb_pa_rb_next_iter(ac->ac_o_ex.fe_logical,
> > +						  tmp_pa_start, iter);
> >  			continue;
> > +		}
> >  
> >  		/* non-extent files can't have physical blocks past 2^32 */
> >  		if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) &&
> > @@ -4439,12 +4480,14 @@ ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
> >  			ext4_mb_use_inode_pa(ac, tmp_pa);
> >  			spin_unlock(&tmp_pa->pa_lock);
> >  			ac->ac_criteria = 10;
> > -			rcu_read_unlock();
> > +			read_unlock(&ei->i_prealloc_lock);
> >  			return true;
> >  		}
> >  		spin_unlock(&tmp_pa->pa_lock);
> > +		iter = ext4_mb_pa_rb_next_iter(ac->ac_o_ex.fe_logical,
> > +				tmp_pa_start, iter);
> >  	}
> > -	rcu_read_unlock();
> > +	read_unlock(&ei->i_prealloc_lock);
> >  
> >  	/* can we use group allocation? */
> >  	if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))
> > @@ -4596,6 +4639,7 @@ static void ext4_mb_put_pa(struct ext4_allocation_context *ac,
> >  {
> >  	ext4_group_t grp;
> >  	ext4_fsblk_t grp_blk;
> > +	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
> >  
> >  	/* in this short window concurrent discard can set pa_deleted */
> >  	spin_lock(&pa->pa_lock);
> > @@ -4641,16 +4685,51 @@ static void ext4_mb_put_pa(struct ext4_allocation_context *ac,
> >  	ext4_unlock_group(sb, grp);
> >  
> >  	if (pa->pa_type == MB_INODE_PA) {
> > -		spin_lock(pa->pa_node_lock.inode_lock);
> > -		list_del_rcu(&pa->pa_node.inode_list);
> > -		spin_unlock(pa->pa_node_lock.inode_lock);
> > +		write_lock(pa->pa_node_lock.inode_lock);
> > +		rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);
> > +		write_unlock(pa->pa_node_lock.inode_lock);
> > +		ext4_mb_pa_free(pa);
> >  	} else {
> >  		spin_lock(pa->pa_node_lock.lg_lock);
> >  		list_del_rcu(&pa->pa_node.lg_list);
> >  		spin_unlock(pa->pa_node_lock.lg_lock);
> > +		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
> >  	}
> > +}
> > +
> > +static void ext4_mb_rb_insert(struct rb_root *root, struct rb_node *new,
> > +                       int (*cmp)(struct rb_node *, struct rb_node *))
> > +{
> 
> Given this has only one callsite, why not just inline ext4_mb_pa_cmp()
> directly into this function?
> 
> > +       struct rb_node **iter = &root->rb_node, *parent = NULL;
> > +
> > +       while (*iter) {
> > +               parent = *iter;
> > +               if (cmp(new, *iter) > 0)
> > +                       iter = &((*iter)->rb_left);
> > +               else
> > +                       iter = &((*iter)->rb_right);
> > +       }
> > +
> > +       rb_link_node(new, parent, iter);
> > +       rb_insert_color(new, root);
> > +}
> > +
> > +static int ext4_mb_pa_cmp(struct rb_node *new, struct rb_node *cur)
> > +{
> > +	ext4_grpblk_t cur_start, new_start;
>  
> This should be ext4_lblk_t to match with pa->pa_lstart...

Noted, thanks.
> 
> > +	struct ext4_prealloc_space *cur_pa = rb_entry(cur,
> > +						      struct ext4_prealloc_space,
> > +						      pa_node.inode_node);
> > +	struct ext4_prealloc_space *new_pa = rb_entry(new,
> > +						      struct ext4_prealloc_space,
> > +						      pa_node.inode_node);
> > +	cur_start = cur_pa->pa_lstart;
> > +	new_start = new_pa->pa_lstart;
> >  
> > -	call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
> > +	if (new_start < cur_start)
> > +		return 1;
> > +	else
> > +		return -1;
> >  }
> 
> Here and in ext4_mb_rb_insert() the comparison seems to be reversed (thus
> effectively canceling out) but it is still confusing. Usually if we have
> cmp(a,b) functions then if a < b we return -1, if a > b we return 1.

Hmm so for ext4_mb_rb_insert(), it was already defined when I started
with the pathset so I just reused it with a new comparator
ext4_mb_pa_cmp(). While rebasing, I noticed that ext4_mb_rb_insert()
function was removed since we didn't need the rbtree after your changes
to CR1, so I just added it as it is. 

But you are correct, we should modify ext4_mb_rb_insert to make the
return values more intuitive. I'll fix this.
> 
> 								Honza
> -- 
> Jan Kara <jack@xxxxxxxx>
> SUSE Labs, CR

Regards,
ojaswin