ufs_alloc.c

<B>Digital的Unix操作系统VAX 4.2源码</B>

#ifndef lint
static	char	*sccsid = "@(#)ufs_alloc.c	4.3	(ULTRIX)	2/28/91";
#endif lint

/************************************************************************
 *									*
 *			Copyright (c) 1986, 1988 by			*
 *		Digital Equipment Corporation, Maynard, MA		*
 *			All rights reserved.				*
 *									*
 *   This software is furnished under a license and may be used and	*
 *   copied  only  in accordance with the terms of such license and	*
 *   with the  inclusion  of  the  above  copyright  notice.   This	*
 *   software  or  any  other copies thereof may not be provided or	*
 *   otherwise made available to any other person.  No title to and	*
 *   ownership of the software is hereby transferred.			*
 *									*
 *   This software is  derived  from  software  received  from  the	*
 *   University    of   California,   Berkeley,   and   from   Bell	*
 *   Laboratories.  Use, duplication, or disclosure is  subject  to	*
 *   restrictions  under  license  agreements  with  University  of	*
 *   California and with AT&T.						*
 *									*
 *   The information in this software is subject to change  without	*
 *   notice  and should not be construed as a commitment by Digital	*
 *   Equipment Corporation.						*
 *									*
 *   Digital assumes no responsibility for the use  or  reliability	*
 *   of its software on equipment which is not supplied by Digital.	*
 *									*
 ************************************************************************/

/* ------------------------------------------------------------------------
 * Modification History:
 *
 * 27 Feb 91 -- chet
 *	Fix filesystem timestamping.
 *
 *  2 Jan 91 -- prs
 *	Enhanced blkpref() by adding an alogorithm which will
 *	attempt to make the slightly random writer block allocations 
 *	sequential. This is accomplished by looking for a block close
 *	to the one being allocated to determine block preference.
 *
 * 12 Jan 90 -- prs
 *	Removed gp had blocks message.
 *
 * 25 Jul 89 -- chet
 *	Fix syncronous filesystems and meet new bdwrite() interface.
 *
 * 25 Jul 88 -- jmartin
 *	Lock mfind/munhash operation with lk_cmap.
 *
 * 19 May 88 -- prs
 * 	SMP - Added ufs locks.
 *
 * 29 Jan 87 -- chet
 *	add new arg to bdwrite() calls
 *
 * 14 Jan 87 -- rr
 *	change of bwrite back to bdwrite
 *
 * 11 Sep 86 -- koehler
 *	change of panic string to reflect reality
 *
 * 06 Nov 84 -- jrs
 *	Add macro definitions and speedups from latest Berkeley stuff
 *
 * 19 Feb 84 -- jmcg
 *	There are three instances of buffers not being properly released.
 *	This results in system hangs after some delay.  The fix has been
 *	"blessed" by Kirk McKusick and verified by Robert Elz.
 *
 * 19 Feb 84 --jmcg
 *	Derived from 4.2BSD, labeled:
 *		ufs_alloc.c	6.2	83/09/28
 *
 * ------------------------------------------------------------------------
 */

#include "../h/param.h"
#include "../h/systm.h"
#include "../h/mount.h"
#include "../ufs/fs.h"
#include "../h/conf.h"
#include "../h/buf.h"
#include "../h/gnode_common.h"
#include "../ufs/ufs_inode.h"
#include "../h/gnode.h"
#include "../h/dir.h"
#include "../h/user.h"
#include "../h/quota.h"
#include "../h/kernel.h"
#include "../h/fs_types.h"
#include "../h/cmap.h"

extern u_long		hashalloc();
extern gno_t		ialloccg();
extern daddr_t		alloccg();
extern daddr_t		alloccgblk();
extern daddr_t		fragextend();
extern daddr_t		blkpref();
extern daddr_t		mapsearch();
extern int		inside[], around[];
extern unsigned char	*fragtbl[];

/*
 * Allocate a block in the file system.
 * 
 * The size of the requested block is given, which must be some
 * multiple of fs_fsize and <= fs_bsize.
 * A preference may be optionally specified. If a preference is given
 * the following hierarchy is used to allocate a block:
 *   1) allocate the requested block.
 *   2) allocate a rotationally optimal block in the same cylinder.
 *   3) allocate a block in the same cylinder group.
 *   4) quadradically rehash into other cylinder groups, until an
 *      available block is located.
 * If no block preference is given the following heirarchy is used
 * to allocate a block:
 *   1) allocate a block in the cylinder group that contains the
 *      gnode for the file.
 *   2) quadradically rehash into other cylinder groups, until an
 *      available block is located.
 */
struct buf *
alloc(gp, bpref, size)
	register struct gnode *gp;
	daddr_t bpref;
	register int size;
{
	register daddr_t bno;
	register struct fs *fs;
	register struct buf *bp;
	register int cg;

	fs = FS(gp);
	if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) {
		printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n",
		    gp->g_dev, fs->fs_bsize, size, fs->fs_fsmnt);
		panic("alloc: bad size");
	}
	if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0)
		goto nospace;
	if (u.u_uid != 0 && freespace(fs, fs->fs_minfree) <= 0)
		goto nospace;
#ifdef QUOTA
	u.u_error = chkdq(gp, (long)btodb(size), 0);
	if (u.u_error)
		return (NULL);
#endif
	if (bpref >= fs->fs_size)
		bpref = 0;
	if (bpref == 0)
		cg = itog(fs, gp->g_number);
	else
		cg = dtog(fs, bpref);
	bno = (daddr_t)hashalloc(gp, cg, (long)bpref, size,
		(u_long (*)())alloccg);
	if (bno <= 0)
		goto nospace;
	gp->g_blocks += btodb(size);
	G_TO_I(gp)->di_blocks = gp->g_blocks;
	gp->g_flag |= GUPD|GCHG;
	bp = getblk(gp->g_dev, fsbtodb(fs, bno), size, (struct gnode *) NULL);
	clrbuf(bp);
	return (bp);
nospace:
	fserr(gp->g_mp->m_fs_data->fd_path, "file system full");
	uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
	u.u_error = ENOSPC;
	return (NULL);
}

/*
 * Reallocate a fragment to a bigger size
 *
 * The number and size of the old block is given, and a preference
 * and new size is also specified. The allocator attempts to extend
 * the original block. Failing that, the regular block allocator is
 * invoked to get an appropriate block.
 */
struct buf *
realloccg(gp, bprev, bpref, osize, nsize)
	register struct gnode *gp;
	daddr_t bprev, bpref;
	int osize, nsize;
{
	register struct fs *fs;
	register struct buf *bp, *obp;
	int cg, request;
	register daddr_t bno;
	daddr_t bn;
	int i, count, s;
	extern struct cmap *mfind();
	
	fs = FS(gp);
	if ((unsigned)osize > fs->fs_bsize || fragoff(fs, osize) != 0 ||
	    (unsigned)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) {
		printf("dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n",
		    gp->g_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt);
		panic("realloccg: bad size");
	}
	if (u.u_uid != 0 && freespace(fs, fs->fs_minfree) <= 0)
		goto nospace;
	if (bprev == 0) {
		printf("dev = 0x%x, bsize = %d, bprev = %d, fs = %s\n",
		    gp->g_dev, fs->fs_bsize, bprev, fs->fs_fsmnt);
		panic("realloccg: bad bprev");
	}
#ifdef QUOTA
	u.u_error = chkdq(gp, (long)btodb(nsize - osize), 0);
	if (u.u_error)
		return (NULL);
#endif
	cg = dtog(fs, bprev);
	bno = fragextend(gp, cg, (long)bprev, osize, nsize);
	if (bno != 0) {
		do {
			bp = bread(gp->g_dev, fsbtodb(fs, bno), osize, 
				   (struct gnode *) NULL);
			if (bp->b_flags & B_ERROR) {
				brelse(bp);
				return (NULL);
			}
		} while (brealloc(bp, nsize) == 0);
		bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize);
		gp->g_blocks += btodb(nsize - osize);
		G_TO_I(gp)->di_blocks = gp->g_blocks;
		gp->g_flag |= GUPD|GCHG;
		bp->b_flags |= B_DONE;
		return (bp);
	}
	if (bpref >= fs->fs_size)
		bpref = 0;
	fs_lock(gp->g_mp);
	switch ((int)fs->fs_optim) {
	case FS_OPTSPACE:
		/*
		 * Allocate an exact sized fragment. Although this makes 
		 * best use of space, we will waste time relocating it if 
		 * the file continues to grow. If the fragmentation is
		 * less than half of the minimum free reserve, we choose
		 * to begin optimizing for time.
		 */
		request = nsize;
		if (fs->fs_minfree < 5 ||
		    fs->fs_cstotal.cs_nffree >
		    fs->fs_dsize * fs->fs_minfree / (2 * 100))
			break;
		fs->fs_optim = FS_OPTTIME;
		break;
	case FS_OPTTIME:
		/*
		 * At this point we have discovered a file that is trying
		 * to grow a small fragment to a larger fragment. To save
		 * time, we allocate a full sized block, then free the 
		 * unused portion. If the file continues to grow, the 
		 * `fragextend' call above will be able to grow it in place
		 * without further copying. If aberrant programs cause
		 * disk fragmentation to grow within 2% of the free reserve,
		 * we choose to begin optimizing for space.
		 */
		request = fs->fs_bsize;
		if (fs->fs_cstotal.cs_nffree <
		    fs->fs_dsize * (fs->fs_minfree - 2) / 100)
			break;
		fs->fs_optim = FS_OPTSPACE;
		break;
	default:
		printf("dev = 0x%x, optim = %d, fs = %s\n",
		    gp->g_dev, fs->fs_optim, fs->fs_fsmnt);
		panic("realloccg: bad optim");
		/* NOTREACHED */
	}
	fs_unlock(gp->g_mp);
	bno = (daddr_t)hashalloc(gp, cg, (long)bpref, request,
		(u_long (*)())alloccg);
	if (bno > 0) {
		obp = bread(gp->g_dev, fsbtodb(fs, bprev), osize, 
			    (struct gnode *) NULL);
		if (obp->b_flags & B_ERROR) {
			brelse(obp);
			return (NULL);
		}
		bn = fsbtodb(fs, bno);
		bp = getblk(gp->g_dev, bn, nsize, (struct gnode *) NULL);
		bcopy(obp->b_un.b_addr, bp->b_un.b_addr, (u_int)osize);
		count = howmany(osize, DEV_BSIZE);

		/*
		 * mfind/munhash can be a lengthy operation, so we
		 * lock/unlock through each circuit of the loop.
		 */
		s = splimp();
		for (i = 0; i < count; i += CLBYTES / DEV_BSIZE) {
			smp_lock(&lk_cmap, LK_RETRY);
			if (mfind(gp->g_dev, bn + i, gp))
				munhash(gp->g_dev, bn + i, gp);
			smp_unlock(&lk_cmap);
		}
		splx(s);

		bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize);
		if (obp->b_flags & B_DELWRI) {
			obp->b_flags &= ~B_DELWRI;
			u.u_ru.ru_oublock--;		/* delete charge */
		}
		brelse(obp);
		free(gp, bprev, (off_t)osize);
		if (nsize < request)
			free(gp, bno + numfrags(fs, nsize),
				(off_t)(request - nsize));
		gp->g_blocks += btodb(nsize - osize);
		G_TO_I(gp)->di_blocks = gp->g_blocks;
		gp->g_flag |= GUPD|GCHG;
		return (bp);
	}
nospace:
	/*
	 * no space available
	 */
	fserr(gp->g_mp->m_fs_data->fd_path, "file system full");
	uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
	u.u_error = ENOSPC;
	return (NULL);
}

/*
 * Allocate a gnode in the file system.
 * 
 * A preference may be optionally specified. If a preference is given
 * the following hierarchy is used to allocate an gnode:
 *   1) allocate the requested gnode.
 *   2) allocate an gnode in the same cylinder group.
 *   3) quadradically rehash into other cylinder groups, until an
 *      available gnode is located.
 * If no gnode preference is given the following heirarchy is used
 * to allocate an gnode:
 *   1) allocate an gnode in cylinder group 0.
 *   2) quadradically rehash into other cylinder groups, until an
 *      available gnode is located.
 */
struct gnode *
ufs_galloc(pgp, gpref, mode)
	register struct gnode *pgp;
	register gno_t gpref;
	int mode;
{
	register gno_t gno;
	register struct fs *fs;
	register struct gnode *gp;
	register int cg;
	
	fs = FS(pgp);
	if (fs->fs_cstotal.cs_nifree == 0)
		goto nognodes;
#ifdef QUOTA
	u.u_error = chkiq(pgp->g_dev, (struct gnode *)NULL, u.u_uid, 0);
	if (u.u_error)
		return (NULL);
#endif
	if (gpref >= fs->fs_ncg * fs->fs_ipg)
		gpref = 0;
	cg = itog(fs, gpref);
	gno = (gno_t)hashalloc(pgp, cg, (long)gpref, mode, ialloccg);
	if (gno == 0)
		goto nognodes;
	gp = gget(pgp->g_mp, gno, 0);
	if (gp == NULL) {
		ufs_gfree(pgp, gno, 0);
		return (NULL);
	}
	if (gp->g_mp->m_fstype != GT_ULTRIX) 
		panic("ufs_galloc: gget returned wrong fs type");
	if (gp->g_mode) {
		printf("mode = 0%o, gnum = %d, fs = %s\n",
		    gp->g_mode, gp->g_number, fs->fs_fsmnt);
		panic("ufs_galloc: dup alloc");
	}
	if (gp->g_blocks) {				/* XXX */
		gp->g_blocks = 0;
	}
	return (gp);
nognodes:
	fserr(pgp->g_mp->m_fs_data->fd_path, "out of gnodes");
	uprintf("\n%s: create/symlink failed, no gnodes free\n", fs->fs_fsmnt);
	u.u_error = ENOSPC;
	return (NULL);
}

/*
 * Find a cylinder to place a directory.
 *
 * The policy implemented by this algorithm is to select from
 * among those cylinder groups with above the average number of
 * free gnodes, the one with the smallest number of directories.
 */
gno_t
dirpref(fs)
	register struct fs *fs;
{
	register int cg, minndir, mincg, avgifree;

	avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg;
	minndir = fs->fs_ipg;
	mincg = 0;
	for (cg = 0; cg < fs->fs_ncg; cg++)
		if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
		    fs->fs_cs(fs, cg).cs_nifree >= avgifree) {
			mincg = cg;