code:
/*-
 * Copyright (c) 1982, 1986, 1993
 *	The Regents of the University of California.  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.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
 *
 *	@(#)fs.h	8.13 (Berkeley) 3/21/95
 * $FreeBSD: release/9.0.0/sys/ufs/ffs/fs.h 224061 2011-07-15 16:20:33Z mckusick $
 */

#ifndef _UFS_FFS_FS_H_
#define _UFS_FFS_FS_H_

/*
 * Each disk drive contains some number of filesystems.
 * A filesystem consists of a number of cylinder groups.
 * Each cylinder group has inodes and data.
 *
 * A filesystem is described by its super-block, which in turn
 * describes the cylinder groups.  The super-block is critical
 * data and is replicated in each cylinder group to protect against
 * catastrophic loss.  This is done at `newfs' time and the critical
 * super-block data does not change, so the copies need not be
 * referenced further unless disaster strikes.
 *
 * For filesystem fs, the offsets of the various blocks of interest
 * are given in the super block as:
 *	[fs->fs_sblkno]		Super-block
 *	[fs->fs_cblkno]		Cylinder group block
 *	[fs->fs_iblkno]		Inode blocks
 *	[fs->fs_dblkno]		Data blocks
 * The beginning of cylinder group cg in fs, is given by
 * the ``cgbase(fs, cg)'' macro.
 *
 * Depending on the architecture and the media, the superblock may
 * reside in any one of four places. For tiny media where every block
 * counts, it is placed at the very front of the partition. Historically,
 * UFS1 placed it 8K from the front to leave room for the disk label and
 * a small bootstrap. For UFS2 it got moved to 64K from the front to leave
 * room for the disk label and a bigger bootstrap, and for really piggy
 * systems we check at 256K from the front if the first three fail. In
 * all cases the size of the superblock will be SBLOCKSIZE. All values are
 * given in byte-offset form, so they do not imply a sector size. The
 * SBLOCKSEARCH specifies the order in which the locations should be searched.
 */
#define SBLOCK_FLOPPY	     0
#define SBLOCK_UFS1	  8192
#define SBLOCK_UFS2	 65536
#define SBLOCK_PIGGY	262144
#define SBLOCKSIZE	  8192
#define SBLOCKSEARCH \
	{ SBLOCK_UFS2, SBLOCK_UFS1, SBLOCK_FLOPPY, SBLOCK_PIGGY, -1 }

/*
 * Max number of fragments per block. This value is NOT tweakable.
 */
#define MAXFRAG 	8

/*
 * Addresses stored in inodes are capable of addressing fragments
 * of `blocks'. File system blocks of at most size MAXBSIZE can
 * be optionally broken into 2, 4, or 8 pieces, each of which is
 * addressable; these pieces may be DEV_BSIZE, or some multiple of
 * a DEV_BSIZE unit.
 *
 * Large files consist of exclusively large data blocks.  To avoid
 * undue wasted disk space, the last data block of a small file may be
 * allocated as only as many fragments of a large block as are
 * necessary.  The filesystem format retains only a single pointer
 * to such a fragment, which is a piece of a single large block that
 * has been divided.  The size of such a fragment is determinable from
 * information in the inode, using the ``blksize(fs, ip, lbn)'' macro.
 *
 * The filesystem records space availability at the fragment level;
 * to determine block availability, aligned fragments are examined.
 */

/*
 * MINBSIZE is the smallest allowable block size.
 * In order to insure that it is possible to create files of size
 * 2^32 with only two levels of indirection, MINBSIZE is set to 4096.
 * MINBSIZE must be big enough to hold a cylinder group block,
 * thus changes to (struct cg) must keep its size within MINBSIZE.
 * Note that super blocks are always of size SBLOCKSIZE,
 * and that both SBLOCKSIZE and MAXBSIZE must be >= MINBSIZE.
 */
#define MINBSIZE	4096

/*
 * The path name on which the filesystem is mounted is maintained
 * in fs_fsmnt. MAXMNTLEN defines the amount of space allocated in
 * the super block for this name.
 */
#define MAXMNTLEN	468

/*
 * The volume name for this filesystem is maintained in fs_volname.
 * MAXVOLLEN defines the length of the buffer allocated.
 */
#define MAXVOLLEN	32

/*
 * There is a 128-byte region in the superblock reserved for in-core
 * pointers to summary information. Originally this included an array
 * of pointers to blocks of struct csum; now there are just a few
 * pointers and the remaining space is padded with fs_ocsp[].
 *
 * NOCSPTRS determines the size of this padding. One pointer (fs_csp)
 * is taken away to point to a contiguous array of struct csum for
 * all cylinder groups; a second (fs_maxcluster) points to an array
 * of cluster sizes that is computed as cylinder groups are inspected,
 * and the third points to an array that tracks the creation of new
 * directories. A fourth pointer, fs_active, is used when creating
 * snapshots; it points to a bitmap of cylinder groups for which the
 * free-block bitmap has changed since the snapshot operation began.
 */
#define	NOCSPTRS	((128 / sizeof(void *)) - 4)

/*
 * A summary of contiguous blocks of various sizes is maintained
 * in each cylinder group. Normally this is set by the initial
 * value of fs_maxcontig. To conserve space, a maximum summary size
 * is set by FS_MAXCONTIG.
 */
#define FS_MAXCONTIG	16

/*
 * MINFREE gives the minimum acceptable percentage of filesystem
 * blocks which may be free. If the freelist drops below this level
 * only the superuser may continue to allocate blocks. This may
 * be set to 0 if no reserve of free blocks is deemed necessary,
 * however throughput drops by fifty percent if the filesystem
 * is run at between 95% and 100% full; thus the minimum default
 * value of fs_minfree is 5%. However, to get good clustering
 * performance, 10% is a better choice. hence we use 10% as our
 * default value. With 10% free space, fragmentation is not a
 * problem, so we choose to optimize for time.
 */
#define MINFREE		8
#define DEFAULTOPT	FS_OPTTIME

/*
 * Grigoriy Orlov <gluk@ptci.ru> has done some extensive work to fine
 * tune the layout preferences for directories within a filesystem.
 * His algorithm can be tuned by adjusting the following parameters
 * which tell the system the average file size and the average number
 * of files per directory. These defaults are well selected for typical
 * filesystems, but may need to be tuned for odd cases like filesystems
 * being used for squid caches or news spools.
 */
#define AVFILESIZ	16384	/* expected average file size */
#define AFPDIR		64	/* expected number of files per directory */

/*
 * The maximum number of snapshot nodes that can be associated
 * with each filesystem. This limit affects only the number of
 * snapshot files that can be recorded within the superblock so
 * that they can be found when the filesystem is mounted. However,
 * maintaining too many will slow the filesystem performance, so
 * having this limit is a good idea.
 */
#define FSMAXSNAP 20

/*
 * Used to identify special blocks in snapshots:
 *
 * BLK_NOCOPY - A block that was unallocated at the time the snapshot
 *	was taken, hence does not need to be copied when written.
 * BLK_SNAP - A block held by another snapshot that is not needed by this
 *	snapshot. When the other snapshot is freed, the BLK_SNAP entries
 *	are converted to BLK_NOCOPY. These are needed to allow fsck to
 *	identify blocks that are in use by other snapshots (which are
 *	expunged from this snapshot).
 */
#define BLK_NOCOPY ((ufs2_daddr_t)(1))
#define BLK_SNAP ((ufs2_daddr_t)(2))

/*
 * Sysctl values for the fast filesystem.
 */
#define	FFS_ADJ_REFCNT		 1	/* adjust inode reference count */
#define	FFS_ADJ_BLKCNT		 2	/* adjust inode used block count */
#define	FFS_BLK_FREE		 3	/* free range of blocks in map */
#define	FFS_DIR_FREE		 4	/* free specified dir inodes in map */
#define	FFS_FILE_FREE		 5	/* free specified file inodes in map */
#define	FFS_SET_FLAGS		 6	/* set filesystem flags */
#define	FFS_ADJ_NDIR		 7	/* adjust number of directories */
#define	FFS_ADJ_NBFREE		 8	/* adjust number of free blocks */
#define	FFS_ADJ_NIFREE		 9	/* adjust number of free inodes */
#define	FFS_ADJ_NFFREE		10 	/* adjust number of free frags */
#define	FFS_ADJ_NUMCLUSTERS	11	/* adjust number of free clusters */
#define FFS_SET_CWD		12	/* set current directory */
#define	FFS_SET_DOTDOT		13	/* set inode number for ".." */
#define	FFS_UNLINK		14	/* remove a name in the filesystem */
#define	FFS_SET_INODE		15	/* update an on-disk inode */
#define	FFS_SET_BUFOUTPUT	16	/* set buffered writing on descriptor */
#define	FFS_MAXID		16	/* number of valid ffs ids */

/*
 * Command structure passed in to the filesystem to adjust filesystem values.
 */
#define	FFS_CMD_VERSION		0x19790518	/* version ID */
struct fsck_cmd {
	int32_t	version;	/* version of command structure */
	int32_t	handle;		/* reference to filesystem to be changed */
	int64_t	value;		/* inode or block number to be affected */
	int64_t	size;		/* amount or range to be adjusted */
	int64_t	spare;		/* reserved for future use */
};

/*
 * Per cylinder group information; summarized in blocks allocated
 * from first cylinder group data blocks.  These blocks have to be
 * read in from fs_csaddr (size fs_cssize) in addition to the
 * super block.
 */
struct csum {
	int32_t	cs_ndir;		/* number of directories */
	int32_t	cs_nbfree;		/* number of free blocks */
	int32_t	cs_nifree;		/* number of free inodes */
	int32_t	cs_nffree;		/* number of free frags */
};
struct csum_total {
	int64_t	cs_ndir;		/* number of directories */
	int64_t	cs_nbfree;		/* number of free blocks */
	int64_t	cs_nifree;		/* number of free inodes */
	int64_t	cs_nffree;		/* number of free frags */
	int64_t	cs_numclusters;		/* number of free clusters */
	int64_t	cs_spare[3];		/* future expansion */
};

/*
 * Super block for an FFS filesystem.
 */
struct fs {
	int32_t	 fs_firstfield;		/* historic filesystem linked list, */
	int32_t	 fs_unused_1;		/*     used for incore super blocks */
	int32_t	 fs_sblkno;		/* offset of super-block in filesys */
	int32_t	 fs_cblkno;		/* offset of cyl-block in filesys */
	int32_t	 fs_iblkno;		/* offset of inode-blocks in filesys */
	int32_t	 fs_dblkno;		/* offset of first data after cg */
	int32_t	 fs_old_cgoffset;	/* cylinder group offset in cylinder */
	int32_t	 fs_old_cgmask;		/* used to calc mod fs_ntrak */
	int32_t  fs_old_time;		/* last time written */
	int32_t	 fs_old_size;		/* number of blocks in fs */
	int32_t	 fs_old_dsize;		/* number of data blocks in fs */
	u_int32_t fs_ncg;		/* number of cylinder groups */
	int32_t	 fs_bsize;		/* size of basic blocks in fs */
	int32_t	 fs_fsize;		/* size of frag blocks in fs */
	int32_t	 fs_frag;		/* number of frags in a block in fs */
/* these are configuration parameters */
	int32_t	 fs_minfree;		/* minimum percentage of free blocks */
	int32_t	 fs_old_rotdelay;	/* num of ms for optimal next block */
	int32_t	 fs_old_rps;		/* disk revolutions per second */
/* these fields can be computed from the others */
	int32_t	 fs_bmask;		/* ``blkoff'' calc of blk offsets */
	int32_t	 fs_fmask;		/* ``fragoff'' calc of frag offsets */
	int32_t	 fs_bshift;		/* ``lblkno'' calc of logical blkno */
	int32_t	 fs_fshift;		/* ``numfrags'' calc number of frags */
/* these are configuration parameters */
	int32_t	 fs_maxcontig;		/* max number of contiguous blks */
	int32_t	 fs_maxbpg;		/* max number of blks per cyl group */
/* these fields can be computed from the others */
	int32_t	 fs_fragshift;		/* block to frag shift */
	int32_t	 fs_fsbtodb;		/* fsbtodb and dbtofsb shift constant */
	int32_t	 fs_sbsize;		/* actual size of super block */
	int32_t	 fs_spare1[2];		/* old fs_csmask */
					/* old fs_csshift */
	int32_t	 fs_nindir;		/* value of NINDIR */
	u_int32_t fs_inopb;		/* value of INOPB */
	int32_t	 fs_old_nspf;		/* value of NSPF */
/* yet another configuration parameter */
	int32_t	 fs_optim;		/* optimization preference, see below */
	int32_t	 fs_old_npsect;		/* # sectors/track including spares */
	int32_t	 fs_old_interleave;	/* hardware sector interleave */
	int32_t	 fs_old_trackskew;	/* sector 0 skew, per track */
	int32_t	 fs_id[2];		/* unique filesystem id */
/* sizes determined by number of cylinder groups and their sizes */
	int32_t	 fs_old_csaddr;		/* blk addr of cyl grp summary area */
	int32_t	 fs_cssize;		/* size of cyl grp summary area */
	int32_t	 fs_cgsize;		/* cylinder group size */
	int32_t	 fs_spare2;		/* old fs_ntrak */
	int32_t	 fs_old_nsect;		/* sectors per track */
	int32_t  fs_old_spc;		/* sectors per cylinder */
	int32_t	 fs_old_ncyl;		/* cylinders in filesystem */
	int32_t	 fs_old_cpg;		/* cylinders per group */
	u_int32_t fs_ipg;		/* inodes per group */
	int32_t	 fs_fpg;		/* blocks per group * fs_frag */
/* this data must be re-computed after crashes */
	struct	csum fs_old_cstotal;	/* cylinder summary information */
/* these fields are cleared at mount time */
	int8_t   fs_fmod;		/* super block modified flag */
	int8_t   fs_clean;		/* filesystem is clean flag */
	int8_t 	 fs_ronly;		/* mounted read-only flag */
	int8_t   fs_old_flags;		/* old FS_ flags */
	u_char	 fs_fsmnt[MAXMNTLEN];	/* name mounted on */
	u_char	 fs_volname[MAXVOLLEN];	/* volume name */
	u_int64_t fs_swuid;		/* system-wide uid */
	int32_t  fs_pad;		/* due to alignment of fs_swuid */
/* these fields retain the current block allocation info */
	int32_t	 fs_cgrotor;		/* last cg searched */
	void 	*fs_ocsp[NOCSPTRS];	/* padding; was list of fs_cs buffers */
	u_int8_t *fs_contigdirs;	/* (u) # of contig. allocated dirs */
	struct	csum *fs_csp;		/* (u) cg summary info buffer */
	int32_t	*fs_maxcluster;		/* (u) max cluster in each cyl group */
	u_int	*fs_active;		/* (u) used by snapshots to track fs */
	int32_t	 fs_old_cpc;		/* cyl per cycle in postbl */
	int32_t	 fs_maxbsize;		/* maximum blocking factor permitted */
	int64_t	 fs_unrefs;		/* number of unreferenced inodes */
	int64_t	 fs_sparecon64[16];	/* old rotation block list head */
	int64_t	 fs_sblockloc;		/* byte offset of standard superblock */
	struct	csum_total fs_cstotal;	/* (u) cylinder summary information */
	ufs_time_t fs_time;		/* last time written */
	int64_t	 fs_size;		/* number of blocks in fs */
	int64_t	 fs_dsize;		/* number of data blocks in fs */
	ufs2_daddr_t fs_csaddr;		/* blk addr of cyl grp summary area */
	int64_t	 fs_pendingblocks;	/* (u) blocks being freed */
	u_int32_t fs_pendinginodes;	/* (u) inodes being freed */
	ino_t	 fs_snapinum[FSMAXSNAP];/* list of snapshot inode numbers */
	u_int32_t fs_avgfilesize;	/* expected average file size */
	u_int32_t fs_avgfpdir;		/* expected # of files per directory */
	int32_t	 fs_save_cgsize;	/* save real cg size to use fs_bsize */
	ufs_time_t fs_mtime;		/* Last mount or fsck time. */
	int32_t  fs_sujfree;		/* SUJ free list */
	int32_t	 fs_sparecon32[23];	/* reserved for future constants */
	int32_t  fs_flags;		/* see FS_ flags below */
	int32_t	 fs_contigsumsize;	/* size of cluster summary array */
	int32_t	 fs_maxsymlinklen;	/* max length of an internal symlink */
	int32_t	 fs_old_inodefmt;	/* format of on-disk inodes */
	u_int64_t fs_maxfilesize;	/* maximum representable file size */
	int64_t	 fs_qbmask;		/* ~fs_bmask for use with 64-bit size */
	int64_t	 fs_qfmask;		/* ~fs_fmask for use with 64-bit size */
	int32_t	 fs_state;		/* validate fs_clean field */
	int32_t	 fs_old_postblformat;	/* format of positional layout tables */
	int32_t	 fs_old_nrpos;		/* number of rotational positions */
	int32_t	 fs_spare5[2];		/* old fs_postbloff */
					/* old fs_rotbloff */
	int32_t	 fs_magic;		/* magic number */
};

/* Sanity checking. */
#ifdef CTASSERT
CTASSERT(sizeof(struct fs) == 1376);
#endif

/*
 * Filesystem identification
 */
#define	FS_UFS1_MAGIC	0x011954	/* UFS1 fast filesystem magic number */
#define	FS_UFS2_MAGIC	0x19540119	/* UFS2 fast filesystem magic number */
#define	FS_BAD_MAGIC	0x19960408	/* UFS incomplete newfs magic number */
#define	FS_OKAY		0x7c269d38	/* superblock checksum */
#define FS_42INODEFMT	-1		/* 4.2BSD inode format */
#define FS_44INODEFMT	2		/* 4.4BSD inode format */

/*
 * Preference for optimization.
 */
#define FS_OPTTIME	0	/* minimize allocation time */
#define FS_OPTSPACE	1	/* minimize disk fragmentation */

/*
 * Filesystem flags.
 *
 * The FS_UNCLEAN flag is set by the kernel when the filesystem was
 * mounted with fs_clean set to zero. The FS_DOSOFTDEP flag indicates
 * that the filesystem should be managed by the soft updates code.
 * Note that the FS_NEEDSFSCK flag is set and cleared only by the
 * fsck utility. It is set when background fsck finds an unexpected
 * inconsistency which requires a traditional foreground fsck to be
 * run. Such inconsistencies should only be found after an uncorrectable
 * disk error. A foreground fsck will clear the FS_NEEDSFSCK flag when
 * it has successfully cleaned up the filesystem. The kernel uses this
 * flag to enforce that inconsistent filesystems be mounted read-only.
 * The FS_INDEXDIRS flag when set indicates that the kernel maintains
 * on-disk auxiliary indexes (such as B-trees) for speeding directory
 * accesses. Kernels that do not support auxiliary indicies clear the
 * flag to indicate that the indicies need to be rebuilt (by fsck) before
 * they can be used.
 *
 * FS_ACLS indicates that POSIX.1e ACLs are administratively enabled
 * for the file system, so they should be loaded from extended attributes,
 * observed for access control purposes, and be administered by object
 * owners.  FS_NFS4ACLS indicates that NFSv4 ACLs are administratively
 * enabled.  This flag is mutually exclusive with FS_ACLS.  FS_MULTILABEL
 * indicates that the TrustedBSD MAC Framework should attempt to back MAC
 * labels into extended attributes on the file system rather than maintain
 * a single mount label for all objects.
 */
#define FS_UNCLEAN	0x0001	/* filesystem not clean at mount */
#define FS_DOSOFTDEP	0x0002	/* filesystem using soft dependencies */
#define FS_NEEDSFSCK	0x0004	/* filesystem needs sync fsck before mount */
#define	FS_SUJ       	0x0008	/* Filesystem using softupdate journal */
#define FS_ACLS		0x0010	/* file system has POSIX.1e ACLs enabled */
#define FS_MULTILABEL	0x0020	/* file system is MAC multi-label */
#define FS_GJOURNAL	0x0040	/* gjournaled file system */
#define FS_FLAGS_UPDATED 0x0080	/* flags have been moved to new location */
#define FS_NFS4ACLS	0x0100	/* file system has NFSv4 ACLs enabled */
#define FS_INDEXDIRS	0x0200	/* kernel supports indexed directories */
#define	FS_TRIM		0x0400	/* issue BIO_DELETE for deleted blocks */

/*
 * Macros to access bits in the fs_active array.
 */
#define	ACTIVECGNUM(fs, cg)	((fs)->fs_active[(cg) / (NBBY * sizeof(int))])
#define	ACTIVECGOFF(cg)		(1 << ((cg) % (NBBY * sizeof(int))))
#define	ACTIVESET(fs, cg)	do {					\
	if ((fs)->fs_active)						\
		ACTIVECGNUM((fs), (cg)) |= ACTIVECGOFF((cg));		\
} while (0)
#define	ACTIVECLEAR(fs, cg)	do {					\
	if ((fs)->fs_active)						\
		ACTIVECGNUM((fs), (cg)) &= ~ACTIVECGOFF((cg));		\
} while (0)

/*
 * The size of a cylinder group is calculated by CGSIZE. The maximum size
 * is limited by the fact that cylinder groups are at most one block.
 * Its size is derived from the size of the maps maintained in the
 * cylinder group and the (struct cg) size.
 */
#define CGSIZE(fs) \
    /* base cg */	(sizeof(struct cg) + sizeof(int32_t) + \
    /* old btotoff */	(fs)->fs_old_cpg * sizeof(int32_t) + \
    /* old boff */	(fs)->fs_old_cpg * sizeof(u_int16_t) + \
    /* inode map */	howmany((fs)->fs_ipg, NBBY) + \
    /* block map */	howmany((fs)->fs_fpg, NBBY) +\
    /* if present */	((fs)->fs_contigsumsize <= 0 ? 0 : \
    /* cluster sum */	(fs)->fs_contigsumsize * sizeof(int32_t) + \
    /* cluster map */	howmany(fragstoblks(fs, (fs)->fs_fpg), NBBY)))

/*
 * The minimal number of cylinder groups that should be created.
 */
#define MINCYLGRPS	4

/*
 * Convert cylinder group to base address of its global summary info.
 */
#define fs_cs(fs, indx) fs_csp[indx]

/*
 * Cylinder group block for a filesystem.
 */
#define	CG_MAGIC	0x090255
struct cg {
	int32_t	 cg_firstfield;		/* historic cyl groups linked list */
	int32_t	 cg_magic;		/* magic number */
	int32_t  cg_old_time;		/* time last written */
	u_int32_t cg_cgx;		/* we are the cgx'th cylinder group */
	int16_t	 cg_old_ncyl;		/* number of cyl's this cg */
	int16_t  cg_old_niblk;		/* number of inode blocks this cg */
	u_int32_t cg_ndblk;		/* number of data blocks this cg */
	struct	 csum cg_cs;		/* cylinder summary information */
	u_int32_t cg_rotor;		/* position of last used block */
	u_int32_t cg_frotor;		/* position of last used frag */
	u_int32_t cg_irotor;		/* position of last used inode */
	u_int32_t cg_frsum[MAXFRAG];	/* counts of available frags */
	int32_t	 cg_old_btotoff;	/* (int32) block totals per cylinder */
	int32_t	 cg_old_boff;		/* (u_int16) free block positions */
	u_int32_t cg_iusedoff;		/* (u_int8) used inode map */
	u_int32_t cg_freeoff;		/* (u_int8) free block map */
	u_int32_t cg_nextfreeoff;	/* (u_int8) next available space */
	u_int32_t cg_clustersumoff;	/* (u_int32) counts of avail clusters */
	u_int32_t cg_clusteroff;		/* (u_int8) free cluster map */
	u_int32_t cg_nclusterblks;	/* number of clusters this cg */
	u_int32_t cg_niblk;		/* number of inode blocks this cg */
	u_int32_t cg_initediblk;		/* last initialized inode */
	u_int32_t cg_unrefs;		/* number of unreferenced inodes */
	int32_t	 cg_sparecon32[2];	/* reserved for future use */
	ufs_time_t cg_time;		/* time last written */
	int64_t	 cg_sparecon64[3];	/* reserved for future use */
	u_int8_t cg_space[1];		/* space for cylinder group maps */
/* actually longer */
};

/*
 * Macros for access to cylinder group array structures
 */
#define cg_chkmagic(cgp) ((cgp)->cg_magic == CG_MAGIC)
#define cg_inosused(cgp) \
    ((u_int8_t *)((u_int8_t *)(cgp) + (cgp)->cg_iusedoff))
#define cg_blksfree(cgp) \
    ((u_int8_t *)((u_int8_t *)(cgp) + (cgp)->cg_freeoff))
#define cg_clustersfree(cgp) \
    ((u_int8_t *)((u_int8_t *)(cgp) + (cgp)->cg_clusteroff))
#define cg_clustersum(cgp) \
    ((int32_t *)((uintptr_t)(cgp) + (cgp)->cg_clustersumoff))

/*
 * Turn filesystem block numbers into disk block addresses.
 * This maps filesystem blocks to device size blocks.
 */
#define	fsbtodb(fs, b)	((daddr_t)(b) << (fs)->fs_fsbtodb)
#define	dbtofsb(fs, b)	((b) >> (fs)->fs_fsbtodb)

/*
 * Cylinder group macros to locate things in cylinder groups.
 * They calc filesystem addresses of cylinder group data structures.
 */
#define	cgbase(fs, c)	(((ufs2_daddr_t)(fs)->fs_fpg) * (c))
#define	cgdmin(fs, c)	(cgstart(fs, c) + (fs)->fs_dblkno)	/* 1st data */
#define	cgimin(fs, c)	(cgstart(fs, c) + (fs)->fs_iblkno)	/* inode blk */
#define	cgsblock(fs, c)	(cgstart(fs, c) + (fs)->fs_sblkno)	/* super blk */
#define	cgtod(fs, c)	(cgstart(fs, c) + (fs)->fs_cblkno)	/* cg block */
#define cgstart(fs, c)							\
       ((fs)->fs_magic == FS_UFS2_MAGIC ? cgbase(fs, c) :		\
       (cgbase(fs, c) + (fs)->fs_old_cgoffset * ((c) & ~((fs)->fs_old_cgmask))))

/*
 * Macros for handling inode numbers:
 *     inode number to filesystem block offset.
 *     inode number to cylinder group number.
 *     inode number to filesystem block address.
 */
#define	ino_to_cg(fs, x)	(((ino_t)(x)) / (fs)->fs_ipg)
#define	ino_to_fsba(fs, x)						\
	((ufs2_daddr_t)(cgimin(fs, ino_to_cg(fs, (ino_t)(x))) +		\
	    (blkstofrags((fs), ((((ino_t)(x)) % (fs)->fs_ipg) / INOPB(fs))))))
#define	ino_to_fsbo(fs, x)	(((ino_t)(x)) % INOPB(fs))

/*
 * Give cylinder group number for a filesystem block.
 * Give cylinder group block number for a filesystem block.
 */
#define	dtog(fs, d)	((d) / (fs)->fs_fpg)
#define	dtogd(fs, d)	((d) % (fs)->fs_fpg)

/*
 * Extract the bits for a block from a map.
 * Compute the cylinder and rotational position of a cyl block addr.
 */
#define blkmap(fs, map, loc) \
    (((map)[(loc) / NBBY] >> ((loc) % NBBY)) & (0xff >> (NBBY - (fs)->fs_frag)))

/*
 * The following macros optimize certain frequently calculated
 * quantities by using shifts and masks in place of divisions
 * modulos and multiplications.
 */
#define blkoff(fs, loc)		/* calculates (loc % fs->fs_bsize) */ \
	((loc) & (fs)->fs_qbmask)
#define fragoff(fs, loc)	/* calculates (loc % fs->fs_fsize) */ \
	((loc) & (fs)->fs_qfmask)
#define lfragtosize(fs, frag)	/* calculates ((off_t)frag * fs->fs_fsize) */ \
	(((off_t)(frag)) << (fs)->fs_fshift)
#define lblktosize(fs, blk)	/* calculates ((off_t)blk * fs->fs_bsize) */ \
	(((off_t)(blk)) << (fs)->fs_bshift)
/* Use this only when `blk' is known to be small, e.g., < NDADDR. */
#define smalllblktosize(fs, blk)    /* calculates (blk * fs->fs_bsize) */ \
	((blk) << (fs)->fs_bshift)
#define lblkno(fs, loc)		/* calculates (loc / fs->fs_bsize) */ \
	((loc) >> (fs)->fs_bshift)
#define numfrags(fs, loc)	/* calculates (loc / fs->fs_fsize) */ \
	((loc) >> (fs)->fs_fshift)
#define blkroundup(fs, size)	/* calculates roundup(size, fs->fs_bsize) */ \
	(((size) + (fs)->fs_qbmask) & (fs)->fs_bmask)
#define fragroundup(fs, size)	/* calculates roundup(size, fs->fs_fsize) */ \
	(((size) + (fs)->fs_qfmask) & (fs)->fs_fmask)
#define fragstoblks(fs, frags)	/* calculates (frags / fs->fs_frag) */ \
	((frags) >> (fs)->fs_fragshift)
#define blkstofrags(fs, blks)	/* calculates (blks * fs->fs_frag) */ \
	((blks) << (fs)->fs_fragshift)
#define fragnum(fs, fsb)	/* calculates (fsb % fs->fs_frag) */ \
	((fsb) & ((fs)->fs_frag - 1))
#define blknum(fs, fsb)		/* calculates rounddown(fsb, fs->fs_frag) */ \
	((fsb) &~ ((fs)->fs_frag - 1))

/*
 * Determine the number of available frags given a
 * percentage to hold in reserve.
 */
#define freespace(fs, percentreserved) \
	(blkstofrags((fs), (fs)->fs_cstotal.cs_nbfree) + \
	(fs)->fs_cstotal.cs_nffree - \
	(((off_t)((fs)->fs_dsize)) * (percentreserved) / 100))

/*
 * Determining the size of a file block in the filesystem.
 */
#define blksize(fs, ip, lbn) \
	(((lbn) >= NDADDR || (ip)->i_size >= smalllblktosize(fs, (lbn) + 1)) \
	    ? (fs)->fs_bsize \
	    : (fragroundup(fs, blkoff(fs, (ip)->i_size))))
#define sblksize(fs, size, lbn) \
	(((lbn) >= NDADDR || (size) >= ((lbn) + 1) << (fs)->fs_bshift) \
	  ? (fs)->fs_bsize \
	  : (fragroundup(fs, blkoff(fs, (size)))))

/*
 * Number of indirects in a filesystem block.
 */
#define	NINDIR(fs)	((fs)->fs_nindir)

/*
 * Indirect lbns are aligned on NDADDR addresses where single indirects
 * are the negated address of the lowest lbn reachable, double indirects
 * are this lbn - 1 and triple indirects are this lbn - 2.  This yields
 * an unusual bit order to determine level.
 */
static inline int
lbn_level(ufs_lbn_t lbn)
{
	if (lbn >= 0)
		return 0;
	switch (lbn & 0x3) {
	case 0:
		return (0);
	case 1:
		break;
	case 2:
		return (2);
	case 3:
		return (1);
	default:
		break;
	}
	return (-1);
}

static inline ufs_lbn_t
lbn_offset(struct fs *fs, int level)
{
	ufs_lbn_t res;

	for (res = 1; level > 0; level--)
		res *= NINDIR(fs);
	return (res);
}

/*
 * Number of inodes in a secondary storage block/fragment.
 */
#define	INOPB(fs)	((fs)->fs_inopb)
#define	INOPF(fs)	((fs)->fs_inopb >> (fs)->fs_fragshift)

/*
 * Softdep journal record format.
 */

#define	JOP_ADDREF	1	/* Add a reference to an inode. */
#define	JOP_REMREF	2	/* Remove a reference from an inode. */
#define	JOP_NEWBLK	3	/* Allocate a block. */
#define	JOP_FREEBLK	4	/* Free a block or a tree of blocks. */
#define	JOP_MVREF	5	/* Move a reference from one off to another. */
#define	JOP_TRUNC	6	/* Partial truncation record. */
#define	JOP_SYNC	7	/* fsync() complete record. */

#define	JREC_SIZE	32	/* Record and segment header size. */

#define	SUJ_MIN		(4 * 1024 * 1024)	/* Minimum journal size */
#define	SUJ_MAX		(32 * 1024 * 1024)	/* Maximum journal size */
#define	SUJ_FILE	".sujournal"		/* Journal file name */

/*
 * Size of the segment record header.  There is at most one for each disk
 * block in the journal.  The segment header is followed by an array of
 * records.  fsck depends on the first element in each record being 'op'
 * and the second being 'ino'.  Segments may span multiple disk blocks but
 * the header is present on each.
 */
struct jsegrec {
	uint64_t	jsr_seq;	/* Our sequence number */
	uint64_t	jsr_oldest;	/* Oldest valid sequence number */
	uint16_t	jsr_cnt;	/* Count of valid records */
	uint16_t	jsr_blocks;	/* Count of device bsize blocks. */
	uint32_t	jsr_crc;	/* 32bit crc of the valid space */
	ufs_time_t	jsr_time;	/* timestamp for mount instance */
};

/*
 * Reference record.  Records a single link count modification.
 */
struct jrefrec {
	uint32_t	jr_op;
	ino_t		jr_ino;
	ino_t		jr_parent;
	uint16_t	jr_nlink;
	uint16_t	jr_mode;
	off_t		jr_diroff;
	uint64_t	jr_unused;
};

/*
 * Move record.  Records a reference moving within a directory block.  The
 * nlink is unchanged but we must search both locations.
 */
struct jmvrec {
	uint32_t	jm_op;
	ino_t		jm_ino;
	ino_t		jm_parent;
	uint16_t	jm_unused;
	off_t		jm_oldoff;
	off_t		jm_newoff;
};

/*
 * Block record.  A set of frags or tree of blocks starting at an indirect are
 * freed or a set of frags are allocated.
 */
struct jblkrec {
	uint32_t	jb_op;
	uint32_t	jb_ino;
	ufs2_daddr_t	jb_blkno;
	ufs_lbn_t	jb_lbn;
	uint16_t	jb_frags;
	uint16_t	jb_oldfrags;
	uint32_t	jb_unused;
};

/*
 * Truncation record.  Records a partial truncation so that it may be
 * completed at check time.  Also used for sync records.
 */
struct jtrncrec {
	uint32_t	jt_op;
	uint32_t	jt_ino;
	off_t		jt_size;
	uint32_t	jt_extsize;
	uint32_t	jt_pad[3];
};

union jrec {
	struct jsegrec	rec_jsegrec;
	struct jrefrec	rec_jrefrec;
	struct jmvrec	rec_jmvrec;
	struct jblkrec	rec_jblkrec;
	struct jtrncrec	rec_jtrncrec;
};

#ifdef CTASSERT
CTASSERT(sizeof(struct jsegrec) == JREC_SIZE);
CTASSERT(sizeof(struct jrefrec) == JREC_SIZE);
CTASSERT(sizeof(struct jmvrec) == JREC_SIZE);
CTASSERT(sizeof(struct jblkrec) == JREC_SIZE);
CTASSERT(sizeof(struct jtrncrec) == JREC_SIZE);
CTASSERT(sizeof(union jrec) == JREC_SIZE);
#endif

extern int inside[], around[];
extern u_char *fragtbl[];

#endif


code:
/*-
 * Copyright 1998, 2000 Marshall Kirk McKusick. All Rights Reserved.
 *
 * The soft updates code is derived from the appendix of a University
 * of Michigan technical report (Gregory R. Ganger and Yale N. Patt,
 * "Soft Updates: A Solution to the Metadata Update Problem in File
 * Systems", CSE-TR-254-95, August 1995).
 *
 * Further information about soft updates can be obtained from:
 *
 *	Marshall Kirk McKusick		http://www.mckusick.com/softdep/
 *	1614 Oxford Street		mckusick@mckusick.com
 *	Berkeley, CA 94709-1608		+1-510-843-9542
 *	USA
 *
 * 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 MARSHALL KIRK MCKUSICK ``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 MARSHALL KIRK MCKUSICK 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.
 *
 *	@(#)softdep.h	9.7 (McKusick) 6/21/00
 * $FreeBSD: release/9.0.0/sys/ufs/ffs/softdep.h 223772 2011-07-04 22:08:04Z jeff $
 */

#include <sys/queue.h>

/*
 * Allocation dependencies are handled with undo/redo on the in-memory
 * copy of the data. A particular data dependency is eliminated when
 * it is ALLCOMPLETE: that is ATTACHED, DEPCOMPLETE, and COMPLETE.
 *
 * The ATTACHED flag means that the data is not currently being written
 * to disk.
 *
 * The UNDONE flag means that the data has been rolled back to a safe
 * state for writing to the disk. When the I/O completes, the data is
 * restored to its current form and the state reverts to ATTACHED.
 * The data must be locked throughout the rollback, I/O, and roll
 * forward so that the rolled back information is never visible to
 * user processes.
 *
 * The COMPLETE flag indicates that the item has been written. For example,
 * a dependency that requires that an inode be written will be marked
 * COMPLETE after the inode has been written to disk.
 *
 * The DEPCOMPLETE flag indicates the completion of any other
 * dependencies such as the writing of a cylinder group map has been
 * completed. A dependency structure may be freed only when both it
 * and its dependencies have completed and any rollbacks that are in
 * progress have finished as indicated by the set of ALLCOMPLETE flags
 * all being set.
 *
 * The two MKDIR flags indicate additional dependencies that must be done
 * when creating a new directory. MKDIR_BODY is cleared when the directory
 * data block containing the "." and ".." entries has been written.
 * MKDIR_PARENT is cleared when the parent inode with the increased link
 * count for ".." has been written. When both MKDIR flags have been
 * cleared, the DEPCOMPLETE flag is set to indicate that the directory
 * dependencies have been completed. The writing of the directory inode
 * itself sets the COMPLETE flag which then allows the directory entry for
 * the new directory to be written to disk. The RMDIR flag marks a dirrem
 * structure as representing the removal of a directory rather than a
 * file. When the removal dependencies are completed, additional work needs
 * to be done* (an additional decrement of the associated inode, and a
 * decrement of the parent inode).
 *
 * The DIRCHG flag marks a diradd structure as representing the changing
 * of an existing entry rather than the addition of a new one. When
 * the update is complete the dirrem associated with the inode for
 * the old name must be added to the worklist to do the necessary
 * reference count decrement.
 *
 * The GOINGAWAY flag indicates that the data structure is frozen from
 * further change until its dependencies have been completed and its
 * resources freed after which it will be discarded.
 *
 * The IOSTARTED flag prevents multiple calls to the I/O start routine from
 * doing multiple rollbacks.
 *
 * The NEWBLOCK flag marks pagedep structures that have just been allocated,
 * so must be claimed by the inode before all dependencies are complete.
 *
 * The INPROGRESS flag marks worklist structures that are still on the
 * worklist, but are being considered for action by some process.
 *
 * The UFS1FMT flag indicates that the inode being processed is a ufs1 format.
 *
 * The EXTDATA flag indicates that the allocdirect describes an
 * extended-attributes dependency.
 *
 * The ONWORKLIST flag shows whether the structure is currently linked
 * onto a worklist.
 *
 * The UNLINK* flags track the progress of updating the on-disk linked
 * list of active but unlinked inodes. When an inode is first unlinked
 * it is marked as UNLINKED. When its on-disk di_freelink has been
 * written its UNLINKNEXT flags is set. When its predecessor in the
 * list has its di_freelink pointing at us its UNLINKPREV is set.
 * When the on-disk list can reach it from the superblock, its
 * UNLINKONLIST flag is set. Once all of these flags are set, it
 * is safe to let its last name be removed.
 */
#define	ATTACHED	0x000001
#define	UNDONE		0x000002
#define	COMPLETE	0x000004
#define	DEPCOMPLETE	0x000008
#define	MKDIR_PARENT	0x000010 /* diradd, mkdir, jaddref, jsegdep only */
#define	MKDIR_BODY	0x000020 /* diradd, mkdir, jaddref only */
#define	RMDIR		0x000040 /* dirrem only */
#define	DIRCHG		0x000080 /* diradd, dirrem only */
#define	GOINGAWAY	0x000100 /* indirdep, jremref only */
#define	IOSTARTED	0x000200 /* inodedep, pagedep, bmsafemap only */
#define	DELAYEDFREE	0x000400 /* allocindirect free delayed. */
#define	NEWBLOCK	0x000800 /* pagedep, jaddref only */
#define	INPROGRESS	0x001000 /* dirrem, freeblks, freefrag, freefile only */
#define	UFS1FMT		0x002000 /* indirdep only */
#define	EXTDATA		0x004000 /* allocdirect only */
#define ONWORKLIST	0x008000
#define	IOWAITING	0x010000 /* Thread is waiting for IO to complete. */
#define	ONDEPLIST	0x020000 /* Structure is on a dependency list. */
#define	UNLINKED	0x040000 /* inodedep has been unlinked. */
#define	UNLINKNEXT	0x080000 /* inodedep has valid di_freelink */
#define	UNLINKPREV	0x100000 /* inodedep is pointed at in the unlink list */
#define	UNLINKONLIST	0x200000 /* inodedep is in the unlinked list on disk */
#define	UNLINKLINKS	(UNLINKNEXT | UNLINKPREV)

#define	ALLCOMPLETE	(ATTACHED | COMPLETE | DEPCOMPLETE)

/*
 * The workitem queue.
 *
 * It is sometimes useful and/or necessary to clean up certain dependencies
 * in the background rather than during execution of an application process
 * or interrupt service routine. To realize this, we append dependency
 * structures corresponding to such tasks to a "workitem" queue. In a soft
 * updates implementation, most pending workitems should not wait for more
 * than a couple of seconds, so the filesystem syncer process awakens once
 * per second to process the items on the queue.
 */

/* LIST_HEAD(workhead, worklist);	-- declared in buf.h */

/*
 * Each request can be linked onto a work queue through its worklist structure.
 * To avoid the need for a pointer to the structure itself, this structure
 * MUST be declared FIRST in each type in which it appears! If more than one
 * worklist is needed in the structure, then a wk_data field must be added
 * and the macros below changed to use it.
 */
struct worklist {
	LIST_ENTRY(worklist)	wk_list;	/* list of work requests */
	struct mount		*wk_mp;		/* Mount we live in */
	unsigned int		wk_type:8,	/* type of request */
				wk_state:24;	/* state flags */
};
#define WK_DATA(wk) ((void *)(wk))
#define WK_PAGEDEP(wk) ((struct pagedep *)(wk))
#define WK_INODEDEP(wk) ((struct inodedep *)(wk))
#define WK_BMSAFEMAP(wk) ((struct bmsafemap *)(wk))
#define	WK_NEWBLK(wk)  ((struct newblk *)(wk))
#define WK_ALLOCDIRECT(wk) ((struct allocdirect *)(wk))
#define WK_INDIRDEP(wk) ((struct indirdep *)(wk))
#define WK_ALLOCINDIR(wk) ((struct allocindir *)(wk))
#define WK_FREEFRAG(wk) ((struct freefrag *)(wk))
#define WK_FREEBLKS(wk) ((struct freeblks *)(wk))
#define WK_FREEWORK(wk) ((struct freework *)(wk))
#define WK_FREEFILE(wk) ((struct freefile *)(wk))
#define WK_DIRADD(wk) ((struct diradd *)(wk))
#define WK_MKDIR(wk) ((struct mkdir *)(wk))
#define WK_DIRREM(wk) ((struct dirrem *)(wk))
#define WK_NEWDIRBLK(wk) ((struct newdirblk *)(wk))
#define	WK_JADDREF(wk) ((struct jaddref *)(wk))
#define	WK_JREMREF(wk) ((struct jremref *)(wk))
#define	WK_JMVREF(wk) ((struct jmvref *)(wk))
#define	WK_JSEGDEP(wk) ((struct jsegdep *)(wk))
#define	WK_JSEG(wk) ((struct jseg *)(wk))
#define	WK_JNEWBLK(wk) ((struct jnewblk *)(wk))
#define	WK_JFREEBLK(wk) ((struct jfreeblk *)(wk))
#define	WK_FREEDEP(wk) ((struct freedep *)(wk))
#define	WK_JFREEFRAG(wk) ((struct jfreefrag *)(wk))
#define	WK_SBDEP(wk) ((struct sbdep *)(wk))
#define	WK_JTRUNC(wk) ((struct jtrunc *)(wk))
#define	WK_JFSYNC(wk) ((struct jfsync *)(wk))

/*
 * Various types of lists
 */
LIST_HEAD(dirremhd, dirrem);
LIST_HEAD(diraddhd, diradd);
LIST_HEAD(newblkhd, newblk);
LIST_HEAD(inodedephd, inodedep);
LIST_HEAD(allocindirhd, allocindir);
LIST_HEAD(allocdirecthd, allocdirect);
TAILQ_HEAD(allocdirectlst, allocdirect);
LIST_HEAD(indirdephd, indirdep);
LIST_HEAD(jaddrefhd, jaddref);
LIST_HEAD(jremrefhd, jremref);
LIST_HEAD(jmvrefhd, jmvref);
LIST_HEAD(jnewblkhd, jnewblk);
LIST_HEAD(jblkdephd, jblkdep);
LIST_HEAD(freeworkhd, freework);
TAILQ_HEAD(freeworklst, freework);
TAILQ_HEAD(jseglst, jseg);
TAILQ_HEAD(inoreflst, inoref);
TAILQ_HEAD(freeblklst, freeblks);

/*
 * The "pagedep" structure tracks the various dependencies related to
 * a particular directory page. If a directory page has any dependencies,
 * it will have a pagedep linked to its associated buffer. The
 * pd_dirremhd list holds the list of dirrem requests which decrement
 * inode reference counts. These requests are processed after the
 * directory page with the corresponding zero'ed entries has been
 * written. The pd_diraddhd list maintains the list of diradd requests
 * which cannot be committed until their corresponding inode has been
 * written to disk. Because a directory may have many new entries
 * being created, several lists are maintained hashed on bits of the
 * offset of the entry into the directory page to keep the lists from
 * getting too long. Once a new directory entry has been cleared to
 * be written, it is moved to the pd_pendinghd list. After the new
 * entry has been written to disk it is removed from the pd_pendinghd
 * list, any removed operations are done, and the dependency structure
 * is freed.
 */
#define DAHASHSZ 5
#define DIRADDHASH(offset) (((offset) >> 2) % DAHASHSZ)
struct pagedep {
	struct	worklist pd_list;	/* page buffer */
#	define	pd_state pd_list.wk_state /* check for multiple I/O starts */
	LIST_ENTRY(pagedep) pd_hash;	/* hashed lookup */
	ino_t	pd_ino;			/* associated file */
	ufs_lbn_t pd_lbn;		/* block within file */
	struct	newdirblk *pd_newdirblk; /* associated newdirblk if NEWBLOCK */
	struct	dirremhd pd_dirremhd;	/* dirrem's waiting for page */
	struct	diraddhd pd_diraddhd[DAHASHSZ]; /* diradd dir entry updates */
	struct	diraddhd pd_pendinghd;	/* directory entries awaiting write */
	struct	jmvrefhd pd_jmvrefhd;	/* Dependent journal writes. */
};

/*
 * The "inodedep" structure tracks the set of dependencies associated
 * with an inode. One task that it must manage is delayed operations
 * (i.e., work requests that must be held until the inodedep's associated
 * inode has been written to disk). Getting an inode from its incore
 * state to the disk requires two steps to be taken by the filesystem
 * in this order: first the inode must be copied to its disk buffer by
 * the VOP_UPDATE operation; second the inode's buffer must be written
 * to disk. To ensure that both operations have happened in the required
 * order, the inodedep maintains two lists. Delayed operations are
 * placed on the id_inowait list. When the VOP_UPDATE is done, all
 * operations on the id_inowait list are moved to the id_bufwait list.
 * When the buffer is written, the items on the id_bufwait list can be
 * safely moved to the work queue to be processed. A second task of the
 * inodedep structure is to track the status of block allocation within
 * the inode.  Each block that is allocated is represented by an
 * "allocdirect" structure (see below). It is linked onto the id_newinoupdt
 * list until both its contents and its allocation in the cylinder
 * group map have been written to disk. Once these dependencies have been
 * satisfied, it is removed from the id_newinoupdt list and any followup
 * actions such as releasing the previous block or fragment are placed
 * on the id_inowait list. When an inode is updated (a VOP_UPDATE is
 * done), the "inodedep" structure is linked onto the buffer through
 * its worklist. Thus, it will be notified when the buffer is about
 * to be written and when it is done. At the update time, all the
 * elements on the id_newinoupdt list are moved to the id_inoupdt list
 * since those changes are now relevant to the copy of the inode in the
 * buffer. Also at update time, the tasks on the id_inowait list are
 * moved to the id_bufwait list so that they will be executed when
 * the updated inode has been written to disk. When the buffer containing
 * the inode is written to disk, any updates listed on the id_inoupdt
 * list are rolled back as they are not yet safe. Following the write,
 * the changes are once again rolled forward and any actions on the
 * id_bufwait list are processed (since those actions are now safe).
 * The entries on the id_inoupdt and id_newinoupdt lists must be kept
 * sorted by logical block number to speed the calculation of the size
 * of the rolled back inode (see explanation in initiate_write_inodeblock).
 * When a directory entry is created, it is represented by a diradd.
 * The diradd is added to the id_inowait list as it cannot be safely
 * written to disk until the inode that it represents is on disk. After
 * the inode is written, the id_bufwait list is processed and the diradd
 * entries are moved to the id_pendinghd list where they remain until
 * the directory block containing the name has been written to disk.
 * The purpose of keeping the entries on the id_pendinghd list is so that
 * the softdep_fsync function can find and push the inode's directory
 * name(s) as part of the fsync operation for that file.
 */
struct inodedep {
	struct	worklist id_list;	/* buffer holding inode block */
#	define	id_state id_list.wk_state /* inode dependency state */
	LIST_ENTRY(inodedep) id_hash;	/* hashed lookup */
	TAILQ_ENTRY(inodedep) id_unlinked;	/* Unlinked but ref'd inodes */
	struct	fs *id_fs;		/* associated filesystem */
	ino_t	id_ino;			/* dependent inode */
	nlink_t	id_nlinkdelta;		/* saved effective link count */
	nlink_t	id_savednlink;		/* Link saved during rollback */
	LIST_ENTRY(inodedep) id_deps;	/* bmsafemap's list of inodedep's */
	struct	bmsafemap *id_bmsafemap; /* related bmsafemap (if pending) */
	struct	diradd *id_mkdiradd;	/* diradd for a mkdir. */
	struct	inoreflst id_inoreflst;	/* Inode reference adjustments. */
	long	id_savedextsize;	/* ext size saved during rollback */
	off_t	id_savedsize;		/* file size saved during rollback */
	struct	dirremhd id_dirremhd;	/* Removals pending. */
	struct	workhead id_pendinghd;	/* entries awaiting directory write */
	struct	workhead id_bufwait;	/* operations after inode written */
	struct	workhead id_inowait;	/* operations waiting inode update */
	struct	allocdirectlst id_inoupdt; /* updates before inode written */
	struct	allocdirectlst id_newinoupdt; /* updates when inode written */
	struct	allocdirectlst id_extupdt; /* extdata updates pre-inode write */
	struct	allocdirectlst id_newextupdt; /* extdata updates at ino write */
	struct	freeblklst id_freeblklst; /* List of partial truncates. */
	union {
	struct	ufs1_dinode *idu_savedino1; /* saved ufs1_dinode contents */
	struct	ufs2_dinode *idu_savedino2; /* saved ufs2_dinode contents */
	} id_un;
};
#define id_savedino1 id_un.idu_savedino1
#define id_savedino2 id_un.idu_savedino2

/*
 * A "bmsafemap" structure maintains a list of dependency structures
 * that depend on the update of a particular cylinder group map.
 * It has lists for newblks, allocdirects, allocindirs, and inodedeps.
 * It is attached to the buffer of a cylinder group block when any of
 * these things are allocated from the cylinder group. It is freed
 * after the cylinder group map is written and the state of its
 * dependencies are updated with DEPCOMPLETE to indicate that it has
 * been processed.
 */
struct bmsafemap {
	struct	worklist sm_list;	/* cylgrp buffer */
#	define	sm_state sm_list.wk_state
	LIST_ENTRY(bmsafemap) sm_hash;	/* Hash links. */
	LIST_ENTRY(bmsafemap) sm_next;	/* Mount list. */
	int	sm_cg;
	struct	buf *sm_buf;		/* associated buffer */
	struct	allocdirecthd sm_allocdirecthd; /* allocdirect deps */
	struct	allocdirecthd sm_allocdirectwr; /* writing allocdirect deps */
	struct	allocindirhd sm_allocindirhd; /* allocindir deps */
	struct	allocindirhd sm_allocindirwr; /* writing allocindir deps */
	struct	inodedephd sm_inodedephd; /* inodedep deps */
	struct	inodedephd sm_inodedepwr; /* writing inodedep deps */
	struct	newblkhd sm_newblkhd;	/* newblk deps */
	struct	newblkhd sm_newblkwr;	/* writing newblk deps */
	struct	jaddrefhd sm_jaddrefhd;	/* Pending inode allocations. */
	struct	jnewblkhd sm_jnewblkhd;	/* Pending block allocations. */
	struct	workhead sm_freehd;	/* Freedep deps. */
	struct	workhead sm_freewr;	/* Written freedeps. */
};

/*
 * A "newblk" structure is attached to a bmsafemap structure when a block
 * or fragment is allocated from a cylinder group. Its state is set to
 * DEPCOMPLETE when its cylinder group map is written. It is converted to
 * an allocdirect or allocindir allocation once the allocator calls the
 * appropriate setup function. It will initially be linked onto a bmsafemap
 * list. Once converted it can be linked onto the lists described for
 * allocdirect or allocindir as described below.
 */
struct newblk {
	struct	worklist nb_list;	/* See comment above. */
#	define	nb_state nb_list.wk_state
	LIST_ENTRY(newblk) nb_hash;	/* Hashed lookup. */
	LIST_ENTRY(newblk) nb_deps;	/* Bmsafemap's list of newblks. */
	struct	jnewblk *nb_jnewblk;	/* New block journal entry. */
	struct	bmsafemap *nb_bmsafemap;/* Cylgrp dep (if pending). */
	struct	freefrag *nb_freefrag;	/* Fragment to be freed (if any). */
	struct	indirdephd nb_indirdeps; /* Children indirect blocks. */
	struct	workhead nb_newdirblk;	/* Dir block to notify when written. */
	struct	workhead nb_jwork;	/* Journal work pending. */
	ufs2_daddr_t	nb_newblkno;	/* New value of block pointer. */
};

/*
 * An "allocdirect" structure is attached to an "inodedep" when a new block
 * or fragment is allocated and pointed to by the inode described by
 * "inodedep". The worklist is linked to the buffer that holds the block.
 * When the block is first allocated, it is linked to the bmsafemap
 * structure associated with the buffer holding the cylinder group map
 * from which it was allocated. When the cylinder group map is written
 * to disk, ad_state has the DEPCOMPLETE flag set. When the block itself
 * is written, the COMPLETE flag is set. Once both the cylinder group map
 * and the data itself have been written, it is safe to write the inode
 * that claims the block. If there was a previous fragment that had been
 * allocated before the file was increased in size, the old fragment may
 * be freed once the inode claiming the new block is written to disk.
 * This ad_fragfree request is attached to the id_inowait list of the
 * associated inodedep (pointed to by ad_inodedep) for processing after
 * the inode is written. When a block is allocated to a directory, an
 * fsync of a file whose name is within that block must ensure not only
 * that the block containing the file name has been written, but also
 * that the on-disk inode references that block. When a new directory
 * block is created, we allocate a newdirblk structure which is linked
 * to the associated allocdirect (on its ad_newdirblk list). When the
 * allocdirect has been satisfied, the newdirblk structure is moved to
 * the inodedep id_bufwait list of its directory to await the inode
 * being written. When the inode is written, the directory entries are
 * fully committed and can be deleted from their pagedep->id_pendinghd
 * and inodedep->id_pendinghd lists.
 */
struct allocdirect {
	struct	newblk ad_block;	/* Common block logic */
#	define	ad_state ad_block.nb_list.wk_state /* block pointer state */
	TAILQ_ENTRY(allocdirect) ad_next; /* inodedep's list of allocdirect's */
	struct	inodedep *ad_inodedep;	/* associated inodedep */
	ufs2_daddr_t	ad_oldblkno;	/* old value of block pointer */
	int		ad_offset;	/* Pointer offset in parent. */
	long		ad_newsize;	/* size of new block */
	long		ad_oldsize;	/* size of old block */
};
#define	ad_newblkno	ad_block.nb_newblkno
#define	ad_freefrag	ad_block.nb_freefrag
#define	ad_newdirblk	ad_block.nb_newdirblk

/*
 * A single "indirdep" structure manages all allocation dependencies for
 * pointers in an indirect block. The up-to-date state of the indirect
 * block is stored in ir_savedata. The set of pointers that may be safely
 * written to the disk is stored in ir_safecopy. The state field is used
 * only to track whether the buffer is currently being written (in which
 * case it is not safe to update ir_safecopy). Ir_deplisthd contains the
 * list of allocindir structures, one for each block that needs to be
 * written to disk. Once the block and its bitmap allocation have been
 * written the safecopy can be updated to reflect the allocation and the
 * allocindir structure freed. If ir_state indicates that an I/O on the
 * indirect block is in progress when ir_safecopy is to be updated, the
 * update is deferred by placing the allocindir on the ir_donehd list.
 * When the I/O on the indirect block completes, the entries on the
 * ir_donehd list are processed by updating their corresponding ir_safecopy
 * pointers and then freeing the allocindir structure.
 */
struct indirdep {
	struct	worklist ir_list;	/* buffer holding indirect block */
#	define	ir_state ir_list.wk_state /* indirect block pointer state */
	LIST_ENTRY(indirdep) ir_next;	/* alloc{direct,indir} list */
	TAILQ_HEAD(, freework) ir_trunc;	/* List of truncations. */
	caddr_t	ir_saveddata;		/* buffer cache contents */
	struct	buf *ir_savebp;		/* buffer holding safe copy */
	struct	buf *ir_bp;		/* buffer holding live copy */
	struct	allocindirhd ir_completehd; /* waiting for indirdep complete */
	struct	allocindirhd ir_writehd; /* Waiting for the pointer write. */
	struct	allocindirhd ir_donehd;	/* done waiting to update safecopy */
	struct	allocindirhd ir_deplisthd; /* allocindir deps for this block */
	struct	freeblks *ir_freeblks;	/* Freeblks that frees this indir. */
};

/*
 * An "allocindir" structure is attached to an "indirdep" when a new block
 * is allocated and pointed to by the indirect block described by the
 * "indirdep". The worklist is linked to the buffer that holds the new block.
 * When the block is first allocated, it is linked to the bmsafemap
 * structure associated with the buffer holding the cylinder group map
 * from which it was allocated. When the cylinder group map is written
 * to disk, ai_state has the DEPCOMPLETE flag set. When the block itself
 * is written, the COMPLETE flag is set. Once both the cylinder group map
 * and the data itself have been written, it is safe to write the entry in
 * the indirect block that claims the block; the "allocindir" dependency
 * can then be freed as it is no longer applicable.
 */
struct allocindir {
	struct	newblk ai_block;	/* Common block area */
#	define	ai_state ai_block.nb_list.wk_state /* indirect pointer state */
	LIST_ENTRY(allocindir) ai_next;	/* indirdep's list of allocindir's */
	struct	indirdep *ai_indirdep;	/* address of associated indirdep */
	ufs2_daddr_t	ai_oldblkno;	/* old value of block pointer */
	ufs_lbn_t	ai_lbn;		/* Logical block number. */
	int		ai_offset;	/* Pointer offset in parent. */
};
#define	ai_newblkno	ai_block.nb_newblkno
#define	ai_freefrag	ai_block.nb_freefrag
#define	ai_newdirblk	ai_block.nb_newdirblk

/*
 * The allblk union is used to size the newblk structure on allocation so
 * that it may be any one of three types.
 */
union allblk {
	struct	allocindir ab_allocindir;
	struct	allocdirect ab_allocdirect;
	struct	newblk	ab_newblk;
};

/*
 * A "freefrag" structure is attached to an "inodedep" when a previously
 * allocated fragment is replaced with a larger fragment, rather than extended.
 * The "freefrag" structure is constructed and attached when the replacement
 * block is first allocated. It is processed after the inode claiming the
 * bigger block that replaces it has been written to disk.
 */
struct freefrag {
	struct	worklist ff_list;	/* id_inowait or delayed worklist */
#	define	ff_state ff_list.wk_state
	struct	worklist *ff_jdep;	/* Associated journal entry. */
	struct	workhead ff_jwork;	/* Journal work pending. */
	ufs2_daddr_t ff_blkno;		/* fragment physical block number */
	long	ff_fragsize;		/* size of fragment being deleted */
	ino_t	ff_inum;		/* owning inode number */
	enum	vtype ff_vtype;		/* owning inode's file type */
};

/*
 * A "freeblks" structure is attached to an "inodedep" when the
 * corresponding file's length is reduced to zero. It records all
 * the information needed to free the blocks of a file after its
 * zero'ed inode has been written to disk.  The actual work is done
 * by child freework structures which are responsible for individual
 * inode pointers while freeblks is responsible for retiring the
 * entire operation when it is complete and holding common members.
 */
struct freeblks {
	struct	worklist fb_list;	/* id_inowait or delayed worklist */
#	define	fb_state fb_list.wk_state /* inode and dirty block state */
	TAILQ_ENTRY(freeblks) fb_next;	/* List of inode truncates. */
	struct	jblkdephd fb_jblkdephd;	/* Journal entries pending */
	struct	workhead fb_freeworkhd;	/* Work items pending */
	struct	workhead fb_jwork;	/* Journal work pending */
	struct	vnode *fb_devvp;	/* filesystem device vnode */
#ifdef QUOTA
	struct	dquot *fb_quota[MAXQUOTAS]; /* quotas to be adjusted */
#endif
	uint64_t fb_modrev;		/* Inode revision at start of trunc. */
	off_t	fb_len;			/* Length we're truncating to. */
	ufs2_daddr_t fb_chkcnt;		/* Blocks released. */
	ino_t	fb_inum;		/* inode owner of blocks */
	enum	vtype fb_vtype;		/* inode owner's file type */
	uid_t	fb_uid;			/* uid of previous owner of blocks */
	int	fb_ref;			/* Children outstanding. */
	int	fb_cgwait;		/* cg writes outstanding. */
};

/*
 * A "freework" structure handles the release of a tree of blocks or a single
 * block.  Each indirect block in a tree is allocated its own freework
 * structure so that the indirect block may be freed only when all of its
 * children are freed.  In this way we enforce the rule that an allocated
 * block must have a valid path to a root that is journaled.  Each child
 * block acquires a reference and when the ref hits zero the parent ref
 * is decremented.  If there is no parent the freeblks ref is decremented.
 */
struct freework {
	struct	worklist fw_list;		/* Delayed worklist. */
#	define	fw_state fw_list.wk_state
	LIST_ENTRY(freework) fw_segs;		/* Seg list. */
	TAILQ_ENTRY(freework) fw_next;		/* Hash/Trunc list. */
	struct	jnewblk	 *fw_jnewblk;		/* Journal entry to cancel. */
	struct	freeblks *fw_freeblks;		/* Root of operation. */
	struct	freework *fw_parent;		/* Parent indirect. */
	struct	indirdep *fw_indir;		/* indirect block. */
	ufs2_daddr_t	 fw_blkno;		/* Our block #. */
	ufs_lbn_t	 fw_lbn;		/* Original lbn before free. */
	uint16_t	 fw_frags;		/* Number of frags. */
	uint16_t	 fw_ref;		/* Number of children out. */
	uint16_t	 fw_off;		/* Current working position. */
	uint16_t	 fw_start;		/* Start of partial truncate. */
};

/*
 * A "freedep" structure is allocated to track the completion of a bitmap
 * write for a freework.  One freedep may cover many freed blocks so long
 * as they reside in the same cylinder group.  When the cg is written
 * the freedep decrements the ref on the freework which may permit it
 * to be freed as well.
 */
struct freedep {
	struct	worklist fd_list;	/* Delayed worklist. */
	struct	freework *fd_freework;	/* Parent freework. */
};

/*
 * A "freefile" structure is attached to an inode when its
 * link count is reduced to zero. It marks the inode as free in
 * the cylinder group map after the zero'ed inode has been written
 * to disk and any associated blocks and fragments have been freed.
 */
struct freefile {
	struct	worklist fx_list;	/* id_inowait or delayed worklist */
	mode_t	fx_mode;		/* mode of inode */
	ino_t	fx_oldinum;		/* inum of the unlinked file */
	struct	vnode *fx_devvp;	/* filesystem device vnode */
	struct	workhead fx_jwork;	/* journal work pending. */
};

/*
 * A "diradd" structure is linked to an "inodedep" id_inowait list when a
 * new directory entry is allocated that references the inode described
 * by "inodedep". When the inode itself is written (either the initial
 * allocation for new inodes or with the increased link count for
 * existing inodes), the COMPLETE flag is set in da_state. If the entry
 * is for a newly allocated inode, the "inodedep" structure is associated
 * with a bmsafemap which prevents the inode from being written to disk
 * until the cylinder group has been updated. Thus the da_state COMPLETE
 * flag cannot be set until the inode bitmap dependency has been removed.
 * When creating a new file, it is safe to write the directory entry that
 * claims the inode once the referenced inode has been written. Since
 * writing the inode clears the bitmap dependencies, the DEPCOMPLETE flag
 * in the diradd can be set unconditionally when creating a file. When
 * creating a directory, there are two additional dependencies described by
 * mkdir structures (see their description below). When these dependencies
 * are resolved the DEPCOMPLETE flag is set in the diradd structure.
 * If there are multiple links created to the same inode, there will be
 * a separate diradd structure created for each link. The diradd is
 * linked onto the pg_diraddhd list of the pagedep for the directory
 * page that contains the entry. When a directory page is written,
 * the pg_diraddhd list is traversed to rollback any entries that are
 * not yet ready to be written to disk. If a directory entry is being
 * changed (by rename) rather than added, the DIRCHG flag is set and
 * the da_previous entry points to the entry that will be "removed"
 * once the new entry has been committed. During rollback, entries
 * with da_previous are replaced with the previous inode number rather
 * than zero.
 *
 * The overlaying of da_pagedep and da_previous is done to keep the
 * structure down. If a da_previous entry is present, the pointer to its
 * pagedep is available in the associated dirrem entry. If the DIRCHG flag
 * is set, the da_previous entry is valid; if not set the da_pagedep entry
 * is valid. The DIRCHG flag never changes; it is set when the structure
 * is created if appropriate and is never cleared.
 */
struct diradd {
	struct	worklist da_list;	/* id_inowait or id_pendinghd list */
#	define	da_state da_list.wk_state /* state of the new directory entry */
	LIST_ENTRY(diradd) da_pdlist;	/* pagedep holding directory block */
	doff_t	da_offset;		/* offset of new dir entry in dir blk */
	ino_t	da_newinum;		/* inode number for the new dir entry */
	union {
	struct	dirrem *dau_previous;	/* entry being replaced in dir change */
	struct	pagedep *dau_pagedep;	/* pagedep dependency for addition */
	} da_un;
	struct workhead da_jwork;	/* Journal work awaiting completion. */
};
#define da_previous da_un.dau_previous
#define da_pagedep da_un.dau_pagedep

/*
 * Two "mkdir" structures are needed to track the additional dependencies
 * associated with creating a new directory entry. Normally a directory
 * addition can be committed as soon as the newly referenced inode has been
 * written to disk with its increased link count. When a directory is
 * created there are two additional dependencies: writing the directory
 * data block containing the "." and ".." entries (MKDIR_BODY) and writing
 * the parent inode with the increased link count for ".." (MKDIR_PARENT).
 * These additional dependencies are tracked by two mkdir structures that
 * reference the associated "diradd" structure. When they have completed,
 * they set the DEPCOMPLETE flag on the diradd so that it knows that its
 * extra dependencies have been completed. The md_state field is used only
 * to identify which type of dependency the mkdir structure is tracking.
 * It is not used in the mainline code for any purpose other than consistency
 * checking. All the mkdir structures in the system are linked together on
 * a list. This list is needed so that a diradd can find its associated
 * mkdir structures and deallocate them if it is prematurely freed (as for
 * example if a mkdir is immediately followed by a rmdir of the same directory).
 * Here, the free of the diradd must traverse the list to find the associated
 * mkdir structures that reference it. The deletion would be faster if the
 * diradd structure were simply augmented to have two pointers that referenced
 * the associated mkdir's. However, this would increase the size of the diradd
 * structure to speed a very infrequent operation.
 */
struct mkdir {
	struct	worklist md_list;	/* id_inowait or buffer holding dir */
#	define	md_state md_list.wk_state /* type: MKDIR_PARENT or MKDIR_BODY */
	struct	diradd *md_diradd;	/* associated diradd */
	struct	jaddref *md_jaddref;	/* dependent jaddref. */
	struct	buf *md_buf;		/* MKDIR_BODY: buffer holding dir */
	LIST_ENTRY(mkdir) md_mkdirs;	/* list of all mkdirs */
};

/*
 * A "dirrem" structure describes an operation to decrement the link
 * count on an inode. The dirrem structure is attached to the pg_dirremhd
 * list of the pagedep for the directory page that contains the entry.
 * It is processed after the directory page with the deleted entry has
 * been written to disk.
 */
struct dirrem {
	struct	worklist dm_list;	/* delayed worklist */
#	define	dm_state dm_list.wk_state /* state of the old directory entry */
	LIST_ENTRY(dirrem) dm_next;	/* pagedep's list of dirrem's */
	LIST_ENTRY(dirrem) dm_inonext;	/* inodedep's list of dirrem's */
	struct	jremrefhd dm_jremrefhd;	/* Pending remove reference deps. */
	ino_t	dm_oldinum;		/* inum of the removed dir entry */
	doff_t	dm_offset;		/* offset of removed dir entry in blk */
	union {
	struct	pagedep *dmu_pagedep;	/* pagedep dependency for remove */
	ino_t	dmu_dirinum;		/* parent inode number (for rmdir) */
	} dm_un;
	struct workhead dm_jwork;	/* Journal work awaiting completion. */
};
#define dm_pagedep dm_un.dmu_pagedep
#define dm_dirinum dm_un.dmu_dirinum

/*
 * A "newdirblk" structure tracks the progress of a newly allocated
 * directory block from its creation until it is claimed by its on-disk
 * inode. When a block is allocated to a directory, an fsync of a file
 * whose name is within that block must ensure not only that the block
 * containing the file name has been written, but also that the on-disk
 * inode references that block. When a new directory block is created,
 * we allocate a newdirblk structure which is linked to the associated
 * allocdirect (on its ad_newdirblk list). When the allocdirect has been
 * satisfied, the newdirblk structure is moved to the inodedep id_bufwait
 * list of its directory to await the inode being written. When the inode
 * is written, the directory entries are fully committed and can be
 * deleted from their pagedep->id_pendinghd and inodedep->id_pendinghd
 * lists. Note that we could track directory blocks allocated to indirect
 * blocks using a similar scheme with the allocindir structures. Rather
 * than adding this level of complexity, we simply write those newly
 * allocated indirect blocks synchronously as such allocations are rare.
 * In the case of a new directory the . and .. links are tracked with
 * a mkdir rather than a pagedep.  In this case we track the mkdir
 * so it can be released when it is written.  A workhead is used
 * to simplify canceling a mkdir that is removed by a subsequent dirrem.
 */
struct newdirblk {
	struct	worklist db_list;	/* id_inowait or pg_newdirblk */
#	define	db_state db_list.wk_state
	struct	pagedep *db_pagedep;	/* associated pagedep */
	struct	workhead db_mkdir;
};

/*
 * The inoref structure holds the elements common to jaddref and jremref
 * so they may easily be queued in-order on the inodedep.
 */
struct inoref {
	struct	worklist if_list;	/* Journal pending or jseg entries. */
#	define	if_state if_list.wk_state
	TAILQ_ENTRY(inoref) if_deps;	/* Links for inodedep. */
	struct	jsegdep	*if_jsegdep;	/* Will track our journal record. */
	off_t		if_diroff;	/* Directory offset. */
	ino_t		if_ino;		/* Inode number. */
	ino_t		if_parent;	/* Parent inode number. */
	nlink_t		if_nlink;	/* nlink before addition. */
	uint16_t	if_mode;	/* File mode, needed for IFMT. */
};

/*
 * A "jaddref" structure tracks a new reference (link count) on an inode
 * and prevents the link count increase and bitmap allocation until a
 * journal entry can be written.  Once the journal entry is written,
 * the inode is put on the pendinghd of the bmsafemap and a diradd or
 * mkdir entry is placed on the bufwait list of the inode.  The DEPCOMPLETE
 * flag is used to indicate that all of the required information for writing
 * the journal entry is present.  MKDIR_BODY and MKDIR_PARENT are used to
 * differentiate . and .. links from regular file names.  NEWBLOCK indicates
 * a bitmap is still pending.  If a new reference is canceled by a delete
 * prior to writing the journal the jaddref write is canceled and the
 * structure persists to prevent any disk-visible changes until it is
 * ultimately released when the file is freed or the link is dropped again.
 */
struct jaddref {
	struct	inoref	ja_ref;		/* see inoref above. */
#	define	ja_list	ja_ref.if_list	/* Jrnl pending, id_inowait, dm_jwork.*/
#	define	ja_state ja_ref.if_list.wk_state
	LIST_ENTRY(jaddref) ja_bmdeps;	/* Links for bmsafemap. */
	union {
		struct	diradd	*jau_diradd;	/* Pending diradd. */
		struct	mkdir	*jau_mkdir;	/* MKDIR_{PARENT,BODY} */
	} ja_un;
};
#define	ja_diradd	ja_un.jau_diradd
#define	ja_mkdir	ja_un.jau_mkdir
#define	ja_diroff	ja_ref.if_diroff
#define	ja_ino		ja_ref.if_ino
#define	ja_parent	ja_ref.if_parent
#define	ja_mode		ja_ref.if_mode

/*
 * A "jremref" structure tracks a removed reference (unlink) on an
 * inode and prevents the directory remove from proceeding until the
 * journal entry is written.  Once the journal has been written the remove
 * may proceed as normal.
 */
struct jremref {
	struct	inoref	jr_ref;		/* see inoref above. */
#	define	jr_list	jr_ref.if_list	/* Linked to softdep_journal_pending. */
#	define	jr_state jr_ref.if_list.wk_state
	LIST_ENTRY(jremref) jr_deps;	/* Links for dirrem. */
	struct	dirrem	*jr_dirrem;	/* Back pointer to dirrem. */
};

/*
 * A "jmvref" structure tracks a name relocations within the same
 * directory block that occur as a result of directory compaction.
 * It prevents the updated directory entry from being written to disk
 * until the journal entry is written. Once the journal has been
 * written the compacted directory may be written to disk.
 */
struct jmvref {
	struct	worklist jm_list;	/* Linked to softdep_journal_pending. */
	LIST_ENTRY(jmvref) jm_deps;	/* Jmvref on pagedep. */
	struct pagedep	*jm_pagedep;	/* Back pointer to pagedep. */
	ino_t		jm_parent;	/* Containing directory inode number. */
	ino_t		jm_ino;		/* Inode number of our entry. */
	off_t		jm_oldoff;	/* Our old offset in directory. */
	off_t		jm_newoff;	/* Our new offset in directory. */
};

/*
 * A "jnewblk" structure tracks a newly allocated block or fragment and
 * prevents the direct or indirect block pointer as well as the cg bitmap
 * from being written until it is logged.  After it is logged the jsegdep
 * is attached to the allocdirect or allocindir until the operation is
 * completed or reverted.  If the operation is reverted prior to the journal
 * write the jnewblk structure is maintained to prevent the bitmaps from
 * reaching the disk.  Ultimately the jnewblk structure will be passed
 * to the free routine as the in memory cg is modified back to the free
 * state at which time it can be released. It may be held on any of the
 * fx_jwork, fw_jwork, fb_jwork, ff_jwork, nb_jwork, or ir_jwork lists.
 */
struct jnewblk {
	struct	worklist jn_list;	/* See lists above. */
#	define	jn_state jn_list.wk_state
	struct	jsegdep	*jn_jsegdep;	/* Will track our journal record. */
	LIST_ENTRY(jnewblk) jn_deps;	/* Jnewblks on sm_jnewblkhd. */
	struct	worklist *jn_dep;	/* Dependency to ref completed seg. */
	ufs_lbn_t	jn_lbn;		/* Lbn to which allocated. */
	ufs2_daddr_t	jn_blkno;	/* Blkno allocated */
	ino_t		jn_ino;		/* Ino to which allocated. */
	int		jn_oldfrags;	/* Previous fragments when extended. */
	int		jn_frags;	/* Number of fragments. */
};

/*
 * A "jblkdep" structure tracks jfreeblk and jtrunc records attached to a
 * freeblks structure.
 */
struct jblkdep {
	struct	worklist jb_list;	/* For softdep journal pending. */
	struct	jsegdep *jb_jsegdep;	/* Reference to the jseg. */
	struct	freeblks *jb_freeblks;	/* Back pointer to freeblks. */
	LIST_ENTRY(jblkdep) jb_deps;	/* Dep list on freeblks. */

};

/*
 * A "jfreeblk" structure tracks the journal write for freeing a block
 * or tree of blocks.  The block pointer must not be cleared in the inode
 * or indirect prior to the jfreeblk being written to the journal.
 */
struct jfreeblk {
	struct	jblkdep	jf_dep;		/* freeblks linkage. */
	ufs_lbn_t	jf_lbn;		/* Lbn from which blocks freed. */
	ufs2_daddr_t	jf_blkno;	/* Blkno being freed. */
	ino_t		jf_ino;		/* Ino from which blocks freed. */
	int		jf_frags;	/* Number of frags being freed. */
};

/*
 * A "jfreefrag" tracks the freeing of a single block when a fragment is
 * extended or an indirect page is replaced.  It is not part of a larger
 * freeblks operation.
 */
struct jfreefrag {
	struct	worklist fr_list;	/* Linked to softdep_journal_pending. */
#	define	fr_state fr_list.wk_state
	struct	jsegdep	*fr_jsegdep;	/* Will track our journal record. */
	struct freefrag	*fr_freefrag;	/* Back pointer to freefrag. */
	ufs_lbn_t	fr_lbn;		/* Lbn from which frag freed. */
	ufs2_daddr_t	fr_blkno;	/* Blkno being freed. */
	ino_t		fr_ino;		/* Ino from which frag freed. */
	int		fr_frags;	/* Size of frag being freed. */
};

/*
 * A "jtrunc" journals the intent to truncate an inode's data or extent area.
 */
struct jtrunc {
	struct	jblkdep	jt_dep;		/* freeblks linkage. */
	off_t		jt_size;	/* Final file size. */
	int		jt_extsize;	/* Final extent size. */
	ino_t		jt_ino;		/* Ino being truncated. */
};

/*
 * A "jfsync" journals the completion of an fsync which invalidates earlier
 * jtrunc records in the journal.
 */
struct jfsync {
	struct worklist	jfs_list;	/* For softdep journal pending. */
	off_t		jfs_size;	/* Sync file size. */
	int		jfs_extsize;	/* Sync extent size. */
	ino_t		jfs_ino;	/* ino being synced. */
};

/*
 * A "jsegdep" structure tracks a single reference to a written journal
 * segment so the journal space can be reclaimed when all dependencies
 * have been written. It can hang off of id_inowait, dm_jwork, da_jwork,
 * nb_jwork, ff_jwork, or fb_jwork lists.
 */
struct jsegdep {
	struct	worklist jd_list;	/* See above for lists. */
#	define	jd_state jd_list.wk_state
	struct	jseg	*jd_seg;	/* Our journal record. */
};

/*
 * A "jseg" structure contains all of the journal records written in a
 * single disk write.  The jaddref and jremref structures are linked into
 * js_entries so thay may be completed when the write completes.  The
 * js_entries also include the write dependency structures: jmvref,
 * jnewblk, jfreeblk, jfreefrag, and jtrunc.  The js_refs field counts
 * the number of entries on the js_entries list. Thus there is a single
 * jseg entry to describe each journal write.
 */
struct jseg {
	struct	worklist js_list;	/* b_deps link for journal */
#	define	js_state js_list.wk_state
	struct	workhead js_entries;	/* Entries awaiting write */
	LIST_HEAD(, freework) js_indirs;/* List of indirects in this seg. */
	TAILQ_ENTRY(jseg) js_next;	/* List of all unfinished segments. */
	struct	jblocks *js_jblocks;	/* Back pointer to block/seg list */
	struct	buf *js_buf;		/* Buffer while unwritten */
	uint64_t js_seq;		/* Journal record sequence number. */
	uint64_t js_oldseq;		/* Oldest valid sequence number. */
	int	js_size;		/* Size of journal record in bytes. */
	int	js_cnt;			/* Total items allocated. */
	int	js_refs;		/* Count of js_entries items. */
};

/*
 * A 'sbdep' structure tracks the head of the free inode list and
 * superblock writes.  This makes sure the superblock is always pointing at
 * the first possible unlinked inode for the suj recovery process.  If a
 * block write completes and we discover a new head is available the buf
 * is dirtied and the dep is kept. See the description of the UNLINK*
 * flags above for more details.
 */
struct sbdep {
	struct	worklist sb_list;	/* b_dep linkage */
	struct	fs	*sb_fs;		/* Filesystem pointer within buf. */
	struct	ufsmount *sb_ump;	/* Our mount structure */
};

repo_name: veiledmerc/mira

license: mit


code:
/*-
 * Copyright (c) 1999-2001 Robert N. M. Watson
 * All rights reserved.
 *
 * This software was developed by Robert Watson for the TrustedBSD Project.
 *
 * 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 AUTHOR 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 AUTHOR 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.
 *
 * $FreeBSD: release/9.0.0/sys/ufs/ufs/acl.h 200796 2009-12-21 19:39:10Z trasz $
 */
/*
 * Developed by the TrustedBSD Project.
 * Support for POSIX.1e access control lists.
 */

#ifndef _UFS_UFS_ACL_H_
#define	_UFS_UFS_ACL_H_

#ifdef _KERNEL

int	ufs_getacl_nfs4_internal(struct vnode *vp, struct acl *aclp, struct thread *td);
int	ufs_setacl_nfs4_internal(struct vnode *vp, struct acl *aclp, struct thread *td);
void	ufs_sync_acl_from_inode(struct inode *ip, struct acl *acl);
void	ufs_sync_inode_from_acl(struct acl *acl, struct inode *ip);

int	ufs_getacl(struct vop_getacl_args *);
int	ufs_setacl(struct vop_setacl_args *);
int	ufs_aclcheck(struct vop_aclcheck_args *);

#endif /* !_KERNEL */

#endif /* !_UFS_UFS_ACL_H_ */


code:
/*-
 * Copyright (c) 2002 Networks Associates Technology, Inc.
 * All rights reserved.
 *
 * This software was developed for the FreeBSD Project by Marshall
 * Kirk McKusick and Network Associates Laboratories, the Security
 * Research Division of Network Associates, Inc. under DARPA/SPAWAR
 * contract N66001-01-C-8035 ("CBOSS"), as part of the DARPA CHATS
 * research program
 *
 * 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 AUTHOR 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 AUTHOR 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.
 *
 * Copyright (c) 1982, 1989, 1993
 *	The Regents of the University of California.  All rights reserved.
 * (c) UNIX System Laboratories, Inc.
 * All or some portions of this file are derived from material licensed
 * to the University of California by American Telephone and Telegraph
 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
 * the permission of UNIX System Laboratories, Inc.
 *
 * 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.
 * 3. The names of the authors may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
 *
 *	@(#)dinode.h	8.3 (Berkeley) 1/21/94
 * $FreeBSD: release/9.0.0/sys/ufs/ufs/dinode.h 207141 2010-04-24 07:05:35Z jeff $
 */

#ifndef _UFS_UFS_DINODE_H_
#define	_UFS_UFS_DINODE_H_

/*
 * The root inode is the root of the filesystem.  Inode 0 can't be used for
 * normal purposes and historically bad blocks were linked to inode 1, thus
 * the root inode is 2.  (Inode 1 is no longer used for this purpose, however
 * numerous dump tapes make this assumption, so we are stuck with it).
 */
#define	ROOTINO	((ino_t)2)

/*
 * The Whiteout inode# is a dummy non-zero inode number which will
 * never be allocated to a real file.  It is used as a place holder
 * in the directory entry which has been tagged as a DT_WHT entry.
 * See the comments about ROOTINO above.
 */
#define	WINO	((ino_t)1)

/*
 * The size of physical and logical block numbers and time fields in UFS.
 */
typedef	int32_t	ufs1_daddr_t;
typedef	int64_t	ufs2_daddr_t;
typedef int64_t ufs_lbn_t;
typedef int64_t ufs_time_t;

/* File permissions. */
#define	IEXEC		0000100		/* Executable. */
#define	IWRITE		0000200		/* Writeable. */
#define	IREAD		0000400		/* Readable. */
#define	ISVTX		0001000		/* Sticky bit. */
#define	ISGID		0002000		/* Set-gid. */
#define	ISUID		0004000		/* Set-uid. */

/* File types. */
#define	IFMT		0170000		/* Mask of file type. */
#define	IFIFO		0010000		/* Named pipe (fifo). */
#define	IFCHR		0020000		/* Character device. */
#define	IFDIR		0040000		/* Directory file. */
#define	IFBLK		0060000		/* Block device. */
#define	IFREG		0100000		/* Regular file. */
#define	IFLNK		0120000		/* Symbolic link. */
#define	IFSOCK		0140000		/* UNIX domain socket. */
#define	IFWHT		0160000		/* Whiteout. */

/*
 * A dinode contains all the meta-data associated with a UFS2 file.
 * This structure defines the on-disk format of a dinode. Since
 * this structure describes an on-disk structure, all its fields
 * are defined by types with precise widths.
 */

#define	NXADDR	2			/* External addresses in inode. */
#define	NDADDR	12			/* Direct addresses in inode. */
#define	NIADDR	3			/* Indirect addresses in inode. */

struct ufs2_dinode {
	u_int16_t	di_mode;	/*   0: IFMT, permissions; see below. */
	int16_t		di_nlink;	/*   2: File link count. */
	u_int32_t	di_uid;		/*   4: File owner. */
	u_int32_t	di_gid;		/*   8: File group. */
	u_int32_t	di_blksize;	/*  12: Inode blocksize. */
	u_int64_t	di_size;	/*  16: File byte count. */
	u_int64_t	di_blocks;	/*  24: Blocks actually held. */
	ufs_time_t	di_atime;	/*  32: Last access time. */
	ufs_time_t	di_mtime;	/*  40: Last modified time. */
	ufs_time_t	di_ctime;	/*  48: Last inode change time. */
	ufs_time_t	di_birthtime;	/*  56: Inode creation time. */
	int32_t		di_mtimensec;	/*  64: Last modified time. */
	int32_t		di_atimensec;	/*  68: Last access time. */
	int32_t		di_ctimensec;	/*  72: Last inode change time. */
	int32_t		di_birthnsec;	/*  76: Inode creation time. */
	int32_t		di_gen;		/*  80: Generation number. */
	u_int32_t	di_kernflags;	/*  84: Kernel flags. */
	u_int32_t	di_flags;	/*  88: Status flags (chflags). */
	int32_t		di_extsize;	/*  92: External attributes block. */
	ufs2_daddr_t	di_extb[NXADDR];/*  96: External attributes block. */
	ufs2_daddr_t	di_db[NDADDR];	/* 112: Direct disk blocks. */
	ufs2_daddr_t	di_ib[NIADDR];	/* 208: Indirect disk blocks. */
	u_int64_t	di_modrev;	/* 232: i_modrev for NFSv4 */
	ino_t		di_freelink;	/* 240: SUJ: Next unlinked inode. */
	uint32_t	di_spare[3];	/* 244: Reserved; currently unused */
};

/*
 * The di_db fields may be overlaid with other information for
 * file types that do not have associated disk storage. Block
 * and character devices overlay the first data block with their
 * dev_t value. Short symbolic links place their path in the
 * di_db area.
 */
#define	di_rdev di_db[0]

/*
 * A UFS1 dinode contains all the meta-data associated with a UFS1 file.
 * This structure defines the on-disk format of a UFS1 dinode. Since
 * this structure describes an on-disk structure, all its fields
 * are defined by types with precise widths.
 */
struct ufs1_dinode {
	u_int16_t	di_mode;	/*   0: IFMT, permissions; see below. */
	int16_t		di_nlink;	/*   2: File link count. */
	ino_t		di_freelink;	/*   4: SUJ: Next unlinked inode. */
	u_int64_t	di_size;	/*   8: File byte count. */
	int32_t		di_atime;	/*  16: Last access time. */
	int32_t		di_atimensec;	/*  20: Last access time. */
	int32_t		di_mtime;	/*  24: Last modified time. */
	int32_t		di_mtimensec;	/*  28: Last modified time. */
	int32_t		di_ctime;	/*  32: Last inode change time. */
	int32_t		di_ctimensec;	/*  36: Last inode change time. */
	ufs1_daddr_t	di_db[NDADDR];	/*  40: Direct disk blocks. */
	ufs1_daddr_t	di_ib[NIADDR];	/*  88: Indirect disk blocks. */
	u_int32_t	di_flags;	/* 100: Status flags (chflags). */
	int32_t		di_blocks;	/* 104: Blocks actually held. */
	int32_t		di_gen;		/* 108: Generation number. */
	u_int32_t	di_uid;		/* 112: File owner. */
	u_int32_t	di_gid;		/* 116: File group. */
	u_int64_t	di_modrev;	/* 120: i_modrev for NFSv4 */
};

#endif /* _UFS_UFS_DINODE_H_ */


code:
/*-
 * Copyright (c) 1982, 1986, 1989, 1993
 *	The Regents of the University of California.  All rights reserved.
 * (c) UNIX System Laboratories, Inc.
 * All or some portions of this file are derived from material licensed
 * to the University of California by American Telephone and Telegraph
 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
 * the permission of UNIX System Laboratories, Inc.
 *
 * 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.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
 *
 *	@(#)dir.h	8.2 (Berkeley) 1/21/94
 * $FreeBSD: release/9.0.0/sys/ufs/ufs/dir.h 171147 2007-07-02 01:31:43Z peter $
 */

#ifndef _UFS_UFS_DIR_H_
#define	_UFS_UFS_DIR_H_

/*
 * Theoretically, directories can be more than 2Gb in length, however, in
 * practice this seems unlikely. So, we define the type doff_t as a 32-bit
 * quantity to keep down the cost of doing lookup on a 32-bit machine.
 */
#define	doff_t		int32_t
#define MAXDIRSIZE	(0x7fffffff)

/*
 * A directory consists of some number of blocks of DIRBLKSIZ
 * bytes, where DIRBLKSIZ is chosen such that it can be transferred
 * to disk in a single atomic operation (e.g. 512 bytes on most machines).
 *
 * Each DIRBLKSIZ byte block contains some number of directory entry
 * structures, which are of variable length.  Each directory entry has
 * a struct direct at the front of it, containing its inode number,
 * the length of the entry, and the length of the name contained in
 * the entry.  These are followed by the name padded to a 4 byte boundary
 * with null bytes.  All names are guaranteed null terminated.
 * The maximum length of a name in a directory is MAXNAMLEN.
 *
 * The macro DIRSIZ(fmt, dp) gives the amount of space required to represent
 * a directory entry.  Free space in a directory is represented by
 * entries which have dp->d_reclen > DIRSIZ(fmt, dp).  All DIRBLKSIZ bytes
 * in a directory block are claimed by the directory entries.  This
 * usually results in the last entry in a directory having a large
 * dp->d_reclen.  When entries are deleted from a directory, the
 * space is returned to the previous entry in the same directory
 * block by increasing its dp->d_reclen.  If the first entry of
 * a directory block is free, then its dp->d_ino is set to 0.
 * Entries other than the first in a directory do not normally have
 * dp->d_ino set to 0.
 */
#define DIRBLKSIZ	DEV_BSIZE
#define	MAXNAMLEN	255

struct	direct {
	u_int32_t d_ino;		/* inode number of entry */
	u_int16_t d_reclen;		/* length of this record */
	u_int8_t  d_type; 		/* file type, see below */
	u_int8_t  d_namlen;		/* length of string in d_name */
	char	  d_name[MAXNAMLEN + 1];/* name with length <= MAXNAMLEN */
};

/*
 * File types
 */
#define	DT_UNKNOWN	 0
#define	DT_FIFO		 1
#define	DT_CHR		 2
#define	DT_DIR		 4
#define	DT_BLK		 6
#define	DT_REG		 8
#define	DT_LNK		10
#define	DT_SOCK		12
#define	DT_WHT		14

/*
 * Convert between stat structure types and directory types.
 */
#define	IFTODT(mode)	(((mode) & 0170000) >> 12)
#define	DTTOIF(dirtype)	((dirtype) << 12)

/*
 * The DIRSIZ macro gives the minimum record length which will hold
 * the directory entry.  This requires the amount of space in struct direct
 * without the d_name field, plus enough space for the name with a terminating
 * null byte (dp->d_namlen+1), rounded up to a 4 byte boundary.
 *
 *
 */
#define	DIRECTSIZ(namlen)						\
	(((uintptr_t)&((struct direct *)0)->d_name +			\
	  ((namlen)+1)*sizeof(((struct direct *)0)->d_name[0]) + 3) & ~3)
#if (BYTE_ORDER == LITTLE_ENDIAN)
#define DIRSIZ(oldfmt, dp) \
    ((oldfmt) ? DIRECTSIZ((dp)->d_type) : DIRECTSIZ((dp)->d_namlen))
#else
#define DIRSIZ(oldfmt, dp) \
    DIRECTSIZ((dp)->d_namlen)
#endif
#define OLDDIRFMT	1
#define NEWDIRFMT	0

/*
 * Template for manipulating directories.  Should use struct direct's,
 * but the name field is MAXNAMLEN - 1, and this just won't do.
 */
struct dirtemplate {
	u_int32_t	dot_ino;
	int16_t		dot_reclen;
	u_int8_t	dot_type;
	u_int8_t	dot_namlen;
	char		dot_name[4];	/* must be multiple of 4 */
	u_int32_t	dotdot_ino;
	int16_t		dotdot_reclen;
	u_int8_t	dotdot_type;
	u_int8_t	dotdot_namlen;
	char		dotdot_name[4];	/* ditto */
};

/*
 * This is the old format of directories, sanz type element.
 */
struct odirtemplate {
	u_int32_t	dot_ino;
	int16_t		dot_reclen;
	u_int16_t	dot_namlen;
	char		dot_name[4];	/* must be multiple of 4 */
	u_int32_t	dotdot_ino;
	int16_t		dotdot_reclen;
	u_int16_t	dotdot_namlen;
	char		dotdot_name[4];	/* ditto */
};
#endif /* !_DIR_H_ */


code:
/*-
 * Copyright (c) 2001 Ian Dowse.  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 AUTHOR 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 AUTHOR 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.
 *
 * $FreeBSD: release/9.0.0/sys/ufs/ufs/dirhash.h 219384 2011-03-07 18:33:29Z jhb $
 */

#ifndef _UFS_UFS_DIRHASH_H_
#define _UFS_UFS_DIRHASH_H_

#include <sys/_lock.h>
#include <sys/_sx.h>

/*
 * For fast operations on large directories, we maintain a hash
 * that maps the file name to the offset of the directory entry within
 * the directory file.
 *
 * The hashing uses a dumb spillover to the next free slot on
 * collisions, so we must keep the utilisation low to avoid
 * long linear searches. Deleted entries that are not the last
 * in a chain must be marked DIRHASH_DEL.
 *
 * We also maintain information about free space in each block
 * to speed up creations.
 */
#define DIRHASH_EMPTY	(-1)	/* entry unused */
#define DIRHASH_DEL	(-2)	/* deleted entry; may be part of chain */

#define DIRALIGN	4
#define DH_NFSTATS	(DIRECTSIZ(MAXNAMLEN + 1) / DIRALIGN)
				 /* max DIRALIGN words in a directory entry */

/*
 * Dirhash uses a score mechanism to achieve a hybrid between a
 * least-recently-used and a least-often-used algorithm for entry
 * recycling. The score is incremented when a directory is used, and
 * decremented when the directory is a candidate for recycling. When
 * the score reaches zero, the hash is recycled. Hashes are linked
 * together on a TAILQ list, and hashes with higher scores filter
 * towards the tail (most recently used) end of the list.
 *
 * New hash entries are given an inital score of DH_SCOREINIT and are
 * placed at the most-recently-used end of the list. This helps a lot
 * in the worst-case case scenario where every directory access is
 * to a directory that is not hashed (i.e. the working set of hash
 * candidates is much larger than the configured memry limit). In this
 * case it limits the number of hash builds to 1/DH_SCOREINIT of the
 * number of accesses.
 */
#define DH_SCOREINIT	8	/* initial dh_score when dirhash built */
#define DH_SCOREMAX	64	/* max dh_score value */

/*
 * The main hash table has 2 levels. It is an array of pointers to
 * blocks of DH_NBLKOFF offsets.
 */
#define DH_BLKOFFSHIFT	8
#define DH_NBLKOFF	(1 << DH_BLKOFFSHIFT)
#define DH_BLKOFFMASK	(DH_NBLKOFF - 1)

#define DH_ENTRY(dh, slot) \
    ((dh)->dh_hash[(slot) >> DH_BLKOFFSHIFT][(slot) & DH_BLKOFFMASK])

struct dirhash {
	struct sx dh_lock;	/* protects all fields except list & score */
	int	dh_refcount;

	doff_t	**dh_hash;	/* the hash array (2-level) */
	int	dh_narrays;	/* number of entries in dh_hash */
	int	dh_hlen;	/* total slots in the 2-level hash array */
	int	dh_hused;	/* entries in use */
	int	dh_memreq;	/* Memory used. */

	/* Free space statistics. XXX assumes DIRBLKSIZ is 512. */
	u_int8_t *dh_blkfree;	/* free DIRALIGN words in each dir block */
	int	dh_nblk;	/* size of dh_blkfree array */
	int	dh_dirblks;	/* number of DIRBLKSIZ blocks in dir */
	int	dh_firstfree[DH_NFSTATS + 1]; /* first blk with N words free */

	doff_t	dh_seqoff;	/* sequential access optimisation offset */

	int	dh_score;	/* access count for this dirhash */

	int	dh_onlist;	/* true if on the ufsdirhash_list chain */

	time_t	dh_lastused;	/* time the dirhash was last read or written*/

	/* Protected by ufsdirhash_mtx. */
	TAILQ_ENTRY(dirhash) dh_list;	/* chain of all dirhashes */
};

/*
 * Dirhash functions.
 */
void	ufsdirhash_init(void);
void	ufsdirhash_uninit(void);
int	ufsdirhash_build(struct inode *);
doff_t	ufsdirhash_findfree(struct inode *, int, int *);
doff_t	ufsdirhash_enduseful(struct inode *);
int	ufsdirhash_lookup(struct inode *, char *, int, doff_t *, struct buf **,
	    doff_t *);
void	ufsdirhash_newblk(struct inode *, doff_t);
void	ufsdirhash_add(struct inode *, struct direct *, doff_t);
void	ufsdirhash_remove(struct inode *, struct direct *, doff_t);
void	ufsdirhash_move(struct inode *, struct direct *, doff_t, doff_t);
void	ufsdirhash_dirtrunc(struct inode *, doff_t);
void	ufsdirhash_free(struct inode *);

void	ufsdirhash_checkblock(struct inode *, char *, doff_t);

#endif /* !_UFS_UFS_DIRHASH_H_ */