home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / sys / ufs / ufs_alloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-05-02  |  29.6 KB  |  1,102 lines
  1. /*
  2.  * Copyright (c) 1982, 1986, 1989 Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  *
  33.  *    @(#)ufs_alloc.c    7.26 (Berkeley) 5/2/91
  34.  */
  35.  
  36. #include "param.h"
  37. #include "systm.h"
  38. #include "buf.h"
  39. #include "proc.h"
  40. #include "vnode.h"
  41. #include "kernel.h"
  42. #include "syslog.h"
  43.  
  44. #include "quota.h"
  45. #include "inode.h"
  46. #include "fs.h"
  47.  
  48. extern u_long        hashalloc();
  49. extern ino_t        ialloccg();
  50. extern daddr_t        alloccg();
  51. extern daddr_t        alloccgblk();
  52. extern daddr_t        fragextend();
  53. extern daddr_t        blkpref();
  54. extern daddr_t        mapsearch();
  55. extern int        inside[], around[];
  56. extern unsigned char    *fragtbl[];
  57.  
  58. /*
  59.  * Allocate a block in the file system.
  60.  * 
  61.  * The size of the requested block is given, which must be some
  62.  * multiple of fs_fsize and <= fs_bsize.
  63.  * A preference may be optionally specified. If a preference is given
  64.  * the following hierarchy is used to allocate a block:
  65.  *   1) allocate the requested block.
  66.  *   2) allocate a rotationally optimal block in the same cylinder.
  67.  *   3) allocate a block in the same cylinder group.
  68.  *   4) quadradically rehash into other cylinder groups, until an
  69.  *      available block is located.
  70.  * If no block preference is given the following heirarchy is used
  71.  * to allocate a block:
  72.  *   1) allocate a block in the cylinder group that contains the
  73.  *      inode for the file.
  74.  *   2) quadradically rehash into other cylinder groups, until an
  75.  *      available block is located.
  76.  */
  77. alloc(ip, lbn, bpref, size, bnp)
  78.     register struct inode *ip;
  79.     daddr_t lbn, bpref;
  80.     int size;
  81.     daddr_t *bnp;
  82. {
  83.     daddr_t bno;
  84.     register struct fs *fs;
  85.     register struct buf *bp;
  86.     int cg, error;
  87.     struct ucred *cred = curproc->p_ucred;        /* XXX */
  88.     
  89.     *bnp = 0;
  90.     fs = ip->i_fs;
  91.     if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) {
  92.         printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n",
  93.             ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt);
  94.         panic("alloc: bad size");
  95.     }
  96.     if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0)
  97.         goto nospace;
  98.     if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0)
  99.         goto nospace;
  100. #ifdef QUOTA
  101.     if (error = chkdq(ip, (long)btodb(size), cred, 0))
  102.         return (error);
  103. #endif
  104.     if (bpref >= fs->fs_size)
  105.         bpref = 0;
  106.     if (bpref == 0)
  107.         cg = itog(fs, ip->i_number);
  108.     else
  109.         cg = dtog(fs, bpref);
  110.     bno = (daddr_t)hashalloc(ip, cg, (long)bpref, size,
  111.         (u_long (*)())alloccg);
  112.     if (bno > 0) {
  113.         ip->i_blocks += btodb(size);
  114.         ip->i_flag |= IUPD|ICHG;
  115.         *bnp = bno;
  116.         return (0);
  117.     }
  118. #ifdef QUOTA
  119.     /*
  120.      * Restore user's disk quota because allocation failed.
  121.      */
  122.     (void) chkdq(ip, (long)-btodb(size), cred, FORCE);
  123. #endif
  124. nospace:
  125.     fserr(fs, cred->cr_uid, "file system full");
  126.     uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
  127.     return (ENOSPC);
  128. }
  129.  
  130. /*
  131.  * Reallocate a fragment to a bigger size
  132.  *
  133.  * The number and size of the old block is given, and a preference
  134.  * and new size is also specified. The allocator attempts to extend
  135.  * the original block. Failing that, the regular block allocator is
  136.  * invoked to get an appropriate block.
  137.  */
  138. realloccg(ip, lbprev, bpref, osize, nsize, bpp)
  139.     register struct inode *ip;
  140.     off_t lbprev;
  141.     daddr_t bpref;
  142.     int osize, nsize;
  143.     struct buf **bpp;
  144. {
  145.     register struct fs *fs;
  146.     struct buf *bp, *obp;
  147.     int cg, request, error;
  148.     daddr_t bprev, bno;
  149.     struct ucred *cred = curproc->p_ucred;        /* XXX */
  150.     
  151.     *bpp = 0;
  152.     fs = ip->i_fs;
  153.     if ((unsigned)osize > fs->fs_bsize || fragoff(fs, osize) != 0 ||
  154.         (unsigned)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) {
  155.         printf("dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n",
  156.             ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt);
  157.         panic("realloccg: bad size");
  158.     }
  159.     if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0)
  160.         goto nospace;
  161.     if ((bprev = ip->i_db[lbprev]) == 0) {
  162.         printf("dev = 0x%x, bsize = %d, bprev = %d, fs = %s\n",
  163.             ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt);
  164.         panic("realloccg: bad bprev");
  165.     }
  166.     /*
  167.      * Allocate the extra space in the buffer.
  168.      */
  169.     if (error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp)) {
  170.         brelse(bp);
  171.         return (error);
  172.     }
  173. #ifdef QUOTA
  174.     if (error = chkdq(ip, (long)btodb(nsize - osize), cred, 0)) {
  175.         brelse(bp);
  176.         return (error);
  177.     }
  178. #endif
  179.     /*
  180.      * Check for extension in the existing location.
  181.      */
  182.     cg = dtog(fs, bprev);
  183.     if (bno = fragextend(ip, cg, (long)bprev, osize, nsize)) {
  184.         if (bp->b_blkno != fsbtodb(fs, bno))
  185.             panic("bad blockno");
  186.         ip->i_blocks += btodb(nsize - osize);
  187.         ip->i_flag |= IUPD|ICHG;
  188.         allocbuf(bp, nsize);
  189.         bp->b_flags |= B_DONE;
  190.         bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize);
  191.         *bpp = bp;
  192.         return (0);
  193.     }
  194.     /*
  195.      * Allocate a new disk location.
  196.      */
  197.     if (bpref >= fs->fs_size)
  198.         bpref = 0;
  199.     switch ((int)fs->fs_optim) {
  200.     case FS_OPTSPACE:
  201.         /*
  202.          * Allocate an exact sized fragment. Although this makes 
  203.          * best use of space, we will waste time relocating it if 
  204.          * the file continues to grow. If the fragmentation is
  205.          * less than half of the minimum free reserve, we choose
  206.          * to begin optimizing for time.
  207.          */
  208.         request = nsize;
  209.         if (fs->fs_minfree < 5 ||
  210.             fs->fs_cstotal.cs_nffree >
  211.             fs->fs_dsize * fs->fs_minfree / (2 * 100))
  212.             break;
  213.         log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n",
  214.             fs->fs_fsmnt);
  215.         fs->fs_optim = FS_OPTTIME;
  216.         break;
  217.     case FS_OPTTIME:
  218.         /*
  219.          * At this point we have discovered a file that is trying
  220.          * to grow a small fragment to a larger fragment. To save
  221.          * time, we allocate a full sized block, then free the 
  222.          * unused portion. If the file continues to grow, the 
  223.          * `fragextend' call above will be able to grow it in place
  224.          * without further copying. If aberrant programs cause
  225.          * disk fragmentation to grow within 2% of the free reserve,
  226.          * we choose to begin optimizing for space.
  227.          */
  228.         request = fs->fs_bsize;
  229.         if (fs->fs_cstotal.cs_nffree <
  230.             fs->fs_dsize * (fs->fs_minfree - 2) / 100)
  231.             break;
  232.         log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n",
  233.             fs->fs_fsmnt);
  234.         fs->fs_optim = FS_OPTSPACE;
  235.         break;
  236.     default:
  237.         printf("dev = 0x%x, optim = %d, fs = %s\n",
  238.             ip->i_dev, fs->fs_optim, fs->fs_fsmnt);
  239.         panic("realloccg: bad optim");
  240.         /* NOTREACHED */
  241.     }
  242.     bno = (daddr_t)hashalloc(ip, cg, (long)bpref, request,
  243.         (u_long (*)())alloccg);
  244.     if (bno > 0) {
  245.         bp->b_blkno = fsbtodb(fs, bno);
  246.         (void) vnode_pager_uncache(ITOV(ip));
  247.         blkfree(ip, bprev, (off_t)osize);
  248.         if (nsize < request)
  249.             blkfree(ip, bno + numfrags(fs, nsize),
  250.                 (off_t)(request - nsize));
  251.         ip->i_blocks += btodb(nsize - osize);
  252.         ip->i_flag |= IUPD|ICHG;
  253.         allocbuf(bp, nsize);
  254.         bp->b_flags |= B_DONE;
  255.         bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize);
  256.         *bpp = bp;
  257.         return (0);
  258.     }
  259. #ifdef QUOTA
  260.     /*
  261.      * Restore user's disk quota because allocation failed.
  262.      */
  263.     (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE);
  264. #endif
  265.     brelse(bp);
  266. nospace:
  267.     /*
  268.      * no space available
  269.      */
  270.     fserr(fs, cred->cr_uid, "file system full");
  271.     uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
  272.     return (ENOSPC);
  273. }
  274.  
  275. /*
  276.  * Allocate an inode in the file system.
  277.  * 
  278.  * A preference may be optionally specified. If a preference is given
  279.  * the following hierarchy is used to allocate an inode:
  280.  *   1) allocate the requested inode.
  281.  *   2) allocate an inode in the same cylinder group.
  282.  *   3) quadradically rehash into other cylinder groups, until an
  283.  *      available inode is located.
  284.  * If no inode preference is given the following heirarchy is used
  285.  * to allocate an inode:
  286.  *   1) allocate an inode in cylinder group 0.
  287.  *   2) quadradically rehash into other cylinder groups, until an
  288.  *      available inode is located.
  289.  */
  290. ialloc(pip, ipref, mode, cred, ipp)
  291.     register struct inode *pip;
  292.     ino_t ipref;
  293.     int mode;
  294.     struct ucred *cred;
  295.     struct inode **ipp;
  296. {
  297.     ino_t ino;
  298.     register struct fs *fs;
  299.     register struct inode *ip;
  300.     int cg, error;
  301.     
  302.     *ipp = 0;
  303.     fs = pip->i_fs;
  304.     if (fs->fs_cstotal.cs_nifree == 0)
  305.         goto noinodes;
  306.     if (ipref >= fs->fs_ncg * fs->fs_ipg)
  307.         ipref = 0;
  308.     cg = itog(fs, ipref);
  309.     ino = (ino_t)hashalloc(pip, cg, (long)ipref, mode, ialloccg);
  310.     if (ino == 0)
  311.         goto noinodes;
  312.     error = iget(pip, ino, ipp);
  313.     if (error) {
  314.         ifree(pip, ino, mode);
  315.         return (error);
  316.     }
  317.     ip = *ipp;
  318.     if (ip->i_mode) {
  319.         printf("mode = 0%o, inum = %d, fs = %s\n",
  320.             ip->i_mode, ip->i_number, fs->fs_fsmnt);
  321.         panic("ialloc: dup alloc");
  322.     }
  323.     if (ip->i_blocks) {                /* XXX */
  324.         printf("free inode %s/%d had %d blocks\n",
  325.             fs->fs_fsmnt, ino, ip->i_blocks);
  326.         ip->i_blocks = 0;
  327.     }
  328.     ip->i_flags = 0;
  329.     /*
  330.      * Set up a new generation number for this inode.
  331.      */
  332.     if (++nextgennumber < (u_long)time.tv_sec)
  333.         nextgennumber = time.tv_sec;
  334.     ip->i_gen = nextgennumber;
  335.     return (0);
  336. noinodes:
  337.     fserr(fs, cred->cr_uid, "out of inodes");
  338.     uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt);
  339.     return (ENOSPC);
  340. }
  341.  
  342. /*
  343.  * Find a cylinder to place a directory.
  344.  *
  345.  * The policy implemented by this algorithm is to select from
  346.  * among those cylinder groups with above the average number of
  347.  * free inodes, the one with the smallest number of directories.
  348.  */
  349. ino_t
  350. dirpref(fs)
  351.     register struct fs *fs;
  352. {
  353.     int cg, minndir, mincg, avgifree;
  354.  
  355.     avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg;
  356.     minndir = fs->fs_ipg;
  357.     mincg = 0;
  358.     for (cg = 0; cg < fs->fs_ncg; cg++)
  359.         if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
  360.             fs->fs_cs(fs, cg).cs_nifree >= avgifree) {
  361.             mincg = cg;
  362.             minndir = fs->fs_cs(fs, cg).cs_ndir;
  363.         }
  364.     return ((ino_t)(fs->fs_ipg * mincg));
  365. }
  366.  
  367. /*
  368.  * Select the desired position for the next block in a file.  The file is
  369.  * logically divided into sections. The first section is composed of the
  370.  * direct blocks. Each additional section contains fs_maxbpg blocks.
  371.  * 
  372.  * If no blocks have been allocated in the first section, the policy is to
  373.  * request a block in the same cylinder group as the inode that describes
  374.  * the file. If no blocks have been allocated in any other section, the
  375.  * policy is to place the section in a cylinder group with a greater than
  376.  * average number of free blocks.  An appropriate cylinder group is found
  377.  * by using a rotor that sweeps the cylinder groups. When a new group of
  378.  * blocks is needed, the sweep begins in the cylinder group following the
  379.  * cylinder group from which the previous allocation was made. The sweep
  380.  * continues until a cylinder group with greater than the average number
  381.  * of free blocks is found. If the allocation is for the first block in an
  382.  * indirect block, the information on the previous allocation is unavailable;
  383.  * here a best guess is made based upon the logical block number being
  384.  * allocated.
  385.  * 
  386.  * If a section is already partially allocated, the policy is to
  387.  * contiguously allocate fs_maxcontig blocks.  The end of one of these
  388.  * contiguous blocks and the beginning of the next is physically separated
  389.  * so that the disk head will be in transit between them for at least
  390.  * fs_rotdelay milliseconds.  This is to allow time for the processor to
  391.  * schedule another I/O transfer.
  392.  */
  393. daddr_t
  394. blkpref(ip, lbn, indx, bap)
  395.     struct inode *ip;
  396.     daddr_t lbn;
  397.     int indx;
  398.     daddr_t *bap;
  399. {
  400.     register struct fs *fs;
  401.     register int cg;
  402.     int avgbfree, startcg;
  403.     daddr_t nextblk;
  404.  
  405.     fs = ip->i_fs;
  406.     if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) {
  407.         if (lbn < NDADDR) {
  408.             cg = itog(fs, ip->i_number);
  409.             return (fs->fs_fpg * cg + fs->fs_frag);
  410.         }
  411.         /*
  412.          * Find a cylinder with greater than average number of
  413.          * unused data blocks.
  414.          */
  415.         if (indx == 0 || bap[indx - 1] == 0)
  416.             startcg = itog(fs, ip->i_number) + lbn / fs->fs_maxbpg;
  417.         else
  418.             startcg = dtog(fs, bap[indx - 1]) + 1;
  419.         startcg %= fs->fs_ncg;
  420.         avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
  421.         for (cg = startcg; cg < fs->fs_ncg; cg++)
  422.             if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
  423.                 fs->fs_cgrotor = cg;
  424.                 return (fs->fs_fpg * cg + fs->fs_frag);
  425.             }
  426.         for (cg = 0; cg <= startcg; cg++)
  427.             if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
  428.                 fs->fs_cgrotor = cg;
  429.                 return (fs->fs_fpg * cg + fs->fs_frag);
  430.             }
  431.         return (NULL);
  432.     }
  433.     /*
  434.      * One or more previous blocks have been laid out. If less
  435.      * than fs_maxcontig previous blocks are contiguous, the
  436.      * next block is requested contiguously, otherwise it is
  437.      * requested rotationally delayed by fs_rotdelay milliseconds.
  438.      */
  439.     nextblk = bap[indx - 1] + fs->fs_frag;
  440.     if (indx > fs->fs_maxcontig &&
  441.         bap[indx - fs->fs_maxcontig] + blkstofrags(fs, fs->fs_maxcontig)
  442.         != nextblk)
  443.         return (nextblk);
  444.     if (fs->fs_rotdelay != 0)
  445.         /*
  446.          * Here we convert ms of delay to frags as:
  447.          * (frags) = (ms) * (rev/sec) * (sect/rev) /
  448.          *    ((sect/frag) * (ms/sec))
  449.          * then round up to the next block.
  450.          */
  451.         nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect /
  452.             (NSPF(fs) * 1000), fs->fs_frag);
  453.     return (nextblk);
  454. }
  455.  
  456. /*
  457.  * Implement the cylinder overflow algorithm.
  458.  *
  459.  * The policy implemented by this algorithm is:
  460.  *   1) allocate the block in its requested cylinder group.
  461.  *   2) quadradically rehash on the cylinder group number.
  462.  *   3) brute force search for a free block.
  463.  */
  464. /*VARARGS5*/
  465. u_long
  466. hashalloc(ip, cg, pref, size, allocator)
  467.     struct inode *ip;
  468.     int cg;
  469.     long pref;
  470.     int size;    /* size for data blocks, mode for inodes */
  471.     u_long (*allocator)();
  472. {
  473.     register struct fs *fs;
  474.     long result;
  475.     int i, icg = cg;
  476.  
  477.     fs = ip->i_fs;
  478.     /*
  479.      * 1: preferred cylinder group
  480.      */
  481.     result = (*allocator)(ip, cg, pref, size);
  482.     if (result)
  483.         return (result);
  484.     /*
  485.      * 2: quadratic rehash
  486.      */
  487.     for (i = 1; i < fs->fs_ncg; i *= 2) {
  488.         cg += i;
  489.         if (cg >= fs->fs_ncg)
  490.             cg -= fs->fs_ncg;
  491.         result = (*allocator)(ip, cg, 0, size);
  492.         if (result)
  493.             return (result);
  494.     }
  495.     /*
  496.      * 3: brute force search
  497.      * Note that we start at i == 2, since 0 was checked initially,
  498.      * and 1 is always checked in the quadratic rehash.
  499.      */
  500.     cg = (icg + 2) % fs->fs_ncg;
  501.     for (i = 2; i < fs->fs_ncg; i++) {
  502.         result = (*allocator)(ip, cg, 0, size);
  503.         if (result)
  504.             return (result);
  505.         cg++;
  506.         if (cg == fs->fs_ncg)
  507.             cg = 0;
  508.     }
  509.     return (NULL);
  510. }
  511.  
  512. /*
  513.  * Determine whether a fragment can be extended.
  514.  *
  515.  * Check to see if the necessary fragments are available, and 
  516.  * if they are, allocate them.
  517.  */
  518. daddr_t
  519. fragextend(ip, cg, bprev, osize, nsize)
  520.     struct inode *ip;
  521.     int cg;
  522.     long bprev;
  523.     int osize, nsize;
  524. {
  525.     register struct fs *fs;
  526.     register struct cg *cgp;
  527.     struct buf *bp;
  528.     long bno;
  529.     int frags, bbase;
  530.     int i, error;
  531.  
  532.     fs = ip->i_fs;
  533.     if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize))
  534.         return (NULL);
  535.     frags = numfrags(fs, nsize);
  536.     bbase = fragnum(fs, bprev);
  537.     if (bbase > fragnum(fs, (bprev + frags - 1))) {
  538.         /* cannot extend across a block boundary */
  539.         return (NULL);
  540.     }
  541.     error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
  542.         (int)fs->fs_cgsize, NOCRED, &bp);
  543.     if (error) {
  544.         brelse(bp);
  545.         return (NULL);
  546.     }
  547.     cgp = bp->b_un.b_cg;
  548.     if (!cg_chkmagic(cgp)) {
  549.         brelse(bp);
  550.         return (NULL);
  551.     }
  552.     cgp->cg_time = time.tv_sec;
  553.     bno = dtogd(fs, bprev);
  554.     for (i = numfrags(fs, osize); i < frags; i++)
  555.         if (isclr(cg_blksfree(cgp), bno + i)) {
  556.             brelse(bp);
  557.             return (NULL);
  558.         }
  559.     /*
  560.      * the current fragment can be extended
  561.      * deduct the count on fragment being extended into
  562.      * increase the count on the remaining fragment (if any)
  563.      * allocate the extended piece
  564.      */
  565.     for (i = frags; i < fs->fs_frag - bbase; i++)
  566.         if (isclr(cg_blksfree(cgp), bno + i))
  567.             break;
  568.     cgp->cg_frsum[i - numfrags(fs, osize)]--;
  569.     if (i != frags)
  570.         cgp->cg_frsum[i - frags]++;
  571.     for (i = numfrags(fs, osize); i < frags; i++) {
  572.         clrbit(cg_blksfree(cgp), bno + i);
  573.         cgp->cg_cs.cs_nffree--;
  574.         fs->fs_cstotal.cs_nffree--;
  575.         fs->fs_cs(fs, cg).cs_nffree--;
  576.     }
  577.     fs->fs_fmod++;
  578.     bdwrite(bp);
  579.     return (bprev);
  580. }
  581.  
  582. /*
  583.  * Determine whether a block can be allocated.
  584.  *
  585.  * Check to see if a block of the apprpriate size is available,
  586.  * and if it is, allocate it.
  587.  */
  588. daddr_t
  589. alloccg(ip, cg, bpref, size)
  590.     struct inode *ip;
  591.     int cg;
  592.     daddr_t bpref;
  593.     int size;
  594. {
  595.     register struct fs *fs;
  596.     register struct cg *cgp;
  597.     struct buf *bp;
  598.     register int i;
  599.     int error, bno, frags, allocsiz;
  600.  
  601.     fs = ip->i_fs;
  602.     if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize)
  603.         return (NULL);
  604.     error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
  605.         (int)fs->fs_cgsize, NOCRED, &bp);
  606.     if (error) {
  607.         brelse(bp);
  608.         return (NULL);
  609.     }
  610.     cgp = bp->b_un.b_cg;
  611.     if (!cg_chkmagic(cgp) ||
  612.         (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) {
  613.         brelse(bp);
  614.         return (NULL);
  615.     }
  616.     cgp->cg_time = time.tv_sec;
  617.     if (size == fs->fs_bsize) {
  618.         bno = alloccgblk(fs, cgp, bpref);
  619.         bdwrite(bp);
  620.         return (bno);
  621.     }
  622.     /*
  623.      * check to see if any fragments are already available
  624.      * allocsiz is the size which will be allocated, hacking
  625.      * it down to a smaller size if necessary
  626.      */
  627.     frags = numfrags(fs, size);
  628.     for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++)
  629.         if (cgp->cg_frsum[allocsiz] != 0)
  630.             break;
  631.     if (allocsiz == fs->fs_frag) {
  632.         /*
  633.          * no fragments were available, so a block will be 
  634.          * allocated, and hacked up
  635.          */
  636.         if (cgp->cg_cs.cs_nbfree == 0) {
  637.             brelse(bp);
  638.             return (NULL);
  639.         }
  640.         bno = alloccgblk(fs, cgp, bpref);
  641.         bpref = dtogd(fs, bno);
  642.         for (i = frags; i < fs->fs_frag; i++)
  643.             setbit(cg_blksfree(cgp), bpref + i);
  644.         i = fs->fs_frag - frags;
  645.         cgp->cg_cs.cs_nffree += i;
  646.         fs->fs_cstotal.cs_nffree += i;
  647.         fs->fs_cs(fs, cg).cs_nffree += i;
  648.         fs->fs_fmod++;
  649.         cgp->cg_frsum[i]++;
  650.         bdwrite(bp);
  651.         return (bno);
  652.     }
  653.     bno = mapsearch(fs, cgp, bpref, allocsiz);
  654.     if (bno < 0) {
  655.         brelse(bp);
  656.         return (NULL);
  657.     }
  658.     for (i = 0; i < frags; i++)
  659.         clrbit(cg_blksfree(cgp), bno + i);
  660.     cgp->cg_cs.cs_nffree -= frags;
  661.     fs->fs_cstotal.cs_nffree -= frags;
  662.     fs->fs_cs(fs, cg).cs_nffree -= frags;
  663.     fs->fs_fmod++;
  664.     cgp->cg_frsum[allocsiz]--;
  665.     if (frags != allocsiz)
  666.         cgp->cg_frsum[allocsiz - frags]++;
  667.     bdwrite(bp);
  668.     return (cg * fs->fs_fpg + bno);
  669. }
  670.  
  671. /*
  672.  * Allocate a block in a cylinder group.
  673.  *
  674.  * This algorithm implements the following policy:
  675.  *   1) allocate the requested block.
  676.  *   2) allocate a rotationally optimal block in the same cylinder.
  677.  *   3) allocate the next available block on the block rotor for the
  678.  *      specified cylinder group.
  679.  * Note that this routine only allocates fs_bsize blocks; these
  680.  * blocks may be fragmented by the routine that allocates them.
  681.  */
  682. daddr_t
  683. alloccgblk(fs, cgp, bpref)
  684.     register struct fs *fs;
  685.     register struct cg *cgp;
  686.     daddr_t bpref;
  687. {
  688.     daddr_t bno;
  689.     int cylno, pos, delta;
  690.     short *cylbp;
  691.     register int i;
  692.  
  693.     if (bpref == 0) {
  694.         bpref = cgp->cg_rotor;
  695.         goto norot;
  696.     }
  697.     bpref = blknum(fs, bpref);
  698.     bpref = dtogd(fs, bpref);
  699.     /*
  700.      * if the requested block is available, use it
  701.      */
  702.     if (isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) {
  703.         bno = bpref;
  704.         goto gotit;
  705.     }
  706.     /*
  707.      * check for a block available on the same cylinder
  708.      */
  709.     cylno = cbtocylno(fs, bpref);
  710.     if (cg_blktot(cgp)[cylno] == 0)
  711.         goto norot;
  712.     if (fs->fs_cpc == 0) {
  713.         /*
  714.          * block layout info is not available, so just have
  715.          * to take any block in this cylinder.
  716.          */
  717.         bpref = howmany(fs->fs_spc * cylno, NSPF(fs));
  718.         goto norot;
  719.     }
  720.     /*
  721.      * check the summary information to see if a block is 
  722.      * available in the requested cylinder starting at the
  723.      * requested rotational position and proceeding around.
  724.      */
  725.     cylbp = cg_blks(fs, cgp, cylno);
  726.     pos = cbtorpos(fs, bpref);
  727.     for (i = pos; i < fs->fs_nrpos; i++)
  728.         if (cylbp[i] > 0)
  729.             break;
  730.     if (i == fs->fs_nrpos)
  731.         for (i = 0; i < pos; i++)
  732.             if (cylbp[i] > 0)
  733.                 break;
  734.     if (cylbp[i] > 0) {
  735.         /*
  736.          * found a rotational position, now find the actual
  737.          * block. A panic if none is actually there.
  738.          */
  739.         pos = cylno % fs->fs_cpc;
  740.         bno = (cylno - pos) * fs->fs_spc / NSPB(fs);
  741.         if (fs_postbl(fs, pos)[i] == -1) {
  742.             printf("pos = %d, i = %d, fs = %s\n",
  743.                 pos, i, fs->fs_fsmnt);
  744.             panic("alloccgblk: cyl groups corrupted");
  745.         }
  746.         for (i = fs_postbl(fs, pos)[i];; ) {
  747.             if (isblock(fs, cg_blksfree(cgp), bno + i)) {
  748.                 bno = blkstofrags(fs, (bno + i));
  749.                 goto gotit;
  750.             }
  751.             delta = fs_rotbl(fs)[i];
  752.             if (delta <= 0 ||
  753.                 delta + i > fragstoblks(fs, fs->fs_fpg))
  754.                 break;
  755.             i += delta;
  756.         }
  757.         printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt);
  758.         panic("alloccgblk: can't find blk in cyl");
  759.     }
  760. norot:
  761.     /*
  762.      * no blocks in the requested cylinder, so take next
  763.      * available one in this cylinder group.
  764.      */
  765.     bno = mapsearch(fs, cgp, bpref, (int)fs->fs_frag);
  766.     if (bno < 0)
  767.         return (NULL);
  768.     cgp->cg_rotor = bno;
  769. gotit:
  770.     clrblock(fs, cg_blksfree(cgp), (long)fragstoblks(fs, bno));
  771.     cgp->cg_cs.cs_nbfree--;
  772.     fs->fs_cstotal.cs_nbfree--;
  773.     fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--;
  774.     cylno = cbtocylno(fs, bno);
  775.     cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--;
  776.     cg_blktot(cgp)[cylno]--;
  777.     fs->fs_fmod++;
  778.     return (cgp->cg_cgx * fs->fs_fpg + bno);
  779. }
  780.  
  781. /*
  782.  * Determine whether an inode can be allocated.
  783.  *
  784.  * Check to see if an inode is available, and if it is,
  785.  * allocate it using the following policy:
  786.  *   1) allocate the requested inode.
  787.  *   2) allocate the next available inode after the requested
  788.  *      inode in the specified cylinder group.
  789.  */
  790. ino_t
  791. ialloccg(ip, cg, ipref, mode)
  792.     struct inode *ip;
  793.     int cg;
  794.     daddr_t ipref;
  795.     int mode;
  796. {
  797.     register struct fs *fs;
  798.     register struct cg *cgp;
  799.     struct buf *bp;
  800.     int error, start, len, loc, map, i;
  801.  
  802.     fs = ip->i_fs;
  803.     if (fs->fs_cs(fs, cg).cs_nifree == 0)
  804.         return (NULL);
  805.     error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
  806.         (int)fs->fs_cgsize, NOCRED, &bp);
  807.     if (error) {
  808.         brelse(bp);
  809.         return (NULL);
  810.     }
  811.     cgp = bp->b_un.b_cg;
  812.     if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) {
  813.         brelse(bp);
  814.         return (NULL);
  815.     }
  816.     cgp->cg_time = time.tv_sec;
  817.     if (ipref) {
  818.         ipref %= fs->fs_ipg;
  819.         if (isclr(cg_inosused(cgp), ipref))
  820.             goto gotit;
  821.     }
  822.     start = cgp->cg_irotor / NBBY;
  823.     len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY);
  824.     loc = skpc(0xff, len, &cg_inosused(cgp)[start]);
  825.     if (loc == 0) {
  826.         len = start + 1;
  827.         start = 0;
  828.         loc = skpc(0xff, len, &cg_inosused(cgp)[0]);
  829.         if (loc == 0) {
  830.             printf("cg = %s, irotor = %d, fs = %s\n",
  831.                 cg, cgp->cg_irotor, fs->fs_fsmnt);
  832.             panic("ialloccg: map corrupted");
  833.             /* NOTREACHED */
  834.         }
  835.     }
  836.     i = start + len - loc;
  837.     map = cg_inosused(cgp)[i];
  838.     ipref = i * NBBY;
  839.     for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) {
  840.         if ((map & i) == 0) {
  841.             cgp->cg_irotor = ipref;
  842.             goto gotit;
  843.         }
  844.     }
  845.     printf("fs = %s\n", fs->fs_fsmnt);
  846.     panic("ialloccg: block not in map");
  847.     /* NOTREACHED */
  848. gotit:
  849.     setbit(cg_inosused(cgp), ipref);
  850.     cgp->cg_cs.cs_nifree--;
  851.     fs->fs_cstotal.cs_nifree--;
  852.     fs->fs_cs(fs, cg).cs_nifree--;
  853.     fs->fs_fmod++;
  854.     if ((mode & IFMT) == IFDIR) {
  855.         cgp->cg_cs.cs_ndir++;
  856.         fs->fs_cstotal.cs_ndir++;
  857.         fs->fs_cs(fs, cg).cs_ndir++;
  858.     }
  859.     bdwrite(bp);
  860.     return (cg * fs->fs_ipg + ipref);
  861. }
  862.  
  863. /*
  864.  * Free a block or fragment.
  865.  *
  866.  * The specified block or fragment is placed back in the
  867.  * free map. If a fragment is deallocated, a possible 
  868.  * block reassembly is checked.
  869.  */
  870. blkfree(ip, bno, size)
  871.     register struct inode *ip;
  872.     daddr_t bno;
  873.     off_t size;
  874. {
  875.     register struct fs *fs;
  876.     register struct cg *cgp;
  877.     struct buf *bp;
  878.     int error, cg, blk, frags, bbase;
  879.     register int i;
  880.     struct ucred *cred = curproc->p_ucred;    /* XXX */
  881.  
  882.     fs = ip->i_fs;
  883.     if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) {
  884.         printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n",
  885.             ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt);
  886.         panic("blkfree: bad size");
  887.     }
  888.     cg = dtog(fs, bno);
  889.     if ((unsigned)bno >= fs->fs_size) {
  890.         printf("bad block %d, ino %d\n", bno, ip->i_number);
  891.         fserr(fs, cred->cr_uid, "bad block");
  892.         return;
  893.     }
  894.     error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
  895.         (int)fs->fs_cgsize, NOCRED, &bp);
  896.     if (error) {
  897.         brelse(bp);
  898.         return;
  899.     }
  900.     cgp = bp->b_un.b_cg;
  901.     if (!cg_chkmagic(cgp)) {
  902.         brelse(bp);
  903.         return;
  904.     }
  905.     cgp->cg_time = time.tv_sec;
  906.     bno = dtogd(fs, bno);
  907.     if (size == fs->fs_bsize) {
  908.         if (isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno))) {
  909.             printf("dev = 0x%x, block = %d, fs = %s\n",
  910.                 ip->i_dev, bno, fs->fs_fsmnt);
  911.             panic("blkfree: freeing free block");
  912.         }
  913.         setblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno));
  914.         cgp->cg_cs.cs_nbfree++;
  915.         fs->fs_cstotal.cs_nbfree++;
  916.         fs->fs_cs(fs, cg).cs_nbfree++;
  917.         i = cbtocylno(fs, bno);
  918.         cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++;
  919.         cg_blktot(cgp)[i]++;
  920.     } else {
  921.         bbase = bno - fragnum(fs, bno);
  922.         /*
  923.          * decrement the counts associated with the old frags
  924.          */
  925.         blk = blkmap(fs, cg_blksfree(cgp), bbase);
  926.         fragacct(fs, blk, cgp->cg_frsum, -1);
  927.         /*
  928.          * deallocate the fragment
  929.          */
  930.         frags = numfrags(fs, size);
  931.         for (i = 0; i < frags; i++) {
  932.             if (isset(cg_blksfree(cgp), bno + i)) {
  933.                 printf("dev = 0x%x, block = %d, fs = %s\n",
  934.                     ip->i_dev, bno + i, fs->fs_fsmnt);
  935.                 panic("blkfree: freeing free frag");
  936.             }
  937.             setbit(cg_blksfree(cgp), bno + i);
  938.         }
  939.         cgp->cg_cs.cs_nffree += i;
  940.         fs->fs_cstotal.cs_nffree += i;
  941.         fs->fs_cs(fs, cg).cs_nffree += i;
  942.         /*
  943.          * add back in counts associated with the new frags
  944.          */
  945.         blk = blkmap(fs, cg_blksfree(cgp), bbase);
  946.         fragacct(fs, blk, cgp->cg_frsum, 1);
  947.         /*
  948.          * if a complete block has been reassembled, account for it
  949.          */
  950.         if (isblock(fs, cg_blksfree(cgp),
  951.             (daddr_t)fragstoblks(fs, bbase))) {
  952.             cgp->cg_cs.cs_nffree -= fs->fs_frag;
  953.             fs->fs_cstotal.cs_nffree -= fs->fs_frag;
  954.             fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag;
  955.             cgp->cg_cs.cs_nbfree++;
  956.             fs->fs_cstotal.cs_nbfree++;
  957.             fs->fs_cs(fs, cg).cs_nbfree++;
  958.             i = cbtocylno(fs, bbase);
  959.             cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++;
  960.             cg_blktot(cgp)[i]++;
  961.         }
  962.     }
  963.     fs->fs_fmod++;
  964.     bdwrite(bp);
  965. }
  966.  
  967. /*
  968.  * Free an inode.
  969.  *
  970.  * The specified inode is placed back in the free map.
  971.  */
  972. ifree(ip, ino, mode)
  973.     struct inode *ip;
  974.     ino_t ino;
  975.     int mode;
  976. {
  977.     register struct fs *fs;
  978.     register struct cg *cgp;
  979.     struct buf *bp;
  980.     int error, cg;
  981.  
  982.     fs = ip->i_fs;
  983.     if ((unsigned)ino >= fs->fs_ipg*fs->fs_ncg) {
  984.         printf("dev = 0x%x, ino = %d, fs = %s\n",
  985.             ip->i_dev, ino, fs->fs_fsmnt);
  986.         panic("ifree: range");
  987.     }
  988.     cg = itog(fs, ino);
  989.     error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
  990.         (int)fs->fs_cgsize, NOCRED, &bp);
  991.     if (error) {
  992.         brelse(bp);
  993.         return;
  994.     }
  995.     cgp = bp->b_un.b_cg;
  996.     if (!cg_chkmagic(cgp)) {
  997.         brelse(bp);
  998.         return;
  999.     }
  1000.     cgp->cg_time = time.tv_sec;
  1001.     ino %= fs->fs_ipg;
  1002.     if (isclr(cg_inosused(cgp), ino)) {
  1003.         printf("dev = 0x%x, ino = %d, fs = %s\n",
  1004.             ip->i_dev, ino, fs->fs_fsmnt);
  1005.         if (fs->fs_ronly == 0)
  1006.             panic("ifree: freeing free inode");
  1007.     }
  1008.     clrbit(cg_inosused(cgp), ino);
  1009.     if (ino < cgp->cg_irotor)
  1010.         cgp->cg_irotor = ino;
  1011.     cgp->cg_cs.cs_nifree++;
  1012.     fs->fs_cstotal.cs_nifree++;
  1013.     fs->fs_cs(fs, cg).cs_nifree++;
  1014.     if ((mode & IFMT) == IFDIR) {
  1015.         cgp->cg_cs.cs_ndir--;
  1016.         fs->fs_cstotal.cs_ndir--;
  1017.         fs->fs_cs(fs, cg).cs_ndir--;
  1018.     }
  1019.     fs->fs_fmod++;
  1020.     bdwrite(bp);
  1021. }
  1022.  
  1023. /*
  1024.  * Find a block of the specified size in the specified cylinder group.
  1025.  *
  1026.  * It is a panic if a request is made to find a block if none are
  1027.  * available.
  1028.  */
  1029. daddr_t
  1030. mapsearch(fs, cgp, bpref, allocsiz)
  1031.     register struct fs *fs;
  1032.     register struct cg *cgp;
  1033.     daddr_t bpref;
  1034.     int allocsiz;
  1035. {
  1036.     daddr_t bno;
  1037.     int start, len, loc, i;
  1038.     int blk, field, subfield, pos;
  1039.  
  1040.     /*
  1041.      * find the fragment by searching through the free block
  1042.      * map for an appropriate bit pattern
  1043.      */
  1044.     if (bpref)
  1045.         start = dtogd(fs, bpref) / NBBY;
  1046.     else
  1047.         start = cgp->cg_frotor / NBBY;
  1048.     len = howmany(fs->fs_fpg, NBBY) - start;
  1049.     loc = scanc((unsigned)len, (u_char *)&cg_blksfree(cgp)[start],
  1050.         (u_char *)fragtbl[fs->fs_frag],
  1051.         (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
  1052.     if (loc == 0) {
  1053.         len = start + 1;
  1054.         start = 0;
  1055.         loc = scanc((unsigned)len, (u_char *)&cg_blksfree(cgp)[0],
  1056.             (u_char *)fragtbl[fs->fs_frag],
  1057.             (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
  1058.         if (loc == 0) {
  1059.             printf("start = %d, len = %d, fs = %s\n",
  1060.                 start, len, fs->fs_fsmnt);
  1061.             panic("alloccg: map corrupted");
  1062.             /* NOTREACHED */
  1063.         }
  1064.     }
  1065.     bno = (start + len - loc) * NBBY;
  1066.     cgp->cg_frotor = bno;
  1067.     /*
  1068.      * found the byte in the map
  1069.      * sift through the bits to find the selected frag
  1070.      */
  1071.     for (i = bno + NBBY; bno < i; bno += fs->fs_frag) {
  1072.         blk = blkmap(fs, cg_blksfree(cgp), bno);
  1073.         blk <<= 1;
  1074.         field = around[allocsiz];
  1075.         subfield = inside[allocsiz];
  1076.         for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) {
  1077.             if ((blk & field) == subfield)
  1078.                 return (bno + pos);
  1079.             field <<= 1;
  1080.             subfield <<= 1;
  1081.         }
  1082.     }
  1083.     printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt);
  1084.     panic("alloccg: block not in map");
  1085.     return (-1);
  1086. }
  1087.  
  1088. /*
  1089.  * Fserr prints the name of a file system with an error diagnostic.
  1090.  * 
  1091.  * The form of the error message is:
  1092.  *    fs: error message
  1093.  */
  1094. fserr(fs, uid, cp)
  1095.     struct fs *fs;
  1096.     uid_t uid;
  1097.     char *cp;
  1098. {
  1099.  
  1100.     log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->fs_fsmnt, cp);
  1101. }
  1102.