Skip to contentSkip to conversation

Replace buffer cache hash with rbtrees

RFC PATCH In review Dave Chinner 3 participants 17 messages Sep 8, 2010 – Sep 14, 2010 XFS filesystem

lore
Share & tools
lore
#0 lore raw

cover Replace buffer cache hash with rbtrees

This patch series cleans up several unconventional buffer uses to avoid using cached buffers, and then converts the buffer cache indexing to use a set of per-ag rbtrees rather than a hash. This version show no performance degradation on my 1.1TB filesystem under parallel create and unlink compared to the existing enlarged hash cache. In both cases _xfs_buf_find() is consuming 5-6% of the entire CPU time of the workload.

This patchset is needed to prepare for moving away from using the page cache as the backing cache and instead maintaining a LRU of cached buffers. This is necessary because on larger filesystems we are completely unable to maintain the working set of metadata buffers hot in cache as we cannot control page cache reclaim. It means that we need to be able to hold a lot more buffers in memory than we currently do and as such the hash based indexing needs replacing first.

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

#1 lore raw

PATCH 1/4 xfs: kill XBF_FS_MANAGED buffers

From: Dave Chinner <[email protected]>

Filesystem level managed buffers are buffers that have their lifecycle controlled by the filesystem layer, not the buffer cache. We currently hash these buffers, which makes cleanup and hash walking somewhat troublesome. Convert the fs managed buffers to unhashed buffers obtained by via xfs_buf_get_noaddr(), and remove the XBF_FS_MANAGED special cases from the buffer cache.

---
 fs/xfs/linux-2.6/xfs_buf.c |   20 +++-------------
 fs/xfs/linux-2.6/xfs_buf.h |    4 ---
 fs/xfs/xfs_mount.c         |   54 +++++++++++++++++++++++++------------------
 3 files changed, 35 insertions(+), 43 deletions(-)
fs/xfs/linux-2.6/xfs_buf.c +4 -16
index 998bfb3..860a23c 100644
@@ -791,8 +791,6 @@ xfs_buf_rele(
 			atomic_inc(&bp->b_hold);
 			spin_unlock(&hash->bh_lock);
 			(*(bp->b_relse)) (bp);
-		} else if (bp->b_flags & XBF_FS_MANAGED) {
-			spin_unlock(&hash->bh_lock);
 		} else {
 			ASSERT(!(bp->b_flags & (XBF_DELWRI|_XBF_DELWRI_Q)));
 			list_del_init(&bp->b_hash_list);
@@ -1401,26 +1399,16 @@ void
 xfs_wait_buftarg(
 	xfs_buftarg_t	*btp)
 {
-	xfs_buf_t	*bp, *n;
 	xfs_bufhash_t	*hash;
 	uint		i;
 
 	for (i = 0; i < (1 << btp->bt_hashshift); i++) {
 		hash = &btp->bt_hash[i];
-again:
 		spin_lock(&hash->bh_lock);
-		list_for_each_entry_safe(bp, n, &hash->bh_list, b_hash_list) {
-			ASSERT(btp == bp->b_target);
-			if (!(bp->b_flags & XBF_FS_MANAGED)) {
-				spin_unlock(&hash->bh_lock);
-				/*
-				 * Catch superblock reference count leaks
-				 * immediately
-				 */
-				BUG_ON(bp->b_bn == 0);
-				delay(100);
-				goto again;
-			}
+		while (!list_empty(&hash->bh_list)) {
+			spin_unlock(&hash->bh_lock);
+			delay(100);
+			spin_lock(&hash->bh_lock);
 		}
 		spin_unlock(&hash->bh_lock);
 	}
fs/xfs/linux-2.6/xfs_buf.h +0 -4
index 2a05614..72215d8 100644
@@ -51,7 +51,6 @@ typedef enum {
 #define XBF_DONE	(1 << 5) /* all pages in the buffer uptodate */
 #define XBF_DELWRI	(1 << 6) /* buffer has dirty pages */
 #define XBF_STALE	(1 << 7) /* buffer has been staled, do not find it */
-#define XBF_FS_MANAGED	(1 << 8) /* filesystem controls freeing memory */
 #define XBF_ORDERED	(1 << 11)/* use ordered writes */
 #define XBF_READ_AHEAD	(1 << 12)/* asynchronous read-ahead */
 #define XBF_LOG_BUFFER	(1 << 13)/* this is a buffer used for the log */
@@ -104,7 +103,6 @@ typedef unsigned int xfs_buf_flags_t;
 	{ XBF_DONE,		"DONE" }, \
 	{ XBF_DELWRI,		"DELWRI" }, \
 	{ XBF_STALE,		"STALE" }, \
-	{ XBF_FS_MANAGED,	"FS_MANAGED" }, \
 	{ XBF_ORDERED,		"ORDERED" }, \
 	{ XBF_READ_AHEAD,	"READ_AHEAD" }, \
 	{ XBF_LOCK,		"LOCK" },  	/* should never be set */\
@@ -276,8 +274,6 @@ extern void xfs_buf_terminate(void);
 					XFS_BUF_DONE(bp);	\
 				} while (0)
 
-#define XFS_BUF_UNMANAGE(bp)	((bp)->b_flags &= ~XBF_FS_MANAGED)
-
 #define XFS_BUF_DELAYWRITE(bp)		((bp)->b_flags |= XBF_DELWRI)
 #define XFS_BUF_UNDELAYWRITE(bp)	xfs_buf_delwri_dequeue(bp)
 #define XFS_BUF_ISDELAYWRITE(bp)	((bp)->b_flags & XBF_DELWRI)
fs/xfs/xfs_mount.c +31 -23

97 lines not on this page · raw message

Signature · 6 lines
1.7.1

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

Re: [PATCH 1/4] xfs: kill XBF_FS_MANAGED buffers

Looks good, but a few comments below:

fs/xfs/xfs_mount.c xfs_readsb(xfs_mount_t *mp, int flags) · line 658

Quoted 3 lines
fs/xfs/xfs_mount.c +2 -0
+	bp = xfs_buf_get_noaddr(sector_size, mp->m_ddev_targp);
+
 	if (!bp || XFS_BUF_ISERROR(bp)) {

xfs_buf_get_noaddr will never return a buffer with an error set.

fs/xfs/xfs_mount.c xfs_readsb(xfs_mount_t *mp, int flags) · line 668

Quoted 7 lines
fs/xfs/xfs_mount.c +6 -1
-	ASSERT(XFS_BUF_VALUSEMA(bp) <= 0);
+
+	/* set up the buffer for a read IO */
+	xfs_buf_lock(bp);
+	XFS_BUF_SET_ADDR(bp, XFS_SB_DADDR);
+        XFS_BUF_READ(bp);
+        XFS_BUF_BUSY(bp);

Various indentation problems.

fs/xfs/xfs_mount.c xfs_readsb(xfs_mount_t *mp, int flags) · line 718

Quoted 5 lines
fs/xfs/xfs_mount.c +3 -0
+	/* grab a reference for caching the buffer */
+        XFS_BUF_HOLD(bp);
 	mp->m_sb_bp = bp;
+
 	xfs_buf_relse(bp);

Grabbing the reference just to drop it three lines later is rather pointless, just remove both.

Quoted 1 line

ASSERT(XFS_BUF_VALUSEMA(bp) > 0);

Given that we took the lock a few lines above this one also feels rather poinless.

fs/xfs/xfs_mount.c xfs_readsb(xfs_mount_t *mp, int flags) · line 725

Quoted 5 lines
fs/xfs/xfs_mount.c +2 -1
+fail:
+	if (bp)
 		xfs_buf_relse(bp);
-	}
 	return error;

I'd rather see this split into a fail_buf_relese label that puts the buffer, and a fail label that just returns the error.

fs/xfs/xfs_mount.c xfs_freesb( · line 2020

Quoted 13 lines
fs/xfs/xfs_mount.c +7 -2
 	 * when we call xfs_buf_relse().
 	 */
 	bp = xfs_getsb(mp, 0);
-	XFS_BUF_UNMANAGE(bp);
-	xfs_buf_relse(bp);
 	mp->m_sb_bp = NULL;
+
+	/*
+	 * need to release the buffer twice to free it because we hold an extra
+	 * reference count on it.
+	 */
+	xfs_buf_relse(bp);
+	xfs_buf_relse(bp);

I'd rather rewrite xfs_freesb to not use xfs_getsb and thus avoid taking the superflous reference:

void
xfs_freesb(

	struct xfs_mount	*mp);

	struct xfs_buf		*bp = mp->m_sb_bp;

	mp->m_sb_bp = NULL;
	if (xfs_buf_cond_lock(bp)
		BUG();
	xfs_buf_relse(bp);
}

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

#3 lore raw

Re: [PATCH 1/4] xfs: kill XBF_FS_MANAGED buffers

Quoted 7 lines · Christoph Hellwig

Looks good, but a few comments below:

fs/xfs/xfs_mount.c xfs_readsb(xfs_mount_t *mp, int flags) · line 658

Quoted 3 lines
fs/xfs/xfs_mount.c +2 -0
+	bp = xfs_buf_get_noaddr(sector_size, mp->m_ddev_targp);
+
 	if (!bp || XFS_BUF_ISERROR(bp)) {

xfs_buf_get_noaddr will never return a buffer with an error set.

OK, will fix.

Quoted 9 lines

fs/xfs/xfs_mount.c xfs_readsb(xfs_mount_t *mp, int flags) · line 668

Quoted 7 lines
fs/xfs/xfs_mount.c +6 -1
-	ASSERT(XFS_BUF_VALUSEMA(bp) <= 0);
+
+	/* set up the buffer for a read IO */
+	xfs_buf_lock(bp);
+	XFS_BUF_SET_ADDR(bp, XFS_SB_DADDR);
+        XFS_BUF_READ(bp);
+        XFS_BUF_BUSY(bp);

Various indentation problems.

I'll fix all these by putting the uncached read function factoring into an initial patch.

Quoted 8 lines

fs/xfs/xfs_mount.c xfs_readsb(xfs_mount_t *mp, int flags) · line 718

Quoted 5 lines
fs/xfs/xfs_mount.c +3 -0
+	/* grab a reference for caching the buffer */
+        XFS_BUF_HOLD(bp);
 	mp->m_sb_bp = bp;
+
 	xfs_buf_relse(bp);

Grabbing the reference just to drop it three lines later is rather pointless, just remove both.

Except that xfs_buf_relse(bp) also unlocks bp. maybe I coul djust make it do an explicit unlock....

Quoted 4 lines
Quoted 1 line

ASSERT(XFS_BUF_VALUSEMA(bp) > 0);

Given that we took the lock a few lines above this one also feels rather poinless.

That's checking the buffer is unlocked, which could be removed if there is an explicit unlock call. I'll do that.

Quoted 29 lines

fs/xfs/xfs_mount.c xfs_readsb(xfs_mount_t *mp, int flags) · line 725

Quoted 6 lines
fs/xfs/xfs_mount.c +2 -1
+fail:
+	if (bp)
 		xfs_buf_relse(bp);
-	}
 	return error;

I'd rather see this split into a fail_buf_relese label that puts the buffer, and a fail label that just returns the error.

fs/xfs/xfs_mount.c xfs_freesb( · line 2020

Quoted 13 lines
fs/xfs/xfs_mount.c +7 -2
 	 * when we call xfs_buf_relse().
 	 */
 	bp = xfs_getsb(mp, 0);
-	XFS_BUF_UNMANAGE(bp);
-	xfs_buf_relse(bp);
 	mp->m_sb_bp = NULL;
+
+	/*
+	 * need to release the buffer twice to free it because we hold an extra
+	 * reference count on it.
+	 */
+	xfs_buf_relse(bp);
+	xfs_buf_relse(bp);

I'd rather rewrite xfs_freesb to not use xfs_getsb and thus avoid taking the superflous reference:

void
xfs_freesb(

Quoted 9 lines
	struct xfs_mount	*mp);

	struct xfs_buf		*bp = mp->m_sb_bp;

	mp->m_sb_bp = NULL;
	if (xfs_buf_cond_lock(bp)
		BUG();
	xfs_buf_relse(bp);
}

Yeah, that's better. I'll do that.

Cheers,

Dave.

Signature · 7 lines
Dave Chinner
[email protected]

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

Re: [PATCH 1/4] xfs: kill XBF_FS_MANAGED buffers

In reply to Dave Chinner
Quoted 8 lines · Dave Chinner

From: Dave Chinner <[email protected]>

Filesystem level managed buffers are buffers that have their lifecycle controlled by the filesystem layer, not the buffer cache. We currently hash these buffers, which makes cleanup and hash walking somewhat troublesome. Convert the fs managed buffers to unhashed buffers obtained by via xfs_buf_get_noaddr(), and remove the XBF_FS_MANAGED special cases from the buffer cache.

I've looked this over and it looks good to me.
I agree with all of Christoph's comments from
the other day. I'll look for your update.

-Alex

Quoted 1 line

. . .

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

#5 lore raw

PATCH 2/4 xfs: use unhashed buffers for size checks

In reply to Dave Chinner

From: Dave Chinner <[email protected]>

When we are checking we can access the last block of each device, we do not need to use hashed buffers as they will be tossed away immediately. Use unhashed buffers for size checks so that all IO prior to full in-memory structure initialisation does not use the buffer cache hashes.

---
 fs/xfs/linux-2.6/xfs_buf.c |   36 ++++++++++++++++++++++++
 fs/xfs/linux-2.6/xfs_buf.h |    4 +++
 fs/xfs/xfs_fsops.c         |   11 +++----
 fs/xfs/xfs_mount.c         |   65 ++++++++++++++-----------------------------
 fs/xfs/xfs_rtalloc.c       |   29 +++++++++-----------
 5 files changed, 79 insertions(+), 66 deletions(-)
fs/xfs/linux-2.6/xfs_buf.c +36 -0
index 860a23c..59df94c 100644
@@ -638,6 +638,42 @@ xfs_buf_readahead(
 	xfs_buf_read(target, ioff, isize, flags);
 }
 
+/*
+ * Read an uncached buffer from disk. Allocates and returns a locked
+ * buffer containing the disk contents or nothing.
+ */
+struct xfs_buf *
+xfs_buf_read_uncached(
+	struct xfs_mount	*mp,
+	struct xfs_buftarg	*target,
+	xfs_daddr_t		daddr,
+	size_t			length)
+{
+	xfs_buf_t	*bp;
+	int		error;
+
+	bp = xfs_buf_get_noaddr(length, target);
+	if (!bp || XFS_BUF_ISERROR(bp))
+		goto fail;
+
+	/* set up the buffer for a read IO */
+	xfs_buf_lock(bp);
+	XFS_BUF_SET_ADDR(bp, daddr);
+	XFS_BUF_READ(bp);
+	XFS_BUF_BUSY(bp);
+
+	xfsbdstrat(mp, bp);
+	error = xfs_iowait(bp);
+	if (error || XFS_BUF_ISERROR(bp))
+		goto fail;
+
+	return bp;
+fail:
+	if (bp)
+		xfs_buf_relse(bp);
+	return NULL;
+}
+
 xfs_buf_t *
 xfs_buf_get_empty(
 	size_t			len,
fs/xfs/linux-2.6/xfs_buf.h +4 -0
index 72215d8..802dc5e 100644
@@ -217,6 +217,10 @@ extern void xfs_buf_hold(xfs_buf_t *);
 extern void xfs_buf_readahead(xfs_buftarg_t *, xfs_off_t, size_t,
 				xfs_buf_flags_t);
 
+struct xfs_buf * xfs_buf_read_uncached(struct xfs_mount *mp,
+				struct xfs_buftarg *target,
+				xfs_daddr_t daddr, size_t length);
+
 /* Releasing Buffers */
 extern void xfs_buf_free(xfs_buf_t *);
 extern void xfs_buf_rele(xfs_buf_t *);
fs/xfs/xfs_fsops.c +5 -6
index 43b1d56..158d5ab 100644
@@ -144,12 +144,11 @@ xfs_growfs_data_private(
 	if ((error = xfs_sb_validate_fsb_count(&mp->m_sb, nb)))
 		return error;
 	dpct = pct - mp->m_sb.sb_imax_pct;
-	error = xfs_read_buf(mp, mp->m_ddev_targp,
-			XFS_FSB_TO_BB(mp, nb) - XFS_FSS_TO_BB(mp, 1),
-			XFS_FSS_TO_BB(mp, 1), 0, &bp);
-	if (error)
-		return error;
-	ASSERT(bp);
+	bp = xfs_buf_read_uncached(mp, mp->m_ddev_targp,
+				XFS_FSB_TO_BB(mp, nb) - XFS_FSS_TO_BB(mp, 1),
+				BBTOB(XFS_FSS_TO_BB(mp, 1)));
+	if (!bp)
+		return EIO;
 	xfs_buf_relse(bp);
 
 	new = nb;	/* use new as a temporary here */
fs/xfs/xfs_mount.c +21 -44

97 lines not on this page · raw message

fs/xfs/xfs_rtalloc.c +13 -16
index 891260f..5c5a4c4 100644
@@ -39,6 +39,7 @@
 #include "xfs_trans_space.h"
 #include "xfs_utils.h"
 #include "xfs_trace.h"
+#include "xfs_buf.h"
 
 
 /*
@@ -1883,13 +1884,13 @@ xfs_growfs_rt(
 	/*
 	 * Read in the last block of the device, make sure it exists.
 	 */
-	error = xfs_read_buf(mp, mp->m_rtdev_targp,
-			XFS_FSB_TO_BB(mp, nrblocks - 1),
-			XFS_FSB_TO_BB(mp, 1), 0, &bp);
-	if (error)
-		return error;
-	ASSERT(bp);
+	bp = xfs_buf_read_uncached(mp, mp->m_rtdev_targp,
+				XFS_FSB_TO_BB(mp, nrblocks - 1),
+				XFS_FSB_TO_B(mp, 1));
+	if (!bp)
+		return EIO;
 	xfs_buf_relse(bp);
+
 	/*
 	 * Calculate new parameters.  These are the final values to be reached.
 	 */
@@ -2215,7 +2216,6 @@ xfs_rtmount_init(
 {
 	xfs_buf_t	*bp;	/* buffer for last block of subvolume */
 	xfs_daddr_t	d;	/* address of last block of subvolume */
-	int		error;	/* error return value */
 	xfs_sb_t	*sbp;	/* filesystem superblock copy in mount */
 
 	sbp = &mp->m_sb;
@@ -2242,15 +2242,12 @@ xfs_rtmount_init(
 			(unsigned long long) mp->m_sb.sb_rblocks);
 		return XFS_ERROR(EFBIG);
 	}
-	error = xfs_read_buf(mp, mp->m_rtdev_targp,
-				d - XFS_FSB_TO_BB(mp, 1),
-				XFS_FSB_TO_BB(mp, 1), 0, &bp);
-	if (error) {
-		cmn_err(CE_WARN,
-	"XFS: realtime mount -- xfs_read_buf failed, returned %d", error);
-		if (error == ENOSPC)
-			return XFS_ERROR(EFBIG);
-		return error;
+	bp = xfs_buf_read_uncached(mp, mp->m_rtdev_targp,
+					d - XFS_FSB_TO_BB(mp, 1),
+					XFS_FSB_TO_B(mp, 1));
+	if (!bp) {
+		cmn_err(CE_WARN, "XFS: realtime device size check failed");
+		return EIO;
 	}
 	xfs_buf_relse(bp);
 	return 0;
Signature · 6 lines
1.7.1

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

Re: [PATCH 2/4] xfs: use unhashed buffers for size checks

fs/xfs/linux-2.6/xfs_buf.c xfs_buf_readahead( · line 653

Quoted 9 lines
fs/xfs/linux-2.6/xfs_buf.c +9 -0
+struct xfs_buf *
+xfs_buf_read_uncached(
+	struct xfs_mount	*mp,
+	struct xfs_buftarg	*target,
+	xfs_daddr_t		daddr,
+	size_t			length)
+{
+	xfs_buf_t	*bp;
+	int		error;

struct xfs_buf and the same indentation as the parameters, please.

fs/xfs/linux-2.6/xfs_buf.c xfs_buf_readahead( · line 655

Quoted 2 lines
fs/xfs/linux-2.6/xfs_buf.c +2 -0
+
+	bp = xfs_buf_get_noaddr(length, target);

I think both the buf_get and buf_read interfaces for the non-hash buffers should have the same name. Either your uncached or maybe better unhashed? (And certainly no noaddr, which is not very useful)

Review

Quoted 2 lines
(quoted diff) +2 -0
+	if (!bp || XFS_BUF_ISERROR(bp))
+		goto fail;

xfs_buf_get_noaddr never returns an error in the buffer.

Quoted 5 lines
fs/xfs/linux-2.6/xfs_buf.c +5 -0
+	/* set up the buffer for a read IO */
+	xfs_buf_lock(bp);
+	XFS_BUF_SET_ADDR(bp, daddr);
+	XFS_BUF_READ(bp);
+	XFS_BUF_BUSY(bp);

fs/xfs/linux-2.6/xfs_buf.c xfs_buf_readahead( · line 673

Quoted 10 lines
fs/xfs/linux-2.6/xfs_buf.c +10 -0
+
+	xfsbdstrat(mp, bp);
+	error = xfs_iowait(bp);
+	if (error || XFS_BUF_ISERROR(bp))
+		goto fail;
+
+	return bp;
+fail:
+	if (bp)
+		xfs_buf_relse(bp);

again, different labels please.

Also this one returns the buffer locked, while buf_get_noaddr doesn't. I suspect we should also change buf_get_noaddr to return a locked buffer to make it consistant with all other buf_read/get interfaces.

fs/xfs/linux-2.6/xfs_buf.h extern void xfs_buf_hold(xfs_buf_t *); · line 222

Quoted 3 lines
fs/xfs/linux-2.6/xfs_buf.h +3 -0
+struct xfs_buf * xfs_buf_read_uncached(struct xfs_mount *mp,
+				struct xfs_buftarg *target,
+				xfs_daddr_t daddr, size_t length);

wrong placement of the *

This patch, or at least the introduction of the new read helper should be moved before patch 1 so that we don't add code that gets removed a little later.

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

#7 lore raw

Re: [PATCH 2/4] xfs: use unhashed buffers for size checks

Quoted 12 lines · Christoph Hellwig

fs/xfs/linux-2.6/xfs_buf.c xfs_buf_readahead( · line 653

Quoted 9 lines
fs/xfs/linux-2.6/xfs_buf.c +9 -0
+struct xfs_buf *
+xfs_buf_read_uncached(
+	struct xfs_mount	*mp,
+	struct xfs_buftarg	*target,
+	xfs_daddr_t		daddr,
+	size_t			length)
+{
+	xfs_buf_t	*bp;
+	int		error;

struct xfs_buf and the same indentation as the parameters, please.

Quoted 6 lines

fs/xfs/linux-2.6/xfs_buf.c xfs_buf_readahead( · line 655

Quoted 2 lines
fs/xfs/linux-2.6/xfs_buf.c +2 -0
+
+	bp = xfs_buf_get_noaddr(length, target);

I think both the buf_get and buf_read interfaces for the non-hash buffers should have the same name. Either your uncached or maybe better unhashed? (And certainly no noaddr, which is not very useful)

I'll rename it *_uncached, because the hash is going away ;)

Quoted 5 lines

Review

Quoted 3 lines
(quoted diff) +2 -0
+	if (!bp || XFS_BUF_ISERROR(bp))
+		goto fail;

xfs_buf_get_noaddr never returns an error in the buffer.

I'll fix all these - they are just CNP from the previous patch.

Quoted 4 lines

Also this one returns the buffer locked, while buf_get_noaddr doesn't. I suspect we should also change buf_get_noaddr to return a locked buffer to make it consistant with all other buf_read/get interfaces.

None of the other callers require locked buffers. I'll leave this for a separate patch set for the moment.

Quoted 10 lines

fs/xfs/linux-2.6/xfs_buf.h extern void xfs_buf_hold(xfs_buf_t *); · line 222

Quoted 3 lines
fs/xfs/linux-2.6/xfs_buf.h +3 -0
+struct xfs_buf * xfs_buf_read_uncached(struct xfs_mount *mp,
+				struct xfs_buftarg *target,
+				xfs_daddr_t daddr, size_t length);

wrong placement of the *

This patch, or at least the introduction of the new read helper should be moved before patch 1 so that we don't add code that gets removed a little later.

Yes, I plan to do that.

Cheers,

Dave.

Signature · 7 lines
Dave Chinner
[email protected]

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

Re: [PATCH 2/4] xfs: use unhashed buffers for size checks

In reply to Dave Chinner
Quoted 7 lines · Dave Chinner

From: Dave Chinner <[email protected]>

When we are checking we can access the last block of each device, we do not need to use hashed buffers as they will be tossed away immediately. Use unhashed buffers for size checks so that all IO prior to full in-memory structure initialisation does not use the buffer cache hashes.

This one also looks good, and again I agree with the comments Christoph made. I'll look for your update. Patch 3 in the series is good too; I'll look at the last patch (the switch to rbtrees) over the weekend.

Quoted 1 line

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

#9 lore raw

PATCH 3/4 xfs: remove buftarg hash for external devices

In reply to Dave Chinner

From: Dave Chinner <[email protected]>

For RT and external log devices, we never use hashed buffers on them now. Remove the buftarg hash tables that are set up for them.

---
 fs/xfs/linux-2.6/xfs_buf.c |    6 +++++-
 1 files changed, 5 insertions(+), 1 deletions(-)
fs/xfs/linux-2.6/xfs_buf.c +5 -1
index 59df94c..b2b5dea 100644
@@ -1462,7 +1462,11 @@ xfs_alloc_bufhash(
 {
 	unsigned int		i;
 
-	btp->bt_hashshift = external ? 3 : 12;	/* 8 or 4096 buckets */
+	if (external) {
+		btp->bt_hash = NULL;
+		return;
+	}
+	btp->bt_hashshift = 12;	/* 4096 buckets */
 	btp->bt_hash = kmem_zalloc_large((1 << btp->bt_hashshift) *
 					 sizeof(xfs_bufhash_t));
 	for (i = 0; i < (1 << btp->bt_hashshift); i++) {
Signature · 6 lines
1.7.1

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs
Reviewed-by on v1 3/4
#10 lore raw

Re: [PATCH 3/4] xfs: remove buftarg hash for external devices

Quoted 6 lines · Dave Chinner

From: Dave Chinner <[email protected]>

For RT and external log devices, we never use hashed buffers on them now. Remove the buftarg hash tables that are set up for them.

Looks good,

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

#11 lore raw

PATCH 4/4 xfs: convert buffer cache hash to rbtree

In reply to Dave Chinner

From: Dave Chinner <[email protected]>

The buffer cache hash is starting to show typical hash scalability problems. large scale testing is showing the number of cached items growing far larger than the hash can efficiently handle. Hence we need to move to a self-scaling cache indexing mechanism.

I have selected rbtrees for indexing becuse they can have O(log n) search scalability, and insert and remove cost is not excessive, even on large trees. Hence we should be able to cache large numbers of buffers without incurring the excessive cache miss search penalties that the hash is imposing on us.

To ensure we still have parallel access to the cache, we need multiple trees. Rather than hashing the buffers by disk address to select a tree, it seems more sensible to separate trees by typical access patterns. Most operations use buffers from within a single AG at a time, so rather than searching lots of different lists, separate the buffer indexes out into per-AG rbtrees. This means that searches during metadata operation have a much higher chance of hitting cache resident nodes, and that updates of the tree are less likely to disturb trees being accessed on other CPUs doing independent operations.

---
 fs/xfs/linux-2.6/xfs_buf.c   |  139 +++++++++++++++++++++--------------------
 fs/xfs/linux-2.6/xfs_buf.h   |   14 ++--
 fs/xfs/linux-2.6/xfs_super.c |    6 +-
 fs/xfs/xfs_ag.h              |    4 +
 fs/xfs/xfs_mount.c           |    4 +-
 5 files changed, 87 insertions(+), 80 deletions(-)
fs/xfs/linux-2.6/xfs_buf.c +70 -67
index b2b5dea..facd37e 100644
@@ -188,7 +188,7 @@ _xfs_buf_initialize(
 	atomic_set(&bp->b_hold, 1);
 	init_completion(&bp->b_iowait);
 	INIT_LIST_HEAD(&bp->b_list);
-	INIT_LIST_HEAD(&bp->b_hash_list);
+	RB_CLEAR_NODE(&bp->b_rbnode);
 	init_MUTEX_LOCKED(&bp->b_sema); /* held, no waiters */
 	XB_SET_OWNER(bp);
 	bp->b_target = target;
@@ -422,8 +422,10 @@ _xfs_buf_find(
 {
 	xfs_off_t		range_base;
 	size_t			range_length;
-	xfs_bufhash_t		*hash;
-	xfs_buf_t		*bp, *n;
+	struct xfs_perag	*pag;
+	struct rb_node		**rbp;
+	struct rb_node		*parent;
+	xfs_buf_t		*bp;
 
 	range_base = (ioff << BBSHIFT);
 	range_length = (isize << BBSHIFT);
@@ -432,14 +434,36 @@ _xfs_buf_find(
 	ASSERT(!(range_length < (1 << btp->bt_sshift)));
 	ASSERT(!(range_base & (xfs_off_t)btp->bt_smask));
 
-	hash = &btp->bt_hash[hash_long((unsigned long)ioff, btp->bt_hashshift)];
-
-	spin_lock(&hash->bh_lock);
-
-	list_for_each_entry_safe(bp, n, &hash->bh_list, b_hash_list) {
-		ASSERT(btp == bp->b_target);
-		if (bp->b_file_offset == range_base &&
-		    bp->b_buffer_length == range_length) {
+	/* get tree root */
+	pag = xfs_perag_get(btp->bt_mp, xfs_daddr_to_agno(btp->bt_mp, ioff));
+
+	/* walk tree */
+	spin_lock(&pag->pagbuf_lock);
+	rbp = &pag->pagbuf_tree.rb_node;
+	parent = NULL;
+	bp = NULL;
+	while (*rbp) {
+		parent = *rbp;
+		bp = rb_entry(parent, struct xfs_buf, b_rbnode);
+
+		if (bp->b_file_offset < range_base)
+			rbp = &(*rbp)->rb_left;
+		else if (bp->b_file_offset > range_base)
+			rbp = &(*rbp)->rb_right;
+		else {
+			/*
+			 * found a block offset match. If the range doesn't
+			 * match, the only way this is allowed is if the buffer
+			 * in the cache is stale and the transaction that made
+			 * it stale has not yet committed. i.e. we are
+			 * reallocating a busy extent. Skip this buffer and
+			 * continue searching to the right for an exact match.
+			 */
+			if (bp->b_buffer_length != range_length) {
+				ASSERT(bp->b_flags & XBF_STALE);
+				rbp = &(*rbp)->rb_right;
+				continue;
+			}
 			atomic_inc(&bp->b_hold);
 			goto found;
 		}
@@ -449,17 +473,20 @@ _xfs_buf_find(
 	if (new_bp) {
 		_xfs_buf_initialize(new_bp, btp, range_base,
 				range_length, flags);
-		new_bp->b_hash = hash;
-		list_add(&new_bp->b_hash_list, &hash->bh_list);
+		new_bp->b_pag = pag;
+		rb_link_node(&new_bp->b_rbnode, parent, rbp);
+		rb_insert_color(&new_bp->b_rbnode, &pag->pagbuf_tree);
+		spin_unlock(&pag->pagbuf_lock);
 	} else {
 		XFS_STATS_INC(xb_miss_locked);
+		spin_unlock(&pag->pagbuf_lock);
+		xfs_perag_put(pag);
 	}
-
-	spin_unlock(&hash->bh_lock);
 	return new_bp;
 
 found:
-	spin_unlock(&hash->bh_lock);
+	spin_unlock(&pag->pagbuf_lock);
+	xfs_perag_put(pag);
 
 	/* Attempt to get the semaphore without sleeping,
 	 * if this does not work then we need to drop the
@@ -810,27 +837,30 @@ void
 xfs_buf_rele(
 	xfs_buf_t		*bp)
 {
-	xfs_bufhash_t		*hash = bp->b_hash;
+	struct xfs_perag	*pag = bp->b_pag;
 
 	trace_xfs_buf_rele(bp, _RET_IP_);
 
-	if (unlikely(!hash)) {
+	if (!pag) {
 		ASSERT(!bp->b_relse);
+		ASSERT(RB_EMPTY_NODE(&bp->b_rbnode));
 		if (atomic_dec_and_test(&bp->b_hold))
 			xfs_buf_free(bp);
 		return;
 	}
 
+	ASSERT(!RB_EMPTY_NODE(&bp->b_rbnode));
 	ASSERT(atomic_read(&bp->b_hold) > 0);
-	if (atomic_dec_and_lock(&bp->b_hold, &hash->bh_lock)) {
+	if (atomic_dec_and_lock(&bp->b_hold, &pag->pagbuf_lock)) {
 		if (bp->b_relse) {
 			atomic_inc(&bp->b_hold);
-			spin_unlock(&hash->bh_lock);
+			spin_unlock(&pag->pagbuf_lock);
 			(*(bp->b_relse)) (bp);
 		} else {
 			ASSERT(!(bp->b_flags & (XBF_DELWRI|_XBF_DELWRI_Q)));
-			list_del_init(&bp->b_hash_list);
-			spin_unlock(&hash->bh_lock);
+			rb_erase(&bp->b_rbnode, &pag->pagbuf_tree);
+			spin_unlock(&pag->pagbuf_lock);
+			xfs_perag_put(pag);
 			xfs_buf_free(bp);
 		}
 	}
@@ -1433,57 +1463,25 @@ xfs_buf_iomove(
  */
 void
 xfs_wait_buftarg(
-	xfs_buftarg_t	*btp)
+	struct xfs_buftarg	*btp)
 {
-	xfs_bufhash_t	*hash;
-	uint		i;
+	struct xfs_perag	*pag;
+	uint			i;
 
-	for (i = 0; i < (1 << btp->bt_hashshift); i++) {
-		hash = &btp->bt_hash[i];
-		spin_lock(&hash->bh_lock);
-		while (!list_empty(&hash->bh_list)) {
-			spin_unlock(&hash->bh_lock);
+	for (i = 0; i < btp->bt_mp->m_sb.sb_agcount; i++) {
+		pag = xfs_perag_get(btp->bt_mp, i);
+		spin_lock(&pag->pagbuf_lock);
+		while (rb_first(&pag->pagbuf_tree)) {
+			spin_unlock(&pag->pagbuf_lock);
 			delay(100);
-			spin_lock(&hash->bh_lock);
+			spin_lock(&pag->pagbuf_lock);
 		}
-		spin_unlock(&hash->bh_lock);
+		spin_unlock(&pag->pagbuf_lock);
+		xfs_perag_put(pag);
 	}
 }
 
 /*
- *	Allocate buffer hash table for a given target.
- *	For devices containing metadata (i.e. not the log/realtime devices)
- *	we need to allocate a much larger hash table.
- */
-STATIC void
-xfs_alloc_bufhash(
-	xfs_buftarg_t		*btp,
-	int			external)
-{
-	unsigned int		i;
-
-	if (external) {
-		btp->bt_hash = NULL;
-		return;
-	}
-	btp->bt_hashshift = 12;	/* 4096 buckets */
-	btp->bt_hash = kmem_zalloc_large((1 << btp->bt_hashshift) *
-					 sizeof(xfs_bufhash_t));
-	for (i = 0; i < (1 << btp->bt_hashshift); i++) {
-		spin_lock_init(&btp->bt_hash[i].bh_lock);
-		INIT_LIST_HEAD(&btp->bt_hash[i].bh_list);
-	}
-}
-
-STATIC void
-xfs_free_bufhash(
-	xfs_buftarg_t		*btp)
-{
-	kmem_free_large(btp->bt_hash);
-	btp->bt_hash = NULL;
-}
-
-/*
  *	buftarg list for delwrite queue processing
  */
 static LIST_HEAD(xfs_buftarg_list);
@@ -1515,7 +1513,6 @@ xfs_free_buftarg(
 	xfs_flush_buftarg(btp, 1);
 	if (mp->m_flags & XFS_MOUNT_BARRIER)
 		xfs_blkdev_issue_flush(btp);
-	xfs_free_bufhash(btp);
 	iput(btp->bt_mapping->host);
 
 	/* Unregister the buftarg first so that we don't get a
@@ -1637,6 +1634,7 @@ out_error:
 
 xfs_buftarg_t *
 xfs_alloc_buftarg(
+	struct xfs_mount	*mp,
 	struct block_device	*bdev,
 	int			external,
 	const char		*fsname)
@@ -1645,6 +1643,12 @@ xfs_alloc_buftarg(
 
 	btp = kmem_zalloc(sizeof(*btp), KM_SLEEP);
 
+	/*
+	 * The buftarg cache should never be used by external devices.
+	 * Ensure we catch any users with extreme prejudice.
+	 */
+	btp->bt_mp = external ? NULL : mp;
+
 	btp->bt_dev =  bdev->bd_dev;
 	btp->bt_bdev = bdev;
 	if (xfs_setsize_buftarg_early(btp, bdev))
@@ -1653,7 +1657,6 @@ xfs_alloc_buftarg(
 		goto error;
 	if (xfs_alloc_delwrite_queue(btp, fsname))
 		goto error;
-	xfs_alloc_bufhash(btp, external);
 	return btp;
 
 error:
fs/xfs/linux-2.6/xfs_buf.h +7 -7
index 802dc5e..3797ee8 100644
@@ -126,18 +126,17 @@ typedef struct xfs_bufhash {
 	spinlock_t		bh_lock;
 } xfs_bufhash_t;
 
+struct xfs_mount;
+
 typedef struct xfs_buftarg {
 	dev_t			bt_dev;
 	struct block_device	*bt_bdev;
 	struct address_space	*bt_mapping;
+	struct xfs_mount	*bt_mp;
 	unsigned int		bt_bsize;
 	unsigned int		bt_sshift;
 	size_t			bt_smask;
 
-	/* per device buffer hash table */
-	uint			bt_hashshift;
-	xfs_bufhash_t		*bt_hash;
-
 	/* per device delwri queue */
 	struct task_struct	*bt_task;
 	struct list_head	bt_list;
@@ -171,8 +170,8 @@ typedef struct xfs_buf {
 	wait_queue_head_t	b_waiters;	/* unpin waiters */
 	struct list_head	b_list;
 	xfs_buf_flags_t		b_flags;	/* status flags */
-	struct list_head	b_hash_list;	/* hash table list */
-	xfs_bufhash_t		*b_hash;	/* hash table list start */
+	struct rb_node		b_rbnode;	/* rbtree node */
+	struct xfs_perag	*b_pag;		/* rbtree root */
 	xfs_buftarg_t		*b_target;	/* buffer target (device) */
 	atomic_t		b_hold;		/* reference count */
 	xfs_daddr_t		b_bn;		/* block number for I/O */
@@ -374,7 +373,8 @@ static inline void xfs_buf_relse(xfs_buf_t *bp)
 /*
  *	Handling of buftargs.
  */
-extern xfs_buftarg_t *xfs_alloc_buftarg(struct block_device *, int, const char *);
+extern xfs_buftarg_t *xfs_alloc_buftarg(struct xfs_mount *,
+				struct block_device *, int, const char *);
 extern void xfs_free_buftarg(struct xfs_mount *, struct xfs_buftarg *);
 extern void xfs_wait_buftarg(xfs_buftarg_t *);
 extern int xfs_setsize_buftarg(xfs_buftarg_t *, unsigned int, unsigned int);
fs/xfs/linux-2.6/xfs_super.c +3 -3
index a4e0797..7426319 100644
@@ -758,18 +758,18 @@ xfs_open_devices(
 	 * Setup xfs_mount buffer target pointers
 	 */
 	error = ENOMEM;
-	mp->m_ddev_targp = xfs_alloc_buftarg(ddev, 0, mp->m_fsname);
+	mp->m_ddev_targp = xfs_alloc_buftarg(mp, ddev, 0, mp->m_fsname);
 	if (!mp->m_ddev_targp)
 		goto out_close_rtdev;
 
 	if (rtdev) {
-		mp->m_rtdev_targp = xfs_alloc_buftarg(rtdev, 1, mp->m_fsname);
+		mp->m_rtdev_targp = xfs_alloc_buftarg(mp, rtdev, 1, mp->m_fsname);
 		if (!mp->m_rtdev_targp)
 			goto out_free_ddev_targ;
 	}
 
 	if (logdev && logdev != ddev) {
-		mp->m_logdev_targp = xfs_alloc_buftarg(logdev, 1, mp->m_fsname);
+		mp->m_logdev_targp = xfs_alloc_buftarg(mp, logdev, 1, mp->m_fsname);
 		if (!mp->m_logdev_targp)
 			goto out_free_rtdev_targ;
 	} else {
fs/xfs/xfs_ag.h +4 -0
index 4917d4e..e01d4cf 100644
@@ -230,6 +230,10 @@ typedef struct xfs_perag {
 	rwlock_t	pag_ici_lock;	/* incore inode lock */
 	struct radix_tree_root pag_ici_root;	/* incore inode cache root */
 	int		pag_ici_reclaimable;	/* reclaimable inodes */
+
+	/* buffer cache index */
+	spinlock_t	pagbuf_lock;	/* lock for pagbuf_tree */
+	struct rb_root	pagbuf_tree;	/* ordered tree of active buffers */
 #endif
 	int		pagb_count;	/* pagb slots in use */
 } xfs_perag_t;
fs/xfs/xfs_mount.c +2 -2
index 2c8dd69..5d9f49c 100644
@@ -210,8 +210,6 @@ xfs_perag_get(struct xfs_mount *mp, xfs_agnumber_t agno)
 	pag = radix_tree_lookup(&mp->m_perag_tree, agno);
 	if (pag) {
 		ASSERT(atomic_read(&pag->pag_ref) >= 0);
-		/* catch leaks in the positive direction during testing */
-		ASSERT(atomic_read(&pag->pag_ref) < 1000);
 		ref = atomic_inc_return(&pag->pag_ref);
 	}
 	spin_unlock(&mp->m_perag_lock);
@@ -445,6 +443,8 @@ xfs_initialize_perag(
 		pag->pag_mount = mp;
 		rwlock_init(&pag->pag_ici_lock);
 		INIT_RADIX_TREE(&pag->pag_ici_root, GFP_ATOMIC);
+		spin_lock_init(&pag->pagbuf_lock);
+		pag->pagbuf_tree = RB_ROOT;
 
 		if (radix_tree_preload(GFP_NOFS))
 			goto out_unwind;
Signature · 6 lines
1.7.1

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

Re: [PATCH 4/4] xfs: convert buffer cache hash to rbtree

Quoted 5 lines · Dave Chinner

I have selected rbtrees for indexing becuse they can have O(log n) search scalability, and insert and remove cost is not excessive, even on large trees. Hence we should be able to cache large numbers of buffers without incurring the excessive cache miss search penalties that the hash is imposing on us.

Once thing that worries me about the rbtrees is that the Linux implementation doesn't allow for lockless readers. But in the end the buffer cache implementation is very well encapsulated, so if the need arises we could easily change the underlying data structure.

fs/xfs/linux-2.6/xfs_buf.c xfs_alloc_buftarg( · line 1650

Quoted 5 lines
fs/xfs/linux-2.6/xfs_buf.c +5 -0
+	/*
+	 * The buftarg cache should never be used by external devices.
+	 * Ensure we catch any users with extreme prejudice.
+	 */
+	btp->bt_mp = external ? NULL : mp;

I'd much prefer to always initialize this field. We currently have a b_mount field struct xfs_buf which is used only in a few places and initialized rather, ehmm, lazily. If we could replace it with ->b_target->bt_mount we can shrink struct buf and make the information available much more consistently. Just adding the mount argument to the buftarg and removing it from the buf would be a nice little preparatory patch.

And yes, I think bt_mount would be much nicer name than bt_mp.

fs/xfs/xfs_mount.c xfs_perag_get(struct xfs_mount *mp, xfs_agnumber_t agno) · line 214

Quoted 6 lines
fs/xfs/xfs_mount.c +0 -2
@@ -210,8 +210,6 @@ xfs_perag_get(struct xfs_mount *mp, xfs_agnumber_t agno)
 	pag = radix_tree_lookup(&mp->m_perag_tree, agno);
 	if (pag) {
 		ASSERT(atomic_read(&pag->pag_ref) >= 0);
-		/* catch leaks in the positive direction during testing */
-		ASSERT(atomic_read(&pag->pag_ref) < 1000);

Di you manage to hit this during testing? Either way it should probably be a separate patch.

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

#13 lore raw

Re: [PATCH 4/4] xfs: convert buffer cache hash to rbtree

Quoted 11 lines · Christoph Hellwig
Quoted 5 lines · Dave Chinner

I have selected rbtrees for indexing becuse they can have O(log n) search scalability, and insert and remove cost is not excessive, even on large trees. Hence we should be able to cache large numbers of buffers without incurring the excessive cache miss search penalties that the hash is imposing on us.

Once thing that worries me about the rbtrees is that the Linux implementation doesn't allow for lockless readers. But in the end the buffer cache implementation is very well encapsulated, so if the need arises we could easily change the underlying data structure.

Agreed. I'm going for simplicity of implementation first - list to rbtree conversion is pretty trivial and realtively easy to verify. We can revisit the choice of rbtrees later on if/when we need to.

Quoted 6 lines

fs/xfs/linux-2.6/xfs_buf.c xfs_alloc_buftarg( · line 1650

Quoted 5 lines
fs/xfs/linux-2.6/xfs_buf.c +5 -0
+	/*
+	 * The buftarg cache should never be used by external devices.
+	 * Ensure we catch any users with extreme prejudice.
+	 */
+	btp->bt_mp = external ? NULL : mp;
Quoted 7 lines

I'd much prefer to always initialize this field. We currently have a b_mount field struct xfs_buf which is used only in a few places and initialized rather, ehmm, lazily. If we could replace it with ->b_target->bt_mount we can shrink struct buf and make the information available much more consistently. Just adding the mount argument to the buftarg and removing it from the buf would be a nice little preparatory patch.

Good idea. I'll run up a patch to do that - if we've got more buffers around, giving them a diet makes sense.

Quoted 1 line

And yes, I think bt_mount would be much nicer name than bt_mp.

Agreed. call me lazy ;)

Quoted 9 lines

fs/xfs/xfs_mount.c xfs_perag_get(struct xfs_mount *mp, xfs_agnumber_t agno) · line 214

Quoted 6 lines
fs/xfs/xfs_mount.c +0 -2
@@ -210,8 +210,6 @@ xfs_perag_get(struct xfs_mount *mp, xfs_agnumber_t agno)
 	pag = radix_tree_lookup(&mp->m_perag_tree, agno);
 	if (pag) {
 		ASSERT(atomic_read(&pag->pag_ref) >= 0);
-		/* catch leaks in the positive direction during testing */
-		ASSERT(atomic_read(&pag->pag_ref) < 1000);

Di you manage to hit this during testing? Either way it should probably be a separate patch.

Not with xfstests. Takes about 0.5s for fsmark to hit it, though. ;) I'll put it in a separate patch, too.

Cheers,

Dave.

Signature · 7 lines
Dave Chinner
[email protected]

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

Re: [PATCH 4/4] xfs: convert buffer cache hash to rbtree

In reply to Christoph Hellwig
Quoted 10 lines

fs/xfs/xfs_mount.c xfs_perag_get(struct xfs_mount *mp, xfs_agnumber_t agno) · line 214

Quoted 7 lines
fs/xfs/xfs_mount.c +0 -2
@@ -210,8 +210,6 @@ xfs_perag_get(struct xfs_mount *mp, xfs_agnumber_t agno)
 	pag = radix_tree_lookup(&mp->m_perag_tree, agno);
 	if (pag) {
 		ASSERT(atomic_read(&pag->pag_ref) >= 0);
-		/* catch leaks in the positive direction during testing */
-		ASSERT(atomic_read(&pag->pag_ref) < 1000);

Di you manage to hit this during testing? Either way it should probably be a separate patch.

I'm pretty sure this is due to each buffer now holding a perag reference. It might be nice to preserve this functionality by checking against the number of blocks in the AG or something similar. But it's debug so it's not quite as critical.

-Alex

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

#15 lore raw

Re: [PATCH 4/4] xfs: convert buffer cache hash to rbtree

In reply to Dave Chinner
Quoted 13 lines · Dave Chinner

From: Dave Chinner <[email protected]>

The buffer cache hash is starting to show typical hash scalability problems. large scale testing is showing the number of cached items growing far larger than the hash can efficiently handle. Hence we need to move to a self-scaling cache indexing mechanism.

I have selected rbtrees for indexing becuse they can have O(log n) search scalability, and insert and remove cost is not excessive, even on large trees. Hence we should be able to cache large numbers of buffers without incurring the excessive cache miss search penalties that the hash is imposing on us.

Quoted 10 lines

To ensure we still have parallel access to the cache, we need multiple trees. Rather than hashing the buffers by disk address to select a tree, it seems more sensible to separate trees by typical access patterns. Most operations use buffers from within a single AG at a time, so rather than searching lots of different lists, separate the buffer indexes out into per-AG rbtrees. This means that searches during metadata operation have a much higher chance of hitting cache resident nodes, and that updates of the tree are less likely to disturb trees being accessed on other CPUs doing independent operations.

I found a bug in this, and have a bunch of other less important comments for you to consider. I haven't spent any time contemplating your decision to use RB trees on AG's but it seems quite reasonable.

fs/xfs/linux-2.6/xfs_buf.c

Quoted 13 lines
---
 fs/xfs/linux-2.6/xfs_buf.c   |  139 +++++++++++++++++++++--------------------
 fs/xfs/linux-2.6/xfs_buf.h   |   14 ++--
 fs/xfs/linux-2.6/xfs_super.c |    6 +-
 fs/xfs/xfs_ag.h              |    4 +
 fs/xfs/xfs_mount.c           |    4 +-
 5 files changed, 87 insertions(+), 80 deletions(-)
fs/xfs/linux-2.6/xfs_buf.c +0 -0
index b2b5dea..facd37e 100644

. . .

Quoted 9 lines
fs/xfs/linux-2.6/xfs_buf.c +0 -5
@@ -432,14 +434,36 @@ _xfs_buf_find(
 	ASSERT(!(range_length < (1 << btp->bt_sshift)));
 	ASSERT(!(range_base & (xfs_off_t)btp->bt_smask));
 
-	hash = &btp->bt_hash[hash_long((unsigned long)ioff, btp->bt_hashshift)];
-
-	spin_lock(&hash->bh_lock);
-
-	list_for_each_entry_safe(bp, n, &hash->bh_list, b_hash_list) {

fs/xfs/linux-2.6/xfs_buf.c _xfs_buf_find( · line 443

Quoted 10 lines
fs/xfs/linux-2.6/xfs_buf.c +7 -3
-		ASSERT(btp == bp->b_target);
-		if (bp->b_file_offset == range_base &&
-		    bp->b_buffer_length == range_length) {
+	/* get tree root */
+	pag = xfs_perag_get(btp->bt_mp, xfs_daddr_to_agno(btp->bt_mp, ioff));
+
+	/* walk tree */
+	spin_lock(&pag->pagbuf_lock);
+	rbp = &pag->pagbuf_tree.rb_node;
+	parent = NULL;

Could drop the above assignment and change the while statement to read: while ((parent = *rbp)) { (I know that leads to a mildly controversial style.)

fs/xfs/linux-2.6/xfs_buf.c _xfs_buf_find( · line 447

Quoted 4 lines
fs/xfs/linux-2.6/xfs_buf.c +4 -0
+	bp = NULL;
+	while (*rbp) {
+		parent = *rbp;
+		bp = rb_entry(parent, struct xfs_buf, b_rbnode);

Below here you might as well make use of the value of "parent" in places where (*rbp) is used. I realize you're just mimicking what's in the rbtree.h file though... If the result seems to read funny, maybe you could rename "parent" to be "entry" or something.

Here's the BUG:

fs/xfs/linux-2.6/xfs_buf.c _xfs_buf_find( · line 452

Quoted 4 lines
fs/xfs/linux-2.6/xfs_buf.c +4 -0
+		if (bp->b_file_offset < range_base)
+			rbp = &(*rbp)->rb_left;
+		else if (bp->b_file_offset > range_base)
+			rbp = &(*rbp)->rb_right;

Your comparisons here are reversed. In other words, I believe it should be:

	if (range_base < bp->b_file_offset)	
		rbp = &parent->rb_left;
	else if (range_base > bp->b_file_offset)
		rbp = &parent->rb_right;

Maybe it mostly works in the order you have it, but I'm pretty sure it's wrong. (The "continue searching to the right" below would be wrong though.)

fs/xfs/linux-2.6/xfs_buf.c _xfs_buf_find( · line 463

Quoted 11 lines
fs/xfs/linux-2.6/xfs_buf.c +11 -0
+		else {
+			/*
+			 * found a block offset match. If the range doesn't
+			 * match, the only way this is allowed is if the buffer
+			 * in the cache is stale and the transaction that made
+			 * it stale has not yet committed. i.e. we are
+			 * reallocating a busy extent. Skip this buffer and
+			 * continue searching to the right for an exact match.
+			 */
+			if (bp->b_buffer_length != range_length) {
+				ASSERT(bp->b_flags & XBF_STALE);

This assertion is new. I trust it's correct, but maybe it should go in separately (first).

fs/xfs/linux-2.6/xfs_buf.c _xfs_buf_find( · line 469

Quoted 6 lines
fs/xfs/linux-2.6/xfs_buf.c +3 -0
+				rbp = &(*rbp)->rb_right;
+				continue;
+			}
 			atomic_inc(&bp->b_hold);
 			goto found;
 		}

When I first read the next hunk I thought you were mistakenly not dropping the perag reference. Later I realized it was intentional--that the buffer holds a reference on the perag until it (the buffer) is released. This is a minor point but I think it would be helpful to see a comment explaining that.

Quoted 27 lines
fs/xfs/linux-2.6/xfs_buf.c +8 -5
@@ -449,17 +473,20 @@ _xfs_buf_find(
 	if (new_bp) {
 		_xfs_buf_initialize(new_bp, btp, range_base,
 				range_length, flags);
-		new_bp->b_hash = hash;
-		list_add(&new_bp->b_hash_list, &hash->bh_list);
+		new_bp->b_pag = pag;
+		rb_link_node(&new_bp->b_rbnode, parent, rbp);
+		rb_insert_color(&new_bp->b_rbnode, &pag->pagbuf_tree);
+		spin_unlock(&pag->pagbuf_lock);
 	} else {
 		XFS_STATS_INC(xb_miss_locked);
+		spin_unlock(&pag->pagbuf_lock);
+		xfs_perag_put(pag);
 	}
-
-	spin_unlock(&hash->bh_lock);
 	return new_bp;
 
 found:
-	spin_unlock(&hash->bh_lock);
+	spin_unlock(&pag->pagbuf_lock);
+	xfs_perag_put(pag);
 
 	/* Attempt to get the semaphore without sleeping,
 	 * if this does not work then we need to drop the

fs/xfs/linux-2.6/xfs_buf.c void · line 844

Quoted 10 lines
fs/xfs/linux-2.6/xfs_buf.c +2 -2
@@ -810,27 +837,30 @@ void
 xfs_buf_rele(
 	xfs_buf_t		*bp)
 {
-	xfs_bufhash_t		*hash = bp->b_hash;
+	struct xfs_perag	*pag = bp->b_pag;
 
 	trace_xfs_buf_rele(bp, _RET_IP_);
 
-	if (unlikely(!hash)) {
+	if (!pag) {

I know this is not related to your change, but I'm curious whether this can even happen, and if so, when?

Quoted 6 lines
fs/xfs/linux-2.6/xfs_buf.c +1 -0
 		ASSERT(!bp->b_relse);
+		ASSERT(RB_EMPTY_NODE(&bp->b_rbnode));
 		if (atomic_dec_and_test(&bp->b_hold))
 			xfs_buf_free(bp);
 		return;
 	}

fs/xfs/linux-2.6/xfs_buf.c void · line 858

Quoted 10 lines
fs/xfs/linux-2.6/xfs_buf.c +3 -2
 
+	ASSERT(!RB_EMPTY_NODE(&bp->b_rbnode));
 	ASSERT(atomic_read(&bp->b_hold) > 0);
-	if (atomic_dec_and_lock(&bp->b_hold, &hash->bh_lock)) {
+	if (atomic_dec_and_lock(&bp->b_hold, &pag->pagbuf_lock)) {
 		if (bp->b_relse) {
 			atomic_inc(&bp->b_hold);
-			spin_unlock(&hash->bh_lock);
+			spin_unlock(&pag->pagbuf_lock);
 			(*(bp->b_relse)) (bp);

Drop the excess parentheses here (above) while you're at it.

Quoted 31 lines
fs/xfs/linux-2.6/xfs_buf.c +10 -10
 		} else {
 			ASSERT(!(bp->b_flags & (XBF_DELWRI|_XBF_DELWRI_Q)));
-			list_del_init(&bp->b_hash_list);
-			spin_unlock(&hash->bh_lock);
+			rb_erase(&bp->b_rbnode, &pag->pagbuf_tree);
+			spin_unlock(&pag->pagbuf_lock);
+			xfs_perag_put(pag);
 			xfs_buf_free(bp);
 		}
 	}
@@ -1433,57 +1463,25 @@ xfs_buf_iomove(
  */
 void
 xfs_wait_buftarg(
-	xfs_buftarg_t	*btp)
+	struct xfs_buftarg	*btp)
 {
-	xfs_bufhash_t	*hash;
-	uint		i;
+	struct xfs_perag	*pag;
+	uint			i;
 
-	for (i = 0; i < (1 << btp->bt_hashshift); i++) {
-		hash = &btp->bt_hash[i];
-		spin_lock(&hash->bh_lock);
-		while (!list_empty(&hash->bh_list)) {
-			spin_unlock(&hash->bh_lock);
+	for (i = 0; i < btp->bt_mp->m_sb.sb_agcount; i++) {
+		pag = xfs_perag_get(btp->bt_mp, i);
+		spin_lock(&pag->pagbuf_lock);
+		while (rb_first(&pag->pagbuf_tree)) {

fs/xfs/linux-2.6/xfs_buf.c xfs_buf_iomove( · line 1482

Quoted 10 lines
fs/xfs/linux-2.6/xfs_buf.c +4 -2
+			spin_unlock(&pag->pagbuf_lock);
 			delay(100);
-			spin_lock(&hash->bh_lock);
+			spin_lock(&pag->pagbuf_lock);
 		}
-		spin_unlock(&hash->bh_lock);
+		spin_unlock(&pag->pagbuf_lock);
+		xfs_perag_put(pag);
 	}
 }

This suggestion is again not related to your change, but... Would this basic structure (not tested) be better than the above?

	int more;

	do {
		more = 0;
		for (i = 0; i < btp->bt_mp->m_sb.sb_agcount; i++) {
			pag = xfs_perag_get(btp->bt_mp, i);
			spin_lock(&pag->pagbuf_lock);
			if (rb_first(&pag->pagbuf_tree))
				more++;
			spin_unlock(&pag->pagbuf_lock);
			xfs_perag_put(pag);
		}
		if (more)
			delay(100);
	} while (more);

fs/xfs/linux-2.6/xfs_buf.c xfs_buf_iomove( · line 1456

Quoted 5 lines
fs/xfs/linux-2.6/xfs_buf.c +0 -3
 /*
- *	Allocate buffer hash table for a given target.
- *	For devices containing metadata (i.e. not the log/realtime devices)
- *	we need to allocate a much larger hash table.

. . .

fs/xfs/linux-2.6/xfs_buf.c xfs_alloc_buftarg( · line 1647

Quoted 6 lines
fs/xfs/linux-2.6/xfs_buf.c +2 -0
@@ -1645,6 +1643,12 @@ xfs_alloc_buftarg(
 
 	btp = kmem_zalloc(sizeof(*btp), KM_SLEEP);
 
+	/*
+	 * The buftarg cache should never be used by external devices.

I suggest that "buftarg cache" is not a good name for the (now per-AG) buffer cache.

fs/xfs/linux-2.6/xfs_buf.h

Quoted 19 lines
fs/xfs/linux-2.6/xfs_buf.c +4 -1
+	 * Ensure we catch any users with extreme prejudice.
+	 */
+	btp->bt_mp = external ? NULL : mp;
+
 	btp->bt_dev =  bdev->bd_dev;
 	btp->bt_bdev = bdev;
 	if (xfs_setsize_buftarg_early(btp, bdev))
@@ -1653,7 +1657,6 @@ xfs_alloc_buftarg(
 		goto error;
 	if (xfs_alloc_delwrite_queue(btp, fsname))
 		goto error;
-	xfs_alloc_bufhash(btp, external);
 	return btp;
 
 error:
fs/xfs/linux-2.6/xfs_buf.h +0 -0
index 802dc5e..3797ee8 100644

. . .

fs/xfs/linux-2.6/xfs_buf.h typedef struct xfs_buf { · line 174

Quoted 8 lines
fs/xfs/linux-2.6/xfs_buf.h +2 -2
@@ -171,8 +170,8 @@ typedef struct xfs_buf {
 	wait_queue_head_t	b_waiters;	/* unpin waiters */
 	struct list_head	b_list;
 	xfs_buf_flags_t		b_flags;	/* status flags */
-	struct list_head	b_hash_list;	/* hash table list */
-	xfs_bufhash_t		*b_hash;	/* hash table list start */
+	struct rb_node		b_rbnode;	/* rbtree node */
+	struct xfs_perag	*b_pag;		/* rbtree root */

Rather, "contains rbtree root" (in the comment).

fs/xfs/linux-2.6/xfs_buf.h typedef struct xfs_buf { · line 177

Quoted 3 lines
fs/xfs/linux-2.6/xfs_buf.h +0 -0
 	xfs_buftarg_t		*b_target;	/* buffer target (device) */
 	atomic_t		b_hold;		/* reference count */
 	xfs_daddr_t		b_bn;		/* block number for I/O */

. . .

fs/xfs/xfs_ag.h typedef struct xfs_perag { · line 236

Quoted 12 lines
fs/xfs/xfs_ag.h +4 -0
index 4917d4e..e01d4cf 100644
@@ -230,6 +230,10 @@ typedef struct xfs_perag {
 	rwlock_t	pag_ici_lock;	/* incore inode lock */
 	struct radix_tree_root pag_ici_root;	/* incore inode cache root */
 	int		pag_ici_reclaimable;	/* reclaimable inodes */
+
+	/* buffer cache index */
+	spinlock_t	pagbuf_lock;	/* lock for pagbuf_tree */
+	struct rb_root	pagbuf_tree;	/* ordered tree of active buffers */

I know it's in some way consistent with the rest of the naming scheme for fields in this structure, maybe these could be named pag_buf_lock and pag_buf_tree. (The rest of the fields here have a sort of strange convention and maybe they've got strong enough history that they should be left alone.)

fs/xfs/xfs_ag.h typedef struct xfs_perag { · line 239

Quoted 3 lines
fs/xfs/xfs_ag.h +0 -0
 #endif
 	int		pagb_count;	/* pagb slots in use */
 } xfs_perag_t;

. . .

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

#16 lore raw

Re: [PATCH 4/4] xfs: convert buffer cache hash to rbtree

Quoted 61 lines · Alex Elder
Quoted 13 lines · Dave Chinner

From: Dave Chinner <[email protected]>

The buffer cache hash is starting to show typical hash scalability problems. large scale testing is showing the number of cached items growing far larger than the hash can efficiently handle. Hence we need to move to a self-scaling cache indexing mechanism.

I have selected rbtrees for indexing becuse they can have O(log n) search scalability, and insert and remove cost is not excessive, even on large trees. Hence we should be able to cache large numbers of buffers without incurring the excessive cache miss search penalties that the hash is imposing on us.

Quoted 10 lines

To ensure we still have parallel access to the cache, we need multiple trees. Rather than hashing the buffers by disk address to select a tree, it seems more sensible to separate trees by typical access patterns. Most operations use buffers from within a single AG at a time, so rather than searching lots of different lists, separate the buffer indexes out into per-AG rbtrees. This means that searches during metadata operation have a much higher chance of hitting cache resident nodes, and that updates of the tree are less likely to disturb trees being accessed on other CPUs doing independent operations.

I found a bug in this, and have a bunch of other less important comments for you to consider. I haven't spent any time contemplating your decision to use RB trees on AG's but it seems quite reasonable.

fs/xfs/linux-2.6/xfs_buf.c

Quoted 13 lines
---
 fs/xfs/linux-2.6/xfs_buf.c   |  139 +++++++++++++++++++++--------------------
 fs/xfs/linux-2.6/xfs_buf.h   |   14 ++--
 fs/xfs/linux-2.6/xfs_super.c |    6 +-
 fs/xfs/xfs_ag.h              |    4 +
 fs/xfs/xfs_mount.c           |    4 +-
 5 files changed, 87 insertions(+), 80 deletions(-)
fs/xfs/linux-2.6/xfs_buf.c +0 -0
index b2b5dea..facd37e 100644

. . .

Quoted 15 lines
fs/xfs/linux-2.6/xfs_buf.c +3 -8
@@ -432,14 +434,36 @@ _xfs_buf_find(
 	ASSERT(!(range_length < (1 << btp->bt_sshift)));
 	ASSERT(!(range_base & (xfs_off_t)btp->bt_smask));
 
-	hash = &btp->bt_hash[hash_long((unsigned long)ioff, btp->bt_hashshift)];
-
-	spin_lock(&hash->bh_lock);
-
-	list_for_each_entry_safe(bp, n, &hash->bh_list, b_hash_list) {
-		ASSERT(btp == bp->b_target);
-		if (bp->b_file_offset == range_base &&
-		    bp->b_buffer_length == range_length) {
+	/* get tree root */
+	pag = xfs_perag_get(btp->bt_mp, xfs_daddr_to_agno(btp->bt_mp, ioff));
+
Quoted 8 lines

fs/xfs/linux-2.6/xfs_buf.c _xfs_buf_find( · line 443

Quoted 4 lines
fs/xfs/linux-2.6/xfs_buf.c +4 -0
+	/* walk tree */
+	spin_lock(&pag->pagbuf_lock);
+	rbp = &pag->pagbuf_tree.rb_node;
+	parent = NULL;

Could drop the above assignment and change the while statement to read: while ((parent = *rbp)) { (I know that leads to a mildly controversial style.)

That doesn't work. When we walk off the end of the tree, *rbp == NULL, but we need parent to point to the previous node we searched, as that is where we will insert the new node. The above code would change it so that on a search miss parent == NULL as well, which would panic or corrupt the tree on insert.

Quoted 9 lines

fs/xfs/linux-2.6/xfs_buf.c _xfs_buf_find( · line 447

Quoted 4 lines
fs/xfs/linux-2.6/xfs_buf.c +4 -0
+	bp = NULL;
+	while (*rbp) {
+		parent = *rbp;
+		bp = rb_entry(parent, struct xfs_buf, b_rbnode);

Below here you might as well make use of the value of "parent" in places where (*rbp) is used. I realize you're just mimicking what's in the rbtree.h file though...

And the same code that is in xfs_alloc.c for the busy extent list. I'd prefer to keep the code in a common form.

Quoted 3 lines

If the result seems to
read funny, maybe you could rename "parent" to be "entry" or something.

If we fall through to the insert case, it is the parent node we insert at. Hence parent is appropriate....

Quoted 8 lines

Here's the BUG:

fs/xfs/linux-2.6/xfs_buf.c _xfs_buf_find( · line 452

Quoted 4 lines
fs/xfs/linux-2.6/xfs_buf.c +4 -0
+		if (bp->b_file_offset < range_base)
+			rbp = &(*rbp)->rb_left;
+		else if (bp->b_file_offset > range_base)
+			rbp = &(*rbp)->rb_right;

Your comparisons here are reversed.

Hmmm, yes, good catch, but I don't think it matters because the left/right node relationship of the rbtree is maintained through rotations. Hence as long as we always search the same way as we do for insert, then we will always find the node we are looking for in the same number of steps.

Having just tested it, there is zero difference in performance, cache behaviour or CPU uasge. I'll swap it anyway, as it makes more sense to order the tree as people expect....

Quoted 11 lines

In other words,
I believe it should be:

	if (range_base < bp->b_file_offset)	
		rbp = &parent->rb_left;
	else if (range_base > bp->b_file_offset)
		rbp = &parent->rb_right;

Maybe it mostly works in the order you have it, but I'm pretty sure it's wrong. (The "continue searching to the right" below would be wrong though.)

Once again, as long as we always do things the same way (i.e. duplicate entries are always stored on the same side) it doesn't matter if we chose to continue the search to the left or right....

Quoted 6 lines
Quoted 6 lines
fs/xfs/linux-2.6/xfs_buf.c +6 -0
+		else {
+			/*
+			 * found a block offset match. If the range doesn't
+			 * match, the only way this is allowed is if the buffer
+			 * in the cache is stale and the transaction that made
+			 * it stale has not yet committed. i.e. we are
Quoted 8 lines

fs/xfs/linux-2.6/xfs_buf.c _xfs_buf_find( · line 463

Quoted 5 lines
fs/xfs/linux-2.6/xfs_buf.c +5 -0
+			 * reallocating a busy extent. Skip this buffer and
+			 * continue searching to the right for an exact match.
+			 */
+			if (bp->b_buffer_length != range_length) {
+				ASSERT(bp->b_flags & XBF_STALE);

This assertion is new. I trust it's correct, but maybe it should go in separately (first).

It's there to ensure that my assumption about why we can get duplicates in the rbtree is correct. In a hash, duplicate keys are not a big deal, and I want to ensure i understand why they are occurring. I'd prefer to leave it in this patch...

Quoted 5 lines
Quoted 5 lines
fs/xfs/linux-2.6/xfs_buf.c +3 -0
+				rbp = &(*rbp)->rb_right;
+				continue;
+			}
 			atomic_inc(&bp->b_hold);
 			goto found;
Quoted 8 lines

fs/xfs/linux-2.6/xfs_buf.c _xfs_buf_find( · line 468

Quoted 1 line
fs/xfs/linux-2.6/xfs_buf.c +0 -0
 		}

When I first read the next hunk I thought you were mistakenly not dropping the perag reference. Later I realized it was intentional--that the buffer holds a reference on the perag until it (the buffer) is released. This is a minor point but I think it would be helpful to see a comment explaining that.

Ok.

Quoted 6 lines
Quoted 6 lines
fs/xfs/linux-2.6/xfs_buf.c +1 -1
 xfs_buf_rele(
 	xfs_buf_t		*bp)
 {
-	xfs_bufhash_t		*hash = bp->b_hash;
+	struct xfs_perag	*pag = bp->b_pag;
Quoted 7 lines

fs/xfs/linux-2.6/xfs_buf.c void · line 844

Quoted 4 lines
fs/xfs/linux-2.6/xfs_buf.c +1 -1
 	trace_xfs_buf_rele(bp, _RET_IP_);
 
-	if (unlikely(!hash)) {
+	if (!pag) {

I know this is not related to your change, but I'm curious whether this can even happen, and if so, when?

All the uncached buffers obtained through xfs_buf_get_uncached() and xfs_buf_read_uncached() still use xfs_brelse()/xfs_buf_rele() to drop references.

Quoted 34 lines
Quoted 19 lines

void
xfs_wait_buftarg(

fs/xfs/linux-2.6/xfs_buf.c +7 -8
-	xfs_buftarg_t	*btp)
+	struct xfs_buftarg	*btp)
 {
-	xfs_bufhash_t	*hash;
-	uint		i;
+	struct xfs_perag	*pag;
+	uint			i;
 
-	for (i = 0; i < (1 << btp->bt_hashshift); i++) {
-		hash = &btp->bt_hash[i];
-		spin_lock(&hash->bh_lock);
-		while (!list_empty(&hash->bh_list)) {
-			spin_unlock(&hash->bh_lock);
+	for (i = 0; i < btp->bt_mp->m_sb.sb_agcount; i++) {
+		pag = xfs_perag_get(btp->bt_mp, i);
+		spin_lock(&pag->pagbuf_lock);
+		while (rb_first(&pag->pagbuf_tree)) {

fs/xfs/linux-2.6/xfs_buf.c xfs_buf_iomove( · line 1482

Quoted 10 lines
fs/xfs/linux-2.6/xfs_buf.c +4 -2
+			spin_unlock(&pag->pagbuf_lock);
 			delay(100);
-			spin_lock(&hash->bh_lock);
+			spin_lock(&pag->pagbuf_lock);
 		}
-		spin_unlock(&hash->bh_lock);
+		spin_unlock(&pag->pagbuf_lock);
+		xfs_perag_put(pag);
 	}
 }

This suggestion is again not related to your change, but... Would this basic structure (not tested) be better than the above?

Quoted 15 lines
	int more;

	do {
		more = 0;
		for (i = 0; i < btp->bt_mp->m_sb.sb_agcount; i++) {
			pag = xfs_perag_get(btp->bt_mp, i);
			spin_lock(&pag->pagbuf_lock);
			if (rb_first(&pag->pagbuf_tree))
				more++;
			spin_unlock(&pag->pagbuf_lock);
			xfs_perag_put(pag);
		}
		if (more)
			delay(100);
	} while (more);

Once we've found one AG that we have to wait for, checking the rest to see if we have to do a wait is unnecessary. We may as well wait first, then continue.

Quoted 10 lines
Quoted 5 lines

/*
- * Allocate buffer hash table for a given target.
- * For devices containing metadata (i.e. not the log/realtime devices)
- * we need to allocate a much larger hash table.

. . .

Quoted 2 lines
fs/xfs/linux-2.6/xfs_buf.c +0 -0
@@ -1645,6 +1643,12 @@ xfs_alloc_buftarg(
 
Quoted 7 lines

fs/xfs/linux-2.6/xfs_buf.c xfs_alloc_buftarg( · line 1647

Quoted 4 lines
fs/xfs/linux-2.6/xfs_buf.c +2 -0
 	btp = kmem_zalloc(sizeof(*btp), KM_SLEEP);
 
+	/*
+	 * The buftarg cache should never be used by external devices.

I suggest that "buftarg cache" is not a good name for the (now per-AG) buffer cache.

That's already gone.

Quoted 49 lines

fs/xfs/linux-2.6/xfs_buf.h

Quoted 20 lines
fs/xfs/linux-2.6/xfs_buf.c +4 -1
+	 * Ensure we catch any users with extreme prejudice.
+	 */
+	btp->bt_mp = external ? NULL : mp;
+
 	btp->bt_dev =  bdev->bd_dev;
 	btp->bt_bdev = bdev;
 	if (xfs_setsize_buftarg_early(btp, bdev))
@@ -1653,7 +1657,6 @@ xfs_alloc_buftarg(
 		goto error;
 	if (xfs_alloc_delwrite_queue(btp, fsname))
 		goto error;
-	xfs_alloc_bufhash(btp, external);
 	return btp;
 
 error:
fs/xfs/linux-2.6/xfs_buf.h +0 -0
index 802dc5e..3797ee8 100644

. . .

fs/xfs/linux-2.6/xfs_buf.h typedef struct xfs_buf { · line 174

Quoted 8 lines
fs/xfs/linux-2.6/xfs_buf.h +2 -2
@@ -171,8 +170,8 @@ typedef struct xfs_buf {
 	wait_queue_head_t	b_waiters;	/* unpin waiters */
 	struct list_head	b_list;
 	xfs_buf_flags_t		b_flags;	/* status flags */
-	struct list_head	b_hash_list;	/* hash table list */
-	xfs_bufhash_t		*b_hash;	/* hash table list start */
+	struct rb_node		b_rbnode;	/* rbtree node */
+	struct xfs_perag	*b_pag;		/* rbtree root */

Rather, "contains rbtree root" (in the comment).

fs/xfs/linux-2.6/xfs_buf.h typedef struct xfs_buf { · line 177

Quoted 3 lines
fs/xfs/linux-2.6/xfs_buf.h +0 -0
 	xfs_buftarg_t		*b_target;	/* buffer target (device) */
 	atomic_t		b_hold;		/* reference count */
 	xfs_daddr_t		b_bn;		/* block number for I/O */

. . .

Quoted 11 lines
fs/xfs/xfs_ag.h +3 -0
index 4917d4e..e01d4cf 100644
@@ -230,6 +230,10 @@ typedef struct xfs_perag {
 	rwlock_t	pag_ici_lock;	/* incore inode lock */
 	struct radix_tree_root pag_ici_root;	/* incore inode cache root */
 	int		pag_ici_reclaimable;	/* reclaimable inodes */
+
+	/* buffer cache index */
+	spinlock_t	pagbuf_lock;	/* lock for pagbuf_tree */
Quoted 8 lines

fs/xfs/xfs_ag.h typedef struct xfs_perag { · line 236

Quoted 1 line
fs/xfs/xfs_ag.h +1 -0
+	struct rb_root	pagbuf_tree;	/* ordered tree of active buffers */

I know it's in some way consistent with the rest of the naming scheme for fields in this structure, maybe these could be named pag_buf_lock and pag_buf_tree. (The rest of the fields here have a sort of strange convention and maybe they've got strong enough history that they should be left alone.)

OK. I'll change if to pag_buf_...

FYI:
pagi = per-ag AGI data
pagf = per-ag AGF data
pagb = per-ag busy extent
pagl = per-ag inode lookup
pag_ici = per-ag inode cache index

Cheers,

Dave.

Signature · 7 lines
Dave Chinner
[email protected]

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