ffs_alloc.c revision 62976
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 * 3322521Sdyson * @(#)ffs_alloc.c 8.18 (Berkeley) 5/26/95 3450477Speter * $FreeBSD: head/sys/ufs/ffs/ffs_alloc.c 62976 2000-07-11 22:07:57Z mckusick $ 351541Srgrimes */ 361541Srgrimes 3713260Swollman#include "opt_quota.h" 3813260Swollman 391541Srgrimes#include <sys/param.h> 401541Srgrimes#include <sys/systm.h> 4160041Sphk#include <sys/bio.h> 421541Srgrimes#include <sys/buf.h> 4350253Sbde#include <sys/conf.h> 441541Srgrimes#include <sys/proc.h> 451541Srgrimes#include <sys/vnode.h> 461541Srgrimes#include <sys/mount.h> 4741124Sdg#include <sys/kernel.h> 4812911Sphk#include <sys/sysctl.h> 491541Srgrimes#include <sys/syslog.h> 501541Srgrimes 5159241Srwatson#include <ufs/ufs/extattr.h> 521541Srgrimes#include <ufs/ufs/quota.h> 531541Srgrimes#include <ufs/ufs/inode.h> 5441124Sdg#include <ufs/ufs/ufs_extern.h> 5530474Sphk#include <ufs/ufs/ufsmount.h> 561541Srgrimes 571541Srgrimes#include <ufs/ffs/fs.h> 581541Srgrimes#include <ufs/ffs/ffs_extern.h> 591541Srgrimes 6022521Sdysontypedef ufs_daddr_t allocfcn_t __P((struct inode *ip, int cg, ufs_daddr_t bpref, 6122521Sdyson int size)); 6212590Sbde 6322521Sdysonstatic ufs_daddr_t ffs_alloccg __P((struct inode *, int, ufs_daddr_t, int)); 6434266Sjulianstatic ufs_daddr_t 6534266Sjulian ffs_alloccgblk __P((struct inode *, struct buf *, ufs_daddr_t)); 6631352Sbde#ifdef DIAGNOSTIC 6731352Sbdestatic int ffs_checkblk __P((struct inode *, ufs_daddr_t, long)); 6831352Sbde#endif 6922521Sdysonstatic void ffs_clusteracct __P((struct fs *, struct cg *, ufs_daddr_t, 7022521Sdyson int)); 7131351Sbdestatic ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t, 7231351Sbde int)); 731541Srgrimesstatic ino_t ffs_dirpref __P((struct fs *)); 7422521Sdysonstatic ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 751541Srgrimesstatic void ffs_fserr __P((struct fs *, u_int, char *)); 761541Srgrimesstatic u_long ffs_hashalloc 7712590Sbde __P((struct inode *, int, long, int, allocfcn_t *)); 7822521Sdysonstatic ino_t ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int)); 7922521Sdysonstatic ufs_daddr_t ffs_mapsearch __P((struct fs *, struct cg *, ufs_daddr_t, 8022521Sdyson int)); 811541Srgrimes 821541Srgrimes/* 831541Srgrimes * Allocate a block in the file system. 848876Srgrimes * 851541Srgrimes * The size of the requested block is given, which must be some 861541Srgrimes * multiple of fs_fsize and <= fs_bsize. 871541Srgrimes * A preference may be optionally specified. If a preference is given 881541Srgrimes * the following hierarchy is used to allocate a block: 891541Srgrimes * 1) allocate the requested block. 901541Srgrimes * 2) allocate a rotationally optimal block in the same cylinder. 911541Srgrimes * 3) allocate a block in the same cylinder group. 921541Srgrimes * 4) quadradically rehash into other cylinder groups, until an 931541Srgrimes * available block is located. 941541Srgrimes * If no block preference is given the following heirarchy is used 951541Srgrimes * to allocate a block: 961541Srgrimes * 1) allocate a block in the cylinder group that contains the 971541Srgrimes * inode for the file. 981541Srgrimes * 2) quadradically rehash into other cylinder groups, until an 991541Srgrimes * available block is located. 1001541Srgrimes */ 1011549Srgrimesint 1021541Srgrimesffs_alloc(ip, lbn, bpref, size, cred, bnp) 1031541Srgrimes register struct inode *ip; 10422521Sdyson ufs_daddr_t lbn, bpref; 1051541Srgrimes int size; 1061541Srgrimes struct ucred *cred; 10722521Sdyson ufs_daddr_t *bnp; 1081541Srgrimes{ 1091541Srgrimes register struct fs *fs; 11022521Sdyson ufs_daddr_t bno; 1116357Sphk int cg; 1126357Sphk#ifdef QUOTA 1136357Sphk int error; 1146357Sphk#endif 1158876Srgrimes 1161541Srgrimes *bnp = 0; 1171541Srgrimes fs = ip->i_fs; 1181541Srgrimes#ifdef DIAGNOSTIC 1191541Srgrimes if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 12050253Sbde printf("dev = %s, bsize = %ld, size = %d, fs = %s\n", 12150253Sbde devtoname(ip->i_dev), (long)fs->fs_bsize, size, 12250253Sbde fs->fs_fsmnt); 1231541Srgrimes panic("ffs_alloc: bad size"); 1241541Srgrimes } 1251541Srgrimes if (cred == NOCRED) 1267170Sdg panic("ffs_alloc: missing credential"); 1271541Srgrimes#endif /* DIAGNOSTIC */ 1281541Srgrimes if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 1291541Srgrimes goto nospace; 13029609Sphk if (cred->cr_uid != 0 && 13129609Sphk freespace(fs, fs->fs_minfree) - numfrags(fs, size) < 0) 1321541Srgrimes goto nospace; 1331541Srgrimes#ifdef QUOTA 1343487Sphk error = chkdq(ip, (long)btodb(size), cred, 0); 1353487Sphk if (error) 1361541Srgrimes return (error); 1371541Srgrimes#endif 1381541Srgrimes if (bpref >= fs->fs_size) 1391541Srgrimes bpref = 0; 1401541Srgrimes if (bpref == 0) 1411541Srgrimes cg = ino_to_cg(fs, ip->i_number); 1421541Srgrimes else 1431541Srgrimes cg = dtog(fs, bpref); 14422521Sdyson bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 14522521Sdyson ffs_alloccg); 1461541Srgrimes if (bno > 0) { 1471541Srgrimes ip->i_blocks += btodb(size); 1481541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 1491541Srgrimes *bnp = bno; 1501541Srgrimes return (0); 1511541Srgrimes } 1521541Srgrimes#ifdef QUOTA 1531541Srgrimes /* 1541541Srgrimes * Restore user's disk quota because allocation failed. 1551541Srgrimes */ 1561541Srgrimes (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 1571541Srgrimes#endif 1581541Srgrimesnospace: 1591541Srgrimes ffs_fserr(fs, cred->cr_uid, "file system full"); 1601541Srgrimes uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 1611541Srgrimes return (ENOSPC); 1621541Srgrimes} 1631541Srgrimes 1641541Srgrimes/* 1651541Srgrimes * Reallocate a fragment to a bigger size 1661541Srgrimes * 1671541Srgrimes * The number and size of the old block is given, and a preference 1681541Srgrimes * and new size is also specified. The allocator attempts to extend 1691541Srgrimes * the original block. Failing that, the regular block allocator is 1701541Srgrimes * invoked to get an appropriate block. 1711541Srgrimes */ 1721549Srgrimesint 1731541Srgrimesffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp) 1741541Srgrimes register struct inode *ip; 17522521Sdyson ufs_daddr_t lbprev; 17622521Sdyson ufs_daddr_t bpref; 1771541Srgrimes int osize, nsize; 1781541Srgrimes struct ucred *cred; 1791541Srgrimes struct buf **bpp; 1801541Srgrimes{ 1811541Srgrimes register struct fs *fs; 1821541Srgrimes struct buf *bp; 1831541Srgrimes int cg, request, error; 18422521Sdyson ufs_daddr_t bprev, bno; 1858876Srgrimes 1861541Srgrimes *bpp = 0; 1871541Srgrimes fs = ip->i_fs; 1881541Srgrimes#ifdef DIAGNOSTIC 18962976Smckusick if (ITOV(ip)->v_mount->mnt_kern_flag & MNTK_SUSPENDED) 19062976Smckusick panic("ffs_realloccg: allocation on suspended filesystem"); 1911541Srgrimes if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 1921541Srgrimes (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 1931541Srgrimes printf( 19450253Sbde "dev = %s, bsize = %ld, osize = %d, nsize = %d, fs = %s\n", 19550253Sbde devtoname(ip->i_dev), (long)fs->fs_bsize, osize, 1968456Srgrimes nsize, fs->fs_fsmnt); 1971541Srgrimes panic("ffs_realloccg: bad size"); 1981541Srgrimes } 1991541Srgrimes if (cred == NOCRED) 2007170Sdg panic("ffs_realloccg: missing credential"); 2011541Srgrimes#endif /* DIAGNOSTIC */ 20229609Sphk if (cred->cr_uid != 0 && 20329609Sphk freespace(fs, fs->fs_minfree) - numfrags(fs, nsize - osize) < 0) 2041541Srgrimes goto nospace; 2051541Srgrimes if ((bprev = ip->i_db[lbprev]) == 0) { 20650253Sbde printf("dev = %s, bsize = %ld, bprev = %ld, fs = %s\n", 20750253Sbde devtoname(ip->i_dev), (long)fs->fs_bsize, (long)bprev, 20837555Sbde fs->fs_fsmnt); 2091541Srgrimes panic("ffs_realloccg: bad bprev"); 2101541Srgrimes } 2111541Srgrimes /* 2121541Srgrimes * Allocate the extra space in the buffer. 2131541Srgrimes */ 2143487Sphk error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp); 2153487Sphk if (error) { 2161541Srgrimes brelse(bp); 2171541Srgrimes return (error); 2181541Srgrimes } 2196864Sdg 2206864Sdg if( bp->b_blkno == bp->b_lblkno) { 2216864Sdg if( lbprev >= NDADDR) 2226864Sdg panic("ffs_realloccg: lbprev out of range"); 2236864Sdg bp->b_blkno = fsbtodb(fs, bprev); 2246864Sdg } 2258876Srgrimes 2261541Srgrimes#ifdef QUOTA 2273487Sphk error = chkdq(ip, (long)btodb(nsize - osize), cred, 0); 2283487Sphk if (error) { 2291541Srgrimes brelse(bp); 2301541Srgrimes return (error); 2311541Srgrimes } 2321541Srgrimes#endif 2331541Srgrimes /* 2341541Srgrimes * Check for extension in the existing location. 2351541Srgrimes */ 2361541Srgrimes cg = dtog(fs, bprev); 2373487Sphk bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize); 2383487Sphk if (bno) { 2391541Srgrimes if (bp->b_blkno != fsbtodb(fs, bno)) 24023560Smpp panic("ffs_realloccg: bad blockno"); 2411541Srgrimes ip->i_blocks += btodb(nsize - osize); 2421541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 2437399Sdg allocbuf(bp, nsize); 2441541Srgrimes bp->b_flags |= B_DONE; 2451541Srgrimes bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 2461541Srgrimes *bpp = bp; 2471541Srgrimes return (0); 2481541Srgrimes } 2491541Srgrimes /* 2501541Srgrimes * Allocate a new disk location. 2511541Srgrimes */ 2521541Srgrimes if (bpref >= fs->fs_size) 2531541Srgrimes bpref = 0; 2541541Srgrimes switch ((int)fs->fs_optim) { 2551541Srgrimes case FS_OPTSPACE: 2561541Srgrimes /* 2578876Srgrimes * Allocate an exact sized fragment. Although this makes 2588876Srgrimes * best use of space, we will waste time relocating it if 2591541Srgrimes * the file continues to grow. If the fragmentation is 2601541Srgrimes * less than half of the minimum free reserve, we choose 2611541Srgrimes * to begin optimizing for time. 2621541Srgrimes */ 2631541Srgrimes request = nsize; 2646993Sdg if (fs->fs_minfree <= 5 || 2651541Srgrimes fs->fs_cstotal.cs_nffree > 26658087Smckusick (off_t)fs->fs_dsize * fs->fs_minfree / (2 * 100)) 2671541Srgrimes break; 2681541Srgrimes log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 2691541Srgrimes fs->fs_fsmnt); 2701541Srgrimes fs->fs_optim = FS_OPTTIME; 2711541Srgrimes break; 2721541Srgrimes case FS_OPTTIME: 2731541Srgrimes /* 2741541Srgrimes * At this point we have discovered a file that is trying to 2751541Srgrimes * grow a small fragment to a larger fragment. To save time, 2761541Srgrimes * we allocate a full sized block, then free the unused portion. 2771541Srgrimes * If the file continues to grow, the `ffs_fragextend' call 2781541Srgrimes * above will be able to grow it in place without further 2791541Srgrimes * copying. If aberrant programs cause disk fragmentation to 2801541Srgrimes * grow within 2% of the free reserve, we choose to begin 2811541Srgrimes * optimizing for space. 2821541Srgrimes */ 2831541Srgrimes request = fs->fs_bsize; 2841541Srgrimes if (fs->fs_cstotal.cs_nffree < 28558087Smckusick (off_t)fs->fs_dsize * (fs->fs_minfree - 2) / 100) 2861541Srgrimes break; 2871541Srgrimes log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 2881541Srgrimes fs->fs_fsmnt); 2891541Srgrimes fs->fs_optim = FS_OPTSPACE; 2901541Srgrimes break; 2911541Srgrimes default: 29250253Sbde printf("dev = %s, optim = %ld, fs = %s\n", 29350253Sbde devtoname(ip->i_dev), (long)fs->fs_optim, fs->fs_fsmnt); 2941541Srgrimes panic("ffs_realloccg: bad optim"); 2951541Srgrimes /* NOTREACHED */ 2961541Srgrimes } 29722521Sdyson bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 29822521Sdyson ffs_alloccg); 2991541Srgrimes if (bno > 0) { 3001541Srgrimes bp->b_blkno = fsbtodb(fs, bno); 30134266Sjulian if (!DOINGSOFTDEP(ITOV(ip))) 30234266Sjulian ffs_blkfree(ip, bprev, (long)osize); 3031541Srgrimes if (nsize < request) 3041541Srgrimes ffs_blkfree(ip, bno + numfrags(fs, nsize), 3051541Srgrimes (long)(request - nsize)); 3061541Srgrimes ip->i_blocks += btodb(nsize - osize); 3071541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 3087399Sdg allocbuf(bp, nsize); 3091541Srgrimes bp->b_flags |= B_DONE; 3101541Srgrimes bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 3111541Srgrimes *bpp = bp; 3121541Srgrimes return (0); 3131541Srgrimes } 3141541Srgrimes#ifdef QUOTA 3151541Srgrimes /* 3161541Srgrimes * Restore user's disk quota because allocation failed. 3171541Srgrimes */ 3181541Srgrimes (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 3191541Srgrimes#endif 3201541Srgrimes brelse(bp); 3211541Srgrimesnospace: 3221541Srgrimes /* 3231541Srgrimes * no space available 3241541Srgrimes */ 3251541Srgrimes ffs_fserr(fs, cred->cr_uid, "file system full"); 3261541Srgrimes uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 3271541Srgrimes return (ENOSPC); 3281541Srgrimes} 3291541Srgrimes 33038907SbdeSYSCTL_NODE(_vfs, OID_AUTO, ffs, CTLFLAG_RW, 0, "FFS filesystem"); 33138907Sbde 3321541Srgrimes/* 3331541Srgrimes * Reallocate a sequence of blocks into a contiguous sequence of blocks. 3341541Srgrimes * 3351541Srgrimes * The vnode and an array of buffer pointers for a range of sequential 3361541Srgrimes * logical blocks to be made contiguous is given. The allocator attempts 3371541Srgrimes * to find a range of sequential blocks starting as close as possible to 3381541Srgrimes * an fs_rotdelay offset from the end of the allocation for the logical 3391541Srgrimes * block immediately preceeding the current range. If successful, the 3401541Srgrimes * physical block numbers in the buffer pointers and in the inode are 3411541Srgrimes * changed to reflect the new allocation. If unsuccessful, the allocation 3421541Srgrimes * is left unchanged. The success in doing the reallocation is returned. 3431541Srgrimes * Note that the error return is not reflected back to the user. Rather 3441541Srgrimes * the previous block allocation will be used. 3451541Srgrimes */ 34612911Sphkstatic int doasyncfree = 1; 34722521SdysonSYSCTL_INT(_vfs_ffs, FFS_ASYNCFREE, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, ""); 34822521Sdyson 34931352Sbdestatic int doreallocblks = 1; 35022521SdysonSYSCTL_INT(_vfs_ffs, FFS_REALLOCBLKS, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, ""); 35122521Sdyson 35242351Sbde#ifdef DEBUG 35342351Sbdestatic volatile int prtrealloc = 0; 35442351Sbde#endif 35531351Sbde 3561541Srgrimesint 3571541Srgrimesffs_reallocblks(ap) 3581541Srgrimes struct vop_reallocblks_args /* { 3591541Srgrimes struct vnode *a_vp; 3601541Srgrimes struct cluster_save *a_buflist; 3611541Srgrimes } */ *ap; 3621541Srgrimes{ 3631541Srgrimes struct fs *fs; 3641541Srgrimes struct inode *ip; 3651541Srgrimes struct vnode *vp; 3661541Srgrimes struct buf *sbp, *ebp; 36722521Sdyson ufs_daddr_t *bap, *sbap, *ebap = 0; 3681541Srgrimes struct cluster_save *buflist; 36922521Sdyson ufs_daddr_t start_lbn, end_lbn, soff, newblk, blkno; 3701541Srgrimes struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 3711541Srgrimes int i, len, start_lvl, end_lvl, pref, ssize; 3721541Srgrimes 37322521Sdyson if (doreallocblks == 0) 37422521Sdyson return (ENOSPC); 3751541Srgrimes vp = ap->a_vp; 3761541Srgrimes ip = VTOI(vp); 3771541Srgrimes fs = ip->i_fs; 3781541Srgrimes if (fs->fs_contigsumsize <= 0) 3791541Srgrimes return (ENOSPC); 3801541Srgrimes buflist = ap->a_buflist; 3811541Srgrimes len = buflist->bs_nchildren; 3821541Srgrimes start_lbn = buflist->bs_children[0]->b_lblkno; 3831541Srgrimes end_lbn = start_lbn + len - 1; 3841541Srgrimes#ifdef DIAGNOSTIC 38522521Sdyson for (i = 0; i < len; i++) 38622521Sdyson if (!ffs_checkblk(ip, 38722521Sdyson dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 38822521Sdyson panic("ffs_reallocblks: unallocated block 1"); 3891541Srgrimes for (i = 1; i < len; i++) 3901541Srgrimes if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 39122521Sdyson panic("ffs_reallocblks: non-logical cluster"); 39222521Sdyson blkno = buflist->bs_children[0]->b_blkno; 39322521Sdyson ssize = fsbtodb(fs, fs->fs_frag); 39422521Sdyson for (i = 1; i < len - 1; i++) 39522521Sdyson if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize)) 39622521Sdyson panic("ffs_reallocblks: non-physical cluster %d", i); 3971541Srgrimes#endif 3981541Srgrimes /* 3991541Srgrimes * If the latest allocation is in a new cylinder group, assume that 4001541Srgrimes * the filesystem has decided to move and do not force it back to 4011541Srgrimes * the previous cylinder group. 4021541Srgrimes */ 4031541Srgrimes if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 4041541Srgrimes dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 4051541Srgrimes return (ENOSPC); 4061541Srgrimes if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 4071541Srgrimes ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 4081541Srgrimes return (ENOSPC); 4091541Srgrimes /* 4101541Srgrimes * Get the starting offset and block map for the first block. 4111541Srgrimes */ 4121541Srgrimes if (start_lvl == 0) { 4131541Srgrimes sbap = &ip->i_db[0]; 4141541Srgrimes soff = start_lbn; 4151541Srgrimes } else { 4161541Srgrimes idp = &start_ap[start_lvl - 1]; 4171541Srgrimes if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 4181541Srgrimes brelse(sbp); 4191541Srgrimes return (ENOSPC); 4201541Srgrimes } 42122521Sdyson sbap = (ufs_daddr_t *)sbp->b_data; 4221541Srgrimes soff = idp->in_off; 4231541Srgrimes } 4241541Srgrimes /* 4251541Srgrimes * Find the preferred location for the cluster. 4261541Srgrimes */ 4271541Srgrimes pref = ffs_blkpref(ip, start_lbn, soff, sbap); 4281541Srgrimes /* 4291541Srgrimes * If the block range spans two block maps, get the second map. 4301541Srgrimes */ 4311541Srgrimes if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 4321541Srgrimes ssize = len; 4331541Srgrimes } else { 4341541Srgrimes#ifdef DIAGNOSTIC 4351541Srgrimes if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 4361541Srgrimes panic("ffs_reallocblk: start == end"); 4371541Srgrimes#endif 4381541Srgrimes ssize = len - (idp->in_off + 1); 4391541Srgrimes if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 4401541Srgrimes goto fail; 44122521Sdyson ebap = (ufs_daddr_t *)ebp->b_data; 4421541Srgrimes } 4431541Srgrimes /* 4441541Srgrimes * Search the block map looking for an allocation of the desired size. 4451541Srgrimes */ 44622521Sdyson if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref, 44712590Sbde len, ffs_clusteralloc)) == 0) 4481541Srgrimes goto fail; 4491541Srgrimes /* 4501541Srgrimes * We have found a new contiguous block. 4511541Srgrimes * 4521541Srgrimes * First we have to replace the old block pointers with the new 4531541Srgrimes * block pointers in the inode and indirect blocks associated 4541541Srgrimes * with the file. 4551541Srgrimes */ 45622521Sdyson#ifdef DEBUG 45722521Sdyson if (prtrealloc) 45822521Sdyson printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number, 45922521Sdyson start_lbn, end_lbn); 46022521Sdyson#endif 4611541Srgrimes blkno = newblk; 4621541Srgrimes for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 46334266Sjulian if (i == ssize) { 4641541Srgrimes bap = ebap; 46534266Sjulian soff = -i; 46634266Sjulian } 4671541Srgrimes#ifdef DIAGNOSTIC 46822521Sdyson if (!ffs_checkblk(ip, 46922521Sdyson dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 47022521Sdyson panic("ffs_reallocblks: unallocated block 2"); 47122521Sdyson if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap) 4721541Srgrimes panic("ffs_reallocblks: alloc mismatch"); 4731541Srgrimes#endif 47422521Sdyson#ifdef DEBUG 47522521Sdyson if (prtrealloc) 47622521Sdyson printf(" %d,", *bap); 47722521Sdyson#endif 47834266Sjulian if (DOINGSOFTDEP(vp)) { 47934266Sjulian if (sbap == &ip->i_db[0] && i < ssize) 48034266Sjulian softdep_setup_allocdirect(ip, start_lbn + i, 48134266Sjulian blkno, *bap, fs->fs_bsize, fs->fs_bsize, 48234266Sjulian buflist->bs_children[i]); 48334266Sjulian else 48434266Sjulian softdep_setup_allocindir_page(ip, start_lbn + i, 48534266Sjulian i < ssize ? sbp : ebp, soff + i, blkno, 48634266Sjulian *bap, buflist->bs_children[i]); 48734266Sjulian } 4881541Srgrimes *bap++ = blkno; 4891541Srgrimes } 4901541Srgrimes /* 4911541Srgrimes * Next we must write out the modified inode and indirect blocks. 4921541Srgrimes * For strict correctness, the writes should be synchronous since 4931541Srgrimes * the old block values may have been written to disk. In practise 4948876Srgrimes * they are almost never written, but if we are concerned about 4951541Srgrimes * strict correctness, the `doasyncfree' flag should be set to zero. 4961541Srgrimes * 4971541Srgrimes * The test on `doasyncfree' should be changed to test a flag 4981541Srgrimes * that shows whether the associated buffers and inodes have 4991541Srgrimes * been written. The flag should be set when the cluster is 5001541Srgrimes * started and cleared whenever the buffer or inode is flushed. 5011541Srgrimes * We can then check below to see if it is set, and do the 5021541Srgrimes * synchronous write only when it has been cleared. 5031541Srgrimes */ 5041541Srgrimes if (sbap != &ip->i_db[0]) { 5051541Srgrimes if (doasyncfree) 5061541Srgrimes bdwrite(sbp); 5071541Srgrimes else 5081541Srgrimes bwrite(sbp); 5091541Srgrimes } else { 5101541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 51142374Sbde if (!doasyncfree) 51242374Sbde UFS_UPDATE(vp, 1); 5131541Srgrimes } 51446568Speter if (ssize < len) { 5151541Srgrimes if (doasyncfree) 5161541Srgrimes bdwrite(ebp); 5171541Srgrimes else 5181541Srgrimes bwrite(ebp); 51946568Speter } 5201541Srgrimes /* 5211541Srgrimes * Last, free the old blocks and assign the new blocks to the buffers. 5221541Srgrimes */ 52322521Sdyson#ifdef DEBUG 52422521Sdyson if (prtrealloc) 52522521Sdyson printf("\n\tnew:"); 52622521Sdyson#endif 5271541Srgrimes for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 52834266Sjulian if (!DOINGSOFTDEP(vp)) 52934266Sjulian ffs_blkfree(ip, 53034266Sjulian dbtofsb(fs, buflist->bs_children[i]->b_blkno), 53134266Sjulian fs->fs_bsize); 5321541Srgrimes buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 53350305Ssheldonh#ifdef DIAGNOSTIC 53422521Sdyson if (!ffs_checkblk(ip, 53522521Sdyson dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 53622521Sdyson panic("ffs_reallocblks: unallocated block 3"); 53750305Ssheldonh#endif 53850305Ssheldonh#ifdef DEBUG 53922521Sdyson if (prtrealloc) 54022521Sdyson printf(" %d,", blkno); 54122521Sdyson#endif 5421541Srgrimes } 54322521Sdyson#ifdef DEBUG 54422521Sdyson if (prtrealloc) { 54522521Sdyson prtrealloc--; 54622521Sdyson printf("\n"); 54722521Sdyson } 54822521Sdyson#endif 5491541Srgrimes return (0); 5501541Srgrimes 5511541Srgrimesfail: 5521541Srgrimes if (ssize < len) 5531541Srgrimes brelse(ebp); 5541541Srgrimes if (sbap != &ip->i_db[0]) 5551541Srgrimes brelse(sbp); 5561541Srgrimes return (ENOSPC); 5571541Srgrimes} 5581541Srgrimes 5591541Srgrimes/* 5601541Srgrimes * Allocate an inode in the file system. 5618876Srgrimes * 5621541Srgrimes * If allocating a directory, use ffs_dirpref to select the inode. 5631541Srgrimes * If allocating in a directory, the following hierarchy is followed: 5641541Srgrimes * 1) allocate the preferred inode. 5651541Srgrimes * 2) allocate an inode in the same cylinder group. 5661541Srgrimes * 3) quadradically rehash into other cylinder groups, until an 5671541Srgrimes * available inode is located. 5681541Srgrimes * If no inode preference is given the following heirarchy is used 5691541Srgrimes * to allocate an inode: 5701541Srgrimes * 1) allocate an inode in cylinder group 0. 5711541Srgrimes * 2) quadradically rehash into other cylinder groups, until an 5721541Srgrimes * available inode is located. 5731541Srgrimes */ 5741549Srgrimesint 57530474Sphkffs_valloc(pvp, mode, cred, vpp) 57630474Sphk struct vnode *pvp; 57730474Sphk int mode; 57830474Sphk struct ucred *cred; 57930474Sphk struct vnode **vpp; 5801541Srgrimes{ 5811541Srgrimes register struct inode *pip; 5821541Srgrimes register struct fs *fs; 5831541Srgrimes register struct inode *ip; 5841541Srgrimes ino_t ino, ipref; 5851541Srgrimes int cg, error; 5868876Srgrimes 58730474Sphk *vpp = NULL; 5881541Srgrimes pip = VTOI(pvp); 5891541Srgrimes fs = pip->i_fs; 5901541Srgrimes if (fs->fs_cstotal.cs_nifree == 0) 5911541Srgrimes goto noinodes; 5921541Srgrimes 5931541Srgrimes if ((mode & IFMT) == IFDIR) 5941541Srgrimes ipref = ffs_dirpref(fs); 5951541Srgrimes else 5961541Srgrimes ipref = pip->i_number; 5971541Srgrimes if (ipref >= fs->fs_ncg * fs->fs_ipg) 5981541Srgrimes ipref = 0; 5991541Srgrimes cg = ino_to_cg(fs, ipref); 60012861Speter ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, 60112861Speter (allocfcn_t *)ffs_nodealloccg); 6021541Srgrimes if (ino == 0) 6031541Srgrimes goto noinodes; 60430474Sphk error = VFS_VGET(pvp->v_mount, ino, vpp); 6051541Srgrimes if (error) { 60630474Sphk UFS_VFREE(pvp, ino, mode); 6071541Srgrimes return (error); 6081541Srgrimes } 60930474Sphk ip = VTOI(*vpp); 6101541Srgrimes if (ip->i_mode) { 61137555Sbde printf("mode = 0%o, inum = %lu, fs = %s\n", 61237555Sbde ip->i_mode, (u_long)ip->i_number, fs->fs_fsmnt); 6131541Srgrimes panic("ffs_valloc: dup alloc"); 6141541Srgrimes } 6151541Srgrimes if (ip->i_blocks) { /* XXX */ 61637555Sbde printf("free inode %s/%lu had %ld blocks\n", 61737555Sbde fs->fs_fsmnt, (u_long)ino, (long)ip->i_blocks); 6181541Srgrimes ip->i_blocks = 0; 6191541Srgrimes } 6201541Srgrimes ip->i_flags = 0; 6211541Srgrimes /* 6221541Srgrimes * Set up a new generation number for this inode. 6231541Srgrimes */ 62431484Sbde if (ip->i_gen == 0 || ++ip->i_gen == 0) 62524149Sguido ip->i_gen = random() / 2 + 1; 6261541Srgrimes return (0); 6271541Srgrimesnoinodes: 62830474Sphk ffs_fserr(fs, cred->cr_uid, "out of inodes"); 6291541Srgrimes uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 6301541Srgrimes return (ENOSPC); 6311541Srgrimes} 6321541Srgrimes 6331541Srgrimes/* 6341541Srgrimes * Find a cylinder to place a directory. 6351541Srgrimes * 6361541Srgrimes * The policy implemented by this algorithm is to select from 6371541Srgrimes * among those cylinder groups with above the average number of 6381541Srgrimes * free inodes, the one with the smallest number of directories. 6391541Srgrimes */ 6401541Srgrimesstatic ino_t 6411541Srgrimesffs_dirpref(fs) 6421541Srgrimes register struct fs *fs; 6431541Srgrimes{ 6441541Srgrimes int cg, minndir, mincg, avgifree; 6451541Srgrimes 6461541Srgrimes avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 6471541Srgrimes minndir = fs->fs_ipg; 6481541Srgrimes mincg = 0; 6491541Srgrimes for (cg = 0; cg < fs->fs_ncg; cg++) 6501541Srgrimes if (fs->fs_cs(fs, cg).cs_ndir < minndir && 6511541Srgrimes fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 6521541Srgrimes mincg = cg; 6531541Srgrimes minndir = fs->fs_cs(fs, cg).cs_ndir; 6541541Srgrimes } 6551541Srgrimes return ((ino_t)(fs->fs_ipg * mincg)); 6561541Srgrimes} 6571541Srgrimes 6581541Srgrimes/* 6591541Srgrimes * Select the desired position for the next block in a file. The file is 6601541Srgrimes * logically divided into sections. The first section is composed of the 6611541Srgrimes * direct blocks. Each additional section contains fs_maxbpg blocks. 6628876Srgrimes * 6631541Srgrimes * If no blocks have been allocated in the first section, the policy is to 6641541Srgrimes * request a block in the same cylinder group as the inode that describes 6651541Srgrimes * the file. If no blocks have been allocated in any other section, the 6661541Srgrimes * policy is to place the section in a cylinder group with a greater than 6671541Srgrimes * average number of free blocks. An appropriate cylinder group is found 6681541Srgrimes * by using a rotor that sweeps the cylinder groups. When a new group of 6691541Srgrimes * blocks is needed, the sweep begins in the cylinder group following the 6701541Srgrimes * cylinder group from which the previous allocation was made. The sweep 6711541Srgrimes * continues until a cylinder group with greater than the average number 6721541Srgrimes * of free blocks is found. If the allocation is for the first block in an 6731541Srgrimes * indirect block, the information on the previous allocation is unavailable; 6741541Srgrimes * here a best guess is made based upon the logical block number being 6751541Srgrimes * allocated. 6768876Srgrimes * 6771541Srgrimes * If a section is already partially allocated, the policy is to 6781541Srgrimes * contiguously allocate fs_maxcontig blocks. The end of one of these 6791541Srgrimes * contiguous blocks and the beginning of the next is physically separated 6801541Srgrimes * so that the disk head will be in transit between them for at least 6811541Srgrimes * fs_rotdelay milliseconds. This is to allow time for the processor to 6821541Srgrimes * schedule another I/O transfer. 6831541Srgrimes */ 68422521Sdysonufs_daddr_t 6851541Srgrimesffs_blkpref(ip, lbn, indx, bap) 6861541Srgrimes struct inode *ip; 68722521Sdyson ufs_daddr_t lbn; 6881541Srgrimes int indx; 68922521Sdyson ufs_daddr_t *bap; 6901541Srgrimes{ 6911541Srgrimes register struct fs *fs; 6921541Srgrimes register int cg; 6931541Srgrimes int avgbfree, startcg; 69422521Sdyson ufs_daddr_t nextblk; 6951541Srgrimes 6961541Srgrimes fs = ip->i_fs; 6971541Srgrimes if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 69853996Smckusick if (lbn < NDADDR + NINDIR(fs)) { 6991541Srgrimes cg = ino_to_cg(fs, ip->i_number); 7001541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 7011541Srgrimes } 7021541Srgrimes /* 7031541Srgrimes * Find a cylinder with greater than average number of 7041541Srgrimes * unused data blocks. 7051541Srgrimes */ 7061541Srgrimes if (indx == 0 || bap[indx - 1] == 0) 7071541Srgrimes startcg = 7081541Srgrimes ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 7091541Srgrimes else 7101541Srgrimes startcg = dtog(fs, bap[indx - 1]) + 1; 7111541Srgrimes startcg %= fs->fs_ncg; 7121541Srgrimes avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 7131541Srgrimes for (cg = startcg; cg < fs->fs_ncg; cg++) 7141541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 7151541Srgrimes fs->fs_cgrotor = cg; 7161541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 7171541Srgrimes } 7181541Srgrimes for (cg = 0; cg <= startcg; cg++) 7191541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 7201541Srgrimes fs->fs_cgrotor = cg; 7211541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 7221541Srgrimes } 72317108Sbde return (0); 7241541Srgrimes } 7251541Srgrimes /* 7261541Srgrimes * One or more previous blocks have been laid out. If less 7271541Srgrimes * than fs_maxcontig previous blocks are contiguous, the 7281541Srgrimes * next block is requested contiguously, otherwise it is 7291541Srgrimes * requested rotationally delayed by fs_rotdelay milliseconds. 7301541Srgrimes */ 7311541Srgrimes nextblk = bap[indx - 1] + fs->fs_frag; 73210632Sdg if (fs->fs_rotdelay == 0 || indx < fs->fs_maxcontig || 73310632Sdg bap[indx - fs->fs_maxcontig] + 7341541Srgrimes blkstofrags(fs, fs->fs_maxcontig) != nextblk) 7351541Srgrimes return (nextblk); 73610632Sdg /* 73710632Sdg * Here we convert ms of delay to frags as: 73810632Sdg * (frags) = (ms) * (rev/sec) * (sect/rev) / 73910632Sdg * ((sect/frag) * (ms/sec)) 74010632Sdg * then round up to the next block. 74110632Sdg */ 74210632Sdg nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 74310632Sdg (NSPF(fs) * 1000), fs->fs_frag); 7441541Srgrimes return (nextblk); 7451541Srgrimes} 7461541Srgrimes 7471541Srgrimes/* 7481541Srgrimes * Implement the cylinder overflow algorithm. 7491541Srgrimes * 7501541Srgrimes * The policy implemented by this algorithm is: 7511541Srgrimes * 1) allocate the block in its requested cylinder group. 7521541Srgrimes * 2) quadradically rehash on the cylinder group number. 7531541Srgrimes * 3) brute force search for a free block. 7541541Srgrimes */ 7551541Srgrimes/*VARARGS5*/ 7561541Srgrimesstatic u_long 7571541Srgrimesffs_hashalloc(ip, cg, pref, size, allocator) 7581541Srgrimes struct inode *ip; 7591541Srgrimes int cg; 7601541Srgrimes long pref; 7611541Srgrimes int size; /* size for data blocks, mode for inodes */ 76212590Sbde allocfcn_t *allocator; 7631541Srgrimes{ 7641541Srgrimes register struct fs *fs; 76512590Sbde long result; /* XXX why not same type as we return? */ 7661541Srgrimes int i, icg = cg; 7671541Srgrimes 76862976Smckusick#ifdef DIAGNOSTIC 76962976Smckusick if (ITOV(ip)->v_mount->mnt_kern_flag & MNTK_SUSPENDED) 77062976Smckusick panic("ffs_hashalloc: allocation on suspended filesystem"); 77162976Smckusick#endif 7721541Srgrimes fs = ip->i_fs; 7731541Srgrimes /* 7741541Srgrimes * 1: preferred cylinder group 7751541Srgrimes */ 7761541Srgrimes result = (*allocator)(ip, cg, pref, size); 7771541Srgrimes if (result) 7781541Srgrimes return (result); 7791541Srgrimes /* 7801541Srgrimes * 2: quadratic rehash 7811541Srgrimes */ 7821541Srgrimes for (i = 1; i < fs->fs_ncg; i *= 2) { 7831541Srgrimes cg += i; 7841541Srgrimes if (cg >= fs->fs_ncg) 7851541Srgrimes cg -= fs->fs_ncg; 7861541Srgrimes result = (*allocator)(ip, cg, 0, size); 7871541Srgrimes if (result) 7881541Srgrimes return (result); 7891541Srgrimes } 7901541Srgrimes /* 7911541Srgrimes * 3: brute force search 7921541Srgrimes * Note that we start at i == 2, since 0 was checked initially, 7931541Srgrimes * and 1 is always checked in the quadratic rehash. 7941541Srgrimes */ 7951541Srgrimes cg = (icg + 2) % fs->fs_ncg; 7961541Srgrimes for (i = 2; i < fs->fs_ncg; i++) { 7971541Srgrimes result = (*allocator)(ip, cg, 0, size); 7981541Srgrimes if (result) 7991541Srgrimes return (result); 8001541Srgrimes cg++; 8011541Srgrimes if (cg == fs->fs_ncg) 8021541Srgrimes cg = 0; 8031541Srgrimes } 80412590Sbde return (0); 8051541Srgrimes} 8061541Srgrimes 8071541Srgrimes/* 8081541Srgrimes * Determine whether a fragment can be extended. 8091541Srgrimes * 8108876Srgrimes * Check to see if the necessary fragments are available, and 8111541Srgrimes * if they are, allocate them. 8121541Srgrimes */ 81322521Sdysonstatic ufs_daddr_t 8141541Srgrimesffs_fragextend(ip, cg, bprev, osize, nsize) 8151541Srgrimes struct inode *ip; 8161541Srgrimes int cg; 8171541Srgrimes long bprev; 8181541Srgrimes int osize, nsize; 8191541Srgrimes{ 8201541Srgrimes register struct fs *fs; 8211541Srgrimes register struct cg *cgp; 8221541Srgrimes struct buf *bp; 8231541Srgrimes long bno; 8241541Srgrimes int frags, bbase; 8251541Srgrimes int i, error; 82658087Smckusick u_int8_t *blksfree; 8271541Srgrimes 8281541Srgrimes fs = ip->i_fs; 8291541Srgrimes if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 83017108Sbde return (0); 8311541Srgrimes frags = numfrags(fs, nsize); 8321541Srgrimes bbase = fragnum(fs, bprev); 8331541Srgrimes if (bbase > fragnum(fs, (bprev + frags - 1))) { 8341541Srgrimes /* cannot extend across a block boundary */ 83517108Sbde return (0); 8361541Srgrimes } 8371541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 8381541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 8391541Srgrimes if (error) { 8401541Srgrimes brelse(bp); 84117108Sbde return (0); 8421541Srgrimes } 8431541Srgrimes cgp = (struct cg *)bp->b_data; 8441541Srgrimes if (!cg_chkmagic(cgp)) { 8451541Srgrimes brelse(bp); 84617108Sbde return (0); 8471541Srgrimes } 84855697Smckusick bp->b_xflags |= BX_BKGRDWRITE; 84934961Sphk cgp->cg_time = time_second; 8501541Srgrimes bno = dtogd(fs, bprev); 85158087Smckusick blksfree = cg_blksfree(cgp); 8521541Srgrimes for (i = numfrags(fs, osize); i < frags; i++) 85358087Smckusick if (isclr(blksfree, bno + i)) { 8541541Srgrimes brelse(bp); 85517108Sbde return (0); 8561541Srgrimes } 8571541Srgrimes /* 8581541Srgrimes * the current fragment can be extended 8591541Srgrimes * deduct the count on fragment being extended into 8601541Srgrimes * increase the count on the remaining fragment (if any) 8611541Srgrimes * allocate the extended piece 8621541Srgrimes */ 8631541Srgrimes for (i = frags; i < fs->fs_frag - bbase; i++) 86458087Smckusick if (isclr(blksfree, bno + i)) 8651541Srgrimes break; 8661541Srgrimes cgp->cg_frsum[i - numfrags(fs, osize)]--; 8671541Srgrimes if (i != frags) 8681541Srgrimes cgp->cg_frsum[i - frags]++; 8691541Srgrimes for (i = numfrags(fs, osize); i < frags; i++) { 87058087Smckusick clrbit(blksfree, bno + i); 8711541Srgrimes cgp->cg_cs.cs_nffree--; 8721541Srgrimes fs->fs_cstotal.cs_nffree--; 8731541Srgrimes fs->fs_cs(fs, cg).cs_nffree--; 8741541Srgrimes } 8751541Srgrimes fs->fs_fmod = 1; 87634266Sjulian if (DOINGSOFTDEP(ITOV(ip))) 87734266Sjulian softdep_setup_blkmapdep(bp, fs, bprev); 8781541Srgrimes bdwrite(bp); 8791541Srgrimes return (bprev); 8801541Srgrimes} 8811541Srgrimes 8821541Srgrimes/* 8831541Srgrimes * Determine whether a block can be allocated. 8841541Srgrimes * 8851541Srgrimes * Check to see if a block of the appropriate size is available, 8861541Srgrimes * and if it is, allocate it. 8871541Srgrimes */ 88822521Sdysonstatic ufs_daddr_t 8891541Srgrimesffs_alloccg(ip, cg, bpref, size) 8901541Srgrimes struct inode *ip; 8911541Srgrimes int cg; 89222521Sdyson ufs_daddr_t bpref; 8931541Srgrimes int size; 8941541Srgrimes{ 8951541Srgrimes register struct fs *fs; 8961541Srgrimes register struct cg *cgp; 8971541Srgrimes struct buf *bp; 8981541Srgrimes register int i; 89934266Sjulian ufs_daddr_t bno, blkno; 90034266Sjulian int allocsiz, error, frags; 90158087Smckusick u_int8_t *blksfree; 9021541Srgrimes 9031541Srgrimes fs = ip->i_fs; 9041541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 90517108Sbde return (0); 9061541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 9071541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 9081541Srgrimes if (error) { 9091541Srgrimes brelse(bp); 91017108Sbde return (0); 9111541Srgrimes } 9121541Srgrimes cgp = (struct cg *)bp->b_data; 9131541Srgrimes if (!cg_chkmagic(cgp) || 9141541Srgrimes (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 9151541Srgrimes brelse(bp); 91617108Sbde return (0); 9171541Srgrimes } 91855697Smckusick bp->b_xflags |= BX_BKGRDWRITE; 91934961Sphk cgp->cg_time = time_second; 9201541Srgrimes if (size == fs->fs_bsize) { 92134266Sjulian bno = ffs_alloccgblk(ip, bp, bpref); 9221541Srgrimes bdwrite(bp); 9231541Srgrimes return (bno); 9241541Srgrimes } 9251541Srgrimes /* 9261541Srgrimes * check to see if any fragments are already available 9271541Srgrimes * allocsiz is the size which will be allocated, hacking 9281541Srgrimes * it down to a smaller size if necessary 9291541Srgrimes */ 93058087Smckusick blksfree = cg_blksfree(cgp); 9311541Srgrimes frags = numfrags(fs, size); 9321541Srgrimes for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 9331541Srgrimes if (cgp->cg_frsum[allocsiz] != 0) 9341541Srgrimes break; 9351541Srgrimes if (allocsiz == fs->fs_frag) { 9361541Srgrimes /* 9378876Srgrimes * no fragments were available, so a block will be 9381541Srgrimes * allocated, and hacked up 9391541Srgrimes */ 9401541Srgrimes if (cgp->cg_cs.cs_nbfree == 0) { 9411541Srgrimes brelse(bp); 94217108Sbde return (0); 9431541Srgrimes } 94434266Sjulian bno = ffs_alloccgblk(ip, bp, bpref); 9451541Srgrimes bpref = dtogd(fs, bno); 9461541Srgrimes for (i = frags; i < fs->fs_frag; i++) 94758087Smckusick setbit(blksfree, bpref + i); 9481541Srgrimes i = fs->fs_frag - frags; 9491541Srgrimes cgp->cg_cs.cs_nffree += i; 9501541Srgrimes fs->fs_cstotal.cs_nffree += i; 9511541Srgrimes fs->fs_cs(fs, cg).cs_nffree += i; 9521541Srgrimes fs->fs_fmod = 1; 9531541Srgrimes cgp->cg_frsum[i]++; 9541541Srgrimes bdwrite(bp); 9551541Srgrimes return (bno); 9561541Srgrimes } 9571541Srgrimes bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 9581541Srgrimes if (bno < 0) { 9591541Srgrimes brelse(bp); 96017108Sbde return (0); 9611541Srgrimes } 9621541Srgrimes for (i = 0; i < frags; i++) 96358087Smckusick clrbit(blksfree, bno + i); 9641541Srgrimes cgp->cg_cs.cs_nffree -= frags; 9651541Srgrimes fs->fs_cstotal.cs_nffree -= frags; 9661541Srgrimes fs->fs_cs(fs, cg).cs_nffree -= frags; 9671541Srgrimes fs->fs_fmod = 1; 9681541Srgrimes cgp->cg_frsum[allocsiz]--; 9691541Srgrimes if (frags != allocsiz) 9701541Srgrimes cgp->cg_frsum[allocsiz - frags]++; 97134266Sjulian blkno = cg * fs->fs_fpg + bno; 97234266Sjulian if (DOINGSOFTDEP(ITOV(ip))) 97334266Sjulian softdep_setup_blkmapdep(bp, fs, blkno); 9741541Srgrimes bdwrite(bp); 97534266Sjulian return ((u_long)blkno); 9761541Srgrimes} 9771541Srgrimes 9781541Srgrimes/* 9791541Srgrimes * Allocate a block in a cylinder group. 9801541Srgrimes * 9811541Srgrimes * This algorithm implements the following policy: 9821541Srgrimes * 1) allocate the requested block. 9831541Srgrimes * 2) allocate a rotationally optimal block in the same cylinder. 9841541Srgrimes * 3) allocate the next available block on the block rotor for the 9851541Srgrimes * specified cylinder group. 9861541Srgrimes * Note that this routine only allocates fs_bsize blocks; these 9871541Srgrimes * blocks may be fragmented by the routine that allocates them. 9881541Srgrimes */ 98922521Sdysonstatic ufs_daddr_t 99034266Sjulianffs_alloccgblk(ip, bp, bpref) 99134266Sjulian struct inode *ip; 99234266Sjulian struct buf *bp; 99322521Sdyson ufs_daddr_t bpref; 9941541Srgrimes{ 99534266Sjulian struct fs *fs; 99634266Sjulian struct cg *cgp; 99722521Sdyson ufs_daddr_t bno, blkno; 9981541Srgrimes int cylno, pos, delta; 9991541Srgrimes short *cylbp; 10001541Srgrimes register int i; 100158087Smckusick u_int8_t *blksfree; 10021541Srgrimes 100334266Sjulian fs = ip->i_fs; 100434266Sjulian cgp = (struct cg *)bp->b_data; 100558087Smckusick blksfree = cg_blksfree(cgp); 10061541Srgrimes if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) { 10071541Srgrimes bpref = cgp->cg_rotor; 10081541Srgrimes goto norot; 10091541Srgrimes } 10101541Srgrimes bpref = blknum(fs, bpref); 10111541Srgrimes bpref = dtogd(fs, bpref); 10121541Srgrimes /* 10131541Srgrimes * if the requested block is available, use it 10141541Srgrimes */ 101558087Smckusick if (ffs_isblock(fs, blksfree, fragstoblks(fs, bpref))) { 10161541Srgrimes bno = bpref; 10171541Srgrimes goto gotit; 10181541Srgrimes } 10196769Sse if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) { 10201541Srgrimes /* 10211541Srgrimes * Block layout information is not available. 10221541Srgrimes * Leaving bpref unchanged means we take the 10238876Srgrimes * next available free block following the one 10241541Srgrimes * we just allocated. Hopefully this will at 10251541Srgrimes * least hit a track cache on drives of unknown 10261541Srgrimes * geometry (e.g. SCSI). 10271541Srgrimes */ 10281541Srgrimes goto norot; 10291541Srgrimes } 10301541Srgrimes /* 10316769Sse * check for a block available on the same cylinder 10326769Sse */ 10336769Sse cylno = cbtocylno(fs, bpref); 10346769Sse if (cg_blktot(cgp)[cylno] == 0) 10356769Sse goto norot; 10366769Sse /* 10378876Srgrimes * check the summary information to see if a block is 10381541Srgrimes * available in the requested cylinder starting at the 10391541Srgrimes * requested rotational position and proceeding around. 10401541Srgrimes */ 10411541Srgrimes cylbp = cg_blks(fs, cgp, cylno); 10421541Srgrimes pos = cbtorpos(fs, bpref); 10431541Srgrimes for (i = pos; i < fs->fs_nrpos; i++) 10441541Srgrimes if (cylbp[i] > 0) 10451541Srgrimes break; 10461541Srgrimes if (i == fs->fs_nrpos) 10471541Srgrimes for (i = 0; i < pos; i++) 10481541Srgrimes if (cylbp[i] > 0) 10491541Srgrimes break; 10501541Srgrimes if (cylbp[i] > 0) { 10511541Srgrimes /* 10521541Srgrimes * found a rotational position, now find the actual 10531541Srgrimes * block. A panic if none is actually there. 10541541Srgrimes */ 10551541Srgrimes pos = cylno % fs->fs_cpc; 10561541Srgrimes bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 10571541Srgrimes if (fs_postbl(fs, pos)[i] == -1) { 10581541Srgrimes printf("pos = %d, i = %d, fs = %s\n", 10591541Srgrimes pos, i, fs->fs_fsmnt); 10601541Srgrimes panic("ffs_alloccgblk: cyl groups corrupted"); 10611541Srgrimes } 10621541Srgrimes for (i = fs_postbl(fs, pos)[i];; ) { 106358087Smckusick if (ffs_isblock(fs, blksfree, bno + i)) { 10641541Srgrimes bno = blkstofrags(fs, (bno + i)); 10651541Srgrimes goto gotit; 10661541Srgrimes } 10671541Srgrimes delta = fs_rotbl(fs)[i]; 10681541Srgrimes if (delta <= 0 || 10691541Srgrimes delta + i > fragstoblks(fs, fs->fs_fpg)) 10701541Srgrimes break; 10711541Srgrimes i += delta; 10721541Srgrimes } 10731541Srgrimes printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 10741541Srgrimes panic("ffs_alloccgblk: can't find blk in cyl"); 10751541Srgrimes } 10761541Srgrimesnorot: 10771541Srgrimes /* 10781541Srgrimes * no blocks in the requested cylinder, so take next 10791541Srgrimes * available one in this cylinder group. 10801541Srgrimes */ 10811541Srgrimes bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 10821541Srgrimes if (bno < 0) 108317108Sbde return (0); 10841541Srgrimes cgp->cg_rotor = bno; 10851541Srgrimesgotit: 10861541Srgrimes blkno = fragstoblks(fs, bno); 108758087Smckusick ffs_clrblock(fs, blksfree, (long)blkno); 10881541Srgrimes ffs_clusteracct(fs, cgp, blkno, -1); 10891541Srgrimes cgp->cg_cs.cs_nbfree--; 10901541Srgrimes fs->fs_cstotal.cs_nbfree--; 10911541Srgrimes fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 10921541Srgrimes cylno = cbtocylno(fs, bno); 10931541Srgrimes cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 10941541Srgrimes cg_blktot(cgp)[cylno]--; 10951541Srgrimes fs->fs_fmod = 1; 109634266Sjulian blkno = cgp->cg_cgx * fs->fs_fpg + bno; 109734266Sjulian if (DOINGSOFTDEP(ITOV(ip))) 109834266Sjulian softdep_setup_blkmapdep(bp, fs, blkno); 109934266Sjulian return (blkno); 11001541Srgrimes} 11011541Srgrimes 11021541Srgrimes/* 11031541Srgrimes * Determine whether a cluster can be allocated. 11041541Srgrimes * 11051541Srgrimes * We do not currently check for optimal rotational layout if there 11061541Srgrimes * are multiple choices in the same cylinder group. Instead we just 11071541Srgrimes * take the first one that we find following bpref. 11081541Srgrimes */ 110922521Sdysonstatic ufs_daddr_t 11101541Srgrimesffs_clusteralloc(ip, cg, bpref, len) 11111541Srgrimes struct inode *ip; 11121541Srgrimes int cg; 111322521Sdyson ufs_daddr_t bpref; 11141541Srgrimes int len; 11151541Srgrimes{ 11161541Srgrimes register struct fs *fs; 11171541Srgrimes register struct cg *cgp; 11181541Srgrimes struct buf *bp; 111922521Sdyson int i, got, run, bno, bit, map; 11201541Srgrimes u_char *mapp; 112122521Sdyson int32_t *lp; 112258087Smckusick u_int8_t *blksfree; 11231541Srgrimes 11241541Srgrimes fs = ip->i_fs; 112522521Sdyson if (fs->fs_maxcluster[cg] < len) 112654952Seivind return (0); 11271541Srgrimes if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 11281541Srgrimes NOCRED, &bp)) 11291541Srgrimes goto fail; 11301541Srgrimes cgp = (struct cg *)bp->b_data; 11311541Srgrimes if (!cg_chkmagic(cgp)) 11321541Srgrimes goto fail; 113355697Smckusick bp->b_xflags |= BX_BKGRDWRITE; 11341541Srgrimes /* 11351541Srgrimes * Check to see if a cluster of the needed size (or bigger) is 11361541Srgrimes * available in this cylinder group. 11371541Srgrimes */ 113822521Sdyson lp = &cg_clustersum(cgp)[len]; 11391541Srgrimes for (i = len; i <= fs->fs_contigsumsize; i++) 114022521Sdyson if (*lp++ > 0) 11411541Srgrimes break; 114222521Sdyson if (i > fs->fs_contigsumsize) { 114322521Sdyson /* 114422521Sdyson * This is the first time looking for a cluster in this 114522521Sdyson * cylinder group. Update the cluster summary information 114622521Sdyson * to reflect the true maximum sized cluster so that 114722521Sdyson * future cluster allocation requests can avoid reading 114822521Sdyson * the cylinder group map only to find no clusters. 114922521Sdyson */ 115022521Sdyson lp = &cg_clustersum(cgp)[len - 1]; 115122521Sdyson for (i = len - 1; i > 0; i--) 115222521Sdyson if (*lp-- > 0) 115322521Sdyson break; 115422521Sdyson fs->fs_maxcluster[cg] = i; 11551541Srgrimes goto fail; 115622521Sdyson } 11571541Srgrimes /* 11581541Srgrimes * Search the cluster map to find a big enough cluster. 11591541Srgrimes * We take the first one that we find, even if it is larger 11601541Srgrimes * than we need as we prefer to get one close to the previous 11611541Srgrimes * block allocation. We do not search before the current 11621541Srgrimes * preference point as we do not want to allocate a block 11631541Srgrimes * that is allocated before the previous one (as we will 11641541Srgrimes * then have to wait for another pass of the elevator 11651541Srgrimes * algorithm before it will be read). We prefer to fail and 11661541Srgrimes * be recalled to try an allocation in the next cylinder group. 11671541Srgrimes */ 11681541Srgrimes if (dtog(fs, bpref) != cg) 11691541Srgrimes bpref = 0; 11701541Srgrimes else 11711541Srgrimes bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 11721541Srgrimes mapp = &cg_clustersfree(cgp)[bpref / NBBY]; 11731541Srgrimes map = *mapp++; 11741541Srgrimes bit = 1 << (bpref % NBBY); 117522521Sdyson for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) { 11761541Srgrimes if ((map & bit) == 0) { 11771541Srgrimes run = 0; 11781541Srgrimes } else { 11791541Srgrimes run++; 11801541Srgrimes if (run == len) 11811541Srgrimes break; 11821541Srgrimes } 118322521Sdyson if ((got & (NBBY - 1)) != (NBBY - 1)) { 11841541Srgrimes bit <<= 1; 11851541Srgrimes } else { 11861541Srgrimes map = *mapp++; 11871541Srgrimes bit = 1; 11881541Srgrimes } 11891541Srgrimes } 119027890Sphk if (got >= cgp->cg_nclusterblks) 11911541Srgrimes goto fail; 11921541Srgrimes /* 11931541Srgrimes * Allocate the cluster that we have found. 11941541Srgrimes */ 119558087Smckusick blksfree = cg_blksfree(cgp); 119622521Sdyson for (i = 1; i <= len; i++) 119758087Smckusick if (!ffs_isblock(fs, blksfree, got - run + i)) 119822521Sdyson panic("ffs_clusteralloc: map mismatch"); 119922521Sdyson bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1); 120022521Sdyson if (dtog(fs, bno) != cg) 120122521Sdyson panic("ffs_clusteralloc: allocated out of group"); 12021541Srgrimes len = blkstofrags(fs, len); 12031541Srgrimes for (i = 0; i < len; i += fs->fs_frag) 120434266Sjulian if ((got = ffs_alloccgblk(ip, bp, bno + i)) != bno + i) 12051541Srgrimes panic("ffs_clusteralloc: lost block"); 12069980Sdg bdwrite(bp); 12071541Srgrimes return (bno); 12081541Srgrimes 12091541Srgrimesfail: 12101541Srgrimes brelse(bp); 12111541Srgrimes return (0); 12121541Srgrimes} 12131541Srgrimes 12141541Srgrimes/* 12151541Srgrimes * Determine whether an inode can be allocated. 12161541Srgrimes * 12171541Srgrimes * Check to see if an inode is available, and if it is, 12181541Srgrimes * allocate it using the following policy: 12191541Srgrimes * 1) allocate the requested inode. 12201541Srgrimes * 2) allocate the next available inode after the requested 12211541Srgrimes * inode in the specified cylinder group. 12221541Srgrimes */ 12231541Srgrimesstatic ino_t 12241541Srgrimesffs_nodealloccg(ip, cg, ipref, mode) 12251541Srgrimes struct inode *ip; 12261541Srgrimes int cg; 122722521Sdyson ufs_daddr_t ipref; 12281541Srgrimes int mode; 12291541Srgrimes{ 12301541Srgrimes register struct fs *fs; 12311541Srgrimes register struct cg *cgp; 12321541Srgrimes struct buf *bp; 123358087Smckusick u_int8_t *inosused; 12341541Srgrimes int error, start, len, loc, map, i; 12351541Srgrimes 12361541Srgrimes fs = ip->i_fs; 12371541Srgrimes if (fs->fs_cs(fs, cg).cs_nifree == 0) 123817108Sbde return (0); 12391541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 12401541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 12411541Srgrimes if (error) { 12421541Srgrimes brelse(bp); 124317108Sbde return (0); 12441541Srgrimes } 12451541Srgrimes cgp = (struct cg *)bp->b_data; 12461541Srgrimes if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 12471541Srgrimes brelse(bp); 124817108Sbde return (0); 12491541Srgrimes } 125055697Smckusick bp->b_xflags |= BX_BKGRDWRITE; 125134961Sphk cgp->cg_time = time_second; 125258087Smckusick inosused = cg_inosused(cgp); 12531541Srgrimes if (ipref) { 12541541Srgrimes ipref %= fs->fs_ipg; 125558087Smckusick if (isclr(inosused, ipref)) 12561541Srgrimes goto gotit; 12571541Srgrimes } 12581541Srgrimes start = cgp->cg_irotor / NBBY; 12591541Srgrimes len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 126058087Smckusick loc = skpc(0xff, len, &inosused[start]); 12611541Srgrimes if (loc == 0) { 12621541Srgrimes len = start + 1; 12631541Srgrimes start = 0; 126458087Smckusick loc = skpc(0xff, len, &inosused[0]); 12651541Srgrimes if (loc == 0) { 12666357Sphk printf("cg = %d, irotor = %ld, fs = %s\n", 126737555Sbde cg, (long)cgp->cg_irotor, fs->fs_fsmnt); 12681541Srgrimes panic("ffs_nodealloccg: map corrupted"); 12691541Srgrimes /* NOTREACHED */ 12701541Srgrimes } 12711541Srgrimes } 12721541Srgrimes i = start + len - loc; 127358087Smckusick map = inosused[i]; 12741541Srgrimes ipref = i * NBBY; 12751541Srgrimes for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 12761541Srgrimes if ((map & i) == 0) { 12771541Srgrimes cgp->cg_irotor = ipref; 12781541Srgrimes goto gotit; 12791541Srgrimes } 12801541Srgrimes } 12811541Srgrimes printf("fs = %s\n", fs->fs_fsmnt); 12821541Srgrimes panic("ffs_nodealloccg: block not in map"); 12831541Srgrimes /* NOTREACHED */ 12841541Srgrimesgotit: 128534266Sjulian if (DOINGSOFTDEP(ITOV(ip))) 128634266Sjulian softdep_setup_inomapdep(bp, ip, cg * fs->fs_ipg + ipref); 128758087Smckusick setbit(inosused, ipref); 12881541Srgrimes cgp->cg_cs.cs_nifree--; 12891541Srgrimes fs->fs_cstotal.cs_nifree--; 12901541Srgrimes fs->fs_cs(fs, cg).cs_nifree--; 12911541Srgrimes fs->fs_fmod = 1; 12921541Srgrimes if ((mode & IFMT) == IFDIR) { 12931541Srgrimes cgp->cg_cs.cs_ndir++; 12941541Srgrimes fs->fs_cstotal.cs_ndir++; 12951541Srgrimes fs->fs_cs(fs, cg).cs_ndir++; 12961541Srgrimes } 12971541Srgrimes bdwrite(bp); 12981541Srgrimes return (cg * fs->fs_ipg + ipref); 12991541Srgrimes} 13001541Srgrimes 13011541Srgrimes/* 13021541Srgrimes * Free a block or fragment. 13031541Srgrimes * 13041541Srgrimes * The specified block or fragment is placed back in the 13058876Srgrimes * free map. If a fragment is deallocated, a possible 13061541Srgrimes * block reassembly is checked. 13071541Srgrimes */ 13081549Srgrimesvoid 13091541Srgrimesffs_blkfree(ip, bno, size) 13101541Srgrimes register struct inode *ip; 131122521Sdyson ufs_daddr_t bno; 13121541Srgrimes long size; 13131541Srgrimes{ 13141541Srgrimes register struct fs *fs; 13151541Srgrimes register struct cg *cgp; 13161541Srgrimes struct buf *bp; 131722521Sdyson ufs_daddr_t blkno; 13181541Srgrimes int i, error, cg, blk, frags, bbase; 131958087Smckusick u_int8_t *blksfree; 132062976Smckusick struct vnode *vp; 13211541Srgrimes 13221541Srgrimes fs = ip->i_fs; 132362976Smckusick#ifdef DIAGNOSTIC 132462976Smckusick if ((vp = ITOV(ip)) != NULL && vp->v_mount != NULL && 132562976Smckusick (vp->v_mount->mnt_kern_flag & MNTK_SUSPENDED)) 132662976Smckusick panic("ffs_blkfree: deallocation on suspended filesystem"); 132734266Sjulian if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0 || 132834266Sjulian fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) { 132950253Sbde printf("dev=%s, bno = %ld, bsize = %ld, size = %ld, fs = %s\n", 133050253Sbde devtoname(ip->i_dev), (long)bno, (long)fs->fs_bsize, size, 133150253Sbde fs->fs_fsmnt); 133223560Smpp panic("ffs_blkfree: bad size"); 13331541Srgrimes } 133462976Smckusick#endif 133562976Smckusick if ((ip->i_devvp->v_flag & VCOPYONWRITE) && 133662976Smckusick ffs_snapblkfree(ip, bno, size)) 133762976Smckusick return; 133862976Smckusick VOP_FREEBLKS(ip->i_devvp, fsbtodb(fs, bno), size); 13391541Srgrimes cg = dtog(fs, bno); 13401541Srgrimes if ((u_int)bno >= fs->fs_size) { 134137555Sbde printf("bad block %ld, ino %lu\n", 134237555Sbde (long)bno, (u_long)ip->i_number); 13431541Srgrimes ffs_fserr(fs, ip->i_uid, "bad block"); 13441541Srgrimes return; 13451541Srgrimes } 13461541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 13471541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 13481541Srgrimes if (error) { 13491541Srgrimes brelse(bp); 13501541Srgrimes return; 13511541Srgrimes } 13521541Srgrimes cgp = (struct cg *)bp->b_data; 13531541Srgrimes if (!cg_chkmagic(cgp)) { 13541541Srgrimes brelse(bp); 13551541Srgrimes return; 13561541Srgrimes } 135755697Smckusick bp->b_xflags |= BX_BKGRDWRITE; 135834961Sphk cgp->cg_time = time_second; 13591541Srgrimes bno = dtogd(fs, bno); 136058087Smckusick blksfree = cg_blksfree(cgp); 13611541Srgrimes if (size == fs->fs_bsize) { 13621541Srgrimes blkno = fragstoblks(fs, bno); 136358087Smckusick if (!ffs_isfreeblock(fs, blksfree, blkno)) { 136450253Sbde printf("dev = %s, block = %ld, fs = %s\n", 136550253Sbde devtoname(ip->i_dev), (long)bno, fs->fs_fsmnt); 136623560Smpp panic("ffs_blkfree: freeing free block"); 13671541Srgrimes } 136858087Smckusick ffs_setblock(fs, blksfree, blkno); 13691541Srgrimes ffs_clusteracct(fs, cgp, blkno, 1); 13701541Srgrimes cgp->cg_cs.cs_nbfree++; 13711541Srgrimes fs->fs_cstotal.cs_nbfree++; 13721541Srgrimes fs->fs_cs(fs, cg).cs_nbfree++; 13731541Srgrimes i = cbtocylno(fs, bno); 13741541Srgrimes cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; 13751541Srgrimes cg_blktot(cgp)[i]++; 13761541Srgrimes } else { 13771541Srgrimes bbase = bno - fragnum(fs, bno); 13781541Srgrimes /* 13791541Srgrimes * decrement the counts associated with the old frags 13801541Srgrimes */ 138158087Smckusick blk = blkmap(fs, blksfree, bbase); 13821541Srgrimes ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 13831541Srgrimes /* 13841541Srgrimes * deallocate the fragment 13851541Srgrimes */ 13861541Srgrimes frags = numfrags(fs, size); 13871541Srgrimes for (i = 0; i < frags; i++) { 138858087Smckusick if (isset(blksfree, bno + i)) { 138950253Sbde printf("dev = %s, block = %ld, fs = %s\n", 139050253Sbde devtoname(ip->i_dev), (long)(bno + i), 139137555Sbde fs->fs_fsmnt); 139223560Smpp panic("ffs_blkfree: freeing free frag"); 13931541Srgrimes } 139458087Smckusick setbit(blksfree, bno + i); 13951541Srgrimes } 13961541Srgrimes cgp->cg_cs.cs_nffree += i; 13971541Srgrimes fs->fs_cstotal.cs_nffree += i; 13981541Srgrimes fs->fs_cs(fs, cg).cs_nffree += i; 13991541Srgrimes /* 14001541Srgrimes * add back in counts associated with the new frags 14011541Srgrimes */ 140258087Smckusick blk = blkmap(fs, blksfree, bbase); 14031541Srgrimes ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 14041541Srgrimes /* 14051541Srgrimes * if a complete block has been reassembled, account for it 14061541Srgrimes */ 14071541Srgrimes blkno = fragstoblks(fs, bbase); 140858087Smckusick if (ffs_isblock(fs, blksfree, blkno)) { 14091541Srgrimes cgp->cg_cs.cs_nffree -= fs->fs_frag; 14101541Srgrimes fs->fs_cstotal.cs_nffree -= fs->fs_frag; 14111541Srgrimes fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 14121541Srgrimes ffs_clusteracct(fs, cgp, blkno, 1); 14131541Srgrimes cgp->cg_cs.cs_nbfree++; 14141541Srgrimes fs->fs_cstotal.cs_nbfree++; 14151541Srgrimes fs->fs_cs(fs, cg).cs_nbfree++; 14161541Srgrimes i = cbtocylno(fs, bbase); 14171541Srgrimes cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 14181541Srgrimes cg_blktot(cgp)[i]++; 14191541Srgrimes } 14201541Srgrimes } 14211541Srgrimes fs->fs_fmod = 1; 14221541Srgrimes bdwrite(bp); 14231541Srgrimes} 14241541Srgrimes 142522521Sdyson#ifdef DIAGNOSTIC 14261541Srgrimes/* 142722521Sdyson * Verify allocation of a block or fragment. Returns true if block or 142822521Sdyson * fragment is allocated, false if it is free. 142922521Sdyson */ 143031352Sbdestatic int 143122521Sdysonffs_checkblk(ip, bno, size) 143222521Sdyson struct inode *ip; 143322521Sdyson ufs_daddr_t bno; 143422521Sdyson long size; 143522521Sdyson{ 143622521Sdyson struct fs *fs; 143722521Sdyson struct cg *cgp; 143822521Sdyson struct buf *bp; 143922521Sdyson int i, error, frags, free; 144058087Smckusick u_int8_t *blksfree; 144122521Sdyson 144222521Sdyson fs = ip->i_fs; 144322521Sdyson if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 144437555Sbde printf("bsize = %ld, size = %ld, fs = %s\n", 144537555Sbde (long)fs->fs_bsize, size, fs->fs_fsmnt); 144622544Smpp panic("ffs_checkblk: bad size"); 144722521Sdyson } 144822521Sdyson if ((u_int)bno >= fs->fs_size) 144922544Smpp panic("ffs_checkblk: bad block %d", bno); 145022521Sdyson error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))), 145122521Sdyson (int)fs->fs_cgsize, NOCRED, &bp); 145222544Smpp if (error) 145322544Smpp panic("ffs_checkblk: cg bread failed"); 145422521Sdyson cgp = (struct cg *)bp->b_data; 145522544Smpp if (!cg_chkmagic(cgp)) 145622544Smpp panic("ffs_checkblk: cg magic mismatch"); 145755697Smckusick bp->b_xflags |= BX_BKGRDWRITE; 145858087Smckusick blksfree = cg_blksfree(cgp); 145922521Sdyson bno = dtogd(fs, bno); 146022521Sdyson if (size == fs->fs_bsize) { 146158087Smckusick free = ffs_isblock(fs, blksfree, fragstoblks(fs, bno)); 146222521Sdyson } else { 146322521Sdyson frags = numfrags(fs, size); 146422521Sdyson for (free = 0, i = 0; i < frags; i++) 146558087Smckusick if (isset(blksfree, bno + i)) 146622521Sdyson free++; 146722521Sdyson if (free != 0 && free != frags) 146822544Smpp panic("ffs_checkblk: partially free fragment"); 146922521Sdyson } 147022521Sdyson brelse(bp); 147122521Sdyson return (!free); 147222521Sdyson} 147322521Sdyson#endif /* DIAGNOSTIC */ 147422521Sdyson 147522521Sdyson/* 14761541Srgrimes * Free an inode. 14771541Srgrimes */ 14781541Srgrimesint 147934266Sjulianffs_vfree( pvp, ino, mode) 148030474Sphk struct vnode *pvp; 148130474Sphk ino_t ino; 148230474Sphk int mode; 14831541Srgrimes{ 148434266Sjulian if (DOINGSOFTDEP(pvp)) { 148534266Sjulian softdep_freefile(pvp, ino, mode); 148634266Sjulian return (0); 148734266Sjulian } 148834266Sjulian return (ffs_freefile(pvp, ino, mode)); 148934266Sjulian} 149034266Sjulian 149134266Sjulian/* 149234266Sjulian * Do the actual free operation. 149334266Sjulian * The specified inode is placed back in the free map. 149434266Sjulian */ 149534266Sjulian int 149634266Sjulian ffs_freefile( pvp, ino, mode) 149734266Sjulian struct vnode *pvp; 149834266Sjulian ino_t ino; 149934266Sjulian int mode; 150034266Sjulian{ 15011541Srgrimes register struct fs *fs; 15021541Srgrimes register struct cg *cgp; 15031541Srgrimes register struct inode *pip; 15041541Srgrimes struct buf *bp; 15051541Srgrimes int error, cg; 150658087Smckusick u_int8_t *inosused; 15071541Srgrimes 150830474Sphk pip = VTOI(pvp); 15091541Srgrimes fs = pip->i_fs; 15101541Srgrimes if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 151147085Speter panic("ffs_vfree: range: dev = (%d,%d), ino = %d, fs = %s", 151247085Speter major(pip->i_dev), minor(pip->i_dev), ino, fs->fs_fsmnt); 15131541Srgrimes cg = ino_to_cg(fs, ino); 15141541Srgrimes error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 15151541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 15161541Srgrimes if (error) { 15171541Srgrimes brelse(bp); 151834266Sjulian return (error); 15191541Srgrimes } 15201541Srgrimes cgp = (struct cg *)bp->b_data; 15211541Srgrimes if (!cg_chkmagic(cgp)) { 15221541Srgrimes brelse(bp); 15231541Srgrimes return (0); 15241541Srgrimes } 152555697Smckusick bp->b_xflags |= BX_BKGRDWRITE; 152634961Sphk cgp->cg_time = time_second; 152758087Smckusick inosused = cg_inosused(cgp); 15281541Srgrimes ino %= fs->fs_ipg; 152958087Smckusick if (isclr(inosused, ino)) { 153050253Sbde printf("dev = %s, ino = %lu, fs = %s\n", 153150253Sbde devtoname(pip->i_dev), (u_long)ino, fs->fs_fsmnt); 15321541Srgrimes if (fs->fs_ronly == 0) 153323560Smpp panic("ffs_vfree: freeing free inode"); 15341541Srgrimes } 153558087Smckusick clrbit(inosused, ino); 15361541Srgrimes if (ino < cgp->cg_irotor) 15371541Srgrimes cgp->cg_irotor = ino; 15381541Srgrimes cgp->cg_cs.cs_nifree++; 15391541Srgrimes fs->fs_cstotal.cs_nifree++; 15401541Srgrimes fs->fs_cs(fs, cg).cs_nifree++; 154130474Sphk if ((mode & IFMT) == IFDIR) { 15421541Srgrimes cgp->cg_cs.cs_ndir--; 15431541Srgrimes fs->fs_cstotal.cs_ndir--; 15441541Srgrimes fs->fs_cs(fs, cg).cs_ndir--; 15451541Srgrimes } 15461541Srgrimes fs->fs_fmod = 1; 15471541Srgrimes bdwrite(bp); 15481541Srgrimes return (0); 15491541Srgrimes} 15501541Srgrimes 15511541Srgrimes/* 15521541Srgrimes * Find a block of the specified size in the specified cylinder group. 15531541Srgrimes * 15541541Srgrimes * It is a panic if a request is made to find a block if none are 15551541Srgrimes * available. 15561541Srgrimes */ 155722521Sdysonstatic ufs_daddr_t 15581541Srgrimesffs_mapsearch(fs, cgp, bpref, allocsiz) 15591541Srgrimes register struct fs *fs; 15601541Srgrimes register struct cg *cgp; 156122521Sdyson ufs_daddr_t bpref; 15621541Srgrimes int allocsiz; 15631541Srgrimes{ 156422521Sdyson ufs_daddr_t bno; 15651541Srgrimes int start, len, loc, i; 15661541Srgrimes int blk, field, subfield, pos; 156758087Smckusick u_int8_t *blksfree; 15681541Srgrimes 15691541Srgrimes /* 15701541Srgrimes * find the fragment by searching through the free block 15711541Srgrimes * map for an appropriate bit pattern 15721541Srgrimes */ 15731541Srgrimes if (bpref) 15741541Srgrimes start = dtogd(fs, bpref) / NBBY; 15751541Srgrimes else 15761541Srgrimes start = cgp->cg_frotor / NBBY; 157758087Smckusick blksfree = cg_blksfree(cgp); 15781541Srgrimes len = howmany(fs->fs_fpg, NBBY) - start; 157958087Smckusick loc = scanc((u_int)len, (u_char *)&blksfree[start], 15801541Srgrimes (u_char *)fragtbl[fs->fs_frag], 15811541Srgrimes (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 15821541Srgrimes if (loc == 0) { 15831541Srgrimes len = start + 1; 15841541Srgrimes start = 0; 158558087Smckusick loc = scanc((u_int)len, (u_char *)&blksfree[0], 15861541Srgrimes (u_char *)fragtbl[fs->fs_frag], 15871541Srgrimes (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 15881541Srgrimes if (loc == 0) { 15891541Srgrimes printf("start = %d, len = %d, fs = %s\n", 15901541Srgrimes start, len, fs->fs_fsmnt); 15911541Srgrimes panic("ffs_alloccg: map corrupted"); 15921541Srgrimes /* NOTREACHED */ 15931541Srgrimes } 15941541Srgrimes } 15951541Srgrimes bno = (start + len - loc) * NBBY; 15961541Srgrimes cgp->cg_frotor = bno; 15971541Srgrimes /* 15981541Srgrimes * found the byte in the map 15991541Srgrimes * sift through the bits to find the selected frag 16001541Srgrimes */ 16011541Srgrimes for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 160258087Smckusick blk = blkmap(fs, blksfree, bno); 16031541Srgrimes blk <<= 1; 16041541Srgrimes field = around[allocsiz]; 16051541Srgrimes subfield = inside[allocsiz]; 16061541Srgrimes for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 16071541Srgrimes if ((blk & field) == subfield) 16081541Srgrimes return (bno + pos); 16091541Srgrimes field <<= 1; 16101541Srgrimes subfield <<= 1; 16111541Srgrimes } 16121541Srgrimes } 16133487Sphk printf("bno = %lu, fs = %s\n", (u_long)bno, fs->fs_fsmnt); 16141541Srgrimes panic("ffs_alloccg: block not in map"); 16151541Srgrimes return (-1); 16161541Srgrimes} 16171541Srgrimes 16181541Srgrimes/* 16191541Srgrimes * Update the cluster map because of an allocation or free. 16201541Srgrimes * 16211541Srgrimes * Cnt == 1 means free; cnt == -1 means allocating. 16221541Srgrimes */ 162312911Sphkstatic void 16241541Srgrimesffs_clusteracct(fs, cgp, blkno, cnt) 16251541Srgrimes struct fs *fs; 16261541Srgrimes struct cg *cgp; 162722521Sdyson ufs_daddr_t blkno; 16281541Srgrimes int cnt; 16291541Srgrimes{ 163022521Sdyson int32_t *sump; 163122521Sdyson int32_t *lp; 16321541Srgrimes u_char *freemapp, *mapp; 16331541Srgrimes int i, start, end, forw, back, map, bit; 16341541Srgrimes 16351541Srgrimes if (fs->fs_contigsumsize <= 0) 16361541Srgrimes return; 16371541Srgrimes freemapp = cg_clustersfree(cgp); 16381541Srgrimes sump = cg_clustersum(cgp); 16391541Srgrimes /* 16401541Srgrimes * Allocate or clear the actual block. 16411541Srgrimes */ 16421541Srgrimes if (cnt > 0) 16431541Srgrimes setbit(freemapp, blkno); 16441541Srgrimes else 16451541Srgrimes clrbit(freemapp, blkno); 16461541Srgrimes /* 16471541Srgrimes * Find the size of the cluster going forward. 16481541Srgrimes */ 16491541Srgrimes start = blkno + 1; 16501541Srgrimes end = start + fs->fs_contigsumsize; 16511541Srgrimes if (end >= cgp->cg_nclusterblks) 16521541Srgrimes end = cgp->cg_nclusterblks; 16531541Srgrimes mapp = &freemapp[start / NBBY]; 16541541Srgrimes map = *mapp++; 16551541Srgrimes bit = 1 << (start % NBBY); 16561541Srgrimes for (i = start; i < end; i++) { 16571541Srgrimes if ((map & bit) == 0) 16581541Srgrimes break; 16591541Srgrimes if ((i & (NBBY - 1)) != (NBBY - 1)) { 16601541Srgrimes bit <<= 1; 16611541Srgrimes } else { 16621541Srgrimes map = *mapp++; 16631541Srgrimes bit = 1; 16641541Srgrimes } 16651541Srgrimes } 16661541Srgrimes forw = i - start; 16671541Srgrimes /* 16681541Srgrimes * Find the size of the cluster going backward. 16691541Srgrimes */ 16701541Srgrimes start = blkno - 1; 16711541Srgrimes end = start - fs->fs_contigsumsize; 16721541Srgrimes if (end < 0) 16731541Srgrimes end = -1; 16741541Srgrimes mapp = &freemapp[start / NBBY]; 16751541Srgrimes map = *mapp--; 16761541Srgrimes bit = 1 << (start % NBBY); 16771541Srgrimes for (i = start; i > end; i--) { 16781541Srgrimes if ((map & bit) == 0) 16791541Srgrimes break; 16801541Srgrimes if ((i & (NBBY - 1)) != 0) { 16811541Srgrimes bit >>= 1; 16821541Srgrimes } else { 16831541Srgrimes map = *mapp--; 16841541Srgrimes bit = 1 << (NBBY - 1); 16851541Srgrimes } 16861541Srgrimes } 16871541Srgrimes back = start - i; 16881541Srgrimes /* 16891541Srgrimes * Account for old cluster and the possibly new forward and 16901541Srgrimes * back clusters. 16911541Srgrimes */ 16921541Srgrimes i = back + forw + 1; 16931541Srgrimes if (i > fs->fs_contigsumsize) 16941541Srgrimes i = fs->fs_contigsumsize; 16951541Srgrimes sump[i] += cnt; 16961541Srgrimes if (back > 0) 16971541Srgrimes sump[back] -= cnt; 16981541Srgrimes if (forw > 0) 16991541Srgrimes sump[forw] -= cnt; 170022521Sdyson /* 170122521Sdyson * Update cluster summary information. 170222521Sdyson */ 170322521Sdyson lp = &sump[fs->fs_contigsumsize]; 170422521Sdyson for (i = fs->fs_contigsumsize; i > 0; i--) 170522521Sdyson if (*lp-- > 0) 170622521Sdyson break; 170722521Sdyson fs->fs_maxcluster[cgp->cg_cgx] = i; 17081541Srgrimes} 17091541Srgrimes 17101541Srgrimes/* 17111541Srgrimes * Fserr prints the name of a file system with an error diagnostic. 17128876Srgrimes * 17131541Srgrimes * The form of the error message is: 17141541Srgrimes * fs: error message 17151541Srgrimes */ 17161541Srgrimesstatic void 17171541Srgrimesffs_fserr(fs, uid, cp) 17181541Srgrimes struct fs *fs; 17191541Srgrimes u_int uid; 17201541Srgrimes char *cp; 17211541Srgrimes{ 172218330Speter struct proc *p = curproc; /* XXX */ 17231541Srgrimes 172418330Speter log(LOG_ERR, "pid %d (%s), uid %d on %s: %s\n", p ? p->p_pid : -1, 172518330Speter p ? p->p_comm : "-", uid, fs->fs_fsmnt, cp); 17261541Srgrimes} 1727