Re: [PATCH v4 8/9] ext4: Use rbtrees to manage PAs instead of inode i_prealloc_list

[Ojaswin Mujoo]

On Mon, Feb 27, 2023 at 01:19:25PM +0100, Jan Kara wrote:
> On Fri 17-02-23 17:44:17, Ojaswin Mujoo wrote:
> > Currently, the kernel uses i_prealloc_list to hold all the inode
> > preallocations. This is known to cause degradation in performance in
> > workloads which perform large number of sparse writes on a single file.
> > This is mainly because functions like ext4_mb_normalize_request() and
> > ext4_mb_use_preallocated() iterate over this complete list, resulting in
> > slowdowns when large number of PAs are present.
> > 
> > Patch 27bc446e2 partially fixed this by enforcing a limit of 512 for
> > the inode preallocation list and adding logic to continually trim the
> > list if it grows above the threshold, however our testing revealed that
> > a hardcoded value is not suitable for all kinds of workloads.
> > 
> > To optimize this, add an rbtree to the inode and hold the inode
> > preallocations in this rbtree. This will make iterating over inode PAs
> > faster and scale much better than a linked list. Additionally, we also
> > had to remove the LRU logic that was added during trimming of the list
> > (in ext4_mb_release_context()) as it will add extra overhead in rbtree.
> > The discards now happen in the lowest-logical-offset-first order.
> > 
> > ** Locking notes **
> > 
> > With the introduction of rbtree to maintain inode PAs, we can't use RCU
> > to walk the tree for searching since it can result in partial traversals
> > which might miss some nodes(or entire subtrees) while discards happen
> > in parallel (which happens under a lock).  Hence this patch converts the
> > ei->i_prealloc_lock spin_lock to rw_lock.
> > 
> > Almost all the codepaths that read/modify the PA rbtrees are protected
> > by the higher level inode->i_data_sem (except
> > ext4_mb_discard_group_preallocations() and ext4_clear_inode()) IIUC, the
> > only place we need lock protection is when one thread is reading
> > "searching" the PA rbtree (earlier protected under rcu_read_lock()) and
> > another is "deleting" the PAs in ext4_mb_discard_group_preallocations()
> > function (which iterates all the PAs using the grp->bb_prealloc_list and
> > deletes PAs from the tree without taking any inode lock (i_data_sem)).
> > 
> > So, this patch converts all rcu_read_lock/unlock() paths for inode list
> > PA to use read_lock() and all places where we were using
> > ei->i_prealloc_lock spinlock will now be using write_lock().
> > 
> > Note that this makes the fast path (searching of the right PA e.g.
> > ext4_mb_use_preallocated() or ext4_mb_normalize_request()), now use
> > read_lock() instead of rcu_read_lock/unlock().  Ths also will now block
> > due to slow discard path (ext4_mb_discard_group_preallocations()) which
> > uses write_lock().
> > 
> > But this is not as bad as it looks. This is because -
> > 
> > 1. The slow path only occurs when the normal allocation failed and we
> >    can say that we are low on disk space.  One can argue this scenario
> >    won't be much frequent.
> > 
> > 2. ext4_mb_discard_group_preallocations(), locks and unlocks the rwlock
> >    for deleting every individual PA.  This gives enough opportunity for
> >    the fast path to acquire the read_lock for searching the PA inode
> >    list.
> > 
> > Signed-off-by: Ojaswin Mujoo <ojaswin@xxxxxxxxxxxxx>
> 
> Looks good to me. Feel free to add:
> 
> Reviewed-by: Jan Kara <jack@xxxxxxx>
> 
> Just a few style nits below...
> 
> > @@ -3992,80 +4010,162 @@ ext4_mb_pa_assert_overlap(struct ext4_allocation_context *ac,
> >  	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
> >  	struct ext4_prealloc_space *tmp_pa;
> >  	ext4_lblk_t tmp_pa_start, tmp_pa_end;
> > +	struct rb_node *iter;
> >  
> > -	rcu_read_lock();
> > -	list_for_each_entry_rcu(tmp_pa, &ei->i_prealloc_list, pa_node.inode_list) {
> > -		spin_lock(&tmp_pa->pa_lock);
> > -		if (tmp_pa->pa_deleted == 0) {
> > -			tmp_pa_start = tmp_pa->pa_lstart;
> > -			tmp_pa_end = tmp_pa->pa_lstart + EXT4_C2B(sbi, tmp_pa->pa_len);
> > +	read_lock(&ei->i_prealloc_lock);
> > +	for (iter = ei->i_prealloc_node.rb_node; iter;
> > +	     iter = ext4_mb_pa_rb_next_iter(start, tmp_pa_start, iter)) {
> > +		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);
> >  
> > +		spin_lock(&tmp_pa->pa_lock);
> > +		if (tmp_pa->pa_deleted == 0)
> >  			BUG_ON(!(start >= tmp_pa_end || end <= tmp_pa_start));
> > -		}
> >  		spin_unlock(&tmp_pa->pa_lock);
> >  	}
> > -	rcu_read_unlock();
> > +	read_unlock(&ei->i_prealloc_lock);
> >  }
> > -
> 
> Please keep the empty line here.
> 
> > @@ -4402,6 +4502,7 @@ ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
> >  	struct ext4_locality_group *lg;
> >  	struct ext4_prealloc_space *tmp_pa, *cpa = NULL;
> >  	ext4_lblk_t tmp_pa_start, tmp_pa_end;
> > +	struct rb_node *iter;
> >  	ext4_fsblk_t goal_block;
> >  
> >  	/* only data can be preallocated */
> > @@ -4409,14 +4510,17 @@ 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);
> > +	for (iter = ei->i_prealloc_node.rb_node; iter;
> > +	     iter = ext4_mb_pa_rb_next_iter(ac->ac_o_ex.fe_logical, tmp_pa_start, iter)) {
> > +		tmp_pa = rb_entry(iter, struct ext4_prealloc_space, pa_node.inode_node);
> 
> Perhaps wrap above two lines to fit in 80 characters?
> 
> > @@ -5043,17 +5177,18 @@ void ext4_discard_preallocations(struct inode *inode, unsigned int needed)
> >  
> >  repeat:
> >  	/* first, collect all pa's in the inode */
> > -	spin_lock(&ei->i_prealloc_lock);
> > -	while (!list_empty(&ei->i_prealloc_list) && needed) {
> > -		pa = list_entry(ei->i_prealloc_list.prev,
> > -				struct ext4_prealloc_space, pa_node.inode_list);
> > +	write_lock(&ei->i_prealloc_lock);
> > +	for (iter = rb_first(&ei->i_prealloc_node); iter && needed; iter = rb_next(iter)) {
> 
> Wrap this line as well?
> 
> > +		pa = rb_entry(iter, struct ext4_prealloc_space,
> > +				pa_node.inode_node);
> >  		BUG_ON(pa->pa_node_lock.inode_lock != &ei->i_prealloc_lock);
> > +

Thanks for the review Jan and Ritesh. I'll fix the styling issues and
resend the series. 

Ted, just wanted to check if you still want me to rebase this over
Kemeng's [1] mballoc cleanup series since seems like they'll have to
send another version.

[1]
https://lore.kernel.org/linux-ext4/81568343-36fb-aa90-2952-d1f26547541c@xxxxxxxxxxxxxxx/T/#t

Regards,
Ojaswin

> 
> 								Honza
> -- 
> Jan Kara <jack@xxxxxxxx>
> SUSE Labs, CR