PERFORCE change 168680 for review

[Aditya Sarawgi]

http://perforce.freebsd.org/chv.cgi?CH=168680

Change 168680 by truncs at aditya on 2009/09/19 13:43:32

	WIP - Orlov block allocator for ext2fs. It will restrict many directories 
	to be in the same group. This will result in other directories having 
	sufficient space for their sub-directories and file. It also allows 
	spreading of directories in the root directory. 

Affected files ...

.. //depot/projects/soc2009/soc_ext2fs/src/sys/fs/ext2fs/ext2_alloc.c#7 edit
.. //depot/projects/soc2009/soc_ext2fs/src/sys/fs/ext2fs/ext2fs.h#2 edit

Differences ...

==== //depot/projects/soc2009/soc_ext2fs/src/sys/fs/ext2fs/ext2_alloc.c#7 (text+ko) ====

@@ -52,7 +52,7 @@
 #include <fs/ext2fs/ext2_extern.h>
 
 static daddr_t	ext2_alloccg(struct inode *, int, daddr_t, int);
-static u_long	ext2_dirpref(struct m_ext2fs *);
+static u_long	ext2_dirpref(struct inode *);
 static void	ext2_fserr(struct m_ext2fs *, u_int, char *);
 static u_long	ext2_hashalloc(struct inode *, int, long, int,
 				daddr_t (*)(struct inode *, int, daddr_t, 
@@ -344,7 +344,7 @@
 	 * inode.
 	 */
 	if((mode & IFMT) == IFDIR)
-		cg = ext2_dirpref(fs);
+		cg = ext2_dirpref(pip);
 	else
 		cg = ino_to_cg(fs, pip->i_number);
 	ipref = cg * fs->e2fs->e2fs_ipg + 1;
@@ -393,26 +393,61 @@
 /*
  * 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 inodes, the one with the smallest number of directories.
+ * The policy implemented by this algorithm is to allocate a
+ * directory inode in the same cylinder group as its parent
+ * directory, but also to reserve space for its files inodes
+ * and data. Restrict the number of directories which may be
+ * allocated one after another in the same cylinder group
+ * without intervening allocation of files.
+ *
+ * If we allocate a first level directory then force allocation
+ * in another cylinder group.
+ *
  */
 static u_long
-ext2_dirpref(struct m_ext2fs *fs)
+ext2_dirpref(struct inode *pip)
 {
-        int cg, maxspace, mincg, avgifree;
-        avgifree = fs->e2fs->e2fs_ficount / fs->e2fs_gcount;
-        maxspace = 0;
-        mincg = -1;
-        for (cg = 0; cg < fs->e2fs_gcount; cg++) {
-                if ( fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree) {
-                        if (mincg == -1 || fs->e2fs_gd[cg].ext2bgd_nbfree > maxspace) {
+	struct m_ext2fs *fs;
+        int cg, prefcg, dirsize, cgsize;
+	int avgifree, avgbfree, avgndir, curdirsize;
+	int minifree, minbfree, maxndir;
+	int mincg, minndir;
+	int maxcontigdirs;
+
+	fs = pip->i_e2fs;
+
+ 	avgifree = fs->e2fs->e2fs_ficount / fs->e2fs_gcount;
+	avgbfree = fs->e2fs->e2fs_fbcount / fs->e2fs_gcount;
+	avgndir  = fs->e2fs_total_dir / e2fs->e2fs_gcount;
+
+	/*
+	 * Force allocation in another cg if creating a first level dir.
+	 */
+	ASSERT_VOP_LOCKED(ITOV(pip), "ext2fs_dirpref");
+	if (ITOV(pip)->v_vflag & VV_ROOT) {
+		prefcg = arc4random() % fs->e2fs_gcount;
+		mincg = prefcg;
+		minndir = fs->e2fs_ipg;
+		for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
+			if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir &&
+			    fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree &&
+			    fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) {
+				mincg = cg;
+				minndir = fs->e2fs_gd[cg].ext2bgd_ndirs;
+			}
+		for (cg = 0; cg < prefcg; cg++)
+			if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir &&
+                            fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree &&
+                            fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) {
                                 mincg = cg;
-                                maxspace = fs->e2fs_gd[cg].ext2bgd_nbfree;
+                                minndir = fs->e2fs_gd[cg].ext2bgd_ndirs;
                         }
-                }
+
+		return (mincg);
 	}
-        return mincg;
+
+
+
 }
 
 /*

==== //depot/projects/soc2009/soc_ext2fs/src/sys/fs/ext2fs/ext2fs.h#2 (text+ko) ====

@@ -187,6 +187,7 @@
 	int32_t  e2fs_isize;      /* Size of inode */
 	uint32_t e2fs_mount_opt;
 	uint32_t e2fs_blocksize_bits;
+	uint32_t e2fs_total_dir;  /* Total number of directories */
 	char e2fs_wasvalid;       /* valid at mount time */
 	off_t e2fs_maxfilesize;
 	struct ext2_gd *e2fs_gd; /* Group Descriptors */