Date: Mon, 22 Jun 2009 20:44:03 GMT From: Aditya Sarawgi <truncs@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 164904 for review Message-ID: <200906222044.n5MKi3JK060859@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
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); +} +
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200906222044.n5MKi3JK060859>