From owner-p4-projects@FreeBSD.ORG  Mon Jun 22 20:44:04 2009
Return-Path: <owner-p4-projects@FreeBSD.ORG>
Delivered-To: p4-projects@freebsd.org
Received: by hub.freebsd.org (Postfix, from userid 32767)
	id 51E6E1065673; Mon, 22 Jun 2009 20:44:04 +0000 (UTC)
Delivered-To: perforce@FreeBSD.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 10277106564A
	for <perforce@FreeBSD.org>; Mon, 22 Jun 2009 20:44:04 +0000 (UTC)
	(envelope-from truncs@FreeBSD.org)
Received: from repoman.freebsd.org (repoman.freebsd.org
	[IPv6:2001:4f8:fff6::29])
	by mx1.freebsd.org (Postfix) with ESMTP id D89388FC13
	for <perforce@FreeBSD.org>; Mon, 22 Jun 2009 20:44:03 +0000 (UTC)
	(envelope-from truncs@FreeBSD.org)
Received: from repoman.freebsd.org (localhost [127.0.0.1])
	by repoman.freebsd.org (8.14.3/8.14.3) with ESMTP id n5MKi3QS060861
	for <perforce@FreeBSD.org>; Mon, 22 Jun 2009 20:44:03 GMT
	(envelope-from truncs@FreeBSD.org)
Received: (from perforce@localhost)
	by repoman.freebsd.org (8.14.3/8.14.3/Submit) id n5MKi3JK060859
	for perforce@freebsd.org; Mon, 22 Jun 2009 20:44:03 GMT
	(envelope-from truncs@FreeBSD.org)
Date: Mon, 22 Jun 2009 20:44:03 GMT
Message-Id: <200906222044.n5MKi3JK060859@repoman.freebsd.org>
X-Authentication-Warning: repoman.freebsd.org: perforce set sender to
	truncs@FreeBSD.org using -f
From: Aditya Sarawgi <truncs@FreeBSD.org>
To: Perforce Change Reviews <perforce@FreeBSD.org>
Cc: 
Subject: PERFORCE change 164904 for review
X-BeenThere: p4-projects@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: p4 projects tree changes <p4-projects.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/p4-projects>,
	<mailto:p4-projects-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/p4-projects>
List-Post: <mailto:p4-projects@freebsd.org>
List-Help: <mailto:p4-projects-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/p4-projects>,
	<mailto:p4-projects-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Mon, 22 Jun 2009 20:44:05 -0000

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

Change 164904 by truncs@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);
+}
+