sbin/fsck_ffs/suj.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright 2009, 2010 Jeffrey W. Roberson <jeff@FreeBSD.org>
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
  20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26  * SUCH DAMAGE.
  27  */
  28
  29 #include <sys/cdefs.h>
  30 __FBSDID("$FreeBSD$");
  31
  32 #include <sys/param.h>
  33 #include <sys/disk.h>
  34 #include <sys/disklabel.h>
  35 #include <sys/mount.h>
  36 #include <sys/stat.h>
  37
  38 #include <ufs/ufs/ufsmount.h>
  39 #include <ufs/ufs/dinode.h>
  40 #include <ufs/ufs/dir.h>
  41 #include <ufs/ffs/fs.h>
  42
  43 #include <assert.h>
  44 #include <err.h>
  45 #include <setjmp.h>
  46 #include <stdarg.h>
  47 #include <stdio.h>
  48 #include <stdlib.h>
  49 #include <stdint.h>
  50 #include <libufs.h>
  51 #include <string.h>
  52 #include <strings.h>
  53 #include <sysexits.h>
  54 #include <time.h>
  55
  56 #include "fsck.h"
  57
  58 #define DOTDOT_OFFSET   DIRECTSIZ(1)
  59
  60 struct suj_seg {
  61         TAILQ_ENTRY(suj_seg) ss_next;
  62         struct jsegrec  ss_rec;
  63         uint8_t         *ss_blk;
  64 };
  65
  66 struct suj_rec {
  67         TAILQ_ENTRY(suj_rec) sr_next;
  68         union jrec      *sr_rec;
  69 };
  70 TAILQ_HEAD(srechd, suj_rec);
  71
  72 struct suj_ino {
  73         LIST_ENTRY(suj_ino)     si_next;
  74         struct srechd           si_recs;
  75         struct srechd           si_newrecs;
  76         struct srechd           si_movs;
  77         struct jtrncrec         *si_trunc;
  78         ino_t                   si_ino;
  79         char                    si_skipparent;
  80         char                    si_hasrecs;
  81         char                    si_blkadj;
  82         char                    si_linkadj;
  83         int                     si_mode;
  84         nlink_t                 si_nlinkadj;
  85         nlink_t                 si_nlink;
  86         nlink_t                 si_dotlinks;
  87 };
  88 LIST_HEAD(inohd, suj_ino);
  89
  90 struct suj_blk {
  91         LIST_ENTRY(suj_blk)     sb_next;
  92         struct srechd           sb_recs;
  93         ufs2_daddr_t            sb_blk;
  94 };
  95 LIST_HEAD(blkhd, suj_blk);
  96
  97 struct suj_cg {
  98         LIST_ENTRY(suj_cg)      sc_next;
  99         struct blkhd            sc_blkhash[HASHSIZE];
 100         struct inohd            sc_inohash[HASHSIZE];
 101         struct ino_blk          *sc_lastiblk;
 102         struct suj_ino          *sc_lastino;
 103         struct suj_blk          *sc_lastblk;
 104         struct bufarea          *sc_cgbp;
 105         struct cg               *sc_cgp;
 106         int                     sc_cgx;
 107 };
 108
 109 static LIST_HEAD(cghd, suj_cg) cghash[HASHSIZE];
 110 static struct suj_cg *lastcg;
 111
 112 static TAILQ_HEAD(seghd, suj_seg) allsegs;
 113 static uint64_t oldseq;
 114 static struct fs *fs = NULL;
 115 static ino_t sujino;
 116
 117 /*
 118  * Summary statistics.
 119  */
 120 static uint64_t freefrags;
 121 static uint64_t freeblocks;
 122 static uint64_t freeinos;
 123 static uint64_t freedir;
 124 static uint64_t jbytes;
 125 static uint64_t jrecs;
 126
 127 static jmp_buf  jmpbuf;
 128
 129 typedef void (*ino_visitor)(ino_t, ufs_lbn_t, ufs2_daddr_t, int);
 130 static void err_suj(const char *, ...) __dead2;
 131 static void ino_trunc(ino_t, off_t);
 132 static void ino_decr(ino_t);
 133 static void ino_adjust(struct suj_ino *);
 134 static void ino_build(struct suj_ino *);
 135 static int blk_isfree(ufs2_daddr_t);
 136 static void initsuj(void);
 137
 138 static void *
 139 errmalloc(size_t n)
 140 {
 141         void *a;
 142
 143         a = Malloc(n);
 144         if (a == NULL)
 145                 err(EX_OSERR, "malloc(%zu)", n);
 146         return (a);
 147 }
 148
 149 /*
 150  * When hit a fatal error in journalling check, print out
 151  * the error and then offer to fallback to normal fsck.
 152  */
 153 static void
 154 err_suj(const char * restrict fmt, ...)
 155 {
 156         va_list ap;
 157
 158         if (preen)
 159                 (void)fprintf(stdout, "%s: ", cdevname);
 160
 161         va_start(ap, fmt);
 162         (void)vfprintf(stdout, fmt, ap);
 163         va_end(ap);
 164
 165         longjmp(jmpbuf, -1);
 166 }
 167
 168 /*
 169  * Lookup a cg by number in the hash so we can keep track of which cgs
 170  * need stats rebuilt.
 171  */
 172 static struct suj_cg *
 173 cg_lookup(int cgx)
 174 {
 175         struct cghd *hd;
 176         struct suj_cg *sc;
 177         struct bufarea *cgbp;
 178
 179         if (cgx < 0 || cgx >= fs->fs_ncg)
 180                 err_suj("Bad cg number %d\n", cgx);
 181         if (lastcg && lastcg->sc_cgx == cgx)
 182                 return (lastcg);
 183         cgbp = cglookup(cgx);
 184         if (!check_cgmagic(cgx, cgbp, 0))
 185                 err_suj("UNABLE TO REBUILD CYLINDER GROUP %d", cgx);
 186         hd = &cghash[HASH(cgx)];
 187         LIST_FOREACH(sc, hd, sc_next)
 188                 if (sc->sc_cgx == cgx) {
 189                         sc->sc_cgbp = cgbp;
 190                         sc->sc_cgp = sc->sc_cgbp->b_un.b_cg;
 191                         lastcg = sc;
 192                         return (sc);
 193                 }
 194         sc = errmalloc(sizeof(*sc));
 195         bzero(sc, sizeof(*sc));
 196         sc->sc_cgbp = cgbp;
 197         sc->sc_cgp = sc->sc_cgbp->b_un.b_cg;
 198         sc->sc_cgx = cgx;
 199         LIST_INSERT_HEAD(hd, sc, sc_next);
 200         return (sc);
 201 }
 202
 203 /*
 204  * Lookup an inode number in the hash and allocate a suj_ino if it does
 205  * not exist.
 206  */
 207 static struct suj_ino *
 208 ino_lookup(ino_t ino, int creat)
 209 {
 210         struct suj_ino *sino;
 211         struct inohd *hd;
 212         struct suj_cg *sc;
 213
 214         sc = cg_lookup(ino_to_cg(fs, ino));
 215         if (sc->sc_lastino && sc->sc_lastino->si_ino == ino)
 216                 return (sc->sc_lastino);
 217         hd = &sc->sc_inohash[HASH(ino)];
 218         LIST_FOREACH(sino, hd, si_next)
 219                 if (sino->si_ino == ino)
 220                         return (sino);
 221         if (creat == 0)
 222                 return (NULL);
 223         sino = errmalloc(sizeof(*sino));
 224         bzero(sino, sizeof(*sino));
 225         sino->si_ino = ino;
 226         TAILQ_INIT(&sino->si_recs);
 227         TAILQ_INIT(&sino->si_newrecs);
 228         TAILQ_INIT(&sino->si_movs);
 229         LIST_INSERT_HEAD(hd, sino, si_next);
 230
 231         return (sino);
 232 }
 233
 234 /*
 235  * Lookup a block number in the hash and allocate a suj_blk if it does
 236  * not exist.
 237  */
 238 static struct suj_blk *
 239 blk_lookup(ufs2_daddr_t blk, int creat)
 240 {
 241         struct suj_blk *sblk;
 242         struct suj_cg *sc;
 243         struct blkhd *hd;
 244
 245         sc = cg_lookup(dtog(fs, blk));
 246         if (sc->sc_lastblk && sc->sc_lastblk->sb_blk == blk)
 247                 return (sc->sc_lastblk);
 248         hd = &sc->sc_blkhash[HASH(fragstoblks(fs, blk))];
 249         LIST_FOREACH(sblk, hd, sb_next)
 250                 if (sblk->sb_blk == blk)
 251                         return (sblk);
 252         if (creat == 0)
 253                 return (NULL);
 254         sblk = errmalloc(sizeof(*sblk));
 255         bzero(sblk, sizeof(*sblk));
 256         sblk->sb_blk = blk;
 257         TAILQ_INIT(&sblk->sb_recs);
 258         LIST_INSERT_HEAD(hd, sblk, sb_next);
 259
 260         return (sblk);
 261 }
 262
 263 static int
 264 blk_overlaps(struct jblkrec *brec, ufs2_daddr_t start, int frags)
 265 {
 266         ufs2_daddr_t bstart;
 267         ufs2_daddr_t bend;
 268         ufs2_daddr_t end;
 269
 270         end = start + frags;
 271         bstart = brec->jb_blkno + brec->jb_oldfrags;
 272         bend = bstart + brec->jb_frags;
 273         if (start < bend && end > bstart)
 274                 return (1);
 275         return (0);
 276 }
 277
 278 static int
 279 blk_equals(struct jblkrec *brec, ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t start,
 280     int frags)
 281 {
 282
 283         if (brec->jb_ino != ino || brec->jb_lbn != lbn)
 284                 return (0);
 285         if (brec->jb_blkno + brec->jb_oldfrags != start)
 286                 return (0);
 287         if (brec->jb_frags < frags)
 288                 return (0);
 289         return (1);
 290 }
 291
 292 static void
 293 blk_setmask(struct jblkrec *brec, int *mask)
 294 {
 295         int i;
 296
 297         for (i = brec->jb_oldfrags; i < brec->jb_oldfrags + brec->jb_frags; i++)
 298                 *mask |= 1 << i;
 299 }
 300
 301 /*
 302  * Determine whether a given block has been reallocated to a new location.
 303  * Returns a mask of overlapping bits if any frags have been reused or
 304  * zero if the block has not been re-used and the contents can be trusted.
 305  *
 306  * This is used to ensure that an orphaned pointer due to truncate is safe
 307  * to be freed.  The mask value can be used to free partial blocks.
 308  */
 309 static int
 310 blk_freemask(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn, int frags)
 311 {
 312         struct suj_blk *sblk;
 313         struct suj_rec *srec;
 314         struct jblkrec *brec;
 315         int mask;
 316         int off;
 317
 318         /*
 319          * To be certain we're not freeing a reallocated block we lookup
 320          * this block in the blk hash and see if there is an allocation
 321          * journal record that overlaps with any fragments in the block
 322          * we're concerned with.  If any fragments have ben reallocated
 323          * the block has already been freed and re-used for another purpose.
 324          */
 325         mask = 0;
 326         sblk = blk_lookup(blknum(fs, blk), 0);
 327         if (sblk == NULL)
 328                 return (0);
 329         off = blk - sblk->sb_blk;
 330         TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) {
 331                 brec = (struct jblkrec *)srec->sr_rec;
 332                 /*
 333                  * If the block overlaps but does not match
 334                  * exactly this record refers to the current
 335                  * location.
 336                  */
 337                 if (blk_overlaps(brec, blk, frags) == 0)
 338                         continue;
 339                 if (blk_equals(brec, ino, lbn, blk, frags) == 1)
 340                         mask = 0;
 341                 else
 342                         blk_setmask(brec, &mask);
 343         }
 344         if (debug)
 345                 printf("blk_freemask: blk %jd sblk %jd off %d mask 0x%X\n",
 346                     blk, sblk->sb_blk, off, mask);
 347         return (mask >> off);
 348 }
 349
 350 /*
 351  * Determine whether it is safe to follow an indirect.  It is not safe
 352  * if any part of the indirect has been reallocated or the last journal
 353  * entry was an allocation.  Just allocated indirects may not have valid
 354  * pointers yet and all of their children will have their own records.
 355  * It is also not safe to follow an indirect if the cg bitmap has been
 356  * cleared as a new allocation may write to the block prior to the journal
 357  * being written.
 358  *
 359  * Returns 1 if it's safe to follow the indirect and 0 otherwise.
 360  */
 361 static int
 362 blk_isindir(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn)
 363 {
 364         struct suj_blk *sblk;
 365         struct jblkrec *brec;
 366
 367         sblk = blk_lookup(blk, 0);
 368         if (sblk == NULL)
 369                 return (1);
 370         if (TAILQ_EMPTY(&sblk->sb_recs))
 371                 return (1);
 372         brec = (struct jblkrec *)TAILQ_LAST(&sblk->sb_recs, srechd)->sr_rec;
 373         if (blk_equals(brec, ino, lbn, blk, fs->fs_frag))
 374                 if (brec->jb_op == JOP_FREEBLK)
 375                         return (!blk_isfree(blk));
 376         return (0);
 377 }
 378
 379 /*
 380  * Clear an inode from the cg bitmap.  If the inode was already clear return
 381  * 0 so the caller knows it does not have to check the inode contents.
 382  */
 383 static int
 384 ino_free(ino_t ino, int mode)
 385 {
 386         struct suj_cg *sc;
 387         uint8_t *inosused;
 388         struct cg *cgp;
 389         int cg;
 390
 391         cg = ino_to_cg(fs, ino);
 392         ino = ino % fs->fs_ipg;
 393         sc = cg_lookup(cg);
 394         cgp = sc->sc_cgp;
 395         inosused = cg_inosused(cgp);
 396         /*
 397          * The bitmap may never have made it to the disk so we have to
 398          * conditionally clear.  We can avoid writing the cg in this case.
 399          */
 400         if (isclr(inosused, ino))
 401                 return (0);
 402         freeinos++;
 403         clrbit(inosused, ino);
 404         if (ino < cgp->cg_irotor)
 405                 cgp->cg_irotor = ino;
 406         cgp->cg_cs.cs_nifree++;
 407         if ((mode & IFMT) == IFDIR) {
 408                 freedir++;
 409                 cgp->cg_cs.cs_ndir--;
 410         }
 411         cgdirty(sc->sc_cgbp);
 412
 413         return (1);
 414 }
 415
 416 /*
 417  * Free 'frags' frags starting at filesystem block 'bno' skipping any frags
 418  * set in the mask.
 419  */
 420 static void
 421 blk_free(ufs2_daddr_t bno, int mask, int frags)
 422 {
 423         ufs1_daddr_t fragno, cgbno;
 424         struct suj_cg *sc;
 425         struct cg *cgp;
 426         int i, cg;
 427         uint8_t *blksfree;
 428
 429         if (debug)
 430                 printf("Freeing %d frags at blk %jd mask 0x%x\n",
 431                     frags, bno, mask);
 432         cg = dtog(fs, bno);
 433         sc = cg_lookup(cg);
 434         cgp = sc->sc_cgp;
 435         cgbno = dtogd(fs, bno);
 436         blksfree = cg_blksfree(cgp);
 437
 438         /*
 439          * If it's not allocated we only wrote the journal entry
 440          * and never the bitmaps.  Here we unconditionally clear and
 441          * resolve the cg summary later.
 442          */
 443         if (frags == fs->fs_frag && mask == 0) {
 444                 fragno = fragstoblks(fs, cgbno);
 445                 ffs_setblock(fs, blksfree, fragno);
 446                 freeblocks++;
 447         } else {
 448                 /*
 449                  * deallocate the fragment
 450                  */
 451                 for (i = 0; i < frags; i++)
 452                         if ((mask & (1 << i)) == 0 && isclr(blksfree, cgbno +i)) {
 453                                 freefrags++;
 454                                 setbit(blksfree, cgbno + i);
 455                         }
 456         }
 457         cgdirty(sc->sc_cgbp);
 458 }
 459
 460 /*
 461  * Returns 1 if the whole block starting at 'bno' is marked free and 0
 462  * otherwise.
 463  */
 464 static int
 465 blk_isfree(ufs2_daddr_t bno)
 466 {
 467         struct suj_cg *sc;
 468
 469         sc = cg_lookup(dtog(fs, bno));
 470         return ffs_isblock(fs, cg_blksfree(sc->sc_cgp), dtogd(fs, bno));
 471 }
 472
 473 /*
 474  * Determine whether a block exists at a particular lbn in an inode.
 475  * Returns 1 if found, 0 if not.  lbn may be negative for indirects
 476  * or ext blocks.
 477  */
 478 static int
 479 blk_isat(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int *frags)
 480 {
 481         struct inode ip;
 482         union dinode *dp;
 483         ufs2_daddr_t nblk;
 484
 485         ginode(ino, &ip);
 486         dp = ip.i_dp;
 487         if (DIP(dp, di_nlink) == 0 || DIP(dp, di_mode) == 0) {
 488                 irelse(&ip);
 489                 return (0);
 490         }
 491         nblk = ino_blkatoff(dp, ino, lbn, frags, NULL);
 492         irelse(&ip);
 493         return (nblk == blk);
 494 }
 495
 496 /*
 497  * Clear the directory entry at diroff that should point to child.  Minimal
 498  * checking is done and it is assumed that this path was verified with isat.
 499  */
 500 static void
 501 ino_clrat(ino_t parent, off_t diroff, ino_t child)
 502 {
 503         union dinode *dip;
 504         struct direct *dp;
 505         struct inode ip;
 506         ufs2_daddr_t blk;
 507         struct bufarea *bp;
 508         ufs_lbn_t lbn;
 509         int blksize;
 510         int frags;
 511         int doff;
 512
 513         if (debug)
 514                 printf("Clearing inode %ju from parent %ju at offset %jd\n",
 515                     (uintmax_t)child, (uintmax_t)parent, diroff);
 516
 517         lbn = lblkno(fs, diroff);
 518         doff = blkoff(fs, diroff);
 519         ginode(parent, &ip);
 520         dip = ip.i_dp;
 521         blk = ino_blkatoff(dip, parent, lbn, &frags, NULL);
 522         blksize = sblksize(fs, DIP(dip, di_size), lbn);
 523         irelse(&ip);
 524         bp = getdatablk(blk, blksize, BT_DIRDATA);
 525         if (bp->b_errs != 0)
 526                 err_suj("ino_clrat: UNRECOVERABLE I/O ERROR");
 527         dp = (struct direct *)&bp->b_un.b_buf[doff];
 528         if (dp->d_ino != child)
 529                 errx(1, "Inode %ju does not exist in %ju at %jd",
 530                     (uintmax_t)child, (uintmax_t)parent, diroff);
 531         dp->d_ino = 0;
 532         dirty(bp);
 533         brelse(bp);
 534         /*
 535          * The actual .. reference count will already have been removed
 536          * from the parent by the .. remref record.
 537          */
 538 }
 539
 540 /*
 541  * Determines whether a pointer to an inode exists within a directory
 542  * at a specified offset.  Returns the mode of the found entry.
 543  */
 544 static int
 545 ino_isat(ino_t parent, off_t diroff, ino_t child, int *mode, int *isdot)
 546 {
 547         struct inode ip;
 548         union dinode *dip;
 549         struct bufarea *bp;
 550         struct direct *dp;
 551         ufs2_daddr_t blk;
 552         ufs_lbn_t lbn;
 553         int blksize;
 554         int frags;
 555         int dpoff;
 556         int doff;
 557
 558         *isdot = 0;
 559         ginode(parent, &ip);
 560         dip = ip.i_dp;
 561         *mode = DIP(dip, di_mode);
 562         if ((*mode & IFMT) != IFDIR) {
 563                 if (debug) {
 564                         /*
 565                          * This can happen if the parent inode
 566                          * was reallocated.
 567                          */
 568                         if (*mode != 0)
 569                                 printf("Directory %ju has bad mode %o\n",
 570                                     (uintmax_t)parent, *mode);
 571                         else
 572                                 printf("Directory %ju has zero mode\n",
 573                                     (uintmax_t)parent);
 574                 }
 575                 irelse(&ip);
 576                 return (0);
 577         }
 578         lbn = lblkno(fs, diroff);
 579         doff = blkoff(fs, diroff);
 580         blksize = sblksize(fs, DIP(dip, di_size), lbn);
 581         if (diroff + DIRECTSIZ(1) > DIP(dip, di_size) || doff >= blksize) {
 582                 if (debug)
 583                         printf("ino %ju absent from %ju due to offset %jd"
 584                             " exceeding size %jd\n",
 585                             (uintmax_t)child, (uintmax_t)parent, diroff,
 586                             DIP(dip, di_size));
 587                 irelse(&ip);
 588                 return (0);
 589         }
 590         blk = ino_blkatoff(dip, parent, lbn, &frags, NULL);
 591         irelse(&ip);
 592         if (blk <= 0) {
 593                 if (debug)
 594                         printf("Sparse directory %ju", (uintmax_t)parent);
 595                 return (0);
 596         }
 597         bp = getdatablk(blk, blksize, BT_DIRDATA);
 598         if (bp->b_errs != 0)
 599                 err_suj("ino_isat: UNRECOVERABLE I/O ERROR");
 600         /*
 601          * Walk through the records from the start of the block to be
 602          * certain we hit a valid record and not some junk in the middle
 603          * of a file name.  Stop when we reach or pass the expected offset.
 604          */
 605         dpoff = rounddown(doff, DIRBLKSIZ);
 606         do {
 607                 dp = (struct direct *)&bp->b_un.b_buf[dpoff];
 608                 if (dpoff == doff)
 609                         break;
 610                 if (dp->d_reclen == 0)
 611                         break;
 612                 dpoff += dp->d_reclen;
 613         } while (dpoff <= doff);
 614         if (dpoff > fs->fs_bsize)
 615                 err_suj("Corrupt directory block in dir ino %ju\n",
 616                     (uintmax_t)parent);
 617         /* Not found. */
 618         if (dpoff != doff) {
 619                 if (debug)
 620                         printf("ino %ju not found in %ju, lbn %jd, dpoff %d\n",
 621                             (uintmax_t)child, (uintmax_t)parent, lbn, dpoff);
 622                 brelse(bp);
 623                 return (0);
 624         }
 625         /*
 626          * We found the item in question.  Record the mode and whether it's
 627          * a . or .. link for the caller.
 628          */
 629         if (dp->d_ino == child) {
 630                 if (child == parent)
 631                         *isdot = 1;
 632                 else if (dp->d_namlen == 2 &&
 633                     dp->d_name[0] == '.' && dp->d_name[1] == '.')
 634                         *isdot = 1;
 635                 *mode = DTTOIF(dp->d_type);
 636                 brelse(bp);
 637                 return (1);
 638         }
 639         if (debug)
 640                 printf("ino %ju doesn't match dirent ino %ju in parent %ju\n",
 641                     (uintmax_t)child, (uintmax_t)dp->d_ino, (uintmax_t)parent);
 642         brelse(bp);
 643         return (0);
 644 }
 645
 646 #define VISIT_INDIR     0x0001
 647 #define VISIT_EXT       0x0002
 648 #define VISIT_ROOT      0x0004  /* Operation came via root & valid pointers. */
 649
 650 /*
 651  * Read an indirect level which may or may not be linked into an inode.
 652  */
 653 static void
 654 indir_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, uint64_t *frags,
 655     ino_visitor visitor, int flags)
 656 {
 657         struct bufarea *bp;
 658         ufs_lbn_t lbnadd;
 659         ufs2_daddr_t nblk;
 660         ufs_lbn_t nlbn;
 661         int level;
 662         int i;
 663
 664         /*
 665          * Don't visit indirect blocks with contents we can't trust.  This
 666          * should only happen when indir_visit() is called to complete a
 667          * truncate that never finished and not when a pointer is found via
 668          * an inode.
 669          */
 670         if (blk == 0)
 671                 return;
 672         level = lbn_level(lbn);
 673         if (level == -1)
 674                 err_suj("Invalid level for lbn %jd\n", lbn);
 675         if ((flags & VISIT_ROOT) == 0 && blk_isindir(blk, ino, lbn) == 0) {
 676                 if (debug)
 677                         printf("blk %jd ino %ju lbn %jd(%d) is not indir.\n",
 678                             blk, (uintmax_t)ino, lbn, level);
 679                 goto out;
 680         }
 681         lbnadd = 1;
 682         for (i = level; i > 0; i--)
 683                 lbnadd *= NINDIR(fs);
 684         bp = getdatablk(blk, fs->fs_bsize, BT_LEVEL1 + level);
 685         if (bp->b_errs != 0)
 686                 err_suj("indir_visit: UNRECOVERABLE I/O ERROR");
 687         for (i = 0; i < NINDIR(fs); i++) {
 688                 if ((nblk = IBLK(bp, i)) == 0)
 689                         continue;
 690                 if (level == 0) {
 691                         nlbn = -lbn + i * lbnadd;
 692                         (*frags) += fs->fs_frag;
 693                         visitor(ino, nlbn, nblk, fs->fs_frag);
 694                 } else {
 695                         nlbn = (lbn + 1) - (i * lbnadd);
 696                         indir_visit(ino, nlbn, nblk, frags, visitor, flags);
 697                 }
 698         }
 699         brelse(bp);
 700 out:
 701         if (flags & VISIT_INDIR) {
 702                 (*frags) += fs->fs_frag;
 703                 visitor(ino, lbn, blk, fs->fs_frag);
 704         }
 705 }
 706
 707 /*
 708  * Visit each block in an inode as specified by 'flags' and call a
 709  * callback function.  The callback may inspect or free blocks.  The
 710  * count of frags found according to the size in the file is returned.
 711  * This is not valid for sparse files but may be used to determine
 712  * the correct di_blocks for a file.
 713  */
 714 static uint64_t
 715 ino_visit(union dinode *dp, ino_t ino, ino_visitor visitor, int flags)
 716 {
 717         ufs_lbn_t nextlbn;
 718         ufs_lbn_t tmpval;
 719         ufs_lbn_t lbn;
 720         uint64_t size;
 721         uint64_t fragcnt;
 722         int mode;
 723         int frags;
 724         int i;
 725
 726         size = DIP(dp, di_size);
 727         mode = DIP(dp, di_mode) & IFMT;
 728         fragcnt = 0;
 729         if ((flags & VISIT_EXT) &&
 730             fs->fs_magic == FS_UFS2_MAGIC && dp->dp2.di_extsize) {
 731                 for (i = 0; i < UFS_NXADDR; i++) {
 732                         if (dp->dp2.di_extb[i] == 0)
 733                                 continue;
 734                         frags = sblksize(fs, dp->dp2.di_extsize, i);
 735                         frags = numfrags(fs, frags);
 736                         fragcnt += frags;
 737                         visitor(ino, -1 - i, dp->dp2.di_extb[i], frags);
 738                 }
 739         }
 740         /* Skip datablocks for short links and devices. */
 741         if (mode == IFBLK || mode == IFCHR ||
 742             (mode == IFLNK && size < fs->fs_maxsymlinklen))
 743                 return (fragcnt);
 744         for (i = 0; i < UFS_NDADDR; i++) {
 745                 if (DIP(dp, di_db[i]) == 0)
 746                         continue;
 747                 frags = sblksize(fs, size, i);
 748                 frags = numfrags(fs, frags);
 749                 fragcnt += frags;
 750                 visitor(ino, i, DIP(dp, di_db[i]), frags);
 751         }
 752         /*
 753          * We know the following indirects are real as we're following
 754          * real pointers to them.
 755          */
 756         flags |= VISIT_ROOT;
 757         for (i = 0, tmpval = NINDIR(fs), lbn = UFS_NDADDR; i < UFS_NIADDR; i++,
 758             lbn = nextlbn) {
 759                 nextlbn = lbn + tmpval;
 760                 tmpval *= NINDIR(fs);
 761                 if (DIP(dp, di_ib[i]) == 0)
 762                         continue;
 763                 indir_visit(ino, -lbn - i, DIP(dp, di_ib[i]), &fragcnt, visitor,
 764                     flags);
 765         }
 766         return (fragcnt);
 767 }
 768
 769 /*
 770  * Null visitor function used when we just want to count blocks and
 771  * record the lbn.
 772  */
 773 ufs_lbn_t visitlbn;
 774 static void
 775 null_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
 776 {
 777         if (lbn > 0)
 778                 visitlbn = lbn;
 779 }
 780
 781 /*
 782  * Recalculate di_blocks when we discover that a block allocation or
 783  * free was not successfully completed.  The kernel does not roll this back
 784  * because it would be too expensive to compute which indirects were
 785  * reachable at the time the inode was written.
 786  */
 787 static void
 788 ino_adjblks(struct suj_ino *sino)
 789 {
 790         struct inode ip;
 791         union dinode *dp;
 792         uint64_t blocks;
 793         uint64_t frags;
 794         off_t isize;
 795         off_t size;
 796         ino_t ino;
 797
 798         ino = sino->si_ino;
 799         ginode(ino, &ip);
 800         dp = ip.i_dp;
 801         /* No need to adjust zero'd inodes. */
 802         if (DIP(dp, di_mode) == 0) {
 803                 irelse(&ip);
 804                 return;
 805         }
 806         /*
 807          * Visit all blocks and count them as well as recording the last
 808          * valid lbn in the file.  If the file size doesn't agree with the
 809          * last lbn we need to truncate to fix it.  Otherwise just adjust
 810          * the blocks count.
 811          */
 812         visitlbn = 0;
 813         frags = ino_visit(dp, ino, null_visit, VISIT_INDIR | VISIT_EXT);
 814         blocks = fsbtodb(fs, frags);
 815         /*
 816          * We assume the size and direct block list is kept coherent by
 817          * softdep.  For files that have extended into indirects we truncate
 818          * to the size in the inode or the maximum size permitted by
 819          * populated indirects.
 820          */
 821         if (visitlbn >= UFS_NDADDR) {
 822                 isize = DIP(dp, di_size);
 823                 size = lblktosize(fs, visitlbn + 1);
 824                 if (isize > size)
 825                         isize = size;
 826                 /* Always truncate to free any unpopulated indirects. */
 827                 ino_trunc(ino, isize);
 828                 irelse(&ip);
 829                 return;
 830         }
 831         if (blocks == DIP(dp, di_blocks)) {
 832                 irelse(&ip);
 833                 return;
 834         }
 835         if (debug)
 836                 printf("ino %ju adjusting block count from %jd to %jd\n",
 837                     (uintmax_t)ino, DIP(dp, di_blocks), blocks);
 838         DIP_SET(dp, di_blocks, blocks);
 839         inodirty(&ip);
 840         irelse(&ip);
 841 }
 842
 843 static void
 844 blk_free_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
 845 {
 846
 847         blk_free(blk, blk_freemask(blk, ino, lbn, frags), frags);
 848 }
 849
 850 /*
 851  * Free a block or tree of blocks that was previously rooted in ino at
 852  * the given lbn.  If the lbn is an indirect all children are freed
 853  * recursively.
 854  */
 855 static void
 856 blk_free_lbn(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn, int frags, int follow)
 857 {
 858         uint64_t resid;
 859         int mask;
 860
 861         mask = blk_freemask(blk, ino, lbn, frags);
 862         resid = 0;
 863         if (lbn <= -UFS_NDADDR && follow && mask == 0)
 864                 indir_visit(ino, lbn, blk, &resid, blk_free_visit, VISIT_INDIR);
 865         else
 866                 blk_free(blk, mask, frags);
 867 }
 868
 869 static void
 870 ino_setskip(struct suj_ino *sino, ino_t parent)
 871 {
 872         int isdot;
 873         int mode;
 874
 875         if (ino_isat(sino->si_ino, DOTDOT_OFFSET, parent, &mode, &isdot))
 876                 sino->si_skipparent = 1;
 877 }
 878
 879 static void
 880 ino_remref(ino_t parent, ino_t child, uint64_t diroff, int isdotdot)
 881 {
 882         struct suj_ino *sino;
 883         struct suj_rec *srec;
 884         struct jrefrec *rrec;
 885
 886         /*
 887          * Lookup this inode to see if we have a record for it.
 888          */
 889         sino = ino_lookup(child, 0);
 890         /*
 891          * Tell any child directories we've already removed their
 892          * parent link cnt.  Don't try to adjust our link down again.
 893          */
 894         if (sino != NULL && isdotdot == 0)
 895                 ino_setskip(sino, parent);
 896         /*
 897          * No valid record for this inode.  Just drop the on-disk
 898          * link by one.
 899          */
 900         if (sino == NULL || sino->si_hasrecs == 0) {
 901                 ino_decr(child);
 902                 return;
 903         }
 904         /*
 905          * Use ino_adjust() if ino_check() has already processed this
 906          * child.  If we lose the last non-dot reference to a
 907          * directory it will be discarded.
 908          */
 909         if (sino->si_linkadj) {
 910                 if (sino->si_nlink == 0)
 911                         err_suj("ino_remref: ino %ld mode 0%o about to go "
 912                             "negative\n", sino->si_ino, sino->si_mode);
 913                 sino->si_nlink--;
 914                 if (isdotdot)
 915                         sino->si_dotlinks--;
 916                 ino_adjust(sino);
 917                 return;
 918         }
 919         /*
 920          * If we haven't yet processed this inode we need to make
 921          * sure we will successfully discover the lost path.  If not
 922          * use nlinkadj to remember.
 923          */
 924         TAILQ_FOREACH(srec, &sino->si_recs, sr_next) {
 925                 rrec = (struct jrefrec *)srec->sr_rec;
 926                 if (rrec->jr_parent == parent &&
 927                     rrec->jr_diroff == diroff)
 928                         return;
 929         }
 930         sino->si_nlinkadj++;
 931 }
 932
 933 /*
 934  * Free the children of a directory when the directory is discarded.
 935  */
 936 static void
 937 ino_free_children(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
 938 {
 939         struct suj_ino *sino;
 940         struct bufarea *bp;
 941         struct direct *dp;
 942         off_t diroff;
 943         int skipparent;
 944         int isdotdot;
 945         int dpoff;
 946         int size;
 947
 948         sino = ino_lookup(ino, 0);
 949         if (sino)
 950                 skipparent = sino->si_skipparent;
 951         else
 952                 skipparent = 0;
 953         size = lfragtosize(fs, frags);
 954         bp = getdatablk(blk, size, BT_DIRDATA);
 955         if (bp->b_errs != 0)
 956                 err_suj("ino_free_children: UNRECOVERABLE I/O ERROR");
 957         dp = (struct direct *)&bp->b_un.b_buf[0];
 958         for (dpoff = 0; dpoff < size && dp->d_reclen; dpoff += dp->d_reclen) {
 959                 dp = (struct direct *)&bp->b_un.b_buf[dpoff];
 960                 if (dp->d_ino == 0 || dp->d_ino == UFS_WINO)
 961                         continue;
 962                 if (dp->d_namlen == 1 && dp->d_name[0] == '.')
 963                         continue;
 964                 isdotdot = dp->d_namlen == 2 && dp->d_name[0] == '.' &&
 965                     dp->d_name[1] == '.';
 966                 if (isdotdot && skipparent == 1)
 967                         continue;
 968                 if (debug)
 969                         printf("Directory %ju removing ino %ju name %s\n",
 970                             (uintmax_t)ino, (uintmax_t)dp->d_ino, dp->d_name);
 971                 diroff = lblktosize(fs, lbn) + dpoff;
 972                 ino_remref(ino, dp->d_ino, diroff, isdotdot);
 973         }
 974         brelse(bp);
 975 }
 976
 977 /*
 978  * Reclaim an inode, freeing all blocks and decrementing all children's
 979  * link counts.  Free the inode back to the cg.
 980  */
 981 static void
 982 ino_reclaim(struct inode *ip, ino_t ino, int mode)
 983 {
 984         union dinode *dp;
 985         uint32_t gen;
 986
 987         dp = ip->i_dp;
 988         if (ino == UFS_ROOTINO)
 989                 err_suj("Attempting to free UFS_ROOTINO\n");
 990         if (debug)
 991                 printf("Truncating and freeing ino %ju, nlink %d, mode %o\n",
 992                     (uintmax_t)ino, DIP(dp, di_nlink), DIP(dp, di_mode));
 993
 994         /* We are freeing an inode or directory. */
 995         if ((DIP(dp, di_mode) & IFMT) == IFDIR)
 996                 ino_visit(dp, ino, ino_free_children, 0);
 997         DIP_SET(dp, di_nlink, 0);
 998         ino_visit(dp, ino, blk_free_visit, VISIT_EXT | VISIT_INDIR);
 999         /* Here we have to clear the inode and release any blocks it holds. */
1000         gen = DIP(dp, di_gen);
1001         if (fs->fs_magic == FS_UFS1_MAGIC)
1002                 bzero(dp, sizeof(struct ufs1_dinode));
1003         else
1004                 bzero(dp, sizeof(struct ufs2_dinode));
1005         DIP_SET(dp, di_gen, gen);
1006         inodirty(ip);
1007         ino_free(ino, mode);
1008         return;
1009 }
1010
1011 /*
1012  * Adjust an inode's link count down by one when a directory goes away.
1013  */
1014 static void
1015 ino_decr(ino_t ino)
1016 {
1017         struct inode ip;
1018         union dinode *dp;
1019         int reqlink;
1020         int nlink;
1021         int mode;
1022
1023         ginode(ino, &ip);
1024         dp = ip.i_dp;
1025         nlink = DIP(dp, di_nlink);
1026         mode = DIP(dp, di_mode);
1027         if (nlink < 1)
1028                 err_suj("Inode %d link count %d invalid\n", ino, nlink);
1029         if (mode == 0)
1030                 err_suj("Inode %d has a link of %d with 0 mode\n", ino, nlink);
1031         nlink--;
1032         if ((mode & IFMT) == IFDIR)
1033                 reqlink = 2;
1034         else
1035                 reqlink = 1;
1036         if (nlink < reqlink) {
1037                 if (debug)
1038                         printf("ino %ju not enough links to live %d < %d\n",
1039                             (uintmax_t)ino, nlink, reqlink);
1040                 ino_reclaim(&ip, ino, mode);
1041                 irelse(&ip);
1042                 return;
1043         }
1044         DIP_SET(dp, di_nlink, nlink);
1045         inodirty(&ip);
1046         irelse(&ip);
1047 }
1048
1049 /*
1050  * Adjust the inode link count to 'nlink'.  If the count reaches zero
1051  * free it.
1052  */
1053 static void
1054 ino_adjust(struct suj_ino *sino)
1055 {
1056         struct jrefrec *rrec;
1057         struct suj_rec *srec;
1058         struct suj_ino *stmp;
1059         union dinode *dp;
1060         struct inode ip;
1061         nlink_t nlink;
1062         nlink_t reqlink;
1063         int recmode;
1064         int isdot;
1065         int mode;
1066         ino_t ino;
1067
1068         nlink = sino->si_nlink;
1069         ino = sino->si_ino;
1070         mode = sino->si_mode & IFMT;
1071         /*
1072          * If it's a directory with no dot links, it was truncated before
1073          * the name was cleared.  We need to clear the dirent that
1074          * points at it.
1075          */
1076         if (mode == IFDIR && nlink == 1 && sino->si_dotlinks == 0) {
1077                 sino->si_nlink = nlink = 0;
1078                 TAILQ_FOREACH(srec, &sino->si_recs, sr_next) {
1079                         rrec = (struct jrefrec *)srec->sr_rec;
1080                         if (ino_isat(rrec->jr_parent, rrec->jr_diroff, ino,
1081                             &recmode, &isdot) == 0)
1082                                 continue;
1083                         ino_clrat(rrec->jr_parent, rrec->jr_diroff, ino);
1084                         break;
1085                 }
1086                 if (srec == NULL)
1087                         errx(1, "Directory %ju name not found", (uintmax_t)ino);
1088         }
1089         /*
1090          * If it's a directory with no real names pointing to it go ahead
1091          * and truncate it.  This will free any children.
1092          */
1093         if (mode == IFDIR && nlink - sino->si_dotlinks == 0) {
1094                 sino->si_nlink = nlink = 0;
1095                 /*
1096                  * Mark any .. links so they know not to free this inode
1097                  * when they are removed.
1098                  */
1099                 TAILQ_FOREACH(srec, &sino->si_recs, sr_next) {
1100                         rrec = (struct jrefrec *)srec->sr_rec;
1101                         if (rrec->jr_diroff == DOTDOT_OFFSET) {
1102                                 stmp = ino_lookup(rrec->jr_parent, 0);
1103                                 if (stmp)
1104                                         ino_setskip(stmp, ino);
1105                         }
1106                 }
1107         }
1108         ginode(ino, &ip);
1109         dp = ip.i_dp;
1110         mode = DIP(dp, di_mode) & IFMT;
1111         if (nlink > UFS_LINK_MAX)
1112                 err_suj("ino %ju nlink manipulation error, new %ju, old %d\n",
1113                     (uintmax_t)ino, (uintmax_t)nlink, DIP(dp, di_nlink));
1114         if (debug)
1115                printf("Adjusting ino %ju, nlink %ju, old link %d lastmode %o\n",
1116                     (uintmax_t)ino, (uintmax_t)nlink, DIP(dp, di_nlink),
1117                     sino->si_mode);
1118         if (mode == 0) {
1119                 if (debug)
1120                         printf("ino %ju, zero inode freeing bitmap\n",
1121                             (uintmax_t)ino);
1122                 ino_free(ino, sino->si_mode);
1123                 irelse(&ip);
1124                 return;
1125         }
1126         /* XXX Should be an assert? */
1127         if (mode != sino->si_mode && debug)
1128                 printf("ino %ju, mode %o != %o\n",
1129                     (uintmax_t)ino, mode, sino->si_mode);
1130         if ((mode & IFMT) == IFDIR)
1131                 reqlink = 2;
1132         else
1133                 reqlink = 1;
1134         /* If the inode doesn't have enough links to live, free it. */
1135         if (nlink < reqlink) {
1136                 if (debug)
1137                         printf("ino %ju not enough links to live %ju < %ju\n",
1138                             (uintmax_t)ino, (uintmax_t)nlink,
1139                             (uintmax_t)reqlink);
1140                 ino_reclaim(&ip, ino, mode);
1141                 irelse(&ip);
1142                 return;
1143         }
1144         /* If required write the updated link count. */
1145         if (DIP(dp, di_nlink) == nlink) {
1146                 if (debug)
1147                         printf("ino %ju, link matches, skipping.\n",
1148                             (uintmax_t)ino);
1149                 irelse(&ip);
1150                 return;
1151         }
1152         DIP_SET(dp, di_nlink, nlink);
1153         inodirty(&ip);
1154         irelse(&ip);
1155 }
1156
1157 /*
1158  * Truncate some or all blocks in an indirect, freeing any that are required
1159  * and zeroing the indirect.
1160  */
1161 static void
1162 indir_trunc(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, ufs_lbn_t lastlbn,
1163         union dinode *dp)
1164 {
1165         struct bufarea *bp;
1166         ufs_lbn_t lbnadd;
1167         ufs2_daddr_t nblk;
1168         ufs_lbn_t next;
1169         ufs_lbn_t nlbn;
1170         int isdirty;
1171         int level;
1172         int i;
1173
1174         if (blk == 0)
1175                 return;
1176         isdirty = 0;
1177         level = lbn_level(lbn);
1178         if (level == -1)
1179                 err_suj("Invalid level for lbn %jd\n", lbn);
1180         lbnadd = 1;
1181         for (i = level; i > 0; i--)
1182                 lbnadd *= NINDIR(fs);
1183         bp = getdatablk(blk, fs->fs_bsize, BT_LEVEL1 + level);
1184         if (bp->b_errs != 0)
1185                 err_suj("indir_trunc: UNRECOVERABLE I/O ERROR");
1186         for (i = 0; i < NINDIR(fs); i++) {
1187                 if ((nblk = IBLK(bp, i)) == 0)
1188                         continue;
1189                 if (level != 0) {
1190                         nlbn = (lbn + 1) - (i * lbnadd);
1191                         /*
1192                          * Calculate the lbn of the next indirect to
1193                          * determine if any of this indirect must be
1194                          * reclaimed.
1195                          */
1196                         next = -(lbn + level) + ((i+1) * lbnadd);
1197                         if (next <= lastlbn)
1198                                 continue;
1199                         indir_trunc(ino, nlbn, nblk, lastlbn, dp);
1200                         /* If all of this indirect was reclaimed, free it. */
1201                         nlbn = next - lbnadd;
1202                         if (nlbn < lastlbn)
1203                                 continue;
1204                 } else {
1205                         nlbn = -lbn + i * lbnadd;
1206                         if (nlbn < lastlbn)
1207                                 continue;
1208                 }
1209                 isdirty = 1;
1210                 blk_free(nblk, 0, fs->fs_frag);
1211                 IBLK_SET(bp, i, 0);
1212         }
1213         if (isdirty)
1214                 dirty(bp);
1215         brelse(bp);
1216 }
1217
1218 /*
1219  * Truncate an inode to the minimum of the given size or the last populated
1220  * block after any over size have been discarded.  The kernel would allocate
1221  * the last block in the file but fsck does not and neither do we.  This
1222  * code never extends files, only shrinks them.
1223  */
1224 static void
1225 ino_trunc(ino_t ino, off_t size)
1226 {
1227         struct inode ip;
1228         union dinode *dp;
1229         struct bufarea *bp;
1230         ufs2_daddr_t bn;
1231         uint64_t totalfrags;
1232         ufs_lbn_t nextlbn;
1233         ufs_lbn_t lastlbn;
1234         ufs_lbn_t tmpval;
1235         ufs_lbn_t lbn;
1236         ufs_lbn_t i;
1237         int blksize, frags;
1238         off_t cursize;
1239         off_t off;
1240         int mode;
1241
1242         ginode(ino, &ip);
1243         dp = ip.i_dp;
1244         mode = DIP(dp, di_mode) & IFMT;
1245         cursize = DIP(dp, di_size);
1246         if (debug)
1247                 printf("Truncating ino %ju, mode %o to size %jd from size %jd\n",
1248                     (uintmax_t)ino, mode, size, cursize);
1249
1250         /* Skip datablocks for short links and devices. */
1251         if (mode == 0 || mode == IFBLK || mode == IFCHR ||
1252             (mode == IFLNK && cursize < fs->fs_maxsymlinklen)) {
1253                 irelse(&ip);
1254                 return;
1255         }
1256         /* Don't extend. */
1257         if (size > cursize) {
1258                 irelse(&ip);
1259                 return;
1260         }
1261         if ((DIP(dp, di_flags) & SF_SNAPSHOT) != 0) {
1262                 if (size > 0)
1263                         err_suj("Partial truncation of ino %ju snapshot file\n",
1264                             (uintmax_t)ino);
1265         }
1266         lastlbn = lblkno(fs, blkroundup(fs, size));
1267         for (i = lastlbn; i < UFS_NDADDR; i++) {
1268                 if ((bn = DIP(dp, di_db[i])) == 0)
1269                         continue;
1270                 blksize = sblksize(fs, cursize, i);
1271                 blk_free(bn, 0, numfrags(fs, blksize));
1272                 DIP_SET(dp, di_db[i], 0);
1273         }
1274         /*
1275          * Follow indirect blocks, freeing anything required.
1276          */
1277         for (i = 0, tmpval = NINDIR(fs), lbn = UFS_NDADDR; i < UFS_NIADDR; i++,
1278             lbn = nextlbn) {
1279                 nextlbn = lbn + tmpval;
1280                 tmpval *= NINDIR(fs);
1281                 /* If we're not freeing any in this indirect range skip it. */
1282                 if (lastlbn >= nextlbn)
1283                         continue;
1284                 if (DIP(dp, di_ib[i]) == 0)
1285                         continue;
1286                 indir_trunc(ino, -lbn - i, DIP(dp, di_ib[i]), lastlbn, dp);
1287                 /* If we freed everything in this indirect free the indir. */
1288                 if (lastlbn > lbn)
1289                         continue;
1290                 blk_free(DIP(dp, di_ib[i]), 0, fs->fs_frag);
1291                 DIP_SET(dp, di_ib[i], 0);
1292         }
1293         /*
1294          * Now that we've freed any whole blocks that exceed the desired
1295          * truncation size, figure out how many blocks remain and what the
1296          * last populated lbn is.  We will set the size to this last lbn
1297          * rather than worrying about allocating the final lbn as the kernel
1298          * would've done.  This is consistent with normal fsck behavior.
1299          */
1300         visitlbn = 0;
1301         totalfrags = ino_visit(dp, ino, null_visit, VISIT_INDIR | VISIT_EXT);
1302         if (size > lblktosize(fs, visitlbn + 1))
1303                 size = lblktosize(fs, visitlbn + 1);
1304         /*
1305          * If we're truncating direct blocks we have to adjust frags
1306          * accordingly.
1307          */
1308         if (visitlbn < UFS_NDADDR && totalfrags) {
1309                 long oldspace, newspace;
1310
1311                 bn = DIP(dp, di_db[visitlbn]);
1312                 if (bn == 0)
1313                         err_suj("Bad blk at ino %ju lbn %jd\n",
1314                             (uintmax_t)ino, visitlbn);
1315                 oldspace = sblksize(fs, cursize, visitlbn);
1316                 newspace = sblksize(fs, size, visitlbn);
1317                 if (oldspace != newspace) {
1318                         bn += numfrags(fs, newspace);
1319                         frags = numfrags(fs, oldspace - newspace);
1320                         blk_free(bn, 0, frags);
1321                         totalfrags -= frags;
1322                 }
1323         }
1324         DIP_SET(dp, di_blocks, fsbtodb(fs, totalfrags));
1325         DIP_SET(dp, di_size, size);
1326         inodirty(&ip);
1327         /*
1328          * If we've truncated into the middle of a block or frag we have
1329          * to zero it here.  Otherwise the file could extend into
1330          * uninitialized space later.
1331          */
1332         off = blkoff(fs, size);
1333         if (off && DIP(dp, di_mode) != IFDIR) {
1334                 long clrsize;
1335
1336                 bn = ino_blkatoff(dp, ino, visitlbn, &frags, NULL);
1337                 if (bn == 0)
1338                         err_suj("Block missing from ino %ju at lbn %jd\n",
1339                             (uintmax_t)ino, visitlbn);
1340                 clrsize = frags * fs->fs_fsize;
1341                 bp = getdatablk(bn, clrsize, BT_DATA);
1342                 if (bp->b_errs != 0)
1343                         err_suj("ino_trunc: UNRECOVERABLE I/O ERROR");
1344                 clrsize -= off;
1345                 bzero(&bp->b_un.b_buf[off], clrsize);
1346                 dirty(bp);
1347                 brelse(bp);
1348         }
1349         irelse(&ip);
1350         return;
1351 }
1352
1353 /*
1354  * Process records available for one inode and determine whether the
1355  * link count is correct or needs adjusting.
1356  */
1357 static void
1358 ino_check(struct suj_ino *sino)
1359 {
1360         struct suj_rec *srec;
1361         struct jrefrec *rrec;
1362         nlink_t dotlinks;
1363         nlink_t newlinks;
1364         nlink_t removes;
1365         nlink_t nlink;
1366         ino_t ino;
1367         int isdot;
1368         int isat;
1369         int mode;
1370
1371         if (sino->si_hasrecs == 0)
1372                 return;
1373         ino = sino->si_ino;
1374         rrec = (struct jrefrec *)TAILQ_FIRST(&sino->si_recs)->sr_rec;
1375         nlink = rrec->jr_nlink;
1376         newlinks = 0;
1377         dotlinks = 0;
1378         removes = sino->si_nlinkadj;
1379         TAILQ_FOREACH(srec, &sino->si_recs, sr_next) {
1380                 rrec = (struct jrefrec *)srec->sr_rec;
1381                 isat = ino_isat(rrec->jr_parent, rrec->jr_diroff,
1382                     rrec->jr_ino, &mode, &isdot);
1383                 if (isat && (mode & IFMT) != (rrec->jr_mode & IFMT))
1384                         err_suj("Inode mode/directory type mismatch %o != %o\n",
1385                             mode, rrec->jr_mode);
1386                 if (debug)
1387                         printf("jrefrec: op %d ino %ju, nlink %ju, parent %ju, "
1388                             "diroff %jd, mode %o, isat %d, isdot %d\n",
1389                             rrec->jr_op, (uintmax_t)rrec->jr_ino,
1390                             (uintmax_t)rrec->jr_nlink,
1391                             (uintmax_t)rrec->jr_parent,
1392                             (uintmax_t)rrec->jr_diroff,
1393                             rrec->jr_mode, isat, isdot);
1394                 mode = rrec->jr_mode & IFMT;
1395                 if (rrec->jr_op == JOP_REMREF)
1396                         removes++;
1397                 newlinks += isat;
1398                 if (isdot)
1399                         dotlinks += isat;
1400         }
1401         /*
1402          * The number of links that remain are the starting link count
1403          * subtracted by the total number of removes with the total
1404          * links discovered back in.  An incomplete remove thus
1405          * makes no change to the link count but an add increases
1406          * by one.
1407          */
1408         if (debug)
1409                 printf(
1410                     "ino %ju nlink %ju newlinks %ju removes %ju dotlinks %ju\n",
1411                     (uintmax_t)ino, (uintmax_t)nlink, (uintmax_t)newlinks,
1412                     (uintmax_t)removes, (uintmax_t)dotlinks);
1413         nlink += newlinks;
1414         nlink -= removes;
1415         sino->si_linkadj = 1;
1416         sino->si_nlink = nlink;
1417         sino->si_dotlinks = dotlinks;
1418         sino->si_mode = mode;
1419         ino_adjust(sino);
1420 }
1421
1422 /*
1423  * Process records available for one block and determine whether it is
1424  * still allocated and whether the owning inode needs to be updated or
1425  * a free completed.
1426  */
1427 static void
1428 blk_check(struct suj_blk *sblk)
1429 {
1430         struct suj_rec *srec;
1431         struct jblkrec *brec;
1432         struct suj_ino *sino;
1433         ufs2_daddr_t blk;
1434         int mask;
1435         int frags;
1436         int isat;
1437
1438         /*
1439          * Each suj_blk actually contains records for any fragments in that
1440          * block.  As a result we must evaluate each record individually.
1441          */
1442         sino = NULL;
1443         TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) {
1444                 brec = (struct jblkrec *)srec->sr_rec;
1445                 frags = brec->jb_frags;
1446                 blk = brec->jb_blkno + brec->jb_oldfrags;
1447                 isat = blk_isat(brec->jb_ino, brec->jb_lbn, blk, &frags);
1448                 if (sino == NULL || sino->si_ino != brec->jb_ino) {
1449                         sino = ino_lookup(brec->jb_ino, 1);
1450                         sino->si_blkadj = 1;
1451                 }
1452                 if (debug)
1453                         printf("op %d blk %jd ino %ju lbn %jd frags %d isat %d (%d)\n",
1454                             brec->jb_op, blk, (uintmax_t)brec->jb_ino,
1455                             brec->jb_lbn, brec->jb_frags, isat, frags);
1456                 /*
1457                  * If we found the block at this address we still have to
1458                  * determine if we need to free the tail end that was
1459                  * added by adding contiguous fragments from the same block.
1460                  */
1461                 if (isat == 1) {
1462                         if (frags == brec->jb_frags)
1463                                 continue;
1464                         mask = blk_freemask(blk, brec->jb_ino, brec->jb_lbn,
1465                             brec->jb_frags);
1466                         mask >>= frags;
1467                         blk += frags;
1468                         frags = brec->jb_frags - frags;
1469                         blk_free(blk, mask, frags);
1470                         continue;
1471                 }
1472                 /*
1473                  * The block wasn't found, attempt to free it.  It won't be
1474                  * freed if it was actually reallocated.  If this was an
1475                  * allocation we don't want to follow indirects as they
1476                  * may not be written yet.  Any children of the indirect will
1477                  * have their own records.  If it's a free we need to
1478                  * recursively free children.
1479                  */
1480                 blk_free_lbn(blk, brec->jb_ino, brec->jb_lbn, brec->jb_frags,
1481                     brec->jb_op == JOP_FREEBLK);
1482         }
1483 }
1484
1485 /*
1486  * Walk the list of inode records for this cg and resolve moved and duplicate
1487  * inode references now that we have a complete picture.
1488  */
1489 static void
1490 cg_build(struct suj_cg *sc)
1491 {
1492         struct suj_ino *sino;
1493         int i;
1494
1495         for (i = 0; i < HASHSIZE; i++)
1496                 LIST_FOREACH(sino, &sc->sc_inohash[i], si_next)
1497                         ino_build(sino);
1498 }
1499
1500 /*
1501  * Handle inodes requiring truncation.  This must be done prior to
1502  * looking up any inodes in directories.
1503  */
1504 static void
1505 cg_trunc(struct suj_cg *sc)
1506 {
1507         struct suj_ino *sino;
1508         int i;
1509
1510         for (i = 0; i < HASHSIZE; i++) {
1511                 LIST_FOREACH(sino, &sc->sc_inohash[i], si_next) {
1512                         if (sino->si_trunc) {
1513                                 ino_trunc(sino->si_ino,
1514                                     sino->si_trunc->jt_size);
1515                                 sino->si_blkadj = 0;
1516                                 sino->si_trunc = NULL;
1517                         }
1518                         if (sino->si_blkadj)
1519                                 ino_adjblks(sino);
1520                 }
1521         }
1522 }
1523
1524 static void
1525 cg_adj_blk(struct suj_cg *sc)
1526 {
1527         struct suj_ino *sino;
1528         int i;
1529
1530         for (i = 0; i < HASHSIZE; i++) {
1531                 LIST_FOREACH(sino, &sc->sc_inohash[i], si_next) {
1532                         if (sino->si_blkadj)
1533                                 ino_adjblks(sino);
1534                 }
1535         }
1536 }
1537
1538 /*
1539  * Free any partially allocated blocks and then resolve inode block
1540  * counts.
1541  */
1542 static void
1543 cg_check_blk(struct suj_cg *sc)
1544 {
1545         struct suj_blk *sblk;
1546         int i;
1547
1548
1549         for (i = 0; i < HASHSIZE; i++)
1550                 LIST_FOREACH(sblk, &sc->sc_blkhash[i], sb_next)
1551                         blk_check(sblk);
1552 }
1553
1554 /*
1555  * Walk the list of inode records for this cg, recovering any
1556  * changes which were not complete at the time of crash.
1557  */
1558 static void
1559 cg_check_ino(struct suj_cg *sc)
1560 {
1561         struct suj_ino *sino;
1562         int i;
1563
1564         for (i = 0; i < HASHSIZE; i++)
1565                 LIST_FOREACH(sino, &sc->sc_inohash[i], si_next)
1566                         ino_check(sino);
1567 }
1568
1569 static void
1570 cg_apply(void (*apply)(struct suj_cg *))
1571 {
1572         struct suj_cg *scg;
1573         int i;
1574
1575         for (i = 0; i < HASHSIZE; i++)
1576                 LIST_FOREACH(scg, &cghash[i], sc_next)
1577                         apply(scg);
1578 }
1579
1580 /*
1581  * Process the unlinked but referenced file list.  Freeing all inodes.
1582  */
1583 static void
1584 ino_unlinked(void)
1585 {
1586         struct inode ip;
1587         union dinode *dp;
1588         uint16_t mode;
1589         ino_t inon;
1590         ino_t ino;
1591
1592         ino = fs->fs_sujfree;
1593         fs->fs_sujfree = 0;
1594         while (ino != 0) {
1595                 ginode(ino, &ip);
1596                 dp = ip.i_dp;
1597                 mode = DIP(dp, di_mode) & IFMT;
1598                 inon = DIP(dp, di_freelink);
1599                 DIP_SET(dp, di_freelink, 0);
1600                 inodirty(&ip);
1601                 /*
1602                  * XXX Should this be an errx?
1603                  */
1604                 if (DIP(dp, di_nlink) == 0) {
1605                         if (debug)
1606                                 printf("Freeing unlinked ino %ju mode %o\n",
1607                                     (uintmax_t)ino, mode);
1608                         ino_reclaim(&ip, ino, mode);
1609                 } else if (debug)
1610                         printf("Skipping ino %ju mode %o with link %d\n",
1611                             (uintmax_t)ino, mode, DIP(dp, di_nlink));
1612                 ino = inon;
1613                 irelse(&ip);
1614         }
1615 }
1616
1617 /*
1618  * Append a new record to the list of records requiring processing.
1619  */
1620 static void
1621 ino_append(union jrec *rec)
1622 {
1623         struct jrefrec *refrec;
1624         struct jmvrec *mvrec;
1625         struct suj_ino *sino;
1626         struct suj_rec *srec;
1627
1628         mvrec = &rec->rec_jmvrec;
1629         refrec = &rec->rec_jrefrec;
1630         if (debug && mvrec->jm_op == JOP_MVREF)
1631                 printf("ino move: ino %ju, parent %ju, "
1632                     "diroff %jd, oldoff %jd\n",
1633                     (uintmax_t)mvrec->jm_ino, (uintmax_t)mvrec->jm_parent,
1634                     (uintmax_t)mvrec->jm_newoff, (uintmax_t)mvrec->jm_oldoff);
1635         else if (debug &&
1636             (refrec->jr_op == JOP_ADDREF || refrec->jr_op == JOP_REMREF))
1637                 printf("ino ref: op %d, ino %ju, nlink %ju, "
1638                     "parent %ju, diroff %jd\n",
1639                     refrec->jr_op, (uintmax_t)refrec->jr_ino,
1640                     (uintmax_t)refrec->jr_nlink,
1641                     (uintmax_t)refrec->jr_parent, (uintmax_t)refrec->jr_diroff);
1642         sino = ino_lookup(((struct jrefrec *)rec)->jr_ino, 1);
1643         sino->si_hasrecs = 1;
1644         srec = errmalloc(sizeof(*srec));
1645         srec->sr_rec = rec;
1646         TAILQ_INSERT_TAIL(&sino->si_newrecs, srec, sr_next);
1647 }
1648
1649 /*
1650  * Add a reference adjustment to the sino list and eliminate dups.  The
1651  * primary loop in ino_build_ref() checks for dups but new ones may be
1652  * created as a result of offset adjustments.
1653  */
1654 static void
1655 ino_add_ref(struct suj_ino *sino, struct suj_rec *srec)
1656 {
1657         struct jrefrec *refrec;
1658         struct suj_rec *srn;
1659         struct jrefrec *rrn;
1660
1661         refrec = (struct jrefrec *)srec->sr_rec;
1662         /*
1663          * We walk backwards so that the oldest link count is preserved.  If
1664          * an add record conflicts with a remove keep the remove.  Redundant
1665          * removes are eliminated in ino_build_ref.  Otherwise we keep the
1666          * oldest record at a given location.
1667          */
1668         for (srn = TAILQ_LAST(&sino->si_recs, srechd); srn;
1669             srn = TAILQ_PREV(srn, srechd, sr_next)) {
1670                 rrn = (struct jrefrec *)srn->sr_rec;
1671                 if (rrn->jr_parent != refrec->jr_parent ||
1672                     rrn->jr_diroff != refrec->jr_diroff)
1673                         continue;
1674                 if (rrn->jr_op == JOP_REMREF || refrec->jr_op == JOP_ADDREF) {
1675                         rrn->jr_mode = refrec->jr_mode;
1676                         return;
1677                 }
1678                 /*
1679                  * Adding a remove.
1680                  *
1681                  * Replace the record in place with the old nlink in case
1682                  * we replace the head of the list.  Abandon srec as a dup.
1683                  */
1684                 refrec->jr_nlink = rrn->jr_nlink;
1685                 srn->sr_rec = srec->sr_rec;
1686                 return;
1687         }
1688         TAILQ_INSERT_TAIL(&sino->si_recs, srec, sr_next);
1689 }
1690
1691 /*
1692  * Create a duplicate of a reference at a previous location.
1693  */
1694 static void
1695 ino_dup_ref(struct suj_ino *sino, struct jrefrec *refrec, off_t diroff)
1696 {
1697         struct jrefrec *rrn;
1698         struct suj_rec *srn;
1699
1700         rrn = errmalloc(sizeof(*refrec));
1701         *rrn = *refrec;
1702         rrn->jr_op = JOP_ADDREF;
1703         rrn->jr_diroff = diroff;
1704         srn = errmalloc(sizeof(*srn));
1705         srn->sr_rec = (union jrec *)rrn;
1706         ino_add_ref(sino, srn);
1707 }
1708
1709 /*
1710  * Add a reference to the list at all known locations.  We follow the offset
1711  * changes for a single instance and create duplicate add refs at each so
1712  * that we can tolerate any version of the directory block.  Eliminate
1713  * removes which collide with adds that are seen in the journal.  They should
1714  * not adjust the link count down.
1715  */
1716 static void
1717 ino_build_ref(struct suj_ino *sino, struct suj_rec *srec)
1718 {
1719         struct jrefrec *refrec;
1720         struct jmvrec *mvrec;
1721         struct suj_rec *srp;
1722         struct suj_rec *srn;
1723         struct jrefrec *rrn;
1724         off_t diroff;
1725
1726         refrec = (struct jrefrec *)srec->sr_rec;
1727         /*
1728          * Search for a mvrec that matches this offset.  Whether it's an add
1729          * or a remove we can delete the mvref after creating a dup record in
1730          * the old location.
1731          */
1732         if (!TAILQ_EMPTY(&sino->si_movs)) {
1733                 diroff = refrec->jr_diroff;
1734                 for (srn = TAILQ_LAST(&sino->si_movs, srechd); srn; srn = srp) {
1735                         srp = TAILQ_PREV(srn, srechd, sr_next);
1736                         mvrec = (struct jmvrec *)srn->sr_rec;
1737                         if (mvrec->jm_parent != refrec->jr_parent ||
1738                             mvrec->jm_newoff != diroff)
1739                                 continue;
1740                         diroff = mvrec->jm_oldoff;
1741                         TAILQ_REMOVE(&sino->si_movs, srn, sr_next);
1742                         free(srn);
1743                         ino_dup_ref(sino, refrec, diroff);
1744                 }
1745         }
1746         /*
1747          * If a remove wasn't eliminated by an earlier add just append it to
1748          * the list.
1749          */
1750         if (refrec->jr_op == JOP_REMREF) {
1751                 ino_add_ref(sino, srec);
1752                 return;
1753         }
1754         /*
1755          * Walk the list of records waiting to be added to the list.  We
1756          * must check for moves that apply to our current offset and remove
1757          * them from the list.  Remove any duplicates to eliminate removes
1758          * with corresponding adds.
1759          */
1760         TAILQ_FOREACH_SAFE(srn, &sino->si_newrecs, sr_next, srp) {
1761                 switch (srn->sr_rec->rec_jrefrec.jr_op) {
1762                 case JOP_ADDREF:
1763                         /*
1764                          * This should actually be an error we should
1765                          * have a remove for every add journaled.
1766                          */
1767                         rrn = (struct jrefrec *)srn->sr_rec;
1768                         if (rrn->jr_parent != refrec->jr_parent ||
1769                             rrn->jr_diroff != refrec->jr_diroff)
1770                                 break;
1771                         TAILQ_REMOVE(&sino->si_newrecs, srn, sr_next);
1772                         break;
1773                 case JOP_REMREF:
1774                         /*
1775                          * Once we remove the current iteration of the
1776                          * record at this address we're done.
1777                          */
1778                         rrn = (struct jrefrec *)srn->sr_rec;
1779                         if (rrn->jr_parent != refrec->jr_parent ||
1780                             rrn->jr_diroff != refrec->jr_diroff)
1781                                 break;
1782                         TAILQ_REMOVE(&sino->si_newrecs, srn, sr_next);
1783                         ino_add_ref(sino, srec);
1784                         return;
1785                 case JOP_MVREF:
1786                         /*
1787                          * Update our diroff based on any moves that match
1788                          * and remove the move.
1789                          */
1790                         mvrec = (struct jmvrec *)srn->sr_rec;
1791                         if (mvrec->jm_parent != refrec->jr_parent ||
1792                             mvrec->jm_oldoff != refrec->jr_diroff)
1793                                 break;
1794                         ino_dup_ref(sino, refrec, mvrec->jm_oldoff);
1795                         refrec->jr_diroff = mvrec->jm_newoff;
1796                         TAILQ_REMOVE(&sino->si_newrecs, srn, sr_next);
1797                         break;
1798                 default:
1799                         err_suj("ino_build_ref: Unknown op %d\n",
1800                             srn->sr_rec->rec_jrefrec.jr_op);
1801                 }
1802         }
1803         ino_add_ref(sino, srec);
1804 }
1805
1806 /*
1807  * Walk the list of new records and add them in-order resolving any
1808  * dups and adjusted offsets.
1809  */
1810 static void
1811 ino_build(struct suj_ino *sino)
1812 {
1813         struct suj_rec *srec;
1814
1815         while ((srec = TAILQ_FIRST(&sino->si_newrecs)) != NULL) {
1816                 TAILQ_REMOVE(&sino->si_newrecs, srec, sr_next);
1817                 switch (srec->sr_rec->rec_jrefrec.jr_op) {
1818                 case JOP_ADDREF:
1819                 case JOP_REMREF:
1820                         ino_build_ref(sino, srec);
1821                         break;
1822                 case JOP_MVREF:
1823                         /*
1824                          * Add this mvrec to the queue of pending mvs.
1825                          */
1826                         TAILQ_INSERT_TAIL(&sino->si_movs, srec, sr_next);
1827                         break;
1828                 default:
1829                         err_suj("ino_build: Unknown op %d\n",
1830                             srec->sr_rec->rec_jrefrec.jr_op);
1831                 }
1832         }
1833         if (TAILQ_EMPTY(&sino->si_recs))
1834                 sino->si_hasrecs = 0;
1835 }
1836
1837 /*
1838  * Modify journal records so they refer to the base block number
1839  * and a start and end frag range.  This is to facilitate the discovery
1840  * of overlapping fragment allocations.
1841  */
1842 static void
1843 blk_build(struct jblkrec *blkrec)
1844 {
1845         struct suj_rec *srec;
1846         struct suj_blk *sblk;
1847         struct jblkrec *blkrn;
1848         ufs2_daddr_t blk;
1849         int frag;
1850
1851         if (debug)
1852                 printf("blk_build: op %d blkno %jd frags %d oldfrags %d "
1853                     "ino %ju lbn %jd\n",
1854                     blkrec->jb_op, (uintmax_t)blkrec->jb_blkno,
1855                     blkrec->jb_frags, blkrec->jb_oldfrags,
1856                     (uintmax_t)blkrec->jb_ino, (uintmax_t)blkrec->jb_lbn);
1857
1858         blk = blknum(fs, blkrec->jb_blkno);
1859         frag = fragnum(fs, blkrec->jb_blkno);
1860         sblk = blk_lookup(blk, 1);
1861         /*
1862          * Rewrite the record using oldfrags to indicate the offset into
1863          * the block.  Leave jb_frags as the actual allocated count.
1864          */
1865         blkrec->jb_blkno -= frag;
1866         blkrec->jb_oldfrags = frag;
1867         if (blkrec->jb_oldfrags + blkrec->jb_frags > fs->fs_frag)
1868                 err_suj("Invalid fragment count %d oldfrags %d\n",
1869                     blkrec->jb_frags, frag);
1870         /*
1871          * Detect dups.  If we detect a dup we always discard the oldest
1872          * record as it is superseded by the new record.  This speeds up
1873          * later stages but also eliminates free records which are used
1874          * to indicate that the contents of indirects can be trusted.
1875          */
1876         TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) {
1877                 blkrn = (struct jblkrec *)srec->sr_rec;
1878                 if (blkrn->jb_ino != blkrec->jb_ino ||
1879                     blkrn->jb_lbn != blkrec->jb_lbn ||
1880                     blkrn->jb_blkno != blkrec->jb_blkno ||
1881                     blkrn->jb_frags != blkrec->jb_frags ||
1882                     blkrn->jb_oldfrags != blkrec->jb_oldfrags)
1883                         continue;
1884                 if (debug)
1885                         printf("Removed dup.\n");
1886                 /* Discard the free which is a dup with an alloc. */
1887                 if (blkrec->jb_op == JOP_FREEBLK)
1888                         return;
1889                 TAILQ_REMOVE(&sblk->sb_recs, srec, sr_next);
1890                 free(srec);
1891                 break;
1892         }
1893         srec = errmalloc(sizeof(*srec));
1894         srec->sr_rec = (union jrec *)blkrec;
1895         TAILQ_INSERT_TAIL(&sblk->sb_recs, srec, sr_next);
1896 }
1897
1898 static void
1899 ino_build_trunc(struct jtrncrec *rec)
1900 {
1901         struct suj_ino *sino;
1902
1903         if (debug)
1904                 printf("ino_build_trunc: op %d ino %ju, size %jd\n",
1905                     rec->jt_op, (uintmax_t)rec->jt_ino,
1906                     (uintmax_t)rec->jt_size);
1907         sino = ino_lookup(rec->jt_ino, 1);
1908         if (rec->jt_op == JOP_SYNC) {
1909                 sino->si_trunc = NULL;
1910                 return;
1911         }
1912         if (sino->si_trunc == NULL || sino->si_trunc->jt_size > rec->jt_size)
1913                 sino->si_trunc = rec;
1914 }
1915
1916 /*
1917  * Build up tables of the operations we need to recover.
1918  */
1919 static void
1920 suj_build(void)
1921 {
1922         struct suj_seg *seg;
1923         union jrec *rec;
1924         int off;
1925         int i;
1926
1927         TAILQ_FOREACH(seg, &allsegs, ss_next) {
1928                 if (debug)
1929                         printf("seg %jd has %d records, oldseq %jd.\n",
1930                             seg->ss_rec.jsr_seq, seg->ss_rec.jsr_cnt,
1931                             seg->ss_rec.jsr_oldest);
1932                 off = 0;
1933                 rec = (union jrec *)seg->ss_blk;
1934                 for (i = 0; i < seg->ss_rec.jsr_cnt; off += JREC_SIZE, rec++) {
1935                         /* skip the segrec. */
1936                         if ((off % real_dev_bsize) == 0)
1937                                 continue;
1938                         switch (rec->rec_jrefrec.jr_op) {
1939                         case JOP_ADDREF:
1940                         case JOP_REMREF:
1941                         case JOP_MVREF:
1942                                 ino_append(rec);
1943                                 break;
1944                         case JOP_NEWBLK:
1945                         case JOP_FREEBLK:
1946                                 blk_build((struct jblkrec *)rec);
1947                                 break;
1948                         case JOP_TRUNC:
1949                         case JOP_SYNC:
1950                                 ino_build_trunc((struct jtrncrec *)rec);
1951                                 break;
1952                         default:
1953                                 err_suj("Unknown journal operation %d (%d)\n",
1954                                     rec->rec_jrefrec.jr_op, off);
1955                         }
1956                         i++;
1957                 }
1958         }
1959 }
1960
1961 /*
1962  * Prune the journal segments to those we care about based on the
1963  * oldest sequence in the newest segment.  Order the segment list
1964  * based on sequence number.
1965  */
1966 static void
1967 suj_prune(void)
1968 {
1969         struct suj_seg *seg;
1970         struct suj_seg *segn;
1971         uint64_t newseq;
1972         int discard;
1973
1974         if (debug)
1975                 printf("Pruning up to %jd\n", oldseq);
1976         /* First free the expired segments. */
1977         TAILQ_FOREACH_SAFE(seg, &allsegs, ss_next, segn) {
1978                 if (seg->ss_rec.jsr_seq >= oldseq)
1979                         continue;
1980                 TAILQ_REMOVE(&allsegs, seg, ss_next);
1981                 free(seg->ss_blk);
1982                 free(seg);
1983         }
1984         /* Next ensure that segments are ordered properly. */
1985         seg = TAILQ_FIRST(&allsegs);
1986         if (seg == NULL) {
1987                 if (debug)
1988                         printf("Empty journal\n");
1989                 return;
1990         }
1991         newseq = seg->ss_rec.jsr_seq;
1992         for (;;) {
1993                 seg = TAILQ_LAST(&allsegs, seghd);
1994                 if (seg->ss_rec.jsr_seq >= newseq)
1995                         break;
1996                 TAILQ_REMOVE(&allsegs, seg, ss_next);
1997                 TAILQ_INSERT_HEAD(&allsegs, seg, ss_next);
1998                 newseq = seg->ss_rec.jsr_seq;
1999
2000         }
2001         if (newseq != oldseq) {
2002                 TAILQ_FOREACH(seg, &allsegs, ss_next) {
2003                         printf("%jd, ", seg->ss_rec.jsr_seq);
2004                 }
2005                 printf("\n");
2006                 err_suj("Journal file sequence mismatch %jd != %jd\n",
2007                     newseq, oldseq);
2008         }
2009         /*
2010          * The kernel may asynchronously write segments which can create
2011          * gaps in the sequence space.  Throw away any segments after the
2012          * gap as the kernel guarantees only those that are contiguously
2013          * reachable are marked as completed.
2014          */
2015         discard = 0;
2016         TAILQ_FOREACH_SAFE(seg, &allsegs, ss_next, segn) {
2017                 if (!discard && newseq++ == seg->ss_rec.jsr_seq) {
2018                         jrecs += seg->ss_rec.jsr_cnt;
2019                         jbytes += seg->ss_rec.jsr_blocks * real_dev_bsize;
2020                         continue;
2021                 }
2022                 discard = 1;
2023                 if (debug)
2024                         printf("Journal order mismatch %jd != %jd pruning\n",
2025                             newseq-1, seg->ss_rec.jsr_seq);
2026                 TAILQ_REMOVE(&allsegs, seg, ss_next);
2027                 free(seg->ss_blk);
2028                 free(seg);
2029         }
2030         if (debug)
2031                 printf("Processing journal segments from %jd to %jd\n",
2032                     oldseq, newseq-1);
2033 }
2034
2035 /*
2036  * Verify the journal inode before attempting to read records.
2037  */
2038 static int
2039 suj_verifyino(union dinode *dp)
2040 {
2041
2042         if (DIP(dp, di_nlink) != 1) {
2043                 printf("Invalid link count %d for journal inode %ju\n",
2044                     DIP(dp, di_nlink), (uintmax_t)sujino);
2045                 return (-1);
2046         }
2047
2048         if ((DIP(dp, di_flags) & (SF_IMMUTABLE | SF_NOUNLINK)) !=
2049             (SF_IMMUTABLE | SF_NOUNLINK)) {
2050                 printf("Invalid flags 0x%X for journal inode %ju\n",
2051                     DIP(dp, di_flags), (uintmax_t)sujino);
2052                 return (-1);
2053         }
2054
2055         if (DIP(dp, di_mode) != (IFREG | IREAD)) {
2056                 printf("Invalid mode %o for journal inode %ju\n",
2057                     DIP(dp, di_mode), (uintmax_t)sujino);
2058                 return (-1);
2059         }
2060
2061         if (DIP(dp, di_size) < SUJ_MIN) {
2062                 printf("Invalid size %jd for journal inode %ju\n",
2063                     DIP(dp, di_size), (uintmax_t)sujino);
2064                 return (-1);
2065         }
2066
2067         if (DIP(dp, di_modrev) != fs->fs_mtime) {
2068                 printf("Journal timestamp does not match fs mount time\n");
2069                 return (-1);
2070         }
2071
2072         return (0);
2073 }
2074
2075 struct jblocks {
2076         struct jextent *jb_extent;      /* Extent array. */
2077         int             jb_avail;       /* Available extents. */
2078         int             jb_used;        /* Last used extent. */
2079         int             jb_head;        /* Allocator head. */
2080         int             jb_off;         /* Allocator extent offset. */
2081 };
2082 struct jextent {
2083         ufs2_daddr_t    je_daddr;       /* Disk block address. */
2084         int             je_blocks;      /* Disk block count. */
2085 };
2086
2087 static struct jblocks *suj_jblocks;
2088
2089 static struct jblocks *
2090 jblocks_create(void)
2091 {
2092         struct jblocks *jblocks;
2093         int size;
2094
2095         jblocks = errmalloc(sizeof(*jblocks));
2096         jblocks->jb_avail = 10;
2097         jblocks->jb_used = 0;
2098         jblocks->jb_head = 0;
2099         jblocks->jb_off = 0;
2100         size = sizeof(struct jextent) * jblocks->jb_avail;
2101         jblocks->jb_extent = errmalloc(size);
2102         bzero(jblocks->jb_extent, size);
2103
2104         return (jblocks);
2105 }
2106
2107 /*
2108  * Return the next available disk block and the amount of contiguous
2109  * free space it contains.
2110  */
2111 static ufs2_daddr_t
2112 jblocks_next(struct jblocks *jblocks, int bytes, int *actual)
2113 {
2114         struct jextent *jext;
2115         ufs2_daddr_t daddr;
2116         int freecnt;
2117         int blocks;
2118
2119         blocks = btodb(bytes);
2120         jext = &jblocks->jb_extent[jblocks->jb_head];
2121         freecnt = jext->je_blocks - jblocks->jb_off;
2122         if (freecnt == 0) {
2123                 jblocks->jb_off = 0;
2124                 if (++jblocks->jb_head > jblocks->jb_used)
2125                         return (0);
2126                 jext = &jblocks->jb_extent[jblocks->jb_head];
2127                 freecnt = jext->je_blocks;
2128         }
2129         if (freecnt > blocks)
2130                 freecnt = blocks;
2131         *actual = dbtob(freecnt);
2132         daddr = jext->je_daddr + jblocks->jb_off;
2133
2134         return (daddr);
2135 }
2136
2137 /*
2138  * Advance the allocation head by a specified number of bytes, consuming
2139  * one journal segment.
2140  */
2141 static void
2142 jblocks_advance(struct jblocks *jblocks, int bytes)
2143 {
2144
2145         jblocks->jb_off += btodb(bytes);
2146 }
2147
2148 static void
2149 jblocks_destroy(struct jblocks *jblocks)
2150 {
2151
2152         free(jblocks->jb_extent);
2153         free(jblocks);
2154 }
2155
2156 static void
2157 jblocks_add(struct jblocks *jblocks, ufs2_daddr_t daddr, int blocks)
2158 {
2159         struct jextent *jext;
2160         int size;
2161
2162         jext = &jblocks->jb_extent[jblocks->jb_used];
2163         /* Adding the first block. */
2164         if (jext->je_daddr == 0) {
2165                 jext->je_daddr = daddr;
2166                 jext->je_blocks = blocks;
2167                 return;
2168         }
2169         /* Extending the last extent. */
2170         if (jext->je_daddr + jext->je_blocks == daddr) {
2171                 jext->je_blocks += blocks;
2172                 return;
2173         }
2174         /* Adding a new extent. */
2175         if (++jblocks->jb_used == jblocks->jb_avail) {
2176                 jblocks->jb_avail *= 2;
2177                 size = sizeof(struct jextent) * jblocks->jb_avail;
2178                 jext = errmalloc(size);
2179                 bzero(jext, size);
2180                 bcopy(jblocks->jb_extent, jext,
2181                     sizeof(struct jextent) * jblocks->jb_used);
2182                 free(jblocks->jb_extent);
2183                 jblocks->jb_extent = jext;
2184         }
2185         jext = &jblocks->jb_extent[jblocks->jb_used];
2186         jext->je_daddr = daddr;
2187         jext->je_blocks = blocks;
2188
2189         return;
2190 }
2191
2192 /*
2193  * Add a file block from the journal to the extent map.  We can't read
2194  * each file block individually because the kernel treats it as a circular
2195  * buffer and segments may span mutliple contiguous blocks.
2196  */
2197 static void
2198 suj_add_block(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
2199 {
2200
2201         jblocks_add(suj_jblocks, fsbtodb(fs, blk), fsbtodb(fs, frags));
2202 }
2203
2204 static void
2205 suj_read(void)
2206 {
2207         uint8_t block[1 * 1024 * 1024];
2208         struct suj_seg *seg;
2209         struct jsegrec *recn;
2210         struct jsegrec *rec;
2211         ufs2_daddr_t blk;
2212         int readsize;
2213         int blocks;
2214         int recsize;
2215         int size;
2216         int i;
2217
2218         /*
2219          * Read records until we exhaust the journal space.  If we find
2220          * an invalid record we start searching for a valid segment header
2221          * at the next block.  This is because we don't have a head/tail
2222          * pointer and must recover the information indirectly.  At the gap
2223          * between the head and tail we won't necessarily have a valid
2224          * segment.
2225          */
2226 restart:
2227         for (;;) {
2228                 size = sizeof(block);
2229                 blk = jblocks_next(suj_jblocks, size, &readsize);
2230                 if (blk == 0)
2231                         return;
2232                 size = readsize;
2233                 /*
2234                  * Read 1MB at a time and scan for records within this block.
2235                  */
2236                 if (pread(fsreadfd, &block, size, dbtob(blk)) != size) {
2237                         err_suj("Error reading journal block %jd\n",
2238                             (intmax_t)blk);
2239                 }
2240                 for (rec = (void *)block; size; size -= recsize,
2241                     rec = (struct jsegrec *)((uintptr_t)rec + recsize)) {
2242                         recsize = real_dev_bsize;
2243                         if (rec->jsr_time != fs->fs_mtime) {
2244 #ifdef notdef
2245                                 if (debug)
2246                                         printf("Rec time %jd != fs mtime %jd\n",
2247                                             rec->jsr_time, fs->fs_mtime);
2248 #endif
2249                                 jblocks_advance(suj_jblocks, recsize);
2250                                 continue;
2251                         }
2252                         if (rec->jsr_cnt == 0) {
2253                                 if (debug)
2254                                         printf("Found illegal count %d\n",
2255                                             rec->jsr_cnt);
2256                                 jblocks_advance(suj_jblocks, recsize);
2257                                 continue;
2258                         }
2259                         blocks = rec->jsr_blocks;
2260                         recsize = blocks * real_dev_bsize;
2261                         if (recsize > size) {
2262                                 /*
2263                                  * We may just have run out of buffer, restart
2264                                  * the loop to re-read from this spot.
2265                                  */
2266                                 if (size < fs->fs_bsize &&
2267                                     size != readsize &&
2268                                     recsize <= fs->fs_bsize)
2269                                         goto restart;
2270                                 if (debug)
2271                                         printf("Found invalid segsize %d > %d\n",
2272                                             recsize, size);
2273                                 recsize = real_dev_bsize;
2274                                 jblocks_advance(suj_jblocks, recsize);
2275                                 continue;
2276                         }
2277                         /*
2278                          * Verify that all blocks in the segment are present.
2279                          */
2280                         for (i = 1; i < blocks; i++) {
2281                                 recn = (void *)((uintptr_t)rec) + i *
2282                                     real_dev_bsize;
2283                                 if (recn->jsr_seq == rec->jsr_seq &&
2284                                     recn->jsr_time == rec->jsr_time)
2285                                         continue;
2286                                 if (debug)
2287                                         printf("Incomplete record %jd (%d)\n",
2288                                             rec->jsr_seq, i);
2289                                 recsize = i * real_dev_bsize;
2290                                 jblocks_advance(suj_jblocks, recsize);
2291                                 goto restart;
2292                         }
2293                         seg = errmalloc(sizeof(*seg));
2294                         seg->ss_blk = errmalloc(recsize);
2295                         seg->ss_rec = *rec;
2296                         bcopy((void *)rec, seg->ss_blk, recsize);
2297                         if (rec->jsr_oldest > oldseq)
2298                                 oldseq = rec->jsr_oldest;
2299                         TAILQ_INSERT_TAIL(&allsegs, seg, ss_next);
2300                         jblocks_advance(suj_jblocks, recsize);
2301                 }
2302         }
2303 }
2304
2305 /*
2306  * Orchestrate the verification of a filesystem via the softupdates journal.
2307  */
2308 int
2309 suj_check(const char *filesys)
2310 {
2311         struct inodesc idesc;
2312         struct csum *cgsum;
2313         union dinode *jip;
2314         struct inode ip;
2315         uint64_t blocks;
2316         int i, retval;
2317         struct suj_seg *seg;
2318         struct suj_seg *segn;
2319
2320         initsuj();
2321         fs = &sblock;
2322         if (real_dev_bsize == 0 && ioctl(fsreadfd, DIOCGSECTORSIZE,
2323             &real_dev_bsize) == -1)
2324                 real_dev_bsize = secsize;
2325         if (debug)
2326                 printf("dev_bsize %u\n", real_dev_bsize);
2327
2328         /*
2329          * Set an exit point when SUJ check failed
2330          */
2331         retval = setjmp(jmpbuf);
2332         if (retval != 0) {
2333                 pwarn("UNEXPECTED SU+J INCONSISTENCY\n");
2334                 TAILQ_FOREACH_SAFE(seg, &allsegs, ss_next, segn) {
2335                         TAILQ_REMOVE(&allsegs, seg, ss_next);
2336                                 free(seg->ss_blk);
2337                                 free(seg);
2338                 }
2339                 if (reply("FALLBACK TO FULL FSCK") == 0) {
2340                         ckfini(0);
2341                         exit(EEXIT);
2342                 } else
2343                         return (-1);
2344         }
2345
2346         /*
2347          * Search the root directory for the SUJ_FILE.
2348          */
2349         idesc.id_type = DATA;
2350         idesc.id_fix = IGNORE;
2351         idesc.id_number = UFS_ROOTINO;
2352         idesc.id_func = findino;
2353         idesc.id_name = SUJ_FILE;
2354         ginode(UFS_ROOTINO, &ip);
2355         if ((ckinode(ip.i_dp, &idesc) & FOUND) == FOUND) {
2356                 sujino = idesc.id_parent;
2357                 irelse(&ip);
2358         } else {
2359                 printf("Journal inode removed.  Use tunefs to re-create.\n");
2360                 sblock.fs_flags &= ~FS_SUJ;
2361                 sblock.fs_sujfree = 0;
2362                 irelse(&ip);
2363                 return (-1);
2364         }
2365         /*
2366          * Fetch the journal inode and verify it.
2367          */
2368         ginode(sujino, &ip);
2369         jip = ip.i_dp;
2370         printf("** SU+J Recovering %s\n", filesys);
2371         if (suj_verifyino(jip) != 0 || (!preen && !reply("USE JOURNAL"))) {
2372                 irelse(&ip);
2373                 return (-1);
2374         }
2375         /*
2376          * Build a list of journal blocks in jblocks before parsing the
2377          * available journal blocks in with suj_read().
2378          */
2379         printf("** Reading %jd byte journal from inode %ju.\n",
2380             DIP(jip, di_size), (uintmax_t)sujino);
2381         suj_jblocks = jblocks_create();
2382         blocks = ino_visit(jip, sujino, suj_add_block, 0);
2383         if (blocks != numfrags(fs, DIP(jip, di_size))) {
2384                 printf("Sparse journal inode %ju.\n", (uintmax_t)sujino);
2385                 irelse(&ip);
2386                 return (-1);
2387         }
2388         irelse(&ip);
2389         suj_read();
2390         jblocks_destroy(suj_jblocks);
2391         suj_jblocks = NULL;
2392         if (preen || reply("RECOVER")) {
2393                 printf("** Building recovery table.\n");
2394                 suj_prune();
2395                 suj_build();
2396                 cg_apply(cg_build);
2397                 printf("** Resolving unreferenced inode list.\n");
2398                 ino_unlinked();
2399                 printf("** Processing journal entries.\n");
2400                 cg_apply(cg_trunc);
2401                 cg_apply(cg_check_blk);
2402                 cg_apply(cg_adj_blk);
2403                 cg_apply(cg_check_ino);
2404         }
2405         if (preen == 0 && (jrecs > 0 || jbytes > 0) && reply("WRITE CHANGES") == 0)
2406                 return (0);
2407         /*
2408          * Recompute the fs summary info from correct cs summaries.
2409          */
2410         bzero(&fs->fs_cstotal, sizeof(struct csum_total));
2411         for (i = 0; i < fs->fs_ncg; i++) {
2412                 cgsum = &fs->fs_cs(fs, i);
2413                 fs->fs_cstotal.cs_nffree += cgsum->cs_nffree;
2414                 fs->fs_cstotal.cs_nbfree += cgsum->cs_nbfree;
2415                 fs->fs_cstotal.cs_nifree += cgsum->cs_nifree;
2416                 fs->fs_cstotal.cs_ndir += cgsum->cs_ndir;
2417         }
2418         fs->fs_pendinginodes = 0;
2419         fs->fs_pendingblocks = 0;
2420         fs->fs_clean = 1;
2421         fs->fs_time = time(NULL);
2422         fs->fs_mtime = time(NULL);
2423         sbdirty();
2424         ckfini(1);
2425         if (jrecs > 0 || jbytes > 0) {
2426                 printf("** %jd journal records in %jd bytes for %.2f%% utilization\n",
2427                     jrecs, jbytes, ((float)jrecs / (float)(jbytes / JREC_SIZE)) * 100);
2428                 printf("** Freed %jd inodes (%jd dirs) %jd blocks, and %jd frags.\n",
2429                     freeinos, freedir, freeblocks, freefrags);
2430         }
2431
2432         return (0);
2433 }
2434
2435 static void
2436 initsuj(void)
2437 {
2438         int i;
2439
2440         for (i = 0; i < HASHSIZE; i++)
2441                 LIST_INIT(&cghash[i]);
2442         lastcg = NULL;
2443         TAILQ_INIT(&allsegs);
2444         oldseq = 0;
2445         fs = NULL;
2446         sujino = 0;
2447         freefrags = 0;
2448         freeblocks = 0;
2449         freeinos = 0;
2450         freedir = 0;
2451         jbytes = 0;
2452         jrecs = 0;
2453         suj_jblocks = NULL;
2454 }