sbin/fsck_ffs/suj.c

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