sbin/fsck_ffs/suj.c

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