ffs_alloc.c revision 30492
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 3430492Sphk * $Id: ffs_alloc.c,v 1.40 1997/10/16 10:49:19 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)); 6022521Sdysonstatic ufs_daddr_t ffs_alloccgblk __P((struct fs *, struct cg *, ufs_daddr_t)); 6122521Sdysonstatic void ffs_clusteracct __P((struct fs *, struct cg *, ufs_daddr_t, 6222521Sdyson int)); 6322521Sdysonstatic ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t, 6422521Sdyson int)); 651541Srgrimesstatic ino_t ffs_dirpref __P((struct fs *)); 6622521Sdysonstatic ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 671541Srgrimesstatic void ffs_fserr __P((struct fs *, u_int, char *)); 681541Srgrimesstatic u_long ffs_hashalloc 6912590Sbde __P((struct inode *, int, long, int, allocfcn_t *)); 7022521Sdysonstatic ino_t ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int)); 7122521Sdysonstatic ufs_daddr_t ffs_mapsearch __P((struct fs *, struct cg *, ufs_daddr_t, 7222521Sdyson int)); 731541Srgrimes 741541Srgrimes/* 751541Srgrimes * Allocate a block in the file system. 768876Srgrimes * 771541Srgrimes * The size of the requested block is given, which must be some 781541Srgrimes * multiple of fs_fsize and <= fs_bsize. 791541Srgrimes * A preference may be optionally specified. If a preference is given 801541Srgrimes * the following hierarchy is used to allocate a block: 811541Srgrimes * 1) allocate the requested block. 821541Srgrimes * 2) allocate a rotationally optimal block in the same cylinder. 831541Srgrimes * 3) allocate a block in the same cylinder group. 841541Srgrimes * 4) quadradically rehash into other cylinder groups, until an 851541Srgrimes * available block is located. 861541Srgrimes * If no block preference is given the following heirarchy is used 871541Srgrimes * to allocate a block: 881541Srgrimes * 1) allocate a block in the cylinder group that contains the 891541Srgrimes * inode for the file. 901541Srgrimes * 2) quadradically rehash into other cylinder groups, until an 911541Srgrimes * available block is located. 921541Srgrimes */ 931549Srgrimesint 941541Srgrimesffs_alloc(ip, lbn, bpref, size, cred, bnp) 951541Srgrimes register struct inode *ip; 9622521Sdyson ufs_daddr_t lbn, bpref; 971541Srgrimes int size; 981541Srgrimes struct ucred *cred; 9922521Sdyson ufs_daddr_t *bnp; 1001541Srgrimes{ 1011541Srgrimes register struct fs *fs; 10222521Sdyson ufs_daddr_t bno; 1036357Sphk int cg; 1046357Sphk#ifdef QUOTA 1056357Sphk int error; 1066357Sphk#endif 1078876Srgrimes 1081541Srgrimes *bnp = 0; 1091541Srgrimes fs = ip->i_fs; 1101541Srgrimes#ifdef DIAGNOSTIC 1111541Srgrimes if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1123487Sphk printf("dev = 0x%lx, bsize = %ld, size = %d, fs = %s\n", 1133487Sphk (u_long)ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 1141541Srgrimes panic("ffs_alloc: bad size"); 1151541Srgrimes } 1161541Srgrimes if (cred == NOCRED) 1177170Sdg panic("ffs_alloc: missing credential"); 1181541Srgrimes#endif /* DIAGNOSTIC */ 1191541Srgrimes if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 1201541Srgrimes goto nospace; 12129609Sphk if (cred->cr_uid != 0 && 12229609Sphk freespace(fs, fs->fs_minfree) - numfrags(fs, size) < 0) 1231541Srgrimes goto nospace; 1241541Srgrimes#ifdef QUOTA 1253487Sphk error = chkdq(ip, (long)btodb(size), cred, 0); 1263487Sphk if (error) 1271541Srgrimes return (error); 1281541Srgrimes#endif 1291541Srgrimes if (bpref >= fs->fs_size) 1301541Srgrimes bpref = 0; 1311541Srgrimes if (bpref == 0) 1321541Srgrimes cg = ino_to_cg(fs, ip->i_number); 1331541Srgrimes else 1341541Srgrimes cg = dtog(fs, bpref); 13522521Sdyson bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 13622521Sdyson ffs_alloccg); 1371541Srgrimes if (bno > 0) { 1381541Srgrimes ip->i_blocks += btodb(size); 1391541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 1401541Srgrimes *bnp = bno; 1411541Srgrimes return (0); 1421541Srgrimes } 1431541Srgrimes#ifdef QUOTA 1441541Srgrimes /* 1451541Srgrimes * Restore user's disk quota because allocation failed. 1461541Srgrimes */ 1471541Srgrimes (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 1481541Srgrimes#endif 1491541Srgrimesnospace: 1501541Srgrimes ffs_fserr(fs, cred->cr_uid, "file system full"); 1511541Srgrimes uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 1521541Srgrimes return (ENOSPC); 1531541Srgrimes} 1541541Srgrimes 1551541Srgrimes/* 1561541Srgrimes * Reallocate a fragment to a bigger size 1571541Srgrimes * 1581541Srgrimes * The number and size of the old block is given, and a preference 1591541Srgrimes * and new size is also specified. The allocator attempts to extend 1601541Srgrimes * the original block. Failing that, the regular block allocator is 1611541Srgrimes * invoked to get an appropriate block. 1621541Srgrimes */ 1631549Srgrimesint 1641541Srgrimesffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp) 1651541Srgrimes register struct inode *ip; 16622521Sdyson ufs_daddr_t lbprev; 16722521Sdyson ufs_daddr_t bpref; 1681541Srgrimes int osize, nsize; 1691541Srgrimes struct ucred *cred; 1701541Srgrimes struct buf **bpp; 1711541Srgrimes{ 1721541Srgrimes register struct fs *fs; 1731541Srgrimes struct buf *bp; 1741541Srgrimes int cg, request, error; 17522521Sdyson ufs_daddr_t bprev, bno; 1768876Srgrimes 1771541Srgrimes *bpp = 0; 1781541Srgrimes fs = ip->i_fs; 1791541Srgrimes#ifdef DIAGNOSTIC 1801541Srgrimes if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 1811541Srgrimes (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 1821541Srgrimes printf( 1838456Srgrimes "dev = 0x%lx, bsize = %ld, osize = %d, " 1848456Srgrimes "nsize = %d, fs = %s\n", 1858456Srgrimes (u_long)ip->i_dev, fs->fs_bsize, osize, 1868456Srgrimes nsize, fs->fs_fsmnt); 1871541Srgrimes panic("ffs_realloccg: bad size"); 1881541Srgrimes } 1891541Srgrimes if (cred == NOCRED) 1907170Sdg panic("ffs_realloccg: missing credential"); 1911541Srgrimes#endif /* DIAGNOSTIC */ 19229609Sphk if (cred->cr_uid != 0 && 19329609Sphk freespace(fs, fs->fs_minfree) - numfrags(fs, nsize - osize) < 0) 1941541Srgrimes goto nospace; 1951541Srgrimes if ((bprev = ip->i_db[lbprev]) == 0) { 1966357Sphk printf("dev = 0x%lx, bsize = %ld, bprev = %ld, fs = %s\n", 1976357Sphk (u_long) ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt); 1981541Srgrimes panic("ffs_realloccg: bad bprev"); 1991541Srgrimes } 2001541Srgrimes /* 2011541Srgrimes * Allocate the extra space in the buffer. 2021541Srgrimes */ 2033487Sphk error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp); 2043487Sphk if (error) { 2051541Srgrimes brelse(bp); 2061541Srgrimes return (error); 2071541Srgrimes } 2086864Sdg 2096864Sdg if( bp->b_blkno == bp->b_lblkno) { 2106864Sdg if( lbprev >= NDADDR) 2116864Sdg panic("ffs_realloccg: lbprev out of range"); 2126864Sdg bp->b_blkno = fsbtodb(fs, bprev); 2136864Sdg } 2148876Srgrimes 2151541Srgrimes#ifdef QUOTA 2163487Sphk error = chkdq(ip, (long)btodb(nsize - osize), cred, 0); 2173487Sphk if (error) { 2181541Srgrimes brelse(bp); 2191541Srgrimes return (error); 2201541Srgrimes } 2211541Srgrimes#endif 2221541Srgrimes /* 2231541Srgrimes * Check for extension in the existing location. 2241541Srgrimes */ 2251541Srgrimes cg = dtog(fs, bprev); 2263487Sphk bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize); 2273487Sphk if (bno) { 2281541Srgrimes if (bp->b_blkno != fsbtodb(fs, bno)) 22923560Smpp panic("ffs_realloccg: bad blockno"); 2301541Srgrimes ip->i_blocks += btodb(nsize - osize); 2311541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 2327399Sdg allocbuf(bp, nsize); 2331541Srgrimes bp->b_flags |= B_DONE; 2341541Srgrimes bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 2351541Srgrimes *bpp = bp; 2361541Srgrimes return (0); 2371541Srgrimes } 2381541Srgrimes /* 2391541Srgrimes * Allocate a new disk location. 2401541Srgrimes */ 2411541Srgrimes if (bpref >= fs->fs_size) 2421541Srgrimes bpref = 0; 2431541Srgrimes switch ((int)fs->fs_optim) { 2441541Srgrimes case FS_OPTSPACE: 2451541Srgrimes /* 2468876Srgrimes * Allocate an exact sized fragment. Although this makes 2478876Srgrimes * best use of space, we will waste time relocating it if 2481541Srgrimes * the file continues to grow. If the fragmentation is 2491541Srgrimes * less than half of the minimum free reserve, we choose 2501541Srgrimes * to begin optimizing for time. 2511541Srgrimes */ 2521541Srgrimes request = nsize; 2536993Sdg if (fs->fs_minfree <= 5 || 2541541Srgrimes fs->fs_cstotal.cs_nffree > 2551541Srgrimes fs->fs_dsize * fs->fs_minfree / (2 * 100)) 2561541Srgrimes break; 2571541Srgrimes log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 2581541Srgrimes fs->fs_fsmnt); 2591541Srgrimes fs->fs_optim = FS_OPTTIME; 2601541Srgrimes break; 2611541Srgrimes case FS_OPTTIME: 2621541Srgrimes /* 2631541Srgrimes * At this point we have discovered a file that is trying to 2641541Srgrimes * grow a small fragment to a larger fragment. To save time, 2651541Srgrimes * we allocate a full sized block, then free the unused portion. 2661541Srgrimes * If the file continues to grow, the `ffs_fragextend' call 2671541Srgrimes * above will be able to grow it in place without further 2681541Srgrimes * copying. If aberrant programs cause disk fragmentation to 2691541Srgrimes * grow within 2% of the free reserve, we choose to begin 2701541Srgrimes * optimizing for space. 2711541Srgrimes */ 2721541Srgrimes request = fs->fs_bsize; 2731541Srgrimes if (fs->fs_cstotal.cs_nffree < 2741541Srgrimes fs->fs_dsize * (fs->fs_minfree - 2) / 100) 2751541Srgrimes break; 2761541Srgrimes log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 2771541Srgrimes fs->fs_fsmnt); 2781541Srgrimes fs->fs_optim = FS_OPTSPACE; 2791541Srgrimes break; 2801541Srgrimes default: 2813487Sphk printf("dev = 0x%lx, optim = %ld, fs = %s\n", 2823487Sphk (u_long)ip->i_dev, fs->fs_optim, fs->fs_fsmnt); 2831541Srgrimes panic("ffs_realloccg: bad optim"); 2841541Srgrimes /* NOTREACHED */ 2851541Srgrimes } 28622521Sdyson bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 28722521Sdyson ffs_alloccg); 2881541Srgrimes if (bno > 0) { 2891541Srgrimes bp->b_blkno = fsbtodb(fs, bno); 2901541Srgrimes ffs_blkfree(ip, bprev, (long)osize); 2911541Srgrimes if (nsize < request) 2921541Srgrimes ffs_blkfree(ip, bno + numfrags(fs, nsize), 2931541Srgrimes (long)(request - nsize)); 2941541Srgrimes ip->i_blocks += btodb(nsize - osize); 2951541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 2967399Sdg allocbuf(bp, nsize); 2971541Srgrimes bp->b_flags |= B_DONE; 2981541Srgrimes bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 2991541Srgrimes *bpp = bp; 3001541Srgrimes return (0); 3011541Srgrimes } 3021541Srgrimes#ifdef QUOTA 3031541Srgrimes /* 3041541Srgrimes * Restore user's disk quota because allocation failed. 3051541Srgrimes */ 3061541Srgrimes (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 3071541Srgrimes#endif 3081541Srgrimes brelse(bp); 3091541Srgrimesnospace: 3101541Srgrimes /* 3111541Srgrimes * no space available 3121541Srgrimes */ 3131541Srgrimes ffs_fserr(fs, cred->cr_uid, "file system full"); 3141541Srgrimes uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 3151541Srgrimes return (ENOSPC); 3161541Srgrimes} 3171541Srgrimes 3181541Srgrimes/* 3191541Srgrimes * Reallocate a sequence of blocks into a contiguous sequence of blocks. 3201541Srgrimes * 3211541Srgrimes * The vnode and an array of buffer pointers for a range of sequential 3221541Srgrimes * logical blocks to be made contiguous is given. The allocator attempts 3231541Srgrimes * to find a range of sequential blocks starting as close as possible to 3241541Srgrimes * an fs_rotdelay offset from the end of the allocation for the logical 3251541Srgrimes * block immediately preceeding the current range. If successful, the 3261541Srgrimes * physical block numbers in the buffer pointers and in the inode are 3271541Srgrimes * changed to reflect the new allocation. If unsuccessful, the allocation 3281541Srgrimes * is left unchanged. The success in doing the reallocation is returned. 3291541Srgrimes * Note that the error return is not reflected back to the user. Rather 3301541Srgrimes * the previous block allocation will be used. 3311541Srgrimes */ 33212911Sphkstatic int doasyncfree = 1; 33322521SdysonSYSCTL_INT(_vfs_ffs, FFS_ASYNCFREE, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, ""); 33422521Sdyson 33522521Sdysonint doreallocblks = 1; 33622521SdysonSYSCTL_INT(_vfs_ffs, FFS_REALLOCBLKS, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, ""); 33722521Sdyson 33822521Sdysonstatic int prtrealloc = 0; 33922521Sdyson 3401541Srgrimesint 3411541Srgrimesffs_reallocblks(ap) 3421541Srgrimes struct vop_reallocblks_args /* { 3431541Srgrimes struct vnode *a_vp; 3441541Srgrimes struct cluster_save *a_buflist; 3451541Srgrimes } */ *ap; 3461541Srgrimes{ 34712911Sphk#if !defined (not_yes) 34812405Sdyson return (ENOSPC); 34912405Sdyson#else 3501541Srgrimes struct fs *fs; 3511541Srgrimes struct inode *ip; 3521541Srgrimes struct vnode *vp; 3531541Srgrimes struct buf *sbp, *ebp; 35422521Sdyson ufs_daddr_t *bap, *sbap, *ebap = 0; 3551541Srgrimes struct cluster_save *buflist; 35622521Sdyson ufs_daddr_t start_lbn, end_lbn, soff, newblk, blkno; 3571541Srgrimes struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 3581541Srgrimes int i, len, start_lvl, end_lvl, pref, ssize; 35910269Sbde struct timeval tv; 3601541Srgrimes 36122521Sdyson if (doreallocblks == 0) 36222521Sdyson return (ENOSPC); 3631541Srgrimes vp = ap->a_vp; 3641541Srgrimes ip = VTOI(vp); 3651541Srgrimes fs = ip->i_fs; 3661541Srgrimes if (fs->fs_contigsumsize <= 0) 3671541Srgrimes return (ENOSPC); 3681541Srgrimes buflist = ap->a_buflist; 3691541Srgrimes len = buflist->bs_nchildren; 3701541Srgrimes start_lbn = buflist->bs_children[0]->b_lblkno; 3711541Srgrimes end_lbn = start_lbn + len - 1; 3721541Srgrimes#ifdef DIAGNOSTIC 37322521Sdyson for (i = 0; i < len; i++) 37422521Sdyson if (!ffs_checkblk(ip, 37522521Sdyson dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 37622521Sdyson panic("ffs_reallocblks: unallocated block 1"); 3771541Srgrimes for (i = 1; i < len; i++) 3781541Srgrimes if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 37922521Sdyson panic("ffs_reallocblks: non-logical cluster"); 38022521Sdyson blkno = buflist->bs_children[0]->b_blkno; 38122521Sdyson ssize = fsbtodb(fs, fs->fs_frag); 38222521Sdyson for (i = 1; i < len - 1; i++) 38322521Sdyson if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize)) 38422521Sdyson panic("ffs_reallocblks: non-physical cluster %d", i); 3851541Srgrimes#endif 3861541Srgrimes /* 3871541Srgrimes * If the latest allocation is in a new cylinder group, assume that 3881541Srgrimes * the filesystem has decided to move and do not force it back to 3891541Srgrimes * the previous cylinder group. 3901541Srgrimes */ 3911541Srgrimes if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 3921541Srgrimes dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 3931541Srgrimes return (ENOSPC); 3941541Srgrimes if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 3951541Srgrimes ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 3961541Srgrimes return (ENOSPC); 3971541Srgrimes /* 3981541Srgrimes * Get the starting offset and block map for the first block. 3991541Srgrimes */ 4001541Srgrimes if (start_lvl == 0) { 4011541Srgrimes sbap = &ip->i_db[0]; 4021541Srgrimes soff = start_lbn; 4031541Srgrimes } else { 4041541Srgrimes idp = &start_ap[start_lvl - 1]; 4051541Srgrimes if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 4061541Srgrimes brelse(sbp); 4071541Srgrimes return (ENOSPC); 4081541Srgrimes } 40922521Sdyson sbap = (ufs_daddr_t *)sbp->b_data; 4101541Srgrimes soff = idp->in_off; 4111541Srgrimes } 4121541Srgrimes /* 4131541Srgrimes * Find the preferred location for the cluster. 4141541Srgrimes */ 4151541Srgrimes pref = ffs_blkpref(ip, start_lbn, soff, sbap); 4161541Srgrimes /* 4171541Srgrimes * If the block range spans two block maps, get the second map. 4181541Srgrimes */ 4191541Srgrimes if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 4201541Srgrimes ssize = len; 4211541Srgrimes } else { 4221541Srgrimes#ifdef DIAGNOSTIC 4231541Srgrimes if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 4241541Srgrimes panic("ffs_reallocblk: start == end"); 4251541Srgrimes#endif 4261541Srgrimes ssize = len - (idp->in_off + 1); 4271541Srgrimes if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 4281541Srgrimes goto fail; 42922521Sdyson ebap = (ufs_daddr_t *)ebp->b_data; 4301541Srgrimes } 4311541Srgrimes /* 4321541Srgrimes * Search the block map looking for an allocation of the desired size. 4331541Srgrimes */ 43422521Sdyson if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref, 43512590Sbde len, ffs_clusteralloc)) == 0) 4361541Srgrimes goto fail; 4371541Srgrimes /* 4381541Srgrimes * We have found a new contiguous block. 4391541Srgrimes * 4401541Srgrimes * First we have to replace the old block pointers with the new 4411541Srgrimes * block pointers in the inode and indirect blocks associated 4421541Srgrimes * with the file. 4431541Srgrimes */ 44422521Sdyson#ifdef DEBUG 44522521Sdyson if (prtrealloc) 44622521Sdyson printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number, 44722521Sdyson start_lbn, end_lbn); 44822521Sdyson#endif 4491541Srgrimes blkno = newblk; 4501541Srgrimes for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 4511541Srgrimes if (i == ssize) 4521541Srgrimes bap = ebap; 4531541Srgrimes#ifdef DIAGNOSTIC 45422521Sdyson if (!ffs_checkblk(ip, 45522521Sdyson dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 45622521Sdyson panic("ffs_reallocblks: unallocated block 2"); 45722521Sdyson if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap) 4581541Srgrimes panic("ffs_reallocblks: alloc mismatch"); 4591541Srgrimes#endif 46022521Sdyson#ifdef DEBUG 46122521Sdyson if (prtrealloc) 46222521Sdyson printf(" %d,", *bap); 46322521Sdyson#endif 4641541Srgrimes *bap++ = blkno; 4651541Srgrimes } 4661541Srgrimes /* 4671541Srgrimes * Next we must write out the modified inode and indirect blocks. 4681541Srgrimes * For strict correctness, the writes should be synchronous since 4691541Srgrimes * the old block values may have been written to disk. In practise 4708876Srgrimes * they are almost never written, but if we are concerned about 4711541Srgrimes * strict correctness, the `doasyncfree' flag should be set to zero. 4721541Srgrimes * 4731541Srgrimes * The test on `doasyncfree' should be changed to test a flag 4741541Srgrimes * that shows whether the associated buffers and inodes have 4751541Srgrimes * been written. The flag should be set when the cluster is 4761541Srgrimes * started and cleared whenever the buffer or inode is flushed. 4771541Srgrimes * We can then check below to see if it is set, and do the 4781541Srgrimes * synchronous write only when it has been cleared. 4791541Srgrimes */ 4801541Srgrimes if (sbap != &ip->i_db[0]) { 4811541Srgrimes if (doasyncfree) 4821541Srgrimes bdwrite(sbp); 4831541Srgrimes else 4841541Srgrimes bwrite(sbp); 4851541Srgrimes } else { 4861541Srgrimes ip->i_flag |= IN_CHANGE | IN_UPDATE; 48710269Sbde if (!doasyncfree) { 48824101Sbde gettime(&tv); 48930492Sphk UFS_UPDATE(vp, &tv, &tv, 1); 49010269Sbde } 4911541Srgrimes } 4921541Srgrimes if (ssize < len) 4931541Srgrimes if (doasyncfree) 4941541Srgrimes bdwrite(ebp); 4951541Srgrimes else 4961541Srgrimes bwrite(ebp); 4971541Srgrimes /* 4981541Srgrimes * Last, free the old blocks and assign the new blocks to the buffers. 4991541Srgrimes */ 50022521Sdyson#ifdef DEBUG 50122521Sdyson if (prtrealloc) 50222521Sdyson printf("\n\tnew:"); 50322521Sdyson#endif 5041541Srgrimes for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 5051541Srgrimes ffs_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno), 5061541Srgrimes fs->fs_bsize); 5071541Srgrimes buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 50822521Sdyson#ifdef DEBUG 50922521Sdyson if (!ffs_checkblk(ip, 51022521Sdyson dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 51122521Sdyson panic("ffs_reallocblks: unallocated block 3"); 51222521Sdyson if (prtrealloc) 51322521Sdyson printf(" %d,", blkno); 51422521Sdyson#endif 5151541Srgrimes } 51622521Sdyson#ifdef DEBUG 51722521Sdyson if (prtrealloc) { 51822521Sdyson prtrealloc--; 51922521Sdyson printf("\n"); 52022521Sdyson } 52122521Sdyson#endif 5221541Srgrimes return (0); 5231541Srgrimes 5241541Srgrimesfail: 5251541Srgrimes if (ssize < len) 5261541Srgrimes brelse(ebp); 5271541Srgrimes if (sbap != &ip->i_db[0]) 5281541Srgrimes brelse(sbp); 5291541Srgrimes return (ENOSPC); 53012405Sdyson#endif 5311541Srgrimes} 5321541Srgrimes 5331541Srgrimes/* 5341541Srgrimes * Allocate an inode in the file system. 5358876Srgrimes * 5361541Srgrimes * If allocating a directory, use ffs_dirpref to select the inode. 5371541Srgrimes * If allocating in a directory, the following hierarchy is followed: 5381541Srgrimes * 1) allocate the preferred inode. 5391541Srgrimes * 2) allocate an inode in the same cylinder group. 5401541Srgrimes * 3) quadradically rehash into other cylinder groups, until an 5411541Srgrimes * available inode is located. 5421541Srgrimes * If no inode preference is given the following heirarchy is used 5431541Srgrimes * to allocate an inode: 5441541Srgrimes * 1) allocate an inode in cylinder group 0. 5451541Srgrimes * 2) quadradically rehash into other cylinder groups, until an 5461541Srgrimes * available inode is located. 5471541Srgrimes */ 5481549Srgrimesint 54930474Sphkffs_valloc(pvp, mode, cred, vpp) 55030474Sphk struct vnode *pvp; 55130474Sphk int mode; 55230474Sphk struct ucred *cred; 55330474Sphk struct vnode **vpp; 5541541Srgrimes{ 5551541Srgrimes register struct inode *pip; 5561541Srgrimes register struct fs *fs; 5571541Srgrimes register struct inode *ip; 5581541Srgrimes ino_t ino, ipref; 5591541Srgrimes int cg, error; 5608876Srgrimes 56130474Sphk *vpp = NULL; 5621541Srgrimes pip = VTOI(pvp); 5631541Srgrimes fs = pip->i_fs; 5641541Srgrimes if (fs->fs_cstotal.cs_nifree == 0) 5651541Srgrimes goto noinodes; 5661541Srgrimes 5671541Srgrimes if ((mode & IFMT) == IFDIR) 5681541Srgrimes ipref = ffs_dirpref(fs); 5691541Srgrimes else 5701541Srgrimes ipref = pip->i_number; 5711541Srgrimes if (ipref >= fs->fs_ncg * fs->fs_ipg) 5721541Srgrimes ipref = 0; 5731541Srgrimes cg = ino_to_cg(fs, ipref); 57412861Speter ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, 57512861Speter (allocfcn_t *)ffs_nodealloccg); 5761541Srgrimes if (ino == 0) 5771541Srgrimes goto noinodes; 57830474Sphk error = VFS_VGET(pvp->v_mount, ino, vpp); 5791541Srgrimes if (error) { 58030474Sphk UFS_VFREE(pvp, ino, mode); 5811541Srgrimes return (error); 5821541Srgrimes } 58330474Sphk ip = VTOI(*vpp); 5841541Srgrimes if (ip->i_mode) { 5853487Sphk printf("mode = 0%o, inum = %ld, fs = %s\n", 5861541Srgrimes ip->i_mode, ip->i_number, fs->fs_fsmnt); 5871541Srgrimes panic("ffs_valloc: dup alloc"); 5881541Srgrimes } 5891541Srgrimes if (ip->i_blocks) { /* XXX */ 5903487Sphk printf("free inode %s/%ld had %ld blocks\n", 5911541Srgrimes fs->fs_fsmnt, ino, ip->i_blocks); 5921541Srgrimes ip->i_blocks = 0; 5931541Srgrimes } 5941541Srgrimes ip->i_flags = 0; 5951541Srgrimes /* 5961541Srgrimes * Set up a new generation number for this inode. 5971541Srgrimes */ 59824149Sguido if (ip->i_gen == 0 || ++(ip->i_gen) == 0) 59924149Sguido ip->i_gen = random() / 2 + 1; 6001541Srgrimes return (0); 6011541Srgrimesnoinodes: 60230474Sphk ffs_fserr(fs, cred->cr_uid, "out of inodes"); 6031541Srgrimes uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 6041541Srgrimes return (ENOSPC); 6051541Srgrimes} 6061541Srgrimes 6071541Srgrimes/* 6081541Srgrimes * Find a cylinder to place a directory. 6091541Srgrimes * 6101541Srgrimes * The policy implemented by this algorithm is to select from 6111541Srgrimes * among those cylinder groups with above the average number of 6121541Srgrimes * free inodes, the one with the smallest number of directories. 6131541Srgrimes */ 6141541Srgrimesstatic ino_t 6151541Srgrimesffs_dirpref(fs) 6161541Srgrimes register struct fs *fs; 6171541Srgrimes{ 6181541Srgrimes int cg, minndir, mincg, avgifree; 6191541Srgrimes 6201541Srgrimes avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 6211541Srgrimes minndir = fs->fs_ipg; 6221541Srgrimes mincg = 0; 6231541Srgrimes for (cg = 0; cg < fs->fs_ncg; cg++) 6241541Srgrimes if (fs->fs_cs(fs, cg).cs_ndir < minndir && 6251541Srgrimes fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 6261541Srgrimes mincg = cg; 6271541Srgrimes minndir = fs->fs_cs(fs, cg).cs_ndir; 6281541Srgrimes } 6291541Srgrimes return ((ino_t)(fs->fs_ipg * mincg)); 6301541Srgrimes} 6311541Srgrimes 6321541Srgrimes/* 6331541Srgrimes * Select the desired position for the next block in a file. The file is 6341541Srgrimes * logically divided into sections. The first section is composed of the 6351541Srgrimes * direct blocks. Each additional section contains fs_maxbpg blocks. 6368876Srgrimes * 6371541Srgrimes * If no blocks have been allocated in the first section, the policy is to 6381541Srgrimes * request a block in the same cylinder group as the inode that describes 6391541Srgrimes * the file. If no blocks have been allocated in any other section, the 6401541Srgrimes * policy is to place the section in a cylinder group with a greater than 6411541Srgrimes * average number of free blocks. An appropriate cylinder group is found 6421541Srgrimes * by using a rotor that sweeps the cylinder groups. When a new group of 6431541Srgrimes * blocks is needed, the sweep begins in the cylinder group following the 6441541Srgrimes * cylinder group from which the previous allocation was made. The sweep 6451541Srgrimes * continues until a cylinder group with greater than the average number 6461541Srgrimes * of free blocks is found. If the allocation is for the first block in an 6471541Srgrimes * indirect block, the information on the previous allocation is unavailable; 6481541Srgrimes * here a best guess is made based upon the logical block number being 6491541Srgrimes * allocated. 6508876Srgrimes * 6511541Srgrimes * If a section is already partially allocated, the policy is to 6521541Srgrimes * contiguously allocate fs_maxcontig blocks. The end of one of these 6531541Srgrimes * contiguous blocks and the beginning of the next is physically separated 6541541Srgrimes * so that the disk head will be in transit between them for at least 6551541Srgrimes * fs_rotdelay milliseconds. This is to allow time for the processor to 6561541Srgrimes * schedule another I/O transfer. 6571541Srgrimes */ 65822521Sdysonufs_daddr_t 6591541Srgrimesffs_blkpref(ip, lbn, indx, bap) 6601541Srgrimes struct inode *ip; 66122521Sdyson ufs_daddr_t lbn; 6621541Srgrimes int indx; 66322521Sdyson ufs_daddr_t *bap; 6641541Srgrimes{ 6651541Srgrimes register struct fs *fs; 6661541Srgrimes register int cg; 6671541Srgrimes int avgbfree, startcg; 66822521Sdyson ufs_daddr_t nextblk; 6691541Srgrimes 6701541Srgrimes fs = ip->i_fs; 6711541Srgrimes if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 6721541Srgrimes if (lbn < NDADDR) { 6731541Srgrimes cg = ino_to_cg(fs, ip->i_number); 6741541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 6751541Srgrimes } 6761541Srgrimes /* 6771541Srgrimes * Find a cylinder with greater than average number of 6781541Srgrimes * unused data blocks. 6791541Srgrimes */ 6801541Srgrimes if (indx == 0 || bap[indx - 1] == 0) 6811541Srgrimes startcg = 6821541Srgrimes ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 6831541Srgrimes else 6841541Srgrimes startcg = dtog(fs, bap[indx - 1]) + 1; 6851541Srgrimes startcg %= fs->fs_ncg; 6861541Srgrimes avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 6871541Srgrimes for (cg = startcg; cg < fs->fs_ncg; cg++) 6881541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 6891541Srgrimes fs->fs_cgrotor = cg; 6901541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 6911541Srgrimes } 6921541Srgrimes for (cg = 0; cg <= startcg; cg++) 6931541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 6941541Srgrimes fs->fs_cgrotor = cg; 6951541Srgrimes return (fs->fs_fpg * cg + fs->fs_frag); 6961541Srgrimes } 69717108Sbde return (0); 6981541Srgrimes } 6991541Srgrimes /* 7001541Srgrimes * One or more previous blocks have been laid out. If less 7011541Srgrimes * than fs_maxcontig previous blocks are contiguous, the 7021541Srgrimes * next block is requested contiguously, otherwise it is 7031541Srgrimes * requested rotationally delayed by fs_rotdelay milliseconds. 7041541Srgrimes */ 7051541Srgrimes nextblk = bap[indx - 1] + fs->fs_frag; 70610632Sdg if (fs->fs_rotdelay == 0 || indx < fs->fs_maxcontig || 70710632Sdg bap[indx - fs->fs_maxcontig] + 7081541Srgrimes blkstofrags(fs, fs->fs_maxcontig) != nextblk) 7091541Srgrimes return (nextblk); 71010632Sdg /* 71110632Sdg * Here we convert ms of delay to frags as: 71210632Sdg * (frags) = (ms) * (rev/sec) * (sect/rev) / 71310632Sdg * ((sect/frag) * (ms/sec)) 71410632Sdg * then round up to the next block. 71510632Sdg */ 71610632Sdg nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 71710632Sdg (NSPF(fs) * 1000), fs->fs_frag); 7181541Srgrimes return (nextblk); 7191541Srgrimes} 7201541Srgrimes 7211541Srgrimes/* 7221541Srgrimes * Implement the cylinder overflow algorithm. 7231541Srgrimes * 7241541Srgrimes * The policy implemented by this algorithm is: 7251541Srgrimes * 1) allocate the block in its requested cylinder group. 7261541Srgrimes * 2) quadradically rehash on the cylinder group number. 7271541Srgrimes * 3) brute force search for a free block. 7281541Srgrimes */ 7291541Srgrimes/*VARARGS5*/ 7301541Srgrimesstatic u_long 7311541Srgrimesffs_hashalloc(ip, cg, pref, size, allocator) 7321541Srgrimes struct inode *ip; 7331541Srgrimes int cg; 7341541Srgrimes long pref; 7351541Srgrimes int size; /* size for data blocks, mode for inodes */ 73612590Sbde allocfcn_t *allocator; 7371541Srgrimes{ 7381541Srgrimes register struct fs *fs; 73912590Sbde long result; /* XXX why not same type as we return? */ 7401541Srgrimes int i, icg = cg; 7411541Srgrimes 7421541Srgrimes fs = ip->i_fs; 7431541Srgrimes /* 7441541Srgrimes * 1: preferred cylinder group 7451541Srgrimes */ 7461541Srgrimes result = (*allocator)(ip, cg, pref, size); 7471541Srgrimes if (result) 7481541Srgrimes return (result); 7491541Srgrimes /* 7501541Srgrimes * 2: quadratic rehash 7511541Srgrimes */ 7521541Srgrimes for (i = 1; i < fs->fs_ncg; i *= 2) { 7531541Srgrimes cg += i; 7541541Srgrimes if (cg >= fs->fs_ncg) 7551541Srgrimes cg -= fs->fs_ncg; 7561541Srgrimes result = (*allocator)(ip, cg, 0, size); 7571541Srgrimes if (result) 7581541Srgrimes return (result); 7591541Srgrimes } 7601541Srgrimes /* 7611541Srgrimes * 3: brute force search 7621541Srgrimes * Note that we start at i == 2, since 0 was checked initially, 7631541Srgrimes * and 1 is always checked in the quadratic rehash. 7641541Srgrimes */ 7651541Srgrimes cg = (icg + 2) % fs->fs_ncg; 7661541Srgrimes for (i = 2; i < fs->fs_ncg; i++) { 7671541Srgrimes result = (*allocator)(ip, cg, 0, size); 7681541Srgrimes if (result) 7691541Srgrimes return (result); 7701541Srgrimes cg++; 7711541Srgrimes if (cg == fs->fs_ncg) 7721541Srgrimes cg = 0; 7731541Srgrimes } 77412590Sbde return (0); 7751541Srgrimes} 7761541Srgrimes 7771541Srgrimes/* 7781541Srgrimes * Determine whether a fragment can be extended. 7791541Srgrimes * 7808876Srgrimes * Check to see if the necessary fragments are available, and 7811541Srgrimes * if they are, allocate them. 7821541Srgrimes */ 78322521Sdysonstatic ufs_daddr_t 7841541Srgrimesffs_fragextend(ip, cg, bprev, osize, nsize) 7851541Srgrimes struct inode *ip; 7861541Srgrimes int cg; 7871541Srgrimes long bprev; 7881541Srgrimes int osize, nsize; 7891541Srgrimes{ 7901541Srgrimes register struct fs *fs; 7911541Srgrimes register struct cg *cgp; 7921541Srgrimes struct buf *bp; 7931541Srgrimes long bno; 7941541Srgrimes int frags, bbase; 7951541Srgrimes int i, error; 7961541Srgrimes 7971541Srgrimes fs = ip->i_fs; 7981541Srgrimes if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 79917108Sbde return (0); 8001541Srgrimes frags = numfrags(fs, nsize); 8011541Srgrimes bbase = fragnum(fs, bprev); 8021541Srgrimes if (bbase > fragnum(fs, (bprev + frags - 1))) { 8031541Srgrimes /* cannot extend across a block boundary */ 80417108Sbde return (0); 8051541Srgrimes } 8061541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 8071541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 8081541Srgrimes if (error) { 8091541Srgrimes brelse(bp); 81017108Sbde return (0); 8111541Srgrimes } 8121541Srgrimes cgp = (struct cg *)bp->b_data; 8131541Srgrimes if (!cg_chkmagic(cgp)) { 8141541Srgrimes brelse(bp); 81517108Sbde return (0); 8161541Srgrimes } 8171541Srgrimes cgp->cg_time = time.tv_sec; 8181541Srgrimes bno = dtogd(fs, bprev); 8191541Srgrimes for (i = numfrags(fs, osize); i < frags; i++) 8201541Srgrimes if (isclr(cg_blksfree(cgp), bno + i)) { 8211541Srgrimes brelse(bp); 82217108Sbde return (0); 8231541Srgrimes } 8241541Srgrimes /* 8251541Srgrimes * the current fragment can be extended 8261541Srgrimes * deduct the count on fragment being extended into 8271541Srgrimes * increase the count on the remaining fragment (if any) 8281541Srgrimes * allocate the extended piece 8291541Srgrimes */ 8301541Srgrimes for (i = frags; i < fs->fs_frag - bbase; i++) 8311541Srgrimes if (isclr(cg_blksfree(cgp), bno + i)) 8321541Srgrimes break; 8331541Srgrimes cgp->cg_frsum[i - numfrags(fs, osize)]--; 8341541Srgrimes if (i != frags) 8351541Srgrimes cgp->cg_frsum[i - frags]++; 8361541Srgrimes for (i = numfrags(fs, osize); i < frags; i++) { 8371541Srgrimes clrbit(cg_blksfree(cgp), bno + i); 8381541Srgrimes cgp->cg_cs.cs_nffree--; 8391541Srgrimes fs->fs_cstotal.cs_nffree--; 8401541Srgrimes fs->fs_cs(fs, cg).cs_nffree--; 8411541Srgrimes } 8421541Srgrimes fs->fs_fmod = 1; 8431541Srgrimes bdwrite(bp); 8441541Srgrimes return (bprev); 8451541Srgrimes} 8461541Srgrimes 8471541Srgrimes/* 8481541Srgrimes * Determine whether a block can be allocated. 8491541Srgrimes * 8501541Srgrimes * Check to see if a block of the appropriate size is available, 8511541Srgrimes * and if it is, allocate it. 8521541Srgrimes */ 85322521Sdysonstatic ufs_daddr_t 8541541Srgrimesffs_alloccg(ip, cg, bpref, size) 8551541Srgrimes struct inode *ip; 8561541Srgrimes int cg; 85722521Sdyson ufs_daddr_t bpref; 8581541Srgrimes int size; 8591541Srgrimes{ 8601541Srgrimes register struct fs *fs; 8611541Srgrimes register struct cg *cgp; 8621541Srgrimes struct buf *bp; 8631541Srgrimes register int i; 8641541Srgrimes int error, bno, frags, allocsiz; 8651541Srgrimes 8661541Srgrimes fs = ip->i_fs; 8671541Srgrimes if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 86817108Sbde return (0); 8691541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 8701541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 8711541Srgrimes if (error) { 8721541Srgrimes brelse(bp); 87317108Sbde return (0); 8741541Srgrimes } 8751541Srgrimes cgp = (struct cg *)bp->b_data; 8761541Srgrimes if (!cg_chkmagic(cgp) || 8771541Srgrimes (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 8781541Srgrimes brelse(bp); 87917108Sbde return (0); 8801541Srgrimes } 8811541Srgrimes cgp->cg_time = time.tv_sec; 8821541Srgrimes if (size == fs->fs_bsize) { 8831541Srgrimes bno = ffs_alloccgblk(fs, cgp, bpref); 8841541Srgrimes bdwrite(bp); 8851541Srgrimes return (bno); 8861541Srgrimes } 8871541Srgrimes /* 8881541Srgrimes * check to see if any fragments are already available 8891541Srgrimes * allocsiz is the size which will be allocated, hacking 8901541Srgrimes * it down to a smaller size if necessary 8911541Srgrimes */ 8921541Srgrimes frags = numfrags(fs, size); 8931541Srgrimes for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 8941541Srgrimes if (cgp->cg_frsum[allocsiz] != 0) 8951541Srgrimes break; 8961541Srgrimes if (allocsiz == fs->fs_frag) { 8971541Srgrimes /* 8988876Srgrimes * no fragments were available, so a block will be 8991541Srgrimes * allocated, and hacked up 9001541Srgrimes */ 9011541Srgrimes if (cgp->cg_cs.cs_nbfree == 0) { 9021541Srgrimes brelse(bp); 90317108Sbde return (0); 9041541Srgrimes } 9051541Srgrimes bno = ffs_alloccgblk(fs, cgp, bpref); 9061541Srgrimes bpref = dtogd(fs, bno); 9071541Srgrimes for (i = frags; i < fs->fs_frag; i++) 9081541Srgrimes setbit(cg_blksfree(cgp), bpref + i); 9091541Srgrimes i = fs->fs_frag - frags; 9101541Srgrimes cgp->cg_cs.cs_nffree += i; 9111541Srgrimes fs->fs_cstotal.cs_nffree += i; 9121541Srgrimes fs->fs_cs(fs, cg).cs_nffree += i; 9131541Srgrimes fs->fs_fmod = 1; 9141541Srgrimes cgp->cg_frsum[i]++; 9151541Srgrimes bdwrite(bp); 9161541Srgrimes return (bno); 9171541Srgrimes } 9181541Srgrimes bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 9191541Srgrimes if (bno < 0) { 9201541Srgrimes brelse(bp); 92117108Sbde return (0); 9221541Srgrimes } 9231541Srgrimes for (i = 0; i < frags; i++) 9241541Srgrimes clrbit(cg_blksfree(cgp), bno + i); 9251541Srgrimes cgp->cg_cs.cs_nffree -= frags; 9261541Srgrimes fs->fs_cstotal.cs_nffree -= frags; 9271541Srgrimes fs->fs_cs(fs, cg).cs_nffree -= frags; 9281541Srgrimes fs->fs_fmod = 1; 9291541Srgrimes cgp->cg_frsum[allocsiz]--; 9301541Srgrimes if (frags != allocsiz) 9311541Srgrimes cgp->cg_frsum[allocsiz - frags]++; 9321541Srgrimes bdwrite(bp); 9331541Srgrimes return (cg * fs->fs_fpg + bno); 9341541Srgrimes} 9351541Srgrimes 9361541Srgrimes/* 9371541Srgrimes * Allocate a block in a cylinder group. 9381541Srgrimes * 9391541Srgrimes * This algorithm implements the following policy: 9401541Srgrimes * 1) allocate the requested block. 9411541Srgrimes * 2) allocate a rotationally optimal block in the same cylinder. 9421541Srgrimes * 3) allocate the next available block on the block rotor for the 9431541Srgrimes * specified cylinder group. 9441541Srgrimes * Note that this routine only allocates fs_bsize blocks; these 9451541Srgrimes * blocks may be fragmented by the routine that allocates them. 9461541Srgrimes */ 94722521Sdysonstatic ufs_daddr_t 9481541Srgrimesffs_alloccgblk(fs, cgp, bpref) 9491541Srgrimes register struct fs *fs; 9501541Srgrimes register struct cg *cgp; 95122521Sdyson ufs_daddr_t bpref; 9521541Srgrimes{ 95322521Sdyson ufs_daddr_t bno, blkno; 9541541Srgrimes int cylno, pos, delta; 9551541Srgrimes short *cylbp; 9561541Srgrimes register int i; 9571541Srgrimes 9581541Srgrimes if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) { 9591541Srgrimes bpref = cgp->cg_rotor; 9601541Srgrimes goto norot; 9611541Srgrimes } 9621541Srgrimes bpref = blknum(fs, bpref); 9631541Srgrimes bpref = dtogd(fs, bpref); 9641541Srgrimes /* 9651541Srgrimes * if the requested block is available, use it 9661541Srgrimes */ 9671541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) { 9681541Srgrimes bno = bpref; 9691541Srgrimes goto gotit; 9701541Srgrimes } 9716769Sse if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) { 9721541Srgrimes /* 9731541Srgrimes * Block layout information is not available. 9741541Srgrimes * Leaving bpref unchanged means we take the 9758876Srgrimes * next available free block following the one 9761541Srgrimes * we just allocated. Hopefully this will at 9771541Srgrimes * least hit a track cache on drives of unknown 9781541Srgrimes * geometry (e.g. SCSI). 9791541Srgrimes */ 9801541Srgrimes goto norot; 9811541Srgrimes } 9821541Srgrimes /* 9836769Sse * check for a block available on the same cylinder 9846769Sse */ 9856769Sse cylno = cbtocylno(fs, bpref); 9866769Sse if (cg_blktot(cgp)[cylno] == 0) 9876769Sse goto norot; 9886769Sse /* 9898876Srgrimes * check the summary information to see if a block is 9901541Srgrimes * available in the requested cylinder starting at the 9911541Srgrimes * requested rotational position and proceeding around. 9921541Srgrimes */ 9931541Srgrimes cylbp = cg_blks(fs, cgp, cylno); 9941541Srgrimes pos = cbtorpos(fs, bpref); 9951541Srgrimes for (i = pos; i < fs->fs_nrpos; i++) 9961541Srgrimes if (cylbp[i] > 0) 9971541Srgrimes break; 9981541Srgrimes if (i == fs->fs_nrpos) 9991541Srgrimes for (i = 0; i < pos; i++) 10001541Srgrimes if (cylbp[i] > 0) 10011541Srgrimes break; 10021541Srgrimes if (cylbp[i] > 0) { 10031541Srgrimes /* 10041541Srgrimes * found a rotational position, now find the actual 10051541Srgrimes * block. A panic if none is actually there. 10061541Srgrimes */ 10071541Srgrimes pos = cylno % fs->fs_cpc; 10081541Srgrimes bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 10091541Srgrimes if (fs_postbl(fs, pos)[i] == -1) { 10101541Srgrimes printf("pos = %d, i = %d, fs = %s\n", 10111541Srgrimes pos, i, fs->fs_fsmnt); 10121541Srgrimes panic("ffs_alloccgblk: cyl groups corrupted"); 10131541Srgrimes } 10141541Srgrimes for (i = fs_postbl(fs, pos)[i];; ) { 10151541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), bno + i)) { 10161541Srgrimes bno = blkstofrags(fs, (bno + i)); 10171541Srgrimes goto gotit; 10181541Srgrimes } 10191541Srgrimes delta = fs_rotbl(fs)[i]; 10201541Srgrimes if (delta <= 0 || 10211541Srgrimes delta + i > fragstoblks(fs, fs->fs_fpg)) 10221541Srgrimes break; 10231541Srgrimes i += delta; 10241541Srgrimes } 10251541Srgrimes printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 10261541Srgrimes panic("ffs_alloccgblk: can't find blk in cyl"); 10271541Srgrimes } 10281541Srgrimesnorot: 10291541Srgrimes /* 10301541Srgrimes * no blocks in the requested cylinder, so take next 10311541Srgrimes * available one in this cylinder group. 10321541Srgrimes */ 10331541Srgrimes bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 10341541Srgrimes if (bno < 0) 103517108Sbde return (0); 10361541Srgrimes cgp->cg_rotor = bno; 10371541Srgrimesgotit: 10381541Srgrimes blkno = fragstoblks(fs, bno); 10391541Srgrimes ffs_clrblock(fs, cg_blksfree(cgp), (long)blkno); 10401541Srgrimes ffs_clusteracct(fs, cgp, blkno, -1); 10411541Srgrimes cgp->cg_cs.cs_nbfree--; 10421541Srgrimes fs->fs_cstotal.cs_nbfree--; 10431541Srgrimes fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 10441541Srgrimes cylno = cbtocylno(fs, bno); 10451541Srgrimes cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 10461541Srgrimes cg_blktot(cgp)[cylno]--; 10471541Srgrimes fs->fs_fmod = 1; 10481541Srgrimes return (cgp->cg_cgx * fs->fs_fpg + bno); 10491541Srgrimes} 10501541Srgrimes 105112911Sphk#ifdef notyet 10521541Srgrimes/* 10531541Srgrimes * Determine whether a cluster can be allocated. 10541541Srgrimes * 10551541Srgrimes * We do not currently check for optimal rotational layout if there 10561541Srgrimes * are multiple choices in the same cylinder group. Instead we just 10571541Srgrimes * take the first one that we find following bpref. 10581541Srgrimes */ 105922521Sdysonstatic ufs_daddr_t 10601541Srgrimesffs_clusteralloc(ip, cg, bpref, len) 10611541Srgrimes struct inode *ip; 10621541Srgrimes int cg; 106322521Sdyson ufs_daddr_t bpref; 10641541Srgrimes int len; 10651541Srgrimes{ 10661541Srgrimes register struct fs *fs; 10671541Srgrimes register struct cg *cgp; 10681541Srgrimes struct buf *bp; 106922521Sdyson int i, got, run, bno, bit, map; 10701541Srgrimes u_char *mapp; 107122521Sdyson int32_t *lp; 10721541Srgrimes 10731541Srgrimes fs = ip->i_fs; 107422521Sdyson if (fs->fs_maxcluster[cg] < len) 10751541Srgrimes return (NULL); 10761541Srgrimes if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 10771541Srgrimes NOCRED, &bp)) 10781541Srgrimes goto fail; 10791541Srgrimes cgp = (struct cg *)bp->b_data; 10801541Srgrimes if (!cg_chkmagic(cgp)) 10811541Srgrimes goto fail; 10821541Srgrimes /* 10831541Srgrimes * Check to see if a cluster of the needed size (or bigger) is 10841541Srgrimes * available in this cylinder group. 10851541Srgrimes */ 108622521Sdyson lp = &cg_clustersum(cgp)[len]; 10871541Srgrimes for (i = len; i <= fs->fs_contigsumsize; i++) 108822521Sdyson if (*lp++ > 0) 10891541Srgrimes break; 109022521Sdyson if (i > fs->fs_contigsumsize) { 109122521Sdyson /* 109222521Sdyson * This is the first time looking for a cluster in this 109322521Sdyson * cylinder group. Update the cluster summary information 109422521Sdyson * to reflect the true maximum sized cluster so that 109522521Sdyson * future cluster allocation requests can avoid reading 109622521Sdyson * the cylinder group map only to find no clusters. 109722521Sdyson */ 109822521Sdyson lp = &cg_clustersum(cgp)[len - 1]; 109922521Sdyson for (i = len - 1; i > 0; i--) 110022521Sdyson if (*lp-- > 0) 110122521Sdyson break; 110222521Sdyson fs->fs_maxcluster[cg] = i; 11031541Srgrimes goto fail; 110422521Sdyson } 11051541Srgrimes /* 11061541Srgrimes * Search the cluster map to find a big enough cluster. 11071541Srgrimes * We take the first one that we find, even if it is larger 11081541Srgrimes * than we need as we prefer to get one close to the previous 11091541Srgrimes * block allocation. We do not search before the current 11101541Srgrimes * preference point as we do not want to allocate a block 11111541Srgrimes * that is allocated before the previous one (as we will 11121541Srgrimes * then have to wait for another pass of the elevator 11131541Srgrimes * algorithm before it will be read). We prefer to fail and 11141541Srgrimes * be recalled to try an allocation in the next cylinder group. 11151541Srgrimes */ 11161541Srgrimes if (dtog(fs, bpref) != cg) 11171541Srgrimes bpref = 0; 11181541Srgrimes else 11191541Srgrimes bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 11201541Srgrimes mapp = &cg_clustersfree(cgp)[bpref / NBBY]; 11211541Srgrimes map = *mapp++; 11221541Srgrimes bit = 1 << (bpref % NBBY); 112322521Sdyson for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) { 11241541Srgrimes if ((map & bit) == 0) { 11251541Srgrimes run = 0; 11261541Srgrimes } else { 11271541Srgrimes run++; 11281541Srgrimes if (run == len) 11291541Srgrimes break; 11301541Srgrimes } 113122521Sdyson if ((got & (NBBY - 1)) != (NBBY - 1)) { 11321541Srgrimes bit <<= 1; 11331541Srgrimes } else { 11341541Srgrimes map = *mapp++; 11351541Srgrimes bit = 1; 11361541Srgrimes } 11371541Srgrimes } 113827890Sphk if (got >= cgp->cg_nclusterblks) 11391541Srgrimes goto fail; 11401541Srgrimes /* 11411541Srgrimes * Allocate the cluster that we have found. 11421541Srgrimes */ 114322521Sdyson for (i = 1; i <= len; i++) 114422521Sdyson if (!ffs_isblock(fs, cg_blksfree(cgp), got - run + i)) 114522521Sdyson panic("ffs_clusteralloc: map mismatch"); 114622521Sdyson bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1); 114722521Sdyson if (dtog(fs, bno) != cg) 114822521Sdyson panic("ffs_clusteralloc: allocated out of group"); 11491541Srgrimes len = blkstofrags(fs, len); 11501541Srgrimes for (i = 0; i < len; i += fs->fs_frag) 115122521Sdyson if ((got = ffs_alloccgblk(fs, cgp, bno + i)) != bno + i) 11521541Srgrimes panic("ffs_clusteralloc: lost block"); 11539980Sdg bdwrite(bp); 11541541Srgrimes return (bno); 11551541Srgrimes 11561541Srgrimesfail: 11571541Srgrimes brelse(bp); 11581541Srgrimes return (0); 11591541Srgrimes} 116012911Sphk#endif 11611541Srgrimes 11621541Srgrimes/* 11631541Srgrimes * Determine whether an inode can be allocated. 11641541Srgrimes * 11651541Srgrimes * Check to see if an inode is available, and if it is, 11661541Srgrimes * allocate it using the following policy: 11671541Srgrimes * 1) allocate the requested inode. 11681541Srgrimes * 2) allocate the next available inode after the requested 11691541Srgrimes * inode in the specified cylinder group. 11701541Srgrimes */ 11711541Srgrimesstatic ino_t 11721541Srgrimesffs_nodealloccg(ip, cg, ipref, mode) 11731541Srgrimes struct inode *ip; 11741541Srgrimes int cg; 117522521Sdyson ufs_daddr_t ipref; 11761541Srgrimes int mode; 11771541Srgrimes{ 11781541Srgrimes register struct fs *fs; 11791541Srgrimes register struct cg *cgp; 11801541Srgrimes struct buf *bp; 11811541Srgrimes int error, start, len, loc, map, i; 11821541Srgrimes 11831541Srgrimes fs = ip->i_fs; 11841541Srgrimes if (fs->fs_cs(fs, cg).cs_nifree == 0) 118517108Sbde return (0); 11861541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 11871541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 11881541Srgrimes if (error) { 11891541Srgrimes brelse(bp); 119017108Sbde return (0); 11911541Srgrimes } 11921541Srgrimes cgp = (struct cg *)bp->b_data; 11931541Srgrimes if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 11941541Srgrimes brelse(bp); 119517108Sbde return (0); 11961541Srgrimes } 11971541Srgrimes cgp->cg_time = time.tv_sec; 11981541Srgrimes if (ipref) { 11991541Srgrimes ipref %= fs->fs_ipg; 12001541Srgrimes if (isclr(cg_inosused(cgp), ipref)) 12011541Srgrimes goto gotit; 12021541Srgrimes } 12031541Srgrimes start = cgp->cg_irotor / NBBY; 12041541Srgrimes len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 12051541Srgrimes loc = skpc(0xff, len, &cg_inosused(cgp)[start]); 12061541Srgrimes if (loc == 0) { 12071541Srgrimes len = start + 1; 12081541Srgrimes start = 0; 12091541Srgrimes loc = skpc(0xff, len, &cg_inosused(cgp)[0]); 12101541Srgrimes if (loc == 0) { 12116357Sphk printf("cg = %d, irotor = %ld, fs = %s\n", 12121541Srgrimes cg, cgp->cg_irotor, fs->fs_fsmnt); 12131541Srgrimes panic("ffs_nodealloccg: map corrupted"); 12141541Srgrimes /* NOTREACHED */ 12151541Srgrimes } 12161541Srgrimes } 12171541Srgrimes i = start + len - loc; 12181541Srgrimes map = cg_inosused(cgp)[i]; 12191541Srgrimes ipref = i * NBBY; 12201541Srgrimes for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 12211541Srgrimes if ((map & i) == 0) { 12221541Srgrimes cgp->cg_irotor = ipref; 12231541Srgrimes goto gotit; 12241541Srgrimes } 12251541Srgrimes } 12261541Srgrimes printf("fs = %s\n", fs->fs_fsmnt); 12271541Srgrimes panic("ffs_nodealloccg: block not in map"); 12281541Srgrimes /* NOTREACHED */ 12291541Srgrimesgotit: 12301541Srgrimes setbit(cg_inosused(cgp), ipref); 12311541Srgrimes cgp->cg_cs.cs_nifree--; 12321541Srgrimes fs->fs_cstotal.cs_nifree--; 12331541Srgrimes fs->fs_cs(fs, cg).cs_nifree--; 12341541Srgrimes fs->fs_fmod = 1; 12351541Srgrimes if ((mode & IFMT) == IFDIR) { 12361541Srgrimes cgp->cg_cs.cs_ndir++; 12371541Srgrimes fs->fs_cstotal.cs_ndir++; 12381541Srgrimes fs->fs_cs(fs, cg).cs_ndir++; 12391541Srgrimes } 12401541Srgrimes bdwrite(bp); 12411541Srgrimes return (cg * fs->fs_ipg + ipref); 12421541Srgrimes} 12431541Srgrimes 12441541Srgrimes/* 12451541Srgrimes * Free a block or fragment. 12461541Srgrimes * 12471541Srgrimes * The specified block or fragment is placed back in the 12488876Srgrimes * free map. If a fragment is deallocated, a possible 12491541Srgrimes * block reassembly is checked. 12501541Srgrimes */ 12511549Srgrimesvoid 12521541Srgrimesffs_blkfree(ip, bno, size) 12531541Srgrimes register struct inode *ip; 125422521Sdyson ufs_daddr_t bno; 12551541Srgrimes long size; 12561541Srgrimes{ 12571541Srgrimes register struct fs *fs; 12581541Srgrimes register struct cg *cgp; 12591541Srgrimes struct buf *bp; 126022521Sdyson ufs_daddr_t blkno; 12611541Srgrimes int i, error, cg, blk, frags, bbase; 12621541Srgrimes 12631541Srgrimes fs = ip->i_fs; 12641541Srgrimes if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 12653487Sphk printf("dev = 0x%lx, bsize = %ld, size = %ld, fs = %s\n", 12663487Sphk (u_long)ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 126723560Smpp panic("ffs_blkfree: bad size"); 12681541Srgrimes } 12691541Srgrimes cg = dtog(fs, bno); 12701541Srgrimes if ((u_int)bno >= fs->fs_size) { 12716357Sphk printf("bad block %ld, ino %ld\n", bno, ip->i_number); 12721541Srgrimes ffs_fserr(fs, ip->i_uid, "bad block"); 12731541Srgrimes return; 12741541Srgrimes } 12751541Srgrimes error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 12761541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 12771541Srgrimes if (error) { 12781541Srgrimes brelse(bp); 12791541Srgrimes return; 12801541Srgrimes } 12811541Srgrimes cgp = (struct cg *)bp->b_data; 12821541Srgrimes if (!cg_chkmagic(cgp)) { 12831541Srgrimes brelse(bp); 12841541Srgrimes return; 12851541Srgrimes } 12861541Srgrimes cgp->cg_time = time.tv_sec; 12871541Srgrimes bno = dtogd(fs, bno); 12881541Srgrimes if (size == fs->fs_bsize) { 12891541Srgrimes blkno = fragstoblks(fs, bno); 12901541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 12916357Sphk printf("dev = 0x%lx, block = %ld, fs = %s\n", 12926357Sphk (u_long) ip->i_dev, bno, fs->fs_fsmnt); 129323560Smpp panic("ffs_blkfree: freeing free block"); 12941541Srgrimes } 12951541Srgrimes ffs_setblock(fs, cg_blksfree(cgp), blkno); 12961541Srgrimes ffs_clusteracct(fs, cgp, blkno, 1); 12971541Srgrimes cgp->cg_cs.cs_nbfree++; 12981541Srgrimes fs->fs_cstotal.cs_nbfree++; 12991541Srgrimes fs->fs_cs(fs, cg).cs_nbfree++; 13001541Srgrimes i = cbtocylno(fs, bno); 13011541Srgrimes cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; 13021541Srgrimes cg_blktot(cgp)[i]++; 13031541Srgrimes } else { 13041541Srgrimes bbase = bno - fragnum(fs, bno); 13051541Srgrimes /* 13061541Srgrimes * decrement the counts associated with the old frags 13071541Srgrimes */ 13081541Srgrimes blk = blkmap(fs, cg_blksfree(cgp), bbase); 13091541Srgrimes ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 13101541Srgrimes /* 13111541Srgrimes * deallocate the fragment 13121541Srgrimes */ 13131541Srgrimes frags = numfrags(fs, size); 13141541Srgrimes for (i = 0; i < frags; i++) { 13151541Srgrimes if (isset(cg_blksfree(cgp), bno + i)) { 13166357Sphk printf("dev = 0x%lx, block = %ld, fs = %s\n", 13176357Sphk (u_long) ip->i_dev, bno + i, fs->fs_fsmnt); 131823560Smpp panic("ffs_blkfree: freeing free frag"); 13191541Srgrimes } 13201541Srgrimes setbit(cg_blksfree(cgp), bno + i); 13211541Srgrimes } 13221541Srgrimes cgp->cg_cs.cs_nffree += i; 13231541Srgrimes fs->fs_cstotal.cs_nffree += i; 13241541Srgrimes fs->fs_cs(fs, cg).cs_nffree += i; 13251541Srgrimes /* 13261541Srgrimes * add back in counts associated with the new frags 13271541Srgrimes */ 13281541Srgrimes blk = blkmap(fs, cg_blksfree(cgp), bbase); 13291541Srgrimes ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 13301541Srgrimes /* 13311541Srgrimes * if a complete block has been reassembled, account for it 13321541Srgrimes */ 13331541Srgrimes blkno = fragstoblks(fs, bbase); 13341541Srgrimes if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 13351541Srgrimes cgp->cg_cs.cs_nffree -= fs->fs_frag; 13361541Srgrimes fs->fs_cstotal.cs_nffree -= fs->fs_frag; 13371541Srgrimes fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 13381541Srgrimes ffs_clusteracct(fs, cgp, blkno, 1); 13391541Srgrimes cgp->cg_cs.cs_nbfree++; 13401541Srgrimes fs->fs_cstotal.cs_nbfree++; 13411541Srgrimes fs->fs_cs(fs, cg).cs_nbfree++; 13421541Srgrimes i = cbtocylno(fs, bbase); 13431541Srgrimes cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 13441541Srgrimes cg_blktot(cgp)[i]++; 13451541Srgrimes } 13461541Srgrimes } 13471541Srgrimes fs->fs_fmod = 1; 13481541Srgrimes bdwrite(bp); 13491541Srgrimes} 13501541Srgrimes 135122521Sdyson#ifdef DIAGNOSTIC 13521541Srgrimes/* 135322521Sdyson * Verify allocation of a block or fragment. Returns true if block or 135422521Sdyson * fragment is allocated, false if it is free. 135522521Sdyson */ 135622544Smppint 135722521Sdysonffs_checkblk(ip, bno, size) 135822521Sdyson struct inode *ip; 135922521Sdyson ufs_daddr_t bno; 136022521Sdyson long size; 136122521Sdyson{ 136222521Sdyson struct fs *fs; 136322521Sdyson struct cg *cgp; 136422521Sdyson struct buf *bp; 136522521Sdyson int i, error, frags, free; 136622521Sdyson 136722521Sdyson fs = ip->i_fs; 136822521Sdyson if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 136922521Sdyson printf("bsize = %d, size = %d, fs = %s\n", 137022521Sdyson fs->fs_bsize, size, fs->fs_fsmnt); 137122544Smpp panic("ffs_checkblk: bad size"); 137222521Sdyson } 137322521Sdyson if ((u_int)bno >= fs->fs_size) 137422544Smpp panic("ffs_checkblk: bad block %d", bno); 137522521Sdyson error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))), 137622521Sdyson (int)fs->fs_cgsize, NOCRED, &bp); 137722544Smpp if (error) 137822544Smpp panic("ffs_checkblk: cg bread failed"); 137922521Sdyson cgp = (struct cg *)bp->b_data; 138022544Smpp if (!cg_chkmagic(cgp)) 138122544Smpp panic("ffs_checkblk: cg magic mismatch"); 138222521Sdyson bno = dtogd(fs, bno); 138322521Sdyson if (size == fs->fs_bsize) { 138422521Sdyson free = ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno)); 138522521Sdyson } else { 138622521Sdyson frags = numfrags(fs, size); 138722521Sdyson for (free = 0, i = 0; i < frags; i++) 138822521Sdyson if (isset(cg_blksfree(cgp), bno + i)) 138922521Sdyson free++; 139022521Sdyson if (free != 0 && free != frags) 139122544Smpp panic("ffs_checkblk: partially free fragment"); 139222521Sdyson } 139322521Sdyson brelse(bp); 139422521Sdyson return (!free); 139522521Sdyson} 139622521Sdyson#endif /* DIAGNOSTIC */ 139722521Sdyson 139822521Sdyson/* 13991541Srgrimes * Free an inode. 14001541Srgrimes * 14011541Srgrimes * The specified inode is placed back in the free map. 14021541Srgrimes */ 14031541Srgrimesint 140430474Sphkffs_vfree(pvp, ino, mode) 140530474Sphk struct vnode *pvp; 140630474Sphk ino_t ino; 140730474Sphk int mode; 14081541Srgrimes{ 14091541Srgrimes register struct fs *fs; 14101541Srgrimes register struct cg *cgp; 14111541Srgrimes register struct inode *pip; 14121541Srgrimes struct buf *bp; 14131541Srgrimes int error, cg; 14141541Srgrimes 141530474Sphk pip = VTOI(pvp); 14161541Srgrimes fs = pip->i_fs; 14171541Srgrimes if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 141823560Smpp panic("ffs_vfree: range: dev = 0x%x, ino = %d, fs = %s", 14191541Srgrimes pip->i_dev, ino, fs->fs_fsmnt); 14201541Srgrimes cg = ino_to_cg(fs, ino); 14211541Srgrimes error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 14221541Srgrimes (int)fs->fs_cgsize, NOCRED, &bp); 14231541Srgrimes if (error) { 14241541Srgrimes brelse(bp); 14251541Srgrimes return (0); 14261541Srgrimes } 14271541Srgrimes cgp = (struct cg *)bp->b_data; 14281541Srgrimes if (!cg_chkmagic(cgp)) { 14291541Srgrimes brelse(bp); 14301541Srgrimes return (0); 14311541Srgrimes } 14321541Srgrimes cgp->cg_time = time.tv_sec; 14331541Srgrimes ino %= fs->fs_ipg; 14341541Srgrimes if (isclr(cg_inosused(cgp), ino)) { 14356357Sphk printf("dev = 0x%lx, ino = %ld, fs = %s\n", 14363487Sphk (u_long)pip->i_dev, ino, fs->fs_fsmnt); 14371541Srgrimes if (fs->fs_ronly == 0) 143823560Smpp panic("ffs_vfree: freeing free inode"); 14391541Srgrimes } 14401541Srgrimes clrbit(cg_inosused(cgp), ino); 14411541Srgrimes if (ino < cgp->cg_irotor) 14421541Srgrimes cgp->cg_irotor = ino; 14431541Srgrimes cgp->cg_cs.cs_nifree++; 14441541Srgrimes fs->fs_cstotal.cs_nifree++; 14451541Srgrimes fs->fs_cs(fs, cg).cs_nifree++; 144630474Sphk if ((mode & IFMT) == IFDIR) { 14471541Srgrimes cgp->cg_cs.cs_ndir--; 14481541Srgrimes fs->fs_cstotal.cs_ndir--; 14491541Srgrimes fs->fs_cs(fs, cg).cs_ndir--; 14501541Srgrimes } 14511541Srgrimes fs->fs_fmod = 1; 14521541Srgrimes bdwrite(bp); 14531541Srgrimes return (0); 14541541Srgrimes} 14551541Srgrimes 14561541Srgrimes/* 14571541Srgrimes * Find a block of the specified size in the specified cylinder group. 14581541Srgrimes * 14591541Srgrimes * It is a panic if a request is made to find a block if none are 14601541Srgrimes * available. 14611541Srgrimes */ 146222521Sdysonstatic ufs_daddr_t 14631541Srgrimesffs_mapsearch(fs, cgp, bpref, allocsiz) 14641541Srgrimes register struct fs *fs; 14651541Srgrimes register struct cg *cgp; 146622521Sdyson ufs_daddr_t bpref; 14671541Srgrimes int allocsiz; 14681541Srgrimes{ 146922521Sdyson ufs_daddr_t bno; 14701541Srgrimes int start, len, loc, i; 14711541Srgrimes int blk, field, subfield, pos; 14721541Srgrimes 14731541Srgrimes /* 14741541Srgrimes * find the fragment by searching through the free block 14751541Srgrimes * map for an appropriate bit pattern 14761541Srgrimes */ 14771541Srgrimes if (bpref) 14781541Srgrimes start = dtogd(fs, bpref) / NBBY; 14791541Srgrimes else 14801541Srgrimes start = cgp->cg_frotor / NBBY; 14811541Srgrimes len = howmany(fs->fs_fpg, NBBY) - start; 14821541Srgrimes loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[start], 14831541Srgrimes (u_char *)fragtbl[fs->fs_frag], 14841541Srgrimes (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 14851541Srgrimes if (loc == 0) { 14861541Srgrimes len = start + 1; 14871541Srgrimes start = 0; 14881541Srgrimes loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[0], 14891541Srgrimes (u_char *)fragtbl[fs->fs_frag], 14901541Srgrimes (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 14911541Srgrimes if (loc == 0) { 14921541Srgrimes printf("start = %d, len = %d, fs = %s\n", 14931541Srgrimes start, len, fs->fs_fsmnt); 14941541Srgrimes panic("ffs_alloccg: map corrupted"); 14951541Srgrimes /* NOTREACHED */ 14961541Srgrimes } 14971541Srgrimes } 14981541Srgrimes bno = (start + len - loc) * NBBY; 14991541Srgrimes cgp->cg_frotor = bno; 15001541Srgrimes /* 15011541Srgrimes * found the byte in the map 15021541Srgrimes * sift through the bits to find the selected frag 15031541Srgrimes */ 15041541Srgrimes for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 15051541Srgrimes blk = blkmap(fs, cg_blksfree(cgp), bno); 15061541Srgrimes blk <<= 1; 15071541Srgrimes field = around[allocsiz]; 15081541Srgrimes subfield = inside[allocsiz]; 15091541Srgrimes for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 15101541Srgrimes if ((blk & field) == subfield) 15111541Srgrimes return (bno + pos); 15121541Srgrimes field <<= 1; 15131541Srgrimes subfield <<= 1; 15141541Srgrimes } 15151541Srgrimes } 15163487Sphk printf("bno = %lu, fs = %s\n", (u_long)bno, fs->fs_fsmnt); 15171541Srgrimes panic("ffs_alloccg: block not in map"); 15181541Srgrimes return (-1); 15191541Srgrimes} 15201541Srgrimes 15211541Srgrimes/* 15221541Srgrimes * Update the cluster map because of an allocation or free. 15231541Srgrimes * 15241541Srgrimes * Cnt == 1 means free; cnt == -1 means allocating. 15251541Srgrimes */ 152612911Sphkstatic void 15271541Srgrimesffs_clusteracct(fs, cgp, blkno, cnt) 15281541Srgrimes struct fs *fs; 15291541Srgrimes struct cg *cgp; 153022521Sdyson ufs_daddr_t blkno; 15311541Srgrimes int cnt; 15321541Srgrimes{ 153322521Sdyson int32_t *sump; 153422521Sdyson int32_t *lp; 15351541Srgrimes u_char *freemapp, *mapp; 15361541Srgrimes int i, start, end, forw, back, map, bit; 15371541Srgrimes 15381541Srgrimes if (fs->fs_contigsumsize <= 0) 15391541Srgrimes return; 15401541Srgrimes freemapp = cg_clustersfree(cgp); 15411541Srgrimes sump = cg_clustersum(cgp); 15421541Srgrimes /* 15431541Srgrimes * Allocate or clear the actual block. 15441541Srgrimes */ 15451541Srgrimes if (cnt > 0) 15461541Srgrimes setbit(freemapp, blkno); 15471541Srgrimes else 15481541Srgrimes clrbit(freemapp, blkno); 15491541Srgrimes /* 15501541Srgrimes * Find the size of the cluster going forward. 15511541Srgrimes */ 15521541Srgrimes start = blkno + 1; 15531541Srgrimes end = start + fs->fs_contigsumsize; 15541541Srgrimes if (end >= cgp->cg_nclusterblks) 15551541Srgrimes end = cgp->cg_nclusterblks; 15561541Srgrimes mapp = &freemapp[start / NBBY]; 15571541Srgrimes map = *mapp++; 15581541Srgrimes bit = 1 << (start % NBBY); 15591541Srgrimes for (i = start; i < end; i++) { 15601541Srgrimes if ((map & bit) == 0) 15611541Srgrimes break; 15621541Srgrimes if ((i & (NBBY - 1)) != (NBBY - 1)) { 15631541Srgrimes bit <<= 1; 15641541Srgrimes } else { 15651541Srgrimes map = *mapp++; 15661541Srgrimes bit = 1; 15671541Srgrimes } 15681541Srgrimes } 15691541Srgrimes forw = i - start; 15701541Srgrimes /* 15711541Srgrimes * Find the size of the cluster going backward. 15721541Srgrimes */ 15731541Srgrimes start = blkno - 1; 15741541Srgrimes end = start - fs->fs_contigsumsize; 15751541Srgrimes if (end < 0) 15761541Srgrimes end = -1; 15771541Srgrimes mapp = &freemapp[start / NBBY]; 15781541Srgrimes map = *mapp--; 15791541Srgrimes bit = 1 << (start % NBBY); 15801541Srgrimes for (i = start; i > end; i--) { 15811541Srgrimes if ((map & bit) == 0) 15821541Srgrimes break; 15831541Srgrimes if ((i & (NBBY - 1)) != 0) { 15841541Srgrimes bit >>= 1; 15851541Srgrimes } else { 15861541Srgrimes map = *mapp--; 15871541Srgrimes bit = 1 << (NBBY - 1); 15881541Srgrimes } 15891541Srgrimes } 15901541Srgrimes back = start - i; 15911541Srgrimes /* 15921541Srgrimes * Account for old cluster and the possibly new forward and 15931541Srgrimes * back clusters. 15941541Srgrimes */ 15951541Srgrimes i = back + forw + 1; 15961541Srgrimes if (i > fs->fs_contigsumsize) 15971541Srgrimes i = fs->fs_contigsumsize; 15981541Srgrimes sump[i] += cnt; 15991541Srgrimes if (back > 0) 16001541Srgrimes sump[back] -= cnt; 16011541Srgrimes if (forw > 0) 16021541Srgrimes sump[forw] -= cnt; 160322521Sdyson /* 160422521Sdyson * Update cluster summary information. 160522521Sdyson */ 160622521Sdyson lp = &sump[fs->fs_contigsumsize]; 160722521Sdyson for (i = fs->fs_contigsumsize; i > 0; i--) 160822521Sdyson if (*lp-- > 0) 160922521Sdyson break; 161022521Sdyson fs->fs_maxcluster[cgp->cg_cgx] = i; 16111541Srgrimes} 16121541Srgrimes 16131541Srgrimes/* 16141541Srgrimes * Fserr prints the name of a file system with an error diagnostic. 16158876Srgrimes * 16161541Srgrimes * The form of the error message is: 16171541Srgrimes * fs: error message 16181541Srgrimes */ 16191541Srgrimesstatic void 16201541Srgrimesffs_fserr(fs, uid, cp) 16211541Srgrimes struct fs *fs; 16221541Srgrimes u_int uid; 16231541Srgrimes char *cp; 16241541Srgrimes{ 162518330Speter struct proc *p = curproc; /* XXX */ 16261541Srgrimes 162718330Speter log(LOG_ERR, "pid %d (%s), uid %d on %s: %s\n", p ? p->p_pid : -1, 162818330Speter p ? p->p_comm : "-", uid, fs->fs_fsmnt, cp); 16291541Srgrimes} 1630