implement generic xfs_btree_increment

PATCH In review Christoph Hellwig 2 participants 4 messages Jul 29, 2008 – Aug 2, 2008 XFS filesystem

lore

Share & tools

lore

Christoph Hellwig

author

2008-07-29 19:29 UTC #0 lore raw

PATCH 9/21 implement generic xfs_btree_increment

From: Dave Chinner <[email protected]>

Because this is the first major generic btree routine this patch includes some infrastrucure, fistly a few routines to deal with a btree block that can be either in short or long form, and secondly xfs_btree_read_buf_block, which is the new central routine to read a btree block given a cursor.

[hch: split out from bigger patch and minor adaptions]

Signed-off-by Christoph Hellwig <[email protected]>

Notes:

- xfs_btree_read_buf_block now includes a xfs_btree_check_block, removed duplicate call

fs/xfs/xfs_btree.h +21 -0

Index: linux-2.6-xfs/fs/xfs/xfs_btree.h
===================================================================
@@ -191,6 +191,10 @@ struct xfs_btree_ops {
 	/* get inode rooted btree root */
 	struct xfs_btree_block *(*get_root_from_inode)(struct xfs_btree_cur *);
 
+	/* return address of btree structures */
+	union xfs_btree_ptr *(*ptr_addr)(struct xfs_btree_cur *cur, int index,
+					 struct xfs_btree_block *block);
+
 	/* btree tracing */
 #ifdef XFS_BTREE_TRACE
 	void		(*trace_enter)(struct xfs_btree_cur *, const char *,

@@ -502,6 +506,23 @@ xfs_btree_setbuf(
 	int			lev,	/* level in btree */
 	struct xfs_buf		*bp);	/* new buffer to set */
 
+/*
+ * Common btree core entry points.
+ */
+
+int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
+
+
+/*
+ * Helpers.
+ */
+
+static inline int
+xfs_btree_get_numrecs(struct xfs_btree_block *block)
+{
+	return be16_to_cpu(block->bb_h.bb_numrecs);
+}
+
 #endif	/* __KERNEL__ */

fs/xfs/xfs_btree.c +228 -0

237 lines not on this page · raw message

fs/xfs/xfs_alloc_btree.c +15 ~~-95~~

152 lines not on this page · raw message

fs/xfs/xfs_alloc_btree.h +0 -6

Index: linux-2.6-xfs/fs/xfs/xfs_alloc_btree.h
===================================================================
@@ -114,12 +114,6 @@ extern int xfs_alloc_get_rec(struct xfs_
 				xfs_extlen_t *len, int *stat);
 
 /*
- * Increment cursor by one record at the level.
- * For nonzero levels the leaf-ward information is untouched.
- */
-extern int xfs_alloc_increment(struct xfs_btree_cur *cur, int level, int *stat);
-
-/*
  * Insert the current record at the point referenced by cur.
  * The cursor may be inconsistent on return if splits have been done.
  */

fs/xfs/xfs_alloc.c +6 -6

Index: linux-2.6-xfs/fs/xfs/xfs_alloc.c
===================================================================
@@ -818,7 +818,7 @@ xfs_alloc_ag_vextent_near(
 				XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 				if (ltlen >= args->minlen)
 					break;
-				if ((error = xfs_alloc_increment(cnt_cur, 0, &i)))
+				if ((error = xfs_btree_increment(cnt_cur, 0, &i)))
 					goto error0;
 			} while (i);
 			ASSERT(ltlen >= args->minlen);

@@ -828,7 +828,7 @@ xfs_alloc_ag_vextent_near(
 		i = cnt_cur->bc_ptrs[0];
 		for (j = 1, blen = 0, bdiff = 0;
 		     !error && j && (blen < args->maxlen || bdiff > 0);
-		     error = xfs_alloc_increment(cnt_cur, 0, &j)) {
+		     error = xfs_btree_increment(cnt_cur, 0, &j)) {
 			/*
 			 * For each entry, decide if it's better than
 			 * the previous best entry.

@@ -938,7 +938,7 @@ xfs_alloc_ag_vextent_near(
 	 * Increment the cursor, so we will point at the entry just right
 	 * of the leftward entry if any, or to the leftmost entry.
 	 */
-	if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i)))
+	if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
 		goto error0;
 	if (!i) {
 		/*

@@ -977,7 +977,7 @@ xfs_alloc_ag_vextent_near(
 					args->minlen, &gtbnoa, &gtlena);
 			if (gtlena >= args->minlen)
 				break;
-			if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i)))
+			if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
 				goto error0;
 			if (!i) {
 				xfs_btree_del_cursor(bno_cur_gt,

@@ -1066,7 +1066,7 @@ xfs_alloc_ag_vextent_near(
 					/*
 					 * Fell off the right end.
 					 */
-					if ((error = xfs_alloc_increment(
+					if ((error = xfs_btree_increment(
 							bno_cur_gt, 0, &i)))
 						goto error0;
 					if (!i) {

@@ -1548,7 +1548,7 @@ xfs_free_ag_extent(
 	 * Look for a neighboring block on the right (higher block numbers)
 	 * that is contiguous with this space.
 	 */
-	if ((error = xfs_alloc_increment(bno_cur, 0, &haveright)))
+	if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
 		goto error0;
 	if (haveright) {
 		/*

fs/xfs/xfs_ialloc_btree.c +15 ~~-95~~

152 lines not on this page · raw message

fs/xfs/xfs_ialloc.c +7 -7

Index: linux-2.6-xfs/fs/xfs/xfs_ialloc.c
===================================================================
@@ -695,7 +695,7 @@ nextag:
 				goto error0;
 			XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 			freecount += rec.ir_freecount;
-			if ((error = xfs_inobt_increment(cur, 0, &i)))
+			if ((error = xfs_btree_increment(cur, 0, &i)))
 				goto error0;
 		} while (i == 1);

@@ -753,7 +753,7 @@ nextag:
 			/*
 			 * Search right with cur, go forward 1 record.
 			 */
-			if ((error = xfs_inobt_increment(cur, 0, &i)))
+			if ((error = xfs_btree_increment(cur, 0, &i)))
 				goto error1;
 			doneright = !i;
 			if (!doneright) {

@@ -835,7 +835,7 @@ nextag:
 				 * further right.
 				 */
 				else {
-					if ((error = xfs_inobt_increment(cur, 0,
+					if ((error = xfs_btree_increment(cur, 0,
 							&i)))
 						goto error1;
 					doneright = !i;

@@ -890,7 +890,7 @@ nextag:
 				XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 				if (rec.ir_freecount > 0)
 					break;
-				if ((error = xfs_inobt_increment(cur, 0, &i)))
+				if ((error = xfs_btree_increment(cur, 0, &i)))
 					goto error0;
 				XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 			}

@@ -924,7 +924,7 @@ nextag:
 				goto error0;
 			XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 			freecount += rec.ir_freecount;
-			if ((error = xfs_inobt_increment(cur, 0, &i)))
+			if ((error = xfs_btree_increment(cur, 0, &i)))
 				goto error0;
 		} while (i == 1);
 		ASSERT(freecount == be32_to_cpu(agi->agi_freecount) ||

@@ -1033,7 +1033,7 @@ xfs_difree(
 				goto error0;
 			if (i) {
 				freecount += rec.ir_freecount;
-				if ((error = xfs_inobt_increment(cur, 0, &i)))
+				if ((error = xfs_btree_increment(cur, 0, &i)))
 					goto error0;
 			}
 		} while (i == 1);

@@ -1138,7 +1138,7 @@ xfs_difree(
 				goto error0;
 			if (i) {
 				freecount += rec.ir_freecount;
-				if ((error = xfs_inobt_increment(cur, 0, &i)))
+				if ((error = xfs_btree_increment(cur, 0, &i)))
 					goto error0;
 			}
 		} while (i == 1);

fs/xfs/xfs_ialloc_btree.h +0 -6

Index: linux-2.6-xfs/fs/xfs/xfs_ialloc_btree.h
===================================================================
@@ -136,12 +136,6 @@ extern int xfs_inobt_get_rec(struct xfs_
 			     __int32_t *fcnt, xfs_inofree_t *free, int *stat);
 
 /*
- * Increment cursor by one record at the level.
- * For nonzero levels the leaf-ward information is untouched.
- */
-extern int xfs_inobt_increment(struct xfs_btree_cur *cur, int level, int *stat);
-
-/*
  * Insert the current record at the point referenced by cur.
  * The cursor may be inconsistent on return if splits have been done.
  */

fs/xfs/xfs_itable.c +3 -3

Index: linux-2.6-xfs/fs/xfs/xfs_itable.c
===================================================================
@@ -473,7 +473,7 @@ xfs_bulkstat(
 			 * In any case, increment to the next record.
 			 */
 			if (!error)
-				error = xfs_inobt_increment(cur, 0, &tmp);
+				error = xfs_btree_increment(cur, 0, &tmp);
 		} else {
 			/*
 			 * Start of ag.  Lookup the first inode chunk.

@@ -540,7 +540,7 @@ xfs_bulkstat(
 			 * Set agino to after this chunk and bump the cursor.
 			 */
 			agino = gino + XFS_INODES_PER_CHUNK;
-			error = xfs_inobt_increment(cur, 0, &tmp);
+			error = xfs_btree_increment(cur, 0, &tmp);
 			cond_resched();
 		}
 		/*

@@ -887,7 +887,7 @@ xfs_inumbers(
 			bufidx = 0;
 		}
 		if (left) {
-			error = xfs_inobt_increment(cur, 0, &tmp);
+			error = xfs_btree_increment(cur, 0, &tmp);
 			if (error) {
 				xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
 				cur = NULL;

fs/xfs/xfs_bmap.c +2 -2

Index: linux-2.6-xfs/fs/xfs/xfs_bmap.c
===================================================================
@@ -1646,7 +1646,7 @@ xfs_bmap_add_extent_unwritten_real(
 				PREV.br_blockcount - new->br_blockcount,
 				oldext)))
 				goto done;
-			if ((error = xfs_bmbt_increment(cur, 0, &i)))
+			if ((error = xfs_btree_increment(cur, 0, &i)))
 				goto done;
 			if ((error = xfs_bmbt_update(cur, new->br_startoff,
 				new->br_startblock,

@@ -3253,7 +3253,7 @@ xfs_bmap_del_extent(
 						got.br_startblock, temp,
 						got.br_state)))
 					goto done;
-				if ((error = xfs_bmbt_increment(cur, 0, &i)))
+				if ((error = xfs_btree_increment(cur, 0, &i)))
 					goto done;
 				cur->bc_rec.b = new;
 				error = xfs_bmbt_insert(cur, &i);

fs/xfs/xfs_bmap_btree.c +15 ~~-84~~

141 lines not on this page · raw message

fs/xfs/xfs_bmap_btree.h +0 -1

Index: linux-2.6-xfs/fs/xfs/xfs_bmap_btree.h
===================================================================
@@ -251,7 +251,6 @@ extern void xfs_bmbt_disk_get_all(xfs_bm
 extern xfs_filblks_t xfs_bmbt_disk_get_blockcount(xfs_bmbt_rec_t *r);
 extern xfs_fileoff_t xfs_bmbt_disk_get_startoff(xfs_bmbt_rec_t *r);
 
-extern int xfs_bmbt_increment(struct xfs_btree_cur *, int, int *);
 extern int xfs_bmbt_insert(struct xfs_btree_cur *, int *);
 extern void xfs_bmbt_log_block(struct xfs_btree_cur *, struct xfs_buf *, int);
 extern void xfs_bmbt_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int,

Dave Chinner

2008-07-30 02:06 UTC #1 lore raw

Quoted 11 lines · Christoph Hellwig

From: Dave Chinner <[email protected]>
Because this is the first major generic btree routine this patch includes some infrastrucure, fistly a few routines to deal with a btree block that can be either in short or long form, and secondly xfs_btree_read_buf_block, which is the new central routine to read a btree block given a cursor.
[hch: split out from bigger patch and minor adaptions]
Signed-off-by Christoph Hellwig <[email protected]>

.....

fs/xfs/xfs_btree.h xfs_btree_setbuf( · line 513

Quoted 9 lines

fs/xfs/xfs_btree.h +5 -0

@@ -502,6 +506,23 @@ xfs_btree_setbuf(
 	int			lev,	/* level in btree */
 	struct xfs_buf		*bp);	/* new buffer to set */
 
+/*
+ * Common btree core entry points.
+ */
+
+int xfs_btree_increment(struct xfs_btree_cur *, int, int *);

I think for these interfaces it woul dbe better to include variable names in the prototypes. i.e.:

int xfs_btree_increment(struct xfs_btree_cur *cur, int level, int *stat);

Quoted 16 lines

Index: linux-2.6-xfs/fs/xfs/xfs_btree.c
===================================================================

fs/xfs/xfs_btree.c +1 -0

@@ -35,6 +35,7 @@
 #include "xfs_dinode.h"
 #include "xfs_inode.h"
 #include "xfs_btree.h"
+#include "xfs_btree_trace.h"
 #include "xfs_ialloc.h"
 #include "xfs_error.h"

@@ -829,3 +830,230 @@ xfs_btree_setbuf(
 			cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
 	}
 }

fs/xfs/xfs_btree.c xfs_btree_setbuf( · line 842

Quoted 10 lines

fs/xfs/xfs_btree.c +10 -0

+
+STATIC int
+xfs_btree_ptr_is_null(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_ptr	*ptr)
+{
+	if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
+		return be64_to_cpu(ptr->l) == NULLFSBLOCK;
+	else
+		return be32_to_cpu(ptr->s) == NULLAGBLOCK;

Can kill the else there:

	if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
		return be64_to_cpu(ptr->l) == NULLFSBLOCK;
	return be32_to_cpu(ptr->s) == NULLAGBLOCK;

Quoted 16 lines

fs/xfs/xfs_btree.c +16 -0

+}
+
+/*
+ * Get/set/init sibling pointers
+ */
+STATIC void
+xfs_btree_get_sibling(
+	struct xfs_btree_cur	*cur,
+	struct xfs_btree_block	*block,
+	union xfs_btree_ptr	*ptr,
+	int			lr)
+{
+	ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
+
+	if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
+		if (lr == XFS_BB_RIGHTSIB)

fs/xfs/xfs_btree.c xfs_btree_setbuf( · line 868

Quoted 10 lines

fs/xfs/xfs_btree.c +10 -0

+			ptr->l = block->bb_u.l.bb_rightsib;
+		else
+			ptr->l = block->bb_u.l.bb_leftsib;
+	} else {
+		if (lr == XFS_BB_RIGHTSIB)
+			ptr->s = block->bb_u.s.bb_rightsib;
+		else
+			ptr->s = block->bb_u.s.bb_leftsib;
+	}
+}

Should we use trinary notation for this? i.e:

{
	ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
	if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
		ptr->l = (lr == XFS_BB_RIGHTSIB) ? block->bb_u.l.bb_rightsib
						 : block->bb_u.l.bb_leftsib;
	} else {
		ptr->s = (lr == XFS_BB_RIGHTSIB) ? block->bb_u.s.bb_rightsib
						 : block->bb_u.s.bb_leftsib;
	}
}

Quoted 7 lines

fs/xfs/xfs_btree.c +7 -0

+STATIC xfs_daddr_t
+xfs_btree_ptr_to_daddr(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_ptr	*ptr)
+{
+	if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
+		ASSERT(be64_to_cpu(ptr->l) != NULLFSBLOCK);

fs/xfs/xfs_btree.c xfs_btree_setbuf( · line 898

Quoted 10 lines

fs/xfs/xfs_btree.c +10 -0

+
+		return XFS_FSB_TO_DADDR(cur->bc_mp, be64_to_cpu(ptr->l));
+	} else {
+		ASSERT(cur->bc_private.a.agno != NULLAGNUMBER);
+		ASSERT(be32_to_cpu(ptr->s) != NULLAGBLOCK);
+
+		return XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_private.a.agno,
+					be32_to_cpu(ptr->s));
+	}
+}

Can kill the else here as well...

Quoted 24 lines

fs/xfs/xfs_btree.c +24 -0

+/*
+ * Read in the buffer at the given ptr and return the buffer and
+ * the block pointer within the buffer.
+ */
+STATIC int
+xfs_btree_read_buf_block(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_ptr	*ptr,
+	int			level,
+	int			flags,
+	struct xfs_btree_block	**block,
+	struct xfs_buf		**bpp)
+{
+	struct xfs_mount	*mp = cur->bc_mp;
+	xfs_daddr_t		d;
+	int			error;
+
+	/* need to sort out how callers deal with failures first */
+	ASSERT(!(flags & XFS_BUF_TRYLOCK));
+
+	d = xfs_btree_ptr_to_daddr(cur, ptr);
+	error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d,
+				   mp->m_bsize, flags, bpp);
+	if (error)

fs/xfs/xfs_btree.c xfs_btree_setbuf( · line 954

Quoted 10 lines

fs/xfs/xfs_btree.c +10 -0

+		return error;
+
+	ASSERT(*bpp != NULL);
+	ASSERT(!XFS_BUF_GETERROR(*bpp));
+
+	xfs_btree_set_refs(cur, *bpp);
+	*block = XFS_BUF_TO_BLOCK(*bpp);
+
+	return xfs_btree_check_block(cur, *block, level, *bpp);
+}

Hmmm - if xfs_btree_check_block() returns an error, we won't release the buffer in the error handling path. While this may not be a problem right now (as the only error is EFSCORRUPTED) we want to be able to recover from errors here in the future so we should really exit cleanly form this function....

Quoted 10 lines

fs/xfs/xfs_btree.c +10 -0

+/*
+ * Increment cursor by one record at the level.
+ * For nonzero levels the leaf-ward information is untouched.
+ */
+int						/* error */
+xfs_btree_increment(
+	struct xfs_btree_cur	*cur,
+	int			level,
+	int			*stat)		/* success/failure */
+{

.....

fs/xfs/xfs_btree.c xfs_btree_setbuf( · line 1027

Quoted 8 lines

fs/xfs/xfs_btree.c +8 -0

+	/*
+	 * If we went off the root then we are either seriously
+	 * confused or have the tree root in an inode.
+	 */
+	if (lev == cur->bc_nlevels) {
+		ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
+		goto out0;
+	}

Would it be better here to explicitly test this rather than assert? ie.:

	if (lev == cur->bc_nlevels) {
		if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
			goto out0;
		ASSERT(0);
		error = EFSCORRUPTED;
		goto error0;
	}

So that we get an explicit error reported in the production systems rather than carrying on and dying a horrible death somewhere else....

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

Christoph Hellwig

author

2008-08-01 19:38 UTC #2 lore raw

Quoted 6 lines · Dave Chinner

Quoted 1 line
+int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
I think for these interfaces it woul dbe better to include variable names in the prototypes. i.e.:
int xfs_btree_increment(struct xfs_btree_cur *cur, int level, int *stat);

Well, all this and much more is documented at the implementation site, so I'd avoid this churn. If there are strong feelings for it I can change the prototypes.

Quoted 5 lines

Can kill the else there:

	if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
		return be64_to_cpu(ptr->l) == NULLFSBLOCK;
	return be32_to_cpu(ptr->s) == NULLAGBLOCK;

Normally I'd agree with you, but for the short/long pointer case the if else make the symmetry of the code clear and thus is IMHO better readable.

Quoted 7 lines

fs/xfs/xfs_btree.c xfs_btree_setbuf( · line 868
Quoted 5 lines
fs/xfs/xfs_btree.c +5 -0
+			ptr->s = block->bb_u.s.bb_rightsib;
+		else
+			ptr->s = block->bb_u.s.bb_leftsib;
+	}
+}
Should we use trinary notation for this? i.e:

I find the if else much easier to read.

Quoted 5 lines

Hmmm - if xfs_btree_check_block() returns an error, we won't release the buffer in the error handling path. While this may not be a problem right now (as the only error is EFSCORRUPTED) we want to be able to recover from errors here in the future so we should really exit cleanly form this function....

Fixed.

Quoted 11 lines

Would it be better here to explicitly test this rather than assert? ie.:
	if (lev == cur->bc_nlevels) {
		if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
			goto out0;
		ASSERT(0);
		error = EFSCORRUPTED;
		goto error0;
	}

Quoted 2 lines

So that we get an explicit error reported in the production systems rather than carrying on and dying a horrible death somewhere else....

Yes, this is much better. But we're getting on a slipperly slope here to introduce too many improvements. For the initial patches I'd like to stay as close as possible to the old btree implementations.

Anyway, this change is trivial enough and I've added it.

Dave Chinner

2008-08-02 00:34 UTC #3 lore raw

Quoted 11 lines · Christoph Hellwig

Quoted 6 lines · Dave Chinner
Quoted 1 line
+int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
I think for these interfaces it woul dbe better to include variable names in the prototypes. i.e.:
int xfs_btree_increment(struct xfs_btree_cur *cur, int level, int *stat);
Well, all this and much more is documented at the implementation site, so I'd avoid this churn. If there are strong feelings for it I can change the prototypes.

Not a big deal, really. I was just looking at consistency with the other prototypes around this one....

Quoted 11 lines

Quoted 11 lines
Would it be better here to explicitly test this rather than assert? ie.:
	if (lev == cur->bc_nlevels) {
		if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
			goto out0;
		ASSERT(0);
		error = EFSCORRUPTED;
		goto error0;
	}

Quoted 6 lines

Quoted 2 lines
So that we get an explicit error reported in the production systems rather than carrying on and dying a horrible death somewhere else....
Yes, this is much better. But we're getting on a slipperly slope here to introduce too many improvements. For the initial patches I'd like to stay as close as possible to the old btree implementations.

Sure, but this particular piece of code is different to wthe original btree anyway because it has to handle two different cases. better to get it right first time, IMO.

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]