Replace FFS directory preference algorithm(dirpref) by new one.

It allocates directory inode in the same cylinder group as a parent
directory in. This speedup file/directory intensive operations on
a big file systems in times.

Don't forget to recompile fsck_ffs with updated fs.h or you will get
"VALUES IN SUPER BLOCK DISAGREE WITH THOSE IN FIRST ALTERNATE" at
the next boot. In any case you can ignore this error safely.

Requested by deraadt@

5 files changed, 186 insertions, 25 deletions

diff --git a/sbin/fsck_ffs/setup.c b/sbin/fsck_ffs/setup.c
index 75c04b77e7a..624efbe3dac 100644
--- a/sbin/fsck_ffs/setup.c
+++ b/sbin/fsck_ffs/setup.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: setup.c,v 1.8 2001/03/02 08:33:55 art Exp $	*/
+/*	$OpenBSD: setup.c,v 1.9 2001/04/06 20:43:31 gluk Exp $	*/
 /*	$NetBSD: setup.c,v 1.27 1996/09/27 22:45:19 christos Exp $	*/
 
 /*
@@ -38,7 +38,7 @@
 #if 0
 static char sccsid[] = "@(#)setup.c	8.5 (Berkeley) 11/23/94";
 #else
-static char rcsid[] = "$OpenBSD: setup.c,v 1.8 2001/03/02 08:33:55 art Exp $";
+static char rcsid[] = "$OpenBSD: setup.c,v 1.9 2001/04/06 20:43:31 gluk Exp $";
 #endif
 #endif /* not lint */
 
@@ -459,6 +459,9 @@ readsb(listerr)
 	memcpy(altsblock.fs_csp, sblock.fs_csp,
 		sizeof sblock.fs_csp);
 	altsblock.fs_maxcluster = sblock.fs_maxcluster;
+	altsblock.fs_contigdirs = sblock.fs_contigdirs;
+	altsblock.fs_avgfilesize = sblock.fs_avgfilesize;
+	altsblock.fs_avgfpdir = sblock.fs_avgfpdir;
 	memcpy(altsblock.fs_fsmnt, sblock.fs_fsmnt,
 		sizeof sblock.fs_fsmnt);
 	memcpy(altsblock.fs_sparecon, sblock.fs_sparecon,
diff --git a/sbin/tunefs/tunefs.c b/sbin/tunefs/tunefs.c
index 3a33a94ea25..b63a4eaa332 100644
--- a/sbin/tunefs/tunefs.c
+++ b/sbin/tunefs/tunefs.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: tunefs.c,v 1.9 2001/03/22 21:30:00 gluk Exp $	*/
+/*	$OpenBSD: tunefs.c,v 1.10 2001/04/06 20:43:31 gluk Exp $	*/
 /*	$NetBSD: tunefs.c,v 1.10 1995/03/18 15:01:31 cgd Exp $	*/
 
 /*
@@ -44,7 +44,7 @@ static char copyright[] =
 #if 0
 static char sccsid[] = "@(#)tunefs.c	8.2 (Berkeley) 4/19/94";
 #else
-static char rcsid[] = "$OpenBSD: tunefs.c,v 1.9 2001/03/22 21:30:00 gluk Exp $";
+static char rcsid[] = "$OpenBSD: tunefs.c,v 1.10 2001/04/06 20:43:31 gluk Exp $";
 #endif
 #endif /* not lint */
 
@@ -172,6 +172,20 @@ again:
 				sblock.fs_maxbpg = i;
 				continue;
 
+			case 'f':
+				name = "average file size";
+				if (argc < 1)
+					errx(10, "-f: missing %s", name);
+				argc--, argv++;
+				i = atoi(*argv);
+				if (i < 0)
+					errx(10, "%s must be >= 0 (was %s)",
+					    name, *argv);
+				warnx("%s changes from %d to %d",
+				    name, sblock.fs_avgfilesize, i);
+				sblock.fs_avgfilesize = i;
+				continue;
+
 			case 'm':
 				name = "minimum percentage of free space";
 				if (argc < 1)
@@ -191,6 +205,20 @@ again:
 					warnx(OPTWARN, "space", "<", MINFREE);
 				continue;
 
+			case 'n':
+				name = "expected number of files per directory";
+				if (argc < 1)
+					errx(10, "-n: missing %s", name);
+				argc--, argv++;
+				i = atoi(*argv);
+				if (i < 0)
+					errx(10, "%s must be >= 0 (was %s)",
+					    name, *argv);
+				warnx("%s changes from %d to %d",
+				    name, sblock.fs_avgfpdir, i);
+				sblock.fs_avgfpdir = i;
+				continue;
+
 			case 's':
 				name = "soft updates";
 				if (argc < 1)
@@ -263,7 +291,9 @@ usage()
 		"\t-a maximum contiguous blocks\n"
 		"\t-d rotational delay between contiguous blocks\n"
 		"\t-e maximum blocks per file in a cylinder group\n"
+		"\t-f expected average file size\n"
 		"\t-m minimum percentage of free space\n"
+		"\t-n expected number of files per directory\n"
 		"\t-o optimization preference (`space' or `time')\n"
 		"\t-p no change - just prints current tuneable settings\n"
 		"\t-s soft updates ('enable' or 'disable')\n",
diff --git a/sys/ufs/ffs/ffs_alloc.c b/sys/ufs/ffs/ffs_alloc.c
index 6484636e42f..c323def393f 100644
--- a/sys/ufs/ffs/ffs_alloc.c
+++ b/sys/ufs/ffs/ffs_alloc.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ffs_alloc.c,v 1.26 2001/03/27 10:27:49 art Exp $	*/
+/*	$OpenBSD: ffs_alloc.c,v 1.27 2001/04/06 20:43:31 gluk Exp $	*/
 /*	$NetBSD: ffs_alloc.c,v 1.11 1996/05/11 18:27:09 mycroft Exp $	*/
 
 /*
@@ -61,7 +61,7 @@ extern u_long nextgennumber;
 static daddr_t	ffs_alloccg __P((struct inode *, int, daddr_t, int));
 static daddr_t	ffs_alloccgblk __P((struct inode *, struct buf *, daddr_t));
 static daddr_t	ffs_clusteralloc __P((struct inode *, int, daddr_t, int));
-static ino_t	ffs_dirpref __P((struct fs *));
+static ino_t	ffs_dirpref __P((struct inode *));
 static daddr_t	ffs_fragextend __P((struct inode *, int, long, int, int));
 static void	ffs_fserr __P((struct fs *, u_int, char *));
 static u_long	ffs_hashalloc __P((struct inode *, int, long, int,
@@ -579,12 +579,24 @@ ffs_valloc(v)
 		goto noinodes;
 
 	if ((mode & IFMT) == IFDIR)
-		ipref = ffs_dirpref(fs);
+		ipref = ffs_dirpref(pip);
 	else
 		ipref = pip->i_number;
 	if (ipref >= fs->fs_ncg * fs->fs_ipg)
 		ipref = 0;
 	cg = ino_to_cg(fs, ipref);
+
+	/*
+	 * Track number of dirs created one after another
+	 * in a same cg without intervening by files.
+	 */
+	if ((mode & IFMT) == IFDIR) {
+		if (fs->fs_contigdirs[cg] < 255)
+			fs->fs_contigdirs[cg]++;
+	} else {
+		if (fs->fs_contigdirs[cg] > 0)
+			fs->fs_contigdirs[cg]--;
+	}
 	ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, ffs_nodealloccg);
 	if (ino == 0)
 		goto noinodes;
@@ -622,28 +634,126 @@ noinodes:
 }
 
 /*
- * Find a cylinder to place a directory.
+ * Find a cylinder group 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 inodes, the one with the smallest number of directories.
+ * The policy implemented by this algorithm is to allocate inode
+ * in the same cylinder group as a parent directory in, but also
+ * reserve space for file's data and inodes. Restrict number of
+ * directories which may be allocated one after another in a same
+ * cg without intervening by files.
+ * If we allocate a first level directory then force allocation
+ * in another cg.
  */
 static ino_t
-ffs_dirpref(fs)
-	register struct fs *fs;
+ffs_dirpref(pip)
+	struct inode *pip;
 {
-	int cg, minndir, mincg, avgifree;
+	register struct fs *fs;
+	int	cg, prefcg, dirsize, cgsize;
+	int	avgifree, avgbfree, avgndir, curdirsize;
+	int	minifree, minbfree, maxndir;
+	int	mincg, minndir;
+	int	maxcontigdirs;
+
+	fs = pip->i_fs;
 
 	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;
-			minndir = fs->fs_cs(fs, cg).cs_ndir;
+	avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
+	avgndir = fs->fs_cstotal.cs_ndir / fs->fs_ncg;
+#if 1
+
+	/*
+	 * Force allocation in another cg if creating a first level dir.
+	 */
+	if (ITOV(pip)->v_flag & VROOT) {
+		prefcg = arc4random() % fs->fs_ncg;
+		mincg = prefcg;
+		minndir = fs->fs_ipg;
+		for (cg = prefcg; cg < fs->fs_ncg; cg++)
+			if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
+			    fs->fs_cs(fs, cg).cs_nifree >= avgifree &&
+			    fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
+				mincg = cg;
+				minndir = fs->fs_cs(fs, cg).cs_ndir;
+			}
+		for (cg = 0; cg < prefcg; cg++)
+			if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
+			    fs->fs_cs(fs, cg).cs_nifree >= avgifree &&
+			    fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
+				mincg = cg;
+				minndir = fs->fs_cs(fs, cg).cs_ndir;
+			}
+		cg = mincg;
+		goto end;
+	} else
+		prefcg = ino_to_cg(fs, pip->i_number);
+#else
+	prefcg = ino_to_cg(fs, pip->i_number);
+#endif
+
+	/*
+	 * Count various limits which used for
+	 * optimal allocation of a directory inode.
+	 */
+#if 1
+	maxndir = min(avgndir + fs->fs_ipg / 16, fs->fs_ipg);
+	minifree = avgifree - fs->fs_ipg / 4;
+	if (minifree < 0)
+		minifree = 0;
+	minbfree = avgbfree - fs->fs_fpg / fs->fs_frag / 4;
+	if (minbfree < 0)
+		minbfree = 0;
+#else
+	maxndir = avgndir + (fs->fs_ipg - avgndir) / 16;
+	minifree = avgifree * 3 / 4;
+	minbfree = avgbfree * 3 / 4;
+#endif
+	cgsize = fs->fs_fsize * fs->fs_fpg;
+	dirsize = fs->fs_avgfilesize * fs->fs_avgfpdir;
+	if (dirsize <= 0)
+		dirsize = 16384 * 64;
+	curdirsize = avgndir ? (cgsize - avgbfree * fs->fs_bsize) / avgndir : 0;
+	if (dirsize < curdirsize)
+		dirsize = curdirsize;
+	maxcontigdirs = min(cgsize / dirsize, 255);
+	if (fs->fs_avgfpdir > 0)
+		maxcontigdirs = min(maxcontigdirs,
+				    fs->fs_ipg / fs->fs_avgfpdir);
+	if (maxcontigdirs == 0)
+		maxcontigdirs = 1;
+
+	/*
+	 * Limit number of dirs in one cg and reserve space for 
+	 * regular files, but only if we have no deficit in
+	 * inodes or space.
+	 */
+	for (cg = prefcg; cg < fs->fs_ncg; cg++)
+		if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
+		    fs->fs_cs(fs, cg).cs_nifree >= minifree &&
+	    	    fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
+			if (fs->fs_contigdirs[cg] < maxcontigdirs)
+				goto end;
+			else
+				continue;
+		}
+	for (cg = 0; cg < prefcg; cg++)
+		if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
+		    fs->fs_cs(fs, cg).cs_nifree >= minifree &&
+	    	    fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
+			if (fs->fs_contigdirs[cg] < maxcontigdirs)
+				goto end;
+			else
+				continue;
 		}
-	return ((ino_t)(fs->fs_ipg * mincg));
+	/* This work when we have deficit in space */
+	for (cg = prefcg; cg < fs->fs_ncg; cg++)
+		if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
+			goto end;
+	for (cg = 0; cg < prefcg; cg++)
+		if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
+			goto end;
+end:
+	return ((ino_t)(fs->fs_ipg * cg));
 }
 
 /*
diff --git a/sys/ufs/ffs/ffs_vfsops.c b/sys/ufs/ffs/ffs_vfsops.c
index 077b95c9adf..e62006043ad 100644
--- a/sys/ufs/ffs/ffs_vfsops.c
+++ b/sys/ufs/ffs/ffs_vfsops.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ffs_vfsops.c,v 1.35 2001/04/04 20:19:04 gluk Exp $	*/
+/*	$OpenBSD: ffs_vfsops.c,v 1.36 2001/04/06 20:43:31 gluk Exp $	*/
 /*	$NetBSD: ffs_vfsops.c,v 1.19 1996/02/09 22:22:26 christos Exp $	*/
 
 /*
@@ -194,6 +194,7 @@ ffs_mount(mp, path, data, ndp, p)
 				mp->mnt_flag &= ~MNT_SOFTDEP;
 			} else
 				error = ffs_flushfiles(mp, flags, p);
+			free(fs->fs_contigdirs, M_WAITOK);
 			ronly = 1;
 		}
 
@@ -282,6 +283,9 @@ ffs_mount(mp, path, data, ndp, p)
 				if (error)
 					goto error_1;
 			}
+			fs->fs_contigdirs=(u_int8_t*)malloc((u_long)fs->fs_ncg,
+							    M_UFSMNT, M_WAITOK);
+			bzero(fs->fs_contigdirs, fs->fs_ncg);
 
 			ronly = 0;
 		}
@@ -715,6 +719,14 @@ ffs_mountfs(devvp, mp, p)
 	devvp->v_specmountpoint = mp;
 	ffs_oldfscompat(fs);
 
+	if (ronly)
+		fs->fs_contigdirs = NULL;
+	else {
+		fs->fs_contigdirs = (u_int8_t*)malloc((u_long)fs->fs_ncg,
+						      M_UFSMNT, M_WAITOK);
+		bzero(fs->fs_contigdirs, fs->fs_ncg);
+	}
+
 	/*
 	 * Set FS local "last mounted on" information (NULL pad)
 	 */
@@ -743,6 +755,7 @@ ffs_mountfs(devvp, mp, p)
 		if ((fs->fs_flags & FS_DOSOFTDEP) &&
 		    (error = softdep_mount(devvp, mp, fs, cred)) != 0) {
 			free(base, M_UFSMNT);
+			free(fs->fs_contigdirs, M_UFSMNT);
 			goto out;
 		}
 		fs->fs_fmod = 1;
@@ -829,6 +842,7 @@ ffs_unmount(mp, mntflags, p)
 			fs->fs_clean = 0;
 			return (error);
 		}
+		free(fs->fs_contigdirs, M_UFSMNT);
 	}
 	ump->um_devvp->v_specmountpoint = NULL;
 
diff --git a/sys/ufs/ffs/fs.h b/sys/ufs/ffs/fs.h
index e280f92f256..683a87af728 100644
--- a/sys/ufs/ffs/fs.h
+++ b/sys/ufs/ffs/fs.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: fs.h,v 1.8 1998/11/29 00:45:30 art Exp $	*/
+/*	$OpenBSD: fs.h,v 1.9 2001/04/06 20:43:30 gluk Exp $	*/
 /*	$NetBSD: fs.h,v 1.6 1995/04/12 21:21:02 mycroft Exp $	*/
 
 /*
@@ -229,7 +229,11 @@ struct fs {
 	int32_t	 *fs_maxcluster;	/* max cluster in each cyl group */
 	int32_t	 fs_cpc;		/* cyl per cycle in postbl */
 	int16_t	 fs_opostbl[16][8];	/* old rotation block list head */
-	int32_t	 fs_sparecon[49];	/* reserved for future constants */
+	int32_t	 fs_sparecon[46];	/* reserved for future constants */
+/* these fields used in dirpref routine for optimization */
+	u_int8_t *fs_contigdirs;	/* # of contiguously allocated dirs */
+	int32_t	 fs_avgfilesize;	/* expected average file size */
+	int32_t	 fs_avgfpdir;		/* expected # of files per directory */
 	time_t	 fs_fscktime;		/* last time fsck(8)ed */
 	int32_t	 fs_contigsumsize;	/* size of cluster summary array */ 
 	int32_t	 fs_maxsymlinklen;	/* max length of an internal symlink */