db/btheight.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Copyright (C) 2019 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <darrick.wong@oracle.com>
   5  */
   6 #include "libxfs.h"
   7 #include "command.h"
   8 #include "output.h"
   9 #include "init.h"
  10 #include "io.h"
  11 #include "type.h"
  12 #include "input.h"
  13 #include "libfrog/convert.h"
  14
  15 static int refc_maxrecs(struct xfs_mount *mp, int blocklen, int leaf)
  16 {
  17         return libxfs_refcountbt_maxrecs(blocklen, leaf != 0);
  18 }
  19
  20 static int rmap_maxrecs(struct xfs_mount *mp, int blocklen, int leaf)
  21 {
  22         return libxfs_rmapbt_maxrecs(blocklen, leaf);
  23 }
  24
  25 struct btmap {
  26         const char      *tag;
  27         unsigned int    (*maxlevels)(void);
  28         int             (*maxrecs)(struct xfs_mount *mp, int blocklen,
  29                                    int leaf);
  30 } maps[] = {
  31         {
  32                 .tag            = "bnobt",
  33                 .maxlevels      = libxfs_allocbt_maxlevels_ondisk,
  34                 .maxrecs        = libxfs_allocbt_maxrecs,
  35         },
  36         {
  37                 .tag            = "cntbt",
  38                 .maxlevels      = libxfs_allocbt_maxlevels_ondisk,
  39                 .maxrecs        = libxfs_allocbt_maxrecs,
  40         },
  41         {
  42                 .tag            = "inobt",
  43                 .maxlevels      = libxfs_iallocbt_maxlevels_ondisk,
  44                 .maxrecs        = libxfs_inobt_maxrecs,
  45         },
  46         {
  47                 .tag            = "finobt",
  48                 .maxlevels      = libxfs_iallocbt_maxlevels_ondisk,
  49                 .maxrecs        = libxfs_inobt_maxrecs,
  50         },
  51         {
  52                 .tag            = "bmapbt",
  53                 .maxlevels      = libxfs_bmbt_maxlevels_ondisk,
  54                 .maxrecs        = libxfs_bmbt_maxrecs,
  55         },
  56         {
  57                 .tag            = "refcountbt",
  58                 .maxlevels      = libxfs_refcountbt_maxlevels_ondisk,
  59                 .maxrecs        = refc_maxrecs,
  60         },
  61         {
  62                 .tag            = "rmapbt",
  63                 .maxlevels      = libxfs_rmapbt_maxlevels_ondisk,
  64                 .maxrecs        = rmap_maxrecs,
  65         },
  66 };
  67
  68 static void
  69 btheight_help(void)
  70 {
  71         struct btmap    *m;
  72         int             i;
  73
  74         dbprintf(_(
  75 "\n"
  76 " For a given number of btree records and a btree type, report the number of\n"
  77 " records and blocks for each level of the btree, and the total btree size.\n"
  78 " The btree type must be given after the options.  A raw btree geometry can\n"
  79 " be provided in the format \"record_bytes:key_bytes:ptr_bytes:header_type\"\n"
  80 " where header_type is one of \"short\", \"long\", \"shortcrc\", or \"longcrc\".\n"
  81 "\n"
  82 " Options:\n"
  83 "   -b -- Override the btree block size.\n"
  84 "   -n -- Number of records we want to store.\n"
  85 "   -w max -- Show only the best case scenario.\n"
  86 "   -w min -- Show only the worst case scenario.\n"
  87 "   -w absmax -- Print the maximum possible btree height for all filesystems.\n"
  88 "\n"
  89 " Supported btree types:\n"
  90 "   all "
  91 ));
  92         for (i = 0, m = maps; i < ARRAY_SIZE(maps); i++, m++)
  93                 printf("%s ", m->tag);
  94         printf("\n");
  95 }
  96
  97 static void
  98 calc_height(
  99         unsigned long long      nr_records,
 100         uint                    *records_per_block)
 101 {
 102         unsigned int            level = 0;
 103         unsigned long long      total_blocks = 0;
 104         unsigned long long      blocks;
 105         char                    *levels_suffix = "s";
 106         char                    *totblocks_suffix = "s";
 107
 108         while (nr_records) {
 109                 unsigned int    level_rpb = records_per_block[level != 0];
 110                 char            *recs_suffix = "s";
 111                 char            *blocks_suffix = "s";
 112
 113                 blocks = (nr_records + level_rpb - 1) / level_rpb;
 114
 115                 if (nr_records == 1)
 116                         recs_suffix = "";
 117                 if (blocks == 1)
 118                         blocks_suffix = "";
 119
 120                 printf(_("level %u: %llu record%s, %llu block%s\n"),
 121                                 level, nr_records, recs_suffix, blocks,
 122                                 blocks_suffix);
 123
 124                 total_blocks += blocks;
 125                 nr_records = blocks == 1 ? 0 : blocks;
 126                 level++;
 127         }
 128
 129         if (level == 1)
 130                 levels_suffix = "";
 131         if (total_blocks == 1)
 132                 totblocks_suffix = "";
 133
 134         printf(_("%u level%s, %llu block%s total\n"), level, levels_suffix,
 135                         total_blocks, totblocks_suffix);
 136 }
 137
 138 static int
 139 construct_records_per_block(
 140         const char      *tag,
 141         int             blocksize,
 142         unsigned int    *records_per_block)
 143 {
 144         char            *toktag;
 145         struct btmap    *m;
 146         unsigned int    record_size, key_size, ptr_size;
 147         char            *p;
 148         int             i, ret;
 149
 150         for (i = 0, m = maps; i < ARRAY_SIZE(maps); i++, m++) {
 151                 if (!strcmp(m->tag, tag)) {
 152                         records_per_block[0] = m->maxrecs(mp, blocksize, 1);
 153                         records_per_block[1] = m->maxrecs(mp, blocksize, 0);
 154                         return 0;
 155                 }
 156         }
 157
 158         toktag = strdup(tag);
 159         ret = -1;
 160
 161         p = strtok(toktag, ":");
 162         if (!p) {
 163                 fprintf(stderr, _("%s: record size not found.\n"), tag);
 164                 goto out;
 165         }
 166         record_size = cvt_u16(p, 0);
 167         if (errno) {
 168                 perror(p);
 169                 goto out;
 170         }
 171         if (record_size == 0) {
 172                 fprintf(stderr, _("%s: record size cannot be zero.\n"), tag);
 173                 goto out;
 174         }
 175
 176         p = strtok(NULL, ":");
 177         if (!p) {
 178                 fprintf(stderr, _("%s: key size not found.\n"), tag);
 179                 goto out;
 180         }
 181         key_size = cvt_u16(p, 0);
 182         if (errno) {
 183                 perror(p);
 184                 goto out;
 185         }
 186         if (key_size == 0) {
 187                 fprintf(stderr, _("%s: key size cannot be zero.\n"), tag);
 188                 goto out;
 189         }
 190
 191         p = strtok(NULL, ":");
 192         if (!p) {
 193                 fprintf(stderr, _("%s: pointer size not found.\n"), tag);
 194                 goto out;
 195         }
 196         ptr_size = cvt_u16(p, 0);
 197         if (errno) {
 198                 perror(p);
 199                 goto out;
 200         }
 201         if (ptr_size == 0) {
 202                 fprintf(stderr, _("%s: pointer size cannot be zero.\n"), tag);
 203                 goto out;
 204         }
 205
 206         p = strtok(NULL, ":");
 207         if (!p) {
 208                 fprintf(stderr, _("%s: header type not found.\n"), tag);
 209                 goto out;
 210         }
 211         if (!strcmp(p, "short"))
 212                 blocksize -= XFS_BTREE_SBLOCK_LEN;
 213         else if (!strcmp(p, "shortcrc"))
 214                 blocksize -= XFS_BTREE_SBLOCK_CRC_LEN;
 215         else if (!strcmp(p, "long"))
 216                 blocksize -= XFS_BTREE_LBLOCK_LEN;
 217         else if (!strcmp(p, "longcrc"))
 218                 blocksize -= XFS_BTREE_LBLOCK_CRC_LEN;
 219         else {
 220                 fprintf(stderr, _("%s: unrecognized btree header type."),
 221                                 p);
 222                 goto out;
 223         }
 224
 225         if (record_size > blocksize) {
 226                 fprintf(stderr,
 227 _("%s: record size must be less than selected block size (%u bytes).\n"),
 228                         tag, blocksize);
 229                 goto out;
 230         }
 231
 232         if (key_size > blocksize) {
 233                 fprintf(stderr,
 234 _("%s: key size must be less than selected block size (%u bytes).\n"),
 235                         tag, blocksize);
 236                 goto out;
 237         }
 238
 239         if (ptr_size > blocksize) {
 240                 fprintf(stderr,
 241 _("%s: pointer size must be less than selected block size (%u bytes).\n"),
 242                         tag, blocksize);
 243                 goto out;
 244         }
 245
 246         p = strtok(NULL, ":");
 247         if (p) {
 248                 fprintf(stderr,
 249                         _("%s: unrecognized raw btree geometry."),
 250                                 tag);
 251                 goto out;
 252         }
 253
 254         records_per_block[0] = blocksize / record_size;
 255         records_per_block[1] = blocksize / (key_size + ptr_size);
 256         ret = 0;
 257 out:
 258         free(toktag);
 259         return ret;
 260 }
 261
 262 #define REPORT_DEFAULT  (-1U)
 263 #define REPORT_MAX      (1 << 0)
 264 #define REPORT_MIN      (1 << 1)
 265 #define REPORT_ABSMAX   (1 << 2)
 266
 267 static void
 268 report_absmax(const char *tag)
 269 {
 270         struct btmap    *m;
 271         int             i;
 272
 273         for (i = 0, m = maps; i < ARRAY_SIZE(maps); i++, m++) {
 274                 if (!strcmp(m->tag, tag)) {
 275                         printf("%s: %u\n", tag, m->maxlevels());
 276                         return;
 277                 }
 278         }
 279         printf(_("%s: Don't know how to report max height.\n"), tag);
 280 }
 281
 282 static void
 283 report(
 284         const char              *tag,
 285         unsigned int            report_what,
 286         unsigned long long      nr_records,
 287         unsigned int            blocksize)
 288 {
 289         unsigned int            records_per_block[2];
 290         int                     ret;
 291
 292         if (report_what == REPORT_ABSMAX) {
 293                 report_absmax(tag);
 294                 return;
 295         }
 296
 297         ret = construct_records_per_block(tag, blocksize, records_per_block);
 298         if (ret)
 299                 return;
 300
 301         if (report_what & REPORT_MAX) {
 302                 if (records_per_block[0] < 2) {
 303                         fprintf(stderr,
 304 _("%s: cannot calculate best case scenario due to leaf geometry underflow.\n"),
 305                                 tag);
 306                         return;
 307                 }
 308
 309                 if (records_per_block[1] < 4) {
 310                         fprintf(stderr,
 311 _("%s: cannot calculate best case scenario due to node geometry underflow.\n"),
 312                                 tag);
 313                         return;
 314                 }
 315
 316                 printf(
 317 _("%s: best case per %u-byte block: %u records (leaf) / %u keyptrs (node)\n"),
 318                                 tag, blocksize, records_per_block[0],
 319                                 records_per_block[1]);
 320
 321                 calc_height(nr_records, records_per_block);
 322         }
 323
 324         if (report_what & REPORT_MIN) {
 325                 records_per_block[0] /= 2;
 326                 records_per_block[1] /= 2;
 327
 328                 if (records_per_block[0] < 1) {
 329                         fprintf(stderr,
 330 _("%s: cannot calculate worst case scenario due to leaf geometry underflow.\n"),
 331                                 tag);
 332                         return;
 333                 }
 334
 335                 if (records_per_block[1] < 2) {
 336                         fprintf(stderr,
 337 _("%s: cannot calculate worst case scenario due to node geometry underflow.\n"),
 338                                 tag);
 339                         return;
 340                 }
 341
 342                 printf(
 343 _("%s: worst case per %u-byte block: %u records (leaf) / %u keyptrs (node)\n"),
 344                                 tag, blocksize, records_per_block[0],
 345                                 records_per_block[1]);
 346
 347                 calc_height(nr_records, records_per_block);
 348         }
 349 }
 350
 351 static void
 352 report_all(
 353         unsigned int            report_what,
 354         unsigned long long      nr_records,
 355         unsigned int            blocksize)
 356 {
 357         struct btmap            *m;
 358         int                     i;
 359
 360         for (i = 0, m = maps; i < ARRAY_SIZE(maps); i++, m++)
 361                 report(m->tag, report_what, nr_records, blocksize);
 362 }
 363
 364 static int
 365 btheight_f(
 366         int             argc,
 367         char            **argv)
 368 {
 369         long long       blocksize = mp->m_sb.sb_blocksize;
 370         uint64_t        nr_records = 0;
 371         int             report_what = REPORT_DEFAULT;
 372         int             i, c;
 373
 374         while ((c = getopt(argc, argv, "b:n:w:")) != -1) {
 375                 switch (c) {
 376                 case 'b':
 377                         errno = 0;
 378                         blocksize = cvtnum(mp->m_sb.sb_blocksize,
 379                                         mp->m_sb.sb_sectsize,
 380                                         optarg);
 381                         if (errno) {
 382                                 perror(optarg);
 383                                 return 0;
 384                         }
 385                         break;
 386                 case 'n':
 387                         nr_records = cvt_u64(optarg, 0);
 388                         if (errno) {
 389                                 perror(optarg);
 390                                 return 0;
 391                         }
 392                         break;
 393                 case 'w':
 394                         if (!strcmp(optarg, "min"))
 395                                 report_what = REPORT_MIN;
 396                         else if (!strcmp(optarg, "max"))
 397                                 report_what = REPORT_MAX;
 398                         else if (!strcmp(optarg, "absmax"))
 399                                 report_what = REPORT_ABSMAX;
 400                         else {
 401                                 btheight_help();
 402                                 return 0;
 403                         }
 404                         break;
 405                 default:
 406                         btheight_help();
 407                         return 0;
 408                 }
 409         }
 410
 411         if (report_what != REPORT_ABSMAX && nr_records == 0) {
 412                 fprintf(stderr,
 413 _("Number of records must be greater than zero.\n"));
 414                 return 0;
 415         }
 416
 417         if (report_what != REPORT_ABSMAX && blocksize > INT_MAX) {
 418                 fprintf(stderr,
 419 _("The largest block size this command will consider is %u bytes.\n"),
 420                         INT_MAX);
 421                 return 0;
 422         }
 423
 424         if (report_what != REPORT_ABSMAX && blocksize < 128) {
 425                 fprintf(stderr,
 426 _("The smallest block size this command will consider is 128 bytes.\n"));
 427                 return 0;
 428         }
 429
 430         if (argc == optind) {
 431                 btheight_help();
 432                 return 0;
 433         }
 434
 435         for (i = optind; i < argc; i++) {
 436                 if (!strcmp(argv[i], "all")) {
 437                         report_all(report_what, nr_records, blocksize);
 438                         return 0;
 439                 }
 440         }
 441
 442         for (i = optind; i < argc; i++)
 443                 report(argv[i], report_what, nr_records, blocksize);
 444
 445         return 0;
 446 }
 447
 448 static const cmdinfo_t btheight_cmd =
 449         { "btheight", "b", btheight_f, 1, -1, 0,
 450           "[-b blksz] [-n recs] [-w max|-w min] btree types...",
 451           N_("compute btree heights"), btheight_help };
 452
 453 void
 454 btheight_init(void)
 455 {
 456         add_command(&btheight_cmd);
 457 }