xnu-517.tar.gz

[apple/xnu.git] / bsd / ufs / ffs / ffs_alloc.c

diff --git a/bsd/ufs/ffs/ffs_alloc.c b/bsd/ufs/ffs/ffs_alloc.c
index 7671afb01fa66de3eb466d0256ecd91773fc65fb..6b4eb93c28b1ef38f150cbc352f0345b9e097444 100644 (file)
--- a/bsd/ufs/ffs/ffs_alloc.c
+++ b/bsd/ufs/ffs/ffs_alloc.c
@@ -1,5 +1,5 @@
 /*
 /*

- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2003 Apple Computer, Inc. All rights reserved.

  *
  * @APPLE_LICENSE_HEADER_START@
  * 
  *
  * @APPLE_LICENSE_HEADER_START@
  * 


@@ -89,7 +89,7 @@ static ufs_daddr_t ffs_alloccg __P((struct inode *, int, ufs_daddr_t, int));
 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 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
 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


@@ -243,7 +243,7 @@ ffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp)
                ip->i_flag |= IN_CHANGE | IN_UPDATE;
                allocbuf(bp, nsize);
                bp->b_flags |= B_DONE;
                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);
        }
                *bpp = bp;
                return (0);
        }


@@ -307,7 +307,7 @@ ffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp)
                ip->i_flag |= IN_CHANGE | IN_UPDATE;
                allocbuf(bp, nsize);
                bp->b_flags |= B_DONE;
                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);
        }
                *bpp = bp;
                return (0);
        }


@@ -392,16 +392,27 @@ ffs_valloc(ap)
                goto noinodes;
 
        if ((mode & IFMT) == IFDIR)
                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);
        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;
        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);
        if (error) {
                VOP_VFREE(pvp, ino, mode);
                return (error);


@@ -432,28 +443,112 @@ noinodes:
 }
 
 /*
 }
 
 /*

- * 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
  */
 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;
        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));

 }
 
 /*
 }
 
 /*