db/frag.c

   1 /*
   2  * Copyright (c) 2000-2003 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 <xfs/libxfs.h>
  34 #include <sys/time.h>
  35 #include "bmap.h"
  36 #include "command.h"
  37 #include "frag.h"
  38 #include "io.h"
  39 #include "output.h"
  40 #include "type.h"
  41 #include "init.h"
  42 #include "malloc.h"
  43
  44 typedef struct extent {
  45         xfs_fileoff_t   startoff;
  46         xfs_filblks_t   blockcount;
  47 } extent_t;
  48
  49 typedef struct extmap {
  50         int             naents;
  51         int             nents;
  52         extent_t        ents[1];
  53 } extmap_t;
  54 #define EXTMAP_SIZE(n)  \
  55         (offsetof(extmap_t, ents) + (sizeof(extent_t) * (n)))
  56
  57 static int              aflag;
  58 static int              dflag;
  59 static __uint64_t       extcount_actual;
  60 static __uint64_t       extcount_ideal;
  61 static int              fflag;
  62 static int              lflag;
  63 static int              qflag;
  64 static int              Rflag;
  65 static int              rflag;
  66 static int              vflag;
  67
  68 typedef void    (*scan_lbtree_f_t)(xfs_btree_lblock_t   *block,
  69                                    int                  level,
  70                                    extmap_t             **extmapp,
  71                                    typnm_t              btype);
  72
  73 typedef void    (*scan_sbtree_f_t)(xfs_btree_sblock_t   *block,
  74                                    int                  level,
  75                                    xfs_agf_t            *agf);
  76
  77 static extmap_t         *extmap_alloc(xfs_extnum_t nex);
  78 static xfs_extnum_t     extmap_ideal(extmap_t *extmap);
  79 static void             extmap_set_ext(extmap_t **extmapp, xfs_fileoff_t o,
  80                                        xfs_extlen_t c);
  81 static int              frag_f(int argc, char **argv);
  82 static int              init(int argc, char **argv);
  83 static void             process_bmbt_reclist(xfs_bmbt_rec_32_t *rp, int numrecs,
  84                                              extmap_t **extmapp);
  85 static void             process_btinode(xfs_dinode_t *dip, extmap_t **extmapp,
  86                                         int whichfork);
  87 static void             process_exinode(xfs_dinode_t *dip, extmap_t **extmapp,
  88                                         int whichfork);
  89 static void             process_fork(xfs_dinode_t *dip, int whichfork);
  90 static void             process_inode(xfs_agf_t *agf, xfs_agino_t agino,
  91                                       xfs_dinode_t *dip);
  92 static void             scan_ag(xfs_agnumber_t agno);
  93 static void             scan_lbtree(xfs_fsblock_t root, int nlevels,
  94                                     scan_lbtree_f_t func, extmap_t **extmapp,
  95                                     typnm_t btype);
  96 static void             scan_sbtree(xfs_agf_t *agf, xfs_agblock_t root,
  97                                     int nlevels, scan_sbtree_f_t func,
  98                                     typnm_t btype);
  99 static void             scanfunc_bmap(xfs_btree_lblock_t *ablock, int level,
 100                                       extmap_t **extmapp, typnm_t btype);
 101 static void             scanfunc_ino(xfs_btree_sblock_t *ablock, int level,
 102                                      xfs_agf_t *agf);
 103
 104 static const cmdinfo_t  frag_cmd =
 105         { "frag", NULL, frag_f, 0, -1, 0,
 106           "[-a] [-d] [-f] [-l] [-q] [-R] [-r] [-v]",
 107           "get file fragmentation data", NULL };
 108
 109 static extmap_t *
 110 extmap_alloc(
 111         xfs_extnum_t    nex)
 112 {
 113         extmap_t        *extmap;
 114
 115         if (nex < 1)
 116                 nex = 1;
 117         extmap = xmalloc(EXTMAP_SIZE(nex));
 118         extmap->naents = nex;
 119         extmap->nents = 0;
 120         return extmap;
 121 }
 122
 123 static xfs_extnum_t
 124 extmap_ideal(
 125         extmap_t        *extmap)
 126 {
 127         extent_t        *ep;
 128         xfs_extnum_t    rval;
 129
 130         for (ep = &extmap->ents[0], rval = 0;
 131              ep < &extmap->ents[extmap->nents];
 132              ep++) {
 133                 if (ep == &extmap->ents[0] ||
 134                     ep->startoff != ep[-1].startoff + ep[-1].blockcount)
 135                         rval++;
 136         }
 137         return rval;
 138 }
 139
 140 static void
 141 extmap_set_ext(
 142         extmap_t        **extmapp,
 143         xfs_fileoff_t   o,
 144         xfs_extlen_t    c)
 145 {
 146         extmap_t        *extmap;
 147         extent_t        *ent;
 148
 149         extmap = *extmapp;
 150         if (extmap->nents == extmap->naents) {
 151                 extmap->naents++;
 152                 extmap = xrealloc(extmap, EXTMAP_SIZE(extmap->naents));
 153                 *extmapp = extmap;
 154         }
 155         ent = &extmap->ents[extmap->nents];
 156         ent->startoff = o;
 157         ent->blockcount = c;
 158         extmap->nents++;
 159 }
 160
 161 void
 162 frag_init(void)
 163 {
 164         add_command(&frag_cmd);
 165 }
 166
 167 /*
 168  * Get file fragmentation information.
 169  */
 170 static int
 171 frag_f(
 172         int             argc,
 173         char            **argv)
 174 {
 175         xfs_agnumber_t  agno;
 176         double          answer;
 177
 178         if (!init(argc, argv))
 179                 return 0;
 180         for (agno = 0; agno < mp->m_sb.sb_agcount; agno++)
 181                 scan_ag(agno);
 182         if (extcount_actual)
 183                 answer = (double)(extcount_actual - extcount_ideal) * 100.0 /
 184                          (double)extcount_actual;
 185         else
 186                 answer = 0.0;
 187         dbprintf("actual %llu, ideal %llu, fragmentation factor %.2f%%\n",
 188                 extcount_actual, extcount_ideal, answer);
 189         return 0;
 190 }
 191
 192 static int
 193 init(
 194         int             argc,
 195         char            **argv)
 196 {
 197         int             c;
 198
 199         aflag = dflag = fflag = lflag = qflag = Rflag = rflag = vflag = 0;
 200         optind = 0;
 201         while ((c = getopt(argc, argv, "adflqRrv")) != EOF) {
 202                 switch (c) {
 203                 case 'a':
 204                         aflag = 1;
 205                         break;
 206                 case 'd':
 207                         dflag = 1;
 208                         break;
 209                 case 'f':
 210                         fflag = 1;
 211                         break;
 212                 case 'l':
 213                         lflag = 1;
 214                         break;
 215                 case 'q':
 216                         qflag = 1;
 217                         break;
 218                 case 'R':
 219                         Rflag = 1;
 220                         break;
 221                 case 'r':
 222                         rflag = 1;
 223                         break;
 224                 case 'v':
 225                         vflag = 1;
 226                         break;
 227                 default:
 228                         dbprintf("bad option for frag command\n");
 229                         return 0;
 230                 }
 231         }
 232         if (!aflag && !dflag && !fflag && !lflag && !qflag && !Rflag && !rflag)
 233                 aflag = dflag = fflag = lflag = qflag = Rflag = rflag = 1;
 234         extcount_actual = extcount_ideal = 0;
 235         return 1;
 236 }
 237
 238 static void
 239 process_bmbt_reclist(
 240         xfs_bmbt_rec_32_t       *rp,
 241         int                     numrecs,
 242         extmap_t                **extmapp)
 243 {
 244         xfs_dfilblks_t          c;
 245         int                     f;
 246         int                     i;
 247         xfs_dfiloff_t           o;
 248         xfs_dfsbno_t            s;
 249
 250         for (i = 0; i < numrecs; i++, rp++) {
 251                 convert_extent((xfs_bmbt_rec_64_t *)rp, &o, &s, &c, &f);
 252                 extmap_set_ext(extmapp, (xfs_fileoff_t)o, (xfs_extlen_t)c);
 253         }
 254 }
 255
 256 static void
 257 process_btinode(
 258         xfs_dinode_t            *dip,
 259         extmap_t                **extmapp,
 260         int                     whichfork)
 261 {
 262         xfs_bmdr_block_t        *dib;
 263         int                     i;
 264         xfs_bmbt_ptr_t          *pp;
 265         xfs_bmbt_rec_32_t       *rp;
 266
 267         dib = (xfs_bmdr_block_t *)XFS_DFORK_PTR(dip, whichfork);
 268         if (INT_GET(dib->bb_level, ARCH_CONVERT) == 0) {
 269                 rp = (xfs_bmbt_rec_32_t *)XFS_BTREE_REC_ADDR(
 270                         XFS_DFORK_SIZE(dip, mp, whichfork),
 271                         xfs_bmdr, dib, 1,
 272                         XFS_BTREE_BLOCK_MAXRECS(XFS_DFORK_SIZE(dip, mp,
 273                                         whichfork),
 274                                 xfs_bmdr, 1));
 275                 process_bmbt_reclist(rp, INT_GET(dib->bb_numrecs, ARCH_CONVERT), extmapp);
 276                 return;
 277         }
 278         pp = XFS_BTREE_PTR_ADDR(XFS_DFORK_SIZE(dip, mp, whichfork),
 279                 xfs_bmdr, dib, 1,
 280                 XFS_BTREE_BLOCK_MAXRECS(XFS_DFORK_SIZE(dip, mp, whichfork),
 281                                         xfs_bmdr, 0));
 282         for (i = 0; i < INT_GET(dib->bb_numrecs, ARCH_CONVERT); i++)
 283                 scan_lbtree((xfs_fsblock_t)INT_GET(pp[i], ARCH_CONVERT), INT_GET(dib->bb_level, ARCH_CONVERT), scanfunc_bmap,
 284                         extmapp,
 285                         whichfork == XFS_DATA_FORK ? TYP_BMAPBTD : TYP_BMAPBTA);
 286 }
 287
 288 static void
 289 process_exinode(
 290         xfs_dinode_t            *dip,
 291         extmap_t                **extmapp,
 292         int                     whichfork)
 293 {
 294         xfs_bmbt_rec_32_t       *rp;
 295
 296         rp = (xfs_bmbt_rec_32_t *)XFS_DFORK_PTR(dip, whichfork);
 297         process_bmbt_reclist(rp, XFS_DFORK_NEXTENTS(dip, whichfork), extmapp);
 298 }
 299
 300 static void
 301 process_fork(
 302         xfs_dinode_t    *dip,
 303         int             whichfork)
 304 {
 305         extmap_t        *extmap;
 306         int             nex;
 307
 308         nex = XFS_DFORK_NEXTENTS(dip, whichfork);
 309         if (!nex)
 310                 return;
 311         extmap = extmap_alloc(nex);
 312         switch (XFS_DFORK_FORMAT(dip, whichfork)) {
 313         case XFS_DINODE_FMT_EXTENTS:
 314                 process_exinode(dip, &extmap, whichfork);
 315                 break;
 316         case XFS_DINODE_FMT_BTREE:
 317                 process_btinode(dip, &extmap, whichfork);
 318                 break;
 319         }
 320         extcount_actual += extmap->nents;
 321         extcount_ideal += extmap_ideal(extmap);
 322         xfree(extmap);
 323 }
 324
 325 static void
 326 process_inode(
 327         xfs_agf_t               *agf,
 328         xfs_agino_t             agino,
 329         xfs_dinode_t            *dip)
 330 {
 331         __uint64_t              actual;
 332         xfs_dinode_core_t       *dic;
 333         __uint64_t              ideal;
 334         xfs_ino_t               ino;
 335         int                     skipa;
 336         int                     skipd;
 337
 338         dic = &dip->di_core;
 339         ino = XFS_AGINO_TO_INO(mp, INT_GET(agf->agf_seqno, ARCH_CONVERT), agino);
 340         switch (dic->di_mode & S_IFMT) {
 341         case S_IFDIR:
 342                 skipd = !dflag;
 343                 break;
 344         case S_IFREG:
 345                 if (!rflag && (dic->di_flags & XFS_DIFLAG_REALTIME))
 346                         skipd = 1;
 347                 else if (!Rflag &&
 348                          (ino == mp->m_sb.sb_rbmino ||
 349                           ino == mp->m_sb.sb_rsumino))
 350                         skipd = 1;
 351                 else if (!qflag &&
 352                          (ino == mp->m_sb.sb_uquotino ||
 353                           ino == mp->m_sb.sb_gquotino))
 354                         skipd = 1;
 355                 else
 356                         skipd = !fflag;
 357                 break;
 358         case S_IFLNK:
 359                 skipd = !lflag;
 360                 break;
 361         default:
 362                 skipd = 1;
 363                 break;
 364         }
 365         actual = extcount_actual;
 366         ideal = extcount_ideal;
 367         if (!skipd)
 368                 process_fork(dip, XFS_DATA_FORK);
 369         skipa = !aflag || !XFS_DFORK_Q(dip);
 370         if (!skipa)
 371                 process_fork(dip, XFS_ATTR_FORK);
 372         if (vflag && (!skipd || !skipa))
 373                 dbprintf("inode %lld actual %lld ideal %lld\n",
 374                         ino, extcount_actual - actual, extcount_ideal - ideal);
 375 }
 376
 377 static void
 378 scan_ag(
 379         xfs_agnumber_t  agno)
 380 {
 381         xfs_agf_t       *agf;
 382         xfs_agi_t       *agi;
 383
 384         push_cur();
 385         set_cur(&typtab[TYP_AGF],
 386                 XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
 387                 XFS_FSS_TO_BB(mp, 1), DB_RING_IGN, NULL);
 388         if ((agf = iocur_top->data) == NULL) {
 389                 dbprintf("can't read agf block for ag %u\n", agno);
 390                 pop_cur();
 391                 return;
 392         }
 393         push_cur();
 394         set_cur(&typtab[TYP_AGI],
 395                 XFS_AG_DADDR(mp, agno, XFS_AGI_DADDR(mp)),
 396                 XFS_FSS_TO_BB(mp, 1), 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                                 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);
 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 }