usr/src/sys/ufs/lfs/lfs_inode.c

/*	lfs_inode.c	6.1	83/07/29	*/

#include "../h/param.h"
#include "../h/systm.h"
#include "../h/mount.h"
#include "../h/dir.h"
#include "../h/user.h"
#include "../h/inode.h"
#include "../h/fs.h"
#include "../h/conf.h"
#include "../h/buf.h"
#ifdef QUOTA
#include "../h/quota.h"
#endif
#include "../h/kernel.h"

#define	INOHSZ	63
#if	((INOHSZ&(INOHSZ-1)) == 0)
#define	INOHASH(dev,ino)	(((dev)+(ino))&(INOHSZ-1))
#else
#define	INOHASH(dev,ino)	(((unsigned)((dev)+(ino)))%INOHSZ)
#endif

union ihead {				/* inode LRU cache, Chris Maltby */
	union  ihead *ih_head[2];
	struct inode *ih_chain[2];
} ihead[INOHSZ];

struct inode *ifreeh, **ifreet;

/*
 * Initialize hash links for inodes
 * and build inode free list.
 */
ihinit()
{
	register int i;
	register struct inode *ip = inode;
	register union  ihead *ih = ihead;

	for (i = INOHSZ; --i >= 0; ih++) {
		ih->ih_head[0] = ih;
		ih->ih_head[1] = ih;
	}
	ifreeh = ip;
	ifreet = &ip->i_freef;
	ip->i_freeb = &ifreeh;
	ip->i_forw = ip;
	ip->i_back = ip;
	for (i = ninode; --i > 0; ) {
		++ip;
		ip->i_forw = ip;
		ip->i_back = ip;
		*ifreet = ip;
		ip->i_freeb = ifreet;
		ifreet = &ip->i_freef;
	}
	ip->i_freef = NULL;
}

#ifdef notdef
/*
 * Find an inode if it is incore.
 * This is the equivalent, for inodes,
 * of ``incore'' in bio.c or ``pfind'' in subr.c.
 */
struct inode *
ifind(dev, ino)
	dev_t dev;
	ino_t ino;
{
	register struct inode *ip;
	register union  ihead *ih;

	ih = &ihead[INOHASH(dev, ino)];
	for (ip = ih->ih_chain[0]; ip != (struct inode *)ih; ip = ip->i_forw)
		if (ino==ip->i_number && dev==ip->i_dev)
			return (ip);
	return ((struct inode *)0);
}
#endif notdef

/*
 * Look up an inode by device,inumber.
 * If it is in core (in the inode structure),
 * honor the locking protocol.
 * If it is not in core, read it in from the
 * specified device.
 * If the inode is mounted on, perform
 * the indicated indirection.
 * In all cases, a pointer to a locked
 * inode structure is returned.
 *
 * panic: no imt -- if the mounted file
 *	system is not in the mount table.
 *	"cannot happen"
 */
struct inode *
iget(dev, fs, ino)
	dev_t dev;
	register struct fs *fs;
	ino_t ino;
{
	register struct inode *ip;
	register union  ihead *ih;
	register struct mount *mp;
	register struct buf *bp;
	register struct dinode *dp;
	register struct inode *iq;

loop:
	if (getfs(dev) != fs)
		panic("iget: bad fs");
	ih = &ihead[INOHASH(dev, ino)];
	for (ip = ih->ih_chain[0]; ip != (struct inode *)ih; ip = ip->i_forw)
		if (ino == ip->i_number && dev == ip->i_dev) {
			if ((ip->i_flag&ILOCKED) != 0) {
				ip->i_flag |= IWANT;
				sleep((caddr_t)ip, PINOD);
				goto loop;
			}
			if ((ip->i_flag&IMOUNT) != 0) {
				for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++)
					if(mp->m_inodp == ip) {
						dev = mp->m_dev;
						fs = mp->m_bufp->b_un.b_fs;
						ino = ROOTINO;
						goto loop;
					}
				panic("no imt");
			}
			if (ip->i_count == 0) {		/* ino on free list */
				if (iq = ip->i_freef)
					iq->i_freeb = ip->i_freeb;
				else
					ifreet = ip->i_freeb;
				*ip->i_freeb = iq;
				ip->i_freef = NULL;
				ip->i_freeb = NULL;
			}
			ip->i_count++;
			ip->i_flag |= ILOCKED;
			return(ip);
		}

	if ((ip = ifreeh) == NULL) {
		tablefull("inode");
		u.u_error = ENFILE;
		return(NULL);
	}
	if (iq = ip->i_freef)
		iq->i_freeb = &ifreeh;
	ifreeh = iq;
	ip->i_freef = NULL;
	ip->i_freeb = NULL;
	/*
	 * Now to take inode off the hash chain it was on
	 * (initially, or after an iflush, it is on a "hash chain"
	 * consisting entirely of itself, and pointed to by no-one,
	 * but that doesn't matter), and put it on the chain for
	 * its new (ino, dev) pair
	 */
	remque(ip);
	insque(ip, ih);
#ifdef QUOTA
	dqrele(ip->i_dquot);
#endif
	ip->i_dev = dev;
	ip->i_fs = fs;
	ip->i_number = ino;
	ip->i_flag = ILOCKED;
	ip->i_count++;
	ip->i_lastr = 0;
	bp = bread(dev, fsbtodb(fs, itod(fs, ino)), (int)fs->fs_bsize);
	/*
	 * Check I/O errors
	 */
	if ((bp->b_flags&B_ERROR) != 0) {
		brelse(bp);
		/*
		 * the inode doesn't contain anything useful, so it would
		 * be misleading to leave it on its hash chain.
		 * 'iput' will take care of putting it back on the free list.
		 */
		remque(ip);
		ip->i_forw = ip;
		ip->i_back = ip;
		/*
		 * we also loose its inumber, just in case (as iput
		 * doesn't do that any more) - but as it isn't on its
		 * hash chain, I doubt if this is really necessary .. kre
		 * (probably the two methods are interchangable)
		 */
		ip->i_number = 0;
#ifdef QUOTA
		ip->i_dquot = NODQUOT;
#endif
		iput(ip);
		return(NULL);
	}
	dp = bp->b_un.b_dino;
	dp += itoo(fs, ino);
	ip->i_ic = dp->di_ic;
	brelse(bp);
#ifdef QUOTA
	if (ip->i_mode == 0)
		ip->i_dquot = NODQUOT;
	else
		ip->i_dquot = inoquota(ip);
#endif
	return (ip);
}

/*
 * Decrement reference count of
 * an inode structure.
 * On the last reference,
 * write the inode out and if necessary,
 * truncate and deallocate the file.
 */
iput(ip)
	register struct inode *ip;
{

	if ((ip->i_flag & ILOCKED) == 0)
		panic("iput");
	iunlock(ip);
	irele(ip);
}

irele(ip)
	register struct inode *ip;
{
	int mode;

	if (ip->i_count == 1) {
		ip->i_flag |= ILOCKED;
		if (ip->i_nlink <= 0) {
			itrunc(ip, (u_long)0);
			mode = ip->i_mode;
			ip->i_mode = 0;
			ip->i_rdev = 0;
			ip->i_flag |= IUPD|ICHG;
			ifree(ip, ip->i_number, mode);
#ifdef QUOTA
			(void) chkiq(ip->i_dev, ip, ip->i_uid, 0);
			dqrele(ip->i_dquot);
			ip->i_dquot = NODQUOT;
#endif
		}
		IUPDAT(ip, &time, &time, 0);
		iunlock(ip);
		ip->i_flag = 0;
		/*
		 * Put the inode on the end of the free list.
		 * Possibly in some cases it would be better to
		 * put the inode at the head of the free list,
		 * (eg: where i_mode == 0 || i_number == 0)
		 * but I will think about that later .. kre
		 * (i_number is rarely 0 - only after an i/o error in iget,
		 * where i_mode == 0, the inode will probably be wanted
		 * again soon for an ialloc, so possibly we should keep it)
		 */
		if (ifreeh) {
			*ifreet = ip;
			ip->i_freeb = ifreet;
		} else {
			ifreeh = ip;
			ip->i_freeb = &ifreeh;
		}
		ip->i_freef = NULL;
		ifreet = &ip->i_freef;
	}
	ip->i_count--;
}

/*
 * Check accessed and update flags on
 * an inode structure.
 * If any is on, update the inode
 * with the current time.
 * If waitfor is given, then must insure
 * i/o order so wait for write to complete.
 */
iupdat(ip, ta, tm, waitfor)
	register struct inode *ip;
	struct timeval *ta, *tm;
	int waitfor;
{
	register struct buf *bp;
	struct dinode *dp;
	register struct fs *fp;

	fp = ip->i_fs;
	if ((ip->i_flag & (IUPD|IACC|ICHG)) != 0) {
		if (fp->fs_ronly)
			return;
		bp = bread(ip->i_dev, fsbtodb(fp, itod(fp, ip->i_number)),
			(int)fp->fs_bsize);
		if (bp->b_flags & B_ERROR) {
			brelse(bp);
			return;
		}
		if (ip->i_flag&IACC)
			ip->i_atime = ta->tv_sec;
		if (ip->i_flag&IUPD)
			ip->i_mtime = tm->tv_sec;
		if (ip->i_flag&ICHG)
			ip->i_ctime = time.tv_sec;
		ip->i_flag &= ~(IUPD|IACC|ICHG);
		dp = bp->b_un.b_dino + itoo(fp, ip->i_number);
		dp->di_ic = ip->i_ic;
		if (waitfor)
			bwrite(bp);
		else
			bdwrite(bp);
	}
}

#define	SINGLE	0	/* index of single indirect block */
#define	DOUBLE	1	/* index of double indirect block */
#define	TRIPLE	2	/* index of triple indirect block */
/*
 * Truncate the inode ip to at most
 * length size.  Free affected disk
 * blocks -- the blocks of the file
 * are removed in reverse order.
 *
 * NB: triple indirect blocks are untested.
 */
itrunc(oip, length)
	struct inode *oip;
	u_long length;
{
	register i;
	register daddr_t lastblock;
	daddr_t bn, lastiblock[NIADDR];
	register struct fs *fs;
	register struct inode *ip;
	struct inode tip;
	long blocksreleased = 0, nblocks;
	long indirtrunc();
	int level;

	if (oip->i_size <= length) {
		oip->i_flag |= ICHG|IUPD;
		iupdat(oip, &time, &time, 1);
		return;
	}
	/*
	 * Calculate index into inode's block list of
	 * last direct and indirect blocks (if any)
	 * which we want to keep.  Lastblock is -1 when
	 * the file is truncated to 0.
	 */
	fs = oip->i_fs;
	lastblock = lblkno(fs, length + fs->fs_bsize - 1) - 1;
	lastiblock[SINGLE] = lastblock - NDADDR;
	lastiblock[DOUBLE] = lastiblock[SINGLE] - NINDIR(fs);
	lastiblock[TRIPLE] = lastiblock[DOUBLE] - NINDIR(fs) * NINDIR(fs);
	nblocks = btodb(fs->fs_bsize);
	/*
	 * Update size of file and block pointers
	 * on disk before we start freeing blocks.
	 * If we crash before free'ing blocks below,
	 * the blocks will be returned to the free list.
	 * lastiblock values are also normalized to -1
	 * for calls to indirtrunc below.
	 * (? fsck doesn't check validity of pointers in indirect blocks)
	 */
	tip = *oip;
	for (level = TRIPLE; level >= SINGLE; level--)
		if (lastiblock[level] < 0) {
			oip->i_ib[level] = 0;
			lastiblock[level] = -1;
		}
	for (i = NDADDR - 1; i > lastblock; i--)
		oip->i_db[i] = 0;
	oip->i_size = length;
	oip->i_flag |= ICHG|IUPD;
	iupdat(oip, &time, &time, 1);
	ip = &tip;

	/*
	 * Indirect blocks first.
	 */
	for (level = TRIPLE; level >= SINGLE; level--) {
		bn = ip->i_ib[level];
		if (bn != 0) {
			blocksreleased +=
			    indirtrunc(ip, bn, lastiblock[level], level);
			if (lastiblock[level] < 0) {
				ip->i_ib[level] = 0;
				free(ip, bn, (off_t)fs->fs_bsize);
				blocksreleased += nblocks;
			}
		}
		if (lastiblock[level] >= 0)
			goto done;
	}

	/*
	 * All whole direct blocks or frags.
	 */
	for (i = NDADDR - 1; i > lastblock; i--) {
		register int size;

		bn = ip->i_db[i];
		if (bn == 0)
			continue;
		ip->i_db[i] = 0;
		size = (off_t)blksize(fs, ip, i);
		free(ip, bn, size);
		blocksreleased += btodb(size);
	}
	if (lastblock < 0)
		goto done;

	/*
	 * Finally, look for a change in size of the
	 * last direct block; release any frags.
	 */
	bn = ip->i_db[lastblock];
	if (bn != 0) {
		int oldspace, newspace;

		/*
		 * Calculate amount of space we're giving
		 * back as old block size minus new block size.
		 */
		oldspace = blksize(fs, ip, lastblock);
		ip->i_size = length;
		newspace = blksize(fs, ip, lastblock);
		if (newspace == 0)
			panic("itrunc: newspace");
		if (oldspace - newspace > 0) {
			/*
			 * Block number of space to be free'd is
			 * the old block # plus the number of frags
			 * required for the storage we're keeping.
			 */
			bn += numfrags(fs, newspace);
			free(ip, bn, oldspace - newspace);
			blocksreleased += btodb(oldspace - newspace);
		}
	}
done:
/* BEGIN PARANOIA */
	for (level = SINGLE; level <= TRIPLE; level++)
		if (ip->i_ib[level] != oip->i_ib[level])
			panic("itrunc1");
	for (i = 0; i < NDADDR; i++)
		if (ip->i_db[i] != oip->i_db[i])
			panic("itrunc2");
/* END PARANOIA */
	oip->i_blocks -= blocksreleased;
	if (oip->i_blocks < 0)			/* sanity */
		oip->i_blocks = 0;
	oip->i_flag |= ICHG;
#ifdef QUOTA
	(void) chkdq(oip, -blocksreleased, 0);
#endif
}

/*
 * Release blocks associated with the inode ip and
 * stored in the indirect block bn.  Blocks are free'd
 * in LIFO order up to (but not including) lastbn.  If
 * level is greater than SINGLE, the block is an indirect
 * block and recursive calls to indirtrunc must be used to
 * cleanse other indirect blocks.
 *
 * NB: triple indirect blocks are untested.
 */
long
indirtrunc(ip, bn, lastbn, level)
	register struct inode *ip;
	daddr_t bn, lastbn;
	int level;
{
	register int i;
	struct buf *bp, *copy;
	register daddr_t *bap;
	register struct fs *fs = ip->i_fs;
	daddr_t nb, last;
	long factor;
	int blocksreleased = 0, nblocks;

	/*
	 * Calculate index in current block of last
	 * block to be kept.  -1 indicates the entire
	 * block so we need not calculate the index.
	 */
	factor = 1;
	for (i = SINGLE; i < level; i++)
		factor *= NINDIR(fs);
	last = lastbn;
	if (lastbn > 0)
		last /= factor;
	nblocks = btodb(fs->fs_bsize);
	/*
	 * Get buffer of block pointers, zero those
	 * entries corresponding to blocks to be free'd,
	 * and update on disk copy first.
	 */
	copy = geteblk((int)fs->fs_bsize);
	bp = bread(ip->i_dev, fsbtodb(fs, bn), (int)fs->fs_bsize);
	if (bp->b_flags&B_ERROR) {
		brelse(copy);
		brelse(bp);
		return (0);
	}
	bap = bp->b_un.b_daddr;
	bcopy((caddr_t)bap, (caddr_t)copy->b_un.b_daddr, (u_int)fs->fs_bsize);
	bzero((caddr_t)&bap[last + 1],
	  (u_int)(NINDIR(fs) - (last + 1)) * sizeof (daddr_t));
	bwrite(bp);
	bp = copy, bap = bp->b_un.b_daddr;

	/*
	 * Recursively free totally unused blocks.
	 */
	for (i = NINDIR(fs) - 1; i > last; i--) {
		nb = bap[i];
		if (nb == 0)
			continue;
		if (level > SINGLE)
			blocksreleased +=
			    indirtrunc(ip, nb, (daddr_t)-1, level - 1);
		free(ip, nb, (int)fs->fs_bsize);
		blocksreleased += nblocks;
	}

	/*
	 * Recursively free last partial block.
	 */
	if (level > SINGLE && lastbn >= 0) {
		last = lastbn % factor;
		nb = bap[i];
		if (nb != 0)
			blocksreleased += indirtrunc(ip, nb, last, level - 1);
	}
	brelse(bp);
	return (blocksreleased);
}

/*
 * remove any inodes in the inode cache belonging to dev
 *
 * There should not be any active ones, return error if any are found
 * (nb: this is a user error, not a system err)
 *
 * Also, count the references to dev by block devices - this really
 * has nothing to do with the object of the procedure, but as we have
 * to scan the inode table here anyway, we might as well get the
 * extra benefit.
 *
 * this is called from sumount()/sys3.c when dev is being unmounted
 */
#ifdef QUOTA
iflush(dev, iq)
	dev_t dev;
	struct inode *iq;
#else
iflush(dev)
	dev_t dev;
#endif
{
	register struct inode *ip;
	register open = 0;

	for (ip = inode; ip < inodeNINODE; ip++) {
#ifdef QUOTA
		if (ip != iq && ip->i_dev == dev)
#else
		if (ip->i_dev == dev)
#endif
			if (ip->i_count)
				return(-1);
			else {
				remque(ip);
				ip->i_forw = ip;
				ip->i_back = ip;
				/*
				 * as i_count == 0, the inode was on the free
				 * list already, just leave it there, it will
				 * fall off the bottom eventually. We could
				 * perhaps move it to the head of the free
				 * list, but as umounts are done so
				 * infrequently, we would gain very little,
				 * while making the code bigger.
				 */
#ifdef QUOTA
				dqrele(ip->i_dquot);
				ip->i_dquot = NODQUOT;
#endif
			}
		else if (ip->i_count && (ip->i_mode&IFMT)==IFBLK &&
		    ip->i_rdev == dev)
			open++;
	}
	return (open);
}

/*
 * Lock an inode. If its already locked, set the WANT bit and sleep.
 */
ilock(ip)
	register struct inode *ip;
{

	ILOCK(ip);
}

/*
 * Unlock an inode.  If WANT bit is on, wakeup.
 */
iunlock(ip)
	register struct inode *ip;
{

	IUNLOCK(ip);
}
Commit	Line	Data
	1	/* lfs_inode.c 6.1 83/07/29 */
	2
	3	#include "../h/param.h"
	4	#include "../h/systm.h"
	5	#include "../h/mount.h"
	6	#include "../h/dir.h"
	7	#include "../h/user.h"
	8	#include "../h/inode.h"
	9	#include "../h/fs.h"
	10	#include "../h/conf.h"
	11	#include "../h/buf.h"
	12	#ifdef QUOTA
	13	#include "../h/quota.h"
	14	#endif
	15	#include "../h/kernel.h"
	16
	17	#define INOHSZ 63
	18	#if ((INOHSZ&(INOHSZ-1)) == 0)
	19	#define INOHASH(dev,ino) (((dev)+(ino))&(INOHSZ-1))
	20	#else
	21	#define INOHASH(dev,ino) (((unsigned)((dev)+(ino)))%INOHSZ)
	22	#endif
	23
	24	union ihead { /* inode LRU cache, Chris Maltby */
	25	union ihead *ih_head[2];
	26	struct inode *ih_chain[2];
	27	} ihead[INOHSZ];
	28
	29	struct inode ifreeh, *ifreet;
	30
	31	/*
	32	* Initialize hash links for inodes
	33	* and build inode free list.
	34	*/
	35	ihinit()
	36	{
	37	register int i;
	38	register struct inode *ip = inode;
	39	register union ihead *ih = ihead;
	40
	41	for (i = INOHSZ; --i >= 0; ih++) {
	42	ih->ih_head[0] = ih;
	43	ih->ih_head[1] = ih;
	44	}
	45	ifreeh = ip;
	46	ifreet = &ip->i_freef;
	47	ip->i_freeb = &ifreeh;
	48	ip->i_forw = ip;
	49	ip->i_back = ip;
	50	for (i = ninode; --i > 0; ) {
	51	++ip;
	52	ip->i_forw = ip;
	53	ip->i_back = ip;
	54	*ifreet = ip;
	55	ip->i_freeb = ifreet;
	56	ifreet = &ip->i_freef;
	57	}
	58	ip->i_freef = NULL;
	59	}
	60
	61	#ifdef notdef
	62	/*
	63	* Find an inode if it is incore.
	64	* This is the equivalent, for inodes,
	65	* of ``incore'' in bio.c or ``pfind'' in subr.c.
	66	*/
	67	struct inode *
	68	ifind(dev, ino)
	69	dev_t dev;
	70	ino_t ino;
	71	{
	72	register struct inode *ip;
	73	register union ihead *ih;
	74
	75	ih = &ihead[INOHASH(dev, ino)];
	76	for (ip = ih->ih_chain[0]; ip != (struct inode *)ih; ip = ip->i_forw)
	77	if (ino==ip->i_number && dev==ip->i_dev)
	78	return (ip);
	79	return ((struct inode *)0);
	80	}
	81	#endif notdef
	82
	83	/*
	84	* Look up an inode by device,inumber.
	85	* If it is in core (in the inode structure),
	86	* honor the locking protocol.
	87	* If it is not in core, read it in from the
	88	* specified device.
	89	* If the inode is mounted on, perform
	90	* the indicated indirection.
	91	* In all cases, a pointer to a locked
	92	* inode structure is returned.
	93	*
	94	* panic: no imt -- if the mounted file
	95	* system is not in the mount table.
	96	* "cannot happen"
	97	*/
	98	struct inode *
	99	iget(dev, fs, ino)
	100	dev_t dev;
	101	register struct fs *fs;
	102	ino_t ino;
	103	{
	104	register struct inode *ip;
	105	register union ihead *ih;
	106	register struct mount *mp;
	107	register struct buf *bp;
	108	register struct dinode *dp;
	109	register struct inode *iq;
	110
	111	loop:
	112	if (getfs(dev) != fs)
	113	panic("iget: bad fs");
	114	ih = &ihead[INOHASH(dev, ino)];
	115	for (ip = ih->ih_chain[0]; ip != (struct inode *)ih; ip = ip->i_forw)
	116	if (ino == ip->i_number && dev == ip->i_dev) {
	117	if ((ip->i_flag&ILOCKED) != 0) {
	118	ip->i_flag \|= IWANT;
	119	sleep((caddr_t)ip, PINOD);
	120	goto loop;
	121	}
	122	if ((ip->i_flag&IMOUNT) != 0) {
	123	for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++)
	124	if(mp->m_inodp == ip) {
	125	dev = mp->m_dev;
	126	fs = mp->m_bufp->b_un.b_fs;
	127	ino = ROOTINO;
	128	goto loop;
	129	}
	130	panic("no imt");
	131	}
	132	if (ip->i_count == 0) { /* ino on free list */
	133	if (iq = ip->i_freef)
	134	iq->i_freeb = ip->i_freeb;
	135	else
	136	ifreet = ip->i_freeb;
	137	*ip->i_freeb = iq;
	138	ip->i_freef = NULL;
	139	ip->i_freeb = NULL;
	140	}
	141	ip->i_count++;
	142	ip->i_flag \|= ILOCKED;
	143	return(ip);
	144	}
	145
	146	if ((ip = ifreeh) == NULL) {
	147	tablefull("inode");
	148	u.u_error = ENFILE;
	149	return(NULL);
	150	}
	151	if (iq = ip->i_freef)
	152	iq->i_freeb = &ifreeh;
	153	ifreeh = iq;
	154	ip->i_freef = NULL;
	155	ip->i_freeb = NULL;
	156	/*
	157	* Now to take inode off the hash chain it was on
	158	* (initially, or after an iflush, it is on a "hash chain"
	159	* consisting entirely of itself, and pointed to by no-one,
	160	* but that doesn't matter), and put it on the chain for
	161	* its new (ino, dev) pair
	162	*/
	163	remque(ip);
	164	insque(ip, ih);
	165	#ifdef QUOTA
	166	dqrele(ip->i_dquot);
	167	#endif
	168	ip->i_dev = dev;
	169	ip->i_fs = fs;
	170	ip->i_number = ino;
	171	ip->i_flag = ILOCKED;
	172	ip->i_count++;
	173	ip->i_lastr = 0;
	174	bp = bread(dev, fsbtodb(fs, itod(fs, ino)), (int)fs->fs_bsize);
	175	/*
	176	* Check I/O errors
	177	*/
	178	if ((bp->b_flags&B_ERROR) != 0) {
	179	brelse(bp);
	180	/*
	181	* the inode doesn't contain anything useful, so it would
	182	* be misleading to leave it on its hash chain.
	183	* 'iput' will take care of putting it back on the free list.
	184	*/
	185	remque(ip);
	186	ip->i_forw = ip;
	187	ip->i_back = ip;
	188	/*
	189	* we also loose its inumber, just in case (as iput
	190	* doesn't do that any more) - but as it isn't on its
	191	* hash chain, I doubt if this is really necessary .. kre
	192	* (probably the two methods are interchangable)
	193	*/
	194	ip->i_number = 0;
	195	#ifdef QUOTA
	196	ip->i_dquot = NODQUOT;
	197	#endif
	198	iput(ip);
	199	return(NULL);
	200	}
	201	dp = bp->b_un.b_dino;
	202	dp += itoo(fs, ino);
	203	ip->i_ic = dp->di_ic;
	204	brelse(bp);
	205	#ifdef QUOTA
	206	if (ip->i_mode == 0)
	207	ip->i_dquot = NODQUOT;
	208	else
	209	ip->i_dquot = inoquota(ip);
	210	#endif
	211	return (ip);
	212	}
	213
	214	/*
	215	* Decrement reference count of
	216	* an inode structure.
	217	* On the last reference,
	218	* write the inode out and if necessary,
	219	* truncate and deallocate the file.
	220	*/
	221	iput(ip)
	222	register struct inode *ip;
	223	{
	224
	225	if ((ip->i_flag & ILOCKED) == 0)
	226	panic("iput");
	227	iunlock(ip);
	228	irele(ip);
	229	}
	230
	231	irele(ip)
	232	register struct inode *ip;
	233	{
	234	int mode;
	235
	236	if (ip->i_count == 1) {
	237	ip->i_flag \|= ILOCKED;
	238	if (ip->i_nlink <= 0) {
	239	itrunc(ip, (u_long)0);
	240	mode = ip->i_mode;
	241	ip->i_mode = 0;
	242	ip->i_rdev = 0;
	243	ip->i_flag \|= IUPD\|ICHG;
	244	ifree(ip, ip->i_number, mode);
	245	#ifdef QUOTA
	246	(void) chkiq(ip->i_dev, ip, ip->i_uid, 0);
	247	dqrele(ip->i_dquot);
	248	ip->i_dquot = NODQUOT;
	249	#endif
	250	}
	251	IUPDAT(ip, &time, &time, 0);
	252	iunlock(ip);
	253	ip->i_flag = 0;
	254	/*
	255	* Put the inode on the end of the free list.
	256	* Possibly in some cases it would be better to
	257	* put the inode at the head of the free list,
	258	* (eg: where i_mode == 0 \|\| i_number == 0)
	259	* but I will think about that later .. kre
	260	* (i_number is rarely 0 - only after an i/o error in iget,
	261	* where i_mode == 0, the inode will probably be wanted
	262	* again soon for an ialloc, so possibly we should keep it)
	263	*/
	264	if (ifreeh) {
	265	*ifreet = ip;
	266	ip->i_freeb = ifreet;
	267	} else {
	268	ifreeh = ip;
	269	ip->i_freeb = &ifreeh;
	270	}
	271	ip->i_freef = NULL;
	272	ifreet = &ip->i_freef;
	273	}
	274	ip->i_count--;
	275	}
	276
	277	/*
	278	* Check accessed and update flags on
	279	* an inode structure.
	280	* If any is on, update the inode
	281	* with the current time.
	282	* If waitfor is given, then must insure
	283	* i/o order so wait for write to complete.
	284	*/
	285	iupdat(ip, ta, tm, waitfor)
	286	register struct inode *ip;
	287	struct timeval ta, tm;
	288	int waitfor;
	289	{
	290	register struct buf *bp;
	291	struct dinode *dp;
	292	register struct fs *fp;
	293
	294	fp = ip->i_fs;
	295	if ((ip->i_flag & (IUPD\|IACC\|ICHG)) != 0) {
	296	if (fp->fs_ronly)
	297	return;
	298	bp = bread(ip->i_dev, fsbtodb(fp, itod(fp, ip->i_number)),
	299	(int)fp->fs_bsize);
	300	if (bp->b_flags & B_ERROR) {
	301	brelse(bp);
	302	return;
	303	}
	304	if (ip->i_flag&IACC)
	305	ip->i_atime = ta->tv_sec;
	306	if (ip->i_flag&IUPD)
	307	ip->i_mtime = tm->tv_sec;
	308	if (ip->i_flag&ICHG)
	309	ip->i_ctime = time.tv_sec;
	310	ip->i_flag &= ~(IUPD\|IACC\|ICHG);
	311	dp = bp->b_un.b_dino + itoo(fp, ip->i_number);
	312	dp->di_ic = ip->i_ic;
	313	if (waitfor)
	314	bwrite(bp);
	315	else
	316	bdwrite(bp);
	317	}
	318	}
	319
	320	#define SINGLE 0 /* index of single indirect block */
	321	#define DOUBLE 1 /* index of double indirect block */
	322	#define TRIPLE 2 /* index of triple indirect block */
	323	/*
	324	* Truncate the inode ip to at most
	325	* length size. Free affected disk
	326	* blocks -- the blocks of the file
	327	* are removed in reverse order.
	328	*
	329	* NB: triple indirect blocks are untested.
	330	*/
	331	itrunc(oip, length)
	332	struct inode *oip;
	333	u_long length;
	334	{
	335	register i;
	336	register daddr_t lastblock;
	337	daddr_t bn, lastiblock[NIADDR];
	338	register struct fs *fs;
	339	register struct inode *ip;
	340	struct inode tip;
	341	long blocksreleased = 0, nblocks;
	342	long indirtrunc();
	343	int level;
	344
	345	if (oip->i_size <= length) {
	346	oip->i_flag \|= ICHG\|IUPD;
	347	iupdat(oip, &time, &time, 1);
	348	return;
	349	}
	350	/*
	351	* Calculate index into inode's block list of
	352	* last direct and indirect blocks (if any)
	353	* which we want to keep. Lastblock is -1 when
	354	* the file is truncated to 0.
	355	*/
	356	fs = oip->i_fs;
	357	lastblock = lblkno(fs, length + fs->fs_bsize - 1) - 1;
	358	lastiblock[SINGLE] = lastblock - NDADDR;
	359	lastiblock[DOUBLE] = lastiblock[SINGLE] - NINDIR(fs);
	360	lastiblock[TRIPLE] = lastiblock[DOUBLE] - NINDIR(fs) * NINDIR(fs);
	361	nblocks = btodb(fs->fs_bsize);
	362	/*
	363	* Update size of file and block pointers
	364	* on disk before we start freeing blocks.
	365	* If we crash before free'ing blocks below,
	366	* the blocks will be returned to the free list.
	367	* lastiblock values are also normalized to -1
	368	* for calls to indirtrunc below.
	369	* (? fsck doesn't check validity of pointers in indirect blocks)
	370	*/
	371	tip = *oip;
	372	for (level = TRIPLE; level >= SINGLE; level--)
	373	if (lastiblock[level] < 0) {
	374	oip->i_ib[level] = 0;
	375	lastiblock[level] = -1;
	376	}
	377	for (i = NDADDR - 1; i > lastblock; i--)
	378	oip->i_db[i] = 0;
	379	oip->i_size = length;
	380	oip->i_flag \|= ICHG\|IUPD;
	381	iupdat(oip, &time, &time, 1);
	382	ip = &tip;
	383
	384	/*
	385	* Indirect blocks first.
	386	*/
	387	for (level = TRIPLE; level >= SINGLE; level--) {
	388	bn = ip->i_ib[level];
	389	if (bn != 0) {
	390	blocksreleased +=
	391	indirtrunc(ip, bn, lastiblock[level], level);
	392	if (lastiblock[level] < 0) {
	393	ip->i_ib[level] = 0;
	394	free(ip, bn, (off_t)fs->fs_bsize);
	395	blocksreleased += nblocks;
	396	}
	397	}
	398	if (lastiblock[level] >= 0)
	399	goto done;
	400	}
	401
	402	/*
	403	* All whole direct blocks or frags.
	404	*/
	405	for (i = NDADDR - 1; i > lastblock; i--) {
	406	register int size;
	407
	408	bn = ip->i_db[i];
	409	if (bn == 0)
	410	continue;
	411	ip->i_db[i] = 0;
	412	size = (off_t)blksize(fs, ip, i);
	413	free(ip, bn, size);
	414	blocksreleased += btodb(size);
	415	}
	416	if (lastblock < 0)
	417	goto done;
	418
	419	/*
	420	* Finally, look for a change in size of the
	421	* last direct block; release any frags.
	422	*/
	423	bn = ip->i_db[lastblock];
	424	if (bn != 0) {
	425	int oldspace, newspace;
	426
	427	/*
	428	* Calculate amount of space we're giving
	429	* back as old block size minus new block size.
	430	*/
	431	oldspace = blksize(fs, ip, lastblock);
	432	ip->i_size = length;
	433	newspace = blksize(fs, ip, lastblock);
	434	if (newspace == 0)
	435	panic("itrunc: newspace");
	436	if (oldspace - newspace > 0) {
	437	/*
	438	* Block number of space to be free'd is
	439	* the old block # plus the number of frags
	440	* required for the storage we're keeping.
	441	*/
	442	bn += numfrags(fs, newspace);
	443	free(ip, bn, oldspace - newspace);
	444	blocksreleased += btodb(oldspace - newspace);
	445	}
	446	}
	447	done:
	448	/* BEGIN PARANOIA */
	449	for (level = SINGLE; level <= TRIPLE; level++)
	450	if (ip->i_ib[level] != oip->i_ib[level])
	451	panic("itrunc1");
	452	for (i = 0; i < NDADDR; i++)
	453	if (ip->i_db[i] != oip->i_db[i])
	454	panic("itrunc2");
	455	/* END PARANOIA */
	456	oip->i_blocks -= blocksreleased;
	457	if (oip->i_blocks < 0) /* sanity */
	458	oip->i_blocks = 0;
	459	oip->i_flag \|= ICHG;
	460	#ifdef QUOTA
	461	(void) chkdq(oip, -blocksreleased, 0);
	462	#endif
	463	}
	464
	465	/*
	466	* Release blocks associated with the inode ip and
	467	* stored in the indirect block bn. Blocks are free'd
	468	* in LIFO order up to (but not including) lastbn. If
	469	* level is greater than SINGLE, the block is an indirect
	470	* block and recursive calls to indirtrunc must be used to
	471	* cleanse other indirect blocks.
	472	*
	473	* NB: triple indirect blocks are untested.
	474	*/
	475	long
	476	indirtrunc(ip, bn, lastbn, level)
	477	register struct inode *ip;
	478	daddr_t bn, lastbn;
	479	int level;
	480	{
	481	register int i;
	482	struct buf bp, copy;
	483	register daddr_t *bap;
	484	register struct fs *fs = ip->i_fs;
	485	daddr_t nb, last;
	486	long factor;
	487	int blocksreleased = 0, nblocks;
	488
	489	/*
	490	* Calculate index in current block of last
	491	* block to be kept. -1 indicates the entire
	492	* block so we need not calculate the index.
	493	*/
	494	factor = 1;
	495	for (i = SINGLE; i < level; i++)
	496	factor *= NINDIR(fs);
	497	last = lastbn;
	498	if (lastbn > 0)
	499	last /= factor;
	500	nblocks = btodb(fs->fs_bsize);
	501	/*
	502	* Get buffer of block pointers, zero those
	503	* entries corresponding to blocks to be free'd,
	504	* and update on disk copy first.
	505	*/
	506	copy = geteblk((int)fs->fs_bsize);
	507	bp = bread(ip->i_dev, fsbtodb(fs, bn), (int)fs->fs_bsize);
	508	if (bp->b_flags&B_ERROR) {
	509	brelse(copy);
	510	brelse(bp);
	511	return (0);
	512	}
	513	bap = bp->b_un.b_daddr;
	514	bcopy((caddr_t)bap, (caddr_t)copy->b_un.b_daddr, (u_int)fs->fs_bsize);
	515	bzero((caddr_t)&bap[last + 1],
	516	(u_int)(NINDIR(fs) - (last + 1)) * sizeof (daddr_t));
	517	bwrite(bp);
	518	bp = copy, bap = bp->b_un.b_daddr;
	519
	520	/*
	521	* Recursively free totally unused blocks.
	522	*/
	523	for (i = NINDIR(fs) - 1; i > last; i--) {
	524	nb = bap[i];
	525	if (nb == 0)
	526	continue;
	527	if (level > SINGLE)
	528	blocksreleased +=
	529	indirtrunc(ip, nb, (daddr_t)-1, level - 1);
	530	free(ip, nb, (int)fs->fs_bsize);
	531	blocksreleased += nblocks;
	532	}
	533
	534	/*
	535	* Recursively free last partial block.
	536	*/
	537	if (level > SINGLE && lastbn >= 0) {
	538	last = lastbn % factor;
	539	nb = bap[i];
	540	if (nb != 0)
	541	blocksreleased += indirtrunc(ip, nb, last, level - 1);
	542	}
	543	brelse(bp);
	544	return (blocksreleased);
	545	}
	546
	547	/*
	548	* remove any inodes in the inode cache belonging to dev
	549	*
	550	* There should not be any active ones, return error if any are found
	551	* (nb: this is a user error, not a system err)
	552	*
	553	* Also, count the references to dev by block devices - this really
	554	* has nothing to do with the object of the procedure, but as we have
	555	* to scan the inode table here anyway, we might as well get the
	556	* extra benefit.
	557	*
	558	* this is called from sumount()/sys3.c when dev is being unmounted
	559	*/
	560	#ifdef QUOTA
	561	iflush(dev, iq)
	562	dev_t dev;
	563	struct inode *iq;
	564	#else
	565	iflush(dev)
	566	dev_t dev;
	567	#endif
	568	{
	569	register struct inode *ip;
	570	register open = 0;
	571
	572	for (ip = inode; ip < inodeNINODE; ip++) {
	573	#ifdef QUOTA
	574	if (ip != iq && ip->i_dev == dev)
	575	#else
	576	if (ip->i_dev == dev)
	577	#endif
	578	if (ip->i_count)
	579	return(-1);
	580	else {
	581	remque(ip);
	582	ip->i_forw = ip;
	583	ip->i_back = ip;
	584	/*
	585	* as i_count == 0, the inode was on the free
	586	* list already, just leave it there, it will
	587	* fall off the bottom eventually. We could
	588	* perhaps move it to the head of the free
	589	* list, but as umounts are done so
	590	* infrequently, we would gain very little,
	591	* while making the code bigger.
	592	*/
	593	#ifdef QUOTA
	594	dqrele(ip->i_dquot);
	595	ip->i_dquot = NODQUOT;
	596	#endif
	597	}
	598	else if (ip->i_count && (ip->i_mode&IFMT)==IFBLK &&
	599	ip->i_rdev == dev)
	600	open++;
	601	}
	602	return (open);
	603	}
	604
	605	/*
	606	* Lock an inode. If its already locked, set the WANT bit and sleep.
	607	*/
	608	ilock(ip)
	609	register struct inode *ip;
	610	{
	611
	612	ILOCK(ip);
	613	}
	614
	615	/*
	616	* Unlock an inode. If WANT bit is on, wakeup.
	617	*/
	618	iunlock(ip)
	619	register struct inode *ip;
	620	{
	621
	622	IUNLOCK(ip);
	623	}