- Merge soft-updates journaling from projects/suj/head into head. This

   brings in support for an optional intent log which eliminates the need
   for background fsck on unclean shutdown.

Sponsored by:   iXsystems, Yahoo!, and Juniper.
With help from: McKusick and Peter Holm

11 files changed, 5328 insertions, 317 deletions

diff --git a/sbin/dumpfs/dumpfs.c b/sbin/dumpfs/dumpfs.c
index e4b5995..38c05f6 100644
--- a/sbin/dumpfs/dumpfs.c
+++ b/sbin/dumpfs/dumpfs.c
@@ -238,7 +238,7 @@ dumpfs(const char *name)
 	if (fsflags & FS_UNCLEAN)
 		printf("unclean ");
 	if (fsflags & FS_DOSOFTDEP)
-		printf("soft-updates ");
+		printf("soft-updates%s ", (fsflags & FS_SUJ) ? "+journal" : "");
 	if (fsflags & FS_NEEDSFSCK)
 		printf("needs fsck run ");
 	if (fsflags & FS_INDEXDIRS)
@@ -255,7 +255,7 @@ dumpfs(const char *name)
 		printf("nfsv4acls ");
 	fsflags &= ~(FS_UNCLEAN | FS_DOSOFTDEP | FS_NEEDSFSCK | FS_INDEXDIRS |
 		     FS_ACLS | FS_MULTILABEL | FS_GJOURNAL | FS_FLAGS_UPDATED |
-		     FS_NFS4ACLS);
+		     FS_NFS4ACLS | FS_SUJ);
 	if (fsflags != 0)
 		printf("unknown flags (%#x)", fsflags);
 	putchar('\n');
diff --git a/sbin/fsck_ffs/Makefile b/sbin/fsck_ffs/Makefile
index aaae685..db2930b 100644
--- a/sbin/fsck_ffs/Makefile
+++ b/sbin/fsck_ffs/Makefile
@@ -7,8 +7,7 @@ LINKS+=	${BINDIR}/fsck_ffs ${BINDIR}/fsck_4.2bsd
 MAN=	fsck_ffs.8
 MLINKS=	fsck_ffs.8 fsck_ufs.8 fsck_ffs.8 fsck_4.2bsd.8
 SRCS=	dir.c ea.c fsutil.c inode.c main.c pass1.c pass1b.c pass2.c pass3.c \
-	pass4.c pass5.c setup.c utilities.c ffs_subr.c ffs_tables.c gjournal.c \
-	getmntopts.c
+	pass4.c pass5.c setup.c suj.c utilities.c gjournal.c getmntopts.c
 DPADD=	${LIBUFS}
 LDADD=	-lufs
 WARNS?=	2
diff --git a/sbin/fsck_ffs/fsck.h b/sbin/fsck_ffs/fsck.h
index ad7fe13..6dad6b7 100644
--- a/sbin/fsck_ffs/fsck.h
+++ b/sbin/fsck_ffs/fsck.h
@@ -347,10 +347,6 @@ void		direrror(ino_t ino, const char *errmesg);
 int		dirscan(struct inodesc *);
 int		dofix(struct inodesc *, const char *msg);
 int		eascan(struct inodesc *, struct ufs2_dinode *dp);
-void		ffs_clrblock(struct fs *, u_char *, ufs1_daddr_t);
-void		ffs_fragacct(struct fs *, int, int32_t [], int);
-int		ffs_isblock(struct fs *, u_char *, ufs1_daddr_t);
-void		ffs_setblock(struct fs *, u_char *, ufs1_daddr_t);
 void		fileerror(ino_t cwd, ino_t ino, const char *errmesg);
 int		findino(struct inodesc *);
 int		findname(struct inodesc *);
@@ -392,3 +388,4 @@ void		sblock_init(void);
 void		setinodebuf(ino_t);
 int		setup(char *dev);
 void		gjournal_check(const char *filesys);
+int		suj_check(const char *filesys);
diff --git a/sbin/fsck_ffs/gjournal.c b/sbin/fsck_ffs/gjournal.c
index bd887ca..10c32c0 100644
--- a/sbin/fsck_ffs/gjournal.c
+++ b/sbin/fsck_ffs/gjournal.c
@@ -96,27 +96,6 @@ struct ufs2_dinode ufs2_zino;
 static void putcgs(void);
 
 /*
- * Write current block of inodes.
- */
-static int
-putino(struct uufsd *disk, ino_t inode)
-{
-	caddr_t inoblock;
-	struct fs *fs;
-	ssize_t ret;
-
-	fs = &disk->d_fs;
-	inoblock = disk->d_inoblock;
-
-	assert(inoblock != NULL);
-	assert(inode >= disk->d_inomin && inode <= disk->d_inomax);
-	ret = bwrite(disk, fsbtodb(fs, ino_to_fsba(fs, inode)), inoblock,
-	    fs->fs_bsize);
-
-	return (ret == -1 ? -1 : 0);
-}
-
-/*
  * Return cylinder group from the cache or load it if it is not in the
  * cache yet.
  * Don't cache more than MAX_CACHED_CGS cylinder groups.
@@ -242,13 +221,11 @@ cancelcgs(void)
 #endif
 
 /*
- * Open the given provider, load statistics.
+ * Open the given provider, load superblock.
  */
 static void
-getdisk(void)
+opendisk(void)
 {
-	int i;
-
 	if (disk != NULL)
 		return;
 	disk = malloc(sizeof(*disk));
@@ -259,24 +236,6 @@ getdisk(void)
 		    disk->d_error);
 	}
 	fs = &disk->d_fs;
-	fs->fs_csp = malloc((size_t)fs->fs_cssize);
-	if (fs->fs_csp == NULL)
-		err(1, "malloc(%zu)", (size_t)fs->fs_cssize);
-	bzero(fs->fs_csp, (size_t)fs->fs_cssize);
-	for (i = 0; i < fs->fs_cssize; i += fs->fs_bsize) {
-		if (bread(disk, fsbtodb(fs, fs->fs_csaddr + numfrags(fs, i)),
-		    (void *)(((char *)fs->fs_csp) + i),
-		    (size_t)(fs->fs_cssize - i < fs->fs_bsize ? fs->fs_cssize - i : fs->fs_bsize)) == -1) {
-			err(1, "bread: %s", disk->d_error);
-		}
-	}
-	if (fs->fs_contigsumsize > 0) {
-		fs->fs_maxcluster = malloc(fs->fs_ncg * sizeof(int32_t));
-		if (fs->fs_maxcluster == NULL)
-			err(1, "malloc(%zu)", fs->fs_ncg * sizeof(int32_t));
-		for (i = 0; i < fs->fs_ncg; i++)
-			fs->fs_maxcluster[i] = fs->fs_contigsumsize;
-	}
 }
 
 /*
@@ -286,11 +245,6 @@ static void
 closedisk(void)
 {
 
-	free(fs->fs_csp);
-	if (fs->fs_contigsumsize > 0) {
-		free(fs->fs_maxcluster);
-		fs->fs_maxcluster = NULL;
-	}
 	fs->fs_clean = 1;
 	if (sbwrite(disk, 0) == -1)
 		err(1, "sbwrite(%s)", devnam);
@@ -301,227 +255,6 @@ closedisk(void)
 	fs = NULL;
 }
 
-/*
- * Write the statistics back, call closedisk().
- */
-static void
-putdisk(void)
-{
-	int i;
-
-	assert(disk != NULL && fs != NULL);
-	for (i = 0; i < fs->fs_cssize; i += fs->fs_bsize) {
-		if (bwrite(disk, fsbtodb(fs, fs->fs_csaddr + numfrags(fs, i)),
-		    (void *)(((char *)fs->fs_csp) + i),
-		    (size_t)(fs->fs_cssize - i < fs->fs_bsize ? fs->fs_cssize - i : fs->fs_bsize)) == -1) {
-			err(1, "bwrite: %s", disk->d_error);
-		}
-	}
-	closedisk();
-}
-
-#if 0
-/*
- * Free memory, close the disk, but don't write anything back.
- */
-static void
-canceldisk(void)
-{
-	int i;
-
-	assert(disk != NULL && fs != NULL);
-	free(fs->fs_csp);
-	if (fs->fs_contigsumsize > 0)
-		free(fs->fs_maxcluster);
-	if (ufs_disk_close(disk) == -1)
-		err(1, "ufs_disk_close(%s)", devnam);
-	free(disk);
-	disk = NULL;
-	fs = NULL;
-}
-#endif
-
-static int
-isblock(unsigned char *cp, ufs1_daddr_t h)
-{
-	unsigned char mask;
-
-	switch ((int)fs->fs_frag) {
-	case 8:
-		return (cp[h] == 0xff);
-	case 4:
-		mask = 0x0f << ((h & 0x1) << 2);
-		return ((cp[h >> 1] & mask) == mask);
-	case 2:
-		mask = 0x03 << ((h & 0x3) << 1);
-		return ((cp[h >> 2] & mask) == mask);
-	case 1:
-		mask = 0x01 << (h & 0x7);
-		return ((cp[h >> 3] & mask) == mask);
-	default:
-		assert(!"isblock: invalid number of fragments");
-	}
-	return (0);
-}
-
-/*
- * put a block into the map
- */
-static void
-setblock(unsigned char *cp, ufs1_daddr_t h)
-{
-
-	switch ((int)fs->fs_frag) {
-	case 8:
-		cp[h] = 0xff;
-		return;
-	case 4:
-		cp[h >> 1] |= (0x0f << ((h & 0x1) << 2));
-		return;
-	case 2:
-		cp[h >> 2] |= (0x03 << ((h & 0x3) << 1));
-		return;
-	case 1:
-		cp[h >> 3] |= (0x01 << (h & 0x7));
-		return;
-	default:
-		assert(!"setblock: invalid number of fragments");
-	}
-}
-
-/*
- * check if a block is free
- */
-static int
-isfreeblock(u_char *cp, ufs1_daddr_t h)
-{
-
-	switch ((int)fs->fs_frag) {
-	case 8:
-		return (cp[h] == 0);
-	case 4:
-		return ((cp[h >> 1] & (0x0f << ((h & 0x1) << 2))) == 0);
-	case 2:
-		return ((cp[h >> 2] & (0x03 << ((h & 0x3) << 1))) == 0);
-	case 1:
-		return ((cp[h >> 3] & (0x01 << (h & 0x7))) == 0);
-	default:
-		assert(!"isfreeblock: invalid number of fragments");
-	}
-	return (0);
-}
-
-/*
- * Update the frsum fields to reflect addition or deletion
- * of some frags.
- */
-void
-fragacct(int fragmap, int32_t fraglist[], int cnt)
-{
-	int inblk;
-	int field, subfield;
-	int siz, pos;
-
-	inblk = (int)(fragtbl[fs->fs_frag][fragmap]) << 1;
-	fragmap <<= 1;
-	for (siz = 1; siz < fs->fs_frag; siz++) {
-		if ((inblk & (1 << (siz + (fs->fs_frag % NBBY)))) == 0)
-			continue;
-		field = around[siz];
-		subfield = inside[siz];
-		for (pos = siz; pos <= fs->fs_frag; pos++) {
-			if ((fragmap & field) == subfield) {
-				fraglist[siz] += cnt;
-				pos += siz;
-				field <<= siz;
-				subfield <<= siz;
-			}
-			field <<= 1;
-			subfield <<= 1;
-		}
-	}
-}
-
-static void
-clusteracct(struct cg *cgp, ufs1_daddr_t blkno)
-{
-	int32_t *sump;
-	int32_t *lp;
-	u_char *freemapp, *mapp;
-	int i, start, end, forw, back, map, bit;
-
-	if (fs->fs_contigsumsize <= 0)
-		return;
-	freemapp = cg_clustersfree(cgp);
-	sump = cg_clustersum(cgp);
-	/*
-	 * Clear the actual block.
-	 */
-	setbit(freemapp, blkno);
-	/*
-	 * Find the size of the cluster going forward.
-	 */
-	start = blkno + 1;
-	end = start + fs->fs_contigsumsize;
-	if (end >= cgp->cg_nclusterblks)
-		end = cgp->cg_nclusterblks;
-	mapp = &freemapp[start / NBBY];
-	map = *mapp++;
-	bit = 1 << (start % NBBY);
-	for (i = start; i < end; i++) {
-		if ((map & bit) == 0)
-			break;
-		if ((i & (NBBY - 1)) != (NBBY - 1)) {
-			bit <<= 1;
-		} else {
-			map = *mapp++;
-			bit = 1;
-		}
-	}
-	forw = i - start;
-	/*
-	 * Find the size of the cluster going backward.
-	 */
-	start = blkno - 1;
-	end = start - fs->fs_contigsumsize;
-	if (end < 0)
-		end = -1;
-	mapp = &freemapp[start / NBBY];
-	map = *mapp--;
-	bit = 1 << (start % NBBY);
-	for (i = start; i > end; i--) {
-		if ((map & bit) == 0)
-			break;
-		if ((i & (NBBY - 1)) != 0) {
-			bit >>= 1;
-		} else {
-			map = *mapp--;
-			bit = 1 << (NBBY - 1);
-		}
-	}
-	back = start - i;
-	/*
-	 * Account for old cluster and the possibly new forward and
-	 * back clusters.
-	 */
-	i = back + forw + 1;
-	if (i > fs->fs_contigsumsize)
-		i = fs->fs_contigsumsize;
-	sump[i]++;
-	if (back > 0)
-		sump[back]--;
-	if (forw > 0)
-		sump[forw]--;
-	/*
-	 * Update cluster summary information.
-	 */
-	lp = &sump[fs->fs_contigsumsize];
-	for (i = fs->fs_contigsumsize; i > 0; i--)
-		if (*lp-- > 0)
-			break;
-	fs->fs_maxcluster[cgp->cg_cgx] = i;
-}
-
 static void
 blkfree(ufs2_daddr_t bno, long size)
 {
@@ -539,10 +272,10 @@ blkfree(ufs2_daddr_t bno, long size)
 	blksfree = cg_blksfree(cgp);
 	if (size == fs->fs_bsize) {
 		fragno = fragstoblks(fs, cgbno);
-		if (!isfreeblock(blksfree, fragno))
+		if (!ffs_isfreeblock(fs, blksfree, fragno))
 			assert(!"blkfree: freeing free block");
-		setblock(blksfree, fragno);
-		clusteracct(cgp, fragno);
+		ffs_setblock(fs, blksfree, fragno);
+		ffs_clusteracct(fs, cgp, fragno, 1);
 		cgp->cg_cs.cs_nbfree++;
 		fs->fs_cstotal.cs_nbfree++;
 		fs->fs_cs(fs, cg).cs_nbfree++;
@@ -552,7 +285,7 @@ blkfree(ufs2_daddr_t bno, long size)
 		 * decrement the counts associated with the old frags
 		 */
 		blk = blkmap(fs, blksfree, bbase);
-		fragacct(blk, cgp->cg_frsum, -1);
+		ffs_fragacct(fs, blk, cgp->cg_frsum, -1);
 		/*
 		 * deallocate the fragment
 		 */
@@ -569,16 +302,16 @@ blkfree(ufs2_daddr_t bno, long size)
 		 * add back in counts associated with the new frags
 		 */
 		blk = blkmap(fs, blksfree, bbase);
-		fragacct(blk, cgp->cg_frsum, 1);
+		ffs_fragacct(fs, blk, cgp->cg_frsum, 1);
 		/*
 		 * if a complete block has been reassembled, account for it
 		 */
 		fragno = fragstoblks(fs, bbase);
-		if (isblock(blksfree, fragno)) {
+		if (ffs_isblock(fs, blksfree, fragno)) {
 			cgp->cg_cs.cs_nffree -= fs->fs_frag;
 			fs->fs_cstotal.cs_nffree -= fs->fs_frag;
 			fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag;
-			clusteracct(cgp, fragno);
+			ffs_clusteracct(fs, cgp, fragno, 1);
 			cgp->cg_cs.cs_nbfree++;
 			fs->fs_cstotal.cs_nbfree++;
 			fs->fs_cs(fs, cg).cs_nbfree++;
@@ -599,7 +332,7 @@ freeindir(ufs2_daddr_t blk, int level)
 	if (bread(disk, fsbtodb(fs, blk), (void *)&sblks, (size_t)fs->fs_bsize) == -1)
 		err(1, "bread: %s", disk->d_error);
 	blks = (ufs2_daddr_t *)&sblks;
-	for (i = 0; i < howmany(fs->fs_bsize, sizeof(ufs2_daddr_t)); i++) {
+	for (i = 0; i < NINDIR(fs); i++) {
 		if (blks[i] == 0)
 			break;
 		if (level == 0)
@@ -671,7 +404,7 @@ gjournal_check(const char *filesys)
 	int cg, mode;
 
 	devnam = filesys;
-	getdisk();
+	opendisk();
 	/* Are there any unreferenced inodes in this file system? */
 	if (fs->fs_unrefs == 0) {
 		//printf("No unreferenced inodes.\n");
@@ -747,7 +480,7 @@ gjournal_check(const char *filesys)
 			/* Zero-fill the inode. */
 			*dino = ufs2_zino;
 			/* Write the inode back. */
-			if (putino(disk, ino) == -1)
+			if (putino(disk) == -1)
 				err(1, "putino(cg=%d ino=%d)", cg, ino);
 			if (cgp->cg_unrefs == 0) {
 				//printf("No more unreferenced inodes in cg=%d.\n", cg);
@@ -772,5 +505,5 @@ gjournal_check(const char *filesys)
 	/* Write back modified cylinder groups. */
 	putcgs();
 	/* Write back updated statistics and super-block. */
-	putdisk();
+	closedisk();
 }
diff --git a/sbin/fsck_ffs/main.c b/sbin/fsck_ffs/main.c
index 66edd63..e9a9704 100644
--- a/sbin/fsck_ffs/main.c
+++ b/sbin/fsck_ffs/main.c
@@ -242,8 +242,9 @@ checkfilesys(char *filesys)
 		if ((fsreadfd = open(filesys, O_RDONLY)) < 0 || readsb(0) == 0)
 			exit(3);	/* Cannot read superblock */
 		close(fsreadfd);
-		if (sblock.fs_flags & FS_NEEDSFSCK)
-			exit(4);	/* Earlier background failed */
+		/* Earlier background failed or journaled */
+		if (sblock.fs_flags & (FS_NEEDSFSCK | FS_SUJ))
+			exit(4);
 		if ((sblock.fs_flags & FS_DOSOFTDEP) == 0)
 			exit(5);	/* Not running soft updates */
 		size = MIBSIZE;
@@ -299,7 +300,7 @@ checkfilesys(char *filesys)
 			pfatal("MOUNTED READ-ONLY, CANNOT RUN IN BACKGROUND\n");
 		} else if ((fsreadfd = open(filesys, O_RDONLY)) >= 0) {
 			if (readsb(0) != 0) {
-				if (sblock.fs_flags & FS_NEEDSFSCK) {
+				if (sblock.fs_flags & (FS_NEEDSFSCK | FS_SUJ)) {
 					bkgrdflag = 0;
 					pfatal("UNEXPECTED INCONSISTENCY, %s\n",
 					    "CANNOT RUN IN BACKGROUND\n");
@@ -384,6 +385,26 @@ checkfilesys(char *filesys)
 		    sblock.fs_cstotal.cs_nffree * 100.0 / sblock.fs_dsize);
 		return (0);
 	}
+	/*
+	 * Determine if we can and should do journal recovery.
+	 */
+	if ((sblock.fs_flags & (FS_SUJ | FS_NEEDSFSCK)) == FS_SUJ) {
+		if (preen || reply("USE JOURNAL?")) {
+			if (suj_check(filesys) == 0) {
+				if (chkdoreload(mntp) == 0)
+					exit(0);
+				exit(4);
+			}
+			/* suj_check failed, fall through. */
+		}
+		printf("** Skipping journal, falling through to full fsck\n");
+		/*
+		 * Write the superblock so we don't try to recover the
+		 * journal on another pass.
+		 */
+		sblock.fs_mtime = time(NULL);
+		sbdirty();
+	}
 	
 	/*
 	 * Cleared if any questions answered no. Used to decide if
diff --git a/sbin/fsck_ffs/pass5.c b/sbin/fsck_ffs/pass5.c
index 173156e..639ce0f 100644
--- a/sbin/fsck_ffs/pass5.c
+++ b/sbin/fsck_ffs/pass5.c
@@ -45,6 +45,7 @@ __FBSDID("$FreeBSD$");
 #include <inttypes.h>
 #include <limits.h>
 #include <string.h>
+#include <libufs.h>
 
 #include "fsck.h"
 
diff --git a/sbin/fsck_ffs/suj.c b/sbin/fsck_ffs/suj.c
new file mode 100644
index 0000000..84608f1
--- /dev/null
+++ b/sbin/fsck_ffs/suj.c
@@ -0,0 +1,4699 @@
+/*-
+ * Copyright 2009, 2010 Jeffrey W. Roberson <jeff@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <sys/param.h>
+#include <sys/disklabel.h>
+#include <sys/mount.h>
+#include <sys/stat.h>
+
+#include <ufs/ufs/ufsmount.h>
+#include <ufs/ufs/dinode.h>
+#include <ufs/ufs/dir.h>
+#include <ufs/ffs/fs.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <libufs.h>
+#include <string.h>
+#include <strings.h>
+#include <err.h>
+#include <assert.h>
+
+#include "fsck.h"
+
+#define	DOTDOT_OFFSET	DIRECTSIZ(1)
+#define	SUJ_HASHSIZE	2048
+#define	SUJ_HASHMASK	(SUJ_HASHSIZE - 1)
+#define	SUJ_HASH(x)	((x * 2654435761) & SUJ_HASHMASK)
+
+struct suj_seg {
+	TAILQ_ENTRY(suj_seg) ss_next;
+	struct jsegrec	ss_rec;
+	uint8_t		*ss_blk;
+};
+
+struct suj_rec {
+	TAILQ_ENTRY(suj_rec) sr_next;
+	union jrec	*sr_rec;
+};
+TAILQ_HEAD(srechd, suj_rec);
+
+struct suj_ino {
+	LIST_ENTRY(suj_ino)	si_next;
+	struct srechd		si_recs;
+	struct srechd		si_newrecs;
+	struct srechd		si_movs;
+	struct jtrncrec		*si_trunc;
+	ino_t			si_ino;
+	char			si_skipparent;
+	char			si_hasrecs;
+	char			si_blkadj;
+	char			si_linkadj;
+	int			si_mode;
+	nlink_t			si_nlinkadj;
+	nlink_t			si_nlink;
+	nlink_t			si_dotlinks;
+};
+LIST_HEAD(inohd, suj_ino);
+
+struct suj_blk {
+	LIST_ENTRY(suj_blk)	sb_next;
+	struct srechd		sb_recs;
+	ufs2_daddr_t		sb_blk;
+};
+LIST_HEAD(blkhd, suj_blk);
+
+struct data_blk {
+	LIST_ENTRY(data_blk)	db_next;
+	uint8_t			*db_buf;
+	ufs2_daddr_t		db_blk;
+	int			db_size;
+	int			db_dirty;
+};
+
+struct ino_blk {
+	LIST_ENTRY(ino_blk)	ib_next;
+	uint8_t			*ib_buf;
+	int			ib_dirty;
+	ufs2_daddr_t		ib_blk;
+};
+LIST_HEAD(iblkhd, ino_blk);
+
+struct suj_cg {
+	LIST_ENTRY(suj_cg)	sc_next;
+	struct blkhd		sc_blkhash[SUJ_HASHSIZE];
+	struct inohd		sc_inohash[SUJ_HASHSIZE];
+	struct iblkhd		sc_iblkhash[SUJ_HASHSIZE];
+	struct ino_blk		*sc_lastiblk;
+	struct suj_ino		*sc_lastino;
+	struct suj_blk		*sc_lastblk;
+	uint8_t			*sc_cgbuf;
+	struct cg		*sc_cgp;
+	int			sc_dirty;
+	int			sc_cgx;
+};
+
+LIST_HEAD(cghd, suj_cg) cghash[SUJ_HASHSIZE];
+LIST_HEAD(dblkhd, data_blk) dbhash[SUJ_HASHSIZE];
+struct suj_cg *lastcg;
+struct data_blk *lastblk;
+
+TAILQ_HEAD(seghd, suj_seg) allsegs;
+uint64_t oldseq;
+static struct uufsd *disk = NULL;
+static struct fs *fs = NULL;
+ino_t sujino;
+
+/*
+ * Summary statistics.
+ */
+uint64_t freefrags;
+uint64_t freeblocks;
+uint64_t freeinos;
+uint64_t freedir;
+uint64_t jbytes;
+uint64_t jrecs;
+
+typedef void (*ino_visitor)(ino_t, ufs_lbn_t, ufs2_daddr_t, int);
+static void ino_trunc(ino_t, off_t);
+static void ino_decr(ino_t);
+static void ino_adjust(struct suj_ino *);
+static void ino_build(struct suj_ino *);
+static int blk_isfree(ufs2_daddr_t);
+
+static void *
+errmalloc(size_t n)
+{
+	void *a;
+
+	a = malloc(n);
+	if (a == NULL)
+		errx(1, "malloc(%zu)", n);
+	return (a);
+}
+
+/*
+ * Open the given provider, load superblock.
+ */
+static void
+opendisk(const char *devnam)
+{
+	if (disk != NULL)
+		return;
+	disk = malloc(sizeof(*disk));
+	if (disk == NULL)
+		errx(1, "malloc(%zu)", sizeof(*disk));
+	if (ufs_disk_fillout(disk, devnam) == -1) {
+		err(1, "ufs_disk_fillout(%s) failed: %s", devnam,
+		    disk->d_error);
+	}
+	fs = &disk->d_fs;
+}
+
+/*
+ * Mark file system as clean, write the super-block back, close the disk.
+ */
+static void
+closedisk(const char *devnam)
+{
+	struct csum *cgsum;
+	int i;
+
+	/*
+	 * Recompute the fs summary info from correct cs summaries.
+	 */
+	bzero(&fs->fs_cstotal, sizeof(struct csum_total));
+	for (i = 0; i < fs->fs_ncg; i++) {
+		cgsum = &fs->fs_cs(fs, i);
+		fs->fs_cstotal.cs_nffree += cgsum->cs_nffree;
+		fs->fs_cstotal.cs_nbfree += cgsum->cs_nbfree;
+		fs->fs_cstotal.cs_nifree += cgsum->cs_nifree;
+		fs->fs_cstotal.cs_ndir += cgsum->cs_ndir;
+	}
+	fs->fs_pendinginodes = 0;
+	fs->fs_pendingblocks = 0;
+	fs->fs_clean = 1;
+	fs->fs_time = time(NULL);
+	fs->fs_mtime = time(NULL);
+	if (sbwrite(disk, 0) == -1)
+		err(1, "sbwrite(%s)", devnam);
+	if (ufs_disk_close(disk) == -1)
+		err(1, "ufs_disk_close(%s)", devnam);
+	free(disk);
+	disk = NULL;
+	fs = NULL;
+}
+
+/*
+ * Lookup a cg by number in the hash so we can keep track of which cgs
+ * need stats rebuilt.
+ */
+static struct suj_cg *
+cg_lookup(int cgx)
+{
+	struct cghd *hd;
+	struct suj_cg *sc;
+
+	if (cgx < 0 || cgx >= fs->fs_ncg) {
+		abort();
+		errx(1, "Bad cg number %d", cgx);
+	}
+	if (lastcg && lastcg->sc_cgx == cgx)
+		return (lastcg);
+	hd = &cghash[SUJ_HASH(cgx)];
+	LIST_FOREACH(sc, hd, sc_next)
+		if (sc->sc_cgx == cgx) {
+			lastcg = sc;
+			return (sc);
+		}
+	sc = errmalloc(sizeof(*sc));
+	bzero(sc, sizeof(*sc));
+	sc->sc_cgbuf = errmalloc(fs->fs_bsize);
+	sc->sc_cgp = (struct cg *)sc->sc_cgbuf;
+	sc->sc_cgx = cgx;
+	LIST_INSERT_HEAD(hd, sc, sc_next);
+	if (bread(disk, fsbtodb(fs, cgtod(fs, sc->sc_cgx)), sc->sc_cgbuf,
+	    fs->fs_bsize) == -1)
+		err(1, "Unable to read cylinder group %d", sc->sc_cgx);
+
+	return (sc);
+}
+
+/*
+ * Lookup an inode number in the hash and allocate a suj_ino if it does
+ * not exist.
+ */
+static struct suj_ino *
+ino_lookup(ino_t ino, int creat)
+{
+	struct suj_ino *sino;
+	struct inohd *hd;
+	struct suj_cg *sc;
+
+	sc = cg_lookup(ino_to_cg(fs, ino));
+	if (sc->sc_lastino && sc->sc_lastino->si_ino == ino)
+		return (sc->sc_lastino);
+	hd = &sc->sc_inohash[SUJ_HASH(ino)];
+	LIST_FOREACH(sino, hd, si_next)
+		if (sino->si_ino == ino)
+			return (sino);
+	if (creat == 0)
+		return (NULL);
+	sino = errmalloc(sizeof(*sino));
+	bzero(sino, sizeof(*sino));
+	sino->si_ino = ino;
+	TAILQ_INIT(&sino->si_recs);
+	TAILQ_INIT(&sino->si_newrecs);
+	TAILQ_INIT(&sino->si_movs);
+	LIST_INSERT_HEAD(hd, sino, si_next);
+
+	return (sino);
+}
+
+/*
+ * Lookup a block number in the hash and allocate a suj_blk if it does
+ * not exist.
+ */
+static struct suj_blk *
+blk_lookup(ufs2_daddr_t blk, int creat)
+{
+	struct suj_blk *sblk;
+	struct suj_cg *sc;
+	struct blkhd *hd;
+
+	sc = cg_lookup(dtog(fs, blk));
+	if (sc->sc_lastblk && sc->sc_lastblk->sb_blk == blk)
+		return (sc->sc_lastblk);
+	hd = &sc->sc_blkhash[SUJ_HASH(fragstoblks(fs, blk))];
+	LIST_FOREACH(sblk, hd, sb_next)
+		if (sblk->sb_blk == blk)
+			return (sblk);
+	if (creat == 0)
+		return (NULL);
+	sblk = errmalloc(sizeof(*sblk));
+	bzero(sblk, sizeof(*sblk));
+	sblk->sb_blk = blk;
+	TAILQ_INIT(&sblk->sb_recs);
+	LIST_INSERT_HEAD(hd, sblk, sb_next);
+
+	return (sblk);
+}
+
+static struct data_blk *
+dblk_lookup(ufs2_daddr_t blk)
+{
+	struct data_blk *dblk;
+	struct dblkhd *hd;
+
+	hd = &dbhash[SUJ_HASH(fragstoblks(fs, blk))];
+	if (lastblk && lastblk->db_blk == blk)
+		return (lastblk);
+	LIST_FOREACH(dblk, hd, db_next)
+		if (dblk->db_blk == blk)
+			return (dblk);
+	/*
+	 * The inode block wasn't located, allocate a new one.
+	 */
+	dblk = errmalloc(sizeof(*dblk));
+	bzero(dblk, sizeof(*dblk));
+	LIST_INSERT_HEAD(hd, dblk, db_next);
+	dblk->db_blk = blk;
+	return (dblk);
+}
+
+static uint8_t *
+dblk_read(ufs2_daddr_t blk, int size)
+{
+	struct data_blk *dblk;
+
+	dblk = dblk_lookup(blk);
+	/*
+	 * I doubt size mismatches can happen in practice but it is trivial
+	 * to handle.
+	 */
+	if (size != dblk->db_size) {
+		if (dblk->db_buf)
+			free(dblk->db_buf);
+		dblk->db_buf = errmalloc(size);
+		dblk->db_size = size;
+		if (bread(disk, fsbtodb(fs, blk), dblk->db_buf, size) == -1)
+			err(1, "Failed to read data block %jd", blk);
+	}
+	return (dblk->db_buf);
+}
+
+static void
+dblk_dirty(ufs2_daddr_t blk)
+{
+	struct data_blk *dblk;
+
+	dblk = dblk_lookup(blk);
+	dblk->db_dirty = 1;
+}
+
+static void
+dblk_write(void)
+{
+	struct data_blk *dblk;
+	int i;
+
+	for (i = 0; i < SUJ_HASHSIZE; i++) {
+		LIST_FOREACH(dblk, &dbhash[i], db_next) {
+			if (dblk->db_dirty == 0 || dblk->db_size == 0)
+				continue;
+			if (bwrite(disk, fsbtodb(fs, dblk->db_blk),
+			    dblk->db_buf, dblk->db_size) == -1)
+				err(1, "Unable to write block %jd",
+				    dblk->db_blk);
+		}
+	}
+}
+
+static union dinode *
+ino_read(ino_t ino)
+{
+	struct ino_blk *iblk;
+	struct iblkhd *hd;
+	struct suj_cg *sc;
+	ufs2_daddr_t blk;
+	int off;
+
+	blk = ino_to_fsba(fs, ino);
+	sc = cg_lookup(ino_to_cg(fs, ino));
+	iblk = sc->sc_lastiblk;
+	if (iblk && iblk->ib_blk == blk)
+		goto found;
+	hd = &sc->sc_iblkhash[SUJ_HASH(fragstoblks(fs, blk))];
+	LIST_FOREACH(iblk, hd, ib_next)
+		if (iblk->ib_blk == blk)
+			goto found;
+	/*
+	 * The inode block wasn't located, allocate a new one.
+	 */
+	iblk = errmalloc(sizeof(*iblk));
+	bzero(iblk, sizeof(*iblk));
+	iblk->ib_buf = errmalloc(fs->fs_bsize);
+	iblk->ib_blk = blk;
+	LIST_INSERT_HEAD(hd, iblk, ib_next);
+	if (bread(disk, fsbtodb(fs, blk), iblk->ib_buf, fs->fs_bsize) == -1)
+		err(1, "Failed to read inode block %jd", blk);
+found:
+	sc->sc_lastiblk = iblk;
+	off = ino_to_fsbo(fs, ino);
+	if (fs->fs_magic == FS_UFS1_MAGIC)
+		return (union dinode *)&((struct ufs1_dinode *)iblk->ib_buf)[off];
+	else
+		return (union dinode *)&((struct ufs2_dinode *)iblk->ib_buf)[off];
+}
+
+static void
+ino_dirty(ino_t ino)
+{
+	struct ino_blk *iblk;
+	struct iblkhd *hd;
+	struct suj_cg *sc;
+	ufs2_daddr_t blk;
+
+	blk = ino_to_fsba(fs, ino);
+	sc = cg_lookup(ino_to_cg(fs, ino));
+	iblk = sc->sc_lastiblk;
+	if (iblk && iblk->ib_blk == blk) {
+		iblk->ib_dirty = 1;
+		return;
+	}
+	hd = &sc->sc_iblkhash[SUJ_HASH(fragstoblks(fs, blk))];
+	LIST_FOREACH(iblk, hd, ib_next) {
+		if (iblk->ib_blk == blk) {
+			iblk->ib_dirty = 1;
+			return;
+		}
+	}
+	ino_read(ino);
+	ino_dirty(ino);
+}
+
+static void
+iblk_write(struct ino_blk *iblk)
+{
+
+	if (iblk->ib_dirty == 0)
+		return;
+	if (bwrite(disk, fsbtodb(fs, iblk->ib_blk), iblk->ib_buf,
+	    fs->fs_bsize) == -1)
+		err(1, "Failed to write inode block %jd", iblk->ib_blk);
+}
+
+static int
+blk_overlaps(struct jblkrec *brec, ufs2_daddr_t start, int frags)
+{
+	ufs2_daddr_t bstart;
+	ufs2_daddr_t bend;
+	ufs2_daddr_t end;
+
+	end = start + frags;
+	bstart = brec->jb_blkno + brec->jb_oldfrags;
+	bend = bstart + brec->jb_frags;
+	if (start < bend && end > bstart)
+		return (1);
+	return (0);
+}
+
+static int
+blk_equals(struct jblkrec *brec, ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t start,
+    int frags)
+{
+
+	if (brec->jb_ino != ino || brec->jb_lbn != lbn)
+		return (0);
+	if (brec->jb_blkno + brec->jb_oldfrags != start)
+		return (0);
+	if (brec->jb_frags != frags)
+		return (0);
+	return (1);
+}
+
+static void
+blk_setmask(struct jblkrec *brec, int *mask)
+{
+	int i;
+
+	for (i = brec->jb_oldfrags; i < brec->jb_oldfrags + brec->jb_frags; i++)
+		*mask |= 1 << i;
+}
+
+/*
+ * Determine whether a given block has been reallocated to a new location.
+ * Returns a mask of overlapping bits if any frags have been reused or
+ * zero if the block has not been re-used and the contents can be trusted.
+ * 
+ * This is used to ensure that an orphaned pointer due to truncate is safe
+ * to be freed.  The mask value can be used to free partial blocks.
+ */
+static int
+blk_freemask(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn, int frags)
+{
+	struct suj_blk *sblk;
+	struct suj_rec *srec;
+	struct jblkrec *brec;
+	int mask;
+	int off;
+
+	/*
+	 * To be certain we're not freeing a reallocated block we lookup
+	 * this block in the blk hash and see if there is an allocation
+	 * journal record that overlaps with any fragments in the block
+	 * we're concerned with.  If any fragments have ben reallocated
+	 * the block has already been freed and re-used for another purpose.
+	 */
+	mask = 0;
+	sblk = blk_lookup(blknum(fs, blk), 0);
+	if (sblk == NULL)
+		return (0);
+	off = blk - sblk->sb_blk;
+	TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) {
+		brec = (struct jblkrec *)srec->sr_rec;
+		/*
+		 * If the block overlaps but does not match
+		 * exactly it's a new allocation.  If it matches
+		 * exactly this record refers to the current
+		 * location.
+		 */ 
+		if (blk_overlaps(brec, blk, frags) == 0)
+			continue;
+		if (blk_equals(brec, ino, lbn, blk, frags) == 1)
+			mask = 0;
+		else
+			blk_setmask(brec, &mask);
+	}
+	if (debug)
+		printf("blk_freemask: blk %jd sblk %jd off %d mask 0x%X\n",
+		    blk, sblk->sb_blk, off, mask);
+	return (mask >> off);
+}
+
+/*
+ * Determine whether it is safe to follow an indirect.  It is not safe
+ * if any part of the indirect has been reallocated or the last journal
+ * entry was an allocation.  Just allocated indirects may not have valid
+ * pointers yet and all of their children will have their own records.
+ * It is also not safe to follow an indirect if the cg bitmap has been
+ * cleared as a new allocation may write to the block prior to the journal
+ * being written.
+ * 
+ * Returns 1 if it's safe to follow the indirect and 0 otherwise.
+ */
+static int
+blk_isindir(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn)
+{
+	struct suj_blk *sblk;
+	struct jblkrec *brec;
+
+	sblk = blk_lookup(blk, 0);
+	if (sblk == NULL)
+		return (1);
+	if (TAILQ_EMPTY(&sblk->sb_recs))
+		return (1);
+	brec = (struct jblkrec *)TAILQ_LAST(&sblk->sb_recs, srechd)->sr_rec;
+	if (blk_equals(brec, ino, lbn, blk, fs->fs_frag))
+		if (brec->jb_op == JOP_FREEBLK)
+			return (!blk_isfree(blk));
+	return (0);
+}
+
+/*
+ * Clear an inode from the cg bitmap.  If the inode was already clear return
+ * 0 so the caller knows it does not have to check the inode contents.
+ */
+static int
+ino_free(ino_t ino, int mode)
+{
+	struct suj_cg *sc;
+	uint8_t *inosused;
+	struct cg *cgp;
+	int cg;
+
+	cg = ino_to_cg(fs, ino);
+	ino = ino % fs->fs_ipg;
+	sc = cg_lookup(cg);
+	cgp = sc->sc_cgp;
+	inosused = cg_inosused(cgp);
+	/*
+	 * The bitmap may never have made it to the disk so we have to
+	 * conditionally clear.  We can avoid writing the cg in this case.
+	 */
+	if (isclr(inosused, ino))
+		return (0);
+	freeinos++;
+	clrbit(inosused, ino);
+	if (ino < cgp->cg_irotor)
+		cgp->cg_irotor = ino;
+	cgp->cg_cs.cs_nifree++;
+	if ((mode & IFMT) == IFDIR) {
+		freedir++;
+		cgp->cg_cs.cs_ndir--;
+	}
+	sc->sc_dirty = 1;
+
+	return (1);
+}
+
+/*
+ * Free 'frags' frags starting at filesystem block 'bno' skipping any frags
+ * set in the mask.
+ */
+static void
+blk_free(ufs2_daddr_t bno, int mask, int frags)
+{
+	ufs1_daddr_t fragno, cgbno;
+	struct suj_cg *sc;
+	struct cg *cgp;
+	int i, cg;
+	uint8_t *blksfree;
+
+	if (debug)
+		printf("Freeing %d frags at blk %jd\n", frags, bno);
+	cg = dtog(fs, bno);
+	sc = cg_lookup(cg);
+	cgp = sc->sc_cgp;
+	cgbno = dtogd(fs, bno);
+	blksfree = cg_blksfree(cgp);
+
+	/*
+	 * If it's not allocated we only wrote the journal entry
+	 * and never the bitmaps.  Here we unconditionally clear and
+	 * resolve the cg summary later.
+	 */
+	if (frags == fs->fs_frag && mask == 0) {
+		fragno = fragstoblks(fs, cgbno);
+		ffs_setblock(fs, blksfree, fragno);
+		freeblocks++;
+	} else {
+		/*
+		 * deallocate the fragment
+		 */
+		for (i = 0; i < frags; i++)
+			if ((mask & (1 << i)) == 0 && isclr(blksfree, cgbno +i)) {
+				freefrags++;
+				setbit(blksfree, cgbno + i);
+			}
+	}
+	sc->sc_dirty = 1;
+}
+
+/*
+ * Returns 1 if the whole block starting at 'bno' is marked free and 0
+ * otherwise.
+ */
+static int
+blk_isfree(ufs2_daddr_t bno)
+{
+	struct suj_cg *sc;
+
+	sc = cg_lookup(dtog(fs, bno));
+	return ffs_isblock(fs, cg_blksfree(sc->sc_cgp), dtogd(fs, bno));
+}
+
+/*
+ * Fetch an indirect block to find the block at a given lbn.  The lbn
+ * may be negative to fetch a specific indirect block pointer or positive
+ * to fetch a specific block.
+ */
+static ufs2_daddr_t
+indir_blkatoff(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t cur, ufs_lbn_t lbn)
+{
+	ufs2_daddr_t *bap2;
+	ufs2_daddr_t *bap1;
+	ufs_lbn_t lbnadd;
+	ufs_lbn_t base;
+	int level;
+	int i;
+
+	if (blk == 0)
+		return (0);
+	level = lbn_level(cur);
+	if (level == -1)
+		errx(1, "Invalid indir lbn %jd", lbn);
+	if (level == 0 && lbn < 0)
+		errx(1, "Invalid lbn %jd", lbn);
+	bap2 = (void *)dblk_read(blk, fs->fs_bsize);
+	bap1 = (void *)bap2;
+	lbnadd = 1;
+	base = -(cur + level);
+	for (i = level; i > 0; i--)
+		lbnadd *= NINDIR(fs);
+	if (lbn > 0) 
+		i = (lbn - base) / lbnadd;
+	else
+		i = (-lbn - base) / lbnadd;
+	if (i < 0 || i >= NINDIR(fs))
+		errx(1, "Invalid indirect index %d produced by lbn %jd",
+		    i, lbn);
+	if (level == 0)
+		cur = base + (i * lbnadd);
+	else
+		cur = -(base + (i * lbnadd)) - (level - 1);
+	if (fs->fs_magic == FS_UFS1_MAGIC)
+		blk = bap1[i];
+	else
+		blk = bap2[i];
+	if (cur == lbn)
+		return (blk);
+	if (level == 0) {
+		abort();
+		errx(1, "Invalid lbn %jd at level 0", lbn);
+	}
+	return indir_blkatoff(blk, ino, cur, lbn);
+}
+
+/*
+ * Finds the disk block address at the specified lbn within the inode
+ * specified by ip.  This follows the whole tree and honors di_size and
+ * di_extsize so it is a true test of reachability.  The lbn may be
+ * negative if an extattr or indirect block is requested.
+ */
+static ufs2_daddr_t
+ino_blkatoff(union dinode *ip, ino_t ino, ufs_lbn_t lbn, int *frags)
+{
+	ufs_lbn_t tmpval;
+	ufs_lbn_t cur;
+	ufs_lbn_t next;
+	int i;
+
+	/*
+	 * Handle extattr blocks first.
+	 */
+	if (lbn < 0 && lbn >= -NXADDR) {
+		lbn = -1 - lbn;
+		if (lbn > lblkno(fs, ip->dp2.di_extsize - 1))
+			return (0);
+		*frags = numfrags(fs, sblksize(fs, ip->dp2.di_extsize, lbn));
+		return (ip->dp2.di_extb[lbn]);
+	}
+	/*
+	 * Now direct and indirect.
+	 */
+	if (DIP(ip, di_mode) == IFLNK &&
+	    DIP(ip, di_size) < fs->fs_maxsymlinklen)
+		return (0);
+	if (lbn >= 0 && lbn < NDADDR) {
+		*frags = numfrags(fs, sblksize(fs, DIP(ip, di_size), lbn));
+		return (DIP(ip, di_db[lbn]));
+	}
+	*frags = fs->fs_frag;
+
+	for (i = 0, tmpval = NINDIR(fs), cur = NDADDR; i < NIADDR; i++,
+	    tmpval *= NINDIR(fs), cur = next) {
+		next = cur + tmpval;
+		if (lbn == -cur - i)
+			return (DIP(ip, di_ib[i]));
+		/*
+		 * Determine whether the lbn in question is within this tree.
+		 */
+		if (lbn < 0 && -lbn >= next)
+			continue;
+		if (lbn > 0 && lbn >= next)
+			continue;
+		return indir_blkatoff(DIP(ip, di_ib[i]), ino, -cur - i, lbn);
+	}
+	errx(1, "lbn %jd not in ino", lbn);
+}
+
+/*
+ * Determine whether a block exists at a particular lbn in an inode.
+ * Returns 1 if found, 0 if not.  lbn may be negative for indirects
+ * or ext blocks.
+ */
+static int
+blk_isat(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int *frags)
+{
+	union dinode *ip;
+	ufs2_daddr_t nblk;
+
+	ip = ino_read(ino);
+
+	if (DIP(ip, di_nlink) == 0 || DIP(ip, di_mode) == 0)
+		return (0);
+	nblk = ino_blkatoff(ip, ino, lbn, frags);
+
+	return (nblk == blk);
+}
+
+/*
+ * Determines whether a pointer to an inode exists within a directory
+ * at a specified offset.  Returns the mode of the found entry.
+ */
+static int
+ino_isat(ino_t parent, off_t diroff, ino_t child, int *mode, int *isdot)
+{
+	union dinode *dip;
+	struct direct *dp;
+	ufs2_daddr_t blk;
+	uint8_t *block;
+	ufs_lbn_t lbn;
+	int blksize;
+	int frags;
+	int dpoff;
+	int doff;
+
+	*isdot = 0;
+	dip = ino_read(parent);
+	*mode = DIP(dip, di_mode);
+	if ((*mode & IFMT) != IFDIR) {
+		if (debug) {
+			/*
+			 * This can happen if the parent inode
+			 * was reallocated.
+			 */
+			if (*mode != 0)
+				printf("Directory %d has bad mode %o\n",
+				    parent, *mode);
+			else
+				printf("Directory %d zero inode\n", parent);
+		}
+		return (0);
+	}
+	lbn = lblkno(fs, diroff);
+	doff = blkoff(fs, diroff);
+	blksize = sblksize(fs, DIP(dip, di_size), lbn);
+	if (diroff + DIRECTSIZ(1) > DIP(dip, di_size) || doff >= blksize) {
+		if (debug)
+			printf("ino %d absent from %d due to offset %jd"
+			    " exceeding size %jd\n",
+			    child, parent, diroff, DIP(dip, di_size));
+		return (0);
+	}
+	blk = ino_blkatoff(dip, parent, lbn, &frags);
+	if (blk <= 0) {
+		if (debug)
+			printf("Sparse directory %d", parent);
+		return (0);
+	}
+	block = dblk_read(blk, blksize);
+	/*
+	 * Walk through the records from the start of the block to be
+	 * certain we hit a valid record and not some junk in the middle
+	 * of a file name.  Stop when we reach or pass the expected offset.
+	 */
+	dpoff = (doff / DIRBLKSIZ) * DIRBLKSIZ;
+	do {
+		dp = (struct direct *)&block[dpoff];
+		if (dpoff == doff)
+			break;
+		if (dp->d_reclen == 0)
+			break;
+		dpoff += dp->d_reclen;
+	} while (dpoff <= doff);
+	if (dpoff > fs->fs_bsize)
+		errx(1, "Corrupt directory block in dir ino %d", parent);
+	/* Not found. */
+	if (dpoff != doff) {
+		if (debug)
+			printf("ino %d not found in %d, lbn %jd, dpoff %d\n",
+			    child, parent, lbn, dpoff);
+		return (0);
+	}
+	/*
+	 * We found the item in question.  Record the mode and whether it's
+	 * a . or .. link for the caller.
+	 */
+	if (dp->d_ino == child) {
+		if (child == parent)
+			*isdot = 1;
+		else if (dp->d_namlen == 2 &&
+		    dp->d_name[0] == '.' && dp->d_name[1] == '.')
+			*isdot = 1;
+		*mode = DTTOIF(dp->d_type);
+		return (1);
+	}
+	if (debug)
+		printf("ino %d doesn't match dirent ino %d in parent %d\n",
+		    child, dp->d_ino, parent);
+	return (0);
+}
+
+#define	VISIT_INDIR	0x0001
+#define	VISIT_EXT	0x0002
+#define	VISIT_ROOT	0x0004	/* Operation came via root & valid pointers. */
+
+/*
+ * Read an indirect level which may or may not be linked into an inode.
+ */
+static void
+indir_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, uint64_t *frags,
+    ino_visitor visitor, int flags)
+{
+	ufs2_daddr_t *bap2;
+	ufs1_daddr_t *bap1;
+	ufs_lbn_t lbnadd;
+	ufs2_daddr_t nblk;
+	ufs_lbn_t nlbn;
+	int level;
+	int i;
+
+	/*
+	 * Don't visit indirect blocks with contents we can't trust.  This
+	 * should only happen when indir_visit() is called to complete a
+	 * truncate that never finished and not when a pointer is found via
+	 * an inode.
+	 */
+	if (blk == 0)
+		return;
+	level = lbn_level(lbn);
+	if (level == -1)
+		errx(1, "Invalid level for lbn %jd", lbn);
+	if ((flags & VISIT_ROOT) == 0 && blk_isindir(blk, ino, lbn) == 0) {
+		if (debug)
+			printf("blk %jd ino %d lbn %jd(%d) is not indir.\n",
+			    blk, ino, lbn, level);
+		goto out;
+	}
+	lbnadd = 1;
+	for (i = level; i > 0; i--)
+		lbnadd *= NINDIR(fs);
+	bap1 = (void *)dblk_read(blk, fs->fs_bsize);
+	bap2 = (void *)bap1;
+	for (i = 0; i < NINDIR(fs); i++) {
+		if (fs->fs_magic == FS_UFS1_MAGIC)
+			nblk = *bap1++;
+		else
+			nblk = *bap2++;
+		if (nblk == 0)
+			continue;
+		if (level == 0) {
+			nlbn = -lbn + i * lbnadd;
+			(*frags) += fs->fs_frag;
+			visitor(ino, nlbn, nblk, fs->fs_frag);
+		} else {
+			nlbn = (lbn + 1) - (i * lbnadd);
+			indir_visit(ino, nlbn, nblk, frags, visitor, flags);
+		}
+	}
+out:
+	if (flags & VISIT_INDIR) {
+		(*frags) += fs->fs_frag;
+		visitor(ino, lbn, blk, fs->fs_frag);
+	}
+}
+
+/*
+ * Visit each block in an inode as specified by 'flags' and call a
+ * callback function.  The callback may inspect or free blocks.  The
+ * count of frags found according to the size in the file is returned.
+ * This is not valid for sparse files but may be used to determine
+ * the correct di_blocks for a file.
+ */
+static uint64_t
+ino_visit(union dinode *ip, ino_t ino, ino_visitor visitor, int flags)
+{
+	ufs_lbn_t nextlbn;
+	ufs_lbn_t tmpval;
+	ufs_lbn_t lbn;
+	uint64_t size;
+	uint64_t fragcnt;
+	int mode;
+	int frags;
+	int i;
+
+	size = DIP(ip, di_size);
+	mode = DIP(ip, di_mode) & IFMT;
+	fragcnt = 0;
+	if ((flags & VISIT_EXT) &&
+	    fs->fs_magic == FS_UFS2_MAGIC && ip->dp2.di_extsize) {
+		for (i = 0; i < NXADDR; i++) {
+			if (ip->dp2.di_extb[i] == 0)
+				continue;
+			frags = sblksize(fs, ip->dp2.di_extsize, i);
+			frags = numfrags(fs, frags);
+			fragcnt += frags;
+			visitor(ino, -1 - i, ip->dp2.di_extb[i], frags);
+		}
+	}
+	/* Skip datablocks for short links and devices. */
+	if (mode == IFBLK || mode == IFCHR ||
+	    (mode == IFLNK && size < fs->fs_maxsymlinklen))
+		return (fragcnt);
+	for (i = 0; i < NDADDR; i++) {
+		if (DIP(ip, di_db[i]) == 0)
+			continue;
+		frags = sblksize(fs, size, i);
+		frags = numfrags(fs, frags);
+		fragcnt += frags;
+		visitor(ino, i, DIP(ip, di_db[i]), frags);
+	}
+	/*
+	 * We know the following indirects are real as we're following
+	 * real pointers to them.
+	 */
+	flags |= VISIT_ROOT;
+	for (i = 0, tmpval = NINDIR(fs), lbn = NDADDR; i < NIADDR; i++,
+	    lbn = nextlbn) {
+		nextlbn = lbn + tmpval;
+		tmpval *= NINDIR(fs);
+		if (DIP(ip, di_ib[i]) == 0)
+			continue;
+		indir_visit(ino, -lbn - i, DIP(ip, di_ib[i]), &fragcnt, visitor,
+		    flags);
+	}
+	return (fragcnt);
+}
+
+/*
+ * Null visitor function used when we just want to count blocks and
+ * record the lbn.
+ */
+ufs_lbn_t visitlbn;
+static void
+null_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
+{
+	if (lbn > 0)
+		visitlbn = lbn;
+}
+
+/*
+ * Recalculate di_blocks when we discover that a block allocation or
+ * free was not successfully completed.  The kernel does not roll this back
+ * because it would be too expensive to compute which indirects were
+ * reachable at the time the inode was written.
+ */
+static void
+ino_adjblks(struct suj_ino *sino)
+{
+	union dinode *ip;
+	uint64_t blocks;
+	uint64_t frags;
+	off_t isize;
+	off_t size;
+	ino_t ino;
+
+	ino = sino->si_ino;
+	ip = ino_read(ino);
+	/* No need to adjust zero'd inodes. */
+	if (DIP(ip, di_mode) == 0)
+		return;
+	/*
+	 * Visit all blocks and count them as well as recording the last
+	 * valid lbn in the file.  If the file size doesn't agree with the
+	 * last lbn we need to truncate to fix it.  Otherwise just adjust
+	 * the blocks count.
+	 */
+	visitlbn = 0;
+	frags = ino_visit(ip, ino, null_visit, VISIT_INDIR | VISIT_EXT);
+	blocks = fsbtodb(fs, frags);
+	/*
+	 * We assume the size and direct block list is kept coherent by
+	 * softdep.  For files that have extended into indirects we truncate
+	 * to the size in the inode or the maximum size permitted by
+	 * populated indirects.
+	 */
+	if (visitlbn >= NDADDR) {
+		isize = DIP(ip, di_size);
+		size = lblktosize(fs, visitlbn + 1);
+		if (isize > size)
+			isize = size;
+		/* Always truncate to free any unpopulated indirects. */
+		ino_trunc(sino->si_ino, isize);
+		return;
+	}
+	if (blocks == DIP(ip, di_blocks))
+		return;
+	if (debug)
+		printf("ino %d adjusting block count from %jd to %jd\n",
+		    ino, DIP(ip, di_blocks), blocks);
+	DIP_SET(ip, di_blocks, blocks);
+	ino_dirty(ino);
+}
+
+static void
+blk_free_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
+{
+	int mask;
+
+	mask = blk_freemask(blk, ino, lbn, frags);
+	if (debug)
+		printf("blk %jd freemask 0x%X\n", blk, mask);
+	blk_free(blk, mask, frags);
+}
+
+/*
+ * Free a block or tree of blocks that was previously rooted in ino at
+ * the given lbn.  If the lbn is an indirect all children are freed
+ * recursively.
+ */
+static void
+blk_free_lbn(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn, int frags, int follow)
+{
+	uint64_t resid;
+	int mask;
+
+	mask = blk_freemask(blk, ino, lbn, frags);
+	if (debug)
+		printf("blk %jd freemask 0x%X\n", blk, mask);
+	resid = 0;
+	if (lbn <= -NDADDR && follow && mask == 0)
+		indir_visit(ino, lbn, blk, &resid, blk_free_visit, VISIT_INDIR);
+	else
+		blk_free(blk, mask, frags);
+}
+
+static void
+ino_setskip(struct suj_ino *sino, ino_t parent)
+{
+	int isdot;
+	int mode;
+
+	if (ino_isat(sino->si_ino, DOTDOT_OFFSET, parent, &mode, &isdot))
+		sino->si_skipparent = 1;
+}
+
+/*
+ * Free the children of a directory when the directory is discarded.
+ */
+static void
+ino_free_children(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
+{
+	struct suj_ino *sino;
+	struct suj_rec *srec;
+	struct jrefrec *rrec;
+	struct direct *dp;
+	off_t diroff;
+	uint8_t *block;
+	int skipparent;
+	int isparent;
+	int dpoff;
+	int size;
+
+	sino = ino_lookup(ino, 0);
+	if (sino)
+		skipparent = sino->si_skipparent;
+	else
+		skipparent = 0;
+	size = lfragtosize(fs, frags);
+	block = dblk_read(blk, size);
+	dp = (struct direct *)&block[0];
+	for (dpoff = 0; dpoff < size && dp->d_reclen; dpoff += dp->d_reclen) {
+		dp = (struct direct *)&block[dpoff];
+		if (dp->d_ino == 0 || dp->d_ino == WINO)
+			continue;
+		if (dp->d_namlen == 1 && dp->d_name[0] == '.')
+			continue;
+		isparent = dp->d_namlen == 2 && dp->d_name[0] == '.' &&
+		    dp->d_name[1] == '.';
+		if (isparent && skipparent == 1)
+			continue;
+		if (debug)
+			printf("Directory %d removing ino %d name %s\n",
+			    ino, dp->d_ino, dp->d_name);
+		/*
+		 * Lookup this inode to see if we have a record for it.
+		 * If not, we've already adjusted it assuming this path
+		 * was valid and we have to adjust once more.
+		 */
+		sino = ino_lookup(dp->d_ino, 0);
+		if (sino == NULL || sino->si_hasrecs == 0) {
+			ino_decr(ino);
+			continue;
+		}
+		/*
+		 * Use ino_adjust() so if we lose the last non-dot reference
+		 * to a directory it can be discarded.
+		 */
+		if (sino->si_linkadj) {
+			sino->si_nlink--;
+			if (isparent)
+				sino->si_dotlinks--;
+			ino_adjust(sino);
+		}
+		/*
+		 * Tell any child directories we've already removed their
+		 * parent.  Don't try to adjust our link down again.
+		 */
+		if (isparent == 0)
+			ino_setskip(sino, ino);
+		/*
+		 * If we haven't yet processed this inode we need to make
+		 * sure we will successfully discover the lost path.  If not
+		 * use nlinkadj to remember.
+		 */
+		diroff = lblktosize(fs, lbn) + dpoff;
+		TAILQ_FOREACH(srec, &sino->si_recs, sr_next) {
+			rrec = (struct jrefrec *)srec->sr_rec;
+			if (rrec->jr_parent == ino &&
+			    rrec->jr_diroff == diroff)
+				break;
+		}
+		if (srec == NULL)
+			sino->si_nlinkadj++;
+	}
+}
+
+/*
+ * Reclaim an inode, freeing all blocks and decrementing all children's
+ * link counts.  Free the inode back to the cg.
+ */
+static void
+ino_reclaim(union dinode *ip, ino_t ino, int mode)
+{
+	uint32_t gen;
+
+	if (ino == ROOTINO)
+		errx(1, "Attempting to free ROOTINO");
+	if (debug)
+		printf("Truncating and freeing ino %d, nlink %d, mode %o\n",
+		    ino, DIP(ip, di_nlink), DIP(ip, di_mode));
+
+	/* We are freeing an inode or directory. */
+	if ((DIP(ip, di_mode) & IFMT) == IFDIR)
+		ino_visit(ip, ino, ino_free_children, 0);
+	DIP_SET(ip, di_nlink, 0);
+	ino_visit(ip, ino, blk_free_visit, VISIT_EXT | VISIT_INDIR);
+	/* Here we have to clear the inode and release any blocks it holds. */
+	gen = DIP(ip, di_gen);
+	if (fs->fs_magic == FS_UFS1_MAGIC)
+		bzero(ip, sizeof(struct ufs1_dinode));
+	else
+		bzero(ip, sizeof(struct ufs2_dinode));
+	DIP_SET(ip, di_gen, gen);
+	ino_dirty(ino);
+	ino_free(ino, mode);
+	return;
+}
+
+/*
+ * Adjust an inode's link count down by one when a directory goes away.
+ */
+static void
+ino_decr(ino_t ino)
+{
+	union dinode *ip;
+	int reqlink;
+	int nlink;
+	int mode;
+
+	ip = ino_read(ino);
+	nlink = DIP(ip, di_nlink);
+	mode = DIP(ip, di_mode);
+	if (nlink < 1)
+		errx(1, "Inode %d link count %d invalid", ino, nlink);
+	if (mode == 0)
+		errx(1, "Inode %d has a link of %d with 0 mode.", ino, nlink);
+	nlink--;
+	if ((mode & IFMT) == IFDIR)
+		reqlink = 2;
+	else
+		reqlink = 1;
+	if (nlink < reqlink) {
+		if (debug)
+			printf("ino %d not enough links to live %d < %d\n",
+			    ino, nlink, reqlink);
+		ino_reclaim(ip, ino, mode);
+		return;
+	}
+	DIP_SET(ip, di_nlink, nlink);
+	ino_dirty(ino);
+}
+
+/*
+ * Adjust the inode link count to 'nlink'.  If the count reaches zero
+ * free it.
+ */
+static void
+ino_adjust(struct suj_ino *sino)
+{
+	struct jrefrec *rrec;
+	struct suj_rec *srec;
+	struct suj_ino *stmp;
+	union dinode *ip;
+	nlink_t nlink;
+	int reqlink;
+	int mode;
+	ino_t ino;
+
+	nlink = sino->si_nlink;
+	ino = sino->si_ino;
+	/*
+	 * If it's a directory with no real names pointing to it go ahead
+	 * and truncate it.  This will free any children.
+	 */
+	if ((sino->si_mode & IFMT) == IFDIR &&
+	    nlink - sino->si_dotlinks == 0) {
+		sino->si_nlink = nlink = 0;
+		/*
+		 * Mark any .. links so they know not to free this inode
+		 * when they are removed.
+		 */
+		TAILQ_FOREACH(srec, &sino->si_recs, sr_next) {
+			rrec = (struct jrefrec *)srec->sr_rec;
+			if (rrec->jr_diroff == DOTDOT_OFFSET) {
+				stmp = ino_lookup(rrec->jr_parent, 0);
+				if (stmp)
+					ino_setskip(stmp, ino);
+			}
+		}
+	}
+	ip = ino_read(ino);
+	mode = DIP(ip, di_mode) & IFMT;
+	if (nlink > LINK_MAX)
+		errx(1,
+		    "ino %d nlink manipulation error, new link %d, old link %d",
+		    ino, nlink, DIP(ip, di_nlink));
+	if (debug)
+		printf("Adjusting ino %d, nlink %d, old link %d lastmode %o\n",
+		    ino, nlink, DIP(ip, di_nlink), sino->si_mode);
+	if (mode == 0) {
+		if (debug)
+			printf("ino %d, zero inode freeing bitmap\n", ino);
+		ino_free(ino, sino->si_mode);
+		return;
+	}
+	/* XXX Should be an assert? */
+	if (mode != sino->si_mode && debug)
+		printf("ino %d, mode %o != %o\n", ino, mode, sino->si_mode);
+	if ((mode & IFMT) == IFDIR)
+		reqlink = 2;
+	else
+		reqlink = 1;
+	/* If the inode doesn't have enough links to live, free it. */
+	if (nlink < reqlink) {
+		if (debug)
+			printf("ino %d not enough links to live %d < %d\n",
+			    ino, nlink, reqlink);
+		ino_reclaim(ip, ino, mode);
+		return;
+	}
+	/* If required write the updated link count. */
+	if (DIP(ip, di_nlink) == nlink) {
+		if (debug)
+			printf("ino %d, link matches, skipping.\n", ino);
+		return;
+	}
+	DIP_SET(ip, di_nlink, nlink);
+	ino_dirty(ino);
+}
+
+/*
+ * Truncate some or all blocks in an indirect, freeing any that are required
+ * and zeroing the indirect.
+ */
+static void
+indir_trunc(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, ufs_lbn_t lastlbn)
+{
+	ufs2_daddr_t *bap2;
+	ufs1_daddr_t *bap1;
+	ufs_lbn_t lbnadd;
+	ufs2_daddr_t nblk;
+	ufs_lbn_t next;
+	ufs_lbn_t nlbn;
+	int dirty;
+	int level;
+	int i;
+
+	if (blk == 0)
+		return;
+	dirty = 0;
+	level = lbn_level(lbn);
+	if (level == -1)
+		errx(1, "Invalid level for lbn %jd", lbn);
+	lbnadd = 1;
+	for (i = level; i > 0; i--)
+		lbnadd *= NINDIR(fs);
+	bap1 = (void *)dblk_read(blk, fs->fs_bsize);
+	bap2 = (void *)bap1;
+	for (i = 0; i < NINDIR(fs); i++) {
+		if (fs->fs_magic == FS_UFS1_MAGIC)
+			nblk = *bap1++;
+		else
+			nblk = *bap2++;
+		if (nblk == 0)
+			continue;
+		if (level != 0) {
+			nlbn = (lbn + 1) - (i * lbnadd);
+			/*
+			 * Calculate the lbn of the next indirect to
+			 * determine if any of this indirect must be
+			 * reclaimed.
+			 */
+			next = -(lbn + level) + ((i+1) * lbnadd);
+			if (next <= lastlbn)
+				continue;
+			indir_trunc(ino, nlbn, nblk, lastlbn);
+			/* If all of this indirect was reclaimed, free it. */
+			nlbn = next - lbnadd;
+			if (nlbn < lastlbn)
+				continue;
+		} else {
+			nlbn = -lbn + i * lbnadd;
+			if (nlbn < lastlbn)
+				continue;
+		}
+		dirty = 1;
+		blk_free(nblk, 0, fs->fs_frag);
+		if (fs->fs_magic == FS_UFS1_MAGIC)
+			*(bap1 - 1) = 0;
+		else
+			*(bap2 - 1) = 0;
+	}
+	if (dirty)
+		dblk_dirty(blk);
+}
+
+/*
+ * Truncate an inode to the minimum of the given size or the last populated
+ * block after any over size have been discarded.  The kernel would allocate
+ * the last block in the file but fsck does not and neither do we.  This
+ * code never extends files, only shrinks them.
+ */
+static void
+ino_trunc(ino_t ino, off_t size)
+{
+	union dinode *ip;
+	ufs2_daddr_t bn;
+	uint64_t totalfrags;
+	ufs_lbn_t nextlbn;
+	ufs_lbn_t lastlbn;
+	ufs_lbn_t tmpval;
+	ufs_lbn_t lbn;
+	ufs_lbn_t i;
+	int frags;
+	off_t cursize;
+	off_t off;
+	int mode;
+
+	ip = ino_read(ino);
+	mode = DIP(ip, di_mode) & IFMT;
+	cursize = DIP(ip, di_size);
+	if (debug)
+		printf("Truncating ino %d, mode %o to size %jd from size %jd\n",
+		    ino, mode, size, cursize);
+
+	/* Skip datablocks for short links and devices. */
+	if (mode == 0 || mode == IFBLK || mode == IFCHR ||
+	    (mode == IFLNK && cursize < fs->fs_maxsymlinklen))
+		return;
+	/* Don't extend. */
+	if (size > cursize)
+		size = cursize;
+	lastlbn = lblkno(fs, blkroundup(fs, size));
+	for (i = lastlbn; i < NDADDR; i++) {
+		if (DIP(ip, di_db[i]) == 0)
+			continue;
+		frags = sblksize(fs, cursize, i);
+		frags = numfrags(fs, frags);
+		blk_free(DIP(ip, di_db[i]), 0, frags);
+		DIP_SET(ip, di_db[i], 0);
+	}
+	/*
+	 * Follow indirect blocks, freeing anything required.
+	 */
+	for (i = 0, tmpval = NINDIR(fs), lbn = NDADDR; i < NIADDR; i++,
+	    lbn = nextlbn) {
+		nextlbn = lbn + tmpval;
+		tmpval *= NINDIR(fs);
+		/* If we're not freeing any in this indirect range skip it. */
+		if (lastlbn >= nextlbn)
+			continue;
+		if (DIP(ip, di_ib[i]) == 0)
+			continue;
+		indir_trunc(ino, -lbn - i, DIP(ip, di_ib[i]), lastlbn);
+		/* If we freed everything in this indirect free the indir. */
+		if (lastlbn > lbn)
+			continue;
+		blk_free(DIP(ip, di_ib[i]), 0, frags);
+		DIP_SET(ip, di_ib[i], 0);
+	}
+	ino_dirty(ino);
+	/*
+	 * Now that we've freed any whole blocks that exceed the desired
+	 * truncation size, figure out how many blocks remain and what the
+	 * last populated lbn is.  We will set the size to this last lbn
+	 * rather than worrying about allocating the final lbn as the kernel
+	 * would've done.  This is consistent with normal fsck behavior.
+	 */ 
+	visitlbn = 0;
+	totalfrags = ino_visit(ip, ino, null_visit, VISIT_INDIR | VISIT_EXT);
+	if (size > lblktosize(fs, visitlbn + 1))
+		size = lblktosize(fs, visitlbn + 1);
+	/*
+	 * If we're truncating direct blocks we have to adjust frags
+	 * accordingly.
+	 */
+	if (visitlbn < NDADDR && totalfrags) {
+		long oldspace, newspace;
+
+		bn = DIP(ip, di_db[visitlbn]);
+		if (bn == 0)
+			errx(1, "Bad blk at ino %d lbn %jd\n", ino, visitlbn);
+		oldspace = sblksize(fs, cursize, visitlbn);
+		newspace = sblksize(fs, size, visitlbn);
+		if (oldspace != newspace) {
+			bn += numfrags(fs, newspace);
+			frags = numfrags(fs, oldspace - newspace);
+			blk_free(bn, 0, frags);
+			totalfrags -= frags;
+		}
+	}
+	DIP_SET(ip, di_blocks, fsbtodb(fs, totalfrags));
+	DIP_SET(ip, di_size, size);
+	/*
+	 * If we've truncated into the middle of a block or frag we have
+	 * to zero it here.  Otherwise the file could extend into
+	 * uninitialized space later.
+	 */
+	off = blkoff(fs, size);
+	if (off) {
+		uint8_t *buf;
+		long clrsize;
+
+		bn = ino_blkatoff(ip, ino, visitlbn, &frags);
+		if (bn == 0)
+			errx(1, "Block missing from ino %d at lbn %jd\n",
+			    ino, visitlbn);
+		clrsize = frags * fs->fs_fsize;
+		buf = dblk_read(bn, clrsize);
+		clrsize -= off;
+		buf += off;
+		bzero(buf, clrsize);
+		dblk_dirty(bn);
+	}
+	return;
+}
+
+/*
+ * Process records available for one inode and determine whether the
+ * link count is correct or needs adjusting.
+ */
+static void
+ino_check(struct suj_ino *sino)
+{
+	struct suj_rec *srec;
+	struct jrefrec *rrec;
+	nlink_t dotlinks;
+	int newlinks;
+	int removes;
+	int nlink;
+	ino_t ino;
+	int isdot;
+	int isat;
+	int mode;
+
+	if (sino->si_hasrecs == 0)
+		return;
+	ino = sino->si_ino;
+	rrec = (struct jrefrec *)TAILQ_FIRST(&sino->si_recs)->sr_rec;
+	nlink = rrec->jr_nlink;
+	newlinks = 0;
+	dotlinks = 0;
+	removes = sino->si_nlinkadj;
+	TAILQ_FOREACH(srec, &sino->si_recs, sr_next) {
+		rrec = (struct jrefrec *)srec->sr_rec;
+		isat = ino_isat(rrec->jr_parent, rrec->jr_diroff, 
+		    rrec->jr_ino, &mode, &isdot);
+		if (isat && (mode & IFMT) != (rrec->jr_mode & IFMT))
+			errx(1, "Inode mode/directory type mismatch %o != %o",
+			    mode, rrec->jr_mode);
+		if (debug)
+			printf("jrefrec: op %d ino %d, nlink %d, parent %d, "
+			    "diroff %jd, mode %o, isat %d, isdot %d\n",
+			    rrec->jr_op, rrec->jr_ino, rrec->jr_nlink,
+			    rrec->jr_parent, rrec->jr_diroff, rrec->jr_mode,
+			    isat, isdot);
+		mode = rrec->jr_mode & IFMT;
+		if (rrec->jr_op == JOP_REMREF)
+			removes++;
+		newlinks += isat;
+		if (isdot)
+			dotlinks += isat;
+	}
+	/*
+	 * The number of links that remain are the starting link count
+	 * subtracted by the total number of removes with the total
+	 * links discovered back in.  An incomplete remove thus
+	 * makes no change to the link count but an add increases
+	 * by one.
+	 */
+	if (debug)
+		printf("ino %d nlink %d newlinks %d removes %d dotlinks %d\n",
+		    ino, nlink, newlinks, removes, dotlinks);
+	nlink += newlinks;
+	nlink -= removes;
+	sino->si_linkadj = 1;
+	sino->si_nlink = nlink;
+	sino->si_dotlinks = dotlinks;
+	sino->si_mode = mode;
+	ino_adjust(sino);
+}
+
+/*
+ * Process records available for one block and determine whether it is
+ * still allocated and whether the owning inode needs to be updated or
+ * a free completed.
+ */
+static void
+blk_check(struct suj_blk *sblk)
+{
+	struct suj_rec *srec;
+	struct jblkrec *brec;
+	struct suj_ino *sino;
+	ufs2_daddr_t blk;
+	int mask;
+	int frags;
+	int isat;
+
+	/*
+	 * Each suj_blk actually contains records for any fragments in that
+	 * block.  As a result we must evaluate each record individually.
+	 */
+	sino = NULL;
+	TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) {
+		brec = (struct jblkrec *)srec->sr_rec;
+		frags = brec->jb_frags;
+		blk = brec->jb_blkno + brec->jb_oldfrags;
+		isat = blk_isat(brec->jb_ino, brec->jb_lbn, blk, &frags);
+		if (sino == NULL || sino->si_ino != brec->jb_ino) {
+			sino = ino_lookup(brec->jb_ino, 1);
+			sino->si_blkadj = 1;
+		}
+		if (debug)
+			printf("op %d blk %jd ino %d lbn %jd frags %d isat %d (%d)\n",
+			    brec->jb_op, blk, brec->jb_ino, brec->jb_lbn,
+			    brec->jb_frags, isat, frags);
+		/*
+		 * If we found the block at this address we still have to
+		 * determine if we need to free the tail end that was
+		 * added by adding contiguous fragments from the same block.
+		 */
+		if (isat == 1) {
+			if (frags == brec->jb_frags)
+				continue;
+			mask = blk_freemask(blk, brec->jb_ino, brec->jb_lbn,
+			    brec->jb_frags);
+			mask >>= frags;
+			blk += frags;
+			frags = brec->jb_frags - frags;
+			blk_free(blk, mask, frags);
+			continue;
+		}
+		/*
+	 	 * The block wasn't found, attempt to free it.  It won't be
+		 * freed if it was actually reallocated.  If this was an
+		 * allocation we don't want to follow indirects as they
+		 * may not be written yet.  Any children of the indirect will
+		 * have their own records.  If it's a free we need to
+		 * recursively free children.
+		 */
+		blk_free_lbn(blk, brec->jb_ino, brec->jb_lbn, brec->jb_frags,
+		    brec->jb_op == JOP_FREEBLK);
+	}
+}
+
+/*
+ * Walk the list of inode records for this cg and resolve moved and duplicate
+ * inode references now that we have a complete picture.
+ */
+static void
+cg_build(struct suj_cg *sc)
+{
+	struct suj_ino *sino;
+	int i;
+
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH(sino, &sc->sc_inohash[i], si_next)
+			ino_build(sino);
+}
+
+/*
+ * Handle inodes requiring truncation.  This must be done prior to
+ * looking up any inodes in directories.
+ */
+static void
+cg_trunc(struct suj_cg *sc)
+{
+	struct suj_ino *sino;
+	int i;
+
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH(sino, &sc->sc_inohash[i], si_next)
+			if (sino->si_trunc) {
+				ino_trunc(sino->si_ino,
+				    sino->si_trunc->jt_size);
+				sino->si_trunc = NULL;
+			}
+}
+
+/*
+ * Free any partially allocated blocks and then resolve inode block
+ * counts.
+ */
+static void
+cg_check_blk(struct suj_cg *sc)
+{
+	struct suj_ino *sino;
+	struct suj_blk *sblk;
+	int i;
+
+
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH(sblk, &sc->sc_blkhash[i], sb_next)
+			blk_check(sblk);
+	/*
+	 * Now that we've freed blocks which are not referenced we
+	 * make a second pass over all inodes to adjust their block
+	 * counts.
+	 */
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH(sino, &sc->sc_inohash[i], si_next)
+			if (sino->si_blkadj)
+				ino_adjblks(sino);
+}
+
+/*
+ * Walk the list of inode records for this cg, recovering any
+ * changes which were not complete at the time of crash.
+ */
+static void
+cg_check_ino(struct suj_cg *sc)
+{
+	struct suj_ino *sino;
+	int i;
+
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH(sino, &sc->sc_inohash[i], si_next)
+			ino_check(sino);
+}
+
+/*
+ * Write a potentially dirty cg.  Recalculate the summary information and
+ * update the superblock summary.
+ */
+static void
+cg_write(struct suj_cg *sc)
+{
+	ufs1_daddr_t fragno, cgbno, maxbno;
+	u_int8_t *blksfree;
+	struct cg *cgp;
+	int blk;
+	int i;
+
+	if (sc->sc_dirty == 0)
+		return;
+	/*
+	 * Fix the frag and cluster summary.
+	 */
+	cgp = sc->sc_cgp;
+	cgp->cg_cs.cs_nbfree = 0;
+	cgp->cg_cs.cs_nffree = 0;
+	bzero(&cgp->cg_frsum, sizeof(cgp->cg_frsum));
+	maxbno = fragstoblks(fs, fs->fs_fpg);
+	if (fs->fs_contigsumsize > 0) {
+		for (i = 1; i <= fs->fs_contigsumsize; i++)
+			cg_clustersum(cgp)[i] = 0;
+		bzero(cg_clustersfree(cgp), howmany(maxbno, CHAR_BIT));
+	}
+	blksfree = cg_blksfree(cgp);
+	for (cgbno = 0; cgbno < maxbno; cgbno++) {
+		if (ffs_isfreeblock(fs, blksfree, cgbno))
+			continue;
+		if (ffs_isblock(fs, blksfree, cgbno)) {
+			ffs_clusteracct(fs, cgp, cgbno, 1);
+			cgp->cg_cs.cs_nbfree++;
+			continue;
+		}
+		fragno = blkstofrags(fs, cgbno);
+		blk = blkmap(fs, blksfree, fragno);
+		ffs_fragacct(fs, blk, cgp->cg_frsum, 1);
+		for (i = 0; i < fs->fs_frag; i++)
+			if (isset(blksfree, fragno + i))
+				cgp->cg_cs.cs_nffree++;
+	}
+	/*
+	 * Update the superblock cg summary from our now correct values
+	 * before writing the block.
+	 */
+	fs->fs_cs(fs, sc->sc_cgx) = cgp->cg_cs;
+	if (bwrite(disk, fsbtodb(fs, cgtod(fs, sc->sc_cgx)), sc->sc_cgbuf,
+	    fs->fs_bsize) == -1)
+		err(1, "Unable to write cylinder group %d", sc->sc_cgx);
+}
+
+/*
+ * Write out any modified inodes.
+ */
+static void
+cg_write_inos(struct suj_cg *sc)
+{
+	struct ino_blk *iblk;
+	int i;
+
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH(iblk, &sc->sc_iblkhash[i], ib_next)
+			if (iblk->ib_dirty)
+				iblk_write(iblk);
+}
+
+static void
+cg_apply(void (*apply)(struct suj_cg *))
+{
+	struct suj_cg *scg;
+	int i;
+
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH(scg, &cghash[i], sc_next)
+			apply(scg);
+}
+
+/*
+ * Process the unlinked but referenced file list.  Freeing all inodes.
+ */
+static void
+ino_unlinked(void)
+{
+	union dinode *ip;
+	uint16_t mode;
+	ino_t inon;
+	ino_t ino;
+
+	ino = fs->fs_sujfree;
+	fs->fs_sujfree = 0;
+	while (ino != 0) {
+		ip = ino_read(ino);
+		mode = DIP(ip, di_mode) & IFMT;
+		inon = DIP(ip, di_freelink);
+		DIP_SET(ip, di_freelink, 0);
+		/*
+		 * XXX Should this be an errx?
+		 */
+		if (DIP(ip, di_nlink) == 0) {
+			if (debug)
+				printf("Freeing unlinked ino %d mode %o\n",
+				    ino, mode);
+			ino_reclaim(ip, ino, mode);
+		} else if (debug)
+			printf("Skipping ino %d mode %o with link %d\n",
+			    ino, mode, DIP(ip, di_nlink));
+		ino = inon;
+	}
+}
+
+/*
+ * Append a new record to the list of records requiring processing.
+ */
+static void
+ino_append(union jrec *rec)
+{
+	struct jrefrec *refrec;
+	struct jmvrec *mvrec;
+	struct suj_ino *sino;
+	struct suj_rec *srec;
+
+	mvrec = &rec->rec_jmvrec;
+	refrec = &rec->rec_jrefrec;
+	if (debug && mvrec->jm_op == JOP_MVREF)
+		printf("ino move: ino %d, parent %d, diroff %jd, oldoff %jd\n", 
+		    mvrec->jm_ino, mvrec->jm_parent, mvrec->jm_newoff,
+		    mvrec->jm_oldoff);
+	else if (debug &&
+	    (refrec->jr_op == JOP_ADDREF || refrec->jr_op == JOP_REMREF))
+		printf("ino ref: op %d, ino %d, nlink %d, "
+		    "parent %d, diroff %jd\n", 
+		    refrec->jr_op, refrec->jr_ino, refrec->jr_nlink,
+		    refrec->jr_parent, refrec->jr_diroff);
+	/*
+	 * Lookup the ino and clear truncate if one is found.  Partial
+	 * truncates are always done synchronously so if we discover
+	 * an operation that requires a lock the truncation has completed
+	 * and can be discarded.
+	 */
+	sino = ino_lookup(((struct jrefrec *)rec)->jr_ino, 1);
+	sino->si_trunc = NULL;
+	sino->si_hasrecs = 1;
+	srec = errmalloc(sizeof(*srec));
+	srec->sr_rec = rec;
+	TAILQ_INSERT_TAIL(&sino->si_newrecs, srec, sr_next);
+}
+
+/*
+ * Add a reference adjustment to the sino list and eliminate dups.  The
+ * primary loop in ino_build_ref() checks for dups but new ones may be
+ * created as a result of offset adjustments.
+ */
+static void
+ino_add_ref(struct suj_ino *sino, struct suj_rec *srec)
+{
+	struct jrefrec *refrec;
+	struct suj_rec *srn;
+	struct jrefrec *rrn;
+
+	refrec = (struct jrefrec *)srec->sr_rec;
+	/*
+	 * We walk backwards so that the oldest link count is preserved.  If
+	 * an add record conflicts with a remove keep the remove.  Redundant
+	 * removes are eliminated in ino_build_ref.  Otherwise we keep the
+	 * oldest record at a given location.
+	 */
+	for (srn = TAILQ_LAST(&sino->si_recs, srechd); srn;
+	    srn = TAILQ_PREV(srn, srechd, sr_next)) {
+		rrn = (struct jrefrec *)srn->sr_rec;
+		if (rrn->jr_parent != refrec->jr_parent ||
+		    rrn->jr_diroff != refrec->jr_diroff)
+			continue;
+		if (rrn->jr_op == JOP_REMREF || refrec->jr_op == JOP_ADDREF) {
+			rrn->jr_mode = refrec->jr_mode;
+			return;
+		}
+		/*
+		 * Adding a remove.
+		 *
+		 * Replace the record in place with the old nlink in case
+		 * we replace the head of the list.  Abandon srec as a dup.
+		 */
+		refrec->jr_nlink = rrn->jr_nlink;
+		srn->sr_rec = srec->sr_rec;
+		return;
+	}
+	TAILQ_INSERT_TAIL(&sino->si_recs, srec, sr_next);
+}
+
+/*
+ * Create a duplicate of a reference at a previous location.
+ */
+static void
+ino_dup_ref(struct suj_ino *sino, struct jrefrec *refrec, off_t diroff)
+{
+	struct jrefrec *rrn;
+	struct suj_rec *srn;
+
+	rrn = errmalloc(sizeof(*refrec));
+	*rrn = *refrec;
+	rrn->jr_op = JOP_ADDREF;
+	rrn->jr_diroff = diroff;
+	srn = errmalloc(sizeof(*srn));
+	srn->sr_rec = (union jrec *)rrn;
+	ino_add_ref(sino, srn);
+}
+
+/*
+ * Add a reference to the list at all known locations.  We follow the offset
+ * changes for a single instance and create duplicate add refs at each so
+ * that we can tolerate any version of the directory block.  Eliminate
+ * removes which collide with adds that are seen in the journal.  They should
+ * not adjust the link count down.
+ */
+static void
+ino_build_ref(struct suj_ino *sino, struct suj_rec *srec)
+{
+	struct jrefrec *refrec;
+	struct jmvrec *mvrec;
+	struct suj_rec *srp;
+	struct suj_rec *srn;
+	struct jrefrec *rrn;
+	off_t diroff;
+
+	refrec = (struct jrefrec *)srec->sr_rec;
+	/*
+	 * Search for a mvrec that matches this offset.  Whether it's an add
+	 * or a remove we can delete the mvref after creating a dup record in
+	 * the old location.
+	 */
+	if (!TAILQ_EMPTY(&sino->si_movs)) {
+		diroff = refrec->jr_diroff;
+		for (srn = TAILQ_LAST(&sino->si_movs, srechd); srn; srn = srp) {
+			srp = TAILQ_PREV(srn, srechd, sr_next);
+			mvrec = (struct jmvrec *)srn->sr_rec;
+			if (mvrec->jm_parent != refrec->jr_parent ||
+			    mvrec->jm_newoff != diroff)
+				continue;
+			diroff = mvrec->jm_oldoff;
+			TAILQ_REMOVE(&sino->si_movs, srn, sr_next);
+			ino_dup_ref(sino, refrec, diroff);
+		}
+	}
+	/*
+	 * If a remove wasn't eliminated by an earlier add just append it to
+	 * the list.
+	 */
+	if (refrec->jr_op == JOP_REMREF) {
+		ino_add_ref(sino, srec);
+		return;
+	}
+	/*
+	 * Walk the list of records waiting to be added to the list.  We
+	 * must check for moves that apply to our current offset and remove
+	 * them from the list.  Remove any duplicates to eliminate removes
+	 * with corresponding adds.
+	 */
+	TAILQ_FOREACH_SAFE(srn, &sino->si_newrecs, sr_next, srp) {
+		switch (srn->sr_rec->rec_jrefrec.jr_op) {
+		case JOP_ADDREF:
+			/*
+			 * This should actually be an error we should
+			 * have a remove for every add journaled.
+			 */
+			rrn = (struct jrefrec *)srn->sr_rec;
+			if (rrn->jr_parent != refrec->jr_parent ||
+			    rrn->jr_diroff != refrec->jr_diroff)
+				break;
+			TAILQ_REMOVE(&sino->si_newrecs, srn, sr_next);
+			break;
+		case JOP_REMREF:
+			/*
+			 * Once we remove the current iteration of the
+			 * record at this address we're done.
+			 */
+			rrn = (struct jrefrec *)srn->sr_rec;
+			if (rrn->jr_parent != refrec->jr_parent ||
+			    rrn->jr_diroff != refrec->jr_diroff)
+				break;
+			TAILQ_REMOVE(&sino->si_newrecs, srn, sr_next);
+			ino_add_ref(sino, srec);
+			return;
+		case JOP_MVREF:
+			/*
+			 * Update our diroff based on any moves that match
+			 * and remove the move.
+			 */
+			mvrec = (struct jmvrec *)srn->sr_rec;
+			if (mvrec->jm_parent != refrec->jr_parent ||
+			    mvrec->jm_oldoff != refrec->jr_diroff)
+				break;
+			ino_dup_ref(sino, refrec, mvrec->jm_oldoff);
+			refrec->jr_diroff = mvrec->jm_newoff;
+			TAILQ_REMOVE(&sino->si_newrecs, srn, sr_next);
+			break;
+		default:
+			errx(1, "ino_build_ref: Unknown op %d",
+			    srn->sr_rec->rec_jrefrec.jr_op);
+		}
+	}
+	ino_add_ref(sino, srec);
+}
+
+/*
+ * Walk the list of new records and add them in-order resolving any
+ * dups and adjusted offsets.
+ */
+static void
+ino_build(struct suj_ino *sino)
+{
+	struct suj_rec *srec;
+
+	while ((srec = TAILQ_FIRST(&sino->si_newrecs)) != NULL) {
+		TAILQ_REMOVE(&sino->si_newrecs, srec, sr_next);
+		switch (srec->sr_rec->rec_jrefrec.jr_op) {
+		case JOP_ADDREF:
+		case JOP_REMREF:
+			ino_build_ref(sino, srec);
+			break;
+		case JOP_MVREF:
+			/*
+			 * Add this mvrec to the queue of pending mvs.
+			 */
+			TAILQ_INSERT_TAIL(&sino->si_movs, srec, sr_next);
+			break;
+		default:
+			errx(1, "ino_build: Unknown op %d",
+			    srec->sr_rec->rec_jrefrec.jr_op);
+		}
+	}
+	if (TAILQ_EMPTY(&sino->si_recs))
+		sino->si_hasrecs = 0;
+}
+
+/*
+ * Modify journal records so they refer to the base block number
+ * and a start and end frag range.  This is to facilitate the discovery
+ * of overlapping fragment allocations.
+ */
+static void
+blk_build(struct jblkrec *blkrec)
+{
+	struct suj_rec *srec;
+	struct suj_blk *sblk;
+	struct jblkrec *blkrn;
+	struct suj_ino *sino;
+	ufs2_daddr_t blk;
+	off_t foff;
+	int frag;
+
+	if (debug)
+		printf("blk_build: op %d blkno %jd frags %d oldfrags %d "
+		    "ino %d lbn %jd\n",
+		    blkrec->jb_op, blkrec->jb_blkno, blkrec->jb_frags,
+		    blkrec->jb_oldfrags, blkrec->jb_ino, blkrec->jb_lbn);
+
+	/*
+	 * Look up the inode and clear the truncate if any lbns after the
+	 * truncate lbn are freed or allocated.
+	 */
+	sino = ino_lookup(blkrec->jb_ino, 0);
+	if (sino && sino->si_trunc) {
+		foff = lblktosize(fs, blkrec->jb_lbn);
+		foff += lfragtosize(fs, blkrec->jb_frags);
+		if (foff > sino->si_trunc->jt_size)
+			sino->si_trunc = NULL;
+	}
+	blk = blknum(fs, blkrec->jb_blkno);
+	frag = fragnum(fs, blkrec->jb_blkno);
+	sblk = blk_lookup(blk, 1);
+	/*
+	 * Rewrite the record using oldfrags to indicate the offset into
+	 * the block.  Leave jb_frags as the actual allocated count.
+	 */
+	blkrec->jb_blkno -= frag;
+	blkrec->jb_oldfrags = frag;
+	if (blkrec->jb_oldfrags + blkrec->jb_frags > fs->fs_frag)
+		errx(1, "Invalid fragment count %d oldfrags %d",
+		    blkrec->jb_frags, frag);
+	/*
+	 * Detect dups.  If we detect a dup we always discard the oldest
+	 * record as it is superseded by the new record.  This speeds up
+	 * later stages but also eliminates free records which are used
+	 * to indicate that the contents of indirects can be trusted.
+	 */
+	TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) {
+		blkrn = (struct jblkrec *)srec->sr_rec;
+		if (blkrn->jb_ino != blkrec->jb_ino ||
+		    blkrn->jb_lbn != blkrec->jb_lbn ||
+		    blkrn->jb_blkno != blkrec->jb_blkno ||
+		    blkrn->jb_frags != blkrec->jb_frags ||
+		    blkrn->jb_oldfrags != blkrec->jb_oldfrags)
+			continue;
+		if (debug)
+			printf("Removed dup.\n");
+		/* Discard the free which is a dup with an alloc. */
+		if (blkrec->jb_op == JOP_FREEBLK)
+			return;
+		TAILQ_REMOVE(&sblk->sb_recs, srec, sr_next);
+		free(srec);
+		break;
+	}
+	srec = errmalloc(sizeof(*srec));
+	srec->sr_rec = (union jrec *)blkrec;
+	TAILQ_INSERT_TAIL(&sblk->sb_recs, srec, sr_next);
+}
+
+static void
+ino_build_trunc(struct jtrncrec *rec)
+{
+	struct suj_ino *sino;
+
+	if (debug)
+		printf("ino_build_trunc: ino %d, size %jd\n",
+		    rec->jt_ino, rec->jt_size);
+	sino = ino_lookup(rec->jt_ino, 1);
+	sino->si_trunc = rec;
+}
+
+/*
+ * Build up tables of the operations we need to recover.
+ */
+static void
+suj_build(void)
+{
+	struct suj_seg *seg;
+	union jrec *rec;
+	int off;
+	int i;
+
+	TAILQ_FOREACH(seg, &allsegs, ss_next) {
+		if (debug)
+			printf("seg %jd has %d records, oldseq %jd.\n",
+			    seg->ss_rec.jsr_seq, seg->ss_rec.jsr_cnt,
+			    seg->ss_rec.jsr_oldest);
+		off = 0;
+		rec = (union jrec *)seg->ss_blk;
+		for (i = 0; i < seg->ss_rec.jsr_cnt; off += JREC_SIZE, rec++) {
+			/* skip the segrec. */
+			if ((off % DEV_BSIZE) == 0)
+				continue;
+			switch (rec->rec_jrefrec.jr_op) {
+			case JOP_ADDREF:
+			case JOP_REMREF:
+			case JOP_MVREF:
+				ino_append(rec);
+				break;
+			case JOP_NEWBLK:
+			case JOP_FREEBLK:
+				blk_build((struct jblkrec *)rec);
+				break;
+			case JOP_TRUNC:
+				ino_build_trunc((struct jtrncrec *)rec);
+				break;
+			default:
+				errx(1, "Unknown journal operation %d (%d)",
+				    rec->rec_jrefrec.jr_op, off);
+			}
+			i++;
+		}
+	}
+}
+
+/*
+ * Prune the journal segments to those we care about based on the
+ * oldest sequence in the newest segment.  Order the segment list
+ * based on sequence number.
+ */
+static void
+suj_prune(void)
+{
+	struct suj_seg *seg;
+	struct suj_seg *segn;
+	uint64_t newseq;
+	int discard;
+
+	if (debug)
+		printf("Pruning up to %jd\n", oldseq);
+	/* First free the expired segments. */
+	TAILQ_FOREACH_SAFE(seg, &allsegs, ss_next, segn) {
+		if (seg->ss_rec.jsr_seq >= oldseq)
+			continue;
+		TAILQ_REMOVE(&allsegs, seg, ss_next);
+		free(seg->ss_blk);
+		free(seg);
+	}
+	/* Next ensure that segments are ordered properly. */
+	seg = TAILQ_FIRST(&allsegs);
+	if (seg == NULL) {
+		if (debug)
+			printf("Empty journal\n");
+		return;
+	}
+	newseq = seg->ss_rec.jsr_seq;
+	for (;;) {
+		seg = TAILQ_LAST(&allsegs, seghd);
+		if (seg->ss_rec.jsr_seq >= newseq)
+			break;
+		TAILQ_REMOVE(&allsegs, seg, ss_next);
+		TAILQ_INSERT_HEAD(&allsegs, seg, ss_next);
+		newseq = seg->ss_rec.jsr_seq;
+		
+	}
+	if (newseq != oldseq)
+		errx(1, "Journal file sequence mismatch %jd != %jd",
+		    newseq, oldseq);
+	/*
+	 * The kernel may asynchronously write segments which can create
+	 * gaps in the sequence space.  Throw away any segments after the
+	 * gap as the kernel guarantees only those that are contiguously
+	 * reachable are marked as completed.
+	 */
+	discard = 0;
+	TAILQ_FOREACH_SAFE(seg, &allsegs, ss_next, segn) {
+		if (!discard && newseq++ == seg->ss_rec.jsr_seq) {
+			jrecs += seg->ss_rec.jsr_cnt;
+			jbytes += seg->ss_rec.jsr_blocks * DEV_BSIZE;
+			continue;
+		}
+		discard = 1;
+		if (debug)
+			printf("Journal order mismatch %jd != %jd pruning\n",
+			    newseq-1, seg->ss_rec.jsr_seq);
+		TAILQ_REMOVE(&allsegs, seg, ss_next);
+		free(seg->ss_blk);
+		free(seg);
+	}
+	if (debug)
+		printf("Processing journal segments from %jd to %jd\n",
+		    oldseq, newseq-1);
+}
+
+/*
+ * Verify the journal inode before attempting to read records.
+ */
+static int
+suj_verifyino(union dinode *ip)
+{
+
+	if (DIP(ip, di_nlink) != 1) {
+		printf("Invalid link count %d for journal inode %d\n",
+		    DIP(ip, di_nlink), sujino);
+		return (-1);
+	}
+
+	if ((DIP(ip, di_flags) & (SF_IMMUTABLE | SF_NOUNLINK)) !=
+	    (SF_IMMUTABLE | SF_NOUNLINK)) {
+		printf("Invalid flags 0x%X for journal inode %d\n",
+		    DIP(ip, di_flags), sujino);
+		return (-1);
+	}
+
+	if (DIP(ip, di_mode) != (IFREG | IREAD)) {
+		printf("Invalid mode %o for journal inode %d\n",
+		    DIP(ip, di_mode), sujino);
+		return (-1);
+	}
+
+	if (DIP(ip, di_size) < SUJ_MIN || DIP(ip, di_size) > SUJ_MAX) {
+		printf("Invalid size %jd for journal inode %d\n",
+		    DIP(ip, di_size), sujino);
+		return (-1);
+	}
+
+	if (DIP(ip, di_modrev) != fs->fs_mtime) {
+		printf("Journal timestamp does not match fs mount time\n");
+		return (-1);
+	}
+
+	return (0);
+}
+
+struct jblocks {
+	struct jextent *jb_extent;	/* Extent array. */
+	int		jb_avail;	/* Available extents. */
+	int		jb_used;	/* Last used extent. */
+	int		jb_head;	/* Allocator head. */
+	int		jb_off;		/* Allocator extent offset. */
+};
+struct jextent {
+	ufs2_daddr_t	je_daddr;	/* Disk block address. */
+	int		je_blocks;	/* Disk block count. */
+};
+
+struct jblocks *suj_jblocks;
+
+static struct jblocks *
+jblocks_create(void)
+{
+	struct jblocks *jblocks;
+	int size;
+
+	jblocks = errmalloc(sizeof(*jblocks));
+	jblocks->jb_avail = 10;
+	jblocks->jb_used = 0;
+	jblocks->jb_head = 0;
+	jblocks->jb_off = 0;
+	size = sizeof(struct jextent) * jblocks->jb_avail;
+	jblocks->jb_extent = errmalloc(size);
+	bzero(jblocks->jb_extent, size);
+
+	return (jblocks);
+}
+
+/*
+ * Return the next available disk block and the amount of contiguous
+ * free space it contains.
+ */
+static ufs2_daddr_t
+jblocks_next(struct jblocks *jblocks, int bytes, int *actual)
+{
+	struct jextent *jext;
+	ufs2_daddr_t daddr;
+	int freecnt;
+	int blocks;
+
+	blocks = bytes / DEV_BSIZE;
+	jext = &jblocks->jb_extent[jblocks->jb_head];
+	freecnt = jext->je_blocks - jblocks->jb_off;
+	if (freecnt == 0) {
+		jblocks->jb_off = 0;
+		if (++jblocks->jb_head > jblocks->jb_used)
+			return (0);
+		jext = &jblocks->jb_extent[jblocks->jb_head];
+		freecnt = jext->je_blocks;
+	}
+	if (freecnt > blocks)
+		freecnt = blocks;
+	*actual = freecnt * DEV_BSIZE;
+	daddr = jext->je_daddr + jblocks->jb_off;
+
+	return (daddr);
+}
+
+/*
+ * Advance the allocation head by a specified number of bytes, consuming
+ * one journal segment.
+ */
+static void
+jblocks_advance(struct jblocks *jblocks, int bytes)
+{
+
+	jblocks->jb_off += bytes / DEV_BSIZE;
+}
+
+static void
+jblocks_destroy(struct jblocks *jblocks)
+{
+
+	free(jblocks->jb_extent);
+	free(jblocks);
+}
+
+static void
+jblocks_add(struct jblocks *jblocks, ufs2_daddr_t daddr, int blocks)
+{
+	struct jextent *jext;
+	int size;
+
+	jext = &jblocks->jb_extent[jblocks->jb_used];
+	/* Adding the first block. */
+	if (jext->je_daddr == 0) {
+		jext->je_daddr = daddr;
+		jext->je_blocks = blocks;
+		return;
+	}
+	/* Extending the last extent. */
+	if (jext->je_daddr + jext->je_blocks == daddr) {
+		jext->je_blocks += blocks;
+		return;
+	}
+	/* Adding a new extent. */
+	if (++jblocks->jb_used == jblocks->jb_avail) {
+		jblocks->jb_avail *= 2;
+		size = sizeof(struct jextent) * jblocks->jb_avail;
+		jext = errmalloc(size);
+		bzero(jext, size);
+		bcopy(jblocks->jb_extent, jext,
+		    sizeof(struct jextent) * jblocks->jb_used);
+		free(jblocks->jb_extent);
+		jblocks->jb_extent = jext;
+	}
+	jext = &jblocks->jb_extent[jblocks->jb_used];
+	jext->je_daddr = daddr;
+	jext->je_blocks = blocks;
+
+	return;
+}
+
+/*
+ * Add a file block from the journal to the extent map.  We can't read
+ * each file block individually because the kernel treats it as a circular
+ * buffer and segments may span mutliple contiguous blocks.
+ */
+static void
+suj_add_block(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
+{
+
+	jblocks_add(suj_jblocks, fsbtodb(fs, blk), fsbtodb(fs, frags));
+}
+
+static void
+suj_read(void)
+{
+	uint8_t block[1 * 1024 * 1024];
+	struct suj_seg *seg;
+	struct jsegrec *recn;
+	struct jsegrec *rec;
+	ufs2_daddr_t blk;
+	int readsize;
+	int blocks;
+	int recsize;
+	int size;
+	int i;
+
+	/*
+	 * Read records until we exhaust the journal space.  If we find
+	 * an invalid record we start searching for a valid segment header
+	 * at the next block.  This is because we don't have a head/tail
+	 * pointer and must recover the information indirectly.  At the gap
+	 * between the head and tail we won't necessarily have a valid
+	 * segment.
+	 */
+restart:
+	for (;;) {
+		size = sizeof(block);
+		blk = jblocks_next(suj_jblocks, size, &readsize);
+		if (blk == 0)
+			return;
+		size = readsize;
+		/*
+		 * Read 1MB at a time and scan for records within this block.
+		 */
+		if (bread(disk, blk, &block, size) == -1)
+			err(1, "Error reading journal block %jd",
+			    (intmax_t)blk);
+		for (rec = (void *)block; size; size -= recsize,
+		    rec = (struct jsegrec *)((uintptr_t)rec + recsize)) {
+			recsize = DEV_BSIZE;
+			if (rec->jsr_time != fs->fs_mtime) {
+				if (debug)
+					printf("Rec time %jd != fs mtime %jd\n",
+					    rec->jsr_time, fs->fs_mtime);
+				jblocks_advance(suj_jblocks, recsize);
+				continue;
+			}
+			if (rec->jsr_cnt == 0) {
+				if (debug)
+					printf("Found illegal count %d\n",
+					    rec->jsr_cnt);
+				jblocks_advance(suj_jblocks, recsize);
+				continue;
+			}
+			blocks = rec->jsr_blocks;
+			recsize = blocks * DEV_BSIZE;
+			if (recsize > size) {
+				/*
+				 * We may just have run out of buffer, restart
+				 * the loop to re-read from this spot.
+				 */
+				if (size < fs->fs_bsize &&
+				    size != readsize &&
+				    recsize <= fs->fs_bsize)
+					goto restart;
+				if (debug)
+					printf("Found invalid segsize %d > %d\n",
+					    recsize, size);
+				recsize = DEV_BSIZE;
+				jblocks_advance(suj_jblocks, recsize);
+				continue;
+			}
+			/*
+			 * Verify that all blocks in the segment are present.
+			 */
+			for (i = 1; i < blocks; i++) {
+				recn = (void *)
+				    ((uintptr_t)rec) + i * DEV_BSIZE;
+				if (recn->jsr_seq == rec->jsr_seq &&
+				    recn->jsr_time == rec->jsr_time) 
+					continue;
+				if (debug)
+					printf("Incomplete record %jd (%d)\n",
+					    rec->jsr_seq, i);
+				recsize = i * DEV_BSIZE;
+				jblocks_advance(suj_jblocks, recsize);
+				goto restart;
+			}
+			seg = errmalloc(sizeof(*seg));
+			seg->ss_blk = errmalloc(recsize);
+			seg->ss_rec = *rec;
+			bcopy((void *)rec, seg->ss_blk, recsize);
+			if (rec->jsr_oldest > oldseq)
+				oldseq = rec->jsr_oldest;
+			TAILQ_INSERT_TAIL(&allsegs, seg, ss_next);
+			jblocks_advance(suj_jblocks, recsize);
+		}
+	}
+}
+
+/*
+ * Search a directory block for the SUJ_FILE.
+ */
+static void
+suj_find(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
+{
+	char block[MAXBSIZE];
+	struct direct *dp;
+	int bytes;
+	int off;
+
+	if (sujino)
+		return;
+	bytes = lfragtosize(fs, frags);
+	if (bread(disk, fsbtodb(fs, blk), block, bytes) <= 0)
+		err(1, "Failed to read ROOTINO directory block %jd", blk);
+	for (off = 0; off < bytes; off += dp->d_reclen) {
+		dp = (struct direct *)&block[off];
+		if (dp->d_reclen == 0)
+			break;
+		if (dp->d_ino == 0)
+			continue;
+		if (dp->d_namlen != strlen(SUJ_FILE))
+			continue;
+		if (bcmp(dp->d_name, SUJ_FILE, dp->d_namlen) != 0)
+			continue;
+		sujino = dp->d_ino;
+		return;
+	}
+}
+
+/*
+ * Orchestrate the verification of a filesystem via the softupdates journal.
+ */
+int
+suj_check(const char *filesys)
+{
+	union dinode *jip;
+	union dinode *ip;
+	uint64_t blocks;
+
+	opendisk(filesys);
+	TAILQ_INIT(&allsegs);
+	/*
+	 * Find the journal inode.
+	 */
+	ip = ino_read(ROOTINO);
+	sujino = 0;
+	ino_visit(ip, ROOTINO, suj_find, 0);
+	if (sujino == 0)
+		errx(1, "Journal inode removed.  Use tunefs to re-create.");
+	/*
+	 * Fetch the journal inode and verify it.
+	 */
+	jip = ino_read(sujino);
+	printf("** SU+J Recovering %s\n", filesys);
+	if (suj_verifyino(jip) != 0)
+		return (-1);
+	/*
+	 * Build a list of journal blocks in jblocks before parsing the
+	 * available journal blocks in with suj_read().
+	 */
+	printf("** Reading %jd byte journal from inode %d.\n",
+	    DIP(jip, di_size), sujino);
+	suj_jblocks = jblocks_create();
+	blocks = ino_visit(jip, sujino, suj_add_block, 0);
+	if (blocks != numfrags(fs, DIP(jip, di_size)))
+		errx(1, "Sparse journal inode %d.\n", sujino);
+	suj_read();
+	jblocks_destroy(suj_jblocks);
+	suj_jblocks = NULL;
+	if (preen || reply("RECOVER")) {
+		printf("** Building recovery table.\n");
+		suj_prune();
+		suj_build();
+		cg_apply(cg_build);
+		printf("** Resolving unreferenced inode list.\n");
+		ino_unlinked();
+		printf("** Processing journal entries.\n");
+		cg_apply(cg_trunc);
+		cg_apply(cg_check_blk);
+		cg_apply(cg_check_ino);
+	}
+	if (preen == 0 && reply("WRITE CHANGES") == 0)
+		return (0);
+	/*
+	 * To remain idempotent with partial truncations the free bitmaps
+	 * must be written followed by indirect blocks and lastly inode
+	 * blocks.  This preserves access to the modified pointers until
+	 * they are freed.
+	 */
+	cg_apply(cg_write);
+	dblk_write();
+	cg_apply(cg_write_inos);
+	/* Write back superblock. */
+	closedisk(filesys);
+	printf("** %jd journal records in %jd bytes for %.2f%% utilization\n",
+	    jrecs, jbytes, ((float)jrecs / (float)(jbytes / JREC_SIZE)) * 100);
+	printf("** Freed %jd inodes (%jd dirs) %jd blocks, and %jd frags.\n",
+	    freeinos, freedir, freeblocks, freefrags);
+
+	return (0);
+}
+/*-
+ * Copyright (c) 2009 Jeffrey W. Roberson <jeff@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <sys/param.h>
+#include <sys/disklabel.h>
+#include <sys/mount.h>
+#include <sys/stat.h>
+
+#include <ufs/ufs/ufsmount.h>
+#include <ufs/ufs/dinode.h>
+#include <ufs/ufs/dir.h>
+#include <ufs/ffs/fs.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <libufs.h>
+#include <strings.h>
+#include <err.h>
+#include <assert.h>
+
+#include "fsck.h"
+
+static void	ino_decr(ino_t);
+
+#define	SUJ_HASHSIZE	128
+#define	SUJ_HASHMASK	(SUJ_HASHSIZE - 1)
+#define	SUJ_HASH(x)	((x * 2654435761) & SUJ_HASHMASK)
+
+struct suj_seg {
+	TAILQ_ENTRY(suj_seg) ss_next;
+	struct jsegrec	ss_rec;
+	uint8_t		*ss_blk;
+};
+
+struct suj_rec {
+	TAILQ_ENTRY(suj_rec) sr_next;
+	union jrec	*sr_rec;
+};
+TAILQ_HEAD(srechd, suj_rec);
+
+struct suj_ino {
+	LIST_ENTRY(suj_ino)	si_next;
+	struct srechd		si_recs;
+	struct srechd		si_movs;
+	ino_t			si_ino;
+	int			si_nlinkadj;
+	int			si_skipparent;
+	int			si_linkadj;
+	int			si_hasrecs;
+	int			si_blkadj;
+};
+LIST_HEAD(inohd, suj_ino);
+
+struct suj_blk {
+	LIST_ENTRY(suj_blk)	sb_next;
+	struct srechd		sb_recs;
+	ufs2_daddr_t		sb_blk;
+};
+LIST_HEAD(blkhd, suj_blk);
+
+struct data_blk {
+	LIST_ENTRY(data_blk)	db_next;
+	uint8_t			*db_buf;
+	ufs2_daddr_t		db_blk;
+	int			db_size;
+};
+
+struct ino_blk {
+	LIST_ENTRY(ino_blk)	ib_next;
+	uint8_t			*ib_buf;
+	int			ib_dirty;
+	ufs2_daddr_t		ib_blk;
+};
+LIST_HEAD(iblkhd, ino_blk);
+
+struct suj_cg {
+	LIST_ENTRY(suj_cg)	sc_next;
+	struct blkhd		sc_blkhash[SUJ_HASHSIZE];
+	struct inohd		sc_inohash[SUJ_HASHSIZE];
+	struct iblkhd		sc_iblkhash[SUJ_HASHSIZE];
+	struct ino_blk		*sc_lastiblk;
+	uint8_t			*sc_cgbuf;
+	struct cg		*sc_cgp;
+	int			sc_dirty;
+	int			sc_cgx;
+};
+
+LIST_HEAD(cghd, suj_cg) cghash[SUJ_HASHSIZE];
+LIST_HEAD(dblkhd, data_blk) dbhash[SUJ_HASHSIZE];
+
+TAILQ_HEAD(seghd, suj_seg) allsegs;
+uint64_t oldseq;
+static struct uufsd *disk = NULL;
+static struct fs *fs = NULL;
+
+/*
+ * Summary statistics.
+ */
+uint64_t freefrags;
+uint64_t freeblocks;
+uint64_t freeinos;
+uint64_t freedir;
+uint64_t jbytes;
+uint64_t jrecs;
+
+typedef void (*ino_visitor)(ino_t, ufs_lbn_t, ufs2_daddr_t, int);
+
+static void *
+errmalloc(size_t n)
+{
+	void *a;
+
+	a = malloc(n);
+	if (a == NULL)
+		errx(1, "malloc(%zu)", n);
+	return (a);
+}
+
+/*
+ * Open the given provider, load superblock.
+ */
+static void
+opendisk(const char *devnam)
+{
+	if (disk != NULL)
+		return;
+	disk = malloc(sizeof(*disk));
+	if (disk == NULL)
+		errx(1, "malloc(%zu)", sizeof(*disk));
+	if (ufs_disk_fillout(disk, devnam) == -1) {
+		err(1, "ufs_disk_fillout(%s) failed: %s", devnam,
+		    disk->d_error);
+	}
+	fs = &disk->d_fs;
+	/*
+	 * Setup a few things so reply() can work.
+	 */
+	bcopy(fs, &sblock, sizeof(sblock));
+	fsreadfd = disk->d_fd;
+	fswritefd = disk->d_fd;
+}
+
+/*
+ * Mark file system as clean, write the super-block back, close the disk.
+ */
+static void
+closedisk(const char *devnam)
+{
+	struct csum *cgsum;
+	int i;
+
+	/*
+	 * Recompute the fs summary info from correct cs summaries.
+	 */
+	bzero(&fs->fs_cstotal, sizeof(struct csum_total));
+	for (i = 0; i < fs->fs_ncg; i++) {
+		cgsum = &fs->fs_cs(fs, i);
+		fs->fs_cstotal.cs_nffree += cgsum->cs_nffree;
+		fs->fs_cstotal.cs_nbfree += cgsum->cs_nbfree;
+		fs->fs_cstotal.cs_nifree += cgsum->cs_nifree;
+		fs->fs_cstotal.cs_ndir += cgsum->cs_ndir;
+	}
+	/* XXX Don't set clean for now, we don't trust the journal. */
+	/* fs->fs_clean = 1; */
+	fs->fs_time = time(NULL);
+	fs->fs_mtime = time(NULL);
+	if (sbwrite(disk, 0) == -1)
+		err(1, "sbwrite(%s)", devnam);
+	if (ufs_disk_close(disk) == -1)
+		err(1, "ufs_disk_close(%s)", devnam);
+	free(disk);
+	disk = NULL;
+	fs = NULL;
+	fsreadfd = -1;
+	fswritefd = -1;
+}
+
+/*
+ * Lookup a cg by number in the hash so we can keep track of which cgs
+ * need stats rebuilt.
+ */
+static struct suj_cg *
+cg_lookup(int cgx)
+{
+	struct cghd *hd;
+	struct suj_cg *sc;
+
+	if (cgx < 0 || cgx >= fs->fs_ncg) {
+		abort();
+		errx(1, "Bad cg number %d", cgx);
+	}
+	hd = &cghash[SUJ_HASH(cgx)];
+	LIST_FOREACH(sc, hd, sc_next)
+		if (sc->sc_cgx == cgx)
+			return (sc);
+	sc = errmalloc(sizeof(*sc));
+	bzero(sc, sizeof(*sc));
+	sc->sc_cgbuf = errmalloc(fs->fs_bsize);
+	sc->sc_cgp = (struct cg *)sc->sc_cgbuf;
+	sc->sc_cgx = cgx;
+	LIST_INSERT_HEAD(hd, sc, sc_next);
+	if (bread(disk, fsbtodb(fs, cgtod(fs, sc->sc_cgx)), sc->sc_cgbuf,
+	    fs->fs_bsize) == -1)
+		err(1, "Unable to read cylinder group %d", sc->sc_cgx);
+
+	return (sc);
+}
+
+/*
+ * Lookup an inode number in the hash and allocate a suj_ino if it does
+ * not exist.
+ */
+static struct suj_ino *
+ino_lookup(ino_t ino, int creat)
+{
+	struct suj_ino *sino;
+	struct inohd *hd;
+	struct suj_cg *sc;
+
+	sc = cg_lookup(ino_to_cg(fs, ino));
+	hd = &sc->sc_inohash[SUJ_HASH(ino)];
+	LIST_FOREACH(sino, hd, si_next)
+		if (sino->si_ino == ino)
+			return (sino);
+	if (creat == 0)
+		return (NULL);
+	sino = errmalloc(sizeof(*sino));
+	bzero(sino, sizeof(*sino));
+	sino->si_ino = ino;
+	sino->si_nlinkadj = 0;
+	TAILQ_INIT(&sino->si_recs);
+	TAILQ_INIT(&sino->si_movs);
+	LIST_INSERT_HEAD(hd, sino, si_next);
+
+	return (sino);
+}
+
+/*
+ * Lookup a block number in the hash and allocate a suj_blk if it does
+ * not exist.
+ */
+static struct suj_blk *
+blk_lookup(ufs2_daddr_t blk, int creat)
+{
+	struct suj_blk *sblk;
+	struct suj_cg *sc;
+	struct blkhd *hd;
+
+	sc = cg_lookup(dtog(fs, blk));
+	hd = &sc->sc_blkhash[SUJ_HASH(blk)];
+	LIST_FOREACH(sblk, hd, sb_next)
+		if (sblk->sb_blk == blk)
+			return (sblk);
+	if (creat == 0)
+		return (NULL);
+	sblk = errmalloc(sizeof(*sblk));
+	bzero(sblk, sizeof(*sblk));
+	sblk->sb_blk = blk;
+	TAILQ_INIT(&sblk->sb_recs);
+	LIST_INSERT_HEAD(hd, sblk, sb_next);
+
+	return (sblk);
+}
+
+static uint8_t *
+dblk_read(ufs2_daddr_t blk, int size)
+{
+	struct data_blk *dblk;
+	struct dblkhd *hd;
+
+	hd = &dbhash[SUJ_HASH(blk)];
+	LIST_FOREACH(dblk, hd, db_next)
+		if (dblk->db_blk == blk)
+			goto found;
+	/*
+	 * The inode block wasn't located, allocate a new one.
+	 */
+	dblk = errmalloc(sizeof(*dblk));
+	bzero(dblk, sizeof(*dblk));
+	LIST_INSERT_HEAD(hd, dblk, db_next);
+	dblk->db_blk = blk;
+found:
+	/*
+	 * I doubt size mismatches can happen in practice but it is trivial
+	 * to handle.
+	 */
+	if (size != dblk->db_size) {
+		if (dblk->db_buf)
+			free(dblk->db_buf);
+		dblk->db_buf = errmalloc(size);
+		dblk->db_size = size;
+		if (bread(disk, fsbtodb(fs, blk), dblk->db_buf, size) == -1)
+			err(1, "Failed to read data block %jd", blk);
+	}
+	return (dblk->db_buf);
+}
+
+static union dinode *
+ino_read(ino_t ino)
+{
+	struct ino_blk *iblk;
+	struct iblkhd *hd;
+	struct suj_cg *sc;
+	ufs2_daddr_t blk;
+	int off;
+
+	blk = ino_to_fsba(fs, ino);
+	sc = cg_lookup(ino_to_cg(fs, ino));
+	hd = &sc->sc_iblkhash[SUJ_HASH(blk)];
+	LIST_FOREACH(iblk, hd, ib_next)
+		if (iblk->ib_blk == blk)
+			goto found;
+	/*
+	 * The inode block wasn't located, allocate a new one.
+	 */
+	iblk = errmalloc(sizeof(*iblk));
+	bzero(iblk, sizeof(*iblk));
+	iblk->ib_buf = errmalloc(fs->fs_bsize);
+	iblk->ib_blk = blk;
+	LIST_INSERT_HEAD(hd, iblk, ib_next);
+	if (bread(disk, fsbtodb(fs, blk), iblk->ib_buf, fs->fs_bsize) == -1)
+		err(1, "Failed to read inode block %jd", blk);
+found:
+	sc->sc_lastiblk = iblk;
+	off = ino_to_fsbo(fs, ino);
+	if (fs->fs_magic == FS_UFS1_MAGIC)
+		return (union dinode *)&((struct ufs1_dinode *)iblk->ib_buf)[off];
+	else
+		return (union dinode *)&((struct ufs2_dinode *)iblk->ib_buf)[off];
+}
+
+static void
+ino_dirty(ino_t ino)
+{
+	struct ino_blk *iblk;
+	struct iblkhd *hd;
+	struct suj_cg *sc;
+	ufs2_daddr_t blk;
+
+	blk = ino_to_fsba(fs, ino);
+	sc = cg_lookup(ino_to_cg(fs, ino));
+	iblk = sc->sc_lastiblk;
+	if (iblk && iblk->ib_blk == blk) {
+		iblk->ib_dirty = 1;
+		return;
+	}
+	hd = &sc->sc_iblkhash[SUJ_HASH(blk)];
+	LIST_FOREACH(iblk, hd, ib_next) {
+		if (iblk->ib_blk == blk) {
+			iblk->ib_dirty = 1;
+			return;
+		}
+	}
+	ino_read(ino);
+	ino_dirty(ino);
+}
+
+static void
+iblk_write(struct ino_blk *iblk)
+{
+
+	if (iblk->ib_dirty == 0)
+		return;
+	if (bwrite(disk, fsbtodb(fs, iblk->ib_blk), iblk->ib_buf,
+	    fs->fs_bsize) == -1)
+		err(1, "Failed to write inode block %jd", iblk->ib_blk);
+}
+
+/*
+ * Return 1 if the inode was free and 0 if it is allocated.
+ */
+static int
+ino_isfree(ino_t ino)
+{
+	struct suj_cg *sc;
+	uint8_t *inosused;
+	struct cg *cgp;
+	int cg;
+
+	cg = ino_to_cg(fs, ino);
+	ino = ino % fs->fs_ipg;
+	sc = cg_lookup(cg);
+	cgp = sc->sc_cgp;
+	inosused = cg_inosused(cgp);
+	return isclr(inosused, ino);
+}
+
+static int
+blk_overlaps(struct jblkrec *brec, ufs2_daddr_t start, int frags)
+{
+	ufs2_daddr_t bstart;
+	ufs2_daddr_t bend;
+	ufs2_daddr_t end;
+
+	end = start + frags;
+	bstart = brec->jb_blkno + brec->jb_oldfrags;
+	bend = bstart + brec->jb_frags;
+	if (start < bend && end > bstart)
+		return (1);
+	return (0);
+}
+
+static int
+blk_equals(struct jblkrec *brec, ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t start,
+    int frags)
+{
+
+	if (brec->jb_ino != ino || brec->jb_lbn != lbn)
+		return (0);
+	if (brec->jb_blkno + brec->jb_oldfrags != start)
+		return (0);
+	if (brec->jb_frags != frags)
+		return (0);
+	return (1);
+}
+
+static void
+blk_setmask(struct jblkrec *brec, int *mask)
+{
+	int i;
+
+	for (i = brec->jb_oldfrags; i < brec->jb_oldfrags + brec->jb_frags; i++)
+		*mask |= 1 << i;
+}
+
+/*
+ * Determine whether a given block has been reallocated to a new location.
+ * Returns a mask of overlapping bits if any frags have been reused or
+ * zero if the block has not been re-used and the contents can be trusted.
+ * 
+ * This is used to ensure that an orphaned pointer due to truncate is safe
+ * to be freed.  The mask value can be used to free partial blocks.
+ */
+static int
+blk_isfree(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn, int frags)
+{
+	struct suj_blk *sblk;
+	struct suj_rec *srec;
+	struct jblkrec *brec;
+	int mask;
+	int off;
+
+	/*
+	 * To be certain we're not freeing a reallocated block we lookup
+	 * this block in the blk hash and see if there is an allocation
+	 * journal record that overlaps with any fragments in the block
+	 * we're concerned with.  If any fragments have ben reallocated
+	 * the block has already been freed and re-used for another purpose.
+	 */
+	mask = 0;
+	sblk = blk_lookup(blknum(fs, blk), 0);
+	if (sblk == NULL)
+		return (0);
+	off = blk - sblk->sb_blk;
+	TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) {
+		brec = (struct jblkrec *)srec->sr_rec;
+		/*
+		 * If the block overlaps but does not match
+		 * exactly it's a new allocation.  If it matches
+		 * exactly this record refers to the current
+		 * location.
+		 */ 
+		if (blk_overlaps(brec, blk, frags) == 0)
+			continue;
+		if (blk_equals(brec, ino, lbn, blk, frags) == 1)
+			mask = 0;
+		else
+			blk_setmask(brec, &mask);
+	}
+	if (debug)
+		printf("blk_isfree: blk %jd sblk %jd off %d mask 0x%X\n",
+		    blk, sblk->sb_blk, off, mask);
+	return (mask >> off);
+}
+
+/*
+ * Determine whether it is safe to follow an indirect.  It is not safe
+ * if any part of the indirect has been reallocated or the last journal
+ * entry was an allocation.  Just allocated indirects may not have valid
+ * pointers yet and all of their children will have their own records.
+ * 
+ * Returns 1 if it's safe to follow the indirect and 0 otherwise.
+ */
+static int
+blk_isindir(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn)
+{
+	struct suj_blk *sblk;
+	struct jblkrec *brec;
+
+	sblk = blk_lookup(blk, 0);
+	if (sblk == NULL)
+		return (1);
+	if (TAILQ_EMPTY(&sblk->sb_recs))
+		return (1);
+	brec = (struct jblkrec *)TAILQ_LAST(&sblk->sb_recs, srechd)->sr_rec;
+	if (blk_equals(brec, ino, lbn, blk, fs->fs_frag))
+		if (brec->jb_op == JOP_FREEBLK)
+			return (1);
+	return (0);
+}
+
+/*
+ * Clear an inode from the cg bitmap.  If the inode was already clear return
+ * 0 so the caller knows it does not have to check the inode contents.
+ */
+static int
+ino_free(ino_t ino, int mode)
+{
+	struct suj_cg *sc;
+	uint8_t *inosused;
+	struct cg *cgp;
+	int cg;
+
+	cg = ino_to_cg(fs, ino);
+	ino = ino % fs->fs_ipg;
+	sc = cg_lookup(cg);
+	cgp = sc->sc_cgp;
+	inosused = cg_inosused(cgp);
+	/*
+	 * The bitmap may never have made it to the disk so we have to
+	 * conditionally clear.  We can avoid writing the cg in this case.
+	 */
+	if (isclr(inosused, ino))
+		return (0);
+	freeinos++;
+	clrbit(inosused, ino);
+	if (ino < cgp->cg_irotor)
+		cgp->cg_irotor = ino;
+	cgp->cg_cs.cs_nifree++;
+	if ((mode & IFMT) == IFDIR) {
+		freedir++;
+		cgp->cg_cs.cs_ndir--;
+	}
+	sc->sc_dirty = 1;
+
+	return (1);
+}
+
+/*
+ * Free 'frags' frags starting at filesystem block 'bno' skipping any frags
+ * set in the mask.
+ */
+static void
+blk_free(ufs2_daddr_t bno, int mask, int frags)
+{
+	ufs1_daddr_t fragno, cgbno;
+	struct suj_cg *sc;
+	struct cg *cgp;
+	int i, cg;
+	uint8_t *blksfree;
+
+	if (debug)
+		printf("Freeing %d frags at blk %jd\n", frags, bno);
+	cg = dtog(fs, bno);
+	sc = cg_lookup(cg);
+	cgp = sc->sc_cgp;
+	cgbno = dtogd(fs, bno);
+	blksfree = cg_blksfree(cgp);
+
+	/*
+	 * If it's not allocated we only wrote the journal entry
+	 * and never the bitmaps.  Here we unconditionally clear and
+	 * resolve the cg summary later.
+	 */
+	if (frags == fs->fs_frag && mask == 0) {
+		fragno = fragstoblks(fs, cgbno);
+		ffs_setblock(fs, blksfree, fragno);
+		freeblocks++;
+	} else {
+		/*
+		 * deallocate the fragment
+		 */
+		for (i = 0; i < frags; i++)
+			if ((mask & (1 << i)) == 0 && isclr(blksfree, cgbno +i)) {
+				freefrags++;
+				setbit(blksfree, cgbno + i);
+			}
+	}
+	sc->sc_dirty = 1;
+}
+
+/*
+ * Fetch an indirect block to find the block at a given lbn.  The lbn
+ * may be negative to fetch a specific indirect block pointer or positive
+ * to fetch a specific block.
+ */
+static ufs2_daddr_t
+indir_blkatoff(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t cur, ufs_lbn_t lbn, int level)
+{
+	ufs2_daddr_t *bap2;
+	ufs2_daddr_t *bap1;
+	ufs_lbn_t lbnadd;
+	ufs_lbn_t base;
+	int i;
+
+	if (blk == 0)
+		return (0);
+	if (cur == lbn)
+		return (blk);
+	if (level == 0 && lbn < 0) {
+		abort();
+		errx(1, "Invalid lbn %jd", lbn);
+	}
+	bap2 = (void *)dblk_read(blk, fs->fs_bsize);
+	bap1 = (void *)bap2;
+	lbnadd = 1;
+	base = -(cur + level);
+	for (i = level; i > 0; i--)
+		lbnadd *= NINDIR(fs);
+	if (lbn > 0) 
+		i = (lbn - base) / lbnadd;
+	else
+		i = (-lbn - base) / lbnadd;
+	if (i < 0 || i >= NINDIR(fs)) {
+		abort();
+		errx(1, "Invalid indirect index %d produced by lbn %jd",
+		    i, lbn);
+	}
+	if (level == 0)
+		cur = base + (i * lbnadd);
+	else
+		cur = -(base + (i * lbnadd)) - (level - 1);
+	if (fs->fs_magic == FS_UFS1_MAGIC)
+		blk = bap1[i];
+	else
+		blk = bap2[i];
+	if (cur == lbn)
+		return (blk);
+	if (level == 0) {
+		abort();
+		errx(1, "Invalid lbn %jd at level 0", lbn);
+	}
+	return indir_blkatoff(blk, ino, cur, lbn, level - 1);
+}
+
+/*
+ * Finds the disk block address at the specified lbn within the inode
+ * specified by ip.  This follows the whole tree and honors di_size and
+ * di_extsize so it is a true test of reachability.  The lbn may be
+ * negative if an extattr or indirect block is requested.
+ */
+static ufs2_daddr_t
+ino_blkatoff(union dinode *ip, ino_t ino, ufs_lbn_t lbn, int *frags)
+{
+	ufs_lbn_t tmpval;
+	ufs_lbn_t cur;
+	ufs_lbn_t next;
+	int i;
+
+	/*
+	 * Handle extattr blocks first.
+	 */
+	if (lbn < 0 && lbn >= -NXADDR) {
+		lbn = -1 - lbn;
+		if (lbn > lblkno(fs, ip->dp2.di_extsize - 1))
+			return (0);
+		*frags = numfrags(fs, sblksize(fs, ip->dp2.di_extsize, lbn));
+		return (ip->dp2.di_extb[lbn]);
+	}
+	/*
+	 * And now direct and indirect.  Verify that the lbn does not
+	 * exceed the size required to store the file by asking for
+	 * the lbn of the last byte.  These blocks should be 0 anyway
+	 * so this simply saves the traversal.
+	 */
+	if (lbn > 0 && lbn > lblkno(fs, DIP(ip, di_size) - 1))
+		return (0);
+	if (lbn < 0 && -lbn > lblkno(fs, DIP(ip, di_size) - 1))
+		return (0);
+	if (lbn >= 0 && lbn < NDADDR) {
+		*frags = numfrags(fs, sblksize(fs, DIP(ip, di_size), lbn));
+		return (DIP(ip, di_db[lbn]));
+	}
+	*frags = fs->fs_frag;
+
+	for (i = 0, tmpval = NINDIR(fs), cur = NDADDR; i < NIADDR; i++,
+	    tmpval *= NINDIR(fs), cur = next) {
+		next = cur + tmpval;
+		if (lbn == -cur)
+			return (DIP(ip, di_ib[i]));
+		/*
+		 * Determine whether the lbn in question is within this tree.
+		 */
+		if (lbn < 0 && -lbn >= next)
+			continue;
+		if (lbn > 0 && lbn >= next)
+			continue;
+
+		return indir_blkatoff(DIP(ip, di_ib[i]), ino, -cur - i, lbn, i);
+	}
+	errx(1, "lbn %jd not in ino", lbn);
+}
+
+/*
+ * Determine whether a block exists at a particular lbn in an inode.
+ * Returns 1 if found, 0 if not.  lbn may be negative for indirects
+ * or ext blocks.
+ */
+static int
+blk_isat(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int *frags)
+{
+	union dinode *ip;
+	ufs2_daddr_t nblk;
+
+	ip = ino_read(ino);
+
+	if (DIP(ip, di_nlink) == 0 || DIP(ip, di_mode) == 0)
+		return (0);
+	nblk = ino_blkatoff(ip, ino, lbn, frags);
+
+	return (nblk == blk);
+}
+
+/*
+ * Determines whether a pointer to an inode exists within a directory
+ * at a specified offset.  Returns the mode of the found entry.
+ */
+static int
+ino_isat(ino_t parent, off_t diroff, ino_t child, int *mode, int *isdot)
+{
+	union dinode *dip;
+	struct direct *dp;
+	ufs2_daddr_t blk;
+	uint8_t *block;
+	ufs_lbn_t lbn;
+	int blksize;
+	int frags;
+	int dpoff;
+	int doff;
+
+	*isdot = 0;
+	dip = ino_read(parent);
+	*mode = DIP(dip, di_mode);
+	if ((*mode & IFMT) != IFDIR) {
+		if (debug) {
+			/* This can happen if the parent inode was reallocated. */
+			if (*mode != 0)
+				printf("Directory %d has bad mode %o\n",
+				    parent, *mode);
+			else
+				printf("Directory %d zero inode\n", parent);
+		}
+		return (0);
+	}
+	lbn = lblkno(fs, diroff);
+	doff = blkoff(fs, diroff);
+	blksize = sblksize(fs, DIP(dip, di_size), lbn);
+	if (diroff + DIRECTSIZ(1) > DIP(dip, di_size) || doff >= blksize) {
+		if (debug)
+			printf("ino %d absent from %d due to offset %jd"
+			    " exceeding size %jd\n",
+			    child, parent, diroff, DIP(dip, di_size));
+		return (0);
+	}
+	blk = ino_blkatoff(dip, parent, lbn, &frags);
+	if (blk <= 0) {
+		if (debug)
+			printf("Sparse directory %d", parent);
+		return (0);
+	}
+	block = dblk_read(blk, blksize);
+	/*
+	 * Walk through the records from the start of the block to be
+	 * certain we hit a valid record and not some junk in the middle
+	 * of a file name.  Stop when we reach or pass the expected offset.
+	 */
+	dpoff = 0;
+	do {
+		dp = (struct direct *)&block[dpoff];
+		if (dpoff == doff)
+			break;
+		if (dp->d_reclen == 0)
+			break;
+		dpoff += dp->d_reclen;
+	} while (dpoff <= doff);
+	if (dpoff > fs->fs_bsize)
+		errx(1, "Corrupt directory block in dir inode %d", parent);
+	/* Not found. */
+	if (dpoff != doff) {
+		if (debug)
+			printf("ino %d not found in %d, lbn %jd, dpoff %d\n",
+			    child, parent, lbn, dpoff);
+		return (0);
+	}
+	/*
+	 * We found the item in question.  Record the mode and whether it's
+	 * a . or .. link for the caller.
+	 */
+	if (dp->d_ino == child) {
+		if (child == parent)
+			*isdot = 1;
+		else if (dp->d_namlen == 2 &&
+		    dp->d_name[0] == '.' && dp->d_name[1] == '.')
+			*isdot = 1;
+		*mode = DTTOIF(dp->d_type);
+		return (1);
+	}
+	if (debug)
+		printf("ino %d doesn't match dirent ino %d in parent %d\n",
+		    child, dp->d_ino, parent);
+	return (0);
+}
+
+#define	VISIT_INDIR	0x0001
+#define	VISIT_EXT	0x0002
+
+/*
+ * Read an indirect level which may or may not be linked into an inode.
+ */
+static void
+indir_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, uint64_t *frags,
+    ino_visitor visitor, int flags)
+{
+	ufs2_daddr_t *bap2;
+	ufs1_daddr_t *bap1;
+	ufs_lbn_t lbnadd;
+	ufs2_daddr_t nblk;
+	ufs_lbn_t nlbn;
+	int level;
+	int i;
+
+	/*
+	 * Don't visit indirect blocks with contents we can't trust.  This
+	 * should only happen when indir_visit() is called to complete a
+	 * truncate that never finished and not when a pointer is found via
+	 * an inode.
+	 */
+	if (blk == 0)
+		return;
+	if (blk_isindir(blk, ino, lbn) == 0) {
+		if (debug)
+			printf("blk %jd ino %d lbn %jd is not indir.\n",
+			    blk, ino, lbn);
+		goto out;
+	}
+	level = lbn_level(lbn);
+	if (level == -1) {
+		abort();
+		errx(1, "Invalid level for lbn %jd", lbn);
+	}
+	lbnadd = 1;
+	for (i = level; i > 0; i--)
+		lbnadd *= NINDIR(fs);
+	bap1 = (void *)dblk_read(blk, fs->fs_bsize);
+	bap2 = (void *)bap1;
+	for (i = 0; i < NINDIR(fs); i++) {
+		if (fs->fs_magic == FS_UFS1_MAGIC)
+			nblk = *bap1++;
+		else
+			nblk = *bap2++;
+		if (nblk == 0)
+			continue;
+		if (level == 0) {
+			nlbn = -lbn + i * lbnadd;
+			(*frags) += fs->fs_frag;
+			visitor(ino, nlbn, nblk, fs->fs_frag);
+		} else {
+			nlbn = (lbn + 1) - (i * lbnadd);
+			indir_visit(ino, nlbn, nblk, frags, visitor, flags);
+		}
+	}
+out:
+	if (flags & VISIT_INDIR) {
+		(*frags) += fs->fs_frag;
+		visitor(ino, lbn, blk, fs->fs_frag);
+	}
+}
+
+/*
+ * Visit each block in an inode as specified by 'flags' and call a
+ * callback function.  The callback may inspect or free blocks.  The
+ * count of frags found according to the size in the file is returned.
+ * This is not valid for sparse files but may be used to determine
+ * the correct di_blocks for a file.
+ */
+static uint64_t
+ino_visit(union dinode *ip, ino_t ino, ino_visitor visitor, int flags)
+{
+	ufs_lbn_t tmpval;
+	ufs_lbn_t lbn;
+	uint64_t size;
+	uint64_t fragcnt;
+	int mode;
+	int frags;
+	int i;
+
+	size = DIP(ip, di_size);
+	mode = DIP(ip, di_mode) & IFMT;
+	fragcnt = 0;
+	if ((flags & VISIT_EXT) &&
+	    fs->fs_magic == FS_UFS2_MAGIC && ip->dp2.di_extsize) {
+		for (i = 0; i < NXADDR; i++) {
+			if (ip->dp2.di_extb[i] == 0)
+				continue;
+			frags = sblksize(fs, ip->dp2.di_extsize, i);
+			frags = numfrags(fs, frags);
+			fragcnt += frags;
+			visitor(ino, -1 - i, ip->dp2.di_extb[i], frags);
+		}
+	}
+	/* Skip datablocks for short links and devices. */
+	if (mode == IFBLK || mode == IFCHR ||
+	    (mode == IFLNK && size < fs->fs_maxsymlinklen))
+		return (fragcnt);
+	for (i = 0; i < NDADDR; i++) {
+		if (DIP(ip, di_db[i]) == 0)
+			continue;
+		frags = sblksize(fs, size, i);
+		frags = numfrags(fs, frags);
+		fragcnt += frags;
+		visitor(ino, i, DIP(ip, di_db[i]), frags);
+	}
+	for (i = 0, tmpval = NINDIR(fs), lbn = NDADDR; i < NIADDR; i++,
+	    tmpval *= NINDIR(fs), lbn += tmpval) {
+		if (DIP(ip, di_ib[i]) == 0)
+			continue;
+		indir_visit(ino, -lbn - i, DIP(ip, di_ib[i]), &fragcnt, visitor,
+		    flags);
+	}
+	return (fragcnt);
+}
+
+/*
+ * Null visitor function used when we just want to count blocks.
+ */
+static void
+null_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
+{
+}
+
+/*
+ * Recalculate di_blocks when we discover that a block allocation or
+ * free was not successfully completed.  The kernel does not roll this back
+ * because it would be too expensive to compute which indirects were
+ * reachable at the time the inode was written.
+ */
+static void
+ino_adjblks(ino_t ino)
+{
+	struct suj_ino *sino;
+	union dinode *ip;
+	uint64_t blocks;
+	uint64_t frags;
+
+	sino = ino_lookup(ino, 1);
+	if (sino->si_blkadj)
+		return;
+	sino->si_blkadj = 1;
+	ip = ino_read(ino);
+	/* No need to adjust zero'd inodes. */
+	if (DIP(ip, di_mode) == 0)
+		return;
+	frags = ino_visit(ip, ino, null_visit, VISIT_INDIR | VISIT_EXT);
+	blocks = fsbtodb(fs, frags);
+	if (blocks == DIP(ip, di_blocks))
+		return;
+	if (debug)
+		printf("ino %d adjusting block count from %jd to %jd\n",
+		    ino, DIP(ip, di_blocks), blocks);
+	DIP_SET(ip, di_blocks, blocks);
+	ino_dirty(ino);
+}
+
+static void
+blk_free_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
+{
+	int mask;
+
+	mask = blk_isfree(blk, ino, lbn, frags);
+	if (debug)
+		printf("blk %jd freemask 0x%X\n", blk, mask);
+	blk_free(blk, mask, frags);
+}
+
+/*
+ * Free a block or tree of blocks that was previously rooted in ino at
+ * the given lbn.  If the lbn is an indirect all children are freed
+ * recursively.
+ */
+static void
+blk_free_lbn(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn, int frags, int follow)
+{
+	uint64_t resid;
+	int mask;
+
+	mask = blk_isfree(blk, ino, lbn, frags);
+	if (debug)
+		printf("blk %jd freemask 0x%X\n", blk, mask);
+	resid = 0;
+	if (lbn <= -NDADDR && follow && mask == 0)
+		indir_visit(ino, lbn, blk, &resid, blk_free_visit, VISIT_INDIR);
+	else
+		blk_free(blk, mask, frags);
+}
+
+static void
+ino_free_children(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
+{
+	struct suj_ino *sino;
+	struct suj_rec *srec;
+	struct jrefrec *rrec;
+	struct direct *dp;
+	off_t diroff;
+	uint8_t *block;
+	int skipparent;
+	int isparent;
+	int dpoff;
+	int size;
+
+	sino = ino_lookup(ino, 0);
+	if (sino)
+		skipparent = sino->si_skipparent;
+	else
+		skipparent = 0;
+	size = lfragtosize(fs, frags);
+	block = dblk_read(blk, size);
+	dp = (struct direct *)&block[0];
+	for (dpoff = 0; dpoff < size && dp->d_reclen; dpoff += dp->d_reclen) {
+		dp = (struct direct *)&block[dpoff];
+		if (dp->d_ino == 0 || dp->d_ino == WINO)
+			continue;
+		if (dp->d_namlen == 1 && dp->d_name[0] == '.')
+			continue;
+		isparent = dp->d_namlen == 2 && dp->d_name[0] == '.' &&
+		    dp->d_name[1] == '.';
+		if (isparent && skipparent == 1)
+			continue;
+		if (debug)
+			printf("Directory %d removing inode %d name %s\n",
+			    ino, dp->d_ino, dp->d_name);
+		/*
+		 * Lookup this inode to see if we have a record for it.
+		 * If not, we've already adjusted it assuming this path
+		 * was valid and we have to adjust once more.
+		 */
+		sino = ino_lookup(dp->d_ino, 0);
+		if (sino == NULL || sino->si_linkadj || sino->si_hasrecs == 0) {
+			ino_decr(dp->d_ino);
+			continue;
+		}
+		/*
+		 * Tell any child directories we've already removed their
+		 * parent.  Don't try to adjust our link down again.
+		 */
+		if (isparent == 0)
+			sino->si_skipparent = 1;
+		/*
+		 * If we haven't yet processed this inode we need to make
+		 * sure we will successfully discover the lost path.  If not
+		 * use nlinkadj to remember.
+		 */
+		diroff = lblktosize(fs, lbn) + dpoff;
+		TAILQ_FOREACH(srec, &sino->si_recs, sr_next) {
+			rrec = (struct jrefrec *)srec->sr_rec;
+			if (rrec->jr_parent == ino &&
+			    rrec->jr_diroff == diroff)
+				break;
+		}
+		if (srec == NULL)
+			sino->si_nlinkadj--;
+	}
+}
+
+/*
+ * Truncate an inode, freeing all blocks and decrementing all children's
+ * link counts.  Free the inode back to the cg.
+ */
+static void
+ino_truncate(union dinode *ip, ino_t ino, int mode)
+{
+	uint32_t gen;
+
+	if (ino == ROOTINO)
+		errx(1, "Attempting to free ROOTINO");
+	if (debug)
+		printf("Truncating and freeing ino %d, nlink %d, mode %o\n",
+		    ino, DIP(ip, di_nlink), DIP(ip, di_mode));
+
+	/* We are freeing an inode or directory. */
+	if ((DIP(ip, di_mode) & IFMT) == IFDIR)
+		ino_visit(ip, ino, ino_free_children, 0);
+	DIP_SET(ip, di_nlink, 0);
+	ino_visit(ip, ino, blk_free_visit, VISIT_EXT | VISIT_INDIR);
+	/* Here we have to clear the inode and release any blocks it holds. */
+	gen = DIP(ip, di_gen);
+	if (fs->fs_magic == FS_UFS1_MAGIC)
+		bzero(ip, sizeof(struct ufs1_dinode));
+	else
+		bzero(ip, sizeof(struct ufs2_dinode));
+	DIP_SET(ip, di_gen, gen);
+	ino_dirty(ino);
+	ino_free(ino, mode);
+	return;
+}
+
+/*
+ * Adjust an inode's link count down by one when a directory goes away.
+ */
+static void
+ino_decr(ino_t ino)
+{
+	union dinode *ip;
+	int reqlink;
+	int nlink;
+	int mode;
+
+	ip = ino_read(ino);
+	nlink = DIP(ip, di_nlink);
+	mode = DIP(ip, di_mode);
+	if (nlink < 1)
+		errx(1, "Inode %d link count %d invalid", ino, nlink);
+	if (mode == 0)
+		errx(1, "Inode %d has a link of %d with 0 mode.", ino, nlink);
+	nlink--;
+	if ((mode & IFMT) == IFDIR)
+		reqlink = 2;
+	else
+		reqlink = 1;
+	if (nlink < reqlink) {
+		if (debug)
+			printf("ino %d not enough links to live %d < %d\n",
+			    ino, nlink, reqlink);
+		ino_truncate(ip, ino, mode);
+		return;
+	}
+	DIP_SET(ip, di_nlink, nlink);
+	ino_dirty(ino);
+}
+
+/*
+ * Adjust the inode link count to 'nlink'.  If the count reaches zero
+ * free it.
+ */
+static void
+ino_adjust(ino_t ino, int lastmode, nlink_t nlink)
+{
+	union dinode *ip;
+	int reqlink;
+	int mode;
+
+	ip = ino_read(ino);
+	mode = DIP(ip, di_mode) & IFMT;
+	if (nlink > LINK_MAX)
+		errx(1,
+		    "ino %d nlink manipulation error, new link %d, old link %d",
+		    ino, nlink, DIP(ip, di_nlink));
+	if (debug)
+		printf("Adjusting ino %d, nlink %d, old link %d lastmode %o\n",
+		    ino, nlink, DIP(ip, di_nlink), lastmode);
+	if (mode == 0) {
+		if (debug)
+			printf("ino %d, zero inode freeing bitmap\n", ino);
+		ino_free(ino, lastmode);
+		return;
+	}
+	/* XXX Should be an assert? */
+	if (mode != lastmode && debug)
+		printf("ino %d, mode %o != %o\n", ino, mode, lastmode);
+	if ((mode & IFMT) == IFDIR)
+		reqlink = 2;
+	else
+		reqlink = 1;
+	/* If the inode doesn't have enough links to live, free it. */
+	if (nlink < reqlink) {
+		if (debug)
+			printf("ino %d not enough links to live %d < %d\n",
+			    ino, nlink, reqlink);
+		ino_truncate(ip, ino, mode);
+		return;
+	}
+	/* If required write the updated link count. */
+	if (DIP(ip, di_nlink) == nlink) {
+		if (debug)
+			printf("ino %d, link matches, skipping.\n", ino);
+		return;
+	}
+	DIP_SET(ip, di_nlink, nlink);
+	ino_dirty(ino);
+}
+
+#define	DOTDOT_OFFSET	DIRECTSIZ(1)
+
+/*
+ * Process records available for one inode and determine whether the
+ * link count is correct or needs adjusting.
+ *
+ * XXX Failed to fix zero length directory.  Shouldn't .. have been mising?
+ */
+static void
+ino_check(struct suj_ino *sino)
+{
+	struct suj_rec *srec;
+	struct jrefrec *rrec;
+	struct suj_ino *stmp;
+	nlink_t dotlinks;
+	int newlinks;
+	int removes;
+	int nlink;
+	ino_t ino;
+	int isdot;
+	int isat;
+	int mode;
+
+	if (sino->si_hasrecs == 0)
+		return;
+	ino = sino->si_ino;
+	/*
+	 * XXX ino_isfree currently is skipping initialized inodes
+	 * that are unreferenced.
+	 */
+	if (0 && ino_isfree(ino))
+		return;
+	rrec = (struct jrefrec *)TAILQ_FIRST(&sino->si_recs)->sr_rec;
+	nlink = rrec->jr_nlink;
+	newlinks = sino->si_nlinkadj;
+	dotlinks = 0;
+	removes = 0;
+	TAILQ_FOREACH(srec, &sino->si_recs, sr_next) {
+		rrec = (struct jrefrec *)srec->sr_rec;
+		isat = ino_isat(rrec->jr_parent, rrec->jr_diroff, 
+		    rrec->jr_ino, &mode, &isdot);
+		if (isat && (mode & IFMT) != (rrec->jr_mode & IFMT))
+			errx(1, "Inode mode/directory type mismatch %o != %o",
+			    mode, rrec->jr_mode);
+		if (debug)
+			printf("jrefrec: op %d ino %d, nlink %d, parent %d, "
+			    "diroff %jd, mode %o, isat %d, isdot %d\n",
+			    rrec->jr_op, rrec->jr_ino, rrec->jr_nlink,
+			    rrec->jr_parent, rrec->jr_diroff, rrec->jr_mode,
+			    isat, isdot);
+		mode = rrec->jr_mode & IFMT;
+		if (rrec->jr_op == JOP_REMREF)
+			removes++;
+		newlinks += isat;
+		if (isdot)
+			dotlinks += isat;
+	}
+	/*
+	 * The number of links that remain are the starting link count
+	 * subtracted by the total number of removes with the total
+	 * links discovered back in.  An incomplete remove thus
+	 * makes no change to the link count but an add increases
+	 * by one.
+	 */
+	nlink += newlinks;
+	nlink -= removes;
+	/*
+	 * If it's a directory with no real names pointing to it go ahead
+	 * and truncate it.  This will free any children.
+	 */
+	if ((mode & IFMT) == IFDIR && nlink - dotlinks == 0) {
+		nlink = 0;
+		/*
+		 * Mark any .. links so they know not to free this inode
+		 * when they are removed.
+		 */
+		TAILQ_FOREACH(srec, &sino->si_recs, sr_next) {
+			rrec = (struct jrefrec *)srec->sr_rec;
+			if (rrec->jr_diroff == DOTDOT_OFFSET) {
+				stmp = ino_lookup(rrec->jr_parent, 0);
+				if (stmp)
+					stmp->si_skipparent = 1;
+			}
+		}
+	}
+	sino->si_linkadj = 1;
+	ino_adjust(ino, mode, nlink);
+}
+
+/*
+ * Process records available for one block and determine whether it is
+ * still allocated and whether the owning inode needs to be updated or
+ * a free completed.
+ */
+static void
+blk_check(struct suj_blk *sblk)
+{
+	struct suj_rec *srec;
+	struct jblkrec *brec;
+	ufs2_daddr_t blk;
+	int mask;
+	int frags;
+	int isat;
+
+	/*
+	 * Each suj_blk actually contains records for any fragments in that
+	 * block.  As a result we must evaluate each record individually.
+	 */
+	TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) {
+		brec = (struct jblkrec *)srec->sr_rec;
+		frags = brec->jb_frags;
+		blk = brec->jb_blkno + brec->jb_oldfrags;
+		isat = blk_isat(brec->jb_ino, brec->jb_lbn, blk, &frags);
+		if (debug)
+			printf("op %d blk %jd ino %d lbn %jd frags %d isat %d (%d)\n",
+			    brec->jb_op, blk, brec->jb_ino, brec->jb_lbn,
+			    brec->jb_frags, isat, frags);
+		/*
+		 * If we found the block at this address we still have to
+		 * determine if we need to free the tail end that was
+		 * added by adding contiguous fragments from the same block.
+		 */
+		if (isat == 1) {
+			if (frags == brec->jb_frags)
+				continue;
+			mask = blk_isfree(blk, brec->jb_ino, brec->jb_lbn,
+			    brec->jb_frags);
+			mask >>= frags;
+			blk += frags;
+			frags = brec->jb_frags - frags;
+			blk_free(blk, mask, frags);
+			ino_adjblks(brec->jb_ino);
+			continue;
+		}
+		/*
+	 	 * The block wasn't found, attempt to free it.  It won't be
+		 * freed if it was actually reallocated.  If this was an
+		 * allocation we don't want to follow indirects as they
+		 * may not be written yet.  Any children of the indirect will
+		 * have their own records.  If it's a free we need to
+		 * recursively free children.
+		 */
+		blk_free_lbn(blk, brec->jb_ino, brec->jb_lbn, brec->jb_frags,
+		    brec->jb_op == JOP_FREEBLK);
+		ino_adjblks(brec->jb_ino);
+	}
+}
+
+/*
+ * Walk the list of inode and block records for this cg, recovering any
+ * changes which were not complete at the time of crash.
+ */
+static void
+cg_check(struct suj_cg *sc)
+{
+	struct suj_blk *nextb;
+	struct suj_ino *nexti;
+	struct suj_ino *sino;
+	struct suj_blk *sblk;
+	int i;
+
+	if (debug)
+		printf("Recovering cg %d\n", sc->sc_cgx);
+
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH_SAFE(sino, &sc->sc_inohash[i], si_next, nexti)
+			ino_check(sino);
+
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH_SAFE(sblk, &sc->sc_blkhash[i], sb_next, nextb)
+			blk_check(sblk);
+}
+
+/*
+ * Write a potentially dirty cg.  All inodes must be written before the
+ * cg maps are so that an allocated inode is never marked free, even if
+ * we crash during fsck.
+ */
+static void
+cg_write(struct suj_cg *sc)
+{
+	struct ino_blk *iblk;
+	ufs1_daddr_t fragno, cgbno, maxbno;
+	u_int8_t *blksfree;
+	struct cg *cgp;
+	int blk;
+	int i;
+
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH(iblk, &sc->sc_iblkhash[i], ib_next)
+			iblk_write(iblk);
+	if (sc->sc_dirty == 0)
+		return;
+	/*
+	 * Fix the frag and cluster summary.
+	 */
+	cgp = sc->sc_cgp;
+	cgp->cg_cs.cs_nbfree = 0;
+	cgp->cg_cs.cs_nffree = 0;
+	bzero(&cgp->cg_frsum, sizeof(cgp->cg_frsum));
+	maxbno = fragstoblks(fs, fs->fs_fpg);
+	if (fs->fs_contigsumsize > 0) {
+		for (i = 1; i <= fs->fs_contigsumsize; i++)
+			cg_clustersum(cgp)[i] = 0;
+		bzero(cg_clustersfree(cgp), howmany(maxbno, CHAR_BIT));
+	}
+	blksfree = cg_blksfree(cgp);
+	for (cgbno = 0; cgbno < maxbno; cgbno++) {
+		if (ffs_isfreeblock(fs, blksfree, cgbno))
+			continue;
+		if (ffs_isblock(fs, blksfree, cgbno)) {
+			ffs_clusteracct(fs, cgp, cgbno, 1);
+			cgp->cg_cs.cs_nbfree++;
+			continue;
+		}
+		fragno = blkstofrags(fs, cgbno);
+		blk = blkmap(fs, blksfree, fragno);
+		ffs_fragacct(fs, blk, cgp->cg_frsum, 1);
+		for (i = 0; i < fs->fs_frag; i++)
+			if (isset(blksfree, fragno + i))
+				cgp->cg_cs.cs_nffree++;
+	}
+	/*
+	 * Update the superblock cg summary from our now correct values
+	 * before writing the block.
+	 */
+	fs->fs_cs(fs, sc->sc_cgx) = cgp->cg_cs;
+	if (bwrite(disk, fsbtodb(fs, cgtod(fs, sc->sc_cgx)), sc->sc_cgbuf,
+	    fs->fs_bsize) == -1)
+		err(1, "Unable to write cylinder group %d", sc->sc_cgx);
+}
+
+static void
+cg_apply(void (*apply)(struct suj_cg *))
+{
+	struct suj_cg *scg;
+	int i;
+
+	for (i = 0; i < SUJ_HASHSIZE; i++)
+		LIST_FOREACH(scg, &cghash[i], sc_next)
+			apply(scg);
+}
+
+/*
+ * Process the unlinked but referenced file list.  Freeing all inodes.
+ */
+static void
+ino_unlinked(void)
+{
+	union dinode *ip;
+	uint16_t mode;
+	ino_t inon;
+	ino_t ino;
+
+	ino = fs->fs_sujfree;
+	fs->fs_sujfree = 0;
+	while (ino != 0) {
+		ip = ino_read(ino);
+		mode = DIP(ip, di_mode) & IFMT;
+		inon = DIP(ip, di_freelink);
+		DIP_SET(ip, di_freelink, 0);
+		/*
+		 * XXX Should this be an errx?
+		 */
+		if (DIP(ip, di_nlink) == 0) {
+			if (debug)
+				printf("Freeing unlinked ino %d mode %o\n",
+				    ino, mode);
+			ino_truncate(ip, ino, mode);
+		} else if (debug)
+			printf("Skipping ino %d mode %o with link %d\n",
+			    ino, mode, DIP(ip, di_nlink));
+		ino = inon;
+	}
+}
+
+/*
+ * If we see two ops for the same inode to the same parent at the same
+ * offset we could miscount the link with ino_isat() returning twice.
+ * Keep only the first record because it has the valid link count but keep
+ * the mode from the final op as that should be the correct mode in case
+ * it changed.
+ */
+static void
+suj_build_ino(struct jrefrec *refrec)
+{
+	struct jmvrec *mvrec;
+	struct suj_rec *srec;
+	struct suj_ino *sino;
+	struct suj_rec *srn;
+	struct jrefrec *rrn;
+
+	if (debug)
+		printf("suj_build_ino: op %d, ino %d, nlink %d, parent %d, diroff %jd\n", 
+		    refrec->jr_op, refrec->jr_ino, refrec->jr_nlink, refrec->jr_parent,
+		    refrec->jr_diroff);
+	sino = ino_lookup(refrec->jr_ino, 1);
+	/*
+	 * Search for a mvrec that matches this offset.  Whether it's an add
+	 * or a remove we can delete the mvref.  It no longer applies to this
+	 * location.
+	 *
+	 * For removes, we have to find the original offset so we can create
+	 * a remove that matches the earlier add so it can be abandoned
+	 * if necessary.  We create an add in the new location so we can
+	 * tolerate the directory block as it existed before or after
+	 * the move.
+	 */
+	if (!TAILQ_EMPTY(&sino->si_movs)) {
+		for (srn = TAILQ_LAST(&sino->si_movs, srechd); srn;
+		    srn = TAILQ_PREV(srn, srechd, sr_next)) {
+			mvrec = (struct jmvrec *)srn->sr_rec;
+			if (mvrec->jm_parent != refrec->jr_parent ||
+			    mvrec->jm_newoff != refrec->jr_diroff)
+				continue;
+			TAILQ_REMOVE(&sino->si_movs, srn, sr_next);
+			if (refrec->jr_op == JOP_REMREF) {
+				rrn = errmalloc(sizeof(*refrec));
+				*rrn = *refrec;
+				rrn->jr_op = JOP_ADDREF;
+				suj_build_ino(rrn);
+				refrec->jr_diroff = mvrec->jm_oldoff;
+			}
+		}
+	}
+	/*
+	 * We walk backwards so that adds and removes are evaluated in the
+	 * correct order.
+	 */
+	for (srn = TAILQ_LAST(&sino->si_recs, srechd); srn;
+	    srn = TAILQ_PREV(srn, srechd, sr_next)) {
+		rrn = (struct jrefrec *)srn->sr_rec;
+		if (rrn->jr_parent != refrec->jr_parent ||
+		    rrn->jr_diroff != refrec->jr_diroff)
+			continue;
+		if (debug)
+			printf("Discarding dup.\n");
+		rrn->jr_mode = refrec->jr_mode;
+		return;
+	}
+	sino->si_hasrecs = 1;
+	srec = errmalloc(sizeof(*srec));
+	srec->sr_rec = (union jrec *)refrec;
+	TAILQ_INSERT_TAIL(&sino->si_recs, srec, sr_next);
+}
+
+/*
+ * Apply a move record to an inode.  We must search for adds that preceed us
+ * and add duplicates because we won't know which location to search first.
+ * Then we add movs to a queue that is maintained until the moved location
+ * is removed.  If a single record is moved multiple times we only maintain
+ * one copy that contains the original and final diroffs.
+ */
+static void
+suj_move_ino(struct jmvrec *mvrec)
+{
+	struct jrefrec *refrec;
+	struct suj_ino *sino;
+	struct suj_rec *srec;
+	struct jmvrec *mvrn;
+	struct suj_rec *srn;
+	struct jrefrec *rrn;
+
+	if (debug)
+		printf("suj_move_ino: ino %d, parent %d, diroff %jd, oldoff %jd\n", 
+		    mvrec->jm_ino, mvrec->jm_parent, mvrec->jm_newoff,
+		    mvrec->jm_oldoff);
+	sino = ino_lookup(mvrec->jm_ino, 0);
+	if (sino == NULL)
+		return;
+	/*
+	 * We walk backwards so we only evaluate the most recent record at
+	 * this offset.
+	 */
+	for (srn = TAILQ_LAST(&sino->si_recs, srechd); srn;
+	    srn = TAILQ_PREV(srn, srechd, sr_next)) {
+		rrn = (struct jrefrec *)srn->sr_rec;
+		if (rrn->jr_op != JOP_ADDREF)
+			continue;
+		if (rrn->jr_parent != mvrec->jm_parent ||
+		    rrn->jr_diroff != mvrec->jm_oldoff)
+			continue;
+		/*
+		 * When an entry is moved we don't know whether the write
+		 * to move has completed yet.  To resolve this we create
+		 * a new add dependency in the new location as if it were added
+		 * twice.  Only one will succeed.
+		 */
+		refrec = errmalloc(sizeof(*refrec));
+		refrec->jr_op = JOP_ADDREF;
+		refrec->jr_ino = mvrec->jm_ino;
+		refrec->jr_parent = mvrec->jm_parent;
+		refrec->jr_diroff = mvrec->jm_newoff;
+		refrec->jr_mode = rrn->jr_mode;
+		refrec->jr_nlink = rrn->jr_nlink;
+		suj_build_ino(refrec);
+		break;
+	}
+	/*
+	 * Add this mvrec to the queue of pending mvs.
+	 */
+	for (srn = TAILQ_LAST(&sino->si_movs, srechd); srn;
+	    srn = TAILQ_PREV(srn, srechd, sr_next)) {
+		mvrn = (struct jmvrec *)srn->sr_rec;
+		if (mvrn->jm_parent != mvrec->jm_parent ||
+		    mvrn->jm_newoff != mvrec->jm_oldoff)
+			continue;
+		mvrn->jm_newoff = mvrec->jm_newoff;
+		return;
+	}
+	srec = errmalloc(sizeof(*srec));
+	srec->sr_rec = (union jrec *)mvrec;
+	TAILQ_INSERT_TAIL(&sino->si_movs, srec, sr_next);
+}
+
+/*
+ * Modify journal records so they refer to the base block number
+ * and a start and end frag range.  This is to facilitate the discovery
+ * of overlapping fragment allocations.
+ */
+static void
+suj_build_blk(struct jblkrec *blkrec)
+{
+	struct suj_rec *srec;
+	struct suj_blk *sblk;
+	struct jblkrec *blkrn;
+	ufs2_daddr_t blk;
+	int frag;
+
+	if (debug)
+		printf("suj_build_blk: op %d blkno %jd frags %d oldfrags %d "
+		    "ino %d lbn %jd\n",
+		    blkrec->jb_op, blkrec->jb_blkno, blkrec->jb_frags,
+		    blkrec->jb_oldfrags, blkrec->jb_ino, blkrec->jb_lbn);
+	blk = blknum(fs, blkrec->jb_blkno);
+	frag = fragnum(fs, blkrec->jb_blkno);
+	sblk = blk_lookup(blk, 1);
+	/*
+	 * Rewrite the record using oldfrags to indicate the offset into
+	 * the block.  Leave jb_frags as the actual allocated count.
+	 */
+	blkrec->jb_blkno -= frag;
+	blkrec->jb_oldfrags = frag;
+	if (blkrec->jb_oldfrags + blkrec->jb_frags > fs->fs_frag)
+		errx(1, "Invalid fragment count %d oldfrags %d",
+		    blkrec->jb_frags, frag);
+	/*
+	 * Detect dups.  If we detect a dup we always discard the oldest
+	 * record as it is superseded by the new record.  This speeds up
+	 * later stages but also eliminates free records which are used
+	 * to indicate that the contents of indirects can be trusted.
+	 */
+	TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) {
+		blkrn = (struct jblkrec *)srec->sr_rec;
+		if (blkrn->jb_ino != blkrec->jb_ino ||
+		    blkrn->jb_lbn != blkrec->jb_lbn ||
+		    blkrn->jb_blkno != blkrec->jb_blkno ||
+		    blkrn->jb_frags != blkrec->jb_frags ||
+		    blkrn->jb_oldfrags != blkrec->jb_oldfrags)
+			continue;
+		if (debug)
+			printf("Removed dup.\n");
+		/* Discard the free which is a dup with an alloc. */
+		if (blkrec->jb_op == JOP_FREEBLK)
+			return;
+		TAILQ_REMOVE(&sblk->sb_recs, srec, sr_next);
+		free(srec);
+		break;
+	}
+	srec = errmalloc(sizeof(*srec));
+	srec->sr_rec = (union jrec *)blkrec;
+	TAILQ_INSERT_TAIL(&sblk->sb_recs, srec, sr_next);
+}
+
+/*
+ * Build up tables of the operations we need to recover.
+ */
+static void
+suj_build(void)
+{
+	struct suj_seg *seg;
+	union jrec *rec;
+	int i;
+
+	TAILQ_FOREACH(seg, &allsegs, ss_next) {
+		rec = (union jrec *)seg->ss_blk;
+		rec++;	/* skip the segrec. */
+		if (debug)
+			printf("seg %jd has %d records, oldseq %jd.\n",
+			    seg->ss_rec.jsr_seq, seg->ss_rec.jsr_cnt,
+			    seg->ss_rec.jsr_oldest);
+		for (i = 0; i < seg->ss_rec.jsr_cnt; i++, rec++) {
+			switch (rec->rec_jrefrec.jr_op) {
+			case JOP_ADDREF:
+			case JOP_REMREF:
+				suj_build_ino((struct jrefrec *)rec);
+				break;
+			case JOP_MVREF:
+				suj_move_ino((struct jmvrec *)rec);
+				break;
+			case JOP_NEWBLK:
+			case JOP_FREEBLK:
+				suj_build_blk((struct jblkrec *)rec);
+				break;
+			default:
+				errx(1, "Unknown journal operation %d (%d)",
+				    rec->rec_jrefrec.jr_op, i);
+			}
+		}
+	}
+}
+
+/*
+ * Prune the journal segments to those we care about based on the
+ * oldest sequence in the newest segment.  Order the segment list
+ * based on sequence number.
+ */
+static void
+suj_prune(void)
+{
+	struct suj_seg *seg;
+	struct suj_seg *segn;
+	uint64_t newseq;
+	int discard;
+
+	if (debug)
+		printf("Pruning up to %jd\n", oldseq);
+	/* First free the expired segments. */
+	TAILQ_FOREACH_SAFE(seg, &allsegs, ss_next, segn) {
+		if (seg->ss_rec.jsr_seq >= oldseq)
+			continue;
+		TAILQ_REMOVE(&allsegs, seg, ss_next);
+		free(seg->ss_blk);
+		free(seg);
+	}
+	/* Next ensure that segments are ordered properly. */
+	seg = TAILQ_FIRST(&allsegs);
+	if (seg == NULL) {
+		if (debug)
+			printf("Empty journal\n");
+		return;
+	}
+	newseq = seg->ss_rec.jsr_seq;
+	for (;;) {
+		seg = TAILQ_LAST(&allsegs, seghd);
+		if (seg->ss_rec.jsr_seq >= newseq)
+			break;
+		TAILQ_REMOVE(&allsegs, seg, ss_next);
+		TAILQ_INSERT_HEAD(&allsegs, seg, ss_next);
+		newseq = seg->ss_rec.jsr_seq;
+		
+	}
+	if (newseq != oldseq)
+		errx(1, "Journal file sequence mismatch %jd != %jd",
+		    newseq, oldseq);
+	/*
+	 * The kernel may asynchronously write segments which can create
+	 * gaps in the sequence space.  Throw away any segments after the
+	 * gap as the kernel guarantees only those that are contiguously
+	 * reachable are marked as completed.
+	 */
+	discard = 0;
+	TAILQ_FOREACH_SAFE(seg, &allsegs, ss_next, segn) {
+		if (!discard && newseq++ == seg->ss_rec.jsr_seq)
+			continue;
+		discard = 1;
+		if (debug)
+			printf("Journal order mismatch %jd != %jd pruning\n",
+			    newseq-1, seg->ss_rec.jsr_seq);
+		TAILQ_REMOVE(&allsegs, seg, ss_next);
+		free(seg->ss_blk);
+		free(seg);
+	}
+	if (debug)
+		printf("Processing journal segments from %jd to %jd\n",
+		    oldseq, newseq-1);
+}
+
+/*
+ * Verify the journal inode before attempting to read records.
+ */
+static void
+suj_verifyino(union dinode *ip)
+{
+
+	if (DIP(ip, di_nlink) != 1)
+		errx(1, "Invalid link count %d for journal inode %d",
+		    DIP(ip, di_nlink), fs->fs_sujournal);
+
+	if (DIP(ip, di_mode) != IFREG)
+		errx(1, "Invalid mode %d for journal inode %d",
+		    DIP(ip, di_mode), fs->fs_sujournal);
+
+	if (DIP(ip, di_size) < SUJ_MIN || DIP(ip, di_size) > SUJ_MAX)
+		errx(1, "Invalid size %jd for journal inode %d",
+		    DIP(ip, di_size), fs->fs_sujournal);
+
+	if (DIP(ip, di_modrev) != fs->fs_mtime)
+		errx(1, "Journal timestamp does not match fs mount time");
+	/* XXX Add further checks. */
+}
+
+struct jblocks {
+	struct jextent *jb_extent;	/* Extent array. */
+	int		jb_avail;	/* Available extents. */
+	int		jb_used;	/* Last used extent. */
+	int		jb_head;	/* Allocator head. */
+	int		jb_off;		/* Allocator extent offset. */
+};
+struct jextent {
+	ufs2_daddr_t	je_daddr;	/* Disk block address. */
+	int		je_blocks;	/* Disk block count. */
+};
+
+struct jblocks *suj_jblocks;
+
+static struct jblocks *
+jblocks_create(void)
+{
+	struct jblocks *jblocks;
+	int size;
+
+	jblocks = errmalloc(sizeof(*jblocks));
+	jblocks->jb_avail = 10;
+	jblocks->jb_used = 0;
+	jblocks->jb_head = 0;
+	jblocks->jb_off = 0;
+	size = sizeof(struct jextent) * jblocks->jb_avail;
+	jblocks->jb_extent = errmalloc(size);
+	bzero(jblocks->jb_extent, size);
+
+	return (jblocks);
+}
+
+/*
+ * Return the next available disk block and the amount of contiguous
+ * free space it contains.
+ */
+static ufs2_daddr_t
+jblocks_next(struct jblocks *jblocks, int bytes, int *actual)
+{
+	struct jextent *jext;
+	ufs2_daddr_t daddr;
+	int freecnt;
+	int blocks;
+
+	blocks = bytes / DEV_BSIZE;
+	jext = &jblocks->jb_extent[jblocks->jb_head];
+	freecnt = jext->je_blocks - jblocks->jb_off;
+	if (freecnt == 0) {
+		jblocks->jb_off = 0;
+		if (++jblocks->jb_head > jblocks->jb_used)
+			return (0);
+		jext = &jblocks->jb_extent[jblocks->jb_head];
+		freecnt = jext->je_blocks;
+	}
+	if (freecnt > blocks)
+		freecnt = blocks;
+	*actual = freecnt * DEV_BSIZE;
+	daddr = jext->je_daddr + jblocks->jb_off;
+
+	return (daddr);
+}
+
+/*
+ * Advance the allocation head by a specified number of bytes, consuming
+ * one journal segment.
+ */
+static void
+jblocks_advance(struct jblocks *jblocks, int bytes)
+{
+
+	jblocks->jb_off += bytes / DEV_BSIZE;
+}
+
+static void
+jblocks_destroy(struct jblocks *jblocks)
+{
+
+	free(jblocks->jb_extent);
+	free(jblocks);
+}
+
+static void
+jblocks_add(struct jblocks *jblocks, ufs2_daddr_t daddr, int blocks)
+{
+	struct jextent *jext;
+	int size;
+
+	jext = &jblocks->jb_extent[jblocks->jb_used];
+	/* Adding the first block. */
+	if (jext->je_daddr == 0) {
+		jext->je_daddr = daddr;
+		jext->je_blocks = blocks;
+		return;
+	}
+	/* Extending the last extent. */
+	if (jext->je_daddr + jext->je_blocks == daddr) {
+		jext->je_blocks += blocks;
+		return;
+	}
+	/* Adding a new extent. */
+	if (++jblocks->jb_used == jblocks->jb_avail) {
+		jblocks->jb_avail *= 2;
+		size = sizeof(struct jextent) * jblocks->jb_avail;
+		jext = errmalloc(size);
+		bzero(jext, size);
+		bcopy(jblocks->jb_extent, jext,
+		    sizeof(struct jextent) * jblocks->jb_used);
+		free(jblocks->jb_extent);
+		jblocks->jb_extent = jext;
+	}
+	jext = &jblocks->jb_extent[jblocks->jb_used];
+	jext->je_daddr = daddr;
+	jext->je_blocks = blocks;
+
+	return;
+}
+
+/*
+ * Add a file block from the journal to the extent map.  We can't read
+ * each file block individually because the kernel treats it as a circular
+ * buffer and segments may span mutliple contiguous blocks.
+ */
+static void
+suj_add_block(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags)
+{
+
+	jblocks_add(suj_jblocks, fsbtodb(fs, blk), fsbtodb(fs, frags));
+}
+
+static void
+suj_read(void)
+{
+	uint8_t block[1 * 1024 * 1024];
+	struct suj_seg *seg;
+	struct jsegrec *rec;
+	ufs2_daddr_t blk;
+	int recsize;
+	int size;
+
+	/*
+	 * Read records until we exhaust the journal space.  If we find
+	 * an invalid record we start searching for a valid segment header
+	 * at the next block.  This is because we don't have a head/tail
+	 * pointer and must recover the information indirectly.  At the gap
+	 * between the head and tail we won't necessarily have a valid
+	 * segment.
+	 */
+	for (;;) {
+		size = sizeof(block);
+		blk = jblocks_next(suj_jblocks, size, &size);
+		if (blk == 0)
+			return;
+		/*
+		 * Read 1MB at a time and scan for records within this block.
+		 */
+		if (bread(disk, blk, &block, size) == -1)
+			err(1, "Error reading journal block %jd",
+			    (intmax_t)blk);
+		for (rec = (void *)block; size; size -= recsize,
+		    rec = (struct jsegrec *)((uintptr_t)rec + recsize)) {
+			recsize = DEV_BSIZE;
+			if (rec->jsr_time != fs->fs_mtime) {
+				if (debug)
+					printf("Rec time %jd != fs mtime %jd\n",
+					    rec->jsr_time, fs->fs_mtime);
+				jblocks_advance(suj_jblocks, recsize);
+				continue;
+			}
+			if (rec->jsr_cnt == 0) {
+				if (debug)
+					printf("Found illegal count %d\n",
+					    rec->jsr_cnt);
+				jblocks_advance(suj_jblocks, recsize);
+				continue;
+			}
+			recsize = roundup2((rec->jsr_cnt + 1) * JREC_SIZE,
+			    DEV_BSIZE);
+			if (recsize > size) {
+				/*
+				 * We may just have run out of buffer, restart
+				 * the loop to re-read from this spot.
+				 */
+				if (size < fs->fs_bsize && 
+				    recsize <= fs->fs_bsize) {
+					recsize = size;
+					continue;
+				}
+				if (debug)
+					printf("Found invalid segsize %d > %d\n",
+					    recsize, size);
+				recsize = DEV_BSIZE;
+				jblocks_advance(suj_jblocks, recsize);
+				continue;
+			}
+			seg = errmalloc(sizeof(*seg));
+			seg->ss_blk = errmalloc(recsize);
+			seg->ss_rec = *rec;
+			bcopy((void *)rec, seg->ss_blk, recsize);
+			if (rec->jsr_oldest > oldseq)
+				oldseq = rec->jsr_oldest;
+			TAILQ_INSERT_TAIL(&allsegs, seg, ss_next);
+			jrecs += rec->jsr_cnt;
+			jbytes += recsize;
+			jblocks_advance(suj_jblocks, recsize);
+		}
+	}
+}
+
+/*
+ * Orchestrate the verification of a filesystem via the softupdates journal.
+ */
+void
+suj_check(const char *filesys)
+{
+	union dinode *jip;
+	uint64_t blocks;
+
+	opendisk(filesys);
+	TAILQ_INIT(&allsegs);
+	/*
+	 * Fetch the journal inode and verify it.
+	 */
+	jip = ino_read(fs->fs_sujournal);
+	printf("SU+J Checking %s\n", filesys);
+	suj_verifyino(jip);
+	/*
+	 * Build a list of journal blocks in jblocks before parsing the
+	 * available journal blocks in with suj_read().
+	 */
+	printf("Reading %jd byte journal from inode %d.\n",
+	    DIP(jip, di_size), fs->fs_sujournal);
+	suj_jblocks = jblocks_create();
+	blocks = ino_visit(jip, fs->fs_sujournal, suj_add_block, 0);
+	if (blocks != numfrags(fs, DIP(jip, di_size)))
+		errx(1, "Sparse journal inode %d.\n", fs->fs_sujournal);
+	suj_read();
+	jblocks_destroy(suj_jblocks);
+	suj_jblocks = NULL;
+	if (reply("RECOVER")) {
+		printf("Building recovery table.\n");
+		suj_prune();
+		suj_build();
+		printf("Resolving unreferenced inode list.\n");
+		ino_unlinked();
+		printf("Processing journal entries.\n");
+		cg_apply(cg_check);
+	}
+	if (reply("WRITE CHANGES"))
+		cg_apply(cg_write);
+	printf("%jd journal records in %jd bytes for %.2f%% utilization\n",
+	    jrecs, jbytes, ((float)jrecs / (float)(jbytes / JREC_SIZE)) * 100);
+	printf("Freed %jd inodes (%jd directories) %jd blocks and %jd frags.\n",
+	    freeinos, freedir, freeblocks, freefrags);
+	/* Write back superblock. */
+	closedisk(filesys);
+}
diff --git a/sbin/fsdb/fsdb.c b/sbin/fsdb/fsdb.c
index f7354e8..5622cbb 100644
--- a/sbin/fsdb/fsdb.c
+++ b/sbin/fsdb/fsdb.c
@@ -396,7 +396,8 @@ const char *typename[] = {
     "unregistered #13",
     "whiteout",
 };
-    
+
+int diroff; 
 int slot;
 
 int
@@ -404,9 +405,10 @@ scannames(struct inodesc *idesc)
 {
 	struct direct *dirp = idesc->id_dirp;
 
-	printf("slot %d ino %d reclen %d: %s, `%.*s'\n",
-	       slot++, dirp->d_ino, dirp->d_reclen, typename[dirp->d_type],
-	       dirp->d_namlen, dirp->d_name);
+	printf("slot %d off %d ino %d reclen %d: %s, `%.*s'\n",
+	       slot++, diroff, dirp->d_ino, dirp->d_reclen,
+	       typename[dirp->d_type], dirp->d_namlen, dirp->d_name);
+	diroff += dirp->d_reclen;
 	return (KEEPON);
 }
 
@@ -416,6 +418,7 @@ CMDFUNCSTART(ls)
     checkactivedir();			/* let it go on anyway */
 
     slot = 0;
+    diroff = 0;
     idesc.id_number = curinum;
     idesc.id_func = scannames;
     idesc.id_type = DATA;
diff --git a/sbin/fsdb/fsdbutil.c b/sbin/fsdb/fsdbutil.c
index d50c6c0..2c5710a 100644
--- a/sbin/fsdb/fsdbutil.c
+++ b/sbin/fsdb/fsdbutil.c
@@ -52,7 +52,7 @@ static const char rcsid[] =
 #include "fsck.h"
 
 static int charsperline(void);
-static int printindir(ufs2_daddr_t blk, int level, char *bufp);
+static void printindir(ufs2_daddr_t blk, int level, char *bufp);
 static void printblocks(ino_t inum, union dinode *dp);
 
 char **
@@ -226,7 +226,7 @@ charsperline(void)
 /*
  * Recursively print a list of indirect blocks.
  */
-static int
+static void
 printindir(ufs2_daddr_t blk, int level, char *bufp)
 {
     struct bufarea buf, *bp;
@@ -234,6 +234,9 @@ printindir(ufs2_daddr_t blk, int level, char *bufp)
     int i, j, cpl, charssofar;
     ufs2_daddr_t blkno;
 
+    if (blk == 0)
+	return;
+    printf("%jd (%d) =>\n", (intmax_t)blk, level);
     if (level == 0) {
 	/* for the final indirect level, don't use the cache */
 	bp = &buf;
@@ -251,11 +254,8 @@ printindir(ufs2_daddr_t blk, int level, char *bufp)
 		blkno = bp->b_un.b_indir1[i];
 	else
 		blkno = bp->b_un.b_indir2[i];
-	if (blkno == 0) {
-	    if (level == 0)
-		putchar('\n');
-	    return 0;
-	}
+	if (blkno == 0)
+	    continue;
 	j = sprintf(tempbuf, "%jd", (intmax_t)blkno);
 	if (level == 0) {
 	    charssofar += j;
@@ -270,13 +270,14 @@ printindir(ufs2_daddr_t blk, int level, char *bufp)
 	    charssofar += 2;
 	} else {
 	    printf(" =>\n");
-	    if (printindir(blkno, level - 1, bufp) == 0)
-		return 0;
+	    printindir(blkno, level - 1, bufp);
+	    printf("\n");
+	    charssofar = 0;
 	}
     }
     if (level == 0)
 	putchar('\n');
-    return 1;
+    return;
 }
 
 
@@ -309,7 +310,7 @@ printblocks(ino_t inum, union dinode *dp)
 	}
     }
     putchar('\n');
-    if (DIP(dp, di_ib[0]) == 0)
+    if (ndb == 0)
 	return;
 
     bufp = malloc((unsigned int)sblock.fs_bsize);
@@ -317,8 +318,7 @@ printblocks(ino_t inum, union dinode *dp)
 	errx(EEXIT, "cannot allocate indirect block buffer");
     printf("Indirect blocks:\n");
     for (i = 0; i < NIADDR; i++)
-	if (printindir(DIP(dp, di_ib[i]), i, bufp) == 0)
-	    break;
+	printindir(DIP(dp, di_ib[i]), i, bufp);
     free(bufp);
 }
 
diff --git a/sbin/tunefs/tunefs.8 b/sbin/tunefs/tunefs.8
index 53e463c..a883cd4 100644
--- a/sbin/tunefs/tunefs.8
+++ b/sbin/tunefs/tunefs.8
@@ -28,7 +28,7 @@
 .\"     @(#)tunefs.8	8.2 (Berkeley) 12/11/93
 .\" $FreeBSD$
 .\"
-.Dd October 21, 2009
+.Dd March 6, 2010
 .Dt TUNEFS 8
 .Os
 .Sh NAME
@@ -40,6 +40,7 @@
 .Op Fl a Cm enable | disable
 .Op Fl e Ar maxbpg
 .Op Fl f Ar avgfilesize
+.Op Fl j Cm enable | disable
 .Op Fl J Cm enable | disable
 .Op Fl L Ar volname
 .Op Fl l Cm enable | disable
@@ -49,6 +50,7 @@
 .Op Fl o Cm space | time
 .Op Fl p
 .Op Fl s Ar avgfpdir
+.Op Fl S Ar size
 .Ar special | filesystem
 .Sh DESCRIPTION
 The
@@ -89,6 +91,8 @@ For file systems with exclusively large files,
 this parameter should be set higher.
 .It Fl f Ar avgfilesize
 Specify the expected average file size.
+.It Fl j Cm enable | disable
+Turn on/off soft updates journaling.
 .It Fl J Cm enable | disable
 Turn on/off gjournal flag.
 .It Fl L Ar volname
@@ -136,6 +140,9 @@ obtained from the
 utility.
 .It Fl s Ar avgfpdir
 Specify the expected number of files per directory.
+.It Fl S Ar size
+Specify the softdep journal size in bytes.
+The minimum is 4M.
 .El
 .Pp
 At least one of the above flags is required.
diff --git a/sbin/tunefs/tunefs.c b/sbin/tunefs/tunefs.c
index e4adb52..a10b35d 100644
--- a/sbin/tunefs/tunefs.c
+++ b/sbin/tunefs/tunefs.c
@@ -52,6 +52,7 @@ __FBSDID("$FreeBSD$");
 #include <ufs/ufs/ufsmount.h>
 #include <ufs/ufs/dinode.h>
 #include <ufs/ffs/fs.h>
+#include <ufs/ufs/dir.h>
 
 #include <ctype.h>
 #include <err.h>
@@ -61,6 +62,7 @@ __FBSDID("$FreeBSD$");
 #include <paths.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <stdint.h>
 #include <string.h>
 #include <unistd.h>
 
@@ -72,16 +74,20 @@ struct uufsd disk;
 
 void usage(void);
 void printfs(void);
+int journal_alloc(int64_t size);
+void journal_clear(void);
+void sbdirty(void);
 
 int
 main(int argc, char *argv[])
 {
-	char *avalue, *Jvalue, *Lvalue, *lvalue, *Nvalue, *nvalue;
+	char *avalue, *jvalue, *Jvalue, *Lvalue, *lvalue, *Nvalue, *nvalue;
 	const char *special, *on;
 	const char *name;
 	int active;
-	int Aflag, aflag, eflag, evalue, fflag, fvalue, Jflag, Lflag, lflag;
-	int mflag, mvalue, Nflag, nflag, oflag, ovalue, pflag, sflag, svalue;
+	int Aflag, aflag, eflag, evalue, fflag, fvalue, jflag, Jflag, Lflag;
+	int lflag, mflag, mvalue, Nflag, nflag, oflag, ovalue, pflag, sflag;
+	int svalue, Sflag, Svalue;
 	int ch, found_arg, i;
 	const char *chg[2];
 	struct ufs_args args;
@@ -89,13 +95,13 @@ main(int argc, char *argv[])
 
 	if (argc < 3)
 		usage();
-	Aflag = aflag = eflag = fflag = Jflag = Lflag = lflag = mflag = 0;
-	Nflag = nflag = oflag = pflag = sflag = 0;
-	avalue = Jvalue = Lvalue = lvalue = Nvalue = nvalue = NULL;
-	evalue = fvalue = mvalue = ovalue = svalue = 0;
+	Aflag = aflag = eflag = fflag = jflag = Jflag = Lflag = lflag = 0;
+	mflag = Nflag = nflag = oflag = pflag = sflag = 0;
+	avalue = jvalue = Jvalue = Lvalue = lvalue = Nvalue = nvalue = NULL;
+	evalue = fvalue = mvalue = ovalue = svalue = Svalue = 0;
 	active = 0;
 	found_arg = 0;		/* At least one arg is required. */
-	while ((ch = getopt(argc, argv, "Aa:e:f:J:L:l:m:N:n:o:ps:")) != -1)
+	while ((ch = getopt(argc, argv, "Aa:e:f:j:J:L:l:m:N:n:o:ps:S:")) != -1)
 		switch (ch) {
 
 		case 'A':
@@ -135,6 +141,18 @@ main(int argc, char *argv[])
 			fflag = 1;
 			break;
 
+		case 'j':
+			found_arg = 1;
+			name = "softdep journaled file system";
+			jvalue = optarg;
+			if (strcmp(jvalue, "enable") &&
+			    strcmp(jvalue, "disable")) {
+				errx(10, "bad %s (options are %s)",
+				    name, "`enable' or `disable'");
+			}
+			jflag = 1;
+			break;
+
 		case 'J':
 			found_arg = 1;
 			name = "gjournaled file system";
@@ -240,6 +258,16 @@ main(int argc, char *argv[])
 			sflag = 1;
 			break;
 
+		case 'S':
+			found_arg = 1;
+			name = "Softdep Journal Size";
+			Svalue = atoi(optarg);
+			if (Svalue < SUJ_MIN)
+				errx(10, "%s must be >= %d (was %s)",
+				    name, SUJ_MIN, optarg);
+			Sflag = 1;
+			break;
+
 		default:
 			usage();
 		}
@@ -310,6 +338,33 @@ main(int argc, char *argv[])
 			sblock.fs_avgfilesize = fvalue;
 		}
 	}
+	if (jflag) {
+ 		name = "soft updates journaling";
+ 		if (strcmp(jvalue, "enable") == 0) {
+			if ((sblock.fs_flags & (FS_DOSOFTDEP | FS_SUJ)) ==
+			    (FS_DOSOFTDEP | FS_SUJ)) {
+				warnx("%s remains unchanged as enabled", name);
+			} else if (sblock.fs_clean == 0) {
+				warnx("%s cannot be enabled until fsck is run",
+				    name);
+			} else if (journal_alloc(Svalue) != 0) {
+				warnx("%s can not be enabled", name);
+			} else {
+ 				sblock.fs_flags |= FS_DOSOFTDEP | FS_SUJ;
+ 				warnx("%s set", name);
+			}
+ 		} else if (strcmp(jvalue, "disable") == 0) {
+			if ((~sblock.fs_flags & FS_SUJ) == FS_SUJ) {
+				warnx("%s remains unchanged as disabled", name);
+			} else {
+				journal_clear();
+ 				sblock.fs_flags &= ~(FS_DOSOFTDEP | FS_SUJ);
+				sblock.fs_sujfree = 0;
+ 				warnx("%s cleared, "
+				    "remove .sujournal to reclaim space", name);
+			}
+ 		}
+	}
 	if (Jflag) {
 		name = "gjournal";
 		if (strcmp(Jvalue, "enable") == 0) {
@@ -456,6 +511,500 @@ err:
 }
 
 void
+sbdirty(void)
+{
+	disk.d_fs.fs_flags |= FS_UNCLEAN | FS_NEEDSFSCK;
+	disk.d_fs.fs_clean = 0;
+}
+
+int blocks;
+static char clrbuf[MAXBSIZE];
+
+static ufs2_daddr_t
+journal_balloc(void)
+{
+	ufs2_daddr_t blk;
+	struct cg *cgp;
+	int valid;
+	static int contig = 1;
+
+	cgp = &disk.d_cg;
+	for (;;) {
+		blk = cgballoc(&disk);
+		if (blk > 0)
+			break;
+		/*
+		 * If we failed to allocate a block from this cg, move to
+		 * the next.
+		 */
+		if (cgwrite(&disk) < 0) {
+			warn("Failed to write updated cg");
+			return (-1);
+		}
+		while ((valid = cgread(&disk)) == 1) {
+			/*
+			 * Try to minimize fragmentation by requiring a minimum
+			 * number of blocks present.
+			 */
+			if (cgp->cg_cs.cs_nbfree > blocks / 8)
+				break;
+			if (contig == 0 && cgp->cg_cs.cs_nbfree)
+				break;
+		}
+		if (valid)
+			continue;
+		/*
+		 * Try once through looking only for large contiguous regions
+		 * and again taking any space we can find.
+		 */
+		if (contig) {
+			contig = 0;
+			disk.d_ccg = 0;
+			warnx("Journal file fragmented.");
+			continue;
+		}
+		warnx("Failed to find sufficient free blocks for the journal");
+		return -1;
+	}
+	if (bwrite(&disk, fsbtodb(&sblock, blk), clrbuf,
+	    sblock.fs_bsize) <= 0) {
+		warn("Failed to initialize new block");
+		return -1;
+	}
+	return (blk);
+}
+
+/*
+ * Search a directory block for the SUJ_FILE.
+ */
+static ino_t
+dir_search(ufs2_daddr_t blk, int bytes)
+{
+	char block[MAXBSIZE];
+	struct direct *dp;
+	int off;
+
+	if (bread(&disk, fsbtodb(&sblock, blk), block, bytes) <= 0) {
+		warn("Failed to read dir block");
+		return (-1);
+	}
+	for (off = 0; off < bytes; off += dp->d_reclen) {
+		dp = (struct direct *)&block[off];
+		if (dp->d_reclen == 0)
+			break;
+		if (dp->d_ino == 0)
+			continue;
+		if (dp->d_namlen != strlen(SUJ_FILE))
+			continue;
+		if (bcmp(dp->d_name, SUJ_FILE, dp->d_namlen) != 0)
+			continue;
+		return (dp->d_ino);
+	}
+
+	return (0);
+}
+
+/*
+ * Search in the ROOTINO for the SUJ_FILE.  If it exists we can not enable
+ * journaling.
+ */
+static ino_t
+journal_findfile(void)
+{
+	struct ufs1_dinode *dp1;
+	struct ufs2_dinode *dp2;
+	ino_t ino;
+	int mode;
+	void *ip;
+	int i;
+
+	if (getino(&disk, &ip, ROOTINO, &mode) != 0) {
+		warn("Failed to get root inode");
+		return (-1);
+	}
+	dp2 = ip;
+	dp1 = ip;
+	if (sblock.fs_magic == FS_UFS1_MAGIC) {
+		if ((off_t)dp1->di_size >= lblktosize(&sblock, NDADDR)) {
+			warnx("ROOTINO extends beyond direct blocks.");
+			return (-1);
+		}
+		for (i = 0; i < NDADDR; i++) {
+			if (dp1->di_db[i] == 0)
+				break;
+			if ((ino = dir_search(dp1->di_db[i],
+			    sblksize(&sblock, (off_t)dp1->di_size, i))) != 0)
+				return (ino);
+		}
+	} else {
+		if ((off_t)dp1->di_size >= lblktosize(&sblock, NDADDR)) {
+			warnx("ROOTINO extends beyond direct blocks.");
+			return (-1);
+		}
+		for (i = 0; i < NDADDR; i++) {
+			if (dp2->di_db[i] == 0)
+				break;
+			if ((ino = dir_search(dp2->di_db[i],
+			    sblksize(&sblock, (off_t)dp2->di_size, i))) != 0)
+				return (ino);
+		}
+	}
+
+	return (0);
+}
+
+/*
+ * Insert the journal at inode 'ino' into directory blk 'blk' at the first
+ * free offset of 'off'.  DIRBLKSIZ blocks after off are initialized as
+ * empty.
+ */
+static int
+dir_insert(ufs2_daddr_t blk, off_t off, ino_t ino)
+{
+	struct direct *dp;
+	char block[MAXBSIZE];
+
+	if (bread(&disk, fsbtodb(&sblock, blk), block, sblock.fs_bsize) <= 0) {
+		warn("Failed to read dir block");
+		return (-1);
+	}
+	bzero(&block[off], sblock.fs_bsize - off);
+	dp = (struct direct *)&block[off];
+	dp->d_ino = ino;
+	dp->d_reclen = DIRBLKSIZ;
+	dp->d_type = DT_REG;
+	dp->d_namlen = strlen(SUJ_FILE);
+	bcopy(SUJ_FILE, &dp->d_name, strlen(SUJ_FILE));
+	off += DIRBLKSIZ;
+	for (; off < sblock.fs_bsize; off += DIRBLKSIZ) {
+		dp = (struct direct *)&block[off];
+		dp->d_ino = 0;
+		dp->d_reclen = DIRBLKSIZ;
+		dp->d_type = DT_UNKNOWN;
+	}
+	if (bwrite(&disk, fsbtodb(&sblock, blk), block, sblock.fs_bsize) <= 0) {
+		warn("Failed to write dir block");
+		return (-1);
+	}
+	return (0);
+}
+
+/*
+ * Extend a directory block in 'blk' by copying it to a full size block
+ * and inserting the new journal inode into .sujournal.
+ */
+static int
+dir_extend(ufs2_daddr_t blk, ufs2_daddr_t nblk, off_t size, ino_t ino)
+{
+	char block[MAXBSIZE];
+
+	if (bread(&disk, fsbtodb(&sblock, blk), block, size) <= 0) {
+		warn("Failed to read dir block");
+		return (-1);
+	}
+	if (bwrite(&disk, fsbtodb(&sblock, nblk), block, size) <= 0) {
+		warn("Failed to write dir block");
+		return (-1);
+	}
+
+	return dir_insert(nblk, size, ino);
+}
+
+/*
+ * Insert the journal file into the ROOTINO directory.  We always extend the
+ * last frag
+ */
+static int
+journal_insertfile(ino_t ino)
+{
+	struct ufs1_dinode *dp1;
+	struct ufs2_dinode *dp2;
+	void *ip;
+	ufs2_daddr_t nblk;
+	ufs2_daddr_t blk;
+	ufs_lbn_t lbn;
+	int size;
+	int mode;
+	int off;
+
+	if (getino(&disk, &ip, ROOTINO, &mode) != 0) {
+		warn("Failed to get root inode");
+		sbdirty();
+		return (-1);
+	}
+	dp2 = ip;
+	dp1 = ip;
+	blk = 0;
+	size = 0;
+	nblk = journal_balloc();
+	if (nblk <= 0)
+		return (-1);
+	/*
+	 * For simplicity sake we aways extend the ROOTINO into a new
+	 * directory block rather than searching for space and inserting
+	 * into an existing block.  However, if the rootino has frags
+	 * have to free them and extend the block.
+	 */
+	if (sblock.fs_magic == FS_UFS1_MAGIC) {
+		lbn = lblkno(&sblock, dp1->di_size);
+		off = blkoff(&sblock, dp1->di_size);
+		blk = dp1->di_db[lbn];
+		size = sblksize(&sblock, (off_t)dp1->di_size, lbn);
+	} else {
+		lbn = lblkno(&sblock, dp2->di_size);
+		off = blkoff(&sblock, dp2->di_size);
+		blk = dp2->di_db[lbn];
+		size = sblksize(&sblock, (off_t)dp2->di_size, lbn);
+	}
+	if (off != 0) {
+		if (dir_extend(blk, nblk, off, ino) == -1)
+			return (-1);
+	} else {
+		blk = 0;
+		if (dir_insert(nblk, 0, ino) == -1)
+			return (-1);
+	}
+	if (sblock.fs_magic == FS_UFS1_MAGIC) {
+		dp1->di_blocks += (sblock.fs_bsize - size) / DEV_BSIZE;
+		dp1->di_db[lbn] = nblk;
+		dp1->di_size = lblktosize(&sblock, lbn+1);
+	} else {
+		dp2->di_blocks += (sblock.fs_bsize - size) / DEV_BSIZE;
+		dp2->di_db[lbn] = nblk;
+		dp2->di_size = lblktosize(&sblock, lbn+1);
+	}
+	if (putino(&disk) < 0) {
+		warn("Failed to write root inode");
+		return (-1);
+	}
+	if (cgwrite(&disk) < 0) {
+		warn("Failed to write updated cg");
+		sbdirty();
+		return (-1);
+	}
+	if (blk) {
+		if (cgbfree(&disk, blk, size) < 0) {
+			warn("Failed to write cg");
+			return (-1);
+		}
+	}
+
+	return (0);
+}
+
+static int
+indir_fill(ufs2_daddr_t blk, int level, int *resid)
+{
+	char indirbuf[MAXBSIZE];
+	ufs1_daddr_t *bap1;
+	ufs2_daddr_t *bap2;
+	ufs2_daddr_t nblk;
+	int ncnt;
+	int cnt;
+	int i;
+
+	bzero(indirbuf, sizeof(indirbuf));
+	bap1 = (ufs1_daddr_t *)indirbuf;
+	bap2 = (void *)bap1;
+	cnt = 0;
+	for (i = 0; i < NINDIR(&sblock) && *resid != 0; i++) {
+		nblk = journal_balloc();
+		if (nblk <= 0)
+			return (-1);
+		cnt++;
+		if (sblock.fs_magic == FS_UFS1_MAGIC)
+			*bap1++ = nblk;
+		else
+			*bap2++ = nblk;
+		if (level != 0) {
+			ncnt = indir_fill(nblk, level - 1, resid);
+			if (ncnt <= 0)
+				return (-1);
+			cnt += ncnt;
+		} else 
+			(*resid)--;
+	}
+	if (bwrite(&disk, fsbtodb(&sblock, blk), indirbuf,
+	    sblock.fs_bsize) <= 0) {
+		warn("Failed to write indirect");
+		return (-1);
+	}
+	return (cnt);
+}
+
+/*
+ * Clear the flag bits so the journal can be removed.
+ */
+void
+journal_clear(void)
+{
+	struct ufs1_dinode *dp1;
+	struct ufs2_dinode *dp2;
+	ino_t ino;
+	int mode;
+	void *ip;
+
+	ino = journal_findfile();
+	if (ino == (ino_t)-1 || ino == 0) {
+		warnx("Journal file does not exist");
+		return;
+	}
+	printf("Clearing journal flags from inode %d\n", ino);
+	if (getino(&disk, &ip, ino, &mode) != 0) {
+		warn("Failed to get journal inode");
+		return;
+	}
+	dp2 = ip;
+	dp1 = ip;
+	if (sblock.fs_magic == FS_UFS1_MAGIC)
+		dp1->di_flags = 0;
+	else
+		dp2->di_flags = 0;
+	if (putino(&disk) < 0) {
+		warn("Failed to write journal inode");
+		return;
+	}
+}
+
+int
+journal_alloc(int64_t size)
+{
+	struct ufs1_dinode *dp1;
+	struct ufs2_dinode *dp2;
+	ufs2_daddr_t blk;
+	void *ip;
+	struct cg *cgp;
+	int resid;
+	ino_t ino;
+	int blks;
+	int mode;
+	int i;
+
+	cgp = &disk.d_cg;
+	ino = 0;
+
+	/*
+	 * If the journal file exists we can't allocate it.
+	 */
+	ino = journal_findfile();
+	if (ino == (ino_t)-1)
+		return (-1);
+	if (ino > 0) {
+		warnx("Journal file %s already exists, please remove.",
+		    SUJ_FILE);
+		return (-1);
+	}
+	/*
+	 * If the user didn't supply a size pick one based on the filesystem
+	 * size constrained with hardcoded MIN and MAX values.  We opt for
+	 * 1/1024th of the filesystem up to MAX but not exceeding one CG and
+	 * not less than the MIN.
+	 */
+	if (size == 0) {
+		size = (sblock.fs_size * sblock.fs_bsize) / 1024;
+		size = MIN(SUJ_MAX, size);
+		if (size / sblock.fs_fsize > sblock.fs_fpg)
+			size = sblock.fs_fpg * sblock.fs_fsize;
+		size = MAX(SUJ_MIN, size);
+	}
+	resid = blocks = size / sblock.fs_bsize;
+	if (sblock.fs_cstotal.cs_nbfree < blocks) {
+		warn("Insufficient free space for %jd byte journal", size);
+		return (-1);
+	}
+	/*
+	 * Find a cg with enough blocks to satisfy the journal
+	 * size.  Presently the journal does not span cgs.
+	 */
+	while (cgread(&disk) == 1) {
+		if (cgp->cg_cs.cs_nifree == 0)
+			continue;
+		ino = cgialloc(&disk);
+		if (ino <= 0)
+			break;
+		printf("Using inode %d in cg %d for %jd byte journal\n", 
+		    ino, cgp->cg_cgx, size);
+		if (getino(&disk, &ip, ino, &mode) != 0) {
+			warn("Failed to get allocated inode");
+			sbdirty();
+			goto out;
+		}
+		/*
+		 * We leave fields unrelated to the number of allocated
+		 * blocks and size uninitialized.  This causes legacy
+		 * fsck implementations to clear the inode.
+		 */
+		dp2 = ip;
+		dp1 = ip;
+		if (sblock.fs_magic == FS_UFS1_MAGIC) {
+			bzero(dp1, sizeof(*dp1));
+			dp1->di_size = size;
+			dp1->di_mode = IFREG | IREAD;
+			dp1->di_nlink = 1;
+			dp1->di_flags = SF_IMMUTABLE | SF_NOUNLINK | UF_NODUMP;
+		} else {
+			bzero(dp2, sizeof(*dp2));
+			dp2->di_size = size;
+			dp2->di_mode = IFREG | IREAD;
+			dp2->di_nlink = 1;
+			dp2->di_flags = SF_IMMUTABLE | SF_NOUNLINK | UF_NODUMP;
+		}
+		for (i = 0; i < NDADDR && resid; i++, resid--) {
+			blk = journal_balloc();
+			if (blk <= 0)
+				goto out;
+			if (sblock.fs_magic == FS_UFS1_MAGIC) {
+				dp1->di_db[i] = blk;
+				dp1->di_blocks++;
+			} else {
+				dp2->di_db[i] = blk;
+				dp2->di_blocks++;
+			}
+		}
+		for (i = 0; i < NIADDR && resid; i++) {
+			blk = journal_balloc();
+			if (blk <= 0)
+				goto out;
+			blks = indir_fill(blk, i, &resid) + 1;
+			if (blks <= 0) {
+				sbdirty();
+				goto out;
+			}
+			if (sblock.fs_magic == FS_UFS1_MAGIC) {
+				dp1->di_ib[i] = blk;
+				dp1->di_blocks += blks;
+			} else {
+				dp2->di_ib[i] = blk;
+				dp2->di_blocks += blks;
+			}
+		}
+		if (sblock.fs_magic == FS_UFS1_MAGIC)
+			dp1->di_blocks *= sblock.fs_bsize / disk.d_bsize;
+		else
+			dp2->di_blocks *= sblock.fs_bsize / disk.d_bsize;
+		if (putino(&disk) < 0) {
+			warn("Failed to write inode");
+			sbdirty();
+			return (-1);
+		}
+		if (cgwrite(&disk) < 0) {
+			warn("Failed to write updated cg");
+			sbdirty();
+			return (-1);
+		}
+		if (journal_insertfile(ino) < 0) {
+			sbdirty();
+			return (-1);
+		}
+		sblock.fs_sujfree = 0;
+		return (0);
+	}
+	warnx("Insufficient free space for the journal.");
+out:
+	return (-1);
+}
+
+void
 usage(void)
 {
 	fprintf(stderr, "%s\n%s\n%s\n%s\n",
@@ -477,6 +1026,8 @@ printfs(void)
 		(sblock.fs_flags & FS_MULTILABEL)? "enabled" : "disabled");
 	warnx("soft updates: (-n)                                 %s", 
 		(sblock.fs_flags & FS_DOSOFTDEP)? "enabled" : "disabled");
+	warnx("soft update journaling: (-j)                       %s", 
+		(sblock.fs_flags & FS_SUJ)? "enabled" : "disabled");
 	warnx("gjournal: (-J)                                     %s",
 		(sblock.fs_flags & FS_GJOURNAL)? "enabled" : "disabled");
 	warnx("maximum blocks per file in a cylinder group: (-e)  %d",