Skip to contentSkip to conversation

implement generic xfs_btree_update

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

lore
Share & tools
lore

Christoph Hellwig

author
#0 lore raw

PATCH 13/21 implement generic xfs_btree_update

From: Dave Chinner <[email protected]>

The most complicated part here is the lastrec tracking for the alloc btree. Most logic is in the update_lastrec method which has to do some hopefully good enough dirty magic to maintain it.

[hch: split out from bigger patch and a rework of the lastrec
logic]

Signed-off-by Christoph Hellwig <[email protected]>
fs/xfs/xfs_btree.c +87 -0
Index: linux-2.6-xfs/fs/xfs/xfs_btree.c
===================================================================
@@ -867,6 +867,30 @@ xfs_btree_get_sibling(
 	}
 }
 
+/*
+ * Return true if ptr is the last record in the btree and
+ * we need to track updateѕ to this record.  The decision
+ * will be further refined in the update_lastrec method.
+ */
+STATIC int
+xfs_btree_is_lastrec(
+	struct xfs_btree_cur	*cur,
+	struct xfs_btree_block	*block,
+	int			level)
+{
+	union xfs_btree_ptr	ptr;
+
+	if (level > 0)
+		return 0;
+	if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE))
+		return 0;
+
+	xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
+	if (!xfs_btree_ptr_is_null(cur, &ptr))
+		return 0;
+	return 1;
+}
+
 STATIC struct xfs_btree_block *
 xfs_btree_buf_to_block(
 	struct xfs_btree_cur	*cur,

@@ -1417,3 +1441,66 @@ xfs_btree_updkey(
 	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 	return 0;
 }
+
+/*
+ * Update the record referred to by cur to the value in the
+ * given record. This either works (return 0) or gets an
+ * EFSCORRUPTED error.
+ */
+int
+xfs_btree_update(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*rec)
+{
+	struct xfs_btree_block	*block;
+	struct xfs_buf		*bp;
+	int			error;
+	int			ptr;
+	union xfs_btree_rec	*rp;
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
+	XFS_BTREE_TRACE_ARGR(cur, rec);
+
+	/* Pick up the current block. */
+	block = xfs_btree_get_block(cur, 0, &bp);
+
+#ifdef DEBUG
+	error = xfs_btree_check_block(cur, block, 0, bp);
+	if (error)
+		goto error0;
+#endif
+	/* Get the address of the rec to be updated. */
+	ptr = cur->bc_ptrs[0];
+	rp = cur->bc_ops->rec_addr(cur, ptr, block);
+
+	/* Fill in the new contents and log them. */
+	cur->bc_ops->copy_recs(cur, rec, rp, 1);
+	cur->bc_ops->log_recs(cur, bp, ptr, ptr);
+
+	/*
+	 * If we are tracking the last record in the tree and
+	 * we are at the far right edge of the tree, update it.
+	 */
+	if (xfs_btree_is_lastrec(cur, block, 0)) {
+		cur->bc_ops->update_lastrec(cur, block, rec,
+					    ptr, LASTREC_UPDATE);
+	}
+
+	/* Updating first rec in leaf. Pass new key value up to our parent. */
+	if (ptr == 1) {
+		union xfs_btree_key	key;
+
+		cur->bc_ops->init_key_from_rec(cur, &key, rec);
+		error = xfs_btree_updkey(cur, &key, 1);
+		if (error)
+			goto error0;
+	}
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
+	return 0;
+
+error0:
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
+	return error;
+}
+
fs/xfs/xfs_alloc_btree.c +92 -104

254 lines not on this page · raw message

fs/xfs/xfs_btree.h +18 -1
Index: linux-2.6-xfs/fs/xfs/xfs_btree.h
===================================================================
@@ -191,6 +191,11 @@ struct xfs_btree_ops {
 	/* get inode rooted btree root */
 	struct xfs_btree_block *(*get_root_from_inode)(struct xfs_btree_cur *);
 
+	/* updated last record information */
+	void	(*update_lastrec)(struct xfs_btree_cur *,
+				  struct xfs_btree_block *,
+				  union xfs_btree_rec *, int, int);
+
 	/* return address of btree structures */
 	union xfs_btree_ptr *(*ptr_addr)(struct xfs_btree_cur *cur, int index,
 					 struct xfs_btree_block *block);

@@ -214,11 +219,15 @@ struct xfs_btree_ops {
 	void	(*copy_keys)(struct xfs_btree_cur *cur,
 			     union xfs_btree_key *src_key,
 			     union xfs_btree_key *dst_key, int numkeys);
+	void	(*copy_recs)(struct xfs_btree_cur *cur,
+			     union xfs_btree_rec *src_rec,
+			     union xfs_btree_rec *dst_rec, int numkeys);
 
 	/* log changes to btree structures */
 	void	(*log_keys)(struct xfs_btree_cur *cur, struct xfs_buf *bp,
 			    int first, int last);
-
+	void	(*log_recs)(struct xfs_btree_cur *cur, struct xfs_buf *bp,
+			    int first, int last);
 
 	/* btree tracing */
 #ifdef XFS_BTREE_TRACE

@@ -241,6 +250,12 @@ struct xfs_btree_ops {
 };
 
 /*
+ * Reasons for the update_lastrec method to be called.
+ */
+#define LASTREC_UPDATE	0
+
+
+/*
  * Btree cursor structure.
  * This collects all information needed by the btree code in one place.
  */

@@ -284,6 +299,7 @@ typedef struct xfs_btree_cur
 /* cursor flags */
 #define XFS_BTREE_LONG_PTRS		(1<<0)	/* pointers are 64bits long */
 #define XFS_BTREE_ROOT_IN_INODE		(1<<1)	/* root may be variable size */
+#define XFS_BTREE_LASTREC_UPDATE	(1<<2)	/* track last rec externally */
 
 
 #define	XFS_BTREE_NOERROR	0

@@ -539,6 +555,7 @@ int xfs_btree_increment(struct xfs_btree
 int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
 int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
 int xfs_btree_updkey(struct xfs_btree_cur *, union xfs_btree_key *, int);
+int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *);
 
 
 /*
fs/xfs/xfs_alloc.c +17 -0
Index: linux-2.6-xfs/fs/xfs/xfs_alloc.c
===================================================================
@@ -136,6 +136,23 @@ xfs_alloc_lookup_le(
 	return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
 }
 
+/*
+ * Update the record referred to by cur to the value given
+ * by [bno, len].
+ * This either works (return 0) or gets an EFSCORRUPTED error.
+ */
+STATIC int				/* error */
+xfs_alloc_update(
+	struct xfs_btree_cur	*cur,	/* btree cursor */
+	xfs_agblock_t		bno,	/* starting block of extent */
+	xfs_extlen_t		len)	/* length of extent */
+{
+	union xfs_btree_rec	rec;
+
+	rec.alloc.ar_startblock = cpu_to_be32(bno);
+	rec.alloc.ar_blockcount = cpu_to_be32(len);
+	return xfs_btree_update(cur, &rec);
+}
 
 /*
  * Compute aligned version of the found extent.
fs/xfs/xfs_alloc_btree.h +0 -7
Index: linux-2.6-xfs/fs/xfs/xfs_alloc_btree.h
===================================================================
@@ -113,13 +113,6 @@ extern int xfs_alloc_get_rec(struct xfs_
  */
 extern int xfs_alloc_insert(struct xfs_btree_cur *cur, int *stat);
 
-/*
- * Update the record referred to by cur, to the value given by [bno, len].
- * This either works (return 0) or gets an EFSCORRUPTED error.
- */
-extern int xfs_alloc_update(struct xfs_btree_cur *cur, xfs_agblock_t bno,
-				xfs_extlen_t len);
-
 
 extern struct xfs_btree_cur *xfs_allocbt_init_cursor(struct xfs_mount *,
 		struct xfs_trans *, struct xfs_buf *,
fs/xfs/xfs_ialloc.c +20 -0
Index: linux-2.6-xfs/fs/xfs/xfs_ialloc.c
===================================================================
@@ -172,6 +172,26 @@ xfs_inobt_lookup_le(
 }
 
 /*
+ * Update the record referred to by cur to the value given
+ * by [ino, fcnt, free].
+ * This either works (return 0) or gets an EFSCORRUPTED error.
+ */
+STATIC int				/* error */
+xfs_inobt_update(
+	struct xfs_btree_cur	*cur,	/* btree cursor */
+	xfs_agino_t		ino,	/* starting inode of chunk */
+	__int32_t		fcnt,	/* free inode count */
+	xfs_inofree_t		free)	/* free inode mask */
+{
+	union xfs_btree_rec	rec;
+
+	rec.inobt.ir_startino = cpu_to_be32(ino);
+	rec.inobt.ir_freecount = cpu_to_be32(fcnt);
+	rec.inobt.ir_free = cpu_to_be64(free);
+	return xfs_btree_update(cur, &rec);
+}
+
+/*
  * Allocate new inodes in the allocation group specified by agbp.
  * Return 0 for success, else error code.
  */
fs/xfs/xfs_ialloc_btree.c +41 -74

146 lines not on this page · raw message

fs/xfs/xfs_ialloc_btree.h +0 -8
Index: linux-2.6-xfs/fs/xfs/xfs_ialloc_btree.h
===================================================================
@@ -135,14 +135,6 @@ extern int xfs_inobt_get_rec(struct xfs_
  */
 extern int xfs_inobt_insert(struct xfs_btree_cur *cur, int *stat);
 
-/*
- * Update the record referred to by cur, to the value given
- * by [ino, fcnt, free].
- * This either works (return 0) or gets an EFSCORRUPTED error.
- */
-extern int xfs_inobt_update(struct xfs_btree_cur *cur, xfs_agino_t ino,
-				__int32_t fcnt, xfs_inofree_t free);
-
 
 extern struct xfs_btree_cur *xfs_inobt_init_cursor(struct xfs_mount *,
 		struct xfs_trans *, struct xfs_buf *, xfs_agnumber_t);
fs/xfs/xfs_bmap.c +18 -0
Index: linux-2.6-xfs/fs/xfs/xfs_bmap.c
===================================================================
@@ -430,6 +430,24 @@ xfs_bmbt_lookup_ge(
 	return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
 }
 
+/*
+* Update the record referred to by cur to the value given
+ * by [off, bno, len, state].
+ * This either works (return 0) or gets an EFSCORRUPTED error.
+ */
+STATIC int
+xfs_bmbt_update(
+	struct xfs_btree_cur	*cur,
+	xfs_fileoff_t		off,
+	xfs_fsblock_t		bno,
+	xfs_filblks_t		len,
+	xfs_exntst_t		state)
+{
+	union xfs_btree_rec	rec;
+
+	xfs_bmbt_disk_set_allf(&rec.bmbt, off, bno, len, state);
+	return xfs_btree_update(cur, &rec);
+}
 
 /*
  * Called from xfs_bmap_add_attrfork to handle btree format files.
fs/xfs/xfs_bmap_btree.c +40 -73

144 lines not on this page · raw message

fs/xfs/xfs_bmap_btree.h +0 -2
Index: linux-2.6-xfs/fs/xfs/xfs_bmap_btree.h
===================================================================
@@ -274,8 +274,6 @@ extern void xfs_bmbt_disk_set_allf(xfs_b
 			xfs_fsblock_t b, xfs_filblks_t c, xfs_exntst_t v);
 
 extern void xfs_bmbt_to_bmdr(xfs_bmbt_block_t *, int, xfs_bmdr_block_t *, int);
-extern int xfs_bmbt_update(struct xfs_btree_cur *, xfs_fileoff_t,
-				xfs_fsblock_t, xfs_filblks_t, xfs_exntst_t);
 
 extern struct xfs_btree_cur *xfs_bmbt_init_cursor(struct xfs_mount *,
 		struct xfs_trans *, struct xfs_inode *, int);
#1 lore raw
Quoted 34 lines · Christoph Hellwig

From: Dave Chinner <[email protected]>

The most complicated part here is the lastrec tracking for the alloc btree. Most logic is in the update_lastrec method which has to do some hopefully good enough dirty magic to maintain it.

[hch: split out from bigger patch and a rework of the lastrec
logic]

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

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

fs/xfs/xfs_btree.c +13 -0
@@ -867,6 +867,30 @@ xfs_btree_get_sibling(
 	}
 }
 
+/*
+ * Return true if ptr is the last record in the btree and
+ * we need to track updateѕ to this record.  The decision
+ * will be further refined in the update_lastrec method.
+ */
+STATIC int
+xfs_btree_is_lastrec(
+	struct xfs_btree_cur	*cur,
+	struct xfs_btree_block	*block,
+	int			level)
+{
+	union xfs_btree_ptr	ptr;
+

fs/xfs/xfs_btree.c xfs_btree_get_sibling( · line 892

Quoted 10 lines
fs/xfs/xfs_btree.c +10 -0
+	if (level > 0)
+		return 0;
+	if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE))
+		return 0;
+
+	xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
+	if (!xfs_btree_ptr_is_null(cur, &ptr))
+		return 0;
+	return 1;
+}

That is not checking if it's the last record - it's checking if it is the rightmost block in the btree. i.e. if the block contains the last record. If the code is to remain this way, that needs renaming.

Quoted 42 lines
fs/xfs/xfs_btree.c +35 -0
+
 STATIC struct xfs_btree_block *
 xfs_btree_buf_to_block(
 	struct xfs_btree_cur	*cur,

@@ -1417,3 +1441,66 @@ xfs_btree_updkey(
 	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 	return 0;
 }
+
+/*
+ * Update the record referred to by cur to the value in the
+ * given record. This either works (return 0) or gets an
+ * EFSCORRUPTED error.
+ */
+int
+xfs_btree_update(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*rec)
+{
+	struct xfs_btree_block	*block;
+	struct xfs_buf		*bp;
+	int			error;
+	int			ptr;
+	union xfs_btree_rec	*rp;
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
+	XFS_BTREE_TRACE_ARGR(cur, rec);
+
+	/* Pick up the current block. */
+	block = xfs_btree_get_block(cur, 0, &bp);
+
+#ifdef DEBUG
+	error = xfs_btree_check_block(cur, block, 0, bp);
+	if (error)
+		goto error0;
+#endif
+	/* Get the address of the rec to be updated. */
+	ptr = cur->bc_ptrs[0];
+	rp = cur->bc_ops->rec_addr(cur, ptr, block);
+
+	/* Fill in the new contents and log them. */
+	cur->bc_ops->copy_recs(cur, rec, rp, 1);

fs/xfs/xfs_btree.c xfs_btree_updkey( · line 1487

Quoted 10 lines
fs/xfs/xfs_btree.c +10 -0
+	cur->bc_ops->log_recs(cur, bp, ptr, ptr);
+
+	/*
+	 * If we are tracking the last record in the tree and
+	 * we are at the far right edge of the tree, update it.
+	 */
+	if (xfs_btree_is_lastrec(cur, block, 0)) {
+		cur->bc_ops->update_lastrec(cur, block, rec,
+					    ptr, LASTREC_UPDATE);
+	}

So this will update the last record on any update to a record in the last block. Seeing as we will typically be allocating out of the last block (where the biggest extents are) this is somewhat additional overhead, right? This is the code that used to trigger the update:

	/*
	 * If it's the by-size btree and it's the last leaf block and
	 * it's the last record... then update the size of the longest
	 * extent in the a.g., which we cache in the a.g. freelist header.
	 */
	if (cur->bc_btnum == XFS_BTNUM_CNT &&
	    be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
	    ptr == be16_to_cpu(block->bb_numrecs)) {

So it's clear we aren't doing the same check here. My original code had the ptr check in it. Why did you drop it?

Quoted 8 lines
fs/xfs/xfs_btree.c +7 -0
+STATIC void
+xfs_allocbt_update_lastrec(
+	struct xfs_btree_cur	*cur,
+	struct xfs_btree_block	*block,
+	union xfs_btree_rec	*rec,
+	int			ptr,
+	int			reason)
 {

.....

Quoted 4 lines
fs/xfs/xfs_btree.c +3 -0
+	struct xfs_agf		*agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
+	xfs_agnumber_t		seqno = be32_to_cpu(agf->agf_seqno);
+	__be32			len;

.....

Quoted 2 lines
fs/xfs/xfs_btree.c +1 -0
+	ASSERT(cur->bc_btnum == XFS_BTNUM_CNT);

.....

Quoted 3 lines
fs/xfs/xfs_btree.c +2 -0
+	switch (reason) {
+	case LASTREC_UPDATE:
 		/*

.....

Quoted 3 lines
fs/xfs/xfs_btree.c +2 -0
+		 * If this is the last leaf block and it's the last record,
+		 * then update the size of the longest extent in the AG.
 		 */

.....

fs/xfs/xfs_btree.c

Quoted 8 lines
fs/xfs/xfs_btree.c +7 -0
+		if (ptr != xfs_btree_get_numrecs(block))
+			return;
+		len = rec->alloc.ar_blockcount;
+		break;
+	default:
+		ASSERT(0);
+		return;
 	}

Oh, it's be moved inside the update code itself. So, why always call the update function and then check the ptr? Why not the way it was originally done?

fs/xfs/xfs_btree.h struct xfs_btree_ops { · line 197

Quoted 11 lines

===================================================================

fs/xfs/xfs_btree.h +4 -0
@@ -191,6 +191,11 @@ struct xfs_btree_ops {
 	/* get inode rooted btree root */
 	struct xfs_btree_block *(*get_root_from_inode)(struct xfs_btree_cur *);
 
+	/* updated last record information */
+	void	(*update_lastrec)(struct xfs_btree_cur *,
+				  struct xfs_btree_block *,
+				  union xfs_btree_rec *, int, int);

Can you add the variable names to the prototype parameters?

Cheers,

Dave.

Signature · 2 lines
Dave Chinner
[email protected]
author
#2 lore raw
Quoted 3 lines · Dave Chinner

Oh, it's be moved inside the update code itself. So, why always call the update function and then check the ptr? Why not the way it was originally done?

Because all three callers do different checks, and I could not proof that they are either identical or hamrless for the other cases. We can clean this mess up later in small standalone patches.

Quoted 6 lines

fs/xfs/xfs_btree.h struct xfs_btree_ops { · line 197

Quoted 4 lines
fs/xfs/xfs_btree.h +4 -0
+	/* updated last record information */
+	void	(*update_lastrec)(struct xfs_btree_cur *,
+				  struct xfs_btree_block *,
+				  union xfs_btree_rec *, int, int);

Can you add the variable names to the prototype parameters?

Done.

#3 lore raw
Quoted 8 lines · Christoph Hellwig
Quoted 3 lines · Dave Chinner

Oh, it's be moved inside the update code itself. So, why always call the update function and then check the ptr? Why not the way it was originally done?

Because all three callers do different checks, and I could not proof that they are either identical or hamrless for the other cases. We can clean this mess up later in small standalone patches.

Ok. Sounds like a good plan.

Cheers,

Dave.

Signature · 2 lines
Dave Chinner
[email protected]