put in optimal rotational block allocation

SCCS-vsn: sys/ufs/ffs/fs.h 1.4
SCCS-vsn: sys/ufs/ffs/ffs_alloc.c 1.7
SCCS-vsn: sys/ufs/lfs/lfs_alloc.c 1.7
SCCS-vsn: sbin/newfs/mkfs.c 1.8
SCCS-vsn: sbin/fsck/main.c 1.9
SCCS-vsn: sbin/icheck/icheck.c 1.6
SCCS-vsn: sbin/dumpfs/dumpfs.c 1.4

diff --git a/usr/src/sbin/dumpfs/dumpfs.c b/usr/src/sbin/dumpfs/dumpfs.c
index 6c5d273..6105a2d 100644 (file)
--- a/usr/src/sbin/dumpfs/dumpfs.c
+++ b/usr/src/sbin/dumpfs/dumpfs.c
@@ -1,4 +1,4 @@
-static char *sccsid = "@(#)dumpfs.c    1.3 (Berkeley) %G%";
+static char *sccsid = "@(#)dumpfs.c    1.4 (Berkeley) %G%";

 #include "../h/param.h"
 #include "../h/fs.h"
 #include "../h/inode.h"
 #include "../h/param.h"
 #include "../h/fs.h"
 #include "../h/inode.h"


@@ -13,8 +13,6 @@ union {
 } fsun;
 #define        afs     fsun.fs
 
 } fsun;
 #define        afs     fsun.fs
 

-struct csum *fscs;
-

 union {
        struct cg cg;
        char pad[BSIZE];
 union {
        struct cg cg;
        char pad[BSIZE];


@@ -24,7 +22,7 @@ union {
 main(argc, argv)
        char **argv;
 {
 main(argc, argv)
        char **argv;
 {

-       int i;
+       int i, j, k;

 
        close(0);
        if (open(argv[1], 0) != 0)
 
        close(0);
        if (open(argv[1], 0) != 0)


@@ -45,13 +43,27 @@ main(argc, argv)
            afs.fs_cpg, afs.fs_fpg, afs.fs_ipg);
        printf("nffree\t%d\nnbfree\t%d\nnifree\t%d\n",
            afs.fs_nffree, afs.fs_nbfree, afs.fs_nifree);
            afs.fs_cpg, afs.fs_fpg, afs.fs_ipg);
        printf("nffree\t%d\nnbfree\t%d\nnifree\t%d\n",
            afs.fs_nffree, afs.fs_nbfree, afs.fs_nifree);

-       printf("cs[].cs_(nbfree,ndir,nifree):\n\t");
-       fscs = (struct csum *)calloc(afs.fs_ncg, sizeof (struct csum));
-       lseek(0, csaddr(&afs)*FSIZE, 0);
-       if (read(0, fscs, cssize(&afs)) != cssize(&afs))
-               perror(argv[1]), exit(1);
+       printf("cgrotor\t%d\nblocks available in each rotational position",
+           afs.fs_cgrotor);
+       for (i = 0; i < NRPOS; i++) {
+               if (afs.fs_postbl[i] > -1)
+                       printf("\nposition %d:\t", i);
+               for (j = afs.fs_postbl[i], k = 1; j > -1;
+                    j = afs.fs_rotbl[j], k++) {
+                       if (k % 15 == 0)
+                               printf("\n\t\t");
+                       printf("%4d", j);
+               }
+       }
+       printf("\ncs[].cs_(nbfree,ndir,nifree):\n\t");
+       for (i = 0; i < howmany(cssize(&afs), BSIZE); i++) {
+               afs.fs_csp[i] = (struct csum *)calloc(1, BSIZE);
+               lseek(0, (csaddr(&afs) + (i * FRAG)) * FSIZE, 0);
+               if (read(0, afs.fs_csp[i], BSIZE) != BSIZE)
+                       perror(argv[1]), exit(1);
+       }

        for (i = 0; i < afs.fs_ncg; i++) {
        for (i = 0; i < afs.fs_ncg; i++) {

-               struct csum *cs = fscs+i;
+               struct csum *cs = &afs.fs_cs(i);

                if (i && i % 5 == 0)
                        printf("\n\t");
                printf("(%d,%d,%d) ",
                if (i && i % 5 == 0)
                        printf("\n\t");
                printf("(%d,%d,%d) ",


@@ -80,8 +92,10 @@ dumpcg(c)
        printf("magic\t%x\ntime\t%s", acg.cg_magic, ctime(&acg.cg_time));
        printf("cgx\t%d\nncyl\t%d\nniblk\t%d\nndblk\t%d\n",
            acg.cg_cgx, acg.cg_ncyl, acg.cg_niblk, acg.cg_ndblk);
        printf("magic\t%x\ntime\t%s", acg.cg_magic, ctime(&acg.cg_time));
        printf("cgx\t%d\nncyl\t%d\nniblk\t%d\nndblk\t%d\n",
            acg.cg_cgx, acg.cg_ncyl, acg.cg_niblk, acg.cg_ndblk);

-       printf("nifree\t%d\nndir\t%d\nnffree\t%d\nnbfree\t%d\nfrsum",
+       printf("nifree\t%d\nndir\t%d\nnffree\t%d\nnbfree\t%d\n",

            acg.cg_nifree, acg.cg_ndir, acg.cg_nffree, acg.cg_nbfree);
            acg.cg_nifree, acg.cg_ndir, acg.cg_nffree, acg.cg_nbfree);

+       printf("rotor\t%d\nirotor\t%d\nfrotor\t%d\nfrsum",
+           acg.cg_rotor, acg.cg_irotor, acg.cg_frotor);

        for (i = 1, j = 0; i < FRAG; i++) {
                printf("\t%d", acg.cg_frsum[i]);
                j += i * acg.cg_frsum[i];
        for (i = 1, j = 0; i < FRAG; i++) {
                printf("\t%d", acg.cg_frsum[i]);
                j += i * acg.cg_frsum[i];

diff --git a/usr/src/sbin/fsck/main.c b/usr/src/sbin/fsck/main.c
index 1cec331..a70a982 100644 (file)
--- a/usr/src/sbin/fsck/main.c
+++ b/usr/src/sbin/fsck/main.c
@@ -1,4 +1,4 @@
-static char *sccsid = "@(#)main.c      1.8 (Berkeley) %G%";
+static char *sccsid = "@(#)main.c      1.9 (Berkeley) %G%";

 
 #include <stdio.h>
 #include <ctype.h>
 
 #include <stdio.h>
 #include <ctype.h>


@@ -661,12 +661,16 @@ out5:
        if (fixcg) {
                if (preen == 0)
                        printf("** Phase 6 - Salvage Cylinder Groups\n");
        if (fixcg) {
                if (preen == 0)
                        printf("** Phase 6 - Salvage Cylinder Groups\n");

-               sblock.fs_cs = (struct csum *)calloc(1,
-                   roundup(cssize(&sblock), BSIZE));
+               for (i = 0; i < howmany(cssize(&sblock), BSIZE); i++) {
+                       sblock.fs_csp[i] = (struct csum *)calloc(1, BSIZE);
+                       getblk((char *)sblock.fs_csp[i],
+                              csaddr(&sblock) + (i * FRAG), BSIZE);
+               }

                makecg();
                makecg();

-               for (i = 0; i < cssize(&sblock); i += BSIZE)
-                       bwrite(&dfile, ((char *)sblock.fs_cs) + i,
-                               csaddr(&sblock) + i / BSIZE, BSIZE);
+               for (i = 0; i < howmany(cssize(&sblock), BSIZE); i++) {
+                       bwrite(&dfile, (char *)sblock.fs_csp[i],
+                              csaddr(&sblock) + (i * FRAG), BSIZE);
+               }

                n_ffree = sblock.fs_nffree;
                n_bfree = sblock.fs_nbfree;
        }
                n_ffree = sblock.fs_nffree;
                n_bfree = sblock.fs_nbfree;
        }


@@ -1454,7 +1458,7 @@ makecg()
                if (dmax > sblock.fs_size)
                        dmax = sblock.fs_size;
                dmin = cgdmin(c, &sblock) - dbase;
                if (dmax > sblock.fs_size)
                        dmax = sblock.fs_size;
                dmin = cgdmin(c, &sblock) - dbase;

-               cs = &sblock.fs_cs[c];
+               cs = &sblock.fs_cs(c);

                cgrp.cg_time = time(0);
                cgrp.cg_magic = CG_MAGIC;
                cgrp.cg_cgx = c;
                cgrp.cg_time = time(0);
                cgrp.cg_magic = CG_MAGIC;
                cgrp.cg_cgx = c;

diff --git a/usr/src/sbin/icheck/icheck.c b/usr/src/sbin/icheck/icheck.c
index be5ae15..f2ae437 100644 (file)
--- a/usr/src/sbin/icheck/icheck.c
+++ b/usr/src/sbin/icheck/icheck.c
@@ -1,4 +1,4 @@
-static char *sccsid = "@(#)icheck.c    1.5 (Berkeley) %G%";
+static char *sccsid = "@(#)icheck.c    1.6 (Berkeley) %G%";

 
 /*
  * icheck
 
 /*
  * icheck


@@ -149,10 +149,11 @@ char *file;
                nerror |= 04;
                return;
        }
                nerror |= 04;
                return;
        }

-       sblock.fs_cs =
-           (struct csum *)calloc(howmany(cssize(&sblock), BSIZE), BSIZE);
-       lseek(fi, csaddr(&sblock)*FSIZE, 0);
-       read(fi, (char *)sblock.fs_cs, cssize(&sblock));
+       for (n = 0; n < howmany(cssize(&sblock), BSIZE); n++) {
+               sblock.fs_csp[n] = (struct csum *)calloc(1, BSIZE);
+               bread(csaddr(&sblock) + (n * FRAG),
+                     (char *)sblock.fs_csp[n], BSIZE);
+       }

        ino = 0;
        n = (sblock.fs_size*FRAG + BITS-1) / BITS;
 #ifdef STANDALONE
        ino = 0;
        n = (sblock.fs_size*FRAG + BITS-1) / BITS;
 #ifdef STANDALONE


@@ -448,7 +449,7 @@ makecg()
                dmax = dbase + sblock.fs_fpg;
                if (dmax > sblock.fs_size)
                        dmax = sblock.fs_size;
                dmax = dbase + sblock.fs_fpg;
                if (dmax > sblock.fs_size)
                        dmax = sblock.fs_size;

-               cs = &sblock.fs_cs[c];
+               cs = &sblock.fs_cs(c);

                cgrp.cg_time = time((long)0);
                cgrp.cg_magic = CG_MAGIC;
                cgrp.cg_cgx = c;
                cgrp.cg_time = time((long)0);
                cgrp.cg_magic = CG_MAGIC;
                cgrp.cg_cgx = c;


@@ -524,7 +525,8 @@ makecg()
        sblock.fs_ronly = 0;
        sblock.fs_fmod = 0;
        bwrite(SBLOCK, (char *)&sblock, sizeof (sblock));
        sblock.fs_ronly = 0;
        sblock.fs_fmod = 0;
        bwrite(SBLOCK, (char *)&sblock, sizeof (sblock));

-       lseek(fi, csaddr(&sblock) * FSIZE, 0);
-       if (write(fi,(char *)sblock.fs_cs,cssize(&sblock)) != cssize(&sblock))
-               printf("write error %d\n", tell(fi)/BSIZE);
+       for (i = 0; i < howmany(cssize(&sblock), BSIZE); i++) {
+               bwrite(csaddr(&sblock) + (i * FRAG),
+                     (char *)sblock.fs_csp[i], BSIZE);
+       }

 }
 }

diff --git a/usr/src/sbin/newfs/mkfs.c b/usr/src/sbin/newfs/mkfs.c
index 0a0ae74..a5436de 100644 (file)
--- a/usr/src/sbin/newfs/mkfs.c
+++ b/usr/src/sbin/newfs/mkfs.c
@@ -1,4 +1,4 @@
-static char *sccsid = "@(#)mkfs.c      1.7 (Berkeley) %G%";
+static char *sccsid = "@(#)mkfs.c      1.8 (Berkeley) %G%";

 
 /*
  * make file system for cylinder-group style file systems
 
 /*
  * make file system for cylinder-group style file systems


@@ -280,6 +280,16 @@ noinit:
         */
        sblock.fs_nffree = 0;
        sblock.fs_nbfree = 0;
         */
        sblock.fs_nffree = 0;
        sblock.fs_nbfree = 0;

+       sblock.fs_cgrotor = 0;
+       for (i = 0; i < NRPOS; i++)
+               sblock.fs_postbl[i] = -1;
+       for (i = 0; i < sblock.fs_spc; i += (NSPF * FRAG))
+               /* void */;
+       for (i -= (NSPF * FRAG); i >= 0; i -= (NSPF * FRAG)) {
+               c = i % sblock.fs_nsect * NRPOS / sblock.fs_nsect;
+               sblock.fs_rotbl[i / (NSPF * FRAG)] = sblock.fs_postbl[c];
+               sblock.fs_postbl[c] = i / (NSPF * FRAG);
+       }

        for (c = 0; c < sblock.fs_ncg; c++)
                initcg(c);
        printf("\tsuper-block backups (for fsck -b#) at %d+k*%d (%d .. %d)\n",
        for (c = 0; c < sblock.fs_ncg; c++)
                initcg(c);
        printf("\tsuper-block backups (for fsck -b#) at %d+k*%d (%d .. %d)\n",

diff --git a/usr/src/sys/ufs/ffs/ffs_alloc.c b/usr/src/sys/ufs/ffs/ffs_alloc.c
index 43d173f..3c11738 100644 (file)
--- a/usr/src/sys/ufs/ffs/ffs_alloc.c
+++ b/usr/src/sys/ufs/ffs/ffs_alloc.c
@@ -1,6 +1,6 @@
 /* Copyright (c) 1981 Regents of the University of California */
 
 /* Copyright (c) 1981 Regents of the University of California */
 

-static char vers[] = "@(#)ffs_alloc.c 1.6 %G%";
+static char vers[] = "@(#)ffs_alloc.c 1.7 %G%";

 
 /*     alloc.c 4.8     81/03/08        */
 
 
 /*     alloc.c 4.8     81/03/08        */
 


@@ -15,8 +15,12 @@ static char vers[] = "@(#)ffs_alloc.c 1.6 %G%";
 #include "../h/user.h"
 
 extern long            hashalloc();
 #include "../h/user.h"
 
 extern long            hashalloc();

-extern long            alloccg();

 extern long            ialloccg();
 extern long            ialloccg();

+extern daddr_t         alloccg();
+extern daddr_t         alloccgblk();
+extern daddr_t         fragextend();
+extern daddr_t         blkpref();
+extern daddr_t         mapsearch();

 extern int             inside[], around[];
 extern unsigned char   fragtbl[];
 
 extern int             inside[], around[];
 extern unsigned char   fragtbl[];
 


@@ -35,7 +39,9 @@ alloc(dev, ip, bpref, size)
        if ((unsigned)size > BSIZE || size % FSIZE != 0)
                panic("alloc: bad size");
        fs = getfs(dev);
        if ((unsigned)size > BSIZE || size % FSIZE != 0)
                panic("alloc: bad size");
        fs = getfs(dev);

-       if (fs->fs_nbfree == 0 && size == BSIZE)
+       if (size == BSIZE &&
+           (fs->fs_nbfree == 0 ||
+           (!suser() && fs->fs_nbfree < fs->fs_nbfree * minfree / 100)))

                goto nospace;
        if (bpref == 0)
                cg = itog(ip->i_number, fs);
                goto nospace;
        if (bpref == 0)
                cg = itog(ip->i_number, fs);


@@ -55,10 +61,10 @@ nospace:
 }
 
 struct buf *
 }
 
 struct buf *

-realloccg(dev, ip, bprev, osize, nsize)
+realloccg(dev, ip, bprev, bpref, osize, nsize)

        dev_t dev;
        register struct inode *ip;
        dev_t dev;
        register struct inode *ip;

-       daddr_t bprev;
+       daddr_t bprev, bpref;

        int osize, nsize;
 {
        daddr_t bno;
        int osize, nsize;
 {
        daddr_t bno;


@@ -82,7 +88,7 @@ realloccg(dev, ip, bprev, osize, nsize)
                blkclr(bp->b_un.b_addr + osize, nsize - osize);
                return (bp);
        }
                blkclr(bp->b_un.b_addr + osize, nsize - osize);
                return (bp);
        }

-       bno = hashalloc(dev, fs, cg, (long)bprev, nsize, alloccg);
+       bno = hashalloc(dev, fs, cg, (long)bpref, nsize, alloccg);

        if (bno != 0) {
                /*
                 * make a new copy
        if (bno != 0) {
                /*
                 * make a new copy


@@ -140,25 +146,52 @@ noinodes:
        return (NULL);
 }
 
        return (NULL);
 }
 

-dipref(dev)
+/*
+ * find a cylinder to place a directory
+ */
+dirpref(dev)

        dev_t dev;
 {
        register struct fs *fs;
        dev_t dev;
 {
        register struct fs *fs;

-       int cg, minndir, mincg;
+       int cg, minndir, mincg, avgifree;

 
        fs = getfs(dev);
 
        fs = getfs(dev);

-       minndir = fs->fs_cs[0].cs_ndir;
+       avgifree = fs->fs_nifree / fs->fs_ncg;
+       minndir = fs->fs_ipg;

        mincg = 0;
        mincg = 0;

-       for (cg = 1; cg < fs->fs_ncg; cg++)
-               if (fs->fs_cs[cg].cs_ndir < minndir) {
+       for (cg = 0; cg < fs->fs_ncg; cg++)
+               if (fs->fs_cs(cg).cs_ndir < minndir &&
+                   fs->fs_cs(cg).cs_nifree >= avgifree) {

                        mincg = cg;
                        mincg = cg;

-                       minndir = fs->fs_cs[cg].cs_ndir;
-                       if (minndir == 0)
-                               break;
+                       minndir = fs->fs_cs(cg).cs_ndir;

                }
        return (fs->fs_ipg * mincg);
 }
 
                }
        return (fs->fs_ipg * mincg);
 }
 

+/*
+ * select a cylinder to place a large block of data
+ */
+blkpref(dev)
+       dev_t dev;
+{
+       register struct fs *fs;
+       int cg, avgbfree;
+
+       fs = getfs(dev);
+       avgbfree = fs->fs_nbfree / fs->fs_ncg;
+       for (cg = fs->fs_cgrotor + 1; cg < fs->fs_ncg; cg++)
+               if (fs->fs_cs(cg).cs_nbfree >= avgbfree) {
+                       fs->fs_cgrotor = cg;
+                       return (fs->fs_fpg * cg + FRAG);
+               }
+       for (cg = 0; cg <= fs->fs_cgrotor; cg++)
+               if (fs->fs_cs(cg).cs_nbfree >= avgbfree) {
+                       fs->fs_cgrotor = cg;
+                       return (fs->fs_fpg * cg + FRAG);
+               }
+       return (0);
+}
+

 long
 hashalloc(dev, fs, cg, pref, size, allocator)
        dev_t dev;
 long
 hashalloc(dev, fs, cg, pref, size, allocator)
        dev_t dev;


@@ -270,8 +303,6 @@ alloccg(dev, fs, cg, bpref, size)
        register struct cg *cgp;
        int bno, frags;
        int allocsiz;
        register struct cg *cgp;
        int bno, frags;
        int allocsiz;

-       int start, len, loc;
-       int blk, field, subfield, pos;

        register int i;
 
        bp = bread(dev, cgtod(cg, fs), BSIZE);
        register int i;
 
        bp = bread(dev, cgtod(cg, fs), BSIZE);


@@ -316,46 +347,9 @@ alloccg(dev, fs, cg, bpref, size)
                bdwrite(bp);
                return (bno);
        }
                bdwrite(bp);
                return (bno);
        }

-       /*
-        * find the fragment by searching through the free block
-        * map for an appropriate bit pattern
-        */
-       if (bpref)
-               start = bpref % fs->fs_fpg / NBBY;
-       else
-               start = cgp->cg_frotor / NBBY;
-       len = roundup(fs->fs_fpg - 1, NBBY) / NBBY - start;
-       loc = scanc(len, &cgp->cg_free[start], fragtbl, 1 << (allocsiz - 1));
-       if (loc == 0) {
-               len = start - 1;
-               start = (cgdmin(cg, fs) - cgbase(cg, fs)) / NBBY;
-               loc = scanc(len, &cgp->cg_free[start], fragtbl,
-                       1 << (allocsiz - 1));
-               if (loc == 0)
-                       panic("alloccg: can't find frag");
-       }
-       bno = (start + len - loc) * NBBY;
-       cgp->cg_frotor = bno;
-       /*
-        * found the byte in the map
-        * sift through the bits to find the selected frag
-        */
-       for (i = 0; i < NBBY; i += FRAG) {
-               blk = (cgp->cg_free[bno / NBBY] >> i) & (0xff >> NBBY - FRAG);
-               blk <<= 1;
-               field = around[allocsiz];
-               subfield = inside[allocsiz];
-               for (pos = 0; pos <= FRAG - allocsiz; pos++) {
-                       if ((blk & field) == subfield) {
-                               bno += i + pos;
-                               goto gotit;
-                       }
-                       field <<= 1;
-                       subfield <<= 1;
-               }
-       }
-       panic("alloccg: frag not in block");
-gotit:
+       bno = mapsearch(fs, cgp, bpref, allocsiz);
+       if (bno == 0)
+               return (0);

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


@@ -374,35 +368,64 @@ alloccgblk(dev, fs, cgp, bpref)
        register struct cg *cgp;
        daddr_t bpref;
 {
        register struct cg *cgp;
        daddr_t bpref;
 {

-       register int i;
+       daddr_t bno;
+       int cylno, pos;
+       short *cylbp;
+       int i, j;

 
 

-       if (bpref) {
+       if (bpref == 0) {
+               bpref = cgp->cg_rotor;
+       } else {

                bpref &= ~(FRAG - 1);
                bpref %= fs->fs_fpg;
                bpref &= ~(FRAG - 1);
                bpref %= fs->fs_fpg;

-               if (isblock(cgp->cg_free, bpref/FRAG))
-                       goto gotit;
-       } else
-               bpref = cgp->cg_rotor;
-       for (i = 0; i < cgp->cg_ndblk; i += FRAG) {
-               bpref += FRAG;
-               if (bpref >= cgp->cg_ndblk)
-                       bpref = 0;
+               /*
+                * if the requested block is available, use it
+                */

                if (isblock(cgp->cg_free, bpref/FRAG)) {
                if (isblock(cgp->cg_free, bpref/FRAG)) {

-                       cgp->cg_rotor = bpref;
+                       bno = bpref;

                        goto gotit;
                }
                        goto gotit;
                }

+               /*
+                * check for a block available on the same cylinder
+                * beginning with one which is rotationally optimal
+                */
+               i = bpref * NSPF;
+               cylno = i / fs->fs_spc;
+               cylbp = cgp->cg_b[cylno];
+               pos = (i + (ROTDELAY == 0) ?
+                       0 : 1 + ROTDELAY * HZ * fs->fs_nsect / (NSPF * 1000)) %
+                       fs->fs_nsect * NRPOS / fs->fs_nsect;
+               for (i = pos; i < NRPOS; i++)
+                       if (cylbp[i] > 0)
+                               break;
+               if (i == NRPOS)
+                       for (i = 0; i < pos; i++)
+                               if (cylbp[i] > 0)
+                                       break;
+               if (cylbp[i] > 0) {
+                       bpref = cylno * fs->fs_spc / (NSPF * FRAG);
+                       for (j = fs->fs_postbl[i]; j > -1; j = fs->fs_rotbl[j]) {
+                               if (isblock(cgp->cg_free, bpref + j)) {
+                                       bno = (bpref + j) * FRAG;
+                                       goto gotit;
+                               }
+                       }
+                       panic("alloccgblk: can't find blk in cyl");
+               }

        }
        }

-       panic("alloccgblk: can't find a blk");
-       return (0);
+       bno = mapsearch(fs, cgp, bpref, FRAG);
+       if (bno == 0)
+               return (0);
+       cgp->cg_rotor = bno;

 gotit:
 gotit:

-       clrblock(cgp->cg_free, bpref/FRAG);
+       clrblock(cgp->cg_free, bno/FRAG);

        cgp->cg_nbfree--;
        fs->fs_nbfree--;
        cgp->cg_nbfree--;
        fs->fs_nbfree--;

-       fs->fs_cs[cgp->cg_cgx].cs_nbfree--;
-       i = bpref * NSPF;
+       fs->fs_cs(cgp->cg_cgx).cs_nbfree--;
+       i = bno * NSPF;

        cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]--;
        fs->fs_fmod++;
        cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]--;
        fs->fs_fmod++;

-       return (cgp->cg_cgx * fs->fs_fpg + bpref);
+       return (cgp->cg_cgx * fs->fs_fpg + bno);

 }
        
 long
 }
        
 long


@@ -446,11 +469,11 @@ gotit:
        setbit(cgp->cg_iused, ipref);
        cgp->cg_nifree--;
        fs->fs_nifree--;
        setbit(cgp->cg_iused, ipref);
        cgp->cg_nifree--;
        fs->fs_nifree--;

-       fs->fs_cs[cg].cs_nifree--;
+       fs->fs_cs(cg).cs_nifree--;

        fs->fs_fmod++;
        if ((mode & IFMT) == IFDIR) {
                cgp->cg_ndir++;
        fs->fs_fmod++;
        if ((mode & IFMT) == IFDIR) {
                cgp->cg_ndir++;

-               fs->fs_cs[cg].cs_ndir++;
+               fs->fs_cs(cg).cs_ndir++;

        }
        bdwrite(bp);
        return (cg * fs->fs_ipg + ipref);
        }
        bdwrite(bp);
        return (cg * fs->fs_ipg + ipref);


@@ -484,7 +507,7 @@ fre(dev, bno, size)
                setblock(cgp->cg_free, bno/FRAG);
                cgp->cg_nbfree++;
                fs->fs_nbfree++;
                setblock(cgp->cg_free, bno/FRAG);
                cgp->cg_nbfree++;
                fs->fs_nbfree++;

-               fs->fs_cs[cg].cs_nbfree++;
+               fs->fs_cs(cg).cs_nbfree++;

                i = bno * NSPF;
                cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]++;
        } else {
                i = bno * NSPF;
                cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]++;
        } else {


@@ -520,7 +543,7 @@ fre(dev, bno, size)
                        fs->fs_nffree -= FRAG;
                        cgp->cg_nbfree++;
                        fs->fs_nbfree++;
                        fs->fs_nffree -= FRAG;
                        cgp->cg_nbfree++;
                        fs->fs_nbfree++;

-                       fs->fs_cs[cg].cs_nbfree++;
+                       fs->fs_cs(cg).cs_nbfree++;

                        i = bbase * NSPF;
                        cgp->cg_b[i / fs->fs_spc]
                                 [i % fs->fs_nsect * NRPOS / fs->fs_nsect]++;
                        i = bbase * NSPF;
                        cgp->cg_b[i / fs->fs_spc]
                                 [i % fs->fs_nsect * NRPOS / fs->fs_nsect]++;


@@ -555,15 +578,75 @@ ifree(dev, ino, mode)
        clrbit(cgp->cg_iused, ino);
        cgp->cg_nifree++;
        fs->fs_nifree++;
        clrbit(cgp->cg_iused, ino);
        cgp->cg_nifree++;
        fs->fs_nifree++;

-       fs->fs_cs[cg].cs_nifree++;
+       fs->fs_cs(cg).cs_nifree++;

        if ((mode & IFMT) == IFDIR) {
                cgp->cg_ndir--;
        if ((mode & IFMT) == IFDIR) {
                cgp->cg_ndir--;

-               fs->fs_cs[cg].cs_ndir--;
+               fs->fs_cs(cg).cs_ndir--;

        }
        fs->fs_fmod++;
        bdwrite(bp);
 }
 
        }
        fs->fs_fmod++;
        bdwrite(bp);
 }
 

+/*
+ * find a block of the specified size in the specified cylinder group
+ * It is a panic if a request is made to find a block if none are
+ * available.
+ */
+daddr_t
+mapsearch(fs, cgp, bpref, allocsiz)
+       register struct fs *fs;
+       register struct cg *cgp;
+       daddr_t bpref;
+       int allocsiz;
+{
+       daddr_t bno;
+       int start, len, loc, i;
+       int blk, field, subfield, pos;
+
+       /*
+        * find the fragment by searching through the free block
+        * map for an appropriate bit pattern
+        */
+       if (bpref)
+               start = bpref % fs->fs_fpg / NBBY;
+       else
+               start = cgp->cg_frotor / NBBY;
+       len = roundup(fs->fs_fpg - 1, NBBY) / NBBY - start;
+       loc = scanc(len, &cgp->cg_free[start], fragtbl, 1 << (allocsiz - 1));
+       if (loc == 0) {
+               len = start - 1;
+               start = (cgdmin(cgp->cg_cgx, fs) -
+                        cgbase(cgp->cg_cgx, fs)) / NBBY;
+               loc = scanc(len, &cgp->cg_free[start], fragtbl,
+                       1 << (allocsiz - 1));
+               if (loc == 0) {
+                       panic("alloccg: map corrupted");
+                       return (0);
+               }
+       }
+       bno = (start + len - loc) * NBBY;
+       cgp->cg_frotor = bno;
+       /*
+        * found the byte in the map
+        * sift through the bits to find the selected frag
+        */
+       for (i = 0; i < NBBY; i += FRAG) {
+               blk = (cgp->cg_free[bno / NBBY] >> i) & (0xff >> NBBY - FRAG);
+               blk <<= 1;
+               field = around[allocsiz];
+               subfield = inside[allocsiz];
+               for (pos = 0; pos <= FRAG - allocsiz; pos++) {
+                       if ((blk & field) == subfield) {
+                               return (bno + i + pos);
+                       }
+                       field <<= 1;
+                       subfield <<= 1;
+               }
+       }
+       panic("alloccg: block not in map");
+       return (0);
+}
+

 /*
  * update the frsum fields to reflect addition or deletion 
  * of some frags
 /*
  * update the frsum fields to reflect addition or deletion 
  * of some frags


@@ -690,7 +773,7 @@ update()
        register struct buf *bp;
        struct fs *fs;
        time_t tim;
        register struct buf *bp;
        struct fs *fs;
        time_t tim;

-       int i;
+       int i, blks;

 
        if (updlock)
                return;
 
        if (updlock)
                return;


@@ -713,10 +796,10 @@ update()
                        if (bp->b_un.b_fs != fs)
                                panic("update: bad b_fs");
                        bwrite(bp);
                        if (bp->b_un.b_fs != fs)
                                panic("update: bad b_fs");
                        bwrite(bp);

-                       for (i = 0; i < cssize(fs); i += BSIZE) {
-                               bp = getblk(mp->m_dev, csaddr(fs) + i / FSIZE,
+                       blks = howmany(cssize(fs), BSIZE);
+                       for (i = 0; i < blks; i++) {
+                               bp = getblk(mp->m_dev, csaddr(fs) + (i * FRAG),

                                        BSIZE);
                                        BSIZE);

-                               bcopy(fs->fs_cs + i, bp->b_un.b_addr, BSIZE);

                                bwrite(bp);
                        }
                }
                                bwrite(bp);
                        }
                }

diff --git a/usr/src/sys/ufs/ffs/fs.h b/usr/src/sys/ufs/ffs/fs.h
index ba41762..d87b42b 100644 (file)
--- a/usr/src/sys/ufs/ffs/fs.h
+++ b/usr/src/sys/ufs/ffs/fs.h
@@ -1,6 +1,6 @@
 /* Copyright (c) 1981 Regents of the University of California */
 
 /* Copyright (c) 1981 Regents of the University of California */
 

-/*     fs.h    1.3     %G%     */
+/*     fs.h    1.4     %G%     */

 
 /*
  * Each disk drive contains some number of file systems.
 
 /*
  * Each disk drive contains some number of file systems.


@@ -45,7 +45,14 @@
  *
  * The file system records space availability at the fragment level;
  * to determine block availability, aligned fragments are examined.
  *
  * The file system records space availability at the fragment level;
  * to determine block availability, aligned fragments are examined.

- */ 
+ *
+ * For each cylinder we keep track of the availability of blocks at different
+ * rotational positions, so that we can lay out the data to be picked
+ * up with minimum rotational latency.  NRPOS is the number of rotational
+ * positions which we distinguish.  With NRPOS 8 the resolution of our
+ * summary information is 2ms for a typical 3600 rpm drive.
+ */
+#define        NRPOS   8               /* number distinct rotational positions */

 
 /*
  * Information per cylinder group summarized in blocks allocated
 
 /*
  * Information per cylinder group summarized in blocks allocated


@@ -74,8 +81,8 @@ struct csum {
  */
 #define        NBPI    2048
 
  */
 #define        NBPI    2048
 

-#define        DESCPG  8                       /* desired fs_cpg */
-#define        MAXCPG  16                      /* maximum fs_cpg */
+#define        DESCPG  16                      /* desired fs_cpg */
+#define        MAXCPG  32                      /* maximum fs_cpg */

 /* MAXCPG is limited only to dimension an array in (struct cg); */
 /* it can be made larger as long as that structures size remains sane. */
  
 /* MAXCPG is limited only to dimension an array in (struct cg); */
 /* it can be made larger as long as that structures size remains sane. */
  


@@ -117,8 +124,15 @@ struct     fs
        char    fs_fmod;                /* super block modified flag */
        char    fs_ronly;               /* mounted read-only flag */
        char    fs_fsmnt[32];           /* name mounted on */
        char    fs_fmod;                /* super block modified flag */
        char    fs_ronly;               /* mounted read-only flag */
        char    fs_fsmnt[32];           /* name mounted on */

-       struct  csum *fs_cs;
+/* these fields retain the current block allocation info */
+       short   fs_cgrotor;             /* last cg searched */
+       struct  csum *fs_csp[NBUF];     /* list of fs_cs info buffers */
+       short   fs_postbl[NRPOS];       /* head of blocks for each rotation */
+       short   fs_rotbl[1];            /* list of blocks for each rotation */
+/* actually longer */

 };
 };

+#define fs_cs(indx) fs_csp[(indx) / (BSIZE / sizeof(struct csum))] \
+                         [(indx) % (BSIZE / sizeof(struct csum))]

 
 /*
  * Cylinder group macros to locate things in cylinder groups.
 
 /*
  * Cylinder group macros to locate things in cylinder groups.


@@ -161,15 +175,6 @@ struct     fs
  * Cylinder group related limits.
  */
 
  * Cylinder group related limits.
  */
 

-/*
- * For each cylinder we keep track of the availability of blocks at different
- * rotational positions, so that we can lay out the data to be picked
- * up with minimum rotational latency.  NRPOS is the number of rotational
- * positions which we distinguish.  With NRPOS 16 the resolution of our
- * summary information is 1ms for a typical 3600 rpm drive.
- */
-#define        NRPOS   16              /* number distinct rotational positions */
-

 /*
  * MAXIPG bounds the number of inodes per cylinder group, and
  * is needed only to keep the structure simpler by having the
 /*
  * MAXIPG bounds the number of inodes per cylinder group, and
  * is needed only to keep the structure simpler by having the


@@ -212,6 +217,4 @@ struct      cg {
 
 #ifdef KERNEL
 struct fs *getfs();
 
 #ifdef KERNEL
 struct fs *getfs();

-int inside[], around[];
-unsigned char fragtbl[];

 #endif
 #endif

diff --git a/usr/src/sys/ufs/lfs/lfs_alloc.c b/usr/src/sys/ufs/lfs/lfs_alloc.c
index 6633e7a..d51505b 100644 (file)
--- a/usr/src/sys/ufs/lfs/lfs_alloc.c
+++ b/usr/src/sys/ufs/lfs/lfs_alloc.c
@@ -1,6 +1,6 @@
 /* Copyright (c) 1981 Regents of the University of California */
 
 /* Copyright (c) 1981 Regents of the University of California */
 

-static char vers[] = "@(#)lfs_alloc.c 1.6 %G%";
+static char vers[] = "@(#)lfs_alloc.c 1.7 %G%";

 
 /*     alloc.c 4.8     81/03/08        */
 
 
 /*     alloc.c 4.8     81/03/08        */
 


@@ -15,8 +15,12 @@ static char vers[] = "@(#)lfs_alloc.c 1.6 %G%";
 #include "../h/user.h"
 
 extern long            hashalloc();
 #include "../h/user.h"
 
 extern long            hashalloc();

-extern long            alloccg();

 extern long            ialloccg();
 extern long            ialloccg();

+extern daddr_t         alloccg();
+extern daddr_t         alloccgblk();
+extern daddr_t         fragextend();
+extern daddr_t         blkpref();
+extern daddr_t         mapsearch();

 extern int             inside[], around[];
 extern unsigned char   fragtbl[];
 
 extern int             inside[], around[];
 extern unsigned char   fragtbl[];
 


@@ -35,7 +39,9 @@ alloc(dev, ip, bpref, size)
        if ((unsigned)size > BSIZE || size % FSIZE != 0)
                panic("alloc: bad size");
        fs = getfs(dev);
        if ((unsigned)size > BSIZE || size % FSIZE != 0)
                panic("alloc: bad size");
        fs = getfs(dev);

-       if (fs->fs_nbfree == 0 && size == BSIZE)
+       if (size == BSIZE &&
+           (fs->fs_nbfree == 0 ||
+           (!suser() && fs->fs_nbfree < fs->fs_nbfree * minfree / 100)))

                goto nospace;
        if (bpref == 0)
                cg = itog(ip->i_number, fs);
                goto nospace;
        if (bpref == 0)
                cg = itog(ip->i_number, fs);


@@ -55,10 +61,10 @@ nospace:
 }
 
 struct buf *
 }
 
 struct buf *

-realloccg(dev, ip, bprev, osize, nsize)
+realloccg(dev, ip, bprev, bpref, osize, nsize)

        dev_t dev;
        register struct inode *ip;
        dev_t dev;
        register struct inode *ip;

-       daddr_t bprev;
+       daddr_t bprev, bpref;

        int osize, nsize;
 {
        daddr_t bno;
        int osize, nsize;
 {
        daddr_t bno;


@@ -82,7 +88,7 @@ realloccg(dev, ip, bprev, osize, nsize)
                blkclr(bp->b_un.b_addr + osize, nsize - osize);
                return (bp);
        }
                blkclr(bp->b_un.b_addr + osize, nsize - osize);
                return (bp);
        }

-       bno = hashalloc(dev, fs, cg, (long)bprev, nsize, alloccg);
+       bno = hashalloc(dev, fs, cg, (long)bpref, nsize, alloccg);

        if (bno != 0) {
                /*
                 * make a new copy
        if (bno != 0) {
                /*
                 * make a new copy


@@ -140,25 +146,52 @@ noinodes:
        return (NULL);
 }
 
        return (NULL);
 }
 

-dipref(dev)
+/*
+ * find a cylinder to place a directory
+ */
+dirpref(dev)

        dev_t dev;
 {
        register struct fs *fs;
        dev_t dev;
 {
        register struct fs *fs;

-       int cg, minndir, mincg;
+       int cg, minndir, mincg, avgifree;

 
        fs = getfs(dev);
 
        fs = getfs(dev);

-       minndir = fs->fs_cs[0].cs_ndir;
+       avgifree = fs->fs_nifree / fs->fs_ncg;
+       minndir = fs->fs_ipg;

        mincg = 0;
        mincg = 0;

-       for (cg = 1; cg < fs->fs_ncg; cg++)
-               if (fs->fs_cs[cg].cs_ndir < minndir) {
+       for (cg = 0; cg < fs->fs_ncg; cg++)
+               if (fs->fs_cs(cg).cs_ndir < minndir &&
+                   fs->fs_cs(cg).cs_nifree >= avgifree) {

                        mincg = cg;
                        mincg = cg;

-                       minndir = fs->fs_cs[cg].cs_ndir;
-                       if (minndir == 0)
-                               break;
+                       minndir = fs->fs_cs(cg).cs_ndir;

                }
        return (fs->fs_ipg * mincg);
 }
 
                }
        return (fs->fs_ipg * mincg);
 }
 

+/*
+ * select a cylinder to place a large block of data
+ */
+blkpref(dev)
+       dev_t dev;
+{
+       register struct fs *fs;
+       int cg, avgbfree;
+
+       fs = getfs(dev);
+       avgbfree = fs->fs_nbfree / fs->fs_ncg;
+       for (cg = fs->fs_cgrotor + 1; cg < fs->fs_ncg; cg++)
+               if (fs->fs_cs(cg).cs_nbfree >= avgbfree) {
+                       fs->fs_cgrotor = cg;
+                       return (fs->fs_fpg * cg + FRAG);
+               }
+       for (cg = 0; cg <= fs->fs_cgrotor; cg++)
+               if (fs->fs_cs(cg).cs_nbfree >= avgbfree) {
+                       fs->fs_cgrotor = cg;
+                       return (fs->fs_fpg * cg + FRAG);
+               }
+       return (0);
+}
+

 long
 hashalloc(dev, fs, cg, pref, size, allocator)
        dev_t dev;
 long
 hashalloc(dev, fs, cg, pref, size, allocator)
        dev_t dev;


@@ -270,8 +303,6 @@ alloccg(dev, fs, cg, bpref, size)
        register struct cg *cgp;
        int bno, frags;
        int allocsiz;
        register struct cg *cgp;
        int bno, frags;
        int allocsiz;

-       int start, len, loc;
-       int blk, field, subfield, pos;

        register int i;
 
        bp = bread(dev, cgtod(cg, fs), BSIZE);
        register int i;
 
        bp = bread(dev, cgtod(cg, fs), BSIZE);


@@ -316,46 +347,9 @@ alloccg(dev, fs, cg, bpref, size)
                bdwrite(bp);
                return (bno);
        }
                bdwrite(bp);
                return (bno);
        }

-       /*
-        * find the fragment by searching through the free block
-        * map for an appropriate bit pattern
-        */
-       if (bpref)
-               start = bpref % fs->fs_fpg / NBBY;
-       else
-               start = cgp->cg_frotor / NBBY;
-       len = roundup(fs->fs_fpg - 1, NBBY) / NBBY - start;
-       loc = scanc(len, &cgp->cg_free[start], fragtbl, 1 << (allocsiz - 1));
-       if (loc == 0) {
-               len = start - 1;
-               start = (cgdmin(cg, fs) - cgbase(cg, fs)) / NBBY;
-               loc = scanc(len, &cgp->cg_free[start], fragtbl,
-                       1 << (allocsiz - 1));
-               if (loc == 0)
-                       panic("alloccg: can't find frag");
-       }
-       bno = (start + len - loc) * NBBY;
-       cgp->cg_frotor = bno;
-       /*
-        * found the byte in the map
-        * sift through the bits to find the selected frag
-        */
-       for (i = 0; i < NBBY; i += FRAG) {
-               blk = (cgp->cg_free[bno / NBBY] >> i) & (0xff >> NBBY - FRAG);
-               blk <<= 1;
-               field = around[allocsiz];
-               subfield = inside[allocsiz];
-               for (pos = 0; pos <= FRAG - allocsiz; pos++) {
-                       if ((blk & field) == subfield) {
-                               bno += i + pos;
-                               goto gotit;
-                       }
-                       field <<= 1;
-                       subfield <<= 1;
-               }
-       }
-       panic("alloccg: frag not in block");
-gotit:
+       bno = mapsearch(fs, cgp, bpref, allocsiz);
+       if (bno == 0)
+               return (0);

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


@@ -374,35 +368,64 @@ alloccgblk(dev, fs, cgp, bpref)
        register struct cg *cgp;
        daddr_t bpref;
 {
        register struct cg *cgp;
        daddr_t bpref;
 {

-       register int i;
+       daddr_t bno;
+       int cylno, pos;
+       short *cylbp;
+       int i, j;

 
 

-       if (bpref) {
+       if (bpref == 0) {
+               bpref = cgp->cg_rotor;
+       } else {

                bpref &= ~(FRAG - 1);
                bpref %= fs->fs_fpg;
                bpref &= ~(FRAG - 1);
                bpref %= fs->fs_fpg;

-               if (isblock(cgp->cg_free, bpref/FRAG))
-                       goto gotit;
-       } else
-               bpref = cgp->cg_rotor;
-       for (i = 0; i < cgp->cg_ndblk; i += FRAG) {
-               bpref += FRAG;
-               if (bpref >= cgp->cg_ndblk)
-                       bpref = 0;
+               /*
+                * if the requested block is available, use it
+                */

                if (isblock(cgp->cg_free, bpref/FRAG)) {
                if (isblock(cgp->cg_free, bpref/FRAG)) {

-                       cgp->cg_rotor = bpref;
+                       bno = bpref;

                        goto gotit;
                }
                        goto gotit;
                }

+               /*
+                * check for a block available on the same cylinder
+                * beginning with one which is rotationally optimal
+                */
+               i = bpref * NSPF;
+               cylno = i / fs->fs_spc;
+               cylbp = cgp->cg_b[cylno];
+               pos = (i + (ROTDELAY == 0) ?
+                       0 : 1 + ROTDELAY * HZ * fs->fs_nsect / (NSPF * 1000)) %
+                       fs->fs_nsect * NRPOS / fs->fs_nsect;
+               for (i = pos; i < NRPOS; i++)
+                       if (cylbp[i] > 0)
+                               break;
+               if (i == NRPOS)
+                       for (i = 0; i < pos; i++)
+                               if (cylbp[i] > 0)
+                                       break;
+               if (cylbp[i] > 0) {
+                       bpref = cylno * fs->fs_spc / (NSPF * FRAG);
+                       for (j = fs->fs_postbl[i]; j > -1; j = fs->fs_rotbl[j]) {
+                               if (isblock(cgp->cg_free, bpref + j)) {
+                                       bno = (bpref + j) * FRAG;
+                                       goto gotit;
+                               }
+                       }
+                       panic("alloccgblk: can't find blk in cyl");
+               }

        }
        }

-       panic("alloccgblk: can't find a blk");
-       return (0);
+       bno = mapsearch(fs, cgp, bpref, FRAG);
+       if (bno == 0)
+               return (0);
+       cgp->cg_rotor = bno;

 gotit:
 gotit:

-       clrblock(cgp->cg_free, bpref/FRAG);
+       clrblock(cgp->cg_free, bno/FRAG);

        cgp->cg_nbfree--;
        fs->fs_nbfree--;
        cgp->cg_nbfree--;
        fs->fs_nbfree--;

-       fs->fs_cs[cgp->cg_cgx].cs_nbfree--;
-       i = bpref * NSPF;
+       fs->fs_cs(cgp->cg_cgx).cs_nbfree--;
+       i = bno * NSPF;

        cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]--;
        fs->fs_fmod++;
        cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]--;
        fs->fs_fmod++;

-       return (cgp->cg_cgx * fs->fs_fpg + bpref);
+       return (cgp->cg_cgx * fs->fs_fpg + bno);

 }
        
 long
 }
        
 long


@@ -446,11 +469,11 @@ gotit:
        setbit(cgp->cg_iused, ipref);
        cgp->cg_nifree--;
        fs->fs_nifree--;
        setbit(cgp->cg_iused, ipref);
        cgp->cg_nifree--;
        fs->fs_nifree--;

-       fs->fs_cs[cg].cs_nifree--;
+       fs->fs_cs(cg).cs_nifree--;

        fs->fs_fmod++;
        if ((mode & IFMT) == IFDIR) {
                cgp->cg_ndir++;
        fs->fs_fmod++;
        if ((mode & IFMT) == IFDIR) {
                cgp->cg_ndir++;

-               fs->fs_cs[cg].cs_ndir++;
+               fs->fs_cs(cg).cs_ndir++;

        }
        bdwrite(bp);
        return (cg * fs->fs_ipg + ipref);
        }
        bdwrite(bp);
        return (cg * fs->fs_ipg + ipref);


@@ -484,7 +507,7 @@ fre(dev, bno, size)
                setblock(cgp->cg_free, bno/FRAG);
                cgp->cg_nbfree++;
                fs->fs_nbfree++;
                setblock(cgp->cg_free, bno/FRAG);
                cgp->cg_nbfree++;
                fs->fs_nbfree++;

-               fs->fs_cs[cg].cs_nbfree++;
+               fs->fs_cs(cg).cs_nbfree++;

                i = bno * NSPF;
                cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]++;
        } else {
                i = bno * NSPF;
                cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]++;
        } else {


@@ -520,7 +543,7 @@ fre(dev, bno, size)
                        fs->fs_nffree -= FRAG;
                        cgp->cg_nbfree++;
                        fs->fs_nbfree++;
                        fs->fs_nffree -= FRAG;
                        cgp->cg_nbfree++;
                        fs->fs_nbfree++;

-                       fs->fs_cs[cg].cs_nbfree++;
+                       fs->fs_cs(cg).cs_nbfree++;

                        i = bbase * NSPF;
                        cgp->cg_b[i / fs->fs_spc]
                                 [i % fs->fs_nsect * NRPOS / fs->fs_nsect]++;
                        i = bbase * NSPF;
                        cgp->cg_b[i / fs->fs_spc]
                                 [i % fs->fs_nsect * NRPOS / fs->fs_nsect]++;


@@ -555,15 +578,75 @@ ifree(dev, ino, mode)
        clrbit(cgp->cg_iused, ino);
        cgp->cg_nifree++;
        fs->fs_nifree++;
        clrbit(cgp->cg_iused, ino);
        cgp->cg_nifree++;
        fs->fs_nifree++;

-       fs->fs_cs[cg].cs_nifree++;
+       fs->fs_cs(cg).cs_nifree++;

        if ((mode & IFMT) == IFDIR) {
                cgp->cg_ndir--;
        if ((mode & IFMT) == IFDIR) {
                cgp->cg_ndir--;

-               fs->fs_cs[cg].cs_ndir--;
+               fs->fs_cs(cg).cs_ndir--;

        }
        fs->fs_fmod++;
        bdwrite(bp);
 }
 
        }
        fs->fs_fmod++;
        bdwrite(bp);
 }
 

+/*
+ * find a block of the specified size in the specified cylinder group
+ * It is a panic if a request is made to find a block if none are
+ * available.
+ */
+daddr_t
+mapsearch(fs, cgp, bpref, allocsiz)
+       register struct fs *fs;
+       register struct cg *cgp;
+       daddr_t bpref;
+       int allocsiz;
+{
+       daddr_t bno;
+       int start, len, loc, i;
+       int blk, field, subfield, pos;
+
+       /*
+        * find the fragment by searching through the free block
+        * map for an appropriate bit pattern
+        */
+       if (bpref)
+               start = bpref % fs->fs_fpg / NBBY;
+       else
+               start = cgp->cg_frotor / NBBY;
+       len = roundup(fs->fs_fpg - 1, NBBY) / NBBY - start;
+       loc = scanc(len, &cgp->cg_free[start], fragtbl, 1 << (allocsiz - 1));
+       if (loc == 0) {
+               len = start - 1;
+               start = (cgdmin(cgp->cg_cgx, fs) -
+                        cgbase(cgp->cg_cgx, fs)) / NBBY;
+               loc = scanc(len, &cgp->cg_free[start], fragtbl,
+                       1 << (allocsiz - 1));
+               if (loc == 0) {
+                       panic("alloccg: map corrupted");
+                       return (0);
+               }
+       }
+       bno = (start + len - loc) * NBBY;
+       cgp->cg_frotor = bno;
+       /*
+        * found the byte in the map
+        * sift through the bits to find the selected frag
+        */
+       for (i = 0; i < NBBY; i += FRAG) {
+               blk = (cgp->cg_free[bno / NBBY] >> i) & (0xff >> NBBY - FRAG);
+               blk <<= 1;
+               field = around[allocsiz];
+               subfield = inside[allocsiz];
+               for (pos = 0; pos <= FRAG - allocsiz; pos++) {
+                       if ((blk & field) == subfield) {
+                               return (bno + i + pos);
+                       }
+                       field <<= 1;
+                       subfield <<= 1;
+               }
+       }
+       panic("alloccg: block not in map");
+       return (0);
+}
+

 /*
  * update the frsum fields to reflect addition or deletion 
  * of some frags
 /*
  * update the frsum fields to reflect addition or deletion 
  * of some frags


@@ -690,7 +773,7 @@ update()
        register struct buf *bp;
        struct fs *fs;
        time_t tim;
        register struct buf *bp;
        struct fs *fs;
        time_t tim;

-       int i;
+       int i, blks;

 
        if (updlock)
                return;
 
        if (updlock)
                return;


@@ -713,10 +796,10 @@ update()
                        if (bp->b_un.b_fs != fs)
                                panic("update: bad b_fs");
                        bwrite(bp);
                        if (bp->b_un.b_fs != fs)
                                panic("update: bad b_fs");
                        bwrite(bp);

-                       for (i = 0; i < cssize(fs); i += BSIZE) {
-                               bp = getblk(mp->m_dev, csaddr(fs) + i / FSIZE,
+                       blks = howmany(cssize(fs), BSIZE);
+                       for (i = 0; i < blks; i++) {
+                               bp = getblk(mp->m_dev, csaddr(fs) + (i * FRAG),

                                        BSIZE);
                                        BSIZE);

-                               bcopy(fs->fs_cs + i, bp->b_un.b_addr, BSIZE);

                                bwrite(bp);
                        }
                }
                                bwrite(bp);
                        }
                }