xfs: check absolute maximum nlevels for each btree type

Add code for all five btree types so that we can compute the absolute
maximum possible btree height for each btree type, and then check that
none of them exceed XFS_BTREE_CUR_ZONE_MAXLEVELS.  The code to do the
actual checking is a little excessive, but it sets us up for per-type
cursor zones in the next patch.

xfs_btree_absolute_maxlevels exists to enable xfs_db functionality.

Signed-off-by: Darrick J. Wong <djwong@kernel.org>

15 files changed, 282 insertions, 0 deletions

diff --git a/fs/xfs/libxfs/xfs_alloc_btree.c b/fs/xfs/libxfs/xfs_alloc_btree.c
index 502502156fd8..770454e58164 100644
--- a/fs/xfs/libxfs/xfs_alloc_btree.c
+++ b/fs/xfs/libxfs/xfs_alloc_btree.c
@@ -582,6 +582,31 @@ xfs_allocbt_maxrecs(
 	return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t));
 }
 
+static inline __init unsigned int
+xfs_allocbt_absolute_maxlevels(void)
+{
+	unsigned int		minrecs[2];
+
+	xfs_btree_absolute_minrecs(minrecs, 0, sizeof(xfs_alloc_rec_t),
+			sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t));
+
+	return xfs_btree_compute_maxlevels(minrecs,
+			(XFS_MAX_AG_BLOCKS + 1) / 2);
+}
+
+int __init
+xfs_allocbt_create_cursor_cache(void)
+{
+	int			error;
+
+	error = xfs_btree_create_cursor_cache(XFS_BTNUM_BNO, "xfs_allocbt_cur",
+			xfs_allocbt_absolute_maxlevels());
+	if (error)
+		return error;
+
+	return xfs_btree_alias_cursor_cache(XFS_BTNUM_CNT, XFS_BTNUM_BNO);
+}
+
 /* Calculate the freespace btree size for some records. */
 xfs_extlen_t
 xfs_allocbt_calc_size(
diff --git a/fs/xfs/libxfs/xfs_alloc_btree.h b/fs/xfs/libxfs/xfs_alloc_btree.h
index a3cf5f7a4b51..040d532f45a0 100644
--- a/fs/xfs/libxfs/xfs_alloc_btree.h
+++ b/fs/xfs/libxfs/xfs_alloc_btree.h
@@ -61,4 +61,6 @@ extern xfs_extlen_t xfs_allocbt_calc_size(struct xfs_mount *mp,
 void xfs_allocbt_commit_staged_btree(struct xfs_btree_cur *cur,
 		struct xfs_trans *tp, struct xfs_buf *agbp);
 
+int __init xfs_allocbt_create_cursor_cache(void);
+
 #endif	/* __XFS_ALLOC_BTREE_H__ */
diff --git a/fs/xfs/libxfs/xfs_bmap_btree.c b/fs/xfs/libxfs/xfs_bmap_btree.c
index f48278883d28..3e90ee968500 100644
--- a/fs/xfs/libxfs/xfs_bmap_btree.c
+++ b/fs/xfs/libxfs/xfs_bmap_btree.c
@@ -720,6 +720,26 @@ xfs_bmbt_maxrecs(
 	return blocklen / (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t));
 }
 
+static inline __init unsigned int
+xfs_bmbt_absolute_maxlevels(void)
+{
+	unsigned int		minrecs[2];
+
+	xfs_btree_absolute_minrecs(minrecs, XFS_BTREE_LONG_PTRS,
+			sizeof(struct xfs_bmbt_rec),
+			sizeof(struct xfs_bmbt_key) +
+				sizeof(xfs_bmbt_ptr_t));
+
+	return xfs_btree_compute_maxlevels(minrecs, MAXEXTNUM) + 1;
+}
+
+int __init
+xfs_bmbt_create_cursor_cache(void)
+{
+	return xfs_btree_create_cursor_cache(XFS_BTNUM_BMAP, "xfs_bmapbt_cur",
+			xfs_bmbt_absolute_maxlevels());
+}
+
 /*
  * Calculate number of records in a bmap btree inode root.
  */
diff --git a/fs/xfs/libxfs/xfs_bmap_btree.h b/fs/xfs/libxfs/xfs_bmap_btree.h
index aa5e48826dd4..80ecc5a45fc3 100644
--- a/fs/xfs/libxfs/xfs_bmap_btree.h
+++ b/fs/xfs/libxfs/xfs_bmap_btree.h
@@ -52,6 +52,8 @@ void xfs_bmbt_commit_staged_btree(struct xfs_btree_cur *cur,
 extern unsigned long long xfs_bmbt_calc_size(struct xfs_mount *mp,
 		unsigned long long len);
 
+int __init xfs_bmbt_create_cursor_cache(void);
+
 /*
  * Btree block header size depends on a superblock flag.
  */
diff --git a/fs/xfs/libxfs/xfs_btree.c b/fs/xfs/libxfs/xfs_btree.c
index b610f2f97687..31826a4c98f0 100644
--- a/fs/xfs/libxfs/xfs_btree.c
+++ b/fs/xfs/libxfs/xfs_btree.c
@@ -29,6 +29,14 @@
  */
 kmem_zone_t	*xfs_btree_cur_zone;
 
+struct xfs_btree_cur_cache {
+	const char		*name;
+	unsigned short		maxlevels;
+	bool			alias;
+};
+
+static struct xfs_btree_cur_cache xfs_btree_cur_caches[XFS_BTNUM_MAX];
+
 /*
  * Btree magic numbers.
  */
@@ -5332,3 +5340,95 @@ xfs_btree_alloc_cursor(
 
 	return cur;
 }
+
+/*
+ * Compute absolute minrecs for leaf and node btree blocks.  Callers should set
+ * BTREE_LONG_PTRS and BTREE_OVERLAPPING as they would for regular cursors.
+ * Set BTREE_CRC_BLOCKS if the btree type is supported /only/ on V5 or newer
+ * filesystems.
+ */
+void __init
+xfs_btree_absolute_minrecs(
+	unsigned int		*minrecs,
+	unsigned int		bc_flags,
+	unsigned int		leaf_recbytes,
+	unsigned int		node_recbytes)
+{
+	unsigned int		min_recbytes;
+
+	/*
+	 * If this btree type is supported on V4, we use the smaller V4 min
+	 * block size along with the V4 header size.  If the btree type is only
+	 * supported on V5, use the (twice as large) V5 min block size along
+	 * with the V5 header size.
+	 */
+	if (!(bc_flags & XFS_BTREE_CRC_BLOCKS)) {
+		if (bc_flags & XFS_BTREE_LONG_PTRS)
+			min_recbytes = XFS_MIN_BLOCKSIZE -
+							XFS_BTREE_LBLOCK_LEN;
+		else
+			min_recbytes = XFS_MIN_BLOCKSIZE -
+							XFS_BTREE_SBLOCK_LEN;
+	} else if (bc_flags & XFS_BTREE_LONG_PTRS) {
+		min_recbytes = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_LBLOCK_CRC_LEN;
+	} else {
+		min_recbytes = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN;
+	}
+
+	if (bc_flags & XFS_BTREE_OVERLAPPING)
+		node_recbytes <<= 1;
+
+	minrecs[0] = min_recbytes / (2 * leaf_recbytes);
+	minrecs[1] = min_recbytes / (2 * node_recbytes);
+}
+
+/* Set up a btree cursor cache for a given btree type. */
+int __init
+xfs_btree_create_cursor_cache(
+	xfs_btnum_t				btnum,
+	const char				*name,
+	unsigned int				maxlevels)
+{
+	struct xfs_btree_cur_cache		*cc;
+
+	cc = &xfs_btree_cur_caches[btnum];
+
+	ASSERT(cc->maxlevels == 0);
+
+	cc->name = name;
+	cc->maxlevels = maxlevels;
+	cc->alias = false;
+
+	return 0;
+}
+
+/* Set up a btree cursor cache to reuse the cache of another btree type. */
+int __init
+xfs_btree_alias_cursor_cache(
+	xfs_btnum_t				btnum,
+	xfs_btnum_t				src)
+{
+	struct xfs_btree_cur_cache		*cd;
+	const struct xfs_btree_cur_cache	*cs;
+
+
+	cd = &xfs_btree_cur_caches[btnum];
+	cs = &xfs_btree_cur_caches[src];
+
+	ASSERT(cd->maxlevels == 0);
+	ASSERT(cs->maxlevels > 0);
+
+	cd->name = cs->name;
+	cd->maxlevels = cs->maxlevels;
+	cd->alias = true;
+
+	return 0;
+}
+
+/* Return the maximum possible height for a given type of btree. */
+unsigned int
+xfs_btree_absolute_maxlevels(
+	xfs_btnum_t				btnum)
+{
+	return xfs_btree_cur_caches[btnum].maxlevels;
+}
diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h
index e1cc9d700212..f84d36b4b6c2 100644
--- a/fs/xfs/libxfs/xfs_btree.h
+++ b/fs/xfs/libxfs/xfs_btree.h
@@ -592,4 +592,12 @@ struct xfs_btree_cur *xfs_btree_alloc_cursor(struct xfs_mount *mp,
 		struct xfs_trans *tp, xfs_btnum_t btnum);
 unsigned int xfs_btree_maxlevels(struct xfs_mount *mp, xfs_btnum_t btnum);
 
+void __init xfs_btree_absolute_minrecs(unsigned int *minrecs,
+		unsigned int bc_flags, unsigned int leaf_recbytes,
+		unsigned int node_recbytes);
+int __init xfs_btree_create_cursor_cache(xfs_btnum_t btnum, const char *name,
+		unsigned int maxlevels);
+int __init xfs_btree_alias_cursor_cache(xfs_btnum_t btnum, xfs_btnum_t src);
+unsigned int xfs_btree_absolute_maxlevels(xfs_btnum_t btnum);
+
 #endif	/* __XFS_BTREE_H__ */
diff --git a/fs/xfs/libxfs/xfs_fs.h b/fs/xfs/libxfs/xfs_fs.h
index 2594fb647384..ae80a6530750 100644
--- a/fs/xfs/libxfs/xfs_fs.h
+++ b/fs/xfs/libxfs/xfs_fs.h
@@ -271,6 +271,9 @@ typedef struct xfs_fsop_resblks {
  */
 #define XFS_MIN_AG_BYTES	(1ULL << 24)	/* 16 MB */
 #define XFS_MAX_AG_BYTES	(1ULL << 40)	/* 1 TB */
+#define XFS_MAX_AG_BLOCKS	(XFS_MAX_AG_BYTES / XFS_MIN_BLOCKSIZE)
+#define XFS_MAX_CRC_AG_BLOCKS	(XFS_MAX_AG_BYTES / XFS_MIN_CRC_BLOCKSIZE)
+#define XFS_MAX_AG_INODES	(XFS_MAX_AG_BYTES / XFS_DINODE_MIN_SIZE)
 
 /* keep the maximum size under 2^31 by a small amount */
 #define XFS_MAX_LOG_BYTES \
diff --git a/fs/xfs/libxfs/xfs_ialloc_btree.c b/fs/xfs/libxfs/xfs_ialloc_btree.c
index 01cf82bcac97..1f7db27439ef 100644
--- a/fs/xfs/libxfs/xfs_ialloc_btree.c
+++ b/fs/xfs/libxfs/xfs_ialloc_btree.c
@@ -541,6 +541,30 @@ xfs_inobt_maxrecs(
 	return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
 }
 
+static inline __init unsigned int
+xfs_inobt_absolute_maxlevels(void)
+{
+	unsigned int		minrecs[2];
+
+	xfs_btree_absolute_minrecs(minrecs, 0, sizeof(xfs_inobt_rec_t),
+			sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
+
+	return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_AG_INODES);
+}
+
+int __init
+xfs_inobt_create_cursor_cache(void)
+{
+	int			error;
+
+	error = xfs_btree_create_cursor_cache(XFS_BTNUM_INO, "xfs_inobt_cur",
+			xfs_inobt_absolute_maxlevels());
+	if (error)
+		return error;
+
+	return xfs_btree_alias_cursor_cache(XFS_BTNUM_FINO, XFS_BTNUM_INO);
+}
+
 /*
  * Convert the inode record holemask to an inode allocation bitmap. The inode
  * allocation bitmap is inode granularity and specifies whether an inode is
diff --git a/fs/xfs/libxfs/xfs_ialloc_btree.h b/fs/xfs/libxfs/xfs_ialloc_btree.h
index 51241354bd30..330643fa1d36 100644
--- a/fs/xfs/libxfs/xfs_ialloc_btree.h
+++ b/fs/xfs/libxfs/xfs_ialloc_btree.h
@@ -76,4 +76,6 @@ int xfs_inobt_cur(struct xfs_mount *mp, struct xfs_trans *tp,
 void xfs_inobt_commit_staged_btree(struct xfs_btree_cur *cur,
 		struct xfs_trans *tp, struct xfs_buf *agbp);
 
+int __init xfs_inobt_create_cursor_cache(void);
+
 #endif	/* __XFS_IALLOC_BTREE_H__ */
diff --git a/fs/xfs/libxfs/xfs_refcount_btree.c b/fs/xfs/libxfs/xfs_refcount_btree.c
index 22501e7985ea..ca95d62122fa 100644
--- a/fs/xfs/libxfs/xfs_refcount_btree.c
+++ b/fs/xfs/libxfs/xfs_refcount_btree.c
@@ -409,6 +409,27 @@ xfs_refcountbt_maxrecs(
 			   sizeof(xfs_refcount_ptr_t));
 }
 
+static inline __init unsigned int
+xfs_refcountbt_absolute_maxlevels(void)
+{
+	unsigned int		minrecs[2];
+
+	xfs_btree_absolute_minrecs(minrecs, XFS_BTREE_CRC_BLOCKS,
+			sizeof(struct xfs_refcount_rec),
+			sizeof(struct xfs_refcount_key) +
+						sizeof(xfs_refcount_ptr_t));
+
+	return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_CRC_AG_BLOCKS);
+}
+
+int __init
+xfs_refcountbt_create_cursor_cache(void)
+{
+	return xfs_btree_create_cursor_cache(XFS_BTNUM_REFC,
+			"xfs_refcountbt_cur",
+			xfs_refcountbt_absolute_maxlevels());
+}
+
 /* Compute the maximum height of a refcount btree. */
 void
 xfs_refcountbt_compute_maxlevels(
diff --git a/fs/xfs/libxfs/xfs_refcount_btree.h b/fs/xfs/libxfs/xfs_refcount_btree.h
index f5c0ef218b42..181faa16a085 100644
--- a/fs/xfs/libxfs/xfs_refcount_btree.h
+++ b/fs/xfs/libxfs/xfs_refcount_btree.h
@@ -66,4 +66,6 @@ extern int xfs_refcountbt_calc_reserves(struct xfs_mount *mp,
 void xfs_refcountbt_commit_staged_btree(struct xfs_btree_cur *cur,
 		struct xfs_trans *tp, struct xfs_buf *agbp);
 
+int __init xfs_refcountbt_create_cursor_cache(void);
+
 #endif	/* __XFS_REFCOUNT_BTREE_H__ */
diff --git a/fs/xfs/libxfs/xfs_rmap_btree.c b/fs/xfs/libxfs/xfs_rmap_btree.c
index ed2670158d6c..2349941f6b13 100644
--- a/fs/xfs/libxfs/xfs_rmap_btree.c
+++ b/fs/xfs/libxfs/xfs_rmap_btree.c
@@ -544,6 +544,38 @@ xfs_rmapbt_maxrecs(
 		(2 * sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t));
 }
 
+static inline __init unsigned int
+xfs_rmapbt_absolute_maxlevels(void)
+{
+	unsigned int		minrecs[2];
+
+	xfs_btree_absolute_minrecs(minrecs,
+			XFS_BTREE_CRC_BLOCKS | XFS_BTREE_OVERLAPPING,
+			sizeof(struct xfs_rmap_rec),
+			sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t));
+
+	/*
+	 * Compute the asymptotic maxlevels for an rmapbt on any reflink fs.
+	 *
+	 * On a reflink filesystem, each AG block can have up to 2^32 (per the
+	 * refcount record format) owners, which means that theoretically we
+	 * could face up to 2^64 rmap records.  However, we're likely to run
+	 * out of blocks in the AG long before that happens, which means that
+	 * we must compute the max height based on what the btree will look
+	 * like if it consumes almost all the blocks in the AG due to maximal
+	 * sharing factor.
+	 */
+	return xfs_btree_compute_maxlevels_size(XFS_MAX_CRC_AG_BLOCKS,
+			minrecs[1]);
+}
+
+int __init
+xfs_rmapbt_create_cursor_cache(void)
+{
+	return xfs_btree_create_cursor_cache(XFS_BTNUM_RMAP, "xfs_rmapbt_cur",
+			xfs_rmapbt_absolute_maxlevels());
+}
+
 /* Compute the maximum height of an rmap btree. */
 unsigned int
 xfs_rmapbt_compute_maxlevels(
diff --git a/fs/xfs/libxfs/xfs_rmap_btree.h b/fs/xfs/libxfs/xfs_rmap_btree.h
index d8c7253f1a7a..7ce953449f03 100644
--- a/fs/xfs/libxfs/xfs_rmap_btree.h
+++ b/fs/xfs/libxfs/xfs_rmap_btree.h
@@ -60,4 +60,6 @@ extern xfs_extlen_t xfs_rmapbt_max_size(struct xfs_mount *mp,
 extern int xfs_rmapbt_calc_reserves(struct xfs_mount *mp, struct xfs_trans *tp,
 		struct xfs_perag *pag, xfs_extlen_t *ask, xfs_extlen_t *used);
 
+int __init xfs_rmapbt_create_cursor_cache(void);
+
 #endif /* __XFS_RMAP_BTREE_H__ */
diff --git a/fs/xfs/libxfs/xfs_types.h b/fs/xfs/libxfs/xfs_types.h
index d0afc3d11e37..3a1874e6fd6a 100644
--- a/fs/xfs/libxfs/xfs_types.h
+++ b/fs/xfs/libxfs/xfs_types.h
@@ -126,6 +126,9 @@ typedef enum {
 	XFS_BTNUM_INOi, XFS_BTNUM_FINOi, XFS_BTNUM_REFCi, XFS_BTNUM_MAX
 } xfs_btnum_t;
 
+#define for_each_xfs_btnum(btnum) \
+	for((btnum) = XFS_BTNUM_BNOi; (btnum) < XFS_BTNUM_MAX; (btnum)++)
+
 #define XFS_BTNUM_STRINGS \
 	{ XFS_BTNUM_BNOi,	"bnobt" }, \
 	{ XFS_BTNUM_CNTi,	"cntbt" }, \
diff --git a/fs/xfs/xfs_super.c b/fs/xfs/xfs_super.c
index af8c5d06cc82..0b1c1960e6ce 100644
--- a/fs/xfs/xfs_super.c
+++ b/fs/xfs/xfs_super.c
@@ -38,6 +38,12 @@
 #include "xfs_pwork.h"
 #include "xfs_ag.h"
 #include "xfs_swapext_item.h"
+#include "xfs_btree.h"
+#include "xfs_alloc_btree.h"
+#include "xfs_ialloc_btree.h"
+#include "xfs_bmap_btree.h"
+#include "xfs_rmap_btree.h"
+#include "xfs_refcount_btree.h"
 
 #include <linux/magic.h>
 #include <linux/fs_context.h>
@@ -2007,8 +2013,34 @@ static struct file_system_type xfs_fs_type = {
 MODULE_ALIAS_FS("xfs");
 
 STATIC int __init
+xfs_init_btree_caches(void)
+{
+	int				error;
+
+	error = xfs_allocbt_create_cursor_cache();
+	if (error)
+		return error;
+	error = xfs_inobt_create_cursor_cache();
+	if (error)
+		return error;
+	error = xfs_bmbt_create_cursor_cache();
+	if (error)
+		return error;
+	error = xfs_rmapbt_create_cursor_cache();
+	if (error)
+		return error;
+	error = xfs_refcountbt_create_cursor_cache();
+	if (error)
+		return error;
+
+	return 0;
+}
+
+STATIC int __init
 xfs_init_zones(void)
 {
+	int			error;
+
 	xfs_log_ticket_zone = kmem_cache_create("xfs_log_ticket",
 						sizeof(struct xlog_ticket),
 						0, 0, NULL);
@@ -2021,6 +2053,10 @@ xfs_init_zones(void)
 	if (!xfs_bmap_free_item_zone)
 		goto out_destroy_log_ticket_zone;
 
+	error = xfs_init_btree_caches();
+	if (error)
+		goto out_destroy_bmap_free_item_zone;
+
 	xfs_btree_cur_zone = kmem_cache_create("xfs_btree_cur",
 			xfs_btree_cur_sizeof(XFS_BTREE_CUR_ZONE_MAXLEVELS),
 			0, 0, NULL);