xfs: Improve scalability of busy extent tracking

When we free a metadata extent, we record it in the per-AG busy extent array so that it is not re-used before the freeing transaction hits the disk. This array is fixed size, so when it overflows we make further allocation transactions synchronous because we cannot track more freed extents until those transactions hit the disk and are completed. Under heavy mixed allocation and freeing workloads with large log buffers, we can overflow this array quite easily.

Further, the array is sparsely populated, which means that inserts need to search for a free slot, and array searches often have to search many more slots that are actually used to check all the busy extents. Quite inefficient, really.

To enable this aspect of extent freeing to scale better, we need a structure that can grow dynamically. While in other areas of XFS we have used radix trees, the extents being freed are at random locations on disk so are better suited to being indexed by an rbtree.

So, use a per-AG rbtree indexed by block number to track busy extents. This incures a memory allocation when marking an extent busy, but should not occur too often in low memory situations. This should scale to an arbitrary number of extents so should not be a limitation for features such as in-memory aggregation of transactions.

However, there are still situations where we can't avoid allocating busy extents (such as allocation from the AGFL). To minimise the overhead of such occurences, we need to avoid doing a synchronous log force while holding the AGF locked to ensure that the previous transactions are safely on disk before we use the extent. We can do this by marking the transaction doing the allocation as synchronous rather issuing a log force.

Because of the locking involved and the ordering of transactions, the synchronous transaction provides the same guarantees as a synchronous log force because it ensures that all the prior transactions are already on disk when the synchronous transaction hits the disk. i.e. it preserves the free->allocate order of the extent correctly in recovery.

By doing this, we avoid holding the AGF locked while log writes are in progress, hence reducing the length of time the lock is held and therefore we increase the rate at which we can allocate and free from the allocation group, thereby increasing overall throughput.

The only problem with this approach is that when a metadata buffer is marked stale (e.g. a directory block is removed), then buffer remains pinned and locked until the log goes to disk. The issue here is that if that stale buffer is reallocated in a subsequent transaction, the attempt to lock that buffer in the transaction will hang waiting the log to go to disk to unlock and unpin the buffer. Hence if someone tries to lock a pinned, stale, locked buffer we need to push on the log to get it unlocked ASAP. Effectively we are trading off a guaranteed log force for a much less common trigger for log force to occur.

Ideally we should not reallocate busy extents. That is a much more complex fix to the problem as it involves direct intervention in the allocation btree searches in many places. This is left to a future set of modifications.

Finally, now that we track busy extents in allocated memory, we don't need the descriptors in the transaction structure to point to them. We can replace the complex busy chunk infrastructure with a simple linked list of busy extents. This allows us to remove a large chunk of code, making the overall change a net reduction in code size.

Changes since last version:
o folded all three patches into one - they were too intertwined to keep separate without introducing bugs in the code that got removed in the next patch. This also resulted in significant maintenance overhead because fixing the first patch would make the others reject.
o busy extent transaction owner tracked by transaction id, not by address of transaction structure. Tracking by address of the transaction was triggering false ASSERT failures when searching for busy extents with matching start block numbers.
o minor code cleanups
o tested against blocksize < pagesize filesystems

---
 fs/xfs/linux-2.6/xfs_buf.c      |    9 ++
 fs/xfs/linux-2.6/xfs_quotaops.c |    1 +
 fs/xfs/linux-2.6/xfs_trace.h    |   80 ++++++++----
 fs/xfs/support/debug.c          |    1 +
 fs/xfs/xfs_ag.h                 |   21 ++--
 fs/xfs/xfs_alloc.c              |  272 ++++++++++++++++++++++++--------------
 fs/xfs/xfs_alloc.h              |    5 +-
 fs/xfs/xfs_filestream.c         |    1 +
 fs/xfs/xfs_log.h                |    2 +
 fs/xfs/xfs_log_priv.h           |    2 -
 fs/xfs/xfs_trans.c              |   61 +++++----
 fs/xfs/xfs_trans.h              |   36 +-----
 fs/xfs/xfs_trans_extfree.c      |    1 +
 fs/xfs/xfs_trans_item.c         |  109 ----------------
 fs/xfs/xfs_trans_priv.h         |    6 +-
 15 files changed, 292 insertions(+), 315 deletions(-)

index 5f7a355..a8a3eaf 100644
@@ -37,6 +37,7 @@
 
 #include "xfs_sb.h"
 #include "xfs_inum.h"
+#include "xfs_log.h"
 #include "xfs_ag.h"
 #include "xfs_dmapi.h"
 #include "xfs_mount.h"

@@ -850,6 +851,12 @@ xfs_buf_lock_value(
  *	Note that this in no way locks the underlying pages, so it is only
  *	useful for synchronizing concurrent use of buffer objects, not for
  *	synchronizing independent access to the underlying pages.
+ *
+ *	If we come across a stale, pinned, locked buffer, we know that we
+ *	are being asked to lock a buffer that has been reallocated. Because
+ *	it is pinned, we know that the log has not been pushed to disk and
+ *	hence it will still be locked. Rather than sleeping until someone
+ *	else pushes the log, push it ourselves before trying to get the lock.
  */
 void
 xfs_buf_lock(

@@ -857,6 +864,8 @@ xfs_buf_lock(
 {
 	trace_xfs_buf_lock(bp, _RET_IP_);
 
+	if (atomic_read(&bp->b_pin_count) && (bp->b_flags & XBF_STALE))
+		xfs_log_force(bp->b_mount, 0);
 	if (atomic_read(&bp->b_io_remaining))
 		blk_run_address_space(bp->b_target->bt_mapping);
 	down(&bp->b_sema);

index 1947514..2e73688 100644
@@ -19,6 +19,7 @@
 #include "xfs_dmapi.h"
 #include "xfs_sb.h"
 #include "xfs_inum.h"
+#include "xfs_log.h"
 #include "xfs_ag.h"
 #include "xfs_mount.h"
 #include "xfs_quota.h"

index 3f3610a..c52472f 100644
@@ -21,6 +21,7 @@
 /* xfs_mount.h drags a lot of crap in, sorry.. */
 #include "xfs_sb.h"
 #include "xfs_inum.h"
+#include "xfs_log.h"
 #include "xfs_ag.h"
 #include "xfs_dmapi.h"
 #include "xfs_mount.h"

index abb8222..f2c08c6 100644
@@ -175,14 +175,17 @@ typedef struct xfs_agfl {
 } xfs_agfl_t;
 
 /*
- * Busy block/extent entry.  Used in perag to mark blocks that have been freed
- * but whose transactions aren't committed to disk yet.
+ * Busy block/extent entry.  Indexed by a rbtree in perag to mark blocks that
+ * have been freed but whose transactions aren't committed to disk yet.
  */
-typedef struct xfs_perag_busy {
-	xfs_agblock_t	busy_start;
-	xfs_extlen_t	busy_length;
-	struct xfs_trans *busy_tp;	/* transaction that did the free */
-} xfs_perag_busy_t;
+struct xfs_busy_extent {
+	struct rb_node	rb_node;	/* ag by-bno indexed search tree */
+	struct list_head list;		/* transaction busy extent list */
+	xfs_agnumber_t	agno;
+	xfs_agblock_t	bno;
+	xfs_extlen_t	length;
+	xlog_tid_t	tid;		/* transaction identifier */
+};
 
 /*
  * Per-ag incore structure, copies of information in agf and agi,

@@ -216,7 +219,8 @@ typedef struct xfs_perag {
 	xfs_agino_t	pagl_leftrec;
 	xfs_agino_t	pagl_rightrec;
 #ifdef __KERNEL__
-	spinlock_t	pagb_lock;	/* lock for pagb_list */
+	spinlock_t	pagb_lock;	/* lock for pagb_tree */
+	struct rb_root	pagb_tree;	/* ordered tree of busy extents */
 
 	atomic_t        pagf_fstrms;    /* # of filestreams active in this AG */
 

@@ -226,7 +230,6 @@ typedef struct xfs_perag {
 	int		pag_ici_reclaimable;	/* reclaimable inodes */
 #endif
 	int		pagb_count;	/* pagb slots in use */
-	xfs_perag_busy_t pagb_list[XFS_PAGB_NUM_SLOTS];	/* unstable blocks */
 } xfs_perag_t;
 
 /*

index 599bffa..3b88a6b 100644
@@ -22,6 +22,7 @@ struct xfs_buf;
 struct xfs_mount;
 struct xfs_perag;
 struct xfs_trans;
+struct xfs_busy_extent;
 
 /*
  * Freespace allocation types.  Argument to xfs_alloc_[v]extent.

@@ -125,9 +126,7 @@ xfs_alloc_mark_busy(xfs_trans_t *tp,
 		xfs_extlen_t len);
 
 void
-xfs_alloc_clear_busy(xfs_trans_t *tp,
-		xfs_agnumber_t ag,
-		int idx);
+xfs_alloc_clear_busy(struct xfs_mount *mp, struct xfs_busy_extent *busyp);
 
 #endif	/* __KERNEL__ */
 

index 390850e..f9e1c2d 100644
@@ -23,6 +23,7 @@
 #include "xfs_attr_sf.h"
 #include "xfs_dinode.h"
 #include "xfs_inode.h"
+#include "xfs_log.h"
 #include "xfs_ag.h"
 #include "xfs_dmapi.h"
 #include "xfs_log.h"

index 229d1f3..b8579b7 100644
@@ -18,6 +18,8 @@
 #ifndef	__XFS_LOG_H__
 #define __XFS_LOG_H__
 
+typedef __uint32_t xlog_tid_t;
+
 /* get lsn fields */
 
 #define CYCLE_LSN(lsn) ((uint)((lsn)>>32))

index 9cf6951..ac97bdd 100644
@@ -152,8 +152,6 @@ static inline uint xlog_get_client_id(__be32 i)
 #define	XLOG_RECOVERY_NEEDED	0x4	/* log was recovered */
 #define XLOG_IO_ERROR		0x8	/* log hit an I/O error, and being
 					   shutdown */
-typedef __uint32_t xlog_tid_t;
-
 
 #ifdef __KERNEL__
 /*

index c62beee..0c4a1b5 100644
@@ -813,6 +813,7 @@ struct xfs_log_item_desc;
 struct xfs_mount;
 struct xfs_trans;
 struct xfs_dquot_acct;
+struct xfs_busy_extent;
 
 typedef struct xfs_log_item {
 	struct list_head		li_ail;		/* AIL pointers */

@@ -872,34 +873,6 @@ typedef struct xfs_item_ops {
 #define XFS_ITEM_PUSHBUF	3
 
 /*
- * This structure is used to maintain a list of block ranges that have been
- * freed in the transaction.  The ranges are listed in the perag[] busy list
- * between when they're freed and the transaction is committed to disk.
- */
-
-typedef struct xfs_log_busy_slot {
-	xfs_agnumber_t		lbc_ag;
-	ushort			lbc_idx;	/* index in perag.busy[] */
-} xfs_log_busy_slot_t;
-
-#define XFS_LBC_NUM_SLOTS	31
-typedef struct xfs_log_busy_chunk {
-	struct xfs_log_busy_chunk	*lbc_next;
-	uint				lbc_free;	/* free slots bitmask */
-	ushort				lbc_unused;	/* first unused */
-	xfs_log_busy_slot_t		lbc_busy[XFS_LBC_NUM_SLOTS];
-} xfs_log_busy_chunk_t;
-
-#define	XFS_LBC_MAX_SLOT	(XFS_LBC_NUM_SLOTS - 1)
-#define	XFS_LBC_FREEMASK	((1U << XFS_LBC_NUM_SLOTS) - 1)
-
-#define	XFS_LBC_INIT(cp)	((cp)->lbc_free = XFS_LBC_FREEMASK)
-#define	XFS_LBC_CLAIM(cp, slot)	((cp)->lbc_free &= ~(1 << (slot)))
-#define	XFS_LBC_SLOT(cp, slot)	(&((cp)->lbc_busy[(slot)]))
-#define	XFS_LBC_VACANCY(cp)	(((cp)->lbc_free) & XFS_LBC_FREEMASK)
-#define	XFS_LBC_ISFREE(cp, slot) ((cp)->lbc_free & (1 << (slot)))
-
-/*
  * This is the type of function which can be given to xfs_trans_callback()
  * to be called upon the transaction's commit to disk.
  */

@@ -950,8 +923,7 @@ typedef struct xfs_trans {
 	unsigned int		t_items_free;	/* log item descs free */
 	xfs_log_item_chunk_t	t_items;	/* first log item desc chunk */
 	xfs_trans_header_t	t_header;	/* header for in-log trans */
-	unsigned int		t_busy_free;	/* busy descs free */
-	xfs_log_busy_chunk_t	t_busy;		/* busy/async free blocks */
+	struct list_head	t_busy;		/* list of busy extents */
 	unsigned long		t_pflags;	/* saved process flags state */
 } xfs_trans_t;
 

@@ -980,6 +952,7 @@ typedef struct xfs_trans {
 xfs_trans_t	*xfs_trans_alloc(struct xfs_mount *, uint);
 xfs_trans_t	*_xfs_trans_alloc(struct xfs_mount *, uint, uint);
 xfs_trans_t	*xfs_trans_dup(xfs_trans_t *);
+xlog_tid_t	xfs_trans_get_tid(struct xfs_trans *);
 int		xfs_trans_reserve(xfs_trans_t *, uint, uint, uint,
 				  uint, uint);
 void		xfs_trans_mod_sb(xfs_trans_t *, uint, int64_t);

@@ -1025,9 +998,6 @@ int		_xfs_trans_commit(xfs_trans_t *,
 void		xfs_trans_cancel(xfs_trans_t *, int);
 int		xfs_trans_ail_init(struct xfs_mount *);
 void		xfs_trans_ail_destroy(struct xfs_mount *);
-xfs_log_busy_slot_t *xfs_trans_add_busy(xfs_trans_t *tp,
-					xfs_agnumber_t ag,
-					xfs_extlen_t idx);
 
 extern kmem_zone_t	*xfs_trans_zone;
 

index 27cce2a..1940eef 100644
@@ -21,6 +21,7 @@
 #include "xfs_log.h"
 #include "xfs_inum.h"
 #include "xfs_trans.h"
+#include "xfs_log.h"
 #include "xfs_sb.h"
 #include "xfs_ag.h"
 #include "xfs_dmapi.h"

index 73e2ad3..6698db6 100644
@@ -38,10 +38,8 @@ struct xfs_log_item_desc	*xfs_trans_next_item(struct xfs_trans *,
 void				xfs_trans_free_items(struct xfs_trans *, int);
 void				xfs_trans_unlock_items(struct xfs_trans *,
 							xfs_lsn_t);
-void				xfs_trans_free_busy(xfs_trans_t *tp);
-xfs_log_busy_slot_t		*xfs_trans_add_busy(xfs_trans_t *tp,
-						    xfs_agnumber_t ag,
-						    xfs_extlen_t idx);
+
+void	xfs_trans_free_busy(struct xfs_mount *mp, struct list_head *busy_list);
 
 /*
  * AIL traversal cursor.

1.5.6.5

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

Having the patches merged into one certainly helps with readability. This version also passes xfsqa fine while I had some problems with that with the delayed logging tree.

I'm a bit confused by that. How can we ever find a xfs_busy_extent structure for a transaction that's been freed? We always call xfs_trans_free_busy before freeing the transaction, so this should never happen. And if it can happen we can also get a reuse of the tid, even if it is much more likely. So if there's a corner case I've missed we really need to keep a pointer to the xlog_ticket and keep a reference on it as long as we have busy extents belonging to it in the rbtree.

Besides that here's a few cosmetic comments:

Yeah, I can't explain the root cause, either. Short story: at the time I did this I was getting desperate - I'd been trying to work out the failure you reported for three days and had tried just about everything I could think of. I was thinking that "I know this can't happen but I'm going to rule it out, anyway."

Long story:

I managed to reproduce the xfsqa failures you were seeing in the previous version - I could only reproduce it on a single CPU VM with full kernel preemption enabled. I could get it to either the ASSERT(sync transaction) or corrupt the rbtree.

I confirmed via gdb that when the ASSERT fired the transaction pointed to by the busy extent matched the address of the transaction passed in, but it did not look like the right transaction in any way. i.e. no tracked busy extents, not marked sync, very few items attached and it was usually the first allocation in the transaction. I turned on slab poisoning, the kmemleak detector and so on, and none of them fired indicating a use after free or anything like that. If I looked at the rbtree at this time, it was almost always corrupted in some way.

But then there was the fact that none of the debug I put in to verify the rbtree structure ever caught the tree corruption when it occurred. I only ever caught a corrupted tree before an operation was done, never after an operation had been done. And not only that, the busy extent tracing only ever indicated valid operation sequences leading up to the corruption detection and that the busy extent should not be in the tree whenever the ASSERT fired.

Basically, I could only conclude that the tree was being corrupted by some outside event. Every time I triggered the problem, i ended up seeing exactly the same sort of corruption, but never any new information that would lead me to what corrupted the tree.

This is where I started on trying things that couldn't happen. Reference counting transactions was the first thing I tried, and that didn't fix the problem. Then I randomised the transaction IDs and switched to tracking them to avoid the possibility that somewhere, somehow we incorrectly matched a re-allocated transaction.

To my surprise that made all the failures go away. I can't corrupt the rbtree, I can't trigger the sync transaction assert, none of the debug I added to verify the rbtree found any problems any more, etc, and no matter how much stress or how many different workloads I test against, I cannot get the problem to trip again on any sort of configuration I can test here.

Hence I delayed sending this out again because I'm still clueless as to the root cause and I've been hoping I'd be able to see a new problem with it. But i haven't seen any problems, with or without delayed logging, so wider testing is the only way I'm going to uncover any lingering problem. In a way, I'm kind of disappointed that it fixed the problem you reported...

Like I said, i tried that and it didn't help.

Yeah, I can do that.

OK.

Ok. will fix.

Cheers,

Dave.

Dave Chinner
[email protected]

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

Been looking at this a bit and I have a theory:

- a tid is not actually unique to a xfs_trans structure, if we call xfs_trans_dup a single xlog_ticket, and with that the tid is re-used by multiple transaction structure.
- because of that the major semantic change in the version vs the previous one is that we now do not force the synchronous transaction for the case where we re-used a block in the rolled over transaction.

Still not quite sure about the implications of this.

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

Good point, and an angle I had missed.

The problem case is not re-allocation of the busy extent, it's the subsequent freeing of that extent that is already busy. i.e. we've done "free - alloc - free" before the transaction containing the alloc has hit the disk and cleared the original busy extent from the tree.

In a single transaction case, the alloc should mark the transaction synchronous, so the second free should match the tid and assert that it is synchronous.

The mutliple transaction case can be split up:

	{free} {alloc} {free}: mismatched tids -> log force
	{free - alloc} {free}: mismatched tids -> log force
	{free} {alloc - free}: same as the single transaction case

But as you point out, the mutiple transaction case could have duplicate tids, so the first two cases could be getting it wrong. However, if the tids match, then the ASSERT should fire if the transactions were not sycnhronous.

Hence all I can conclude is that xfsqa is not triggering the first two cases from duplicated transactions, but we need to change tid of the log ticket when we dup transactions.

FWIW, now that you've pointed this out, this appears to be another existing source of duplicate TIDs in the log that I did not identify when I first saw them in the log. It seems to me that the best approach to fixing this is that when we regrant the log space on a permanent log ticket we need to regenerate the ticket tid so that individual components of rolling transactions are not confused in log replay. Does this seem reasonable?

Doing this would also handle the above two cases correctly as well. Despite this, I still can't see how such a scenario would cause the problems with transaction pointer matching because the "same transaction pointer but different transactions" situation still can't occur even with duplicated transactions....

I'll change it and run some tests. It'll be next week before I can get to this, though...

Cheers,

Dave.

Dave Chinner
[email protected]

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

Oh, and while I'm at it:

I'd move the list_del_init(&busyp->list); from xfs_trans_free_busy into xfs_alloc_clear_busy, we also do the list insertation inside xfs_alloc_busy_insert, so that makes it symmetic.

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

Or just merge the loop calling xfs_alloc_clear_busy directly in xfs_trans_free, ala:

Index: xfs/fs/xfs/xfs_alloc.c
===================================================================
@@ -2667,6 +2667,8 @@ xfs_alloc_clear_busy(
 	ASSERT(xfs_alloc_busy_search(mp, busyp->agno, busyp->bno,
 						busyp->length) == 1);
 
+	list_del_init(&busyp->list);
+
 	pag = xfs_perag_get(mp, busyp->agno);
 	spin_lock(&pag->pagb_lock);
 	rb_erase(&busyp->rb_node, &pag->pagb_tree);

Index: xfs/fs/xfs/xfs_trans.c
===================================================================
@@ -620,8 +620,13 @@ _xfs_trans_alloc(
  */
 STATIC void
 xfs_trans_free(
-	xfs_trans_t	*tp)
+	struct xfs_trans	*tp)
 {
+	struct xfs_busy_extent	*busyp, *n;
+
+	list_for_each_entry_safe(busyp, n, &tp->t_busy, list)
+		xfs_alloc_clear_busy(tp->t_mountp, busyp);
+
 	atomic_dec(&tp->t_mountp->m_active_trans);
 	xfs_trans_free_dqinfo(tp);
 	kmem_zone_free(xfs_trans_zone, tp);

@@ -795,23 +800,6 @@ undo_blocks:
 }
 
 /*
- * xfs_trans_free_busy
- * Free all of the busy extents from a transaction
- */
-void
-xfs_trans_free_busy(
-	struct xfs_mount	*mp,
-	struct list_head	*busy_list)
-{
-	struct xfs_busy_extent	*busyp, *n;
-
-	list_for_each_entry_safe(busyp, n, busy_list, list) {
-		list_del_init(&busyp->list);
-		xfs_alloc_clear_busy(mp, busyp);
-	}
-}
-
-/*
  * Record the indicated change to the given field for application
  * to the file system's superblock when the transaction commits.
  * For now, just store the change in the transaction structure.

@@ -1351,7 +1339,6 @@ xfs_trans_committed(
 		kmem_free(licp);
 	}
 
-	xfs_trans_free_busy(tp->t_mountp, &tp->t_busy);
 	xfs_trans_free(tp);
 }
 

@@ -1380,7 +1367,6 @@ xfs_trans_uncommit(
 	xfs_trans_unreserve_and_mod_dquots(tp);
 
 	xfs_trans_free_items(tp, flags);
-	xfs_trans_free_busy(tp->t_mountp, &tp->t_busy);
 	xfs_trans_free(tp);
 }
 

@@ -1629,7 +1615,6 @@ out_unreserve:
 	}
 	current_restore_flags_nested(&tp->t_pflags, PF_FSTRANS);
 	xfs_trans_free_items(tp, error ? XFS_TRANS_ABORT : 0);
-	xfs_trans_free_busy(tp->t_mountp, &tp->t_busy);
 	xfs_trans_free(tp);
 
 	XFS_STATS_INC(xs_trans_empty);

@@ -1708,7 +1693,6 @@ xfs_trans_cancel(
 	current_restore_flags_nested(&tp->t_pflags, PF_FSTRANS);
 
 	xfs_trans_free_items(tp, flags);
-	xfs_trans_free_busy(tp->t_mountp, &tp->t_busy);
 	xfs_trans_free(tp);
 }
 

Index: xfs/fs/xfs/xfs_trans_priv.h
===================================================================
@@ -39,8 +39,6 @@ void				xfs_trans_free_items(struct xfs_
 void				xfs_trans_unlock_items(struct xfs_trans *,
 							xfs_lsn_t);
 
-void	xfs_trans_free_busy(struct xfs_mount *mp, struct list_head *busy_list);
-
 /*
  * AIL traversal cursor.
  *

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

Yeah, that looks like a sane thing to do. I'll update it this way.

Cheers,

Dave.

Dave Chinner
[email protected]

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs