Re: [PATCH] xfs: fix off-by-one in inode alloc block reservation calculation

[Brian Foster <bfoster@redhat.com>]

On Thu, Aug 20, 2020 at 10:25:12AM -0700, Darrick J. Wong wrote:
> On Thu, Aug 20, 2020 at 01:07:34PM -0400, Brian Foster wrote:
> > The inode chunk allocation transaction reserves inobt_maxlevels-1
> > blocks to accommodate a full split of the inode btree. A full split
> > requires an allocation for every existing level and a new root
> > block, which means inobt_maxlevels is the worst case block
> > requirement for a transaction that inserts to the inobt. This can
> > lead to a transaction block reservation overrun when tmpfile
> > creation allocates an inode chunk and expands the inobt to its
> > maximum depth. This problem has been observed in conjunction with
> > overlayfs, which makes frequent use of tmpfiles internally.
> > 
> > The existing reservation code goes back as far as the Linux git repo
> > history (v2.6.12). It was likely never observed as a problem because
> > the traditional file/directory creation transactions also include
> > worst case block reservation for directory modifications, which most
> > likely is able to make up for a single block deficiency in the inode
> > allocation portion of the calculation. tmpfile support is relatively
> > more recent (v3.15), less heavily used, and only includes the inode
> > allocation block reservation as tmpfiles aren't linked into the
> > directory tree on creation.
> > 
> > Fix up the inode alloc block reservation macro and a couple of the
> > block allocator minleft parameters that enforce an allocation to
> > leave enough free blocks in the AG for a full inobt split.
> 
> Looks all fine to me, but... does a similar logic apply to the other
> maxlevels uses in the kernel?
> 
> fs/xfs/libxfs/xfs_trans_resv.c:73:      blocks = num_ops * 2 * (2 * mp->m_ag_maxlevels - 1);
> fs/xfs/libxfs/xfs_trans_resv.c:75:              blocks += max(num_ops * (2 * mp->m_rmap_maxlevels - 1),
> fs/xfs/libxfs/xfs_trans_resv.c:78:              blocks += num_ops * (2 * mp->m_refc_maxlevels - 1);
> 
> Can we end up in the same kind of situation with those other trees
> {bno,cnt,rmap,refc} where we have a maxlevels-1 tall tree and split each
> level all the way to the top?
> 

Hmm.. it seems so at first glance, but I'm not sure I follow the
calculations in that function. If we factor out the obvious
num_ops/num_trees components, the comment refers to the following
generic formula:

	((2 blocks/level * max depth) - 1)

I take it that since this is a log reservation calculation, the two
block/level multiplier is there because we have to move records between
two blocks for each level that splits. Is there a reason the -1 is
applied after that multiplier (as opposed to subtracting 1 from the max
depth first)? I'm wondering if that's intentional and it reflects that
the root level is only one block...

Brian

> > Signed-off-by: Brian Foster <bfoster@redhat.com>
> 
> For this bit,
> Reviewed-by: Darrick J. Wong <darrick.wong@oracle.com>
> 
> --D
> 
> > ---
> >  fs/xfs/libxfs/xfs_ialloc.c      | 4 ++--
> >  fs/xfs/libxfs/xfs_trans_space.h | 2 +-
> >  2 files changed, 3 insertions(+), 3 deletions(-)
> > 
> > diff --git a/fs/xfs/libxfs/xfs_ialloc.c b/fs/xfs/libxfs/xfs_ialloc.c
> > index f742a96a2fe1..a6b37db55169 100644
> > --- a/fs/xfs/libxfs/xfs_ialloc.c
> > +++ b/fs/xfs/libxfs/xfs_ialloc.c
> > @@ -688,7 +688,7 @@ xfs_ialloc_ag_alloc(
> >  		args.minalignslop = igeo->cluster_align - 1;
> >  
> >  		/* Allow space for the inode btree to split. */
> > -		args.minleft = igeo->inobt_maxlevels - 1;
> > +		args.minleft = igeo->inobt_maxlevels;
> >  		if ((error = xfs_alloc_vextent(&args)))
> >  			return error;
> >  
> > @@ -736,7 +736,7 @@ xfs_ialloc_ag_alloc(
> >  		/*
> >  		 * Allow space for the inode btree to split.
> >  		 */
> > -		args.minleft = igeo->inobt_maxlevels - 1;
> > +		args.minleft = igeo->inobt_maxlevels;
> >  		if ((error = xfs_alloc_vextent(&args)))
> >  			return error;
> >  	}
> > diff --git a/fs/xfs/libxfs/xfs_trans_space.h b/fs/xfs/libxfs/xfs_trans_space.h
> > index c6df01a2a158..7ad3659c5d2a 100644
> > --- a/fs/xfs/libxfs/xfs_trans_space.h
> > +++ b/fs/xfs/libxfs/xfs_trans_space.h
> > @@ -58,7 +58,7 @@
> >  #define	XFS_IALLOC_SPACE_RES(mp)	\
> >  	(M_IGEO(mp)->ialloc_blks + \
> >  	 ((xfs_sb_version_hasfinobt(&mp->m_sb) ? 2 : 1) * \
> > -	  (M_IGEO(mp)->inobt_maxlevels - 1)))
> > +	  M_IGEO(mp)->inobt_maxlevels))
> >  
> >  /*
> >   * Space reservation values for various transactions.
> > -- 
> > 2.25.4
> > 
>