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