From: "Darrick J. Wong" <darrick.wong@oracle.com>
To: sandeen@sandeen.net, darrick.wong@oracle.com
Cc: linux-xfs@vger.kernel.org
Subject: [PATCH 09/10] xfs_db: add a function to compute btree geometry
Date: Tue, 25 Jun 2019 19:37:46 -0700 [thread overview]
Message-ID: <156151666609.2286979.15035390055843235461.stgit@magnolia> (raw)
In-Reply-To: <156151660523.2286979.13694849827562044045.stgit@magnolia>
From: Darrick J. Wong <darrick.wong@oracle.com>
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 <darrick.wong@oracle.com>
---
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
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 <darrick.wong@oracle.com>
+ */
+#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
next prev parent reply other threads:[~2019-06-26 2:37 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-06-26 2:36 [PATCH v4 00/10] xfsprogs-5.1: fix various problems Darrick J. Wong
2019-06-26 2:36 ` [PATCH 01/10] libfrog: refactor online geometry queries Darrick J. Wong
2019-07-12 13:14 ` Eric Sandeen
2019-06-26 2:36 ` [PATCH 02/10] libfrog: introduce xfs_fd to wrap an fd to a file on an xfs filesystem Darrick J. Wong
2019-06-26 2:37 ` [PATCH 03/10] libfrog: store more inode and block geometry in struct xfs_fd Darrick J. Wong
2019-06-26 2:37 ` [PATCH 04/10] libfrog: create online fs geometry converters Darrick J. Wong
2019-06-26 2:37 ` [PATCH 05/10] libfrog: refactor open-coded bulkstat calls Darrick J. Wong
2019-06-26 2:37 ` [PATCH 06/10] libfrog: refactor open-coded INUMBERS calls Darrick J. Wong
2019-06-26 2:37 ` [PATCH 07/10] libxfs-diff: try harder to find the kernel equivalent libxfs files Darrick J. Wong
2019-06-26 2:37 ` [PATCH 08/10] xfs_db: remove db/convert.h Darrick J. Wong
2019-06-26 2:37 ` Darrick J. Wong [this message]
2019-06-26 2:37 ` [PATCH 10/10] libxfs: move topology declarations into separate header Darrick J. Wong
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=156151666609.2286979.15035390055843235461.stgit@magnolia \
--to=darrick.wong@oracle.com \
--cc=linux-xfs@vger.kernel.org \
--cc=sandeen@sandeen.net \
/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.