ffs_alloc.c revision 18330
11541Srgrimes/* 21541Srgrimes * Copyright (c) 1982, 1986, 1989, 1993 31541Srgrimes * The Regents of the University of California. All rights reserved. 41541Srgrimes * 51541Srgrimes * Redistribution and use in source and binary forms, with or without 61541Srgrimes * modification, are permitted provided that the following conditions 71541Srgrimes * are met: 81541Srgrimes * 1. Redistributions of source code must retain the above copyright 91541Srgrimes * notice, this list of conditions and the following disclaimer. 101541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111541Srgrimes * notice, this list of conditions and the following disclaimer in the 121541Srgrimes * documentation and/or other materials provided with the distribution. 131541Srgrimes * 3. All advertising materials mentioning features or use of this software 141541Srgrimes * must display the following acknowledgement: 151541Srgrimes * This product includes software developed by the University of 161541Srgrimes * California, Berkeley and its contributors. 171541Srgrimes * 4. Neither the name of the University nor the names of its contributors 181541Srgrimes * may be used to endorse or promote products derived from this software 191541Srgrimes * without specific prior written permission. 201541Srgrimes * 211541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 311541Srgrimes * SUCH DAMAGE. 321541Srgrimes * 331541Srgrimes * @(#)ffs_alloc.c 8.8 (Berkeley) 2/21/94 3418330Speter * $Id: ffs_alloc.c,v 1.25 1996/07/12 04:12:14 bde Exp $ 351541Srgrimes */ 361541Srgrimes 3713260Swollman#include "opt_quota.h" 3813260Swollman 391541Srgrimes#include <sys/param.h> 401541Srgrimes#include <sys/systm.h> 411541Srgrimes#include <sys/buf.h> 421541Srgrimes#include <sys/proc.h> 431541Srgrimes#include <sys/vnode.h> 441541Srgrimes#include <sys/mount.h> 451541Srgrimes#include <sys/kernel.h> 4612911Sphk#include <sys/sysctl.h> 471541Srgrimes#include <sys/syslog.h> 481541Srgrimes 491541Srgrimes#include <vm/vm.h> 501541Srgrimes 511541Srgrimes#include <ufs/ufs/quota.h> 521541Srgrimes#include <ufs/ufs/inode.h> 5312590Sbde#include <ufs/ufs/ufs_extern.h> 541541Srgrimes 551541Srgrimes#include <ufs/ffs/fs.h> 561541Srgrimes#include <ufs/ffs/ffs_extern.h> 571541Srgrimes 581541Srgrimesextern u_long nextgennumber; 591541Srgrimes 6015680Sgpalmertypedef daddr_t allocfcn_t __P((struct inode *ip, int cg, daddr_t bpref, 6112590Sbde int size)); 6212590Sbde 631541Srgrimesstatic daddr_t ffs_alloccg __P((struct inode *, int, daddr_t, int)); 641541Srgrimesstatic daddr_t ffs_alloccgblk __P((struct fs *, struct cg *, daddr_t)); 6512911Sphk#ifdef notyet 661541Srgrimesstatic daddr_t ffs_clusteralloc __P((struct inode *, int, daddr_t, int)); 6712911Sphk#endif 681541Srgrimesstatic ino_t ffs_dirpref __P((struct fs *)); 691541Srgrimesstatic daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 701541Srgrimesstatic void ffs_fserr __P((struct fs *, u_int, char *)); 711541Srgrimesstatic u_long ffs_hashalloc 7212590Sbde __P((struct inode *, int, long, int, allocfcn_t *)); 731541Srgrimesstatic ino_t ffs_nodealloccg __P((struct inode *, int, daddr_t, int)); 741541Srgrimesstatic daddr_t ffs_mapsearch __P((struct fs *, struct cg *, daddr_t, int)); 751541Srgrimes 7612911Sphkstatic void ffs_clusteracct __P((struct fs *, struct cg *, daddr_t, int)); 771549Srgrimes 781541Srgrimes/* 791541Srgrimes * Allocate a block in the file system. 808876Srgrimes * 811541Srgrimes * The size of the requested block is given, which must be some 821541Srgrimes * multiple of fs_fsize and <= fs_bsize. 831541Srgrimes * A preference may be optionally specified. If a preference is given 841541Srgrimes * the following hierarchy is used to allocate a block: 851541Srgrimes * 1) allocate the requested block. 861541Srgrimes * 2) allocate a rotationally optimal block in the same cylinder. 871541Srgrimes * 3) allocate a block in the same cylinder group. 881541Srgrimes * 4) quadradically rehash into other cylinder groups, until an 891541Srgrimes * available block is located. 901541Srgrimes * If no block preference is given the following heirarchy is used 911541Srgrimes * to allocate a block: 921541Srgrimes * 1) allocate a block in the cylinder group that contains the 931541Srgrimes * inode for the file. 941541Srgrimes * 2) quadradically rehash into other cylinder groups, until an 951541Srgrimes * available block is located. 961541Srgrimes */ 971549Srgrimesint 981541Srgrimesffs_alloc(ip, lbn, bpref, size, cred, bnp) 991541Srgrimes register struct inode *ip; 1001541Srgrimes daddr_t lbn, bpref; 1011541Srgrimes int size; 1021541Srgrimes struct ucred *cred; 1031541Srgrimes daddr_t *bnp; 1041541Srgrimes{ 1051541Srgrimes register struct fs *fs; 1061541Srgrimes daddr_t bno; 1076357Sphk int cg; 1086357Sphk#ifdef QUOTA 1096357Sphk int error; 1106357Sphk#endif 1118876Srgrimes 1128876Srgrimes 1131541Srgrimes *bnp = 0; 1141541Srgrimes fs = ip->i_fs; 1151541Srgrimes#ifdef DIAGNOSTIC 1161541Srgrimes if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1173487Sphk printf("dev = 0x%lx, bsize = %ld, size = %d, fs = %s\n", 1183487Sphk (u_long)ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 1191541Srgrimes panic("ffs_alloc: bad size"); 1201541Srgrimes } 1211541Srgrimes if (cred == NOCRED) 1227170Sdg panic("ffs_alloc: missing credential"); 1231541Srgrimes#endif /* DIAGNOSTIC */ 1241541Srgrimes if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 1251541Srgrimes goto nospace; 1261541Srgrimes if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) 1271541Srgrimes goto nospace; 1281541Srgrimes#ifdef QUOTA 1293487Sphk error = chkdq(ip, (long)btodb(size), cred, 0); 1303487Sphk if (error) 1311541Srgrimes return (error); 1321541Srgrimes#endif 1331541Srgrimes if (bpref >= fs->fs_size) 1341541Srgrimes bpref = 0; 1351541Srgrimes if (bpref == 0) 1361541Srgrimes cg = ino_to_cg(fs, ip->i_number); 1371541Srgrimes else 1381541Srgrimes cg = dtog(fs, bpref); 13912590Sbde bno = (daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, ffs_alloccg); 1401541Srgrimes if (bno > 0) { 1411541Srgrimes ip->i_blocks += btodb(size); 1421541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 1431541Srgrimes *bnp = bno; 1441541Srgrimes return (0); 1451541Srgrimes } 1461541Srgrimes#ifdef QUOTA 1471541Srgrimes /* 1481541Srgrimes * Restore user's disk quota because allocation failed. 1491541Srgrimes */ 1501541Srgrimes (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 1511541Srgrimes#endif 1521541Srgrimesnospace: 1531541Srgrimes ffs_fserr(fs, cred->cr_uid, "file system full"); 1541541Srgrimes uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 1551541Srgrimes return (ENOSPC); 1561541Srgrimes} 1571541Srgrimes 1581541Srgrimes/* 1591541Srgrimes * Reallocate a fragment to a bigger size 1601541Srgrimes * 1611541Srgrimes * The number and size of the old block is given, and a preference 1621541Srgrimes * and new size is also specified. The allocator attempts to extend 1631541Srgrimes * the original block. Failing that, the regular block allocator is 1641541Srgrimes * invoked to get an appropriate block. 1651541Srgrimes */ 1661549Srgrimesint 1671541Srgrimesffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp) 1681541Srgrimes register struct inode *ip; 1691541Srgrimes daddr_t lbprev; 1701541Srgrimes daddr_t bpref; 1711541Srgrimes int osize, nsize; 1721541Srgrimes struct ucred *cred; 1731541Srgrimes struct buf **bpp; 1741541Srgrimes{ 1751541Srgrimes register struct fs *fs; 1761541Srgrimes struct buf *bp; 1771541Srgrimes int cg, request, error; 1781541Srgrimes daddr_t bprev, bno; 1798876Srgrimes 1801541Srgrimes *bpp = 0; 1811541Srgrimes fs = ip->i_fs; 1821541Srgrimes#ifdef DIAGNOSTIC 1831541Srgrimes if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 1841541Srgrimes (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 1851541Srgrimes printf( 1868456Srgrimes "dev = 0x%lx, bsize = %ld, osize = %d, " 1878456Srgrimes "nsize = %d, fs = %s\n", 1888456Srgrimes (u_long)ip->i_dev, fs->fs_bsize, osize, 1898456Srgrimes nsize, fs->fs_fsmnt); 1901541Srgrimes panic("ffs_realloccg: bad size"); 1911541Srgrimes } 1921541Srgrimes if (cred == NOCRED) 1937170Sdg panic("ffs_realloccg: missing credential"); 1941541Srgrimes#endif /* DIAGNOSTIC */ 1951541Srgrimes if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) 1961541Srgrimes goto nospace; 1971541Srgrimes if ((bprev = ip->i_db[lbprev]) == 0) { 1986357Sphk printf("dev = 0x%lx, bsize = %ld, bprev = %ld, fs = %s\n", 1996357Sphk (u_long) ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt); 2001541Srgrimes panic("ffs_realloccg: bad bprev"); 2011541Srgrimes } 2021541Srgrimes /* 2031541Srgrimes * Allocate the extra space in the buffer. 2041541Srgrimes */ 2053487Sphk error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp); 2063487Sphk if (error) { 2071541Srgrimes brelse(bp); 2081541Srgrimes return (error); 2091541Srgrimes } 2106864Sdg 2116864Sdg if( bp->b_blkno == bp->b_lblkno) { 2126864Sdg if( lbprev >= NDADDR) 2136864Sdg panic("ffs_realloccg: lbprev out of range"); 2146864Sdg bp->b_blkno = fsbtodb(fs, bprev); 2156864Sdg } 2168876Srgrimes 2171541Srgrimes#ifdef QUOTA 2183487Sphk error = chkdq(ip, (long)btodb(nsize - osize), cred, 0); 2193487Sphk if (error) { 2201541Srgrimes brelse(bp); 2211541Srgrimes return (error); 2221541Srgrimes } 2231541Srgrimes#endif 2241541Srgrimes /* 2251541Srgrimes * Check for extension in the existing location. 2261541Srgrimes */ 2271541Srgrimes cg = dtog(fs, bprev); 2283487Sphk bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize); 2293487Sphk if (bno) { 2301541Srgrimes if (bp->b_blkno != fsbtodb(fs, bno)) 2311541Srgrimes panic("bad blockno"); 2321541Srgrimes ip->i_blocks += btodb(nsize - osize); 2331541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 2347399Sdg allocbuf(bp, nsize); 2351541Srgrimes bp->b_flags |= B_DONE; 2361541Srgrimes bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 2371541Srgrimes *bpp = bp; 2381541Srgrimes return (0); 2391541Srgrimes } 2401541Srgrimes /* 2411541Srgrimes * Allocate a new disk location. 2421541Srgrimes */ 2431541Srgrimes if (bpref >= fs->fs_size) 2441541Srgrimes bpref = 0; 2451541Srgrimes switch ((int)fs->fs_optim) { 2461541Srgrimes case FS_OPTSPACE: 2471541Srgrimes /* 2488876Srgrimes * Allocate an exact sized fragment. Although this makes 2498876Srgrimes * best use of space, we will waste time relocating it if 2501541Srgrimes * the file continues to grow. If the fragmentation is 2511541Srgrimes * less than half of the minimum free reserve, we choose 2521541Srgrimes * to begin optimizing for time. 2531541Srgrimes */ 2541541Srgrimes request = nsize; 2556993Sdg if (fs->fs_minfree <= 5 || 2561541Srgrimes fs->fs_cstotal.cs_nffree > 2571541Srgrimes fs->fs_dsize * fs->fs_minfree / (2 * 100)) 2581541Srgrimes break; 2591541Srgrimes log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 2601541Srgrimes fs->fs_fsmnt); 2611541Srgrimes fs->fs_optim = FS_OPTTIME; 2621541Srgrimes break; 2631541Srgrimes case FS_OPTTIME: 2641541Srgrimes /* 2651541Srgrimes * At this point we have discovered a file that is trying to 2661541Srgrimes * grow a small fragment to a larger fragment. To save time, 2671541Srgrimes * we allocate a full sized block, then free the unused portion. 2681541Srgrimes * If the file continues to grow, the `ffs_fragextend' call 2691541Srgrimes * above will be able to grow it in place without further 2701541Srgrimes * copying. If aberrant programs cause disk fragmentation to 2711541Srgrimes * grow within 2% of the free reserve, we choose to begin 2721541Srgrimes * optimizing for space. 2731541Srgrimes */ 2741541Srgrimes request = fs->fs_bsize; 2751541Srgrimes if (fs->fs_cstotal.cs_nffree < 2761541Srgrimes fs->fs_dsize * (fs->fs_minfree - 2) / 100) 2771541Srgrimes break; 2781541Srgrimes log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 2791541Srgrimes fs->fs_fsmnt); 2801541Srgrimes fs->fs_optim = FS_OPTSPACE; 2811541Srgrimes break; 2821541Srgrimes default: 2833487Sphk printf("dev = 0x%lx, optim = %ld, fs = %s\n", 2843487Sphk (u_long)ip->i_dev, fs->fs_optim, fs->fs_fsmnt); 2851541Srgrimes panic("ffs_realloccg: bad optim"); 2861541Srgrimes /* NOTREACHED */ 2871541Srgrimes } 28812590Sbde bno = (daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, ffs_alloccg); 2891541Srgrimes if (bno > 0) { 2901541Srgrimes bp->b_blkno = fsbtodb(fs, bno); 2911541Srgrimes ffs_blkfree(ip, bprev, (long)osize); 2921541Srgrimes if (nsize < request) 2931541Srgrimes ffs_blkfree(ip, bno + numfrags(fs, nsize), 2941541Srgrimes (long)(request - nsize)); 2951541Srgrimes ip->i_blocks += btodb(nsize - osize); 2961541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 2977399Sdg allocbuf(bp, nsize); 2981541Srgrimes bp->b_flags |= B_DONE; 2991541Srgrimes bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 3001541Srgrimes *bpp = bp; 3011541Srgrimes return (0); 3021541Srgrimes } 3031541Srgrimes#ifdef QUOTA 3041541Srgrimes /* 3051541Srgrimes * Restore user's disk quota because allocation failed. 3061541Srgrimes */ 3071541Srgrimes (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 3081541Srgrimes#endif 3091541Srgrimes brelse(bp); 3101541Srgrimesnospace: 3111541Srgrimes /* 3121541Srgrimes * no space available 3131541Srgrimes */ 3141541Srgrimes ffs_fserr(fs, cred->cr_uid, "file system full"); 3151541Srgrimes uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 3161541Srgrimes return (ENOSPC); 3171541Srgrimes} 3181541Srgrimes 3191541Srgrimes/* 3201541Srgrimes * Reallocate a sequence of blocks into a contiguous sequence of blocks. 3211541Srgrimes * 3221541Srgrimes * The vnode and an array of buffer pointers for a range of sequential 3231541Srgrimes * logical blocks to be made contiguous is given. The allocator attempts 3241541Srgrimes * to find a range of sequential blocks starting as close as possible to 3251541Srgrimes * an fs_rotdelay offset from the end of the allocation for the logical 3261541Srgrimes * block immediately preceeding the current range. If successful, the 3271541Srgrimes * physical block numbers in the buffer pointers and in the inode are 3281541Srgrimes * changed to reflect the new allocation. If unsuccessful, the allocation 3291541Srgrimes * is left unchanged. The success in doing the reallocation is returned. 3301541Srgrimes * Note that the error return is not reflected back to the user. Rather 3311541Srgrimes * the previous block allocation will be used. 3321541Srgrimes */ 33312911Sphkstatic int doasyncfree = 1; 33412911SphkSYSCTL_INT(_debug, OID_AUTO, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, ""); 3351541Srgrimesint 3361541Srgrimesffs_reallocblks(ap) 3371541Srgrimes struct vop_reallocblks_args /* { 3381541Srgrimes struct vnode *a_vp; 3391541Srgrimes struct cluster_save *a_buflist; 3401541Srgrimes } */ *ap; 3411541Srgrimes{ 34212911Sphk#if !defined (not_yes) 34312405Sdyson return (ENOSPC); 34412405Sdyson#else 3451541Srgrimes struct fs *fs; 3461541Srgrimes struct inode *ip; 3471541Srgrimes struct vnode *vp; 3481541Srgrimes struct buf *sbp, *ebp; 3491549Srgrimes daddr_t *bap, *sbap, *ebap = 0; 3501541Srgrimes struct cluster_save *buflist; 3513487Sphk daddr_t start_lbn, end_lbn, soff, newblk, blkno; 3521541Srgrimes struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 3531541Srgrimes int i, len, start_lvl, end_lvl, pref, ssize; 35410269Sbde struct timeval tv; 3551541Srgrimes 3561541Srgrimes vp = ap->a_vp; 3571541Srgrimes ip = VTOI(vp); 3581541Srgrimes fs = ip->i_fs; 3591541Srgrimes if (fs->fs_contigsumsize <= 0) 3601541Srgrimes return (ENOSPC); 3611541Srgrimes buflist = ap->a_buflist; 3621541Srgrimes len = buflist->bs_nchildren; 3631541Srgrimes start_lbn = buflist->bs_children[0]->b_lblkno; 3641541Srgrimes end_lbn = start_lbn + len - 1; 3651541Srgrimes#ifdef DIAGNOSTIC 3661541Srgrimes for (i = 1; i < len; i++) 3671541Srgrimes if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 3681541Srgrimes panic("ffs_reallocblks: non-cluster"); 3691541Srgrimes#endif 3701541Srgrimes /* 3711541Srgrimes * If the latest allocation is in a new cylinder group, assume that 3721541Srgrimes * the filesystem has decided to move and do not force it back to 3731541Srgrimes * the previous cylinder group. 3741541Srgrimes */ 3751541Srgrimes if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 3761541Srgrimes dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 3771541Srgrimes return (ENOSPC); 3781541Srgrimes if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 3791541Srgrimes ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 3801541Srgrimes return (ENOSPC); 3811541Srgrimes /* 3821541Srgrimes * Get the starting offset and block map for the first block. 3831541Srgrimes */ 3841541Srgrimes if (start_lvl == 0) { 3851541Srgrimes sbap = &ip->i_db[0]; 3861541Srgrimes soff = start_lbn; 3871541Srgrimes } else { 3881541Srgrimes idp = &start_ap[start_lvl - 1]; 3891541Srgrimes if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 3901541Srgrimes brelse(sbp); 3911541Srgrimes return (ENOSPC); 3921541Srgrimes } 3931541Srgrimes sbap = (daddr_t *)sbp->b_data; 3941541Srgrimes soff = idp->in_off; 3951541Srgrimes } 3961541Srgrimes /* 3971541Srgrimes * Find the preferred location for the cluster. 3981541Srgrimes */ 3991541Srgrimes pref = ffs_blkpref(ip, start_lbn, soff, sbap); 4001541Srgrimes /* 4011541Srgrimes * If the block range spans two block maps, get the second map. 4021541Srgrimes */ 4031541Srgrimes if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 4041541Srgrimes ssize = len; 4051541Srgrimes } else { 4061541Srgrimes#ifdef DIAGNOSTIC 4071541Srgrimes if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 4081541Srgrimes panic("ffs_reallocblk: start == end"); 4091541Srgrimes#endif 4101541Srgrimes ssize = len - (idp->in_off + 1); 4111541Srgrimes if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 4121541Srgrimes goto fail; 4131541Srgrimes ebap = (daddr_t *)ebp->b_data; 4141541Srgrimes } 4151541Srgrimes /* 4161541Srgrimes * Search the block map looking for an allocation of the desired size. 4171541Srgrimes */ 4181541Srgrimes if ((newblk = (daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref, 41912590Sbde len, ffs_clusteralloc)) == 0) 4201541Srgrimes goto fail; 4211541Srgrimes /* 4221541Srgrimes * We have found a new contiguous block. 4231541Srgrimes * 4241541Srgrimes * First we have to replace the old block pointers with the new 4251541Srgrimes * block pointers in the inode and indirect blocks associated 4261541Srgrimes * with the file. 4271541Srgrimes */ 4281541Srgrimes blkno = newblk; 4291541Srgrimes for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 4301541Srgrimes if (i == ssize) 4311541Srgrimes bap = ebap; 4321541Srgrimes#ifdef DIAGNOSTIC 4331541Srgrimes if (buflist->bs_children[i]->b_blkno != fsbtodb(fs, *bap)) 4341541Srgrimes panic("ffs_reallocblks: alloc mismatch"); 4351541Srgrimes#endif 4361541Srgrimes *bap++ = blkno; 4371541Srgrimes } 4381541Srgrimes /* 4391541Srgrimes * Next we must write out the modified inode and indirect blocks. 4401541Srgrimes * For strict correctness, the writes should be synchronous since 4411541Srgrimes * the old block values may have been written to disk. In practise 4428876Srgrimes * they are almost never written, but if we are concerned about 4431541Srgrimes * strict correctness, the `doasyncfree' flag should be set to zero. 4441541Srgrimes * 4451541Srgrimes * The test on `doasyncfree' should be changed to test a flag 4461541Srgrimes * that shows whether the associated buffers and inodes have 4471541Srgrimes * been written. The flag should be set when the cluster is 4481541Srgrimes * started and cleared whenever the buffer or inode is flushed. 4491541Srgrimes * We can then check below to see if it is set, and do the 4501541Srgrimes * synchronous write only when it has been cleared. 4511541Srgrimes */ 4521541Srgrimes if (sbap != &ip->i_db[0]) { 4531541Srgrimes if (doasyncfree) 4541541Srgrimes bdwrite(sbp); 4551541Srgrimes else 4561541Srgrimes bwrite(sbp); 4571541Srgrimes } else { 4581541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 45910269Sbde if (!doasyncfree) { 46010269Sbde tv = time; 46110269Sbde VOP_UPDATE(vp, &tv, &tv, 1); 46210269Sbde } 4631541Srgrimes } 4641541Srgrimes if (ssize < len) 4651541Srgrimes if (doasyncfree) 4661541Srgrimes bdwrite(ebp); 4671541Srgrimes else 4681541Srgrimes bwrite(ebp); 4691541Srgrimes /* 4701541Srgrimes * Last, free the old blocks and assign the new blocks to the buffers. 4711541Srgrimes */ 4721541Srgrimes for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 4731541Srgrimes ffs_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno), 4741541Srgrimes fs->fs_bsize); 4751541Srgrimes buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 4761541Srgrimes } 4771541Srgrimes return (0); 4781541Srgrimes 4791541Srgrimesfail: 4801541Srgrimes if (ssize < len) 4811541Srgrimes brelse(ebp); 4821541Srgrimes if (sbap != &ip->i_db[0]) 4831541Srgrimes brelse(sbp); 4841541Srgrimes return (ENOSPC); 48512405Sdyson#endif 4861541Srgrimes} 4871541Srgrimes 4881541Srgrimes/* 4891541Srgrimes * Allocate an inode in the file system. 4908876Srgrimes * 4911541Srgrimes * If allocating a directory, use ffs_dirpref to select the inode. 4921541Srgrimes * If allocating in a directory, the following hierarchy is followed: 4931541Srgrimes * 1) allocate the preferred inode. 4941541Srgrimes * 2) allocate an inode in the same cylinder group. 4951541Srgrimes * 3) quadradically rehash into other cylinder groups, until an 4961541Srgrimes * available inode is located. 4971541Srgrimes * If no inode preference is given the following heirarchy is used 4981541Srgrimes * to allocate an inode: 4991541Srgrimes * 1) allocate an inode in cylinder group 0. 5001541Srgrimes * 2) quadradically rehash into other cylinder groups, until an 5011541Srgrimes * available inode is located. 5021541Srgrimes */ 5031549Srgrimesint 5041541Srgrimesffs_valloc(ap) 5051541Srgrimes struct vop_valloc_args /* { 5061541Srgrimes struct vnode *a_pvp; 5071541Srgrimes int a_mode; 5081541Srgrimes struct ucred *a_cred; 5091541Srgrimes struct vnode **a_vpp; 5101541Srgrimes } */ *ap; 5111541Srgrimes{ 5121541Srgrimes register struct vnode *pvp = ap->a_pvp; 5131541Srgrimes register struct inode *pip; 5141541Srgrimes register struct fs *fs; 5151541Srgrimes register struct inode *ip; 5161541Srgrimes mode_t mode = ap->a_mode; 5171541Srgrimes ino_t ino, ipref; 5181541Srgrimes int cg, error; 5198876Srgrimes 5201541Srgrimes *ap->a_vpp = NULL; 5211541Srgrimes pip = VTOI(pvp); 5221541Srgrimes fs = pip->i_fs; 5231541Srgrimes if (fs->fs_cstotal.cs_nifree == 0) 5241541Srgrimes goto noinodes; 5251541Srgrimes 5261541Srgrimes if ((mode & IFMT) == IFDIR) 5271541Srgrimes ipref = ffs_dirpref(fs); 5281541Srgrimes else 5291541Srgrimes ipref = pip->i_number; 5301541Srgrimes if (ipref >= fs->fs_ncg * fs->fs_ipg) 5311541Srgrimes ipref = 0; 5321541Srgrimes cg = ino_to_cg(fs, ipref); 53312861Speter ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, 53412861Speter (allocfcn_t *)ffs_nodealloccg); 5351541Srgrimes if (ino == 0) 5361541Srgrimes goto noinodes; 5371541Srgrimes error = VFS_VGET(pvp->v_mount, ino, ap->a_vpp); 5381541Srgrimes if (error) { 5391541Srgrimes VOP_VFREE(pvp, ino, mode); 5401541Srgrimes return (error); 5411541Srgrimes } 5421541Srgrimes ip = VTOI(*ap->a_vpp); 5431541Srgrimes if (ip->i_mode) { 5443487Sphk printf("mode = 0%o, inum = %ld, fs = %s\n", 5451541Srgrimes ip->i_mode, ip->i_number, fs->fs_fsmnt); 5461541Srgrimes panic("ffs_valloc: dup alloc"); 5471541Srgrimes } 5481541Srgrimes if (ip->i_blocks) { /* XXX */ 5493487Sphk printf("free inode %s/%ld had %ld blocks\n", 5501541Srgrimes fs->fs_fsmnt, ino, ip->i_blocks); 5511541Srgrimes ip->i_blocks = 0; 5521541Srgrimes } 5531541Srgrimes ip->i_flags = 0; 5541541Srgrimes /* 5551541Srgrimes * Set up a new generation number for this inode. 5561541Srgrimes */ 5571541Srgrimes if (++nextgennumber < (u_long)time.tv_sec) 5581541Srgrimes nextgennumber = time.tv_sec; 5591541Srgrimes ip->i_gen = nextgennumber; 5601541Srgrimes return (0); 5611541Srgrimesnoinodes: 5621541Srgrimes ffs_fserr(fs, ap->a_cred->cr_uid, "out of inodes"); 5631541Srgrimes uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 5641541Srgrimes return (ENOSPC); 5651541Srgrimes} 5661541Srgrimes 5671541Srgrimes/* 5681541Srgrimes * Find a cylinder to place a directory. 5691541Srgrimes * 5701541Srgrimes * The policy implemented by this algorithm is to select from 5711541Srgrimes * among those cylinder groups with above the average number of 5721541Srgrimes * free inodes, the one with the smallest number of directories. 5731541Srgrimes */ 5741541Srgrimesstatic ino_t 5751541Srgrimesffs_dirpref(fs) 5761541Srgrimes register struct fs *fs; 5771541Srgrimes{ 5781541Srgrimes int cg, minndir, mincg, avgifree; 5791541Srgrimes 5801541Srgrimes avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 5811541Srgrimes minndir = fs->fs_ipg; 5821541Srgrimes mincg = 0; 5831541Srgrimes for (cg = 0; cg < fs->fs_ncg; cg++) 5841541Srgrimes if (fs->fs_cs(fs, cg).cs_ndir < minndir && 5851541Srgrimes fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 5861541Srgrimes mincg = cg; 5871541Srgrimes minndir = fs->fs_cs(fs, cg).cs_ndir; 5881541Srgrimes } 5891541Srgrimes return ((ino_t)(fs->fs_ipg * mincg)); 5901541Srgrimes} 5911541Srgrimes 5921541Srgrimes/* 5931541Srgrimes * Select the desired position for the next block in a file. The file is 5941541Srgrimes * logically divided into sections. The first section is composed of the 5951541Srgrimes * direct blocks. Each additional section contains fs_maxbpg blocks. 5968876Srgrimes * 5971541Srgrimes * If no blocks have been allocated in the first section, the policy is to 5981541Srgrimes * request a block in the same cylinder group as the inode that describes 5991541Srgrimes * the file. If no blocks have been allocated in any other section, the 6001541Srgrimes * policy is to place the section in a cylinder group with a greater than 6011541Srgrimes * average number of free blocks. An appropriate cylinder group is found 6021541Srgrimes * by using a rotor that sweeps the cylinder groups. When a new group of 6031541Srgrimes * blocks is needed, the sweep begins in the cylinder group following the 6041541Srgrimes * cylinder group from which the previous allocation was made. The sweep 6051541Srgrimes * continues until a cylinder group with greater than the average number 6061541Srgrimes * of free blocks is found. If the allocation is for the first block in an 6071541Srgrimes * indirect block, the information on the previous allocation is unavailable; 6081541Srgrimes * here a best guess is made based upon the logical block number being 6091541Srgrimes * allocated. 6108876Srgrimes * 6111541Srgrimes * If a section is already partially allocated, the policy is to 6121541Srgrimes * contiguously allocate fs_maxcontig blocks. The end of one of these 6131541Srgrimes * contiguous blocks and the beginning of the next is physically separated 6141541Srgrimes * so that the disk head will be in transit between them for at least 6151541Srgrimes * fs_rotdelay milliseconds. This is to allow time for the processor to 6161541Srgrimes * schedule another I/O transfer. 6171541Srgrimes */ 6181541Srgrimesdaddr_t 6191541Srgrimesffs_blkpref(ip, lbn, indx, bap) 6201541Srgrimes struct inode *ip; 6211541Srgrimes daddr_t lbn; 6221541Srgrimes int indx; 6231541Srgrimes daddr_t *bap; 6241541Srgrimes{ 6251541Srgrimes register struct fs *fs; 6261541Srgrimes register int cg; 6271541Srgrimes int avgbfree, startcg; 6281541Srgrimes daddr_t nextblk; 6291541Srgrimes 6301541Srgrimes fs = ip->i_fs; 6311541Srgrimes if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 6321541Srgrimes if (lbn < NDADDR) { 6331541Srgrimes cg = ino_to_cg(fs, ip->i_number); 6341541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 6351541Srgrimes } 6361541Srgrimes /* 6371541Srgrimes * Find a cylinder with greater than average number of 6381541Srgrimes * unused data blocks. 6391541Srgrimes */ 6401541Srgrimes if (indx == 0 || bap[indx - 1] == 0) 6411541Srgrimes startcg = 6421541Srgrimes ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 6431541Srgrimes else 6441541Srgrimes startcg = dtog(fs, bap[indx - 1]) + 1; 6451541Srgrimes startcg %= fs->fs_ncg; 6461541Srgrimes avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 6471541Srgrimes for (cg = startcg; cg < fs->fs_ncg; cg++) 6481541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 6491541Srgrimes fs->fs_cgrotor = cg; 6501541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 6511541Srgrimes } 6521541Srgrimes for (cg = 0; cg <= startcg; cg++) 6531541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 6541541Srgrimes fs->fs_cgrotor = cg; 6551541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 6561541Srgrimes } 65717108Sbde return (0); 6581541Srgrimes } 6591541Srgrimes /* 6601541Srgrimes * One or more previous blocks have been laid out. If less 6611541Srgrimes * than fs_maxcontig previous blocks are contiguous, the 6621541Srgrimes * next block is requested contiguously, otherwise it is 6631541Srgrimes * requested rotationally delayed by fs_rotdelay milliseconds. 6641541Srgrimes */ 6651541Srgrimes nextblk = bap[indx - 1] + fs->fs_frag; 66610632Sdg if (fs->fs_rotdelay == 0 || indx < fs->fs_maxcontig || 66710632Sdg bap[indx - fs->fs_maxcontig] + 6681541Srgrimes blkstofrags(fs, fs->fs_maxcontig) != nextblk) 6691541Srgrimes return (nextblk); 67010632Sdg /* 67110632Sdg * Here we convert ms of delay to frags as: 67210632Sdg * (frags) = (ms) * (rev/sec) * (sect/rev) / 67310632Sdg * ((sect/frag) * (ms/sec)) 67410632Sdg * then round up to the next block. 67510632Sdg */ 67610632Sdg nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 67710632Sdg (NSPF(fs) * 1000), fs->fs_frag); 6781541Srgrimes return (nextblk); 6791541Srgrimes} 6801541Srgrimes 6811541Srgrimes/* 6821541Srgrimes * Implement the cylinder overflow algorithm. 6831541Srgrimes * 6841541Srgrimes * The policy implemented by this algorithm is: 6851541Srgrimes * 1) allocate the block in its requested cylinder group. 6861541Srgrimes * 2) quadradically rehash on the cylinder group number. 6871541Srgrimes * 3) brute force search for a free block. 6881541Srgrimes */ 6891541Srgrimes/*VARARGS5*/ 6901541Srgrimesstatic u_long 6911541Srgrimesffs_hashalloc(ip, cg, pref, size, allocator) 6921541Srgrimes struct inode *ip; 6931541Srgrimes int cg; 6941541Srgrimes long pref; 6951541Srgrimes int size; /* size for data blocks, mode for inodes */ 69612590Sbde allocfcn_t *allocator; 6971541Srgrimes{ 6981541Srgrimes register struct fs *fs; 69912590Sbde long result; /* XXX why not same type as we return? */ 7001541Srgrimes int i, icg = cg; 7011541Srgrimes 7021541Srgrimes fs = ip->i_fs; 7031541Srgrimes /* 7041541Srgrimes * 1: preferred cylinder group 7051541Srgrimes */ 7061541Srgrimes result = (*allocator)(ip, cg, pref, size); 7071541Srgrimes if (result) 7081541Srgrimes return (result); 7091541Srgrimes /* 7101541Srgrimes * 2: quadratic rehash 7111541Srgrimes */ 7121541Srgrimes for (i = 1; i < fs->fs_ncg; i *= 2) { 7131541Srgrimes cg += i; 7141541Srgrimes if (cg >= fs->fs_ncg) 7151541Srgrimes cg -= fs->fs_ncg; 7161541Srgrimes result = (*allocator)(ip, cg, 0, size); 7171541Srgrimes if (result) 7181541Srgrimes return (result); 7191541Srgrimes } 7201541Srgrimes /* 7211541Srgrimes * 3: brute force search 7221541Srgrimes * Note that we start at i == 2, since 0 was checked initially, 7231541Srgrimes * and 1 is always checked in the quadratic rehash. 7241541Srgrimes */ 7251541Srgrimes cg = (icg + 2) % fs->fs_ncg; 7261541Srgrimes for (i = 2; i < fs->fs_ncg; i++) { 7271541Srgrimes result = (*allocator)(ip, cg, 0, size); 7281541Srgrimes if (result) 7291541Srgrimes return (result); 7301541Srgrimes cg++; 7311541Srgrimes if (cg == fs->fs_ncg) 7321541Srgrimes cg = 0; 7331541Srgrimes } 73412590Sbde return (0); 7351541Srgrimes} 7361541Srgrimes 7371541Srgrimes/* 7381541Srgrimes * Determine whether a fragment can be extended. 7391541Srgrimes * 7408876Srgrimes * Check to see if the necessary fragments are available, and 7411541Srgrimes * if they are, allocate them. 7421541Srgrimes */ 7431541Srgrimesstatic daddr_t 7441541Srgrimesffs_fragextend(ip, cg, bprev, osize, nsize) 7451541Srgrimes struct inode *ip; 7461541Srgrimes int cg; 7471541Srgrimes long bprev; 7481541Srgrimes int osize, nsize; 7491541Srgrimes{ 7501541Srgrimes register struct fs *fs; 7511541Srgrimes register struct cg *cgp; 7521541Srgrimes struct buf *bp; 7531541Srgrimes long bno; 7541541Srgrimes int frags, bbase; 7551541Srgrimes int i, error; 7561541Srgrimes 7571541Srgrimes fs = ip->i_fs; 7581541Srgrimes if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 75917108Sbde return (0); 7601541Srgrimes frags = numfrags(fs, nsize); 7611541Srgrimes bbase = fragnum(fs, bprev); 7621541Srgrimes if (bbase > fragnum(fs, (bprev + frags - 1))) { 7631541Srgrimes /* cannot extend across a block boundary */ 76417108Sbde return (0); 7651541Srgrimes } 7661541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 7671541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 7681541Srgrimes if (error) { 7691541Srgrimes brelse(bp); 77017108Sbde return (0); 7711541Srgrimes } 7721541Srgrimes cgp = (struct cg *)bp->b_data; 7731541Srgrimes if (!cg_chkmagic(cgp)) { 7741541Srgrimes brelse(bp); 77517108Sbde return (0); 7761541Srgrimes } 7771541Srgrimes cgp->cg_time = time.tv_sec; 7781541Srgrimes bno = dtogd(fs, bprev); 7791541Srgrimes for (i = numfrags(fs, osize); i < frags; i++) 7801541Srgrimes if (isclr(cg_blksfree(cgp), bno + i)) { 7811541Srgrimes brelse(bp); 78217108Sbde return (0); 7831541Srgrimes } 7841541Srgrimes /* 7851541Srgrimes * the current fragment can be extended 7861541Srgrimes * deduct the count on fragment being extended into 7871541Srgrimes * increase the count on the remaining fragment (if any) 7881541Srgrimes * allocate the extended piece 7891541Srgrimes */ 7901541Srgrimes for (i = frags; i < fs->fs_frag - bbase; i++) 7911541Srgrimes if (isclr(cg_blksfree(cgp), bno + i)) 7921541Srgrimes break; 7931541Srgrimes cgp->cg_frsum[i - numfrags(fs, osize)]--; 7941541Srgrimes if (i != frags) 7951541Srgrimes cgp->cg_frsum[i - frags]++; 7961541Srgrimes for (i = numfrags(fs, osize); i < frags; i++) { 7971541Srgrimes clrbit(cg_blksfree(cgp), bno + i); 7981541Srgrimes cgp->cg_cs.cs_nffree--; 7991541Srgrimes fs->fs_cstotal.cs_nffree--; 8001541Srgrimes fs->fs_cs(fs, cg).cs_nffree--; 8011541Srgrimes } 8021541Srgrimes fs->fs_fmod = 1; 8031541Srgrimes bdwrite(bp); 8041541Srgrimes return (bprev); 8051541Srgrimes} 8061541Srgrimes 8071541Srgrimes/* 8081541Srgrimes * Determine whether a block can be allocated. 8091541Srgrimes * 8101541Srgrimes * Check to see if a block of the appropriate size is available, 8111541Srgrimes * and if it is, allocate it. 8121541Srgrimes */ 8131541Srgrimesstatic daddr_t 8141541Srgrimesffs_alloccg(ip, cg, bpref, size) 8151541Srgrimes struct inode *ip; 8161541Srgrimes int cg; 8171541Srgrimes daddr_t bpref; 8181541Srgrimes int size; 8191541Srgrimes{ 8201541Srgrimes register struct fs *fs; 8211541Srgrimes register struct cg *cgp; 8221541Srgrimes struct buf *bp; 8231541Srgrimes register int i; 8241541Srgrimes int error, bno, frags, allocsiz; 8251541Srgrimes 8261541Srgrimes fs = ip->i_fs; 8271541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 82817108Sbde return (0); 8291541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 8301541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 8311541Srgrimes if (error) { 8321541Srgrimes brelse(bp); 83317108Sbde return (0); 8341541Srgrimes } 8351541Srgrimes cgp = (struct cg *)bp->b_data; 8361541Srgrimes if (!cg_chkmagic(cgp) || 8371541Srgrimes (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 8381541Srgrimes brelse(bp); 83917108Sbde return (0); 8401541Srgrimes } 8411541Srgrimes cgp->cg_time = time.tv_sec; 8421541Srgrimes if (size == fs->fs_bsize) { 8431541Srgrimes bno = ffs_alloccgblk(fs, cgp, bpref); 8441541Srgrimes bdwrite(bp); 8451541Srgrimes return (bno); 8461541Srgrimes } 8471541Srgrimes /* 8481541Srgrimes * check to see if any fragments are already available 8491541Srgrimes * allocsiz is the size which will be allocated, hacking 8501541Srgrimes * it down to a smaller size if necessary 8511541Srgrimes */ 8521541Srgrimes frags = numfrags(fs, size); 8531541Srgrimes for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 8541541Srgrimes if (cgp->cg_frsum[allocsiz] != 0) 8551541Srgrimes break; 8561541Srgrimes if (allocsiz == fs->fs_frag) { 8571541Srgrimes /* 8588876Srgrimes * no fragments were available, so a block will be 8591541Srgrimes * allocated, and hacked up 8601541Srgrimes */ 8611541Srgrimes if (cgp->cg_cs.cs_nbfree == 0) { 8621541Srgrimes brelse(bp); 86317108Sbde return (0); 8641541Srgrimes } 8651541Srgrimes bno = ffs_alloccgblk(fs, cgp, bpref); 8661541Srgrimes bpref = dtogd(fs, bno); 8671541Srgrimes for (i = frags; i < fs->fs_frag; i++) 8681541Srgrimes setbit(cg_blksfree(cgp), bpref + i); 8691541Srgrimes i = fs->fs_frag - frags; 8701541Srgrimes cgp->cg_cs.cs_nffree += i; 8711541Srgrimes fs->fs_cstotal.cs_nffree += i; 8721541Srgrimes fs->fs_cs(fs, cg).cs_nffree += i; 8731541Srgrimes fs->fs_fmod = 1; 8741541Srgrimes cgp->cg_frsum[i]++; 8751541Srgrimes bdwrite(bp); 8761541Srgrimes return (bno); 8771541Srgrimes } 8781541Srgrimes bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 8791541Srgrimes if (bno < 0) { 8801541Srgrimes brelse(bp); 88117108Sbde return (0); 8821541Srgrimes } 8831541Srgrimes for (i = 0; i < frags; i++) 8841541Srgrimes clrbit(cg_blksfree(cgp), bno + i); 8851541Srgrimes cgp->cg_cs.cs_nffree -= frags; 8861541Srgrimes fs->fs_cstotal.cs_nffree -= frags; 8871541Srgrimes fs->fs_cs(fs, cg).cs_nffree -= frags; 8881541Srgrimes fs->fs_fmod = 1; 8891541Srgrimes cgp->cg_frsum[allocsiz]--; 8901541Srgrimes if (frags != allocsiz) 8911541Srgrimes cgp->cg_frsum[allocsiz - frags]++; 8921541Srgrimes bdwrite(bp); 8931541Srgrimes return (cg * fs->fs_fpg + bno); 8941541Srgrimes} 8951541Srgrimes 8961541Srgrimes/* 8971541Srgrimes * Allocate a block in a cylinder group. 8981541Srgrimes * 8991541Srgrimes * This algorithm implements the following policy: 9001541Srgrimes * 1) allocate the requested block. 9011541Srgrimes * 2) allocate a rotationally optimal block in the same cylinder. 9021541Srgrimes * 3) allocate the next available block on the block rotor for the 9031541Srgrimes * specified cylinder group. 9041541Srgrimes * Note that this routine only allocates fs_bsize blocks; these 9051541Srgrimes * blocks may be fragmented by the routine that allocates them. 9061541Srgrimes */ 9071541Srgrimesstatic daddr_t 9081541Srgrimesffs_alloccgblk(fs, cgp, bpref) 9091541Srgrimes register struct fs *fs; 9101541Srgrimes register struct cg *cgp; 9111541Srgrimes daddr_t bpref; 9121541Srgrimes{ 9131541Srgrimes daddr_t bno, blkno; 9141541Srgrimes int cylno, pos, delta; 9151541Srgrimes short *cylbp; 9161541Srgrimes register int i; 9171541Srgrimes 9181541Srgrimes if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) { 9191541Srgrimes bpref = cgp->cg_rotor; 9201541Srgrimes goto norot; 9211541Srgrimes } 9221541Srgrimes bpref = blknum(fs, bpref); 9231541Srgrimes bpref = dtogd(fs, bpref); 9241541Srgrimes /* 9251541Srgrimes * if the requested block is available, use it 9261541Srgrimes */ 9271541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) { 9281541Srgrimes bno = bpref; 9291541Srgrimes goto gotit; 9301541Srgrimes } 9316769Sse if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) { 9321541Srgrimes /* 9331541Srgrimes * Block layout information is not available. 9341541Srgrimes * Leaving bpref unchanged means we take the 9358876Srgrimes * next available free block following the one 9361541Srgrimes * we just allocated. Hopefully this will at 9371541Srgrimes * least hit a track cache on drives of unknown 9381541Srgrimes * geometry (e.g. SCSI). 9391541Srgrimes */ 9401541Srgrimes goto norot; 9411541Srgrimes } 9421541Srgrimes /* 9436769Sse * check for a block available on the same cylinder 9446769Sse */ 9456769Sse cylno = cbtocylno(fs, bpref); 9466769Sse if (cg_blktot(cgp)[cylno] == 0) 9476769Sse goto norot; 9486769Sse /* 9498876Srgrimes * check the summary information to see if a block is 9501541Srgrimes * available in the requested cylinder starting at the 9511541Srgrimes * requested rotational position and proceeding around. 9521541Srgrimes */ 9531541Srgrimes cylbp = cg_blks(fs, cgp, cylno); 9541541Srgrimes pos = cbtorpos(fs, bpref); 9551541Srgrimes for (i = pos; i < fs->fs_nrpos; i++) 9561541Srgrimes if (cylbp[i] > 0) 9571541Srgrimes break; 9581541Srgrimes if (i == fs->fs_nrpos) 9591541Srgrimes for (i = 0; i < pos; i++) 9601541Srgrimes if (cylbp[i] > 0) 9611541Srgrimes break; 9621541Srgrimes if (cylbp[i] > 0) { 9631541Srgrimes /* 9641541Srgrimes * found a rotational position, now find the actual 9651541Srgrimes * block. A panic if none is actually there. 9661541Srgrimes */ 9671541Srgrimes pos = cylno % fs->fs_cpc; 9681541Srgrimes bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 9691541Srgrimes if (fs_postbl(fs, pos)[i] == -1) { 9701541Srgrimes printf("pos = %d, i = %d, fs = %s\n", 9711541Srgrimes pos, i, fs->fs_fsmnt); 9721541Srgrimes panic("ffs_alloccgblk: cyl groups corrupted"); 9731541Srgrimes } 9741541Srgrimes for (i = fs_postbl(fs, pos)[i];; ) { 9751541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), bno + i)) { 9761541Srgrimes bno = blkstofrags(fs, (bno + i)); 9771541Srgrimes goto gotit; 9781541Srgrimes } 9791541Srgrimes delta = fs_rotbl(fs)[i]; 9801541Srgrimes if (delta <= 0 || 9811541Srgrimes delta + i > fragstoblks(fs, fs->fs_fpg)) 9821541Srgrimes break; 9831541Srgrimes i += delta; 9841541Srgrimes } 9851541Srgrimes printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 9861541Srgrimes panic("ffs_alloccgblk: can't find blk in cyl"); 9871541Srgrimes } 9881541Srgrimesnorot: 9891541Srgrimes /* 9901541Srgrimes * no blocks in the requested cylinder, so take next 9911541Srgrimes * available one in this cylinder group. 9921541Srgrimes */ 9931541Srgrimes bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 9941541Srgrimes if (bno < 0) 99517108Sbde return (0); 9961541Srgrimes cgp->cg_rotor = bno; 9971541Srgrimesgotit: 9981541Srgrimes blkno = fragstoblks(fs, bno); 9991541Srgrimes ffs_clrblock(fs, cg_blksfree(cgp), (long)blkno); 10001541Srgrimes ffs_clusteracct(fs, cgp, blkno, -1); 10011541Srgrimes cgp->cg_cs.cs_nbfree--; 10021541Srgrimes fs->fs_cstotal.cs_nbfree--; 10031541Srgrimes fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 10041541Srgrimes cylno = cbtocylno(fs, bno); 10051541Srgrimes cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 10061541Srgrimes cg_blktot(cgp)[cylno]--; 10071541Srgrimes fs->fs_fmod = 1; 10081541Srgrimes return (cgp->cg_cgx * fs->fs_fpg + bno); 10091541Srgrimes} 10101541Srgrimes 101112911Sphk#ifdef notyet 10121541Srgrimes/* 10131541Srgrimes * Determine whether a cluster can be allocated. 10141541Srgrimes * 10151541Srgrimes * We do not currently check for optimal rotational layout if there 10161541Srgrimes * are multiple choices in the same cylinder group. Instead we just 10171541Srgrimes * take the first one that we find following bpref. 10181541Srgrimes */ 10191541Srgrimesstatic daddr_t 10201541Srgrimesffs_clusteralloc(ip, cg, bpref, len) 10211541Srgrimes struct inode *ip; 10221541Srgrimes int cg; 10231541Srgrimes daddr_t bpref; 10241541Srgrimes int len; 10251541Srgrimes{ 10261541Srgrimes register struct fs *fs; 10271541Srgrimes register struct cg *cgp; 10281541Srgrimes struct buf *bp; 10291541Srgrimes int i, run, bno, bit, map; 10301541Srgrimes u_char *mapp; 10311541Srgrimes 10321541Srgrimes fs = ip->i_fs; 10331541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree < len) 10341541Srgrimes return (NULL); 10351541Srgrimes if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 10361541Srgrimes NOCRED, &bp)) 10371541Srgrimes goto fail; 10381541Srgrimes cgp = (struct cg *)bp->b_data; 10391541Srgrimes if (!cg_chkmagic(cgp)) 10401541Srgrimes goto fail; 10411541Srgrimes /* 10421541Srgrimes * Check to see if a cluster of the needed size (or bigger) is 10431541Srgrimes * available in this cylinder group. 10441541Srgrimes */ 10451541Srgrimes for (i = len; i <= fs->fs_contigsumsize; i++) 10461541Srgrimes if (cg_clustersum(cgp)[i] > 0) 10471541Srgrimes break; 10481541Srgrimes if (i > fs->fs_contigsumsize) 10491541Srgrimes goto fail; 10501541Srgrimes /* 10511541Srgrimes * Search the cluster map to find a big enough cluster. 10521541Srgrimes * We take the first one that we find, even if it is larger 10531541Srgrimes * than we need as we prefer to get one close to the previous 10541541Srgrimes * block allocation. We do not search before the current 10551541Srgrimes * preference point as we do not want to allocate a block 10561541Srgrimes * that is allocated before the previous one (as we will 10571541Srgrimes * then have to wait for another pass of the elevator 10581541Srgrimes * algorithm before it will be read). We prefer to fail and 10591541Srgrimes * be recalled to try an allocation in the next cylinder group. 10601541Srgrimes */ 10611541Srgrimes if (dtog(fs, bpref) != cg) 10621541Srgrimes bpref = 0; 10631541Srgrimes else 10641541Srgrimes bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 10651541Srgrimes mapp = &cg_clustersfree(cgp)[bpref / NBBY]; 10661541Srgrimes map = *mapp++; 10671541Srgrimes bit = 1 << (bpref % NBBY); 10681541Srgrimes for (run = 0, i = bpref; i < cgp->cg_nclusterblks; i++) { 10691541Srgrimes if ((map & bit) == 0) { 10701541Srgrimes run = 0; 10711541Srgrimes } else { 10721541Srgrimes run++; 10731541Srgrimes if (run == len) 10741541Srgrimes break; 10751541Srgrimes } 10761541Srgrimes if ((i & (NBBY - 1)) != (NBBY - 1)) { 10771541Srgrimes bit <<= 1; 10781541Srgrimes } else { 10791541Srgrimes map = *mapp++; 10801541Srgrimes bit = 1; 10811541Srgrimes } 10821541Srgrimes } 10831541Srgrimes if (i == cgp->cg_nclusterblks) 10841541Srgrimes goto fail; 10851541Srgrimes /* 10861541Srgrimes * Allocate the cluster that we have found. 10871541Srgrimes */ 10881541Srgrimes bno = cg * fs->fs_fpg + blkstofrags(fs, i - run + 1); 10891541Srgrimes len = blkstofrags(fs, len); 10901541Srgrimes for (i = 0; i < len; i += fs->fs_frag) 10911541Srgrimes if (ffs_alloccgblk(fs, cgp, bno + i) != bno + i) 10921541Srgrimes panic("ffs_clusteralloc: lost block"); 10939980Sdg bdwrite(bp); 10941541Srgrimes return (bno); 10951541Srgrimes 10961541Srgrimesfail: 10971541Srgrimes brelse(bp); 10981541Srgrimes return (0); 10991541Srgrimes} 110012911Sphk#endif 11011541Srgrimes 11021541Srgrimes/* 11031541Srgrimes * Determine whether an inode can be allocated. 11041541Srgrimes * 11051541Srgrimes * Check to see if an inode is available, and if it is, 11061541Srgrimes * allocate it using the following policy: 11071541Srgrimes * 1) allocate the requested inode. 11081541Srgrimes * 2) allocate the next available inode after the requested 11091541Srgrimes * inode in the specified cylinder group. 11101541Srgrimes */ 11111541Srgrimesstatic ino_t 11121541Srgrimesffs_nodealloccg(ip, cg, ipref, mode) 11131541Srgrimes struct inode *ip; 11141541Srgrimes int cg; 11151541Srgrimes daddr_t ipref; 11161541Srgrimes int mode; 11171541Srgrimes{ 11181541Srgrimes register struct fs *fs; 11191541Srgrimes register struct cg *cgp; 11201541Srgrimes struct buf *bp; 11211541Srgrimes int error, start, len, loc, map, i; 11221541Srgrimes 11231541Srgrimes fs = ip->i_fs; 11241541Srgrimes if (fs->fs_cs(fs, cg).cs_nifree == 0) 112517108Sbde return (0); 11261541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 11271541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 11281541Srgrimes if (error) { 11291541Srgrimes brelse(bp); 113017108Sbde return (0); 11311541Srgrimes } 11321541Srgrimes cgp = (struct cg *)bp->b_data; 11331541Srgrimes if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 11341541Srgrimes brelse(bp); 113517108Sbde return (0); 11361541Srgrimes } 11371541Srgrimes cgp->cg_time = time.tv_sec; 11381541Srgrimes if (ipref) { 11391541Srgrimes ipref %= fs->fs_ipg; 11401541Srgrimes if (isclr(cg_inosused(cgp), ipref)) 11411541Srgrimes goto gotit; 11421541Srgrimes } 11431541Srgrimes start = cgp->cg_irotor / NBBY; 11441541Srgrimes len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 11451541Srgrimes loc = skpc(0xff, len, &cg_inosused(cgp)[start]); 11461541Srgrimes if (loc == 0) { 11471541Srgrimes len = start + 1; 11481541Srgrimes start = 0; 11491541Srgrimes loc = skpc(0xff, len, &cg_inosused(cgp)[0]); 11501541Srgrimes if (loc == 0) { 11516357Sphk printf("cg = %d, irotor = %ld, fs = %s\n", 11521541Srgrimes cg, cgp->cg_irotor, fs->fs_fsmnt); 11531541Srgrimes panic("ffs_nodealloccg: map corrupted"); 11541541Srgrimes /* NOTREACHED */ 11551541Srgrimes } 11561541Srgrimes } 11571541Srgrimes i = start + len - loc; 11581541Srgrimes map = cg_inosused(cgp)[i]; 11591541Srgrimes ipref = i * NBBY; 11601541Srgrimes for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 11611541Srgrimes if ((map & i) == 0) { 11621541Srgrimes cgp->cg_irotor = ipref; 11631541Srgrimes goto gotit; 11641541Srgrimes } 11651541Srgrimes } 11661541Srgrimes printf("fs = %s\n", fs->fs_fsmnt); 11671541Srgrimes panic("ffs_nodealloccg: block not in map"); 11681541Srgrimes /* NOTREACHED */ 11691541Srgrimesgotit: 11701541Srgrimes setbit(cg_inosused(cgp), ipref); 11711541Srgrimes cgp->cg_cs.cs_nifree--; 11721541Srgrimes fs->fs_cstotal.cs_nifree--; 11731541Srgrimes fs->fs_cs(fs, cg).cs_nifree--; 11741541Srgrimes fs->fs_fmod = 1; 11751541Srgrimes if ((mode & IFMT) == IFDIR) { 11761541Srgrimes cgp->cg_cs.cs_ndir++; 11771541Srgrimes fs->fs_cstotal.cs_ndir++; 11781541Srgrimes fs->fs_cs(fs, cg).cs_ndir++; 11791541Srgrimes } 11801541Srgrimes bdwrite(bp); 11811541Srgrimes return (cg * fs->fs_ipg + ipref); 11821541Srgrimes} 11831541Srgrimes 11841541Srgrimes/* 11851541Srgrimes * Free a block or fragment. 11861541Srgrimes * 11871541Srgrimes * The specified block or fragment is placed back in the 11888876Srgrimes * free map. If a fragment is deallocated, a possible 11891541Srgrimes * block reassembly is checked. 11901541Srgrimes */ 11911549Srgrimesvoid 11921541Srgrimesffs_blkfree(ip, bno, size) 11931541Srgrimes register struct inode *ip; 11941541Srgrimes daddr_t bno; 11951541Srgrimes long size; 11961541Srgrimes{ 11971541Srgrimes register struct fs *fs; 11981541Srgrimes register struct cg *cgp; 11991541Srgrimes struct buf *bp; 12001541Srgrimes daddr_t blkno; 12011541Srgrimes int i, error, cg, blk, frags, bbase; 12021541Srgrimes 12031541Srgrimes fs = ip->i_fs; 12041541Srgrimes if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 12053487Sphk printf("dev = 0x%lx, bsize = %ld, size = %ld, fs = %s\n", 12063487Sphk (u_long)ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 12071541Srgrimes panic("blkfree: bad size"); 12081541Srgrimes } 12091541Srgrimes cg = dtog(fs, bno); 12101541Srgrimes if ((u_int)bno >= fs->fs_size) { 12116357Sphk printf("bad block %ld, ino %ld\n", bno, ip->i_number); 12121541Srgrimes ffs_fserr(fs, ip->i_uid, "bad block"); 12131541Srgrimes return; 12141541Srgrimes } 12151541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 12161541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 12171541Srgrimes if (error) { 12181541Srgrimes brelse(bp); 12191541Srgrimes return; 12201541Srgrimes } 12211541Srgrimes cgp = (struct cg *)bp->b_data; 12221541Srgrimes if (!cg_chkmagic(cgp)) { 12231541Srgrimes brelse(bp); 12241541Srgrimes return; 12251541Srgrimes } 12261541Srgrimes cgp->cg_time = time.tv_sec; 12271541Srgrimes bno = dtogd(fs, bno); 12281541Srgrimes if (size == fs->fs_bsize) { 12291541Srgrimes blkno = fragstoblks(fs, bno); 12301541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 12316357Sphk printf("dev = 0x%lx, block = %ld, fs = %s\n", 12326357Sphk (u_long) ip->i_dev, bno, fs->fs_fsmnt); 12331541Srgrimes panic("blkfree: freeing free block"); 12341541Srgrimes } 12351541Srgrimes ffs_setblock(fs, cg_blksfree(cgp), blkno); 12361541Srgrimes ffs_clusteracct(fs, cgp, blkno, 1); 12371541Srgrimes cgp->cg_cs.cs_nbfree++; 12381541Srgrimes fs->fs_cstotal.cs_nbfree++; 12391541Srgrimes fs->fs_cs(fs, cg).cs_nbfree++; 12401541Srgrimes i = cbtocylno(fs, bno); 12411541Srgrimes cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; 12421541Srgrimes cg_blktot(cgp)[i]++; 12431541Srgrimes } else { 12441541Srgrimes bbase = bno - fragnum(fs, bno); 12451541Srgrimes /* 12461541Srgrimes * decrement the counts associated with the old frags 12471541Srgrimes */ 12481541Srgrimes blk = blkmap(fs, cg_blksfree(cgp), bbase); 12491541Srgrimes ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 12501541Srgrimes /* 12511541Srgrimes * deallocate the fragment 12521541Srgrimes */ 12531541Srgrimes frags = numfrags(fs, size); 12541541Srgrimes for (i = 0; i < frags; i++) { 12551541Srgrimes if (isset(cg_blksfree(cgp), bno + i)) { 12566357Sphk printf("dev = 0x%lx, block = %ld, fs = %s\n", 12576357Sphk (u_long) ip->i_dev, bno + i, fs->fs_fsmnt); 12581541Srgrimes panic("blkfree: freeing free frag"); 12591541Srgrimes } 12601541Srgrimes setbit(cg_blksfree(cgp), bno + i); 12611541Srgrimes } 12621541Srgrimes cgp->cg_cs.cs_nffree += i; 12631541Srgrimes fs->fs_cstotal.cs_nffree += i; 12641541Srgrimes fs->fs_cs(fs, cg).cs_nffree += i; 12651541Srgrimes /* 12661541Srgrimes * add back in counts associated with the new frags 12671541Srgrimes */ 12681541Srgrimes blk = blkmap(fs, cg_blksfree(cgp), bbase); 12691541Srgrimes ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 12701541Srgrimes /* 12711541Srgrimes * if a complete block has been reassembled, account for it 12721541Srgrimes */ 12731541Srgrimes blkno = fragstoblks(fs, bbase); 12741541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 12751541Srgrimes cgp->cg_cs.cs_nffree -= fs->fs_frag; 12761541Srgrimes fs->fs_cstotal.cs_nffree -= fs->fs_frag; 12771541Srgrimes fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 12781541Srgrimes ffs_clusteracct(fs, cgp, blkno, 1); 12791541Srgrimes cgp->cg_cs.cs_nbfree++; 12801541Srgrimes fs->fs_cstotal.cs_nbfree++; 12811541Srgrimes fs->fs_cs(fs, cg).cs_nbfree++; 12821541Srgrimes i = cbtocylno(fs, bbase); 12831541Srgrimes cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 12841541Srgrimes cg_blktot(cgp)[i]++; 12851541Srgrimes } 12861541Srgrimes } 12871541Srgrimes fs->fs_fmod = 1; 12881541Srgrimes bdwrite(bp); 12891541Srgrimes} 12901541Srgrimes 12911541Srgrimes/* 12921541Srgrimes * Free an inode. 12931541Srgrimes * 12941541Srgrimes * The specified inode is placed back in the free map. 12951541Srgrimes */ 12961541Srgrimesint 12971541Srgrimesffs_vfree(ap) 12981541Srgrimes struct vop_vfree_args /* { 12991541Srgrimes struct vnode *a_pvp; 13001541Srgrimes ino_t a_ino; 13011541Srgrimes int a_mode; 13021541Srgrimes } */ *ap; 13031541Srgrimes{ 13041541Srgrimes register struct fs *fs; 13051541Srgrimes register struct cg *cgp; 13061541Srgrimes register struct inode *pip; 13071541Srgrimes ino_t ino = ap->a_ino; 13081541Srgrimes struct buf *bp; 13091541Srgrimes int error, cg; 13101541Srgrimes 13111541Srgrimes pip = VTOI(ap->a_pvp); 13121541Srgrimes fs = pip->i_fs; 13131541Srgrimes if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 13147170Sdg panic("ifree: range: dev = 0x%x, ino = %d, fs = %s", 13151541Srgrimes pip->i_dev, ino, fs->fs_fsmnt); 13161541Srgrimes cg = ino_to_cg(fs, ino); 13171541Srgrimes error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 13181541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 13191541Srgrimes if (error) { 13201541Srgrimes brelse(bp); 13211541Srgrimes return (0); 13221541Srgrimes } 13231541Srgrimes cgp = (struct cg *)bp->b_data; 13241541Srgrimes if (!cg_chkmagic(cgp)) { 13251541Srgrimes brelse(bp); 13261541Srgrimes return (0); 13271541Srgrimes } 13281541Srgrimes cgp->cg_time = time.tv_sec; 13291541Srgrimes ino %= fs->fs_ipg; 13301541Srgrimes if (isclr(cg_inosused(cgp), ino)) { 13316357Sphk printf("dev = 0x%lx, ino = %ld, fs = %s\n", 13323487Sphk (u_long)pip->i_dev, ino, fs->fs_fsmnt); 13331541Srgrimes if (fs->fs_ronly == 0) 13341541Srgrimes panic("ifree: freeing free inode"); 13351541Srgrimes } 13361541Srgrimes clrbit(cg_inosused(cgp), ino); 13371541Srgrimes if (ino < cgp->cg_irotor) 13381541Srgrimes cgp->cg_irotor = ino; 13391541Srgrimes cgp->cg_cs.cs_nifree++; 13401541Srgrimes fs->fs_cstotal.cs_nifree++; 13411541Srgrimes fs->fs_cs(fs, cg).cs_nifree++; 13421541Srgrimes if ((ap->a_mode & IFMT) == IFDIR) { 13431541Srgrimes cgp->cg_cs.cs_ndir--; 13441541Srgrimes fs->fs_cstotal.cs_ndir--; 13451541Srgrimes fs->fs_cs(fs, cg).cs_ndir--; 13461541Srgrimes } 13471541Srgrimes fs->fs_fmod = 1; 13481541Srgrimes bdwrite(bp); 13491541Srgrimes return (0); 13501541Srgrimes} 13511541Srgrimes 13521541Srgrimes/* 13531541Srgrimes * Find a block of the specified size in the specified cylinder group. 13541541Srgrimes * 13551541Srgrimes * It is a panic if a request is made to find a block if none are 13561541Srgrimes * available. 13571541Srgrimes */ 13581541Srgrimesstatic daddr_t 13591541Srgrimesffs_mapsearch(fs, cgp, bpref, allocsiz) 13601541Srgrimes register struct fs *fs; 13611541Srgrimes register struct cg *cgp; 13621541Srgrimes daddr_t bpref; 13631541Srgrimes int allocsiz; 13641541Srgrimes{ 13651541Srgrimes daddr_t bno; 13661541Srgrimes int start, len, loc, i; 13671541Srgrimes int blk, field, subfield, pos; 13681541Srgrimes 13691541Srgrimes /* 13701541Srgrimes * find the fragment by searching through the free block 13711541Srgrimes * map for an appropriate bit pattern 13721541Srgrimes */ 13731541Srgrimes if (bpref) 13741541Srgrimes start = dtogd(fs, bpref) / NBBY; 13751541Srgrimes else 13761541Srgrimes start = cgp->cg_frotor / NBBY; 13771541Srgrimes len = howmany(fs->fs_fpg, NBBY) - start; 13781541Srgrimes loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[start], 13791541Srgrimes (u_char *)fragtbl[fs->fs_frag], 13801541Srgrimes (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 13811541Srgrimes if (loc == 0) { 13821541Srgrimes len = start + 1; 13831541Srgrimes start = 0; 13841541Srgrimes loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[0], 13851541Srgrimes (u_char *)fragtbl[fs->fs_frag], 13861541Srgrimes (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 13871541Srgrimes if (loc == 0) { 13881541Srgrimes printf("start = %d, len = %d, fs = %s\n", 13891541Srgrimes start, len, fs->fs_fsmnt); 13901541Srgrimes panic("ffs_alloccg: map corrupted"); 13911541Srgrimes /* NOTREACHED */ 13921541Srgrimes } 13931541Srgrimes } 13941541Srgrimes bno = (start + len - loc) * NBBY; 13951541Srgrimes cgp->cg_frotor = bno; 13961541Srgrimes /* 13971541Srgrimes * found the byte in the map 13981541Srgrimes * sift through the bits to find the selected frag 13991541Srgrimes */ 14001541Srgrimes for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 14011541Srgrimes blk = blkmap(fs, cg_blksfree(cgp), bno); 14021541Srgrimes blk <<= 1; 14031541Srgrimes field = around[allocsiz]; 14041541Srgrimes subfield = inside[allocsiz]; 14051541Srgrimes for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 14061541Srgrimes if ((blk & field) == subfield) 14071541Srgrimes return (bno + pos); 14081541Srgrimes field <<= 1; 14091541Srgrimes subfield <<= 1; 14101541Srgrimes } 14111541Srgrimes } 14123487Sphk printf("bno = %lu, fs = %s\n", (u_long)bno, fs->fs_fsmnt); 14131541Srgrimes panic("ffs_alloccg: block not in map"); 14141541Srgrimes return (-1); 14151541Srgrimes} 14161541Srgrimes 14171541Srgrimes/* 14181541Srgrimes * Update the cluster map because of an allocation or free. 14191541Srgrimes * 14201541Srgrimes * Cnt == 1 means free; cnt == -1 means allocating. 14211541Srgrimes */ 142212911Sphkstatic void 14231541Srgrimesffs_clusteracct(fs, cgp, blkno, cnt) 14241541Srgrimes struct fs *fs; 14251541Srgrimes struct cg *cgp; 14261541Srgrimes daddr_t blkno; 14271541Srgrimes int cnt; 14281541Srgrimes{ 14291541Srgrimes long *sump; 14301541Srgrimes u_char *freemapp, *mapp; 14311541Srgrimes int i, start, end, forw, back, map, bit; 14321541Srgrimes 14331541Srgrimes if (fs->fs_contigsumsize <= 0) 14341541Srgrimes return; 14351541Srgrimes freemapp = cg_clustersfree(cgp); 14361541Srgrimes sump = cg_clustersum(cgp); 14371541Srgrimes /* 14381541Srgrimes * Allocate or clear the actual block. 14391541Srgrimes */ 14401541Srgrimes if (cnt > 0) 14411541Srgrimes setbit(freemapp, blkno); 14421541Srgrimes else 14431541Srgrimes clrbit(freemapp, blkno); 14441541Srgrimes /* 14451541Srgrimes * Find the size of the cluster going forward. 14461541Srgrimes */ 14471541Srgrimes start = blkno + 1; 14481541Srgrimes end = start + fs->fs_contigsumsize; 14491541Srgrimes if (end >= cgp->cg_nclusterblks) 14501541Srgrimes end = cgp->cg_nclusterblks; 14511541Srgrimes mapp = &freemapp[start / NBBY]; 14521541Srgrimes map = *mapp++; 14531541Srgrimes bit = 1 << (start % NBBY); 14541541Srgrimes for (i = start; i < end; i++) { 14551541Srgrimes if ((map & bit) == 0) 14561541Srgrimes break; 14571541Srgrimes if ((i & (NBBY - 1)) != (NBBY - 1)) { 14581541Srgrimes bit <<= 1; 14591541Srgrimes } else { 14601541Srgrimes map = *mapp++; 14611541Srgrimes bit = 1; 14621541Srgrimes } 14631541Srgrimes } 14641541Srgrimes forw = i - start; 14651541Srgrimes /* 14661541Srgrimes * Find the size of the cluster going backward. 14671541Srgrimes */ 14681541Srgrimes start = blkno - 1; 14691541Srgrimes end = start - fs->fs_contigsumsize; 14701541Srgrimes if (end < 0) 14711541Srgrimes end = -1; 14721541Srgrimes mapp = &freemapp[start / NBBY]; 14731541Srgrimes map = *mapp--; 14741541Srgrimes bit = 1 << (start % NBBY); 14751541Srgrimes for (i = start; i > end; i--) { 14761541Srgrimes if ((map & bit) == 0) 14771541Srgrimes break; 14781541Srgrimes if ((i & (NBBY - 1)) != 0) { 14791541Srgrimes bit >>= 1; 14801541Srgrimes } else { 14811541Srgrimes map = *mapp--; 14821541Srgrimes bit = 1 << (NBBY - 1); 14831541Srgrimes } 14841541Srgrimes } 14851541Srgrimes back = start - i; 14861541Srgrimes /* 14871541Srgrimes * Account for old cluster and the possibly new forward and 14881541Srgrimes * back clusters. 14891541Srgrimes */ 14901541Srgrimes i = back + forw + 1; 14911541Srgrimes if (i > fs->fs_contigsumsize) 14921541Srgrimes i = fs->fs_contigsumsize; 14931541Srgrimes sump[i] += cnt; 14941541Srgrimes if (back > 0) 14951541Srgrimes sump[back] -= cnt; 14961541Srgrimes if (forw > 0) 14971541Srgrimes sump[forw] -= cnt; 14981541Srgrimes} 14991541Srgrimes 15001541Srgrimes/* 15011541Srgrimes * Fserr prints the name of a file system with an error diagnostic. 15028876Srgrimes * 15031541Srgrimes * The form of the error message is: 15041541Srgrimes * fs: error message 15051541Srgrimes */ 15061541Srgrimesstatic void 15071541Srgrimesffs_fserr(fs, uid, cp) 15081541Srgrimes struct fs *fs; 15091541Srgrimes u_int uid; 15101541Srgrimes char *cp; 15111541Srgrimes{ 151218330Speter struct proc *p = curproc; /* XXX */ 15131541Srgrimes 151418330Speter log(LOG_ERR, "pid %d (%s), uid %d on %s: %s\n", p ? p->p_pid : -1, 151518330Speter p ? p->p_comm : "-", uid, fs->fs_fsmnt, cp); 15161541Srgrimes} 1517