PERFORCE change 164904 for review
Aditya Sarawgi
truncs at FreeBSD.org
Mon Jun 22 20:44:05 UTC 2009
http://perforce.freebsd.org/chv.cgi?CH=164904
Change 164904 by truncs at aditya on 2009/06/22 20:43:24
ext2_hashalloc can allocate inode in 3 ways
1) preferred cylinder group
2) quadratic rehashing on a cylinder group
3) Brute force search
Affected files ...
.. //depot/projects/soc2009/soc_ext2fs/src/sys/gnu/fs/ext2fs/ext2_alloc.c#9 edit
Differences ...
==== //depot/projects/soc2009/soc_ext2fs/src/sys/gnu/fs/ext2fs/ext2_alloc.c#9 (text+ko) ====
@@ -563,3 +563,54 @@
return mincg;
}
+/*
+ * 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.
+ */
+static ino_t
+ext2fs_hashalloc(struct inode *ip, int cg, long pref, int size,
+ daddr_t (*allocator)(struct inode *, int, daddr_t, int))
+{
+ struct m_ext2fs *fs;
+ ino_t result;
+ int i, icg = cg;
+
+ fs = ip->i_e2fs;
+ /*
+ * 1: preferred cylinder group
+ */
+ result = (*allocator)(ip, cg, pref, size);
+ if (result)
+ return (result);
+ /*
+ * 2: quadratic rehash
+ */
+ for (i = 1; i < fs->e2fs_ncg; i *= 2) {
+ cg += i;
+ if (cg >= fs->e2fs_ncg)
+ cg -= fs->e2fs_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->e2fs_ncg;
+ for (i = 2; i < fs->e2fs_ncg; i++) {
+ result = (*allocator)(ip, cg, 0, size);
+ if (result)
+ return (result);
+ cg++;
+ if (cg == fs->e2fs_ncg)
+ cg = 0;
+ }
+ return (0);
+}
+
More information about the p4-projects
mailing list