Linux-XFS Archive on lore.kernel.org
 help / color / Atom feed
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
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


  parent reply index

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

Linux-XFS Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-xfs/0 linux-xfs/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-xfs linux-xfs/ https://lore.kernel.org/linux-xfs \
		linux-xfs@vger.kernel.org
	public-inbox-index linux-xfs

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-xfs


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git