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