[09/10] xfs_db: add a function to compute btree geometry

Commit Message

Darrick J. Wong June 26, 2019, 2:37 a.m. UTC

From: Darrick J. Wong <[e-mail]>

Add a new command to xfs_db that uses a btree type and a record count
to report the best and worst case height and level size.  This can be
used to estimate how overhead a metadata index will add to a filesystem.

Signed-off-by: Darrick J. Wong <[e-mail]>
---
 db/Makefile              |    2 
 db/btheight.c            |  307 ++++++++++++++++++++++++++++++++++++++++++++++
 db/command.c             |    1 
 db/command.h             |    1 
 libxfs/libxfs_api_defs.h |    2 
 5 files changed, 312 insertions(+), 1 deletion(-)
 create mode 100644 db/btheight.c

Patch

diff --git a/db/Makefile b/db/Makefile
index 0941b32e..ed9f56c2 100644
--- a/db/Makefile
+++ b/db/Makefile
@@ -14,7 +14,7 @@  HFILES = addr.h agf.h agfl.h agi.h attr.h attrshort.h bit.h block.h bmap.h \
 	io.h logformat.h malloc.h metadump.h output.h print.h quit.h sb.h \
 	sig.h strvec.h text.h type.h write.h attrset.h symlink.h fsmap.h \
 	fuzz.h
-CFILES = $(HFILES:.h=.c) btdump.c convert.c info.c
+CFILES = $(HFILES:.h=.c) btdump.c btheight.c convert.c info.c
 LSRCFILES = xfs_admin.sh xfs_ncheck.sh xfs_metadump.sh
 
 LLDLIBS	= $(LIBXFS) $(LIBXLOG) $(LIBFROG) $(LIBUUID) $(LIBRT) $(LIBPTHREAD)
diff --git a/db/btheight.c b/db/btheight.c
new file mode 100644
index 00000000..84ce6af3
--- /dev/null
+++ b/db/btheight.c
@@ -0,0 +1,307 @@ 
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * Copyright (C) 2019 Oracle.  All Rights Reserved.
+ * Author: Darrick J. Wong <[e-mail]>
+ */
+#include "libxfs.h"
+#include "command.h"
+#include "output.h"
+#include "init.h"
+#include "io.h"
+#include "type.h"
+#include "input.h"
+#include "convert.h"
+
+static int refc_maxrecs(struct xfs_mount *mp, int blocklen, int leaf)
+{
+	return libxfs_refcountbt_maxrecs(blocklen, leaf != 0);
+}
+
+static int rmap_maxrecs(struct xfs_mount *mp, int blocklen, int leaf)
+{
+	return libxfs_rmapbt_maxrecs(blocklen, leaf);
+}
+
+struct btmap {
+	const char	*tag;
+	int		(*maxrecs)(struct xfs_mount *mp, int blocklen,
+				   int leaf);
+} maps[] = {
+	{"bnobt", libxfs_allocbt_maxrecs},
+	{"cntbt", libxfs_allocbt_maxrecs},
+	{"inobt", libxfs_inobt_maxrecs},
+	{"finobt", libxfs_inobt_maxrecs},
+	{"bmapbt", libxfs_bmbt_maxrecs},
+	{"refcountbt", refc_maxrecs},
+	{"rmapbt", rmap_maxrecs},
+};
+
+static void
+btheight_help(void)
+{
+	struct btmap	*m;
+	int		i;
+
+	dbprintf(_(
+"\n"
+" For a given number of btree records and a btree type, report the number of\n"
+" records and blocks for each level of the btree, and the total btree size.\n"
+" The btree type must be given after the options.  A raw btree geometry can\n"
+" be provided in the format \"record_bytes:key_bytes:ptr_bytes:header_type\"\n"
+" where header_type is one of \"short\", \"long\", \"shortcrc\", or \"longcrc\".\n"
+"\n"
+" Options:\n"
+"   -b -- Override the btree block size.\n"
+"   -n -- Number of records we want to store.\n"
+"   -w max -- Show only the best case scenario.\n"
+"   -w min -- Show only the worst case scenario.\n"
+"\n"
+" Supported btree types:\n"
+"   "
+));
+	for (i = 0, m = maps; i < ARRAY_SIZE(maps); i++, m++)
+		printf("%s ", m->tag);
+	printf("\n");
+}
+
+static void
+calc_height(
+	unsigned long long	nr_records,
+	uint			*records_per_block)
+{
+	unsigned int		level = 0;
+	unsigned long long	total_blocks = 0;
+	unsigned long long	blocks;
+	char			*levels_suffix = "s";
+	char			*totblocks_suffix = "s";
+
+	while (nr_records) {
+		unsigned int	level_rpb = records_per_block[level != 0];
+		char		*recs_suffix = "s";
+		char		*blocks_suffix = "s";
+
+		blocks = (nr_records + level_rpb - 1) / level_rpb;
+
+		if (nr_records == 1)
+			recs_suffix = "";
+		if (blocks == 1)
+			blocks_suffix = "";
+
+		printf(_("level %u: %llu record%s, %llu block%s\n"),
+				level, nr_records, recs_suffix, blocks,
+				blocks_suffix);
+
+		total_blocks += blocks;
+		nr_records = blocks == 1 ? 0 : blocks;
+		level++;
+	}
+
+	if (level == 1)
+		levels_suffix = "";
+	if (total_blocks == 1)
+		totblocks_suffix = "";
+
+	printf(_("%u level%s, %llu block%s total\n"), level, levels_suffix,
+			total_blocks, totblocks_suffix);
+}
+
+static int
+construct_records_per_block(
+	char		*tag,
+	int		blocksize,
+	unsigned int	*records_per_block)
+{
+	char		*toktag;
+	struct btmap	*m;
+	unsigned int	record_size, key_size, ptr_size;
+	char		*p;
+	int		i, ret;
+
+	for (i = 0, m = maps; i < ARRAY_SIZE(maps); i++, m++) {
+		if (!strcmp(m->tag, tag)) {
+			records_per_block[0] = m->maxrecs(mp, blocksize, 1);
+			records_per_block[1] = m->maxrecs(mp, blocksize, 0);
+			return 0;
+		}
+	}
+
+	toktag = strdup(tag);
+	ret = -1;
+
+	p = strtok(toktag, ":");
+	if (!p) {
+		fprintf(stderr, _("%s: record size not found.\n"), tag);
+		goto out;
+	}
+	record_size = cvt_u16(p, 0);
+	if (errno) {
+		perror(p);
+		goto out;
+	}
+
+	p = strtok(NULL, ":");
+	if (!p) {
+		fprintf(stderr, _("%s: key size not found.\n"), tag);
+		goto out;
+	}
+	key_size = cvt_u16(p, 0);
+	if (errno) {
+		perror(p);
+		goto out;
+	}
+
+	p = strtok(NULL, ":");
+	if (!p) {
+		fprintf(stderr, _("%s: pointer size not found.\n"), tag);
+		goto out;
+	}
+	ptr_size = cvt_u16(p, 0);
+	if (errno) {
+		perror(p);
+		goto out;
+	}
+
+	p = strtok(NULL, ":");
+	if (!p) {
+		fprintf(stderr, _("%s: header type not found.\n"), tag);
+		goto out;
+	}
+	if (!strcmp(p, "short"))
+		blocksize -= XFS_BTREE_SBLOCK_LEN;
+	else if (!strcmp(p, "shortcrc"))
+		blocksize -= XFS_BTREE_SBLOCK_CRC_LEN;
+	else if (!strcmp(p, "long"))
+		blocksize -= XFS_BTREE_LBLOCK_LEN;
+	else if (!strcmp(p, "longcrc"))
+		blocksize -= XFS_BTREE_LBLOCK_CRC_LEN;
+	else {
+		fprintf(stderr, _("%s: unrecognized btree header type."),
+				p);
+		goto out;
+	}
+
+	p = strtok(NULL, ":");
+	if (p) {
+		fprintf(stderr,
+			_("%s: unrecognized raw btree geometry."),
+				tag);
+		goto out;
+	}
+
+	records_per_block[0] = blocksize / record_size;
+	records_per_block[1] = blocksize / (key_size + ptr_size);
+	ret = 0;
+out:
+	free(toktag);
+	return ret;
+}
+
+#define REPORT_DEFAULT	(-1U)
+#define REPORT_MAX	(1 << 0)
+#define REPORT_MIN	(1 << 1)
+
+static void
+report(
+	char			*tag,
+	unsigned int		report_what,
+	unsigned long long	nr_records,
+	unsigned int		blocksize)
+{
+	unsigned int		records_per_block[2];
+	int			ret;
+
+	ret = construct_records_per_block(tag, blocksize, records_per_block);
+	if (ret) {
+		printf(_("%s: Unable to determine records per block.\n"),
+				tag);
+		return;
+	}
+
+	if (report_what & REPORT_MAX) {
+		printf(
+_("%s: best case per %u-byte block: %u records (leaf) / %u keyptrs (node)\n"),
+				tag, blocksize, records_per_block[0],
+				records_per_block[1]);
+
+		calc_height(nr_records, records_per_block);
+	}
+
+	if (report_what & REPORT_MIN) {
+		records_per_block[0] /= 2;
+		records_per_block[1] /= 2;
+
+		printf(
+_("%s: worst case per %u-byte block: %u records (leaf) / %u keyptrs (node)\n"),
+				tag, blocksize, records_per_block[0],
+				records_per_block[1]);
+
+		calc_height(nr_records, records_per_block);
+	}
+}
+
+static int
+btheight_f(
+	int		argc,
+	char		**argv)
+{
+	long long	blocksize = mp->m_sb.sb_blocksize;
+	uint64_t	nr_records = 0;
+	int		report_what = REPORT_DEFAULT;
+	int		i, c;
+
+	while ((c = getopt(argc, argv, "b:n:w:")) != -1) {
+		switch (c) {
+		case 'b':
+			errno = 0;
+			blocksize = cvtnum(mp->m_sb.sb_blocksize,
+					mp->m_sb.sb_sectsize,
+					optarg);
+			if (errno) {
+				perror(optarg);
+				return 0;
+			}
+			break;
+		case 'n':
+			nr_records = cvt_u64(optarg, 0);
+			if (errno) {
+				perror(optarg);
+				return 0;
+			}
+			break;
+		case 'w':
+			if (!strcmp(optarg, "min"))
+				report_what = REPORT_MIN;
+			else if (!strcmp(optarg, "max"))
+				report_what = REPORT_MAX;
+			else {
+				btheight_help();
+				return 0;
+			}
+			break;
+		default:
+			btheight_help();
+			return 0;
+		}
+	}
+
+	if (argc == optind || blocksize <= 0 || blocksize > INT_MAX ||
+	    nr_records == 0) {
+		btheight_help();
+		return 0;
+	}
+
+	for (i = optind; i < argc; i++)
+		report(argv[i], report_what, nr_records, blocksize);
+
+	return 0;
+}
+
+static const cmdinfo_t btheight_cmd =
+	{ "btheight", "b", btheight_f, 1, -1, 0, "[-a] [-i]",
+	  N_("compute btree heights"), btheight_help };
+
+void
+btheight_init(void)
+{
+	add_command(&btheight_cmd);
+}
diff --git a/db/command.c b/db/command.c
index 89a78f03..0fb44efa 100644
--- a/db/command.c
+++ b/db/command.c
@@ -113,6 +113,7 @@  init_commands(void)
 	block_init();
 	bmap_init();
 	btdump_init();
+	btheight_init();
 	check_init();
 	convert_init();
 	crc_init();
diff --git a/db/command.h b/db/command.h
index 2f9a7e16..b8499de0 100644
--- a/db/command.h
+++ b/db/command.h
@@ -31,3 +31,4 @@  extern void		init_commands(void);
 extern void		convert_init(void);
 extern void		btdump_init(void);
 extern void		info_init(void);
+extern void		btheight_init(void);
diff --git a/libxfs/libxfs_api_defs.h b/libxfs/libxfs_api_defs.h
index 71a7ef53..fff160ef 100644
--- a/libxfs/libxfs_api_defs.h
+++ b/libxfs/libxfs_api_defs.h
@@ -124,6 +124,8 @@ 
 #define xfs_dir_ino_validate		libxfs_dir_ino_validate
 #define xfs_initialize_perag_data	libxfs_initialize_perag_data
 #define xfs_inobt_maxrecs		libxfs_inobt_maxrecs
+#define xfs_rmapbt_maxrecs		libxfs_rmapbt_maxrecs
+#define xfs_refcountbt_maxrecs		libxfs_refcountbt_maxrecs
 #define xfs_iread_extents		libxfs_iread_extents
 #define xfs_log_calc_minimum_size	libxfs_log_calc_minimum_size
 #define xfs_perag_get			libxfs_perag_get