From owner-p4-projects@FreeBSD.ORG Sat Sep 19 13:43:36 2009 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id C60B71065693; Sat, 19 Sep 2009 13:43:35 +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 70F06106568D for ; Sat, 19 Sep 2009 13:43:35 +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 5F7ED8FC17 for ; Sat, 19 Sep 2009 13:43:35 +0000 (UTC) Received: from repoman.freebsd.org (localhost [127.0.0.1]) by repoman.freebsd.org (8.14.3/8.14.3) with ESMTP id n8JDhZHf072271 for ; Sat, 19 Sep 2009 13:43:35 GMT (envelope-from truncs@FreeBSD.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.14.3/8.14.3/Submit) id n8JDhYmc072269 for perforce@freebsd.org; Sat, 19 Sep 2009 13:43:34 GMT (envelope-from truncs@FreeBSD.org) Date: Sat, 19 Sep 2009 13:43:34 GMT Message-Id: <200909191343.n8JDhYmc072269@repoman.freebsd.org> X-Authentication-Warning: repoman.freebsd.org: perforce set sender to truncs@FreeBSD.org using -f From: Aditya Sarawgi To: Perforce Change Reviews Cc: Subject: PERFORCE change 168680 for review X-BeenThere: p4-projects@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: p4 projects tree changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 19 Sep 2009 13:43:36 -0000 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 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 */