[PATCH] xfs: fix inobt inode allocation search optimization

[PATCH] xfs: fix inobt inode allocation search optimization

[Omar Sandoval]

From: Omar Sandoval <osandov@fb.com>

When we try to allocate a free inode by searching the inobt, we try to
find the inode nearest the parent inode by searching chunks both left
and right of the chunk containing the parent. As an optimization, we
cache the leftmost and rightmost records that we previously searched; if
we do another allocation with the same parent inode, we'll pick up the
search where it last left off.

There's a bug in the case where we found a free inode to the left of the
parent's chunk: we need to update the cached left and right records, but
because we already reassigned the right record to point to the left, we
end up assigning the left record to both the cached left and right
records.

This isn't a correctness problem strictly, but it can result in the next
allocation rechecking chunks unnecessarily or allocating inodes further
away from the parent than it needs to. Fix it by swapping the record
pointer after we update the cached left and right records.

Fixes: bd169565993b ("xfs: speed up free inode search")
Signed-off-by: Omar Sandoval <osandov@fb.com>
---
 fs/xfs/libxfs/xfs_ialloc.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/xfs/libxfs/xfs_ialloc.c b/fs/xfs/libxfs/xfs_ialloc.c
index ffd5a15d1bb6..abf5beaae907 100644
--- a/fs/xfs/libxfs/xfs_ialloc.c
+++ b/fs/xfs/libxfs/xfs_ialloc.c
@@ -1246,13 +1246,13 @@ xfs_dialloc_ag_inobt(
 
 			/* free inodes to the left? */
 			if (useleft && trec.ir_freecount) {
-				rec = trec;
 				xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
 				cur = tcur;
 
 				pag->pagl_leftrec = trec.ir_startino;
 				pag->pagl_rightrec = rec.ir_startino;
 				pag->pagl_pagino = pagino;
+				rec = trec;
 				goto alloc_inode;
 			}
 
-- 
2.14.0

Re: [PATCH] xfs: fix inobt inode allocation search optimization

[Christoph Hellwig]

Looks good,

Reviewed-by: Christoph Hellwig <hch@lst.de>

Re: [PATCH] xfs: fix inobt inode allocation search optimization

[Darrick J. Wong]

On Thu, Aug 10, 2017 at 09:45:45PM -0700, Omar Sandoval wrote:

Looks ok, will test...
Reviewed-by: Darrick J. Wong <darrick.wong@oracle.com>

--D

> From: Omar Sandoval <osandov@fb.com>
> 
> When we try to allocate a free inode by searching the inobt, we try to
> find the inode nearest the parent inode by searching chunks both left
> and right of the chunk containing the parent. As an optimization, we
> cache the leftmost and rightmost records that we previously searched; if
> we do another allocation with the same parent inode, we'll pick up the
> search where it last left off.
> 
> There's a bug in the case where we found a free inode to the left of the
> parent's chunk: we need to update the cached left and right records, but
> because we already reassigned the right record to point to the left, we
> end up assigning the left record to both the cached left and right
> records.
> 
> This isn't a correctness problem strictly, but it can result in the next
> allocation rechecking chunks unnecessarily or allocating inodes further
> away from the parent than it needs to. Fix it by swapping the record
> pointer after we update the cached left and right records.
> 
> Fixes: bd169565993b ("xfs: speed up free inode search")
> Signed-off-by: Omar Sandoval <osandov@fb.com>
> ---
>  fs/xfs/libxfs/xfs_ialloc.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/fs/xfs/libxfs/xfs_ialloc.c b/fs/xfs/libxfs/xfs_ialloc.c
> index ffd5a15d1bb6..abf5beaae907 100644
> --- a/fs/xfs/libxfs/xfs_ialloc.c
> +++ b/fs/xfs/libxfs/xfs_ialloc.c
> @@ -1246,13 +1246,13 @@ xfs_dialloc_ag_inobt(
>  
>  			/* free inodes to the left? */
>  			if (useleft && trec.ir_freecount) {
> -				rec = trec;
>  				xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
>  				cur = tcur;
>  
>  				pag->pagl_leftrec = trec.ir_startino;
>  				pag->pagl_rightrec = rec.ir_startino;
>  				pag->pagl_pagino = pagino;
> +				rec = trec;
>  				goto alloc_inode;
>  			}
>  
> -- 
> 2.14.0
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html