db/frag.c

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