use proper types for uids, gids

[unix-history] / usr / src / sys / ufs / ffs / ffs_alloc.c

diff --git a/usr/src/sys/ufs/ffs/ffs_alloc.c b/usr/src/sys/ufs/ffs/ffs_alloc.c
index 202225c..a54f8d7 100644 (file)
--- a/usr/src/sys/ufs/ffs/ffs_alloc.c
+++ b/usr/src/sys/ufs/ffs/ffs_alloc.c
@@ -1,16 +1,22 @@
-/*     ffs_alloc.c     2.25    83/05/21        */
+/*
+ * Copyright (c) 1982 Regents of the University of California.
+ * All rights reserved.  The Berkeley software License Agreement
+ * specifies the terms and conditions for redistribution.
+ *
+ *     @(#)ffs_alloc.c 6.17 (Berkeley) %G%
+ */

 
 

-#include "../h/param.h"
-#include "../h/systm.h"
-#include "../h/mount.h"
-#include "../h/fs.h"
-#include "../h/conf.h"
-#include "../h/buf.h"
-#include "../h/inode.h"
-#include "../h/dir.h"
-#include "../h/user.h"
-#include "../h/quota.h"
-#include "../h/kernel.h"
+#include "param.h"
+#include "systm.h"
+#include "mount.h"
+#include "fs.h"
+#include "buf.h"
+#include "inode.h"
+#include "dir.h"
+#include "user.h"
+#include "quota.h"
+#include "kernel.h"
+#include "syslog.h"

 
 extern u_long          hashalloc();
 extern ino_t           ialloccg();
 
 extern u_long          hashalloc();
 extern ino_t           ialloccg();


@@ -106,7 +112,7 @@ realloccg(ip, bprev, bpref, osize, nsize)
        daddr_t bno;
        register struct fs *fs;
        register struct buf *bp, *obp;
        daddr_t bno;
        register struct fs *fs;
        register struct buf *bp, *obp;

-       int cg;
+       int cg, request;

        
        fs = ip->i_fs;
        if ((unsigned)osize > fs->fs_bsize || fragoff(fs, osize) != 0 ||
        
        fs = ip->i_fs;
        if ((unsigned)osize > fs->fs_bsize || fragoff(fs, osize) != 0 ||


@@ -145,7 +151,50 @@ realloccg(ip, bprev, bpref, osize, nsize)
        }
        if (bpref >= fs->fs_size)
                bpref = 0;
        }
        if (bpref >= fs->fs_size)
                bpref = 0;

-       bno = (daddr_t)hashalloc(ip, cg, (long)bpref, nsize,
+       switch (fs->fs_optim) {
+       case FS_OPTSPACE:
+               /*
+                * Allocate an exact sized fragment. Although this makes 
+                * best use of space, we will waste time relocating it if 
+                * the file continues to grow. If the fragmentation is
+                * less than half of the minimum free reserve, we choose
+                * to begin optimizing for time.
+                */
+               request = nsize;
+               if (fs->fs_minfree < 5 ||
+                   fs->fs_cstotal.cs_nffree >
+                   fs->fs_dsize * fs->fs_minfree / (2 * 100))
+                       break;
+               log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n",
+                       fs->fs_fsmnt);
+               fs->fs_optim = FS_OPTTIME;
+               break;
+       case FS_OPTTIME:
+               /*
+                * At this point we have discovered a file that is trying
+                * to grow a small fragment to a larger fragment. To save
+                * time, we allocate a full sized block, then free the 
+                * unused portion. If the file continues to grow, the 
+                * `fragextend' call above will be able to grow it in place
+                * without further copying. If aberrant programs cause
+                * disk fragmentation to grow within 2% of the free reserve,
+                * we choose to begin optimizing for space.
+                */
+               request = fs->fs_bsize;
+               if (fs->fs_cstotal.cs_nffree <
+                   fs->fs_dsize * (fs->fs_minfree - 2) / 100)
+                       break;
+               log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n",
+                       fs->fs_fsmnt);
+               fs->fs_optim = FS_OPTSPACE;
+               break;
+       default:
+               printf("dev = 0x%x, optim = %d, fs = %s\n",
+                   ip->i_dev, fs->fs_optim, fs->fs_fsmnt);
+               panic("realloccg: bad optim");
+               /* NOTREACHED */
+       }
+       bno = (daddr_t)hashalloc(ip, cg, (long)bpref, request,

                (u_long (*)())alloccg);
        if (bno > 0) {
                obp = bread(ip->i_dev, fsbtodb(fs, bprev), osize);
                (u_long (*)())alloccg);
        if (bno > 0) {
                obp = bread(ip->i_dev, fsbtodb(fs, bprev), osize);


@@ -156,8 +205,15 @@ realloccg(ip, bprev, bpref, osize, nsize)
                bp = getblk(ip->i_dev, fsbtodb(fs, bno), nsize);
                bcopy(obp->b_un.b_addr, bp->b_un.b_addr, (u_int)osize);
                bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize);
                bp = getblk(ip->i_dev, fsbtodb(fs, bno), nsize);
                bcopy(obp->b_un.b_addr, bp->b_un.b_addr, (u_int)osize);
                bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize);

+               if (obp->b_flags & B_DELWRI) {
+                       obp->b_flags &= ~B_DELWRI;
+                       u.u_ru.ru_oublock--;            /* delete charge */
+               }

                brelse(obp);
                free(ip, bprev, (off_t)osize);
                brelse(obp);
                free(ip, bprev, (off_t)osize);

+               if (nsize < request)
+                       free(ip, bno + numfrags(fs, nsize),
+                               (off_t)(request - nsize));

                ip->i_blocks += btodb(nsize - osize);
                ip->i_flag |= IUPD|ICHG;
                return (bp);
                ip->i_blocks += btodb(nsize - osize);
                ip->i_flag |= IUPD|ICHG;
                return (bp);


@@ -214,7 +270,7 @@ ialloc(pip, ipref, mode)
                goto noinodes;
        ip = iget(pip->i_dev, pip->i_fs, ino);
        if (ip == NULL) {
                goto noinodes;
        ip = iget(pip->i_dev, pip->i_fs, ino);
        if (ip == NULL) {

-               ifree(ip, ino, 0);
+               ifree(pip, ino, 0);

                return (NULL);
        }
        if (ip->i_mode) {
                return (NULL);
        }
        if (ip->i_mode) {


@@ -270,9 +326,14 @@ dirpref(fs)
  * the file. If no blocks have been allocated in any other section, the
  * policy is to place the section in a cylinder group with a greater than
  * average number of free blocks.  An appropriate cylinder group is found
  * the file. If no blocks have been allocated in any other section, the
  * policy is to place the section in a cylinder group with a greater than
  * average number of free blocks.  An appropriate cylinder group is found

- * by maintaining a rotor that sweeps the cylinder groups. When a new
- * group of blocks is needed, the rotor is advanced until a cylinder group
- * with greater than the average number of free blocks is found.
+ * by using a rotor that sweeps the cylinder groups. When a new group of
+ * blocks is needed, the sweep begins in the cylinder group following the
+ * cylinder group from which the previous allocation was made. The sweep
+ * continues until a cylinder group with greater than the average number
+ * of free blocks is found. If the allocation is for the first block in an
+ * indirect block, the information on the previous allocation is unavailable;
+ * here a best guess is made based upon the logical block number being
+ * allocated.

  * 
  * If a section is already partially allocated, the policy is to
  * contiguously allocate fs_maxcontig blocks.  The end of one of these
  * 
  * If a section is already partially allocated, the policy is to
  * contiguously allocate fs_maxcontig blocks.  The end of one of these


@@ -289,7 +350,8 @@ blkpref(ip, lbn, indx, bap)
        daddr_t *bap;
 {
        register struct fs *fs;
        daddr_t *bap;
 {
        register struct fs *fs;

-       int cg, avgbfree;
+       register int cg;
+       int avgbfree, startcg;

        daddr_t nextblk;
 
        fs = ip->i_fs;
        daddr_t nextblk;
 
        fs = ip->i_fs;


@@ -302,13 +364,18 @@ blkpref(ip, lbn, indx, bap)
                 * Find a cylinder with greater than average number of
                 * unused data blocks.
                 */
                 * Find a cylinder with greater than average number of
                 * unused data blocks.
                 */

+               if (indx == 0 || bap[indx - 1] == 0)
+                       startcg = itog(fs, ip->i_number) + lbn / fs->fs_maxbpg;
+               else
+                       startcg = dtog(fs, bap[indx - 1]) + 1;
+               startcg %= fs->fs_ncg;

                avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
                avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;

-               for (cg = fs->fs_cgrotor + 1; cg < fs->fs_ncg; cg++)
+               for (cg = startcg; cg < fs->fs_ncg; cg++)

                        if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
                                fs->fs_cgrotor = cg;
                                return (fs->fs_fpg * cg + fs->fs_frag);
                        }
                        if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
                                fs->fs_cgrotor = cg;
                                return (fs->fs_fpg * cg + fs->fs_frag);
                        }

-               for (cg = 0; cg <= fs->fs_cgrotor; cg++)
+               for (cg = 0; cg <= startcg; cg++)

                        if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
                                fs->fs_cgrotor = cg;
                                return (fs->fs_fpg * cg + fs->fs_frag);
                        if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
                                fs->fs_cgrotor = cg;
                                return (fs->fs_fpg * cg + fs->fs_frag);


@@ -415,11 +482,11 @@ fragextend(ip, cg, bprev, osize, nsize)
        int i;
 
        fs = ip->i_fs;
        int i;
 
        fs = ip->i_fs;

-       if (fs->fs_cs(fs, cg).cs_nffree < nsize - osize)
+       if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize))

                return (NULL);
        frags = numfrags(fs, nsize);
                return (NULL);
        frags = numfrags(fs, nsize);

-       bbase = fragoff(fs, bprev);
-       if (bbase > (bprev + frags - 1) % fs->fs_frag) {
+       bbase = fragnum(fs, bprev);
+       if (bbase > fragnum(fs, (bprev + frags - 1))) {

                /* cannot extend across a block boundry */
                return (NULL);
        }
                /* cannot extend across a block boundry */
                return (NULL);
        }


@@ -484,12 +551,11 @@ alloccg(ip, cg, bpref, size)
                return (NULL);
        bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize);
        cgp = bp->b_un.b_cg;
                return (NULL);
        bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize);
        cgp = bp->b_un.b_cg;

-       if (bp->b_flags & B_ERROR || cgp->cg_magic != CG_MAGIC) {
+       if (bp->b_flags & B_ERROR || cgp->cg_magic != CG_MAGIC ||
+           (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) {

                brelse(bp);
                return (NULL);
        }
                brelse(bp);
                return (NULL);
        }

-       if (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)
-               return (NULL);

        cgp->cg_time = time.tv_sec;
        if (size == fs->fs_bsize) {
                bno = alloccgblk(fs, cgp, bpref);
        cgp->cg_time = time.tv_sec;
        if (size == fs->fs_bsize) {
                bno = alloccgblk(fs, cgp, bpref);


@@ -528,8 +594,10 @@ alloccg(ip, cg, bpref, size)
                return (bno);
        }
        bno = mapsearch(fs, cgp, bpref, allocsiz);
                return (bno);
        }
        bno = mapsearch(fs, cgp, bpref, allocsiz);

-       if (bno < 0)
+       if (bno < 0) {
+               brelse(bp);

                return (NULL);
                return (NULL);

+       }

        for (i = 0; i < frags; i++)
                clrbit(cgp->cg_free, bno + i);
        cgp->cg_cs.cs_nffree -= frags;
        for (i = 0; i < frags; i++)
                clrbit(cgp->cg_free, bno + i);
        cgp->cg_cs.cs_nffree -= frags;


@@ -569,7 +637,7 @@ alloccgblk(fs, cgp, bpref)
                bpref = cgp->cg_rotor;
                goto norot;
        }
                bpref = cgp->cg_rotor;
                goto norot;
        }

-       bpref &= ~(fs->fs_frag - 1);
+       bpref = blknum(fs, bpref);

        bpref = dtogd(fs, bpref);
        /*
         * if the requested block is available, use it
        bpref = dtogd(fs, bpref);
        /*
         * if the requested block is available, use it


@@ -669,39 +737,52 @@ ialloccg(ip, cg, ipref, mode)
        int mode;
 {
        register struct fs *fs;
        int mode;
 {
        register struct fs *fs;

-       register struct buf *bp;

        register struct cg *cgp;
        register struct cg *cgp;

-       int i;
+       struct buf *bp;
+       int start, len, loc, map, i;

 
        fs = ip->i_fs;
        if (fs->fs_cs(fs, cg).cs_nifree == 0)
                return (NULL);
        bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize);
        cgp = bp->b_un.b_cg;
 
        fs = ip->i_fs;
        if (fs->fs_cs(fs, cg).cs_nifree == 0)
                return (NULL);
        bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize);
        cgp = bp->b_un.b_cg;

-       if (bp->b_flags & B_ERROR || cgp->cg_magic != CG_MAGIC) {
+       if (bp->b_flags & B_ERROR || cgp->cg_magic != CG_MAGIC ||
+           cgp->cg_cs.cs_nifree == 0) {

                brelse(bp);
                return (NULL);
        }
                brelse(bp);
                return (NULL);
        }

-       if (cgp->cg_cs.cs_nifree == 0)
-               return (NULL);

        cgp->cg_time = time.tv_sec;
        if (ipref) {
                ipref %= fs->fs_ipg;
                if (isclr(cgp->cg_iused, ipref))
                        goto gotit;
        cgp->cg_time = time.tv_sec;
        if (ipref) {
                ipref %= fs->fs_ipg;
                if (isclr(cgp->cg_iused, ipref))
                        goto gotit;

-       } else
-               ipref = cgp->cg_irotor;
-       for (i = 0; i < fs->fs_ipg; i++) {
-               ipref++;
-               if (ipref >= fs->fs_ipg)
-                       ipref = 0;
-               if (isclr(cgp->cg_iused, ipref)) {
+       }
+       start = cgp->cg_irotor / NBBY;
+       len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY);
+       loc = skpc(0xff, len, &cgp->cg_iused[start]);
+       if (loc == 0) {
+               len = start + 1;
+               start = 0;
+               loc = skpc(0xff, len, &cgp->cg_iused[0]);
+               if (loc == 0) {
+                       printf("cg = %s, irotor = %d, fs = %s\n",
+                           cg, cgp->cg_irotor, fs->fs_fsmnt);
+                       panic("ialloccg: map corrupted");
+                       /* NOTREACHED */
+               }
+       }
+       i = start + len - loc;
+       map = cgp->cg_iused[i];
+       ipref = i * NBBY;
+       for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) {
+               if ((map & i) == 0) {

                        cgp->cg_irotor = ipref;
                        goto gotit;
                }
        }
                        cgp->cg_irotor = ipref;
                        goto gotit;
                }
        }

-       brelse(bp);
-       return (NULL);
+       printf("fs = %s\n", fs->fs_fsmnt);
+       panic("ialloccg: block not in map");
+       /* NOTREACHED */

 gotit:
        setbit(cgp->cg_iused, ipref);
        cgp->cg_cs.cs_nifree--;
 gotit:
        setbit(cgp->cg_iused, ipref);
        cgp->cg_cs.cs_nifree--;


@@ -768,7 +849,7 @@ free(ip, bno, size)
                cgp->cg_b[i][cbtorpos(fs, bno)]++;
                cgp->cg_btot[i]++;
        } else {
                cgp->cg_b[i][cbtorpos(fs, bno)]++;
                cgp->cg_btot[i]++;
        } else {

-               bbase = bno - (bno % fs->fs_frag);
+               bbase = bno - fragnum(fs, bno);

                /*
                 * decrement the counts associated with the old frags
                 */
                /*
                 * decrement the counts associated with the old frags
                 */


@@ -849,6 +930,8 @@ ifree(ip, ino, mode)
                panic("ifree: freeing free inode");
        }
        clrbit(cgp->cg_iused, ino);
                panic("ifree: freeing free inode");
        }
        clrbit(cgp->cg_iused, ino);

+       if (ino < cgp->cg_irotor)
+               cgp->cg_irotor = ino;

        cgp->cg_cs.cs_nifree++;
        fs->fs_cstotal.cs_nifree++;
        fs->fs_cs(fs, cg).cs_nifree++;
        cgp->cg_cs.cs_nifree++;
        fs->fs_cstotal.cs_nifree++;
        fs->fs_cs(fs, cg).cs_nifree++;


@@ -887,15 +970,21 @@ mapsearch(fs, cgp, bpref, allocsiz)
        else
                start = cgp->cg_frotor / NBBY;
        len = howmany(fs->fs_fpg, NBBY) - start;
        else
                start = cgp->cg_frotor / NBBY;
        len = howmany(fs->fs_fpg, NBBY) - start;

-       loc = scanc(len, &cgp->cg_free[start], fragtbl[fs->fs_frag],
-               1 << (allocsiz - 1 + (fs->fs_frag % NBBY)));
+       loc = scanc((unsigned)len, (caddr_t)&cgp->cg_free[start],
+               (caddr_t)fragtbl[fs->fs_frag],
+               (int)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));

        if (loc == 0) {
                len = start + 1;
                start = 0;
        if (loc == 0) {
                len = start + 1;
                start = 0;

-               loc = scanc(len, &cgp->cg_free[start], fragtbl[fs->fs_frag],
-                       1 << (allocsiz - 1 + (fs->fs_frag % NBBY)));
-               if (loc == 0)
-                       return (-1);
+               loc = scanc((unsigned)len, (caddr_t)&cgp->cg_free[0],
+                       (caddr_t)fragtbl[fs->fs_frag],
+                       (int)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
+               if (loc == 0) {
+                       printf("start = %d, len = %d, fs = %s\n",
+                           start, len, fs->fs_fsmnt);
+                       panic("alloccg: map corrupted");
+                       /* NOTREACHED */
+               }

        }
        bno = (start + len - loc) * NBBY;
        cgp->cg_frotor = bno;
        }
        bno = (start + len - loc) * NBBY;
        cgp->cg_frotor = bno;


@@ -931,5 +1020,5 @@ fserr(fs, cp)
        char *cp;
 {
 
        char *cp;
 {
 

-       printf("%s: %s\n", fs->fs_fsmnt, cp);
+       log(LOG_ERR, "%s: %s\n", fs->fs_fsmnt, cp);

 }
 }