Replace buffer cache hash with rbtrees
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
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
@@ -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 @@ voidxfs_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
@@ -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
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
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_noaddrwill 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_releselabel 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_freesbto not usexfs_getsband 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
Re: [PATCH 1/4] xfs: kill XBF_FS_MANAGED buffers
In reply to Dave ChinnerQuoted 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 theXBF_FS_MANAGEDspecial 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
Signed-off-by Dave Chinner <[email protected]>
. . .
_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs
PATCH 2/4 xfs: use unhashed buffers for size checks
In reply to Dave ChinnerFrom: 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
@@ -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
@@ -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
@@ -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
@@ -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
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
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_bufand 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_getandbuf_readinterfaces 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_noaddrnever 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_noaddrdoesn't. I suspect we should also changebuf_get_noaddrto 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
Re: [PATCH 2/4] xfs: use unhashed buffers for size checks
In reply to Dave ChinnerQuoted 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
Signed-off-by Dave Chinner <[email protected]>
_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs
PATCH 3/4 xfs: remove buftarg hash for external devices
In reply to Dave ChinnerFrom: 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
@@ -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
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.
Signed-off-by Dave Chinner <[email protected]>
Looks good,
_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs
PATCH 4/4 xfs: convert buffer cache hash to rbtree
In reply to Dave ChinnerFrom: 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
@@ -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 @@ voidxfs_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
@@ -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
@@ -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
@@ -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
@@ -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
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
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_mountfield structxfs_bufwhich 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_mountwould be much nicer name thanbt_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
Re: [PATCH 4/4] xfs: convert buffer cache hash to rbtree
In reply to Christoph HellwigQuoted 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
Re: [PATCH 4/4] xfs: convert buffer cache hash to rbtree
In reply to Dave ChinnerQuoted 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
Signed-off-by Dave Chinner <[email protected]>--- 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
. . .
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 @@ voidxfs_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
-0ASSERT (!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
. . .
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
-0xfs_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@@ -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
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
Signed-off-by Dave Chinner <[email protected]>--- 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. . .
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.hfile 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
-1xfs_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
-1trace_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
-0btp =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. . .
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
-0xfs_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@@ -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_lockandpag_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 lookuppag_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