Re: [PATCH 02/11] xfs: create simplified inode walk function

["Darrick J. Wong" <darrick.wong@oracle.com>]

On Tue, Jun 04, 2019 at 05:41:42PM +1000, Dave Chinner wrote:
> On Wed, May 29, 2019 at 03:26:27PM -0700, Darrick J. Wong wrote:
> > From: Darrick J. Wong <darrick.wong@oracle.com>
> > 
> > Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
> 
> Description? :)
> 
> > +/*
> > + * Walking All the Inodes in the Filesystem
> > + * ========================================
> > + * Starting at some @startino, call a walk function on every allocated inode in
> > + * the system.  The walk function is called with the relevant inode number and
> > + * a pointer to caller-provided data.  The walk function can return the usual
> > + * negative error code, 0, or XFS_IWALK_ABORT to stop the iteration.  This
> > + * return value is returned to the caller.
> 
> The walker iterates inodes in what order? What does it do with
> inodes before @startino?

They're walked in increasing order, and it ignores the ones before @startino.

How about:

/*
 * This iterator function walks a subset of filesystem inodes in increasing
 * order from @startino until there are no more inodes.  For each allocated
 * inode it finds, it calls a walk function with the relevant inode number and
 * a pointer to caller-provided data.  The walk function can return the usual
 * negative error code to stop the iteration; 0 to continue the iteration; or
 * XFS_IWALK_ABORT to stop the iteration.  This return value is returned to the
 * caller.
 */

> > + * Internally, we allow the walk function to do anything, which means that we
> > + * cannot maintain the inobt cursor or our lock on the AGI buffer.  We
> > + * therefore build up a batch of inobt records in kernel memory and only call
> > + * the walk function when our memory buffer is full.
> > + */
> 
> "It is the responsibility of the walk function to ensure it accesses
> allocated inodes, as the inobt records may be stale by the time they are
> acted upon."

Added.

> 
> > +struct xfs_iwalk_ag {
> > +	struct xfs_mount		*mp;
> > +	struct xfs_trans		*tp;
> > +
> > +	/* Where do we start the traversal? */
> > +	xfs_ino_t			startino;
> > +
> > +	/* Array of inobt records we cache. */
> > +	struct xfs_inobt_rec_incore	*recs;
> > +	unsigned int			sz_recs;
> > +	unsigned int			nr_recs;
> 
> sz is the size of the allocated array, nr is the number of entries
> used?

Yes.  I'll clarify that:

	/* Number of entries allocated for the @recs array. */
	unsigned int			sz_recs;

	/* Number of entries in the @recs array that are in use. */
	unsigned int			nr_recs;


> > +	/* Inode walk function and data pointer. */
> > +	xfs_iwalk_fn			iwalk_fn;
> > +	void				*data;
> > +};
> > +
> > +/* Allocate memory for a walk. */
> > +STATIC int
> > +xfs_iwalk_allocbuf(
> > +	struct xfs_iwalk_ag	*iwag)
> > +{
> > +	size_t			size;
> > +
> > +	ASSERT(iwag->recs == NULL);
> > +	iwag->nr_recs = 0;
> > +
> > +	/* Allocate a prefetch buffer for inobt records. */
> > +	size = iwag->sz_recs * sizeof(struct xfs_inobt_rec_incore);
> > +	iwag->recs = kmem_alloc(size, KM_SLEEP);
> > +	if (iwag->recs == NULL)
> > +		return -ENOMEM;
> 
> KM_SLEEP will never fail. You mean to use KM_MAYFAIL here?
> 
> > +
> > +	return 0;
> > +}
> > +
> > +/* Free memory we allocated for a walk. */
> > +STATIC void
> > +xfs_iwalk_freebuf(
> > +	struct xfs_iwalk_ag	*iwag)
> > +{
> > +	ASSERT(iwag->recs != NULL);
> > +	kmem_free(iwag->recs);
> > +}
> 
> No need for the assert here - kmem_free() handles null pointers just
> fine.
> 
> > +/* For each inuse inode in each cached inobt record, call our function. */
> > +STATIC int
> > +xfs_iwalk_ag_recs(
> > +	struct xfs_iwalk_ag		*iwag)
> > +{
> > +	struct xfs_mount		*mp = iwag->mp;
> > +	struct xfs_trans		*tp = iwag->tp;
> > +	struct xfs_inobt_rec_incore	*irec;
> > +	xfs_ino_t			ino;
> > +	unsigned int			i, j;
> > +	xfs_agnumber_t			agno;
> > +	int				error;
> > +
> > +	agno = XFS_INO_TO_AGNO(mp, iwag->startino);
> > +	for (i = 0, irec = iwag->recs; i < iwag->nr_recs; i++, irec++) {
> 
> I kinda prefer single iterator loops for array walking like this:
> 
> 	for (i = 0; i < iwag->nr_recs; i++) {
> 		irec = &iwag->recs[i];
> 
> It's much easier to read and understand what is going on...

Ok, I'll shorten the variable scope while I'm at it.

> > +		trace_xfs_iwalk_ag_rec(mp, agno, irec->ir_startino,
> > +				irec->ir_free);
> 
> Could just pass irec to the trace function and extract startino/free
> within the tracepoint macro....

<nod>

> > +		for (j = 0; j < XFS_INODES_PER_CHUNK; j++) {
> > +			/* Skip if this inode is free */
> > +			if (XFS_INOBT_MASK(j) & irec->ir_free)
> > +				continue;
> > +
> > +			/* Otherwise call our function. */
> > +			ino = XFS_AGINO_TO_INO(mp, agno, irec->ir_startino + j);
> > +			error = iwag->iwalk_fn(mp, tp, ino, iwag->data);
> > +			if (error)
> > +				return error;
> > +		}
> > +	}
> > +
> > +	iwag->nr_recs = 0;
> 
> Why is this zeroed here?

Hmm, that should be pushed to the caller, especially given the name...

> > +	return 0;
> > +}
> > +
> > +/* Read AGI and create inobt cursor. */
> > +static inline int
> > +xfs_iwalk_inobt_cur(
> > +	struct xfs_mount	*mp,
> > +	struct xfs_trans	*tp,
> > +	xfs_agnumber_t		agno,
> > +	struct xfs_btree_cur	**curpp,
> > +	struct xfs_buf		**agi_bpp)
> > +{
> > +	struct xfs_btree_cur	*cur;
> > +	int			error;
> > +
> > +	ASSERT(*agi_bpp == NULL);
> > +
> > +	error = xfs_ialloc_read_agi(mp, tp, agno, agi_bpp);
> > +	if (error)
> > +		return error;
> > +
> > +	cur = xfs_inobt_init_cursor(mp, tp, *agi_bpp, agno, XFS_BTNUM_INO);
> > +	if (!cur)
> > +		return -ENOMEM;
> > +	*curpp = cur;
> > +	return 0;
> > +}
> 
> This is a common pattern. Used in xfs_imap_lookup(), xfs_bulkstat(),
> xfs_inumbers and xfs_inobt_count_blocks. Perhaps should be a common
> inobt function?

We're about to zap the middle two callers, but yes, these two could be
common functions.  I wasn't sure if it was worth it to save a few lines.

> > +
> > +/* Delete cursor and let go of AGI. */
> > +static inline void
> > +xfs_iwalk_del_inobt(
> > +	struct xfs_trans	*tp,
> > +	struct xfs_btree_cur	**curpp,
> > +	struct xfs_buf		**agi_bpp,
> > +	int			error)
> > +{
> > +	if (*curpp) {
> > +		xfs_btree_del_cursor(*curpp, error);
> > +		*curpp = NULL;
> > +	}
> > +	if (*agi_bpp) {
> > +		xfs_trans_brelse(tp, *agi_bpp);
> > +		*agi_bpp = NULL;
> > +	}
> > +}
> > +
> > +/*
> > + * Set ourselves up for walking inobt records starting from a given point in
> > + * the filesystem.
> > + *
> > + * If caller passed in a nonzero start inode number, load the record from the
> > + * inobt and make the record look like all the inodes before agino are free so
> > + * that we skip them, and then move the cursor to the next inobt record.  This
> > + * is how we support starting an iwalk in the middle of an inode chunk.
> > + *
> > + * If the caller passed in a start number of zero, move the cursor to the first
> > + * inobt record.
> > + *
> > + * The caller is responsible for cleaning up the cursor and buffer pointer
> > + * regardless of the error status.
> > + */
> > +STATIC int
> > +xfs_iwalk_ag_start(
> > +	struct xfs_iwalk_ag	*iwag,
> > +	xfs_agnumber_t		agno,
> > +	xfs_agino_t		agino,
> > +	struct xfs_btree_cur	**curpp,
> > +	struct xfs_buf		**agi_bpp,
> > +	int			*has_more)
> > +{
> > +	struct xfs_mount	*mp = iwag->mp;
> > +	struct xfs_trans	*tp = iwag->tp;
> > +	int			icount;
> > +	int			error;
> > +
> > +	/* Set up a fresh cursor and empty the inobt cache. */
> > +	iwag->nr_recs = 0;
> > +	error = xfs_iwalk_inobt_cur(mp, tp, agno, curpp, agi_bpp);
> > +	if (error)
> > +		return error;
> > +
> > +	/* Starting at the beginning of the AG?  That's easy! */
> > +	if (agino == 0)
> > +		return xfs_inobt_lookup(*curpp, 0, XFS_LOOKUP_GE, has_more);
> > +
> > +	/*
> > +	 * Otherwise, we have to grab the inobt record where we left off, stuff
> > +	 * the record into our cache, and then see if there are more records.
> > +	 * We require a lookup cache of at least two elements so that we don't
> > +	 * have to deal with tearing down the cursor to walk the records.
> > +	 */
> > +	error = xfs_bulkstat_grab_ichunk(*curpp, agino - 1, &icount,
> > +			&iwag->recs[iwag->nr_recs]);
> > +	if (error)
> > +		return error;
> > +	if (icount)
> > +		iwag->nr_recs++;
> > +
> > +	ASSERT(iwag->nr_recs < iwag->sz_recs);
> 
> Why this code does what it does with nr_recs is a bit of a mystery
> to me...

sz_recs is the number of records we can store in the inobt record cache,
and nr_recs is the number of records that are actually cached.
Therefore, nr_recs should start at zero and increase until nr == sz at
which point we have to run_callbacks().

I'll add the following to the assert if that was a point of confusion:

	/*
	 * set_prefetch is supposed to give us a large enough inobt
	 * record cache that grab_ichunk can stage a partial first
	 * record and the loop body can cache a record without having to
	 * check for cache space until after it reads an inobt record.
	 */

> > +	return xfs_btree_increment(*curpp, 0, has_more);
> > +}
> > +
> > +typedef int (*xfs_iwalk_ag_recs_fn)(struct xfs_iwalk_ag *iwag);
> > +
> > +/*
> > + * Acknowledge that we added an inobt record to the cache.  Flush the inobt
> > + * record cache if the buffer is full, and position the cursor wherever it
> > + * needs to be so that we can keep going.
> > + */
> > +STATIC int
> > +xfs_iwalk_ag_increment(
> > +	struct xfs_iwalk_ag		*iwag,
> > +	xfs_iwalk_ag_recs_fn		walk_ag_recs_fn,
> > +	xfs_agnumber_t			agno,
> > +	struct xfs_btree_cur		**curpp,
> > +	struct xfs_buf			**agi_bpp,
> > +	int				*has_more)
> > +{
> > +	struct xfs_mount		*mp = iwag->mp;
> > +	struct xfs_trans		*tp = iwag->tp;
> > +	struct xfs_inobt_rec_incore	*irec;
> > +	xfs_agino_t			restart;
> > +	int				error;
> > +
> > +	iwag->nr_recs++;
> > +
> > +	/* If there's space, just increment and look for more records. */
> > +	if (iwag->nr_recs < iwag->sz_recs)
> > +		return xfs_btree_increment(*curpp, 0, has_more);
> 
> Incrementing before explaining why we're incrementing seems a bit
> fack-to-bront....
> 
> > +	/*
> > +	 * Otherwise the record cache is full; delete the cursor and walk the
> > +	 * records...
> > +	 */
> > +	xfs_iwalk_del_inobt(tp, curpp, agi_bpp, 0);
> > +	irec = &iwag->recs[iwag->nr_recs - 1];
> > +	restart = irec->ir_startino + XFS_INODES_PER_CHUNK - 1;
> > +
> > +	error = walk_ag_recs_fn(iwag);
> > +	if (error)
> > +		return error;
> 
> Urk, so an "increment" function actually run all the object callbacks?
> But only if it fails to increment?
> 
> > +
> > +	/* ...and recreate cursor where we left off. */
> > +	error = xfs_iwalk_inobt_cur(mp, tp, agno, curpp, agi_bpp);
> > +	if (error)
> > +		return error;
> > +
> > +	return xfs_inobt_lookup(*curpp, restart, XFS_LOOKUP_GE, has_more);
> 
> And then it goes an increments anyway?
> 
> That's all a bit .... non-obvious. Especially as it has a single
> caller - this should really be something like
> xfs_iwalk_run_callbacks(). Bit more context below...

(I'll just skip to the big code blob below...)

> > +}
> > +
> > +/* Walk all inodes in a single AG, from @iwag->startino to the end of the AG. */
> > +STATIC int
> > +xfs_iwalk_ag(
> > +	struct xfs_iwalk_ag		*iwag)
> > +{
> > +	struct xfs_mount		*mp = iwag->mp;
> > +	struct xfs_trans		*tp = iwag->tp;
> > +	struct xfs_buf			*agi_bp = NULL;
> > +	struct xfs_btree_cur		*cur = NULL;
> > +	xfs_agnumber_t			agno;
> > +	xfs_agino_t			agino;
> > +	int				has_more;
> > +	int				error = 0;
> > +
> > +	/* Set up our cursor at the right place in the inode btree. */
> > +	agno = XFS_INO_TO_AGNO(mp, iwag->startino);
> > +	agino = XFS_INO_TO_AGINO(mp, iwag->startino);
> > +	error = xfs_iwalk_ag_start(iwag, agno, agino, &cur, &agi_bp, &has_more);
> > +	if (error)
> > +		goto out_cur;
> > +
> > +	while (has_more) {
> > +		struct xfs_inobt_rec_incore	*irec;
> > +
> > +		/* Fetch the inobt record. */
> > +		irec = &iwag->recs[iwag->nr_recs];
> > +		error = xfs_inobt_get_rec(cur, irec, &has_more);
> > +		if (error)
> > +			goto out_cur;
> > +		if (!has_more)
> > +			break;
> > +
> > +		/* No allocated inodes in this chunk; skip it. */
> > +		if (irec->ir_freecount == irec->ir_count) {
> > +			error = xfs_btree_increment(cur, 0, &has_more);
> > +			goto next_loop;
> > +		}
> > +
> > +		/*
> > +		 * Start readahead for this inode chunk in anticipation of
> > +		 * walking the inodes.
> > +		 */
> > +		xfs_bulkstat_ichunk_ra(mp, agno, irec);
> > +
> > +		/*
> > +		 * Add this inobt record to our cache, flush the cache if
> > +		 * needed, and move on to the next record.
> > +		 */
> > +		error = xfs_iwalk_ag_increment(iwag, xfs_iwalk_ag_recs, agno,
> > +				&cur, &agi_bp, &has_more);
> 
> Ok, so given this loop already has an increment case in it, it seems
> like it would be better to pull some of this function into the loop
> somewhat like:
> 
> 	while (has_more) {
> 		struct xfs_inobt_rec_incore	*irec;
> 
> 		cond_resched();
> 
> 		/* Fetch the inobt record. */
> 		irec = &iwag->recs[iwag->nr_recs];
> 		error = xfs_inobt_get_rec(cur, irec, &has_more);
> 		if (error || !has_more)
> 			break;
> 
> 		/* No allocated inodes in this chunk; skip it. */
> 		if (irec->ir_freecount == irec->ir_count) {
> 			error = xfs_btree_increment(cur, 0, &has_more);
> 			if (error)
> 				break;
> 			continue;
> 		}
> 
> 		/*
> 		 * Start readahead for this inode chunk in anticipation of
> 		 * walking the inodes.
> 		 */
> 		xfs_bulkstat_ichunk_ra(mp, agno, irec);
> 
> 		/* If there's space in the buffer, just grab more records. */
> 		if (++iwag->nr_recs < iwag->sz_recs)
> 			error = xfs_btree_increment(cur, 0, &has_more);
> 			if (error)
> 				break;
> 			continue;
> 		}
> 
> 		error = xfs_iwalk_run_callbacks(iwag, ...);
> 	}
> 
> 	xfs_iwalk_del_inobt(tp, &cur, &agi_bp, error);
> 	if (!iwag->nr_recs || error)
> 		return error;
> 	return xfs_iwalk_ag_recs(iwag);
> }

Yeah, that is cleaner. :)

> > +	/* Walk any records left behind in the cache. */
> > +	if (iwag->nr_recs) {
> > +		xfs_iwalk_del_inobt(tp, &cur, &agi_bp, error);
> > +		return xfs_iwalk_ag_recs(iwag);
> > +	}
> > +
> > +out_cur:
> > +	xfs_iwalk_del_inobt(tp, &cur, &agi_bp, error);
> > +	return error;
> > +}
> > +
> > +/*
> > + * Given the number of inodes to prefetch, set the number of inobt records that
> > + * we cache in memory, which controls the number of inodes we try to read
> > + * ahead.
> > + *
> > + * If no max prefetch was given, default to one page's worth of inobt records;
> > + * this should be plenty of inodes to read ahead.
> 
> That's a lot of inodes on a 64k page size machine. I think it would
> be better capped at number that doesn't change with processor
> architecture...

4096 / sizeof(...); then?

since that's a single x86 page which means we're unlikely to fail the
memory allocation? :)

> > + */
> > +static inline void
> > +xfs_iwalk_set_prefetch(
> > +	struct xfs_iwalk_ag	*iwag,
> > +	unsigned int		max_prefetch)
> > +{
> > +	if (max_prefetch)
> > +		iwag->sz_recs = round_up(max_prefetch, XFS_INODES_PER_CHUNK) /
> > +					XFS_INODES_PER_CHUNK;
> > +	else
> > +		iwag->sz_recs = PAGE_SIZE / sizeof(struct xfs_inobt_rec_incore);
> > +
> > +	/*
> > +	 * Allocate enough space to prefetch at least two records so that we
> > +	 * can cache both the inobt record where the iwalk started and the next
> > +	 * record.  This simplifies the AG inode walk loop setup code.
> > +	 */
> > +	if (iwag->sz_recs < 2)
> > +		iwag->sz_recs = 2;
> 
> 	iwag->sz_recs = max(iwag->sz_recs, 2);
> 
> ....
> > +	xfs_iwalk_set_prefetch(&iwag, max_prefetch);
> > +	error = xfs_iwalk_allocbuf(&iwag);
> ....
> > +	xfs_iwalk_freebuf(&iwag);
> 
> I'd drop the "buf" from the names of those two functions...

<nod>

--D

> Cheers,
> 
> Dave.
> -- 
> Dave Chinner
> david@fromorbit.com