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         dbprintf(_("Note, this number is largely meaningless.\n"));
 176         answer = (double)extcount_actual / (double)extcount_ideal;
 177         dbprintf(_("Files on this filesystem average %.2f extents per file\n"),
 178                 answer);
 179         return 0;
 180 }
 181
 182 static int
 183 init(
 184         int             argc,
 185         char            **argv)
 186 {
 187         int             c;
 188
 189         aflag = dflag = fflag = lflag = qflag = Rflag = rflag = vflag = 0;
 190         optind = 0;
 191         while ((c = getopt(argc, argv, "adflqRrv")) != EOF) {
 192                 switch (c) {
 193                 case 'a':
 194                         aflag = 1;
 195                         break;
 196                 case 'd':
 197                         dflag = 1;
 198                         break;
 199                 case 'f':
 200                         fflag = 1;
 201                         break;
 202                 case 'l':
 203                         lflag = 1;
 204                         break;
 205                 case 'q':
 206                         qflag = 1;
 207                         break;
 208                 case 'R':
 209                         Rflag = 1;
 210                         break;
 211                 case 'r':
 212                         rflag = 1;
 213                         break;
 214                 case 'v':
 215                         vflag = 1;
 216                         break;
 217                 default:
 218                         dbprintf(_("bad option for frag command\n"));
 219                         return 0;
 220                 }
 221         }
 222         if (!aflag && !dflag && !fflag && !lflag && !qflag && !Rflag && !rflag)
 223                 aflag = dflag = fflag = lflag = qflag = Rflag = rflag = 1;
 224         extcount_actual = extcount_ideal = 0;
 225         return 1;
 226 }
 227
 228 static void
 229 process_bmbt_reclist(
 230         xfs_bmbt_rec_t          *rp,
 231         int                     numrecs,
 232         extmap_t                **extmapp)
 233 {
 234         xfs_filblks_t           c;
 235         int                     f;
 236         int                     i;
 237         xfs_fileoff_t           o;
 238         xfs_fsblock_t           s;
 239
 240         for (i = 0; i < numrecs; i++, rp++) {
 241                 convert_extent(rp, &o, &s, &c, &f);
 242                 extmap_set_ext(extmapp, (xfs_fileoff_t)o, (xfs_extlen_t)c);
 243         }
 244 }
 245
 246 static void
 247 process_btinode(
 248         xfs_dinode_t            *dip,
 249         extmap_t                **extmapp,
 250         int                     whichfork)
 251 {
 252         xfs_bmdr_block_t        *dib;
 253         int                     i;
 254         xfs_bmbt_ptr_t          *pp;
 255
 256         dib = (xfs_bmdr_block_t *)XFS_DFORK_PTR(dip, whichfork);
 257         if (be16_to_cpu(dib->bb_level) == 0) {
 258                 xfs_bmbt_rec_t          *rp = XFS_BMDR_REC_ADDR(dib, 1);
 259                 process_bmbt_reclist(rp, be16_to_cpu(dib->bb_numrecs), extmapp);
 260                 return;
 261         }
 262         pp = XFS_BMDR_PTR_ADDR(dib, 1,
 263                 libxfs_bmdr_maxrecs(XFS_DFORK_SIZE(dip, mp, whichfork), 0));
 264         for (i = 0; i < be16_to_cpu(dib->bb_numrecs); i++)
 265                 scan_lbtree(get_unaligned_be64(&pp[i]),
 266                          be16_to_cpu(dib->bb_level), scanfunc_bmap, extmapp,
 267                         whichfork == XFS_DATA_FORK ? TYP_BMAPBTD : TYP_BMAPBTA);
 268 }
 269
 270 static void
 271 process_exinode(
 272         xfs_dinode_t            *dip,
 273         extmap_t                **extmapp,
 274         int                     whichfork)
 275 {
 276         xfs_bmbt_rec_t          *rp;
 277
 278         rp = (xfs_bmbt_rec_t *)XFS_DFORK_PTR(dip, whichfork);
 279         process_bmbt_reclist(rp, XFS_DFORK_NEXTENTS(dip, whichfork), extmapp);
 280 }
 281
 282 static void
 283 process_fork(
 284         xfs_dinode_t    *dip,
 285         int             whichfork)
 286 {
 287         extmap_t        *extmap;
 288         int             nex;
 289
 290         nex = XFS_DFORK_NEXTENTS(dip, whichfork);
 291         if (!nex)
 292                 return;
 293         extmap = extmap_alloc(nex);
 294         switch (XFS_DFORK_FORMAT(dip, whichfork)) {
 295         case XFS_DINODE_FMT_EXTENTS:
 296                 process_exinode(dip, &extmap, whichfork);
 297                 break;
 298         case XFS_DINODE_FMT_BTREE:
 299                 process_btinode(dip, &extmap, whichfork);
 300                 break;
 301         }
 302         extcount_actual += extmap->nents;
 303         extcount_ideal += extmap_ideal(extmap);
 304         xfree(extmap);
 305 }
 306
 307 static void
 308 process_inode(
 309         xfs_agf_t               *agf,
 310         xfs_agino_t             agino,
 311         xfs_dinode_t            *dip)
 312 {
 313         uint64_t                actual;
 314         uint64_t                ideal;
 315         xfs_ino_t               ino;
 316         int                     skipa;
 317         int                     skipd;
 318
 319         ino = XFS_AGINO_TO_INO(mp, be32_to_cpu(agf->agf_seqno), agino);
 320         switch (be16_to_cpu(dip->di_mode) & S_IFMT) {
 321         case S_IFDIR:
 322                 skipd = !dflag;
 323                 break;
 324         case S_IFREG:
 325                 if (!rflag && (be16_to_cpu(dip->di_flags) & XFS_DIFLAG_REALTIME))
 326                         skipd = 1;
 327                 else if (!Rflag &&
 328                          (ino == mp->m_sb.sb_rbmino ||
 329                           ino == mp->m_sb.sb_rsumino))
 330                         skipd = 1;
 331                 else if (!qflag &&
 332                          (ino == mp->m_sb.sb_uquotino ||
 333                           ino == mp->m_sb.sb_gquotino ||
 334                           ino == mp->m_sb.sb_pquotino))
 335                         skipd = 1;
 336                 else
 337                         skipd = !fflag;
 338                 break;
 339         case S_IFLNK:
 340                 skipd = !lflag;
 341                 break;
 342         default:
 343                 skipd = 1;
 344                 break;
 345         }
 346         actual = extcount_actual;
 347         ideal = extcount_ideal;
 348         if (!skipd)
 349                 process_fork(dip, XFS_DATA_FORK);
 350         skipa = !aflag || !XFS_DFORK_Q(dip);
 351         if (!skipa)
 352                 process_fork(dip, XFS_ATTR_FORK);
 353         if (vflag && (!skipd || !skipa))
 354                 dbprintf(_("inode %lld actual %lld ideal %lld\n"),
 355                         ino, extcount_actual - actual, extcount_ideal - ideal);
 356 }
 357
 358 static void
 359 scan_ag(
 360         xfs_agnumber_t  agno)
 361 {
 362         xfs_agf_t       *agf;
 363         xfs_agi_t       *agi;
 364
 365         push_cur();
 366         set_cur(&typtab[TYP_AGF],
 367                 XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
 368                 XFS_FSS_TO_BB(mp, 1), DB_RING_IGN, NULL);
 369         if ((agf = iocur_top->data) == NULL) {
 370                 dbprintf(_("can't read agf block for ag %u\n"), agno);
 371                 pop_cur();
 372                 return;
 373         }
 374         push_cur();
 375         set_cur(&typtab[TYP_AGI],
 376                 XFS_AG_DADDR(mp, agno, XFS_AGI_DADDR(mp)),
 377                 XFS_FSS_TO_BB(mp, 1), DB_RING_IGN, NULL);
 378         if ((agi = iocur_top->data) == NULL) {
 379                 dbprintf(_("can't read agi block for ag %u\n"), agno);
 380                 pop_cur();
 381                 pop_cur();
 382                 return;
 383         }
 384         scan_sbtree(agf, be32_to_cpu(agi->agi_root),
 385                         be32_to_cpu(agi->agi_level), scanfunc_ino, TYP_INOBT);
 386         pop_cur();
 387         pop_cur();
 388 }
 389
 390 static void
 391 scan_lbtree(
 392         xfs_fsblock_t   root,
 393         int             nlevels,
 394         scan_lbtree_f_t func,
 395         extmap_t        **extmapp,
 396         typnm_t         btype)
 397 {
 398         push_cur();
 399         set_cur(&typtab[btype], XFS_FSB_TO_DADDR(mp, root), blkbb, DB_RING_IGN,
 400                 NULL);
 401         if (iocur_top->data == NULL) {
 402                 dbprintf(_("can't read btree block %u/%u\n"),
 403                         XFS_FSB_TO_AGNO(mp, root),
 404                         XFS_FSB_TO_AGBNO(mp, root));
 405                 return;
 406         }
 407         (*func)(iocur_top->data, nlevels - 1, extmapp, btype);
 408         pop_cur();
 409 }
 410
 411 static void
 412 scan_sbtree(
 413         xfs_agf_t       *agf,
 414         xfs_agblock_t   root,
 415         int             nlevels,
 416         scan_sbtree_f_t func,
 417         typnm_t         btype)
 418 {
 419         xfs_agnumber_t  seqno = be32_to_cpu(agf->agf_seqno);
 420
 421         push_cur();
 422         set_cur(&typtab[btype], XFS_AGB_TO_DADDR(mp, seqno, root),
 423                 blkbb, DB_RING_IGN, NULL);
 424         if (iocur_top->data == NULL) {
 425                 dbprintf(_("can't read btree block %u/%u\n"), seqno, root);
 426                 return;
 427         }
 428         (*func)(iocur_top->data, nlevels - 1, agf);
 429         pop_cur();
 430 }
 431
 432 static void
 433 scanfunc_bmap(
 434         struct xfs_btree_block  *block,
 435         int                     level,
 436         extmap_t                **extmapp,
 437         typnm_t                 btype)
 438 {
 439         int                     i;
 440         xfs_bmbt_ptr_t          *pp;
 441         xfs_bmbt_rec_t          *rp;
 442         int                     nrecs;
 443
 444         nrecs = be16_to_cpu(block->bb_numrecs);
 445
 446         if (level == 0) {
 447                 if (nrecs > mp->m_bmap_dmxr[0]) {
 448                         dbprintf(_("invalid numrecs (%u) in %s block\n"),
 449                                    nrecs, typtab[btype].name);
 450                         return;
 451                 }
 452                 rp = XFS_BMBT_REC_ADDR(mp, block, 1);
 453                 process_bmbt_reclist(rp, nrecs, extmapp);
 454                 return;
 455         }
 456
 457         if (nrecs > mp->m_bmap_dmxr[1]) {
 458                 dbprintf(_("invalid numrecs (%u) in %s block\n"),
 459                            nrecs, typtab[btype].name);
 460                 return;
 461         }
 462         pp = XFS_BMBT_PTR_ADDR(mp, block, 1, mp->m_bmap_dmxr[0]);
 463         for (i = 0; i < nrecs; i++)
 464                 scan_lbtree(be64_to_cpu(pp[i]), level, scanfunc_bmap, extmapp,
 465                                                                         btype);
 466 }
 467
 468 static void
 469 scanfunc_ino(
 470         struct xfs_btree_block  *block,
 471         int                     level,
 472         xfs_agf_t               *agf)
 473 {
 474         xfs_agino_t             agino;
 475         xfs_agnumber_t          seqno = be32_to_cpu(agf->agf_seqno);
 476         int                     i;
 477         int                     j;
 478         int                     off;
 479         xfs_inobt_ptr_t         *pp;
 480         xfs_inobt_rec_t         *rp;
 481
 482         if (level == 0) {
 483                 rp = XFS_INOBT_REC_ADDR(mp, block, 1);
 484                 for (i = 0; i < be16_to_cpu(block->bb_numrecs); i++) {
 485                         agino = be32_to_cpu(rp[i].ir_startino);
 486                         off = XFS_INO_TO_OFFSET(mp, agino);
 487                         push_cur();
 488                         set_cur(&typtab[TYP_INODE],
 489                                 XFS_AGB_TO_DADDR(mp, seqno,
 490                                                  XFS_AGINO_TO_AGBNO(mp, agino)),
 491                                 XFS_FSB_TO_BB(mp, mp->m_ialloc_blks),
 492                                 DB_RING_IGN, NULL);
 493                         if (iocur_top->data == NULL) {
 494                                 dbprintf(_("can't read inode block %u/%u\n"),
 495                                         seqno, XFS_AGINO_TO_AGBNO(mp, agino));
 496                                 continue;
 497                         }
 498                         for (j = 0; j < XFS_INODES_PER_CHUNK; j++) {
 499                                 if (XFS_INOBT_IS_FREE_DISK(&rp[i], j))
 500                                         continue;
 501                                 process_inode(agf, agino + j, (xfs_dinode_t *)
 502                                         ((char *)iocur_top->data +
 503                                         ((off + j) << mp->m_sb.sb_inodelog)));
 504                         }
 505                         pop_cur();
 506                 }
 507                 return;
 508         }
 509         pp = XFS_INOBT_PTR_ADDR(mp, block, 1, mp->m_inobt_mxr[1]);
 510         for (i = 0; i < be16_to_cpu(block->bb_numrecs); i++)
 511                 scan_sbtree(agf, be32_to_cpu(pp[i]), level, scanfunc_ino,
 512                                                                 TYP_INOBT);
 513 }