Re: [PATCH 03/14] xfs: repair free space btrees

[Dave Chinner <david@fromorbit.com>]

On Tue, Jun 05, 2018 at 06:50:26PM -0700, Darrick J. Wong wrote:
> On Mon, Jun 04, 2018 at 12:12:34PM +1000, Dave Chinner wrote:
> > On Wed, May 30, 2018 at 12:30:58PM -0700, Darrick J. Wong wrote:
> > > +
> > > +/* Free space btree repair. */
> > 
> > Can you add a decription of the algorithm used here.
> 
> Ok.
> 
> /*
>  * Free Space Btree Repair
>  * =======================
>  *
>  * The reverse mappings are supposed to record all space usage for the
>  * entire AG.  Therefore, we can recalculate the free extents in an AG
>  * by looking for gaps in the physical extents recorded in the rmapbt.
>  * On a reflink filesystem this is a little more tricky in that we have
>  * to be aware that the rmap records are allowed to overlap.
>  *
>  * We derive which blocks belonged to the old bnobt/cntbt by recording
>  * all the OWN_AG extents and subtracting out the blocks owned by all
>  * other OWN_AG metadata: the rmapbt blocks visited while iterating the
>  * reverse mappings and the AGFL blocks.
>  *
>  * Once we have both of those pieces, we can reconstruct the bnobt and
>  * cntbt by blowing out the free block state and freeing all the extents
>  * that we found.  This adds the requirement that we can't have any busy
>  * extents in the AG because the busy code cannot handle duplicate
>  * records.
>  *
>  * Note that we can only rebuild both free space btrees at the same
>  * time.

Ok, so if I've got this right, the limitations indicated in the last
two paragraphs are a result of makring space free by calling
xfs_free_extent() on all the extents in the list? If so, can you
mention that this is an implementation artifact, not a algorithmic
limitation?

> > > +/* Allocate a block from the (cached) longest extent in the AG. */
> > > +STATIC xfs_fsblock_t
> > > +xfs_repair_allocbt_alloc_from_longest(
> > > +	struct xfs_repair_alloc		*ra,
> > > +	struct xfs_repair_alloc_extent	**longest)
> > > +{
> > > +	xfs_fsblock_t			fsb;
> > > +
> > > +	if (*longest && (*longest)->len == 0) {
> > > +		list_del(&(*longest)->list);
> > > +		kmem_free(*longest);
> > > +		*longest = NULL;
> > > +	}
> > > +
> > > +	if (*longest == NULL) {
> > > +		*longest = xfs_repair_allocbt_get_longest(ra);
> > > +		if (*longest == NULL)
> > > +			return NULLFSBLOCK;
> > > +	}
> > > +
> > > +	fsb = XFS_AGB_TO_FSB(ra->sc->mp, ra->sc->sa.agno, (*longest)->bno);
> > > +	(*longest)->bno++;
> > > +	(*longest)->len--;
> > 
> > What if this makes the longest extent no longer the longest on the
> > extent list?
> 
> It should be fine, since all we do later is zero out the free space
> counters in the AG and start freeing extents.  The regular extent
> freeing code takes care to update the agf/perag longest-free counter
> appropriately.

Comment, please. :P

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com