Date: Sat, 19 Sep 2009 13:43:34 GMT From: Aditya Sarawgi <truncs@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 168680 for review Message-ID: <200909191343.n8JDhYmc072269@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=168680 Change 168680 by truncs@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 */
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200909191343.n8JDhYmc072269>