ffs_alloc.c revision 37555
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 3437555Sbde * $Id: ffs_alloc.c,v 1.49 1998/03/30 09:55:50 phk 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 <ufs/ufs/quota.h> 501541Srgrimes#include <ufs/ufs/inode.h> 5130474Sphk#include <ufs/ufs/ufsmount.h> 521541Srgrimes 531541Srgrimes#include <ufs/ffs/fs.h> 541541Srgrimes#include <ufs/ffs/ffs_extern.h> 551541Srgrimes 5622521Sdysontypedef ufs_daddr_t allocfcn_t __P((struct inode *ip, int cg, ufs_daddr_t bpref, 5722521Sdyson int size)); 5812590Sbde 5922521Sdysonstatic ufs_daddr_t ffs_alloccg __P((struct inode *, int, ufs_daddr_t, int)); 6034266Sjulianstatic ufs_daddr_t 6134266Sjulian ffs_alloccgblk __P((struct inode *, struct buf *, ufs_daddr_t)); 6231352Sbde#ifdef DIAGNOSTIC 6331352Sbdestatic int ffs_checkblk __P((struct inode *, ufs_daddr_t, long)); 6431352Sbde#endif 6522521Sdysonstatic void ffs_clusteracct __P((struct fs *, struct cg *, ufs_daddr_t, 6622521Sdyson int)); 6731351Sbde#ifdef notyet 6831351Sbdestatic ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t, 6931351Sbde int)); 7031351Sbde#endif 711541Srgrimesstatic ino_t ffs_dirpref __P((struct fs *)); 7222521Sdysonstatic ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 731541Srgrimesstatic void ffs_fserr __P((struct fs *, u_int, char *)); 741541Srgrimesstatic u_long ffs_hashalloc 7512590Sbde __P((struct inode *, int, long, int, allocfcn_t *)); 7622521Sdysonstatic ino_t ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int)); 7722521Sdysonstatic ufs_daddr_t ffs_mapsearch __P((struct fs *, struct cg *, ufs_daddr_t, 7822521Sdyson int)); 791541Srgrimes 801541Srgrimes/* 811541Srgrimes * Allocate a block in the file system. 828876Srgrimes * 831541Srgrimes * The size of the requested block is given, which must be some 841541Srgrimes * multiple of fs_fsize and <= fs_bsize. 851541Srgrimes * A preference may be optionally specified. If a preference is given 861541Srgrimes * the following hierarchy is used to allocate a block: 871541Srgrimes * 1) allocate the requested block. 881541Srgrimes * 2) allocate a rotationally optimal block in the same cylinder. 891541Srgrimes * 3) allocate a block in the same cylinder group. 901541Srgrimes * 4) quadradically rehash into other cylinder groups, until an 911541Srgrimes * available block is located. 921541Srgrimes * If no block preference is given the following heirarchy is used 931541Srgrimes * to allocate a block: 941541Srgrimes * 1) allocate a block in the cylinder group that contains the 951541Srgrimes * inode for the file. 961541Srgrimes * 2) quadradically rehash into other cylinder groups, until an 971541Srgrimes * available block is located. 981541Srgrimes */ 991549Srgrimesint 1001541Srgrimesffs_alloc(ip, lbn, bpref, size, cred, bnp) 1011541Srgrimes register struct inode *ip; 10222521Sdyson ufs_daddr_t lbn, bpref; 1031541Srgrimes int size; 1041541Srgrimes struct ucred *cred; 10522521Sdyson ufs_daddr_t *bnp; 1061541Srgrimes{ 1071541Srgrimes register struct fs *fs; 10822521Sdyson ufs_daddr_t bno; 1096357Sphk int cg; 1106357Sphk#ifdef QUOTA 1116357Sphk int error; 1126357Sphk#endif 1138876Srgrimes 1141541Srgrimes *bnp = 0; 1151541Srgrimes fs = ip->i_fs; 1161541Srgrimes#ifdef DIAGNOSTIC 1171541Srgrimes if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1183487Sphk printf("dev = 0x%lx, bsize = %ld, size = %d, fs = %s\n", 11937555Sbde (u_long)ip->i_dev, (long)fs->fs_bsize, size, fs->fs_fsmnt); 1201541Srgrimes panic("ffs_alloc: bad size"); 1211541Srgrimes } 1221541Srgrimes if (cred == NOCRED) 1237170Sdg panic("ffs_alloc: missing credential"); 1241541Srgrimes#endif /* DIAGNOSTIC */ 1251541Srgrimes if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 1261541Srgrimes goto nospace; 12729609Sphk if (cred->cr_uid != 0 && 12829609Sphk freespace(fs, fs->fs_minfree) - numfrags(fs, size) < 0) 1291541Srgrimes goto nospace; 1301541Srgrimes#ifdef QUOTA 1313487Sphk error = chkdq(ip, (long)btodb(size), cred, 0); 1323487Sphk if (error) 1331541Srgrimes return (error); 1341541Srgrimes#endif 1351541Srgrimes if (bpref >= fs->fs_size) 1361541Srgrimes bpref = 0; 1371541Srgrimes if (bpref == 0) 1381541Srgrimes cg = ino_to_cg(fs, ip->i_number); 1391541Srgrimes else 1401541Srgrimes cg = dtog(fs, bpref); 14122521Sdyson bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 14222521Sdyson ffs_alloccg); 1431541Srgrimes if (bno > 0) { 1441541Srgrimes ip->i_blocks += btodb(size); 1451541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 1461541Srgrimes *bnp = bno; 1471541Srgrimes return (0); 1481541Srgrimes } 1491541Srgrimes#ifdef QUOTA 1501541Srgrimes /* 1511541Srgrimes * Restore user's disk quota because allocation failed. 1521541Srgrimes */ 1531541Srgrimes (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 1541541Srgrimes#endif 1551541Srgrimesnospace: 1561541Srgrimes ffs_fserr(fs, cred->cr_uid, "file system full"); 1571541Srgrimes uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 1581541Srgrimes return (ENOSPC); 1591541Srgrimes} 1601541Srgrimes 1611541Srgrimes/* 1621541Srgrimes * Reallocate a fragment to a bigger size 1631541Srgrimes * 1641541Srgrimes * The number and size of the old block is given, and a preference 1651541Srgrimes * and new size is also specified. The allocator attempts to extend 1661541Srgrimes * the original block. Failing that, the regular block allocator is 1671541Srgrimes * invoked to get an appropriate block. 1681541Srgrimes */ 1691549Srgrimesint 1701541Srgrimesffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp) 1711541Srgrimes register struct inode *ip; 17222521Sdyson ufs_daddr_t lbprev; 17322521Sdyson ufs_daddr_t bpref; 1741541Srgrimes int osize, nsize; 1751541Srgrimes struct ucred *cred; 1761541Srgrimes struct buf **bpp; 1771541Srgrimes{ 1781541Srgrimes register struct fs *fs; 1791541Srgrimes struct buf *bp; 1801541Srgrimes int cg, request, error; 18122521Sdyson ufs_daddr_t bprev, bno; 1828876Srgrimes 1831541Srgrimes *bpp = 0; 1841541Srgrimes fs = ip->i_fs; 1851541Srgrimes#ifdef DIAGNOSTIC 1861541Srgrimes if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 1871541Srgrimes (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 1881541Srgrimes printf( 18937555Sbde "dev = 0x%lx, bsize = %ld, osize = %d, nsize = %d, fs = %s\n", 19037555Sbde (u_long)ip->i_dev, (long)fs->fs_bsize, osize, 1918456Srgrimes nsize, fs->fs_fsmnt); 1921541Srgrimes panic("ffs_realloccg: bad size"); 1931541Srgrimes } 1941541Srgrimes if (cred == NOCRED) 1957170Sdg panic("ffs_realloccg: missing credential"); 1961541Srgrimes#endif /* DIAGNOSTIC */ 19729609Sphk if (cred->cr_uid != 0 && 19829609Sphk freespace(fs, fs->fs_minfree) - numfrags(fs, nsize - osize) < 0) 1991541Srgrimes goto nospace; 2001541Srgrimes if ((bprev = ip->i_db[lbprev]) == 0) { 2016357Sphk printf("dev = 0x%lx, bsize = %ld, bprev = %ld, fs = %s\n", 20237555Sbde (u_long)ip->i_dev, (long)fs->fs_bsize, (long)bprev, 20337555Sbde fs->fs_fsmnt); 2041541Srgrimes panic("ffs_realloccg: bad bprev"); 2051541Srgrimes } 2061541Srgrimes /* 2071541Srgrimes * Allocate the extra space in the buffer. 2081541Srgrimes */ 2093487Sphk error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp); 2103487Sphk if (error) { 2111541Srgrimes brelse(bp); 2121541Srgrimes return (error); 2131541Srgrimes } 2146864Sdg 2156864Sdg if( bp->b_blkno == bp->b_lblkno) { 2166864Sdg if( lbprev >= NDADDR) 2176864Sdg panic("ffs_realloccg: lbprev out of range"); 2186864Sdg bp->b_blkno = fsbtodb(fs, bprev); 2196864Sdg } 2208876Srgrimes 2211541Srgrimes#ifdef QUOTA 2223487Sphk error = chkdq(ip, (long)btodb(nsize - osize), cred, 0); 2233487Sphk if (error) { 2241541Srgrimes brelse(bp); 2251541Srgrimes return (error); 2261541Srgrimes } 2271541Srgrimes#endif 2281541Srgrimes /* 2291541Srgrimes * Check for extension in the existing location. 2301541Srgrimes */ 2311541Srgrimes cg = dtog(fs, bprev); 2323487Sphk bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize); 2333487Sphk if (bno) { 2341541Srgrimes if (bp->b_blkno != fsbtodb(fs, bno)) 23523560Smpp panic("ffs_realloccg: bad blockno"); 2361541Srgrimes ip->i_blocks += btodb(nsize - osize); 2371541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 2387399Sdg allocbuf(bp, nsize); 2391541Srgrimes bp->b_flags |= B_DONE; 2401541Srgrimes bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 2411541Srgrimes *bpp = bp; 2421541Srgrimes return (0); 2431541Srgrimes } 2441541Srgrimes /* 2451541Srgrimes * Allocate a new disk location. 2461541Srgrimes */ 2471541Srgrimes if (bpref >= fs->fs_size) 2481541Srgrimes bpref = 0; 2491541Srgrimes switch ((int)fs->fs_optim) { 2501541Srgrimes case FS_OPTSPACE: 2511541Srgrimes /* 2528876Srgrimes * Allocate an exact sized fragment. Although this makes 2538876Srgrimes * best use of space, we will waste time relocating it if 2541541Srgrimes * the file continues to grow. If the fragmentation is 2551541Srgrimes * less than half of the minimum free reserve, we choose 2561541Srgrimes * to begin optimizing for time. 2571541Srgrimes */ 2581541Srgrimes request = nsize; 2596993Sdg if (fs->fs_minfree <= 5 || 2601541Srgrimes fs->fs_cstotal.cs_nffree > 2611541Srgrimes fs->fs_dsize * fs->fs_minfree / (2 * 100)) 2621541Srgrimes break; 2631541Srgrimes log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 2641541Srgrimes fs->fs_fsmnt); 2651541Srgrimes fs->fs_optim = FS_OPTTIME; 2661541Srgrimes break; 2671541Srgrimes case FS_OPTTIME: 2681541Srgrimes /* 2691541Srgrimes * At this point we have discovered a file that is trying to 2701541Srgrimes * grow a small fragment to a larger fragment. To save time, 2711541Srgrimes * we allocate a full sized block, then free the unused portion. 2721541Srgrimes * If the file continues to grow, the `ffs_fragextend' call 2731541Srgrimes * above will be able to grow it in place without further 2741541Srgrimes * copying. If aberrant programs cause disk fragmentation to 2751541Srgrimes * grow within 2% of the free reserve, we choose to begin 2761541Srgrimes * optimizing for space. 2771541Srgrimes */ 2781541Srgrimes request = fs->fs_bsize; 2791541Srgrimes if (fs->fs_cstotal.cs_nffree < 2801541Srgrimes fs->fs_dsize * (fs->fs_minfree - 2) / 100) 2811541Srgrimes break; 2821541Srgrimes log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 2831541Srgrimes fs->fs_fsmnt); 2841541Srgrimes fs->fs_optim = FS_OPTSPACE; 2851541Srgrimes break; 2861541Srgrimes default: 2873487Sphk printf("dev = 0x%lx, optim = %ld, fs = %s\n", 28837555Sbde (u_long)ip->i_dev, (long)fs->fs_optim, fs->fs_fsmnt); 2891541Srgrimes panic("ffs_realloccg: bad optim"); 2901541Srgrimes /* NOTREACHED */ 2911541Srgrimes } 29222521Sdyson bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 29322521Sdyson ffs_alloccg); 2941541Srgrimes if (bno > 0) { 2951541Srgrimes bp->b_blkno = fsbtodb(fs, bno); 29634266Sjulian if (!DOINGSOFTDEP(ITOV(ip))) 29734266Sjulian ffs_blkfree(ip, bprev, (long)osize); 2981541Srgrimes if (nsize < request) 2991541Srgrimes ffs_blkfree(ip, bno + numfrags(fs, nsize), 3001541Srgrimes (long)(request - nsize)); 3011541Srgrimes ip->i_blocks += btodb(nsize - osize); 3021541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 3037399Sdg allocbuf(bp, nsize); 3041541Srgrimes bp->b_flags |= B_DONE; 3051541Srgrimes bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 3061541Srgrimes *bpp = bp; 3071541Srgrimes return (0); 3081541Srgrimes } 3091541Srgrimes#ifdef QUOTA 3101541Srgrimes /* 3111541Srgrimes * Restore user's disk quota because allocation failed. 3121541Srgrimes */ 3131541Srgrimes (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 3141541Srgrimes#endif 3151541Srgrimes brelse(bp); 3161541Srgrimesnospace: 3171541Srgrimes /* 3181541Srgrimes * no space available 3191541Srgrimes */ 3201541Srgrimes ffs_fserr(fs, cred->cr_uid, "file system full"); 3211541Srgrimes uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 3221541Srgrimes return (ENOSPC); 3231541Srgrimes} 3241541Srgrimes 32531351Sbde#ifdef notyet 3261541Srgrimes/* 3271541Srgrimes * Reallocate a sequence of blocks into a contiguous sequence of blocks. 3281541Srgrimes * 3291541Srgrimes * The vnode and an array of buffer pointers for a range of sequential 3301541Srgrimes * logical blocks to be made contiguous is given. The allocator attempts 3311541Srgrimes * to find a range of sequential blocks starting as close as possible to 3321541Srgrimes * an fs_rotdelay offset from the end of the allocation for the logical 3331541Srgrimes * block immediately preceeding the current range. If successful, the 3341541Srgrimes * physical block numbers in the buffer pointers and in the inode are 3351541Srgrimes * changed to reflect the new allocation. If unsuccessful, the allocation 3361541Srgrimes * is left unchanged. The success in doing the reallocation is returned. 3371541Srgrimes * Note that the error return is not reflected back to the user. Rather 3381541Srgrimes * the previous block allocation will be used. 3391541Srgrimes */ 34012911Sphkstatic int doasyncfree = 1; 34122521SdysonSYSCTL_INT(_vfs_ffs, FFS_ASYNCFREE, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, ""); 34222521Sdyson 34331352Sbdestatic int doreallocblks = 1; 34422521SdysonSYSCTL_INT(_vfs_ffs, FFS_REALLOCBLKS, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, ""); 34522521Sdyson 34631351Sbdestatic int prtrealloc = 0; 34731351Sbde#endif 34831351Sbde 3491541Srgrimesint 3501541Srgrimesffs_reallocblks(ap) 3511541Srgrimes struct vop_reallocblks_args /* { 3521541Srgrimes struct vnode *a_vp; 3531541Srgrimes struct cluster_save *a_buflist; 3541541Srgrimes } */ *ap; 3551541Srgrimes{ 35612911Sphk#if !defined (not_yes) 35712405Sdyson return (ENOSPC); 35812405Sdyson#else 3591541Srgrimes struct fs *fs; 3601541Srgrimes struct inode *ip; 3611541Srgrimes struct vnode *vp; 3621541Srgrimes struct buf *sbp, *ebp; 36322521Sdyson ufs_daddr_t *bap, *sbap, *ebap = 0; 3641541Srgrimes struct cluster_save *buflist; 36522521Sdyson ufs_daddr_t start_lbn, end_lbn, soff, newblk, blkno; 3661541Srgrimes struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 3671541Srgrimes int i, len, start_lvl, end_lvl, pref, ssize; 36810269Sbde struct timeval tv; 3691541Srgrimes 37022521Sdyson if (doreallocblks == 0) 37122521Sdyson return (ENOSPC); 3721541Srgrimes vp = ap->a_vp; 3731541Srgrimes ip = VTOI(vp); 3741541Srgrimes fs = ip->i_fs; 3751541Srgrimes if (fs->fs_contigsumsize <= 0) 3761541Srgrimes return (ENOSPC); 3771541Srgrimes buflist = ap->a_buflist; 3781541Srgrimes len = buflist->bs_nchildren; 3791541Srgrimes start_lbn = buflist->bs_children[0]->b_lblkno; 3801541Srgrimes end_lbn = start_lbn + len - 1; 3811541Srgrimes#ifdef DIAGNOSTIC 38222521Sdyson for (i = 0; i < len; i++) 38322521Sdyson if (!ffs_checkblk(ip, 38422521Sdyson dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 38522521Sdyson panic("ffs_reallocblks: unallocated block 1"); 3861541Srgrimes for (i = 1; i < len; i++) 3871541Srgrimes if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 38822521Sdyson panic("ffs_reallocblks: non-logical cluster"); 38922521Sdyson blkno = buflist->bs_children[0]->b_blkno; 39022521Sdyson ssize = fsbtodb(fs, fs->fs_frag); 39122521Sdyson for (i = 1; i < len - 1; i++) 39222521Sdyson if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize)) 39322521Sdyson panic("ffs_reallocblks: non-physical cluster %d", i); 3941541Srgrimes#endif 3951541Srgrimes /* 3961541Srgrimes * If the latest allocation is in a new cylinder group, assume that 3971541Srgrimes * the filesystem has decided to move and do not force it back to 3981541Srgrimes * the previous cylinder group. 3991541Srgrimes */ 4001541Srgrimes if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 4011541Srgrimes dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 4021541Srgrimes return (ENOSPC); 4031541Srgrimes if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 4041541Srgrimes ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 4051541Srgrimes return (ENOSPC); 4061541Srgrimes /* 4071541Srgrimes * Get the starting offset and block map for the first block. 4081541Srgrimes */ 4091541Srgrimes if (start_lvl == 0) { 4101541Srgrimes sbap = &ip->i_db[0]; 4111541Srgrimes soff = start_lbn; 4121541Srgrimes } else { 4131541Srgrimes idp = &start_ap[start_lvl - 1]; 4141541Srgrimes if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 4151541Srgrimes brelse(sbp); 4161541Srgrimes return (ENOSPC); 4171541Srgrimes } 41822521Sdyson sbap = (ufs_daddr_t *)sbp->b_data; 4191541Srgrimes soff = idp->in_off; 4201541Srgrimes } 4211541Srgrimes /* 4221541Srgrimes * Find the preferred location for the cluster. 4231541Srgrimes */ 4241541Srgrimes pref = ffs_blkpref(ip, start_lbn, soff, sbap); 4251541Srgrimes /* 4261541Srgrimes * If the block range spans two block maps, get the second map. 4271541Srgrimes */ 4281541Srgrimes if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 4291541Srgrimes ssize = len; 4301541Srgrimes } else { 4311541Srgrimes#ifdef DIAGNOSTIC 4321541Srgrimes if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 4331541Srgrimes panic("ffs_reallocblk: start == end"); 4341541Srgrimes#endif 4351541Srgrimes ssize = len - (idp->in_off + 1); 4361541Srgrimes if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 4371541Srgrimes goto fail; 43822521Sdyson ebap = (ufs_daddr_t *)ebp->b_data; 4391541Srgrimes } 4401541Srgrimes /* 4411541Srgrimes * Search the block map looking for an allocation of the desired size. 4421541Srgrimes */ 44322521Sdyson if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref, 44412590Sbde len, ffs_clusteralloc)) == 0) 4451541Srgrimes goto fail; 4461541Srgrimes /* 4471541Srgrimes * We have found a new contiguous block. 4481541Srgrimes * 4491541Srgrimes * First we have to replace the old block pointers with the new 4501541Srgrimes * block pointers in the inode and indirect blocks associated 4511541Srgrimes * with the file. 4521541Srgrimes */ 45322521Sdyson#ifdef DEBUG 45422521Sdyson if (prtrealloc) 45522521Sdyson printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number, 45622521Sdyson start_lbn, end_lbn); 45722521Sdyson#endif 4581541Srgrimes blkno = newblk; 4591541Srgrimes for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 46034266Sjulian if (i == ssize) { 4611541Srgrimes bap = ebap; 46234266Sjulian soff = -i; 46334266Sjulian } 4641541Srgrimes#ifdef DIAGNOSTIC 46522521Sdyson if (!ffs_checkblk(ip, 46622521Sdyson dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 46722521Sdyson panic("ffs_reallocblks: unallocated block 2"); 46822521Sdyson if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap) 4691541Srgrimes panic("ffs_reallocblks: alloc mismatch"); 4701541Srgrimes#endif 47122521Sdyson#ifdef DEBUG 47222521Sdyson if (prtrealloc) 47322521Sdyson printf(" %d,", *bap); 47422521Sdyson#endif 47534266Sjulian if (DOINGSOFTDEP(vp)) { 47634266Sjulian if (sbap == &ip->i_db[0] && i < ssize) 47734266Sjulian softdep_setup_allocdirect(ip, start_lbn + i, 47834266Sjulian blkno, *bap, fs->fs_bsize, fs->fs_bsize, 47934266Sjulian buflist->bs_children[i]); 48034266Sjulian else 48134266Sjulian softdep_setup_allocindir_page(ip, start_lbn + i, 48234266Sjulian i < ssize ? sbp : ebp, soff + i, blkno, 48334266Sjulian *bap, buflist->bs_children[i]); 48434266Sjulian } 4851541Srgrimes *bap++ = blkno; 4861541Srgrimes } 4871541Srgrimes /* 4881541Srgrimes * Next we must write out the modified inode and indirect blocks. 4891541Srgrimes * For strict correctness, the writes should be synchronous since 4901541Srgrimes * the old block values may have been written to disk. In practise 4918876Srgrimes * they are almost never written, but if we are concerned about 4921541Srgrimes * strict correctness, the `doasyncfree' flag should be set to zero. 4931541Srgrimes * 4941541Srgrimes * The test on `doasyncfree' should be changed to test a flag 4951541Srgrimes * that shows whether the associated buffers and inodes have 4961541Srgrimes * been written. The flag should be set when the cluster is 4971541Srgrimes * started and cleared whenever the buffer or inode is flushed. 4981541Srgrimes * We can then check below to see if it is set, and do the 4991541Srgrimes * synchronous write only when it has been cleared. 5001541Srgrimes */ 5011541Srgrimes if (sbap != &ip->i_db[0]) { 5021541Srgrimes if (doasyncfree) 5031541Srgrimes bdwrite(sbp); 5041541Srgrimes else 5051541Srgrimes bwrite(sbp); 5061541Srgrimes } else { 5071541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 50810269Sbde if (!doasyncfree) { 50924101Sbde gettime(&tv); 51030492Sphk UFS_UPDATE(vp, &tv, &tv, 1); 51110269Sbde } 5121541Srgrimes } 5131541Srgrimes if (ssize < len) 5141541Srgrimes if (doasyncfree) 5151541Srgrimes bdwrite(ebp); 5161541Srgrimes else 5171541Srgrimes bwrite(ebp); 5181541Srgrimes /* 5191541Srgrimes * Last, free the old blocks and assign the new blocks to the buffers. 5201541Srgrimes */ 52122521Sdyson#ifdef DEBUG 52222521Sdyson if (prtrealloc) 52322521Sdyson printf("\n\tnew:"); 52422521Sdyson#endif 5251541Srgrimes for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 52634266Sjulian if (!DOINGSOFTDEP(vp)) 52734266Sjulian ffs_blkfree(ip, 52834266Sjulian dbtofsb(fs, buflist->bs_children[i]->b_blkno), 52934266Sjulian fs->fs_bsize); 5301541Srgrimes buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 53122521Sdyson#ifdef DEBUG 53222521Sdyson if (!ffs_checkblk(ip, 53322521Sdyson dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 53422521Sdyson panic("ffs_reallocblks: unallocated block 3"); 53522521Sdyson if (prtrealloc) 53622521Sdyson printf(" %d,", blkno); 53722521Sdyson#endif 5381541Srgrimes } 53922521Sdyson#ifdef DEBUG 54022521Sdyson if (prtrealloc) { 54122521Sdyson prtrealloc--; 54222521Sdyson printf("\n"); 54322521Sdyson } 54422521Sdyson#endif 5451541Srgrimes return (0); 5461541Srgrimes 5471541Srgrimesfail: 5481541Srgrimes if (ssize < len) 5491541Srgrimes brelse(ebp); 5501541Srgrimes if (sbap != &ip->i_db[0]) 5511541Srgrimes brelse(sbp); 5521541Srgrimes return (ENOSPC); 55312405Sdyson#endif 5541541Srgrimes} 5551541Srgrimes 5561541Srgrimes/* 5571541Srgrimes * Allocate an inode in the file system. 5588876Srgrimes * 5591541Srgrimes * If allocating a directory, use ffs_dirpref to select the inode. 5601541Srgrimes * If allocating in a directory, the following hierarchy is followed: 5611541Srgrimes * 1) allocate the preferred inode. 5621541Srgrimes * 2) allocate an inode in the same cylinder group. 5631541Srgrimes * 3) quadradically rehash into other cylinder groups, until an 5641541Srgrimes * available inode is located. 5651541Srgrimes * If no inode preference is given the following heirarchy is used 5661541Srgrimes * to allocate an inode: 5671541Srgrimes * 1) allocate an inode in cylinder group 0. 5681541Srgrimes * 2) quadradically rehash into other cylinder groups, until an 5691541Srgrimes * available inode is located. 5701541Srgrimes */ 5711549Srgrimesint 57230474Sphkffs_valloc(pvp, mode, cred, vpp) 57330474Sphk struct vnode *pvp; 57430474Sphk int mode; 57530474Sphk struct ucred *cred; 57630474Sphk struct vnode **vpp; 5771541Srgrimes{ 5781541Srgrimes register struct inode *pip; 5791541Srgrimes register struct fs *fs; 5801541Srgrimes register struct inode *ip; 5811541Srgrimes ino_t ino, ipref; 5821541Srgrimes int cg, error; 5838876Srgrimes 58430474Sphk *vpp = NULL; 5851541Srgrimes pip = VTOI(pvp); 5861541Srgrimes fs = pip->i_fs; 5871541Srgrimes if (fs->fs_cstotal.cs_nifree == 0) 5881541Srgrimes goto noinodes; 5891541Srgrimes 5901541Srgrimes if ((mode & IFMT) == IFDIR) 5911541Srgrimes ipref = ffs_dirpref(fs); 5921541Srgrimes else 5931541Srgrimes ipref = pip->i_number; 5941541Srgrimes if (ipref >= fs->fs_ncg * fs->fs_ipg) 5951541Srgrimes ipref = 0; 5961541Srgrimes cg = ino_to_cg(fs, ipref); 59712861Speter ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, 59812861Speter (allocfcn_t *)ffs_nodealloccg); 5991541Srgrimes if (ino == 0) 6001541Srgrimes goto noinodes; 60130474Sphk error = VFS_VGET(pvp->v_mount, ino, vpp); 6021541Srgrimes if (error) { 60330474Sphk UFS_VFREE(pvp, ino, mode); 6041541Srgrimes return (error); 6051541Srgrimes } 60630474Sphk ip = VTOI(*vpp); 6071541Srgrimes if (ip->i_mode) { 60837555Sbde printf("mode = 0%o, inum = %lu, fs = %s\n", 60937555Sbde ip->i_mode, (u_long)ip->i_number, fs->fs_fsmnt); 6101541Srgrimes panic("ffs_valloc: dup alloc"); 6111541Srgrimes } 6121541Srgrimes if (ip->i_blocks) { /* XXX */ 61337555Sbde printf("free inode %s/%lu had %ld blocks\n", 61437555Sbde fs->fs_fsmnt, (u_long)ino, (long)ip->i_blocks); 6151541Srgrimes ip->i_blocks = 0; 6161541Srgrimes } 6171541Srgrimes ip->i_flags = 0; 6181541Srgrimes /* 6191541Srgrimes * Set up a new generation number for this inode. 6201541Srgrimes */ 62131484Sbde if (ip->i_gen == 0 || ++ip->i_gen == 0) 62224149Sguido ip->i_gen = random() / 2 + 1; 6231541Srgrimes return (0); 6241541Srgrimesnoinodes: 62530474Sphk ffs_fserr(fs, cred->cr_uid, "out of inodes"); 6261541Srgrimes uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 6271541Srgrimes return (ENOSPC); 6281541Srgrimes} 6291541Srgrimes 6301541Srgrimes/* 6311541Srgrimes * Find a cylinder to place a directory. 6321541Srgrimes * 6331541Srgrimes * The policy implemented by this algorithm is to select from 6341541Srgrimes * among those cylinder groups with above the average number of 6351541Srgrimes * free inodes, the one with the smallest number of directories. 6361541Srgrimes */ 6371541Srgrimesstatic ino_t 6381541Srgrimesffs_dirpref(fs) 6391541Srgrimes register struct fs *fs; 6401541Srgrimes{ 6411541Srgrimes int cg, minndir, mincg, avgifree; 6421541Srgrimes 6431541Srgrimes avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 6441541Srgrimes minndir = fs->fs_ipg; 6451541Srgrimes mincg = 0; 6461541Srgrimes for (cg = 0; cg < fs->fs_ncg; cg++) 6471541Srgrimes if (fs->fs_cs(fs, cg).cs_ndir < minndir && 6481541Srgrimes fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 6491541Srgrimes mincg = cg; 6501541Srgrimes minndir = fs->fs_cs(fs, cg).cs_ndir; 6511541Srgrimes } 6521541Srgrimes return ((ino_t)(fs->fs_ipg * mincg)); 6531541Srgrimes} 6541541Srgrimes 6551541Srgrimes/* 6561541Srgrimes * Select the desired position for the next block in a file. The file is 6571541Srgrimes * logically divided into sections. The first section is composed of the 6581541Srgrimes * direct blocks. Each additional section contains fs_maxbpg blocks. 6598876Srgrimes * 6601541Srgrimes * If no blocks have been allocated in the first section, the policy is to 6611541Srgrimes * request a block in the same cylinder group as the inode that describes 6621541Srgrimes * the file. If no blocks have been allocated in any other section, the 6631541Srgrimes * policy is to place the section in a cylinder group with a greater than 6641541Srgrimes * average number of free blocks. An appropriate cylinder group is found 6651541Srgrimes * by using a rotor that sweeps the cylinder groups. When a new group of 6661541Srgrimes * blocks is needed, the sweep begins in the cylinder group following the 6671541Srgrimes * cylinder group from which the previous allocation was made. The sweep 6681541Srgrimes * continues until a cylinder group with greater than the average number 6691541Srgrimes * of free blocks is found. If the allocation is for the first block in an 6701541Srgrimes * indirect block, the information on the previous allocation is unavailable; 6711541Srgrimes * here a best guess is made based upon the logical block number being 6721541Srgrimes * allocated. 6738876Srgrimes * 6741541Srgrimes * If a section is already partially allocated, the policy is to 6751541Srgrimes * contiguously allocate fs_maxcontig blocks. The end of one of these 6761541Srgrimes * contiguous blocks and the beginning of the next is physically separated 6771541Srgrimes * so that the disk head will be in transit between them for at least 6781541Srgrimes * fs_rotdelay milliseconds. This is to allow time for the processor to 6791541Srgrimes * schedule another I/O transfer. 6801541Srgrimes */ 68122521Sdysonufs_daddr_t 6821541Srgrimesffs_blkpref(ip, lbn, indx, bap) 6831541Srgrimes struct inode *ip; 68422521Sdyson ufs_daddr_t lbn; 6851541Srgrimes int indx; 68622521Sdyson ufs_daddr_t *bap; 6871541Srgrimes{ 6881541Srgrimes register struct fs *fs; 6891541Srgrimes register int cg; 6901541Srgrimes int avgbfree, startcg; 69122521Sdyson ufs_daddr_t nextblk; 6921541Srgrimes 6931541Srgrimes fs = ip->i_fs; 6941541Srgrimes if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 6951541Srgrimes if (lbn < NDADDR) { 6961541Srgrimes cg = ino_to_cg(fs, ip->i_number); 6971541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 6981541Srgrimes } 6991541Srgrimes /* 7001541Srgrimes * Find a cylinder with greater than average number of 7011541Srgrimes * unused data blocks. 7021541Srgrimes */ 7031541Srgrimes if (indx == 0 || bap[indx - 1] == 0) 7041541Srgrimes startcg = 7051541Srgrimes ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 7061541Srgrimes else 7071541Srgrimes startcg = dtog(fs, bap[indx - 1]) + 1; 7081541Srgrimes startcg %= fs->fs_ncg; 7091541Srgrimes avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 7101541Srgrimes for (cg = startcg; cg < fs->fs_ncg; cg++) 7111541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 7121541Srgrimes fs->fs_cgrotor = cg; 7131541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 7141541Srgrimes } 7151541Srgrimes for (cg = 0; cg <= startcg; cg++) 7161541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 7171541Srgrimes fs->fs_cgrotor = cg; 7181541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 7191541Srgrimes } 72017108Sbde return (0); 7211541Srgrimes } 7221541Srgrimes /* 7231541Srgrimes * One or more previous blocks have been laid out. If less 7241541Srgrimes * than fs_maxcontig previous blocks are contiguous, the 7251541Srgrimes * next block is requested contiguously, otherwise it is 7261541Srgrimes * requested rotationally delayed by fs_rotdelay milliseconds. 7271541Srgrimes */ 7281541Srgrimes nextblk = bap[indx - 1] + fs->fs_frag; 72910632Sdg if (fs->fs_rotdelay == 0 || indx < fs->fs_maxcontig || 73010632Sdg bap[indx - fs->fs_maxcontig] + 7311541Srgrimes blkstofrags(fs, fs->fs_maxcontig) != nextblk) 7321541Srgrimes return (nextblk); 73310632Sdg /* 73410632Sdg * Here we convert ms of delay to frags as: 73510632Sdg * (frags) = (ms) * (rev/sec) * (sect/rev) / 73610632Sdg * ((sect/frag) * (ms/sec)) 73710632Sdg * then round up to the next block. 73810632Sdg */ 73910632Sdg nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 74010632Sdg (NSPF(fs) * 1000), fs->fs_frag); 7411541Srgrimes return (nextblk); 7421541Srgrimes} 7431541Srgrimes 7441541Srgrimes/* 7451541Srgrimes * Implement the cylinder overflow algorithm. 7461541Srgrimes * 7471541Srgrimes * The policy implemented by this algorithm is: 7481541Srgrimes * 1) allocate the block in its requested cylinder group. 7491541Srgrimes * 2) quadradically rehash on the cylinder group number. 7501541Srgrimes * 3) brute force search for a free block. 7511541Srgrimes */ 7521541Srgrimes/*VARARGS5*/ 7531541Srgrimesstatic u_long 7541541Srgrimesffs_hashalloc(ip, cg, pref, size, allocator) 7551541Srgrimes struct inode *ip; 7561541Srgrimes int cg; 7571541Srgrimes long pref; 7581541Srgrimes int size; /* size for data blocks, mode for inodes */ 75912590Sbde allocfcn_t *allocator; 7601541Srgrimes{ 7611541Srgrimes register struct fs *fs; 76212590Sbde long result; /* XXX why not same type as we return? */ 7631541Srgrimes int i, icg = cg; 7641541Srgrimes 7651541Srgrimes fs = ip->i_fs; 7661541Srgrimes /* 7671541Srgrimes * 1: preferred cylinder group 7681541Srgrimes */ 7691541Srgrimes result = (*allocator)(ip, cg, pref, size); 7701541Srgrimes if (result) 7711541Srgrimes return (result); 7721541Srgrimes /* 7731541Srgrimes * 2: quadratic rehash 7741541Srgrimes */ 7751541Srgrimes for (i = 1; i < fs->fs_ncg; i *= 2) { 7761541Srgrimes cg += i; 7771541Srgrimes if (cg >= fs->fs_ncg) 7781541Srgrimes cg -= fs->fs_ncg; 7791541Srgrimes result = (*allocator)(ip, cg, 0, size); 7801541Srgrimes if (result) 7811541Srgrimes return (result); 7821541Srgrimes } 7831541Srgrimes /* 7841541Srgrimes * 3: brute force search 7851541Srgrimes * Note that we start at i == 2, since 0 was checked initially, 7861541Srgrimes * and 1 is always checked in the quadratic rehash. 7871541Srgrimes */ 7881541Srgrimes cg = (icg + 2) % fs->fs_ncg; 7891541Srgrimes for (i = 2; i < fs->fs_ncg; i++) { 7901541Srgrimes result = (*allocator)(ip, cg, 0, size); 7911541Srgrimes if (result) 7921541Srgrimes return (result); 7931541Srgrimes cg++; 7941541Srgrimes if (cg == fs->fs_ncg) 7951541Srgrimes cg = 0; 7961541Srgrimes } 79712590Sbde return (0); 7981541Srgrimes} 7991541Srgrimes 8001541Srgrimes/* 8011541Srgrimes * Determine whether a fragment can be extended. 8021541Srgrimes * 8038876Srgrimes * Check to see if the necessary fragments are available, and 8041541Srgrimes * if they are, allocate them. 8051541Srgrimes */ 80622521Sdysonstatic ufs_daddr_t 8071541Srgrimesffs_fragextend(ip, cg, bprev, osize, nsize) 8081541Srgrimes struct inode *ip; 8091541Srgrimes int cg; 8101541Srgrimes long bprev; 8111541Srgrimes int osize, nsize; 8121541Srgrimes{ 8131541Srgrimes register struct fs *fs; 8141541Srgrimes register struct cg *cgp; 8151541Srgrimes struct buf *bp; 8161541Srgrimes long bno; 8171541Srgrimes int frags, bbase; 8181541Srgrimes int i, error; 8191541Srgrimes 8201541Srgrimes fs = ip->i_fs; 8211541Srgrimes if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 82217108Sbde return (0); 8231541Srgrimes frags = numfrags(fs, nsize); 8241541Srgrimes bbase = fragnum(fs, bprev); 8251541Srgrimes if (bbase > fragnum(fs, (bprev + frags - 1))) { 8261541Srgrimes /* cannot extend across a block boundary */ 82717108Sbde return (0); 8281541Srgrimes } 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 brelse(bp); 83817108Sbde return (0); 8391541Srgrimes } 84034961Sphk cgp->cg_time = time_second; 8411541Srgrimes bno = dtogd(fs, bprev); 8421541Srgrimes for (i = numfrags(fs, osize); i < frags; i++) 8431541Srgrimes if (isclr(cg_blksfree(cgp), bno + i)) { 8441541Srgrimes brelse(bp); 84517108Sbde return (0); 8461541Srgrimes } 8471541Srgrimes /* 8481541Srgrimes * the current fragment can be extended 8491541Srgrimes * deduct the count on fragment being extended into 8501541Srgrimes * increase the count on the remaining fragment (if any) 8511541Srgrimes * allocate the extended piece 8521541Srgrimes */ 8531541Srgrimes for (i = frags; i < fs->fs_frag - bbase; i++) 8541541Srgrimes if (isclr(cg_blksfree(cgp), bno + i)) 8551541Srgrimes break; 8561541Srgrimes cgp->cg_frsum[i - numfrags(fs, osize)]--; 8571541Srgrimes if (i != frags) 8581541Srgrimes cgp->cg_frsum[i - frags]++; 8591541Srgrimes for (i = numfrags(fs, osize); i < frags; i++) { 8601541Srgrimes clrbit(cg_blksfree(cgp), bno + i); 8611541Srgrimes cgp->cg_cs.cs_nffree--; 8621541Srgrimes fs->fs_cstotal.cs_nffree--; 8631541Srgrimes fs->fs_cs(fs, cg).cs_nffree--; 8641541Srgrimes } 8651541Srgrimes fs->fs_fmod = 1; 86634266Sjulian if (DOINGSOFTDEP(ITOV(ip))) 86734266Sjulian softdep_setup_blkmapdep(bp, fs, bprev); 8681541Srgrimes bdwrite(bp); 8691541Srgrimes return (bprev); 8701541Srgrimes} 8711541Srgrimes 8721541Srgrimes/* 8731541Srgrimes * Determine whether a block can be allocated. 8741541Srgrimes * 8751541Srgrimes * Check to see if a block of the appropriate size is available, 8761541Srgrimes * and if it is, allocate it. 8771541Srgrimes */ 87822521Sdysonstatic ufs_daddr_t 8791541Srgrimesffs_alloccg(ip, cg, bpref, size) 8801541Srgrimes struct inode *ip; 8811541Srgrimes int cg; 88222521Sdyson ufs_daddr_t bpref; 8831541Srgrimes int size; 8841541Srgrimes{ 8851541Srgrimes register struct fs *fs; 8861541Srgrimes register struct cg *cgp; 8871541Srgrimes struct buf *bp; 8881541Srgrimes register int i; 88934266Sjulian ufs_daddr_t bno, blkno; 89034266Sjulian int allocsiz, error, frags; 8911541Srgrimes 8921541Srgrimes fs = ip->i_fs; 8931541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 89417108Sbde return (0); 8951541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 8961541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 8971541Srgrimes if (error) { 8981541Srgrimes brelse(bp); 89917108Sbde return (0); 9001541Srgrimes } 9011541Srgrimes cgp = (struct cg *)bp->b_data; 9021541Srgrimes if (!cg_chkmagic(cgp) || 9031541Srgrimes (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 9041541Srgrimes brelse(bp); 90517108Sbde return (0); 9061541Srgrimes } 90734961Sphk cgp->cg_time = time_second; 9081541Srgrimes if (size == fs->fs_bsize) { 90934266Sjulian bno = ffs_alloccgblk(ip, bp, bpref); 9101541Srgrimes bdwrite(bp); 9111541Srgrimes return (bno); 9121541Srgrimes } 9131541Srgrimes /* 9141541Srgrimes * check to see if any fragments are already available 9151541Srgrimes * allocsiz is the size which will be allocated, hacking 9161541Srgrimes * it down to a smaller size if necessary 9171541Srgrimes */ 9181541Srgrimes frags = numfrags(fs, size); 9191541Srgrimes for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 9201541Srgrimes if (cgp->cg_frsum[allocsiz] != 0) 9211541Srgrimes break; 9221541Srgrimes if (allocsiz == fs->fs_frag) { 9231541Srgrimes /* 9248876Srgrimes * no fragments were available, so a block will be 9251541Srgrimes * allocated, and hacked up 9261541Srgrimes */ 9271541Srgrimes if (cgp->cg_cs.cs_nbfree == 0) { 9281541Srgrimes brelse(bp); 92917108Sbde return (0); 9301541Srgrimes } 93134266Sjulian bno = ffs_alloccgblk(ip, bp, bpref); 9321541Srgrimes bpref = dtogd(fs, bno); 9331541Srgrimes for (i = frags; i < fs->fs_frag; i++) 9341541Srgrimes setbit(cg_blksfree(cgp), bpref + i); 9351541Srgrimes i = fs->fs_frag - frags; 9361541Srgrimes cgp->cg_cs.cs_nffree += i; 9371541Srgrimes fs->fs_cstotal.cs_nffree += i; 9381541Srgrimes fs->fs_cs(fs, cg).cs_nffree += i; 9391541Srgrimes fs->fs_fmod = 1; 9401541Srgrimes cgp->cg_frsum[i]++; 9411541Srgrimes bdwrite(bp); 9421541Srgrimes return (bno); 9431541Srgrimes } 9441541Srgrimes bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 9451541Srgrimes if (bno < 0) { 9461541Srgrimes brelse(bp); 94717108Sbde return (0); 9481541Srgrimes } 9491541Srgrimes for (i = 0; i < frags; i++) 9501541Srgrimes clrbit(cg_blksfree(cgp), bno + i); 9511541Srgrimes cgp->cg_cs.cs_nffree -= frags; 9521541Srgrimes fs->fs_cstotal.cs_nffree -= frags; 9531541Srgrimes fs->fs_cs(fs, cg).cs_nffree -= frags; 9541541Srgrimes fs->fs_fmod = 1; 9551541Srgrimes cgp->cg_frsum[allocsiz]--; 9561541Srgrimes if (frags != allocsiz) 9571541Srgrimes cgp->cg_frsum[allocsiz - frags]++; 95834266Sjulian blkno = cg * fs->fs_fpg + bno; 95934266Sjulian if (DOINGSOFTDEP(ITOV(ip))) 96034266Sjulian softdep_setup_blkmapdep(bp, fs, blkno); 9611541Srgrimes bdwrite(bp); 96234266Sjulian return ((u_long)blkno); 9631541Srgrimes} 9641541Srgrimes 9651541Srgrimes/* 9661541Srgrimes * Allocate a block in a cylinder group. 9671541Srgrimes * 9681541Srgrimes * This algorithm implements the following policy: 9691541Srgrimes * 1) allocate the requested block. 9701541Srgrimes * 2) allocate a rotationally optimal block in the same cylinder. 9711541Srgrimes * 3) allocate the next available block on the block rotor for the 9721541Srgrimes * specified cylinder group. 9731541Srgrimes * Note that this routine only allocates fs_bsize blocks; these 9741541Srgrimes * blocks may be fragmented by the routine that allocates them. 9751541Srgrimes */ 97622521Sdysonstatic ufs_daddr_t 97734266Sjulianffs_alloccgblk(ip, bp, bpref) 97834266Sjulian struct inode *ip; 97934266Sjulian struct buf *bp; 98022521Sdyson ufs_daddr_t bpref; 9811541Srgrimes{ 98234266Sjulian struct fs *fs; 98334266Sjulian struct cg *cgp; 98422521Sdyson ufs_daddr_t bno, blkno; 9851541Srgrimes int cylno, pos, delta; 9861541Srgrimes short *cylbp; 9871541Srgrimes register int i; 9881541Srgrimes 98934266Sjulian fs = ip->i_fs; 99034266Sjulian cgp = (struct cg *)bp->b_data; 9911541Srgrimes if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) { 9921541Srgrimes bpref = cgp->cg_rotor; 9931541Srgrimes goto norot; 9941541Srgrimes } 9951541Srgrimes bpref = blknum(fs, bpref); 9961541Srgrimes bpref = dtogd(fs, bpref); 9971541Srgrimes /* 9981541Srgrimes * if the requested block is available, use it 9991541Srgrimes */ 10001541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) { 10011541Srgrimes bno = bpref; 10021541Srgrimes goto gotit; 10031541Srgrimes } 10046769Sse if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) { 10051541Srgrimes /* 10061541Srgrimes * Block layout information is not available. 10071541Srgrimes * Leaving bpref unchanged means we take the 10088876Srgrimes * next available free block following the one 10091541Srgrimes * we just allocated. Hopefully this will at 10101541Srgrimes * least hit a track cache on drives of unknown 10111541Srgrimes * geometry (e.g. SCSI). 10121541Srgrimes */ 10131541Srgrimes goto norot; 10141541Srgrimes } 10151541Srgrimes /* 10166769Sse * check for a block available on the same cylinder 10176769Sse */ 10186769Sse cylno = cbtocylno(fs, bpref); 10196769Sse if (cg_blktot(cgp)[cylno] == 0) 10206769Sse goto norot; 10216769Sse /* 10228876Srgrimes * check the summary information to see if a block is 10231541Srgrimes * available in the requested cylinder starting at the 10241541Srgrimes * requested rotational position and proceeding around. 10251541Srgrimes */ 10261541Srgrimes cylbp = cg_blks(fs, cgp, cylno); 10271541Srgrimes pos = cbtorpos(fs, bpref); 10281541Srgrimes for (i = pos; i < fs->fs_nrpos; i++) 10291541Srgrimes if (cylbp[i] > 0) 10301541Srgrimes break; 10311541Srgrimes if (i == fs->fs_nrpos) 10321541Srgrimes for (i = 0; i < pos; i++) 10331541Srgrimes if (cylbp[i] > 0) 10341541Srgrimes break; 10351541Srgrimes if (cylbp[i] > 0) { 10361541Srgrimes /* 10371541Srgrimes * found a rotational position, now find the actual 10381541Srgrimes * block. A panic if none is actually there. 10391541Srgrimes */ 10401541Srgrimes pos = cylno % fs->fs_cpc; 10411541Srgrimes bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 10421541Srgrimes if (fs_postbl(fs, pos)[i] == -1) { 10431541Srgrimes printf("pos = %d, i = %d, fs = %s\n", 10441541Srgrimes pos, i, fs->fs_fsmnt); 10451541Srgrimes panic("ffs_alloccgblk: cyl groups corrupted"); 10461541Srgrimes } 10471541Srgrimes for (i = fs_postbl(fs, pos)[i];; ) { 10481541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), bno + i)) { 10491541Srgrimes bno = blkstofrags(fs, (bno + i)); 10501541Srgrimes goto gotit; 10511541Srgrimes } 10521541Srgrimes delta = fs_rotbl(fs)[i]; 10531541Srgrimes if (delta <= 0 || 10541541Srgrimes delta + i > fragstoblks(fs, fs->fs_fpg)) 10551541Srgrimes break; 10561541Srgrimes i += delta; 10571541Srgrimes } 10581541Srgrimes printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 10591541Srgrimes panic("ffs_alloccgblk: can't find blk in cyl"); 10601541Srgrimes } 10611541Srgrimesnorot: 10621541Srgrimes /* 10631541Srgrimes * no blocks in the requested cylinder, so take next 10641541Srgrimes * available one in this cylinder group. 10651541Srgrimes */ 10661541Srgrimes bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 10671541Srgrimes if (bno < 0) 106817108Sbde return (0); 10691541Srgrimes cgp->cg_rotor = bno; 10701541Srgrimesgotit: 10711541Srgrimes blkno = fragstoblks(fs, bno); 10721541Srgrimes ffs_clrblock(fs, cg_blksfree(cgp), (long)blkno); 10731541Srgrimes ffs_clusteracct(fs, cgp, blkno, -1); 10741541Srgrimes cgp->cg_cs.cs_nbfree--; 10751541Srgrimes fs->fs_cstotal.cs_nbfree--; 10761541Srgrimes fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 10771541Srgrimes cylno = cbtocylno(fs, bno); 10781541Srgrimes cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 10791541Srgrimes cg_blktot(cgp)[cylno]--; 10801541Srgrimes fs->fs_fmod = 1; 108134266Sjulian blkno = cgp->cg_cgx * fs->fs_fpg + bno; 108234266Sjulian if (DOINGSOFTDEP(ITOV(ip))) 108334266Sjulian softdep_setup_blkmapdep(bp, fs, blkno); 108434266Sjulian return (blkno); 10851541Srgrimes} 10861541Srgrimes 108712911Sphk#ifdef notyet 10881541Srgrimes/* 10891541Srgrimes * Determine whether a cluster can be allocated. 10901541Srgrimes * 10911541Srgrimes * We do not currently check for optimal rotational layout if there 10921541Srgrimes * are multiple choices in the same cylinder group. Instead we just 10931541Srgrimes * take the first one that we find following bpref. 10941541Srgrimes */ 109522521Sdysonstatic ufs_daddr_t 10961541Srgrimesffs_clusteralloc(ip, cg, bpref, len) 10971541Srgrimes struct inode *ip; 10981541Srgrimes int cg; 109922521Sdyson ufs_daddr_t bpref; 11001541Srgrimes int len; 11011541Srgrimes{ 11021541Srgrimes register struct fs *fs; 11031541Srgrimes register struct cg *cgp; 11041541Srgrimes struct buf *bp; 110522521Sdyson int i, got, run, bno, bit, map; 11061541Srgrimes u_char *mapp; 110722521Sdyson int32_t *lp; 11081541Srgrimes 11091541Srgrimes fs = ip->i_fs; 111022521Sdyson if (fs->fs_maxcluster[cg] < len) 11111541Srgrimes return (NULL); 11121541Srgrimes if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 11131541Srgrimes NOCRED, &bp)) 11141541Srgrimes goto fail; 11151541Srgrimes cgp = (struct cg *)bp->b_data; 11161541Srgrimes if (!cg_chkmagic(cgp)) 11171541Srgrimes goto fail; 11181541Srgrimes /* 11191541Srgrimes * Check to see if a cluster of the needed size (or bigger) is 11201541Srgrimes * available in this cylinder group. 11211541Srgrimes */ 112222521Sdyson lp = &cg_clustersum(cgp)[len]; 11231541Srgrimes for (i = len; i <= fs->fs_contigsumsize; i++) 112422521Sdyson if (*lp++ > 0) 11251541Srgrimes break; 112622521Sdyson if (i > fs->fs_contigsumsize) { 112722521Sdyson /* 112822521Sdyson * This is the first time looking for a cluster in this 112922521Sdyson * cylinder group. Update the cluster summary information 113022521Sdyson * to reflect the true maximum sized cluster so that 113122521Sdyson * future cluster allocation requests can avoid reading 113222521Sdyson * the cylinder group map only to find no clusters. 113322521Sdyson */ 113422521Sdyson lp = &cg_clustersum(cgp)[len - 1]; 113522521Sdyson for (i = len - 1; i > 0; i--) 113622521Sdyson if (*lp-- > 0) 113722521Sdyson break; 113822521Sdyson fs->fs_maxcluster[cg] = i; 11391541Srgrimes goto fail; 114022521Sdyson } 11411541Srgrimes /* 11421541Srgrimes * Search the cluster map to find a big enough cluster. 11431541Srgrimes * We take the first one that we find, even if it is larger 11441541Srgrimes * than we need as we prefer to get one close to the previous 11451541Srgrimes * block allocation. We do not search before the current 11461541Srgrimes * preference point as we do not want to allocate a block 11471541Srgrimes * that is allocated before the previous one (as we will 11481541Srgrimes * then have to wait for another pass of the elevator 11491541Srgrimes * algorithm before it will be read). We prefer to fail and 11501541Srgrimes * be recalled to try an allocation in the next cylinder group. 11511541Srgrimes */ 11521541Srgrimes if (dtog(fs, bpref) != cg) 11531541Srgrimes bpref = 0; 11541541Srgrimes else 11551541Srgrimes bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 11561541Srgrimes mapp = &cg_clustersfree(cgp)[bpref / NBBY]; 11571541Srgrimes map = *mapp++; 11581541Srgrimes bit = 1 << (bpref % NBBY); 115922521Sdyson for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) { 11601541Srgrimes if ((map & bit) == 0) { 11611541Srgrimes run = 0; 11621541Srgrimes } else { 11631541Srgrimes run++; 11641541Srgrimes if (run == len) 11651541Srgrimes break; 11661541Srgrimes } 116722521Sdyson if ((got & (NBBY - 1)) != (NBBY - 1)) { 11681541Srgrimes bit <<= 1; 11691541Srgrimes } else { 11701541Srgrimes map = *mapp++; 11711541Srgrimes bit = 1; 11721541Srgrimes } 11731541Srgrimes } 117427890Sphk if (got >= cgp->cg_nclusterblks) 11751541Srgrimes goto fail; 11761541Srgrimes /* 11771541Srgrimes * Allocate the cluster that we have found. 11781541Srgrimes */ 117922521Sdyson for (i = 1; i <= len; i++) 118022521Sdyson if (!ffs_isblock(fs, cg_blksfree(cgp), got - run + i)) 118122521Sdyson panic("ffs_clusteralloc: map mismatch"); 118222521Sdyson bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1); 118322521Sdyson if (dtog(fs, bno) != cg) 118422521Sdyson panic("ffs_clusteralloc: allocated out of group"); 11851541Srgrimes len = blkstofrags(fs, len); 11861541Srgrimes for (i = 0; i < len; i += fs->fs_frag) 118734266Sjulian if ((got = ffs_alloccgblk(ip, bp, bno + i)) != bno + i) 11881541Srgrimes panic("ffs_clusteralloc: lost block"); 11899980Sdg bdwrite(bp); 11901541Srgrimes return (bno); 11911541Srgrimes 11921541Srgrimesfail: 11931541Srgrimes brelse(bp); 11941541Srgrimes return (0); 11951541Srgrimes} 119612911Sphk#endif 11971541Srgrimes 11981541Srgrimes/* 11991541Srgrimes * Determine whether an inode can be allocated. 12001541Srgrimes * 12011541Srgrimes * Check to see if an inode is available, and if it is, 12021541Srgrimes * allocate it using the following policy: 12031541Srgrimes * 1) allocate the requested inode. 12041541Srgrimes * 2) allocate the next available inode after the requested 12051541Srgrimes * inode in the specified cylinder group. 12061541Srgrimes */ 12071541Srgrimesstatic ino_t 12081541Srgrimesffs_nodealloccg(ip, cg, ipref, mode) 12091541Srgrimes struct inode *ip; 12101541Srgrimes int cg; 121122521Sdyson ufs_daddr_t ipref; 12121541Srgrimes int mode; 12131541Srgrimes{ 12141541Srgrimes register struct fs *fs; 12151541Srgrimes register struct cg *cgp; 12161541Srgrimes struct buf *bp; 12171541Srgrimes int error, start, len, loc, map, i; 12181541Srgrimes 12191541Srgrimes fs = ip->i_fs; 12201541Srgrimes if (fs->fs_cs(fs, cg).cs_nifree == 0) 122117108Sbde return (0); 12221541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 12231541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 12241541Srgrimes if (error) { 12251541Srgrimes brelse(bp); 122617108Sbde return (0); 12271541Srgrimes } 12281541Srgrimes cgp = (struct cg *)bp->b_data; 12291541Srgrimes if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 12301541Srgrimes brelse(bp); 123117108Sbde return (0); 12321541Srgrimes } 123334961Sphk cgp->cg_time = time_second; 12341541Srgrimes if (ipref) { 12351541Srgrimes ipref %= fs->fs_ipg; 12361541Srgrimes if (isclr(cg_inosused(cgp), ipref)) 12371541Srgrimes goto gotit; 12381541Srgrimes } 12391541Srgrimes start = cgp->cg_irotor / NBBY; 12401541Srgrimes len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 12411541Srgrimes loc = skpc(0xff, len, &cg_inosused(cgp)[start]); 12421541Srgrimes if (loc == 0) { 12431541Srgrimes len = start + 1; 12441541Srgrimes start = 0; 12451541Srgrimes loc = skpc(0xff, len, &cg_inosused(cgp)[0]); 12461541Srgrimes if (loc == 0) { 12476357Sphk printf("cg = %d, irotor = %ld, fs = %s\n", 124837555Sbde cg, (long)cgp->cg_irotor, fs->fs_fsmnt); 12491541Srgrimes panic("ffs_nodealloccg: map corrupted"); 12501541Srgrimes /* NOTREACHED */ 12511541Srgrimes } 12521541Srgrimes } 12531541Srgrimes i = start + len - loc; 12541541Srgrimes map = cg_inosused(cgp)[i]; 12551541Srgrimes ipref = i * NBBY; 12561541Srgrimes for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 12571541Srgrimes if ((map & i) == 0) { 12581541Srgrimes cgp->cg_irotor = ipref; 12591541Srgrimes goto gotit; 12601541Srgrimes } 12611541Srgrimes } 12621541Srgrimes printf("fs = %s\n", fs->fs_fsmnt); 12631541Srgrimes panic("ffs_nodealloccg: block not in map"); 12641541Srgrimes /* NOTREACHED */ 12651541Srgrimesgotit: 126634266Sjulian if (DOINGSOFTDEP(ITOV(ip))) 126734266Sjulian softdep_setup_inomapdep(bp, ip, cg * fs->fs_ipg + ipref); 12681541Srgrimes setbit(cg_inosused(cgp), ipref); 12691541Srgrimes cgp->cg_cs.cs_nifree--; 12701541Srgrimes fs->fs_cstotal.cs_nifree--; 12711541Srgrimes fs->fs_cs(fs, cg).cs_nifree--; 12721541Srgrimes fs->fs_fmod = 1; 12731541Srgrimes if ((mode & IFMT) == IFDIR) { 12741541Srgrimes cgp->cg_cs.cs_ndir++; 12751541Srgrimes fs->fs_cstotal.cs_ndir++; 12761541Srgrimes fs->fs_cs(fs, cg).cs_ndir++; 12771541Srgrimes } 12781541Srgrimes bdwrite(bp); 12791541Srgrimes return (cg * fs->fs_ipg + ipref); 12801541Srgrimes} 12811541Srgrimes 12821541Srgrimes/* 12831541Srgrimes * Free a block or fragment. 12841541Srgrimes * 12851541Srgrimes * The specified block or fragment is placed back in the 12868876Srgrimes * free map. If a fragment is deallocated, a possible 12871541Srgrimes * block reassembly is checked. 12881541Srgrimes */ 12891549Srgrimesvoid 12901541Srgrimesffs_blkfree(ip, bno, size) 12911541Srgrimes register struct inode *ip; 129222521Sdyson ufs_daddr_t bno; 12931541Srgrimes long size; 12941541Srgrimes{ 12951541Srgrimes register struct fs *fs; 12961541Srgrimes register struct cg *cgp; 12971541Srgrimes struct buf *bp; 129822521Sdyson ufs_daddr_t blkno; 12991541Srgrimes int i, error, cg, blk, frags, bbase; 13001541Srgrimes 13011541Srgrimes fs = ip->i_fs; 130234266Sjulian if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0 || 130334266Sjulian fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) { 130434266Sjulian printf("dev=0x%lx, bno = %d, bsize = %d, size = %ld, fs = %s\n", 130534266Sjulian (u_long)ip->i_dev, bno, fs->fs_bsize, size, fs->fs_fsmnt); 130623560Smpp panic("ffs_blkfree: bad size"); 13071541Srgrimes } 13081541Srgrimes cg = dtog(fs, bno); 13091541Srgrimes if ((u_int)bno >= fs->fs_size) { 131037555Sbde printf("bad block %ld, ino %lu\n", 131137555Sbde (long)bno, (u_long)ip->i_number); 13121541Srgrimes ffs_fserr(fs, ip->i_uid, "bad block"); 13131541Srgrimes return; 13141541Srgrimes } 13151541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 13161541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 13171541Srgrimes if (error) { 13181541Srgrimes brelse(bp); 13191541Srgrimes return; 13201541Srgrimes } 13211541Srgrimes cgp = (struct cg *)bp->b_data; 13221541Srgrimes if (!cg_chkmagic(cgp)) { 13231541Srgrimes brelse(bp); 13241541Srgrimes return; 13251541Srgrimes } 132634961Sphk cgp->cg_time = time_second; 13271541Srgrimes bno = dtogd(fs, bno); 13281541Srgrimes if (size == fs->fs_bsize) { 13291541Srgrimes blkno = fragstoblks(fs, bno); 133034266Sjulian if (!ffs_isfreeblock(fs, cg_blksfree(cgp), blkno)) { 13316357Sphk printf("dev = 0x%lx, block = %ld, fs = %s\n", 133237555Sbde (u_long)ip->i_dev, (long)bno, fs->fs_fsmnt); 133323560Smpp panic("ffs_blkfree: freeing free block"); 13341541Srgrimes } 13351541Srgrimes ffs_setblock(fs, cg_blksfree(cgp), blkno); 13361541Srgrimes ffs_clusteracct(fs, cgp, blkno, 1); 13371541Srgrimes cgp->cg_cs.cs_nbfree++; 13381541Srgrimes fs->fs_cstotal.cs_nbfree++; 13391541Srgrimes fs->fs_cs(fs, cg).cs_nbfree++; 13401541Srgrimes i = cbtocylno(fs, bno); 13411541Srgrimes cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; 13421541Srgrimes cg_blktot(cgp)[i]++; 13431541Srgrimes } else { 13441541Srgrimes bbase = bno - fragnum(fs, bno); 13451541Srgrimes /* 13461541Srgrimes * decrement the counts associated with the old frags 13471541Srgrimes */ 13481541Srgrimes blk = blkmap(fs, cg_blksfree(cgp), bbase); 13491541Srgrimes ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 13501541Srgrimes /* 13511541Srgrimes * deallocate the fragment 13521541Srgrimes */ 13531541Srgrimes frags = numfrags(fs, size); 13541541Srgrimes for (i = 0; i < frags; i++) { 13551541Srgrimes if (isset(cg_blksfree(cgp), bno + i)) { 13566357Sphk printf("dev = 0x%lx, block = %ld, fs = %s\n", 135737555Sbde (u_long)ip->i_dev, (long)(bno + i), 135837555Sbde fs->fs_fsmnt); 135923560Smpp panic("ffs_blkfree: freeing free frag"); 13601541Srgrimes } 13611541Srgrimes setbit(cg_blksfree(cgp), bno + i); 13621541Srgrimes } 13631541Srgrimes cgp->cg_cs.cs_nffree += i; 13641541Srgrimes fs->fs_cstotal.cs_nffree += i; 13651541Srgrimes fs->fs_cs(fs, cg).cs_nffree += i; 13661541Srgrimes /* 13671541Srgrimes * add back in counts associated with the new frags 13681541Srgrimes */ 13691541Srgrimes blk = blkmap(fs, cg_blksfree(cgp), bbase); 13701541Srgrimes ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 13711541Srgrimes /* 13721541Srgrimes * if a complete block has been reassembled, account for it 13731541Srgrimes */ 13741541Srgrimes blkno = fragstoblks(fs, bbase); 13751541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 13761541Srgrimes cgp->cg_cs.cs_nffree -= fs->fs_frag; 13771541Srgrimes fs->fs_cstotal.cs_nffree -= fs->fs_frag; 13781541Srgrimes fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 13791541Srgrimes ffs_clusteracct(fs, cgp, blkno, 1); 13801541Srgrimes cgp->cg_cs.cs_nbfree++; 13811541Srgrimes fs->fs_cstotal.cs_nbfree++; 13821541Srgrimes fs->fs_cs(fs, cg).cs_nbfree++; 13831541Srgrimes i = cbtocylno(fs, bbase); 13841541Srgrimes cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 13851541Srgrimes cg_blktot(cgp)[i]++; 13861541Srgrimes } 13871541Srgrimes } 13881541Srgrimes fs->fs_fmod = 1; 13891541Srgrimes bdwrite(bp); 13901541Srgrimes} 13911541Srgrimes 139222521Sdyson#ifdef DIAGNOSTIC 13931541Srgrimes/* 139422521Sdyson * Verify allocation of a block or fragment. Returns true if block or 139522521Sdyson * fragment is allocated, false if it is free. 139622521Sdyson */ 139731352Sbdestatic int 139822521Sdysonffs_checkblk(ip, bno, size) 139922521Sdyson struct inode *ip; 140022521Sdyson ufs_daddr_t bno; 140122521Sdyson long size; 140222521Sdyson{ 140322521Sdyson struct fs *fs; 140422521Sdyson struct cg *cgp; 140522521Sdyson struct buf *bp; 140622521Sdyson int i, error, frags, free; 140722521Sdyson 140822521Sdyson fs = ip->i_fs; 140922521Sdyson if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 141037555Sbde printf("bsize = %ld, size = %ld, fs = %s\n", 141137555Sbde (long)fs->fs_bsize, size, fs->fs_fsmnt); 141222544Smpp panic("ffs_checkblk: bad size"); 141322521Sdyson } 141422521Sdyson if ((u_int)bno >= fs->fs_size) 141522544Smpp panic("ffs_checkblk: bad block %d", bno); 141622521Sdyson error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))), 141722521Sdyson (int)fs->fs_cgsize, NOCRED, &bp); 141822544Smpp if (error) 141922544Smpp panic("ffs_checkblk: cg bread failed"); 142022521Sdyson cgp = (struct cg *)bp->b_data; 142122544Smpp if (!cg_chkmagic(cgp)) 142222544Smpp panic("ffs_checkblk: cg magic mismatch"); 142322521Sdyson bno = dtogd(fs, bno); 142422521Sdyson if (size == fs->fs_bsize) { 142522521Sdyson free = ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno)); 142622521Sdyson } else { 142722521Sdyson frags = numfrags(fs, size); 142822521Sdyson for (free = 0, i = 0; i < frags; i++) 142922521Sdyson if (isset(cg_blksfree(cgp), bno + i)) 143022521Sdyson free++; 143122521Sdyson if (free != 0 && free != frags) 143222544Smpp panic("ffs_checkblk: partially free fragment"); 143322521Sdyson } 143422521Sdyson brelse(bp); 143522521Sdyson return (!free); 143622521Sdyson} 143722521Sdyson#endif /* DIAGNOSTIC */ 143822521Sdyson 143922521Sdyson/* 14401541Srgrimes * Free an inode. 14411541Srgrimes */ 14421541Srgrimesint 144334266Sjulianffs_vfree( pvp, ino, mode) 144430474Sphk struct vnode *pvp; 144530474Sphk ino_t ino; 144630474Sphk int mode; 14471541Srgrimes{ 144834266Sjulian if (DOINGSOFTDEP(pvp)) { 144934266Sjulian softdep_freefile(pvp, ino, mode); 145034266Sjulian return (0); 145134266Sjulian } 145234266Sjulian return (ffs_freefile(pvp, ino, mode)); 145334266Sjulian} 145434266Sjulian 145534266Sjulian/* 145634266Sjulian * Do the actual free operation. 145734266Sjulian * The specified inode is placed back in the free map. 145834266Sjulian */ 145934266Sjulian int 146034266Sjulian ffs_freefile( pvp, ino, mode) 146134266Sjulian struct vnode *pvp; 146234266Sjulian ino_t ino; 146334266Sjulian int mode; 146434266Sjulian{ 14651541Srgrimes register struct fs *fs; 14661541Srgrimes register struct cg *cgp; 14671541Srgrimes register struct inode *pip; 14681541Srgrimes struct buf *bp; 14691541Srgrimes int error, cg; 14701541Srgrimes 147130474Sphk pip = VTOI(pvp); 14721541Srgrimes fs = pip->i_fs; 14731541Srgrimes if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 147423560Smpp panic("ffs_vfree: range: dev = 0x%x, ino = %d, fs = %s", 14751541Srgrimes pip->i_dev, ino, fs->fs_fsmnt); 14761541Srgrimes cg = ino_to_cg(fs, ino); 14771541Srgrimes error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 14781541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 14791541Srgrimes if (error) { 14801541Srgrimes brelse(bp); 148134266Sjulian return (error); 14821541Srgrimes } 14831541Srgrimes cgp = (struct cg *)bp->b_data; 14841541Srgrimes if (!cg_chkmagic(cgp)) { 14851541Srgrimes brelse(bp); 14861541Srgrimes return (0); 14871541Srgrimes } 148834961Sphk cgp->cg_time = time_second; 14891541Srgrimes ino %= fs->fs_ipg; 14901541Srgrimes if (isclr(cg_inosused(cgp), ino)) { 149137555Sbde printf("dev = 0x%lx, ino = %lu, fs = %s\n", 149237555Sbde (u_long)pip->i_dev, (u_long)ino, fs->fs_fsmnt); 14931541Srgrimes if (fs->fs_ronly == 0) 149423560Smpp panic("ffs_vfree: freeing free inode"); 14951541Srgrimes } 14961541Srgrimes clrbit(cg_inosused(cgp), ino); 14971541Srgrimes if (ino < cgp->cg_irotor) 14981541Srgrimes cgp->cg_irotor = ino; 14991541Srgrimes cgp->cg_cs.cs_nifree++; 15001541Srgrimes fs->fs_cstotal.cs_nifree++; 15011541Srgrimes fs->fs_cs(fs, cg).cs_nifree++; 150230474Sphk if ((mode & IFMT) == IFDIR) { 15031541Srgrimes cgp->cg_cs.cs_ndir--; 15041541Srgrimes fs->fs_cstotal.cs_ndir--; 15051541Srgrimes fs->fs_cs(fs, cg).cs_ndir--; 15061541Srgrimes } 15071541Srgrimes fs->fs_fmod = 1; 15081541Srgrimes bdwrite(bp); 15091541Srgrimes return (0); 15101541Srgrimes} 15111541Srgrimes 15121541Srgrimes/* 15131541Srgrimes * Find a block of the specified size in the specified cylinder group. 15141541Srgrimes * 15151541Srgrimes * It is a panic if a request is made to find a block if none are 15161541Srgrimes * available. 15171541Srgrimes */ 151822521Sdysonstatic ufs_daddr_t 15191541Srgrimesffs_mapsearch(fs, cgp, bpref, allocsiz) 15201541Srgrimes register struct fs *fs; 15211541Srgrimes register struct cg *cgp; 152222521Sdyson ufs_daddr_t bpref; 15231541Srgrimes int allocsiz; 15241541Srgrimes{ 152522521Sdyson ufs_daddr_t bno; 15261541Srgrimes int start, len, loc, i; 15271541Srgrimes int blk, field, subfield, pos; 15281541Srgrimes 15291541Srgrimes /* 15301541Srgrimes * find the fragment by searching through the free block 15311541Srgrimes * map for an appropriate bit pattern 15321541Srgrimes */ 15331541Srgrimes if (bpref) 15341541Srgrimes start = dtogd(fs, bpref) / NBBY; 15351541Srgrimes else 15361541Srgrimes start = cgp->cg_frotor / NBBY; 15371541Srgrimes len = howmany(fs->fs_fpg, NBBY) - start; 15381541Srgrimes loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[start], 15391541Srgrimes (u_char *)fragtbl[fs->fs_frag], 15401541Srgrimes (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 15411541Srgrimes if (loc == 0) { 15421541Srgrimes len = start + 1; 15431541Srgrimes start = 0; 15441541Srgrimes loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[0], 15451541Srgrimes (u_char *)fragtbl[fs->fs_frag], 15461541Srgrimes (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 15471541Srgrimes if (loc == 0) { 15481541Srgrimes printf("start = %d, len = %d, fs = %s\n", 15491541Srgrimes start, len, fs->fs_fsmnt); 15501541Srgrimes panic("ffs_alloccg: map corrupted"); 15511541Srgrimes /* NOTREACHED */ 15521541Srgrimes } 15531541Srgrimes } 15541541Srgrimes bno = (start + len - loc) * NBBY; 15551541Srgrimes cgp->cg_frotor = bno; 15561541Srgrimes /* 15571541Srgrimes * found the byte in the map 15581541Srgrimes * sift through the bits to find the selected frag 15591541Srgrimes */ 15601541Srgrimes for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 15611541Srgrimes blk = blkmap(fs, cg_blksfree(cgp), bno); 15621541Srgrimes blk <<= 1; 15631541Srgrimes field = around[allocsiz]; 15641541Srgrimes subfield = inside[allocsiz]; 15651541Srgrimes for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 15661541Srgrimes if ((blk & field) == subfield) 15671541Srgrimes return (bno + pos); 15681541Srgrimes field <<= 1; 15691541Srgrimes subfield <<= 1; 15701541Srgrimes } 15711541Srgrimes } 15723487Sphk printf("bno = %lu, fs = %s\n", (u_long)bno, fs->fs_fsmnt); 15731541Srgrimes panic("ffs_alloccg: block not in map"); 15741541Srgrimes return (-1); 15751541Srgrimes} 15761541Srgrimes 15771541Srgrimes/* 15781541Srgrimes * Update the cluster map because of an allocation or free. 15791541Srgrimes * 15801541Srgrimes * Cnt == 1 means free; cnt == -1 means allocating. 15811541Srgrimes */ 158212911Sphkstatic void 15831541Srgrimesffs_clusteracct(fs, cgp, blkno, cnt) 15841541Srgrimes struct fs *fs; 15851541Srgrimes struct cg *cgp; 158622521Sdyson ufs_daddr_t blkno; 15871541Srgrimes int cnt; 15881541Srgrimes{ 158922521Sdyson int32_t *sump; 159022521Sdyson int32_t *lp; 15911541Srgrimes u_char *freemapp, *mapp; 15921541Srgrimes int i, start, end, forw, back, map, bit; 15931541Srgrimes 15941541Srgrimes if (fs->fs_contigsumsize <= 0) 15951541Srgrimes return; 15961541Srgrimes freemapp = cg_clustersfree(cgp); 15971541Srgrimes sump = cg_clustersum(cgp); 15981541Srgrimes /* 15991541Srgrimes * Allocate or clear the actual block. 16001541Srgrimes */ 16011541Srgrimes if (cnt > 0) 16021541Srgrimes setbit(freemapp, blkno); 16031541Srgrimes else 16041541Srgrimes clrbit(freemapp, blkno); 16051541Srgrimes /* 16061541Srgrimes * Find the size of the cluster going forward. 16071541Srgrimes */ 16081541Srgrimes start = blkno + 1; 16091541Srgrimes end = start + fs->fs_contigsumsize; 16101541Srgrimes if (end >= cgp->cg_nclusterblks) 16111541Srgrimes end = cgp->cg_nclusterblks; 16121541Srgrimes mapp = &freemapp[start / NBBY]; 16131541Srgrimes map = *mapp++; 16141541Srgrimes bit = 1 << (start % NBBY); 16151541Srgrimes for (i = start; i < end; i++) { 16161541Srgrimes if ((map & bit) == 0) 16171541Srgrimes break; 16181541Srgrimes if ((i & (NBBY - 1)) != (NBBY - 1)) { 16191541Srgrimes bit <<= 1; 16201541Srgrimes } else { 16211541Srgrimes map = *mapp++; 16221541Srgrimes bit = 1; 16231541Srgrimes } 16241541Srgrimes } 16251541Srgrimes forw = i - start; 16261541Srgrimes /* 16271541Srgrimes * Find the size of the cluster going backward. 16281541Srgrimes */ 16291541Srgrimes start = blkno - 1; 16301541Srgrimes end = start - fs->fs_contigsumsize; 16311541Srgrimes if (end < 0) 16321541Srgrimes end = -1; 16331541Srgrimes mapp = &freemapp[start / NBBY]; 16341541Srgrimes map = *mapp--; 16351541Srgrimes bit = 1 << (start % NBBY); 16361541Srgrimes for (i = start; i > end; i--) { 16371541Srgrimes if ((map & bit) == 0) 16381541Srgrimes break; 16391541Srgrimes if ((i & (NBBY - 1)) != 0) { 16401541Srgrimes bit >>= 1; 16411541Srgrimes } else { 16421541Srgrimes map = *mapp--; 16431541Srgrimes bit = 1 << (NBBY - 1); 16441541Srgrimes } 16451541Srgrimes } 16461541Srgrimes back = start - i; 16471541Srgrimes /* 16481541Srgrimes * Account for old cluster and the possibly new forward and 16491541Srgrimes * back clusters. 16501541Srgrimes */ 16511541Srgrimes i = back + forw + 1; 16521541Srgrimes if (i > fs->fs_contigsumsize) 16531541Srgrimes i = fs->fs_contigsumsize; 16541541Srgrimes sump[i] += cnt; 16551541Srgrimes if (back > 0) 16561541Srgrimes sump[back] -= cnt; 16571541Srgrimes if (forw > 0) 16581541Srgrimes sump[forw] -= cnt; 165922521Sdyson /* 166022521Sdyson * Update cluster summary information. 166122521Sdyson */ 166222521Sdyson lp = &sump[fs->fs_contigsumsize]; 166322521Sdyson for (i = fs->fs_contigsumsize; i > 0; i--) 166422521Sdyson if (*lp-- > 0) 166522521Sdyson break; 166622521Sdyson fs->fs_maxcluster[cgp->cg_cgx] = i; 16671541Srgrimes} 16681541Srgrimes 16691541Srgrimes/* 16701541Srgrimes * Fserr prints the name of a file system with an error diagnostic. 16718876Srgrimes * 16721541Srgrimes * The form of the error message is: 16731541Srgrimes * fs: error message 16741541Srgrimes */ 16751541Srgrimesstatic void 16761541Srgrimesffs_fserr(fs, uid, cp) 16771541Srgrimes struct fs *fs; 16781541Srgrimes u_int uid; 16791541Srgrimes char *cp; 16801541Srgrimes{ 168118330Speter struct proc *p = curproc; /* XXX */ 16821541Srgrimes 168318330Speter log(LOG_ERR, "pid %d (%s), uid %d on %s: %s\n", p ? p->p_pid : -1, 168418330Speter p ? p->p_comm : "-", uid, fs->fs_fsmnt, cp); 16851541Srgrimes} 1686