db/frag.c

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