Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!uakari.primate.wisc.edu!uflorida!haven!mimsy!chris
From: chris@mimsy.umd.edu (Chris Torek)
Newsgroups: comp.unix.admin
Subject: Re: tunefs
Message-ID: <26333@mimsy.umd.edu>
Date: 2 Sep 90 14:33:18 GMT
References: <2697.26d4fadc@csc.anu.oz> <1592@shodha.dec.com> <25513@boulder.Colorado.EDU>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 71

In article <25513@boulder.Colorado.EDU> grunwald@foobar.colorado.edu
(Dirk Grunwald) writes:
>if I'm not going to be adding or deleting files often, does the [tunefs
>-m `minimum free space'] threshold really matter?

Free blocks (or lack thereof) matter only when a file needs a new block
or fragment.  UCB CSRG keep archives of particular releases of systems on
line sometimes; these go in file systems with a reserve of 0%, since they
are never modified after creation.

The code in question is in /sys/ufs/ufs_alloc.c (in recent BSDs).  Ideally
it never even uses the second approach; but in order to allocate the very
last block it will usually need the third.

/*
 * Implement the cylinder overflow algorithm.
 *
 * The policy implemented by this algorithm is:
 *   1) allocate the block in its requested cylinder group.
 *   2) quadradically rehash on the cylinder group number.
 *   3) brute force search for a free block.
 */
u_long
hashalloc(ip, cg, pref, size, allocator)
	struct inode *ip;
	int cg;
	long pref;
	int size;	/* size for data blocks, mode for inodes */
	u_long (*allocator)();
{
	register struct fs *fs;
	long result;
	int i, icg = cg;

	fs = ip->i_fs;
	/*
	 * 1: preferred cylinder group
	 */
	result = (*allocator)(ip, cg, pref, size);
	if (result)
		return (result);
	/*
	 * 2: quadratic rehash
	 */
	for (i = 1; i < fs->fs_ncg; i *= 2) {
		cg += i;
		if (cg >= fs->fs_ncg)
			cg -= fs->fs_ncg;
		result = (*allocator)(ip, cg, 0, size);
		if (result)
			return (result);
	}
	/*
	 * 3: brute force search
	 * Note that we start at i == 2, since 0 was checked initially,
	 * and 1 is always checked in the quadratic rehash.
	 */
	cg = (icg + 2) % fs->fs_ncg;
	for (i = 2; i < fs->fs_ncg; i++) {
		result = (*allocator)(ip, cg, 0, size);
		if (result)
			return (result);
		cg++;
		if (cg == fs->fs_ncg)
			cg = 0;
	}
	return (0);
}
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 405 2750)
Domain:	chris@cs.umd.edu	Path:	uunet!mimsy!chris