From a57449541074720475dfc21dfb8b025695b573eb Mon Sep 17 00:00:00 2001 From: jeff Date: Sat, 24 Apr 2010 07:05:35 +0000 Subject: - 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 --- sbin/dumpfs/dumpfs.c | 4 +- sbin/fsck_ffs/Makefile | 3 +- sbin/fsck_ffs/fsck.h | 5 +- sbin/fsck_ffs/gjournal.c | 293 +-- sbin/fsck_ffs/main.c | 27 +- sbin/fsck_ffs/pass5.c | 1 + sbin/fsck_ffs/suj.c | 4699 ++++++++++++++++++++++++++++++++++++++++++++++ sbin/fsdb/fsdb.c | 11 +- sbin/fsdb/fsdbutil.c | 26 +- sbin/tunefs/tunefs.8 | 9 +- sbin/tunefs/tunefs.c | 567 +++++- 11 files changed, 5328 insertions(+), 317 deletions(-) create mode 100644 sbin/fsck_ffs/suj.c (limited to 'sbin') 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 #include #include +#include #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 + * 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 +__FBSDID("$FreeBSD$"); + +#include +#include +#include +#include + +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include + +#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 + * 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 +__FBSDID("$FreeBSD$"); + +#include +#include +#include +#include + +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include + +#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 #include #include +#include #include #include @@ -61,6 +62,7 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include #include #include @@ -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", -- cgit v1.1