db/frag.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
   4  * All Rights Reserved.
   5  */
   6
   7 #include "libxfs.h"
   8 #include <sys/time.h>
   9 #include "bmap.h"
  10 #include "command.h"
  11 #include "frag.h"
  12 #include "io.h"
  13 #include "output.h"
  14 #include "type.h"
  15 #include "init.h"
  16 #include "malloc.h"
  17
  18 typedef struct extent {
  19         xfs_fileoff_t   startoff;
  20         xfs_filblks_t   blockcount;
  21 } extent_t;
  22
  23 typedef struct extmap {
  24         int             naents;
  25         int             nents;
  26         extent_t        ents[1];
  27 } extmap_t;
  28 #define EXTMAP_SIZE(n)  \
  29         (offsetof(extmap_t, ents) + (sizeof(extent_t) * (n)))
  30
  31 static int              aflag;
  32 static int              dflag;
  33 static uint64_t extcount_actual;
  34 static uint64_t extcount_ideal;
  35 static int              fflag;
  36 static int              lflag;
  37 static int              qflag;
  38 static int              Rflag;
  39 static int              rflag;
  40 static int              vflag;
  41
  42 typedef void    (*scan_lbtree_f_t)(struct xfs_btree_block *block,
  43                                    int                  level,
  44                                    extmap_t             **extmapp,
  45                                    typnm_t              btype);
  46
  47 typedef void    (*scan_sbtree_f_t)(struct xfs_btree_block *block,
  48                                    int                  level,
  49                                    xfs_agf_t            *agf);
  50
  51 static extmap_t         *extmap_alloc(xfs_extnum_t nex);
  52 static xfs_extnum_t     extmap_ideal(extmap_t *extmap);
  53 static void             extmap_set_ext(extmap_t **extmapp, xfs_fileoff_t o,
  54                                        xfs_extlen_t c);
  55 static int              frag_f(int argc, char **argv);
  56 static int              init(int argc, char **argv);
  57 static void             process_bmbt_reclist(xfs_bmbt_rec_t *rp, int numrecs,
  58                                              extmap_t **extmapp);
  59 static void             process_btinode(xfs_dinode_t *dip, extmap_t **extmapp,
  60                                         int whichfork);
  61 static void             process_exinode(xfs_dinode_t *dip, extmap_t **extmapp,
  62                                         int whichfork);
  63 static void             process_fork(xfs_dinode_t *dip, int whichfork);
  64 static void             process_inode(xfs_agf_t *agf, xfs_agino_t agino,
  65                                       xfs_dinode_t *dip);
  66 static void             scan_ag(xfs_agnumber_t agno);
  67 static void             scan_lbtree(xfs_fsblock_t root, int nlevels,
  68                                     scan_lbtree_f_t func, extmap_t **extmapp,
  69                                     typnm_t btype);
  70 static void             scan_sbtree(xfs_agf_t *agf, xfs_agblock_t root,
  71                                     int nlevels, scan_sbtree_f_t func,
  72                                     typnm_t btype);
  73 static void             scanfunc_bmap(struct xfs_btree_block *block, int level,
  74                                       extmap_t **extmapp, typnm_t btype);
  75 static void             scanfunc_ino(struct xfs_btree_block *block, int level,
  76                                      xfs_agf_t *agf);
  77
  78 static const cmdinfo_t  frag_cmd =
  79         { "frag", NULL, frag_f, 0, -1, 0,
  80           "[-a] [-d] [-f] [-l] [-q] [-R] [-r] [-v]",
  81           "get file fragmentation data", NULL };
  82
  83 static extmap_t *
  84 extmap_alloc(
  85         xfs_extnum_t    nex)
  86 {
  87         extmap_t        *extmap;
  88
  89         if (nex < 1)
  90                 nex = 1;
  91         extmap = xmalloc(EXTMAP_SIZE(nex));
  92         extmap->naents = nex;
  93         extmap->nents = 0;
  94         return extmap;
  95 }
  96
  97 static xfs_extnum_t
  98 extmap_ideal(
  99         extmap_t        *extmap)
 100 {
 101         extent_t        *ep;
 102         xfs_extnum_t    rval;
 103
 104         for (ep = &extmap->ents[0], rval = 0;
 105              ep < &extmap->ents[extmap->nents];
 106              ep++) {
 107                 if (ep == &extmap->ents[0] ||
 108                     ep->startoff != ep[-1].startoff + ep[-1].blockcount)
 109                         rval++;
 110         }
 111         return rval;
 112 }
 113
 114 static void
 115 extmap_set_ext(
 116         extmap_t        **extmapp,
 117         xfs_fileoff_t   o,
 118         xfs_extlen_t    c)
 119 {
 120         extmap_t        *extmap;
 121         extent_t        *ent;
 122
 123         extmap = *extmapp;
 124         if (extmap->nents == extmap->naents) {
 125                 extmap->naents++;
 126                 extmap = xrealloc(extmap, EXTMAP_SIZE(extmap->naents));
 127                 *extmapp = extmap;
 128         }
 129         ent = &extmap->ents[extmap->nents];
 130         ent->startoff = o;
 131         ent->blockcount = c;
 132         extmap->nents++;
 133 }
 134
 135 void
 136 frag_init(void)
 137 {
 138         add_command(&frag_cmd);
 139 }
 140
 141 /*
 142  * Get file fragmentation information.
 143  */
 144 static int
 145 frag_f(
 146         int             argc,
 147         char            **argv)
 148 {
 149         xfs_agnumber_t  agno;
 150         double          answer;
 151
 152         if (!init(argc, argv))
 153                 return 0;
 154         for (agno = 0; agno < mp->m_sb.sb_agcount; agno++)
 155                 scan_ag(agno);
 156         if (extcount_actual)
 157                 answer = (double)(extcount_actual - extcount_ideal) * 100.0 /
 158                          (double)extcount_actual;
 159         else
 160                 answer = 0.0;
 161         dbprintf(_("actual %llu, ideal %llu, fragmentation factor %.2f%%\n"),
 162                 extcount_actual, extcount_ideal, answer);
 163         dbprintf(_("Note, this number is largely meaningless.\n"));
 164         answer = (double)extcount_actual / (double)extcount_ideal;
 165         dbprintf(_("Files on this filesystem average %.2f extents per file\n"),
 166                 answer);
 167         return 0;
 168 }
 169
 170 static int
 171 init(
 172         int             argc,
 173         char            **argv)
 174 {
 175         int             c;
 176
 177         aflag = dflag = fflag = lflag = qflag = Rflag = rflag = vflag = 0;
 178         optind = 0;
 179         while ((c = getopt(argc, argv, "adflqRrv")) != EOF) {
 180                 switch (c) {
 181                 case 'a':
 182                         aflag = 1;
 183                         break;
 184                 case 'd':
 185                         dflag = 1;
 186                         break;
 187                 case 'f':
 188                         fflag = 1;
 189                         break;
 190                 case 'l':
 191                         lflag = 1;
 192                         break;
 193                 case 'q':
 194                         qflag = 1;
 195                         break;
 196                 case 'R':
 197                         Rflag = 1;
 198                         break;
 199                 case 'r':
 200                         rflag = 1;
 201                         break;
 202                 case 'v':
 203                         vflag = 1;
 204                         break;
 205                 default:
 206                         dbprintf(_("bad option for frag command\n"));
 207                         return 0;
 208                 }
 209         }
 210         if (!aflag && !dflag && !fflag && !lflag && !qflag && !Rflag && !rflag)
 211                 aflag = dflag = fflag = lflag = qflag = Rflag = rflag = 1;
 212         extcount_actual = extcount_ideal = 0;
 213         return 1;
 214 }
 215
 216 static void
 217 process_bmbt_reclist(
 218         xfs_bmbt_rec_t          *rp,
 219         int                     numrecs,
 220         extmap_t                **extmapp)
 221 {
 222         xfs_filblks_t           c;
 223         int                     f;
 224         int                     i;
 225         xfs_fileoff_t           o;
 226         xfs_fsblock_t           s;
 227
 228         for (i = 0; i < numrecs; i++, rp++) {
 229                 convert_extent(rp, &o, &s, &c, &f);
 230                 extmap_set_ext(extmapp, (xfs_fileoff_t)o, (xfs_extlen_t)c);
 231         }
 232 }
 233
 234 static void
 235 process_btinode(
 236         xfs_dinode_t            *dip,
 237         extmap_t                **extmapp,
 238         int                     whichfork)
 239 {
 240         xfs_bmdr_block_t        *dib;
 241         int                     i;
 242         xfs_bmbt_ptr_t          *pp;
 243
 244         dib = (xfs_bmdr_block_t *)XFS_DFORK_PTR(dip, whichfork);
 245         if (be16_to_cpu(dib->bb_level) == 0) {
 246                 xfs_bmbt_rec_t          *rp = XFS_BMDR_REC_ADDR(dib, 1);
 247                 process_bmbt_reclist(rp, be16_to_cpu(dib->bb_numrecs), extmapp);
 248                 return;
 249         }
 250         pp = XFS_BMDR_PTR_ADDR(dib, 1,
 251                 libxfs_bmdr_maxrecs(XFS_DFORK_SIZE(dip, mp, whichfork), 0));
 252         for (i = 0; i < be16_to_cpu(dib->bb_numrecs); i++)
 253                 scan_lbtree(get_unaligned_be64(&pp[i]),
 254                          be16_to_cpu(dib->bb_level), scanfunc_bmap, extmapp,
 255                         whichfork == XFS_DATA_FORK ? TYP_BMAPBTD : TYP_BMAPBTA);
 256 }
 257
 258 static void
 259 process_exinode(
 260         xfs_dinode_t            *dip,
 261         extmap_t                **extmapp,
 262         int                     whichfork)
 263 {
 264         xfs_bmbt_rec_t          *rp;
 265
 266         rp = (xfs_bmbt_rec_t *)XFS_DFORK_PTR(dip, whichfork);
 267         process_bmbt_reclist(rp, XFS_DFORK_NEXTENTS(dip, whichfork), extmapp);
 268 }
 269
 270 static void
 271 process_fork(
 272         xfs_dinode_t    *dip,
 273         int             whichfork)
 274 {
 275         extmap_t        *extmap;
 276         int             nex;
 277
 278         nex = XFS_DFORK_NEXTENTS(dip, whichfork);
 279         if (!nex)
 280                 return;
 281         extmap = extmap_alloc(nex);
 282         switch (XFS_DFORK_FORMAT(dip, whichfork)) {
 283         case XFS_DINODE_FMT_EXTENTS:
 284                 process_exinode(dip, &extmap, whichfork);
 285                 break;
 286         case XFS_DINODE_FMT_BTREE:
 287                 process_btinode(dip, &extmap, whichfork);
 288                 break;
 289         }
 290         extcount_actual += extmap->nents;
 291         extcount_ideal += extmap_ideal(extmap);
 292         xfree(extmap);
 293 }
 294
 295 static void
 296 process_inode(
 297         xfs_agf_t               *agf,
 298         xfs_agino_t             agino,
 299         xfs_dinode_t            *dip)
 300 {
 301         uint64_t                actual;
 302         uint64_t                ideal;
 303         xfs_ino_t               ino;
 304         int                     skipa;
 305         int                     skipd;
 306
 307         ino = XFS_AGINO_TO_INO(mp, be32_to_cpu(agf->agf_seqno), agino);
 308         switch (be16_to_cpu(dip->di_mode) & S_IFMT) {
 309         case S_IFDIR:
 310                 skipd = !dflag;
 311                 break;
 312         case S_IFREG:
 313                 if (!rflag && (be16_to_cpu(dip->di_flags) & XFS_DIFLAG_REALTIME))
 314                         skipd = 1;
 315                 else if (!Rflag &&
 316                          (ino == mp->m_sb.sb_rbmino ||
 317                           ino == mp->m_sb.sb_rsumino))
 318                         skipd = 1;
 319                 else if (!qflag &&
 320                          (ino == mp->m_sb.sb_uquotino ||
 321                           ino == mp->m_sb.sb_gquotino ||
 322                           ino == mp->m_sb.sb_pquotino))
 323                         skipd = 1;
 324                 else
 325                         skipd = !fflag;
 326                 break;
 327         case S_IFLNK:
 328                 skipd = !lflag;
 329                 break;
 330         default:
 331                 skipd = 1;
 332                 break;
 333         }
 334         actual = extcount_actual;
 335         ideal = extcount_ideal;
 336         if (!skipd)
 337                 process_fork(dip, XFS_DATA_FORK);
 338         skipa = !aflag || !XFS_DFORK_Q(dip);
 339         if (!skipa)
 340                 process_fork(dip, XFS_ATTR_FORK);
 341         if (vflag && (!skipd || !skipa))
 342                 dbprintf(_("inode %lld actual %lld ideal %lld\n"),
 343                         ino, extcount_actual - actual, extcount_ideal - ideal);
 344 }
 345
 346 static void
 347 scan_ag(
 348         xfs_agnumber_t  agno)
 349 {
 350         xfs_agf_t       *agf;
 351         xfs_agi_t       *agi;
 352
 353         push_cur();
 354         set_cur(&typtab[TYP_AGF],
 355                 XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
 356                 XFS_FSS_TO_BB(mp, 1), DB_RING_IGN, NULL);
 357         if ((agf = iocur_top->data) == NULL) {
 358                 dbprintf(_("can't read agf block for ag %u\n"), agno);
 359                 pop_cur();
 360                 return;
 361         }
 362         push_cur();
 363         set_cur(&typtab[TYP_AGI],
 364                 XFS_AG_DADDR(mp, agno, XFS_AGI_DADDR(mp)),
 365                 XFS_FSS_TO_BB(mp, 1), DB_RING_IGN, NULL);
 366         if ((agi = iocur_top->data) == NULL) {
 367                 dbprintf(_("can't read agi block for ag %u\n"), agno);
 368                 pop_cur();
 369                 pop_cur();
 370                 return;
 371         }
 372         scan_sbtree(agf, be32_to_cpu(agi->agi_root),
 373                         be32_to_cpu(agi->agi_level), scanfunc_ino, TYP_INOBT);
 374         pop_cur();
 375         pop_cur();
 376 }
 377
 378 static void
 379 scan_lbtree(
 380         xfs_fsblock_t   root,
 381         int             nlevels,
 382         scan_lbtree_f_t func,
 383         extmap_t        **extmapp,
 384         typnm_t         btype)
 385 {
 386         push_cur();
 387         set_cur(&typtab[btype], XFS_FSB_TO_DADDR(mp, root), blkbb, DB_RING_IGN,
 388                 NULL);
 389         if (iocur_top->data == NULL) {
 390                 dbprintf(_("can't read btree block %u/%u\n"),
 391                         XFS_FSB_TO_AGNO(mp, root),
 392                         XFS_FSB_TO_AGBNO(mp, root));
 393                 return;
 394         }
 395         (*func)(iocur_top->data, nlevels - 1, extmapp, btype);
 396         pop_cur();
 397 }
 398
 399 static void
 400 scan_sbtree(
 401         xfs_agf_t       *agf,
 402         xfs_agblock_t   root,
 403         int             nlevels,
 404         scan_sbtree_f_t func,
 405         typnm_t         btype)
 406 {
 407         xfs_agnumber_t  seqno = be32_to_cpu(agf->agf_seqno);
 408
 409         push_cur();
 410         set_cur(&typtab[btype], XFS_AGB_TO_DADDR(mp, seqno, root),
 411                 blkbb, DB_RING_IGN, NULL);
 412         if (iocur_top->data == NULL) {
 413                 dbprintf(_("can't read btree block %u/%u\n"), seqno, root);
 414                 return;
 415         }
 416         (*func)(iocur_top->data, nlevels - 1, agf);
 417         pop_cur();
 418 }
 419
 420 static void
 421 scanfunc_bmap(
 422         struct xfs_btree_block  *block,
 423         int                     level,
 424         extmap_t                **extmapp,
 425         typnm_t                 btype)
 426 {
 427         int                     i;
 428         xfs_bmbt_ptr_t          *pp;
 429         xfs_bmbt_rec_t          *rp;
 430         int                     nrecs;
 431
 432         nrecs = be16_to_cpu(block->bb_numrecs);
 433
 434         if (level == 0) {
 435                 if (nrecs > mp->m_bmap_dmxr[0]) {
 436                         dbprintf(_("invalid numrecs (%u) in %s block\n"),
 437                                    nrecs, typtab[btype].name);
 438                         return;
 439                 }
 440                 rp = XFS_BMBT_REC_ADDR(mp, block, 1);
 441                 process_bmbt_reclist(rp, nrecs, extmapp);
 442                 return;
 443         }
 444
 445         if (nrecs > mp->m_bmap_dmxr[1]) {
 446                 dbprintf(_("invalid numrecs (%u) in %s block\n"),
 447                            nrecs, typtab[btype].name);
 448                 return;
 449         }
 450         pp = XFS_BMBT_PTR_ADDR(mp, block, 1, mp->m_bmap_dmxr[0]);
 451         for (i = 0; i < nrecs; i++)
 452                 scan_lbtree(be64_to_cpu(pp[i]), level, scanfunc_bmap, extmapp,
 453                                                                         btype);
 454 }
 455
 456 static void
 457 scanfunc_ino(
 458         struct xfs_btree_block  *block,
 459         int                     level,
 460         xfs_agf_t               *agf)
 461 {
 462         xfs_agino_t             agino;
 463         xfs_agnumber_t          seqno = be32_to_cpu(agf->agf_seqno);
 464         int                     i;
 465         int                     j;
 466         int                     off;
 467         xfs_inobt_ptr_t         *pp;
 468         xfs_inobt_rec_t         *rp;
 469         xfs_agblock_t           agbno;
 470         xfs_agblock_t           end_agbno;
 471         struct xfs_dinode       *dip;
 472         int                     blks_per_buf;
 473         int                     inodes_per_buf;
 474         int                     ioff;
 475
 476         if (xfs_sb_version_hassparseinodes(&mp->m_sb))
 477                 blks_per_buf = mp->m_blocks_per_cluster;
 478         else
 479                 blks_per_buf = mp->m_ialloc_blks;
 480         inodes_per_buf = min(XFS_FSB_TO_INO(mp, blks_per_buf),
 481                              XFS_INODES_PER_CHUNK);
 482
 483         if (level == 0) {
 484                 rp = XFS_INOBT_REC_ADDR(mp, block, 1);
 485                 for (i = 0; i < be16_to_cpu(block->bb_numrecs); i++) {
 486                         agino = be32_to_cpu(rp[i].ir_startino);
 487                         agbno = XFS_AGINO_TO_AGBNO(mp, agino);
 488                         off = XFS_AGINO_TO_OFFSET(mp, agino);
 489                         end_agbno = agbno + mp->m_ialloc_blks;
 490
 491                         push_cur();
 492                         ioff = 0;
 493                         while (agbno < end_agbno &&
 494                                ioff < XFS_INODES_PER_CHUNK) {
 495                                 if (xfs_inobt_is_sparse_disk(&rp[i], ioff))
 496                                         goto next_buf;
 497
 498                                 set_cur(&typtab[TYP_INODE],
 499                                         XFS_AGB_TO_DADDR(mp, seqno, agbno),
 500                                         XFS_FSB_TO_BB(mp, blks_per_buf),
 501                                         DB_RING_IGN, NULL);
 502                                 if (iocur_top->data == NULL) {
 503                                         dbprintf(_("can't read inode block %u/%u\n"),
 504                                                  seqno, agbno);
 505                                         goto next_buf;
 506                                 }
 507
 508                                 for (j = 0; j < inodes_per_buf; j++) {
 509                                         if (XFS_INOBT_IS_FREE_DISK(&rp[i], ioff + j))
 510                                                 continue;
 511                                         dip = (xfs_dinode_t *)((char *)iocur_top->data +
 512                                                 ((off + j) << mp->m_sb.sb_inodelog));
 513                                         process_inode(agf, agino + ioff + j, dip);
 514                                 }
 515
 516 next_buf:
 517                                 agbno += blks_per_buf;
 518                                 ioff += inodes_per_buf;
 519                         }
 520                         pop_cur();
 521                 }
 522                 return;
 523         }
 524         pp = XFS_INOBT_PTR_ADDR(mp, block, 1, mp->m_inobt_mxr[1]);
 525         for (i = 0; i < be16_to_cpu(block->bb_numrecs); i++)
 526                 scan_sbtree(agf, be32_to_cpu(pp[i]), level, scanfunc_ino,
 527                                                                 TYP_INOBT);
 528 }