FreeBSD/sys/fs/ext2fs/ext2_alloc.c
/*
 * Find a cylinder to place a directory.
 *
 * 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.
 *
 */
Find a cylinder to place a directory.
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.
Find a cylinder to place a directory . 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 inode *pip)
{
	struct m_ext2fs *fs;
	int cg, prefcg, cgsize;
	u_int avgifree, avgbfree, avgndir, curdirsize;
	u_int minifree, minbfree, maxndir;
	u_int mincg, minndir;
	u_int dirsize, maxcontigdirs;
	mtx_assert(EXT2_MTX(pip->i_ump), MA_OWNED);
	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 / fs->e2fs_gcount;
	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;
				minndir = fs->e2fs_gd[cg].ext2bgd_ndirs;
			}
		return (mincg);
	}
	maxndir = min(avgndir + fs->e2fs_ipg / 16, fs->e2fs_ipg);
	minifree = avgifree - avgifree / 4;
	if (minifree < 1)
		minifree = 1;
	minbfree = avgbfree - avgbfree / 4;
	if (minbfree < 1)
		minbfree = 1;
	cgsize = fs->e2fs_fsize * fs->e2fs_fpg;
	dirsize = AVGDIRSIZE;
	curdirsize = avgndir ? (cgsize - avgbfree * fs->e2fs_bsize) / avgndir : 0;
	if (dirsize < curdirsize)
		dirsize = curdirsize;
	maxcontigdirs = min((avgbfree * fs->e2fs_bsize) / dirsize, 255);
	maxcontigdirs = min(maxcontigdirs, fs->e2fs_ipg / AFPDIR);
	if (maxcontigdirs == 0)
		maxcontigdirs = 1;
	prefcg = ino_to_cg(fs, pip->i_number);
	for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
		if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir &&
		    fs->e2fs_gd[cg].ext2bgd_nifree >= minifree &&
		    fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) {
			if (fs->e2fs_contigdirs[cg] < maxcontigdirs)
				return (cg);
		}
	for (cg = 0; cg < prefcg; cg++)
		if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir &&
		    fs->e2fs_gd[cg].ext2bgd_nifree >= minifree &&
		    fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) {
			if (fs->e2fs_contigdirs[cg] < maxcontigdirs)
				return (cg);
		}
	for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
		if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree)
			return (cg);
	for (cg = 0; cg < prefcg; cg++)
		if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree)
			break;
	return (cg);
}
static u_long ext2_dirpref ( struct inode * pip ) { struct m_ext2fs * fs ; int cg , prefcg , cgsize ; u_int avgifree , avgbfree , avgndir , curdirsize ; u_int minifree , minbfree , maxndir ; u_int mincg , minndir ; u_int dirsize , maxcontigdirs ; mtx_assert ( EXT2_MTX ( pip -> i_ump ) , MA_OWNED ) ; 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 / fs -> e2fs_gcount ; ASSERT_VOP_LOCKED ( ITOV ( pip ) , " " ) ; 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 ; minndir = fs -> e2fs_gd [ cg ] . ext2bgd_ndirs ; } return ( mincg ) ; } maxndir = min ( avgndir + fs -> e2fs_ipg / 16 , fs -> e2fs_ipg ) ; minifree = avgifree - avgifree / 4 ; if ( minifree < 1 ) minifree = 1 ; minbfree = avgbfree - avgbfree / 4 ; if ( minbfree < 1 ) minbfree = 1 ; cgsize = fs -> e2fs_fsize * fs -> e2fs_fpg ; dirsize = AVGDIRSIZE ; curdirsize = avgndir ? ( cgsize - avgbfree * fs -> e2fs_bsize ) / avgndir : 0 ; if ( dirsize < curdirsize ) dirsize = curdirsize ; maxcontigdirs = min ( ( avgbfree * fs -> e2fs_bsize ) / dirsize , 255 ) ; maxcontigdirs = min ( maxcontigdirs , fs -> e2fs_ipg / AFPDIR ) ; if ( maxcontigdirs == 0 ) maxcontigdirs = 1 ; prefcg = ino_to_cg ( fs , pip -> i_number ) ; for ( cg = prefcg ; cg < fs -> e2fs_gcount ; cg ++ ) if ( fs -> e2fs_gd [ cg ] . ext2bgd_ndirs < maxndir && fs -> e2fs_gd [ cg ] . ext2bgd_nifree >= minifree && fs -> e2fs_gd [ cg ] . ext2bgd_nbfree >= minbfree ) { if ( fs -> e2fs_contigdirs [ cg ] < maxcontigdirs ) return ( cg ) ; } for ( cg = 0 ; cg < prefcg ; cg ++ ) if ( fs -> e2fs_gd [ cg ] . ext2bgd_ndirs < maxndir && fs -> e2fs_gd [ cg ] . ext2bgd_nifree >= minifree && fs -> e2fs_gd [ cg ] . ext2bgd_nbfree >= minbfree ) { if ( fs -> e2fs_contigdirs [ cg ] < maxcontigdirs ) return ( cg ) ; } for ( cg = prefcg ; cg < fs -> e2fs_gcount ; cg ++ ) if ( fs -> e2fs_gd [ cg ] . ext2bgd_nifree >= avgifree ) return ( cg ) ; for ( cg = 0 ; cg < prefcg ; cg ++ ) if ( fs -> e2fs_gd [ cg ] . ext2bgd_nifree >= avgifree ) break ; return ( cg ) ; }
Find a cylinder to place a directory.
Find a cylinder to place a directory .
/*
	 * Force allocation in another cg if creating a first level dir.
	 */ /*
	 * Count various limits which used for
	 * optimal allocation of a directory inode.
	 */ /*
	 * Limit number of dirs in one cg and reserve space for 
	 * regular files, but only if we have no deficit in
	 * inodes or space.
	 */ /*
	 * This is a backstop when we have deficit in space.
	 */