sbin/fsck_ffs/suj.c

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