From: Dave Chinner <david@fromorbit.com>
To: linux-xfs@vger.kernel.org
Subject: [PATCH 19/27] libxfs: add cache infrastructure to buftarg
Date: Thu, 15 Oct 2020 18:21:47 +1100 [thread overview]
Message-ID: <20201015072155.1631135-20-david@fromorbit.com> (raw)
In-Reply-To: <20201015072155.1631135-1-david@fromorbit.com>
From: Dave Chinner <dchinner@redhat.com>
Add a hash cache interface to the libxfs buftarg implementation.
This is a massively cut down version of the existing cache, just
with all the stuff the buftarg will provide chopped out of it.
Signed-off-by: Dave Chinner <dchinner@redhat.com>
---
include/xfs_mount.h | 3 +
libxfs/buftarg.c | 233 +++++++++++++++++++++++++++++++++++++++++++
libxfs/libxfs_io.h | 3 +-
libxfs/xfs_buftarg.h | 45 +++++++++
4 files changed, 283 insertions(+), 1 deletion(-)
diff --git a/include/xfs_mount.h b/include/xfs_mount.h
index d78c4cdc4f78..114d9744d114 100644
--- a/include/xfs_mount.h
+++ b/include/xfs_mount.h
@@ -10,6 +10,7 @@
struct xfs_inode;
struct xfs_buftarg;
struct xfs_da_geometry;
+struct btcache;
/*
* Define a user-level mount structure with all we need
@@ -155,6 +156,8 @@ typedef struct xfs_perag {
/* reference count */
uint8_t pagf_refcount_level;
+
+ struct btcache *pag_buf_hash;
} xfs_perag_t;
static inline struct xfs_ag_resv *
diff --git a/libxfs/buftarg.c b/libxfs/buftarg.c
index 1f6a89d14ec6..4f4254e4fd70 100644
--- a/libxfs/buftarg.c
+++ b/libxfs/buftarg.c
@@ -425,3 +425,236 @@ xfs_buf_associate_memory(
bp->b_length = BTOBB(len);
return 0;
}
+
+/*
+ * Buffer cache hash implementation
+ */
+
+struct btcache *
+btc_init(
+ unsigned int hashsize)
+{
+ struct btcache *btc;
+ unsigned int i, maxcount;
+
+ maxcount = hashsize * HASH_CACHE_RATIO;
+
+ btc = malloc(sizeof(struct btcache));
+ if (!btc)
+ return NULL;
+ btc->hash = calloc(hashsize, sizeof(struct btcache_hash));
+ if (!btc->hash) {
+ free(btc);
+ return NULL;
+ }
+
+ atomic_set(&btc->count, 0);
+ btc->max = 0;
+ btc->hits = 0;
+ btc->misses = 0;
+ btc->maxcount = maxcount;
+ btc->hashsize = hashsize;
+ btc->hashshift = libxfs_highbit32(hashsize);
+ pthread_mutex_init(&btc->lock, NULL);
+
+ for (i = 0; i < hashsize; i++) {
+ list_head_init(&btc->hash[i].chain);
+ btc->hash[i].count = 0;
+ pthread_mutex_init(&btc->hash[i].lock, NULL);
+ }
+
+ return btc;
+}
+
+void
+btc_destroy(
+ struct btcache *btc)
+{
+ unsigned int i;
+
+ if (!btc)
+ return;
+
+ for (i = 0; i < btc->hashsize; i++) {
+ list_head_destroy(&btc->hash[i].chain);
+ pthread_mutex_destroy(&btc->hash[i].lock);
+ }
+ pthread_mutex_destroy(&btc->lock);
+ free(btc->hash);
+ free(btc);
+}
+
+
+#define HASH_REPORT (3 * HASH_CACHE_RATIO)
+void
+btc_report_ag(
+ FILE *fp,
+ const char *name,
+ xfs_agnumber_t agno,
+ struct btcache *btc)
+{
+ int i;
+ unsigned long count, index, total;
+ unsigned long hash_bucket_lengths[HASH_REPORT + 2];
+
+ if ((btc->hits + btc->misses) == 0)
+ return;
+
+ /* report btc summary */
+ fprintf(fp, "%8u|\t%9u\t%9u\t%8u\t%8u\t%8llu\t%8llu\t%5.2f\n",
+ agno,
+ btc->maxcount,
+ btc->max,
+ atomic_read(&btc->count),
+ btc->hashsize,
+ btc->hits,
+ btc->misses,
+ (double)btc->hits * 100 /
+ (btc->hits + btc->misses)
+ );
+
+ /* report hash bucket lengths */
+ memset(hash_bucket_lengths, 0, sizeof(hash_bucket_lengths));
+
+ for (i = 0; i < btc->hashsize; i++) {
+ count = btc->hash[i].count;
+ if (count > HASH_REPORT)
+ index = HASH_REPORT + 1;
+ else
+ index = count;
+ hash_bucket_lengths[index]++;
+ }
+
+ total = 0;
+ for (i = 0; i < HASH_REPORT + 1; i++) {
+ total += i * hash_bucket_lengths[i];
+ if (hash_bucket_lengths[i] == 0)
+ continue;
+ fprintf(fp, "Hash buckets with %2d entries %6ld (%3ld%%)\n",
+ i, hash_bucket_lengths[i],
+ (i * hash_bucket_lengths[i] * 100) /
+ atomic_read(&btc->count));
+ }
+ if (hash_bucket_lengths[i]) /* last report bucket is the overflow bucket */
+ fprintf(fp, "Hash buckets with >%2d entries %6ld (%3ld%%)\n",
+ i - 1, hash_bucket_lengths[i],
+ ((btc->count - total) * 100) /
+ atomic_read(&btc->count));
+}
+
+void
+btc_report(
+ FILE *fp,
+ const char *name,
+ struct xfs_mount *mp)
+{
+ int i;
+
+ if (!mp)
+ return;
+
+ fprintf(fp, "%s: Per-AG summary\n", name);
+ fprintf(fp, "AG\t|\t\tEntries\t\t|\t\tHash Table\n");
+ fprintf(fp, "\t|\tSupported\tUtilised\tActive\tSize\tHits\tMisses\tRatio\n");
+ for (i = 0; i < mp->m_sb.sb_agcount; i++) {
+ struct xfs_perag *pag = xfs_perag_get(mp, i);
+
+ btc_report_ag(fp, name, i, pag->pag_buf_hash);
+
+ xfs_perag_put(pag);
+ }
+}
+
+/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
+#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
+#define CACHE_LINE_SIZE 64
+static unsigned int
+btchash(xfs_daddr_t blkno, unsigned int hashsize, unsigned int hashshift)
+{
+ uint64_t hashval = blkno;
+ uint64_t tmp;
+
+ tmp = hashval ^ (GOLDEN_RATIO_PRIME + hashval) / CACHE_LINE_SIZE;
+ tmp = tmp ^ ((tmp ^ GOLDEN_RATIO_PRIME) >> hashshift);
+ return tmp % hashsize;
+}
+
+struct xfs_buf *
+btc_node_find(
+ struct btcache *btc,
+ struct xfs_buf_map *map)
+{
+ struct xfs_buf *bp = NULL;
+ struct btcache_hash *hash;
+ struct list_head *head;
+ unsigned int hashidx;
+
+
+ hashidx = btchash(map->bm_bn, btc->hashsize, btc->hashshift);
+ hash = btc->hash + hashidx;
+ head = &hash->chain;
+
+ pthread_mutex_lock(&hash->lock);
+ list_for_each_entry(bp, head, b_hash) {
+ if (bp->b_bn != map->bm_bn)
+ continue;
+
+ if (bp->b_length != map->bm_len) {
+ /*
+ * found a block number match. If the range doesn't
+ * match, the only way this is allowed is if the buffer
+ * in the btc 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 for an exact match.
+ */
+ ASSERT(bp->b_flags & XBF_STALE);
+ continue;
+ }
+ btc->hits++;
+ pthread_mutex_unlock(&hash->lock);
+ return bp;
+
+ }
+ btc->misses++;
+ pthread_mutex_unlock(&hash->lock);
+ return NULL;
+}
+
+void
+btc_node_insert(
+ struct btcache *btc,
+ struct xfs_buf *bp)
+{
+ struct btcache_hash *hash;
+ struct list_head *head;
+ unsigned int hashidx;
+
+ hashidx = btchash(bp->b_bn, btc->hashsize, btc->hashshift);
+ hash = btc->hash + hashidx;
+ head = &hash->chain;
+
+ pthread_mutex_lock(&hash->lock);
+ list_add(&bp->b_hash, head);
+ hash->count++;
+ atomic_inc(&btc->count);
+ pthread_mutex_unlock(&hash->lock);
+}
+
+void
+btc_node_remove(
+ struct btcache *btc,
+ struct xfs_buf *bp)
+{
+ struct btcache_hash *hash;
+ unsigned int hashidx;
+
+ hashidx = btchash(bp->b_bn, btc->hashsize, btc->hashshift);
+ hash = btc->hash + hashidx;
+
+ pthread_mutex_lock(&hash->lock);
+ list_del(&bp->b_hash);
+ hash->count--;
+ atomic_dec(&btc->count);
+ pthread_mutex_unlock(&hash->lock);
+}
diff --git a/libxfs/libxfs_io.h b/libxfs/libxfs_io.h
index c17cdc33bf2a..31c21abce8c9 100644
--- a/libxfs/libxfs_io.h
+++ b/libxfs/libxfs_io.h
@@ -44,9 +44,10 @@ struct xfs_buf_ops {
struct xfs_buf {
struct cache_node b_node;
- unsigned int b_flags;
+ struct list_head b_hash; /* will replace b_node */
xfs_daddr_t b_bn;
unsigned int b_length;
+ unsigned int b_flags;
struct xfs_buftarg *b_target;
pthread_mutex_t b_lock;
pthread_t b_holder;
diff --git a/libxfs/xfs_buftarg.h b/libxfs/xfs_buftarg.h
index 7d2a7ab29c0f..fee20c60db1c 100644
--- a/libxfs/xfs_buftarg.h
+++ b/libxfs/xfs_buftarg.h
@@ -13,6 +13,10 @@ struct xfs_buf_ops;
#define XFS_BUF_DADDR_NULL ((xfs_daddr_t) (-1LL))
+struct xfs_buf;
+struct xfs_buf_map;
+struct xfs_mount;
+
/*
* The xfs_buftarg contains 2 notions of "sector size" -
*
@@ -101,4 +105,45 @@ int xfs_bwrite(struct xfs_buf *bp);
struct xfs_buf *libxfs_getbufr(struct xfs_buftarg *btp, xfs_daddr_t blkno,
int bblen);
+/*
+ * Hash cache implementation
+ */
+/*
+ * xfs_db always writes changes immediately, and so we need to purge buffers
+ * when we get a buffer lookup mismatch due to reading the same block with a
+ * different buffer configuration.
+ *
+ * XXX: probably need to re-implement this
+ */
+#define CACHE_MISCOMPARE_PURGE (1 << 0)
+
+#define HASH_CACHE_RATIO 8
+
+struct btcache_hash {
+ struct list_head chain;
+ unsigned int count;
+ pthread_mutex_t lock;
+};
+
+struct btcache {
+ int flags; /* behavioural flags */
+ unsigned int maxcount; /* max cache nodes */
+ atomic_t count; /* count of nodes */
+ pthread_mutex_t lock; /* node count mutex */
+ unsigned int hashsize; /* hash bucket count */
+ unsigned int hashshift; /* hash key shift */
+ struct btcache_hash *hash; /* hash table buckets */
+ unsigned long long misses; /* cache misses */
+ unsigned long long hits; /* cache hits */
+ unsigned int max; /* max nodes ever used */
+};
+
+struct btcache *btc_init(unsigned int hashsize);
+void btc_destroy(struct btcache *cache);
+
+struct xfs_buf *btc_node_find(struct btcache *cache, struct xfs_buf_map *map);
+void btc_node_insert(struct btcache *cache, struct xfs_buf *bp);
+void btc_node_remove(struct btcache *cache, struct xfs_buf *bp);
+void btc_report(FILE *fp, const char *name, struct xfs_mount *mp);
+
#endif /* __XFS_BUFTARG_H */
--
2.28.0
next prev parent reply other threads:[~2020-10-15 7:22 UTC|newest]
Thread overview: 49+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-10-15 7:21 [PATCH 00/27] [RFC, WIP] xfsprogs: xfs_buf unification and AIO Dave Chinner
2020-10-15 7:21 ` [PATCH 01/27] xfsprogs: remove unused buffer tracing code Dave Chinner
2020-10-15 7:21 ` [PATCH 02/27] xfsprogs: remove unused IO_DEBUG functionality Dave Chinner
2020-11-16 2:31 ` Eric Sandeen
2020-10-15 7:21 ` [PATCH 03/27] libxfs: get rid of b_bcount from xfs_buf Dave Chinner
2020-11-23 19:53 ` Eric Sandeen
2020-10-15 7:21 ` [PATCH 04/27] libxfs: rename buftarg->dev to btdev Dave Chinner
2020-11-16 2:33 ` Eric Sandeen
2020-10-15 7:21 ` [PATCH 05/27] xfsprogs: get rid of ancient btree tracing fragments Dave Chinner
2020-11-16 2:35 ` Eric Sandeen
2020-10-15 7:21 ` [PATCH 06/27] xfsprogs: remove xfs_buf_t typedef Dave Chinner
2020-10-15 15:22 ` Darrick J. Wong
2020-10-15 20:54 ` Dave Chinner
2020-10-15 7:21 ` [PATCH 07/27] xfsprogs: introduce liburcu support Dave Chinner
2020-10-15 7:21 ` [PATCH 08/27] libxfs: add spinlock_t wrapper Dave Chinner
2020-10-15 7:21 ` [PATCH 09/27] atomic: convert to uatomic Dave Chinner
2020-10-15 7:21 ` [PATCH 10/27] libxfs: add kernel-compatible completion API Dave Chinner
2020-10-15 17:09 ` Darrick J. Wong
2020-10-19 22:21 ` Dave Chinner
2020-10-15 7:21 ` [PATCH 11/27] libxfs: add wrappers for kernel semaphores Dave Chinner
2020-10-15 7:21 ` [PATCH 12/27] xfsprogs: convert use-once buffer reads to uncached IO Dave Chinner
2020-10-15 17:12 ` Darrick J. Wong
2020-10-19 22:36 ` Dave Chinner
2020-10-15 7:21 ` [PATCH 13/27] libxfs: introduce userspace buftarg infrastructure Dave Chinner
2020-10-15 7:21 ` [PATCH 14/27] xfs: rename libxfs_buftarg_init to libxfs_open_devices() Dave Chinner
2020-10-15 7:21 ` [PATCH 15/27] libxfs: introduce userspace buftarg infrastructure Dave Chinner
2020-10-15 17:16 ` Darrick J. Wong
2020-10-15 7:21 ` [PATCH 16/27] libxfs: add a synchronous IO engine to the buftarg Dave Chinner
2020-10-15 7:21 ` [PATCH 17/27] xfsprogs: convert libxfs_readbufr to libxfs_buf_read_uncached Dave Chinner
2020-10-15 7:21 ` [PATCH 18/27] libxfs: convert libxfs_bwrite to buftarg IO Dave Chinner
2020-10-15 7:21 ` Dave Chinner [this message]
2020-10-15 7:21 ` [PATCH 20/27] libxfs: add internal lru to btcache Dave Chinner
2020-10-15 7:21 ` [PATCH 21/27] libxfs: Add kernel list_lru wrapper Dave Chinner
2020-10-15 7:21 ` [PATCH 22/27] libxfs: introduce new buffer cache infrastructure Dave Chinner
2020-10-15 17:46 ` Darrick J. Wong
2020-10-15 7:21 ` [PATCH 23/27] libxfs: use PSI information to detect memory pressure Dave Chinner
2020-10-15 17:56 ` Darrick J. Wong
2020-10-15 21:20 ` Dave Chinner
2020-10-15 7:21 ` [PATCH 24/27] libxfs: add a buftarg cache shrinker implementation Dave Chinner
2020-10-15 18:01 ` Darrick J. Wong
2020-10-15 21:33 ` Dave Chinner
2020-10-15 7:21 ` [PATCH 25/27] libxfs: switch buffer cache implementations Dave Chinner
2020-10-15 7:21 ` [PATCH 26/27] build: set platform_defs.h.in dependency correctly Dave Chinner
2020-10-15 7:21 ` [PATCH 27/27] libxfs: convert sync IO buftarg engine to AIO Dave Chinner
2020-10-15 18:26 ` Darrick J. Wong
2020-10-15 21:42 ` Dave Chinner
2020-10-15 7:29 ` [PATCH 00/27] [RFC, WIP] xfsprogs: xfs_buf unification and AIO Dave Chinner
2020-10-15 18:37 ` Darrick J. Wong
2020-10-15 22:35 ` Dave Chinner
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20201015072155.1631135-20-david@fromorbit.com \
--to=david@fromorbit.com \
--cc=linux-xfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.