/*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2003 Apple Computer, Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
static ufs_daddr_t ffs_alloccgblk __P((struct fs *, struct cg *, ufs_daddr_t));
static ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t,
int));
-static ino_t ffs_dirpref __P((struct fs *));
+static ino_t ffs_dirpref __P((struct inode *));
static ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int));
static void ffs_fserr __P((struct fs *, u_int, char *));
static u_long ffs_hashalloc
ip->i_flag |= IN_CHANGE | IN_UPDATE;
allocbuf(bp, nsize);
bp->b_flags |= B_DONE;
- bzero((char *)bp->b_data + osize, (u_int)nsize - osize);
+ bzero((char *)bp->b_data + osize, (u_int)bp->b_bufsize - osize);
*bpp = bp;
return (0);
}
ip->i_flag |= IN_CHANGE | IN_UPDATE;
allocbuf(bp, nsize);
bp->b_flags |= B_DONE;
- bzero((char *)bp->b_data + osize, (u_int)nsize - osize);
+ bzero((char *)bp->b_data + osize, (u_int)bp->b_bufsize - osize);
*bpp = bp;
return (0);
}
goto noinodes;
if ((mode & IFMT) == IFDIR)
- ipref = ffs_dirpref(fs);
+ ipref = ffs_dirpref(pip);
else
ipref = pip->i_number;
if (ipref >= fs->fs_ncg * fs->fs_ipg)
ipref = 0;
cg = ino_to_cg(fs, ipref);
+ /*
+ * Track the number of dirs created one after another
+ * in a cg without intervening files.
+ */
+ if ((mode & IFMT) == IFDIR) {
+ if (fs->fs_contigdirs[cg] < 255)
+ fs->fs_contigdirs[cg]++;
+ } else {
+ if (fs->fs_contigdirs[cg] > 0)
+ fs->fs_contigdirs[cg]--;
+ }
ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, ffs_nodealloccg);
if (ino == 0)
goto noinodes;
- error = VFS_VGET(pvp->v_mount, ino, ap->a_vpp);
+ error = VFS_VGET(pvp->v_mount, (void *)ino, ap->a_vpp);
if (error) {
VOP_VFREE(pvp, ino, mode);
return (error);
}
/*
- * Find a cylinder to place a directory.
+ * Find a cylinder group 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.
*/
static ino_t
-ffs_dirpref(fs)
- register struct fs *fs;
+ffs_dirpref(pip)
+ struct inode *pip;
{
- int cg, minndir, mincg, avgifree;
+ register struct fs *fs;
+ int cg, prefcg, dirsize, cgsize;
+ int avgifree, avgbfree, avgndir, curdirsize;
+ int minifree, minbfree, maxndir;
+ int mincg, minndir;
+ int maxcontigdirs;
+ fs = pip->i_fs;
avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg;
- minndir = fs->fs_ipg;
- mincg = 0;
- for (cg = 0; cg < fs->fs_ncg; cg++)
- if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
- fs->fs_cs(fs, cg).cs_nifree >= avgifree) {
- mincg = cg;
- minndir = fs->fs_cs(fs, cg).cs_ndir;
+ avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
+ avgndir = fs->fs_cstotal.cs_ndir / fs->fs_ncg;
+
+ /*
+ * Force allocation in another cg if creating a first level dir.
+ */
+ if (ITOV(pip)->v_flag & VROOT) {
+#ifdef __APPLE__
+ prefcg = random() % fs->fs_ncg;
+#else
+ prefcg = arc4random() % fs->fs_ncg;
+#endif
+ mincg = prefcg;
+ minndir = fs->fs_ipg;
+ for (cg = prefcg; cg < fs->fs_ncg; cg++)
+ if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
+ fs->fs_cs(fs, cg).cs_nifree >= avgifree &&
+ fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
+ mincg = cg;
+ minndir = fs->fs_cs(fs, cg).cs_ndir;
+ }
+ for (cg = 0; cg < prefcg; cg++)
+ if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
+ fs->fs_cs(fs, cg).cs_nifree >= avgifree &&
+ fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
+ mincg = cg;
+ minndir = fs->fs_cs(fs, cg).cs_ndir;
+ }
+ return ((ino_t)(fs->fs_ipg * mincg));
+ }
+
+ /*
+ * Count various limits which used for
+ * optimal allocation of a directory inode.
+ */
+ maxndir = min(avgndir + fs->fs_ipg / 16, fs->fs_ipg);
+ minifree = avgifree - fs->fs_ipg / 4;
+ if (minifree < 0)
+ minifree = 0;
+ minbfree = avgbfree - fs->fs_fpg / fs->fs_frag / 4;
+ if (minbfree < 0)
+ minbfree = 0;
+ cgsize = fs->fs_fsize * fs->fs_fpg;
+ dirsize = fs->fs_avgfilesize * fs->fs_avgfpdir;
+ curdirsize = avgndir ? (cgsize - avgbfree * fs->fs_bsize) / avgndir : 0;
+ if (dirsize < curdirsize)
+ dirsize = curdirsize;
+ maxcontigdirs = min(cgsize / dirsize, 255);
+ if (fs->fs_avgfpdir > 0)
+ maxcontigdirs = min(maxcontigdirs,
+ fs->fs_ipg / fs->fs_avgfpdir);
+ if (maxcontigdirs == 0)
+ maxcontigdirs = 1;
+
+ /*
+ * Limit number of dirs in one cg and reserve space for
+ * regular files, but only if we have no deficit in
+ * inodes or space.
+ */
+ prefcg = ino_to_cg(fs, pip->i_number);
+ for (cg = prefcg; cg < fs->fs_ncg; cg++)
+ if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
+ fs->fs_cs(fs, cg).cs_nifree >= minifree &&
+ fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
+ if (fs->fs_contigdirs[cg] < maxcontigdirs)
+ return ((ino_t)(fs->fs_ipg * cg));
+ }
+ for (cg = 0; cg < prefcg; cg++)
+ if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
+ fs->fs_cs(fs, cg).cs_nifree >= minifree &&
+ fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
+ if (fs->fs_contigdirs[cg] < maxcontigdirs)
+ return ((ino_t)(fs->fs_ipg * cg));
}
- return ((ino_t)(fs->fs_ipg * mincg));
+ /*
+ * This is a backstop when we have deficit in space.
+ */
+ for (cg = prefcg; cg < fs->fs_ncg; cg++)
+ if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
+ return ((ino_t)(fs->fs_ipg * cg));
+ for (cg = 0; cg < prefcg; cg++)
+ if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
+ break;
+ return ((ino_t)(fs->fs_ipg * cg));
}
/*
projects / apple / xnu.git / blobdiff