X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/0947395d63010a0111f541a8ddd5324448d80901..39a892baf991e3736c10c22e82845b7c5d52cf5d:/usr/src/sys/ufs/ffs/ffs_alloc.c diff --git a/usr/src/sys/ufs/ffs/ffs_alloc.c b/usr/src/sys/ufs/ffs/ffs_alloc.c index 54abb97b09..3095be9f80 100644 --- a/usr/src/sys/ufs/ffs/ffs_alloc.c +++ b/usr/src/sys/ufs/ffs/ffs_alloc.c @@ -1,220 +1,478 @@ -/* Copyright (c) 1981 Regents of the University of California */ +/* + * Copyright (c) 1982, 1986, 1989 Regents of the University of California. + * All rights reserved. + * + * %sccs.include.redist.c% + * + * @(#)ffs_alloc.c 7.30 (Berkeley) %G% + */ + +#include +#include +#include +#include +#include +#include +#include -static char vers[] = "@(#)ffs_alloc.c 1.8 %G%"; +#include +#include -/* alloc.c 4.8 81/03/08 */ +#include +#include -#include "../h/param.h" -#include "../h/systm.h" -#include "../h/mount.h" -#include "../h/fs.h" -#include "../h/conf.h" -#include "../h/buf.h" -#include "../h/inode.h" -#include "../h/dir.h" -#include "../h/user.h" +extern u_long nextgennumber; -extern long hashalloc(); -extern long ialloccg(); -extern daddr_t alloccg(); -extern daddr_t alloccgblk(); -extern daddr_t fragextend(); -extern daddr_t blkpref(); -extern daddr_t mapsearch(); -extern int inside[], around[]; -extern unsigned char fragtbl[]; +static daddr_t ffs_alloccg __P((struct inode *, int, daddr_t, int)); +static daddr_t ffs_alloccgblk __P((struct fs *, struct cg *, daddr_t)); +static ino_t ffs_dirpref __P((struct fs *)); +static daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); +static void ffs_fserr __P((struct fs *, u_int, char *)); +static u_long ffs_hashalloc + __P((struct inode *, int, long, int, u_long (*)())); +static ino_t ffs_ialloccg __P((struct inode *, int, daddr_t, int)); +static daddr_t ffs_mapsearch __P((struct fs *, struct cg *, daddr_t, int)); -struct buf * -alloc(dev, ip, bpref, size) - dev_t dev; +/* + * Allocate a block in the file system. + * + * The size of the requested block is given, which must be some + * multiple of fs_fsize and <= fs_bsize. + * A preference may be optionally specified. If a preference is given + * the following hierarchy is used to allocate a block: + * 1) allocate the requested block. + * 2) allocate a rotationally optimal block in the same cylinder. + * 3) allocate a block in the same cylinder group. + * 4) quadradically rehash into other cylinder groups, until an + * available block is located. + * If no block preference is given the following heirarchy is used + * to allocate a block: + * 1) allocate a block in the cylinder group that contains the + * inode for the file. + * 2) quadradically rehash into other cylinder groups, until an + * available block is located. + */ +ffs_alloc(ip, lbn, bpref, size, bnp) register struct inode *ip; - daddr_t bpref; + daddr_t lbn, bpref; int size; + daddr_t *bnp; { daddr_t bno; register struct fs *fs; register struct buf *bp; - int cg; + int cg, error; + struct ucred *cred = curproc->p_ucred; /* XXX */ - if ((unsigned)size > BSIZE || size % FSIZE != 0) - panic("alloc: bad size"); - fs = getfs(dev); - if (size == BSIZE && fs->fs_cstotal.cs_nbfree == 0) + *bnp = 0; + fs = ip->i_fs; + if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) { + printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", + ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); + panic("ffs_alloc: bad size"); + } + if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) goto nospace; - if (u.u_uid != 0 && - fs->fs_cstotal.cs_nbfree * FRAG + fs->fs_cstotal.cs_nffree < - fs->fs_dsize * minfree / 100) + if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) goto nospace; +#ifdef QUOTA + if (error = chkdq(ip, (long)btodb(size), cred, 0)) + return (error); +#endif + if (bpref >= fs->fs_size) + bpref = 0; if (bpref == 0) - cg = itog(ip->i_number, fs); + cg = itog(fs, ip->i_number); else - cg = dtog(bpref, fs); - bno = hashalloc(dev, fs, cg, (long)bpref, size, alloccg); - if (bno == 0) - goto nospace; - bp = getblk(dev, bno, size); - clrbuf(bp); - return (bp); + cg = dtog(fs, bpref); + bno = (daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, + (u_long (*)())ffs_alloccg); + if (bno > 0) { + ip->i_blocks += btodb(size); + ip->i_flag |= IUPD|ICHG; + *bnp = bno; + return (0); + } +#ifdef QUOTA + /* + * Restore user's disk quota because allocation failed. + */ + (void) chkdq(ip, (long)-btodb(size), cred, FORCE); +#endif nospace: - fserr(fs, "file system full"); + ffs_fserr(fs, cred->cr_uid, "file system full"); uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); - u.u_error = ENOSPC; - return (NULL); + return (ENOSPC); } -struct buf * -realloccg(dev, ip, bprev, bpref, osize, nsize) - dev_t dev; +/* + * Reallocate a fragment to a bigger size + * + * The number and size of the old block is given, and a preference + * and new size is also specified. The allocator attempts to extend + * the original block. Failing that, the regular block allocator is + * invoked to get an appropriate block. + */ +ffs_realloccg(ip, lbprev, bpref, osize, nsize, bpp) register struct inode *ip; - daddr_t bprev, bpref; + off_t lbprev; + daddr_t bpref; int osize, nsize; + struct buf **bpp; { - daddr_t bno; register struct fs *fs; - register struct buf *bp, *obp; - caddr_t cp; - int cg; + struct buf *bp, *obp; + int cg, request, error; + daddr_t bprev, bno; + struct ucred *cred = curproc->p_ucred; /* XXX */ - if ((unsigned)osize > BSIZE || osize % FSIZE != 0 || - (unsigned)nsize > BSIZE || nsize % FSIZE != 0) - panic("realloccg: bad size"); - fs = getfs(dev); - if (u.u_uid != 0 && - fs->fs_cstotal.cs_nbfree * FRAG + fs->fs_cstotal.cs_nffree < - fs->fs_dsize * minfree / 100) + *bpp = 0; + fs = ip->i_fs; + if ((unsigned)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || + (unsigned)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { + printf( + "dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n", + ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt); + panic("ffs_realloccg: bad size"); + } + if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) goto nospace; - if (bprev == 0) - panic("realloccg: bad bprev"); - else - cg = dtog(bprev, fs); - bno = fragextend(dev, fs, cg, (long)bprev, osize, nsize); - if (bno != 0) { - bp = bread(dev, bno, osize); - bp->b_bcount = nsize; - blkclr(bp->b_un.b_addr + osize, nsize - osize); - return (bp); - } - bno = hashalloc(dev, fs, cg, (long)bpref, nsize, alloccg); - if (bno != 0) { + if ((bprev = ip->i_db[lbprev]) == 0) { + printf("dev = 0x%x, bsize = %d, bprev = %d, fs = %s\n", + ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt); + panic("ffs_realloccg: bad bprev"); + } + /* + * Allocate the extra space in the buffer. + */ + if (error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp)) { + brelse(bp); + return (error); + } +#ifdef QUOTA + if (error = chkdq(ip, (long)btodb(nsize - osize), cred, 0)) { + brelse(bp); + return (error); + } +#endif + /* + * Check for extension in the existing location. + */ + cg = dtog(fs, bprev); + if (bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize)) { + if (bp->b_blkno != fsbtodb(fs, bno)) + panic("bad blockno"); + ip->i_blocks += btodb(nsize - osize); + ip->i_flag |= IUPD|ICHG; + allocbuf(bp, nsize); + bp->b_flags |= B_DONE; + bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize); + *bpp = bp; + return (0); + } + /* + * Allocate a new disk location. + */ + if (bpref >= fs->fs_size) + bpref = 0; + switch ((int)fs->fs_optim) { + case FS_OPTSPACE: + /* + * Allocate an exact sized fragment. Although this makes + * best use of space, we will waste time relocating it if + * the file continues to grow. If the fragmentation is + * less than half of the minimum free reserve, we choose + * to begin optimizing for time. + */ + request = nsize; + if (fs->fs_minfree < 5 || + fs->fs_cstotal.cs_nffree > + fs->fs_dsize * fs->fs_minfree / (2 * 100)) + break; + log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", + fs->fs_fsmnt); + fs->fs_optim = FS_OPTTIME; + break; + case FS_OPTTIME: /* - * make a new copy + * At this point we have discovered a file that is trying to + * grow a small fragment to a larger fragment. To save time, + * we allocate a full sized block, then free the unused portion. + * If the file continues to grow, the `ffs_fragextend' call + * above will be able to grow it in place without further + * copying. If aberrant programs cause disk fragmentation to + * grow within 2% of the free reserve, we choose to begin + * optimizing for space. */ - obp = bread(dev, bprev, osize); - bp = getblk(dev, bno, nsize); - cp = bp->b_un.b_addr; - bp->b_un.b_addr = obp->b_un.b_addr; - obp->b_un.b_addr = cp; - obp->b_flags |= B_INVAL; - brelse(obp); - fre(dev, bprev, osize); - blkclr(bp->b_un.b_addr + osize, nsize - osize); - return(bp); + request = fs->fs_bsize; + if (fs->fs_cstotal.cs_nffree < + fs->fs_dsize * (fs->fs_minfree - 2) / 100) + break; + log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", + fs->fs_fsmnt); + fs->fs_optim = FS_OPTSPACE; + break; + default: + printf("dev = 0x%x, optim = %d, fs = %s\n", + ip->i_dev, fs->fs_optim, fs->fs_fsmnt); + panic("ffs_realloccg: bad optim"); + /* NOTREACHED */ + } + bno = (daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, + (u_long (*)())ffs_alloccg); + if (bno > 0) { +#ifdef SECSIZE + obp = bread(ip->i_dev, fsbtodb(fs, bprev), osize, + fs->fs_dbsize); +#else SECSIZE + count = howmany(osize, CLBYTES); + for (i = 0; i < count; i++) +#ifdef SECSIZE + munhash(ip->i_dev, bn + i * CLBYTES / fs->fs_dbsize); +#else SECSIZE + munhash(ip->i_dev, bn + i * CLBYTES / DEV_BSIZE); +#endif SECSIZE + ffs_blkfree(ip, bprev, (off_t)osize); + if (nsize < request) + ffs_blkfree(ip, bno + numfrags(fs, nsize), + (off_t)(request - nsize)); + ip->i_blocks += btodb(nsize - osize); + ip->i_flag |= IUPD|ICHG; + allocbuf(bp, nsize); + bp->b_flags |= B_DONE; + bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize); + *bpp = bp; + return (0); } +#ifdef QUOTA + /* + * Restore user's disk quota because allocation failed. + */ + (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); +#endif + brelse(bp); nospace: /* * no space available */ - fserr(fs, "file system full"); + ffs_fserr(fs, cred->cr_uid, "file system full"); uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); - u.u_error = ENOSPC; - return (NULL); + return (ENOSPC); } -struct inode * -ialloc(dev, ipref, mode) - dev_t dev; - ino_t ipref; +/* + * Allocate an inode in the file system. + * + * If allocating a directory, use ffs_dirpref to select the inode. + * If allocating in a directory, the following hierarchy is followed: + * 1) allocate the preferred inode. + * 2) allocate an inode in the same cylinder group. + * 3) quadradically rehash into other cylinder groups, until an + * available inode is located. + * If no inode preference is given the following heirarchy is used + * to allocate an inode: + * 1) allocate an inode in cylinder group 0. + * 2) quadradically rehash into other cylinder groups, until an + * available inode is located. + */ +ffs_valloc(pvp, mode, cred, vpp) + register struct vnode *pvp; int mode; + struct ucred *cred; + struct vnode **vpp; { - daddr_t ino; + register struct inode *pip; register struct fs *fs; register struct inode *ip; - int cg; + ino_t ino, ipref; + int cg, error; - fs = getfs(dev); + *vpp = NULL; + pip = VTOI(pvp); + fs = pip->i_fs; if (fs->fs_cstotal.cs_nifree == 0) goto noinodes; - cg = itog(ipref, fs); - ino = hashalloc(dev, fs, cg, (long)ipref, mode, ialloccg); + + if ((mode & IFMT) == IFDIR) + ipref = ffs_dirpref(fs); + else + ipref = pip->i_number; + if (ipref >= fs->fs_ncg * fs->fs_ipg) + ipref = 0; + cg = itog(fs, ipref); + ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, ffs_ialloccg); if (ino == 0) goto noinodes; - ip = iget(dev, ino); - if (ip == NULL) { - ifree(dev, ino); - return (NULL); + error = ffs_vget(pvp->v_mount, ino, vpp); + if (error) { + ffs_vfree(pvp, ino, mode); + return (error); + } + ip = VTOI(*vpp); + if (ip->i_mode) { + printf("mode = 0%o, inum = %d, fs = %s\n", + ip->i_mode, ip->i_number, fs->fs_fsmnt); + panic("ffs_valloc: dup alloc"); + } + if (ip->i_blocks) { /* XXX */ + printf("free inode %s/%d had %d blocks\n", + fs->fs_fsmnt, ino, ip->i_blocks); + ip->i_blocks = 0; } - if (ip->i_mode) - panic("ialloc: dup alloc"); - return (ip); + ip->i_flags = 0; + /* + * Set up a new generation number for this inode. + */ + if (++nextgennumber < (u_long)time.tv_sec) + nextgennumber = time.tv_sec; + ip->i_gen = nextgennumber; + return (0); noinodes: - fserr(fs, "out of inodes"); - uprintf("\n%s: create failed, no inodes free\n", fs->fs_fsmnt); - u.u_error = ENOSPC; - return (NULL); + ffs_fserr(fs, cred->cr_uid, "out of inodes"); + uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); + return (ENOSPC); } /* - * find a cylinder to place a directory + * Find a cylinder to place a directory. + * + * The policy implemented by this algorithm is to select from + * among those cylinder groups with above the average number of + * free inodes, the one with the smallest number of directories. */ -dirpref(dev) - dev_t dev; -{ +static ino_t +ffs_dirpref(fs) register struct fs *fs; +{ int cg, minndir, mincg, avgifree; - fs = getfs(dev); avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; minndir = fs->fs_ipg; mincg = 0; for (cg = 0; cg < fs->fs_ncg; cg++) - if (fs->fs_cs(cg).cs_ndir < minndir && - fs->fs_cs(cg).cs_nifree >= avgifree) { + if (fs->fs_cs(fs, cg).cs_ndir < minndir && + fs->fs_cs(fs, cg).cs_nifree >= avgifree) { mincg = cg; - minndir = fs->fs_cs(cg).cs_ndir; + minndir = fs->fs_cs(fs, cg).cs_ndir; } - return (fs->fs_ipg * mincg); + return ((ino_t)(fs->fs_ipg * mincg)); } /* - * select a cylinder to place a large block of data + * Select the desired position for the next block in a file. The file is + * logically divided into sections. The first section is composed of the + * direct blocks. Each additional section contains fs_maxbpg blocks. + * + * If no blocks have been allocated in the first section, the policy is to + * request a block in the same cylinder group as the inode that describes + * the file. If no blocks have been allocated in any other section, the + * policy is to place the section in a cylinder group with a greater than + * average number of free blocks. An appropriate cylinder group is found + * by using a rotor that sweeps the cylinder groups. When a new group of + * blocks is needed, the sweep begins in the cylinder group following the + * cylinder group from which the previous allocation was made. The sweep + * continues until a cylinder group with greater than the average number + * of free blocks is found. If the allocation is for the first block in an + * indirect block, the information on the previous allocation is unavailable; + * here a best guess is made based upon the logical block number being + * allocated. + * + * If a section is already partially allocated, the policy is to + * contiguously allocate fs_maxcontig blocks. The end of one of these + * contiguous blocks and the beginning of the next is physically separated + * so that the disk head will be in transit between them for at least + * fs_rotdelay milliseconds. This is to allow time for the processor to + * schedule another I/O transfer. */ -blkpref(dev) - dev_t dev; +daddr_t +ffs_blkpref(ip, lbn, indx, bap) + struct inode *ip; + daddr_t lbn; + int indx; + daddr_t *bap; { register struct fs *fs; - int cg, avgbfree; + register int cg; + int avgbfree, startcg; + daddr_t nextblk; - fs = getfs(dev); - avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; - for (cg = fs->fs_cgrotor + 1; cg < fs->fs_ncg; cg++) - if (fs->fs_cs(cg).cs_nbfree >= avgbfree) { - fs->fs_cgrotor = cg; - return (fs->fs_fpg * cg + FRAG); + fs = ip->i_fs; + if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { + if (lbn < NDADDR) { + cg = itog(fs, ip->i_number); + return (fs->fs_fpg * cg + fs->fs_frag); } - for (cg = 0; cg <= fs->fs_cgrotor; cg++) - if (fs->fs_cs(cg).cs_nbfree >= avgbfree) { - fs->fs_cgrotor = cg; - return (fs->fs_fpg * cg + FRAG); - } - return (0); + /* + * Find a cylinder with greater than average number of + * unused data blocks. + */ + if (indx == 0 || bap[indx - 1] == 0) + startcg = itog(fs, ip->i_number) + lbn / fs->fs_maxbpg; + else + startcg = dtog(fs, bap[indx - 1]) + 1; + startcg %= fs->fs_ncg; + avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; + for (cg = startcg; cg < fs->fs_ncg; cg++) + if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { + fs->fs_cgrotor = cg; + return (fs->fs_fpg * cg + fs->fs_frag); + } + for (cg = 0; cg <= startcg; cg++) + if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { + fs->fs_cgrotor = cg; + return (fs->fs_fpg * cg + fs->fs_frag); + } + return (NULL); + } + /* + * One or more previous blocks have been laid out. If less + * than fs_maxcontig previous blocks are contiguous, the + * next block is requested contiguously, otherwise it is + * requested rotationally delayed by fs_rotdelay milliseconds. + */ + nextblk = bap[indx - 1] + fs->fs_frag; + if (indx > fs->fs_maxcontig && + bap[indx - fs->fs_maxcontig] + blkstofrags(fs, fs->fs_maxcontig) + != nextblk) + return (nextblk); + if (fs->fs_rotdelay != 0) + /* + * Here we convert ms of delay to frags as: + * (frags) = (ms) * (rev/sec) * (sect/rev) / + * ((sect/frag) * (ms/sec)) + * then round up to the next block. + */ + nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / + (NSPF(fs) * 1000), fs->fs_frag); + return (nextblk); } -long -hashalloc(dev, fs, cg, pref, size, allocator) - dev_t dev; - register struct fs *fs; +/* + * Implement the cylinder overflow algorithm. + * + * The policy implemented by this algorithm is: + * 1) allocate the block in its requested cylinder group. + * 2) quadradically rehash on the cylinder group number. + * 3) brute force search for a free block. + */ +/*VARARGS5*/ +static u_long +ffs_hashalloc(ip, cg, pref, size, allocator) + struct inode *ip; int cg; long pref; int size; /* size for data blocks, mode for inodes */ - long (*allocator)(); + u_long (*allocator)(); { + register struct fs *fs; long result; int i, icg = cg; + fs = ip->i_fs; /* * 1: preferred cylinder group */ - result = (*allocator)(dev, fs, cg, pref, size); + result = (*allocator)(ip, cg, pref, size); if (result) return (result); /* @@ -224,103 +482,144 @@ hashalloc(dev, fs, cg, pref, size, allocator) cg += i; if (cg >= fs->fs_ncg) cg -= fs->fs_ncg; - result = (*allocator)(dev, fs, cg, 0, size); + result = (*allocator)(ip, cg, 0, size); if (result) return (result); } /* * 3: brute force search + * Note that we start at i == 2, since 0 was checked initially, + * and 1 is always checked in the quadratic rehash. */ - cg = icg; - for (i = 0; i < fs->fs_ncg; i++) { - result = (*allocator)(dev, fs, cg, 0, size); + cg = (icg + 2) % fs->fs_ncg; + for (i = 2; i < fs->fs_ncg; i++) { + result = (*allocator)(ip, cg, 0, size); if (result) return (result); cg++; if (cg == fs->fs_ncg) cg = 0; } - return (0); + return (NULL); } -daddr_t -fragextend(dev, fs, cg, bprev, osize, nsize) - dev_t dev; - register struct fs *fs; +/* + * Determine whether a fragment can be extended. + * + * Check to see if the necessary fragments are available, and + * if they are, allocate them. + */ +static daddr_t +ffs_fragextend(ip, cg, bprev, osize, nsize) + struct inode *ip; int cg; long bprev; int osize, nsize; { - register struct buf *bp; + register struct fs *fs; register struct cg *cgp; + struct buf *bp; long bno; int frags, bbase; - int i; + int i, error; - frags = nsize / FSIZE; - bbase = bprev % FRAG; - if (bbase > (bprev + frags - 1) % FRAG) { - /* cannot extend across a block boundry */ - return (0); + fs = ip->i_fs; + if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) + return (NULL); + frags = numfrags(fs, nsize); + bbase = fragnum(fs, bprev); + if (bbase > fragnum(fs, (bprev + frags - 1))) { + /* cannot extend across a block boundary */ + return (NULL); } - bp = bread(dev, cgtod(cg, fs), BSIZE); - if (bp->b_flags & B_ERROR) - return (0); +#ifdef SECSIZE + bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, + fs->fs_dbsize); +#else SECSIZE + error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), + (int)fs->fs_cgsize, NOCRED, &bp); + if (error) { + brelse(bp); + return (NULL); + } +#endif SECSIZE cgp = bp->b_un.b_cg; - bno = bprev % fs->fs_fpg; - for (i = osize / FSIZE; i < frags; i++) { - if (isclr(cgp->cg_free, bno + i)) - break; + if (!cg_chkmagic(cgp)) { + brelse(bp); + return (NULL); } - if (i == frags) { - /* - * the current fragment can be extended - * deduct the count on fragment being extended into - * increase the count on the remaining fragment (if any) - * allocate the extended piece - */ - for (i = frags; i < FRAG - bbase; i++) - if (isclr(cgp->cg_free, bno + i)) - break; - cgp->cg_frsum[i - osize / FSIZE]--; - if (i != frags) - cgp->cg_frsum[i - frags]++; - for (i = osize / FSIZE; i < frags; i++) { - clrbit(cgp->cg_free, bno + i); - cgp->cg_cs.cs_nffree--; - fs->fs_cstotal.cs_nffree--; - fs->fs_cs(cg).cs_nffree--; + cgp->cg_time = time.tv_sec; + bno = dtogd(fs, bprev); + for (i = numfrags(fs, osize); i < frags; i++) + if (isclr(cg_blksfree(cgp), bno + i)) { + brelse(bp); + return (NULL); } - fs->fs_fmod++; - bdwrite(bp); - return (bprev); + /* + * the current fragment can be extended + * deduct the count on fragment being extended into + * increase the count on the remaining fragment (if any) + * allocate the extended piece + */ + for (i = frags; i < fs->fs_frag - bbase; i++) + if (isclr(cg_blksfree(cgp), bno + i)) + break; + cgp->cg_frsum[i - numfrags(fs, osize)]--; + if (i != frags) + cgp->cg_frsum[i - frags]++; + for (i = numfrags(fs, osize); i < frags; i++) { + clrbit(cg_blksfree(cgp), bno + i); + cgp->cg_cs.cs_nffree--; + fs->fs_cstotal.cs_nffree--; + fs->fs_cs(fs, cg).cs_nffree--; } - brelse(bp); - return (0); + fs->fs_fmod = 1; + bdwrite(bp); + return (bprev); } -daddr_t -alloccg(dev, fs, cg, bpref, size) - dev_t dev; - register struct fs *fs; +/* + * Determine whether a block can be allocated. + * + * Check to see if a block of the apprpriate size is available, + * and if it is, allocate it. + */ +static daddr_t +ffs_alloccg(ip, cg, bpref, size) + struct inode *ip; int cg; daddr_t bpref; int size; { - register struct buf *bp; + register struct fs *fs; register struct cg *cgp; - int bno, frags; - int allocsiz; + struct buf *bp; register int i; + int error, bno, frags, allocsiz; - if (fs->fs_cs(cg).cs_nbfree == 0 && size == BSIZE) - return (0); - bp = bread(dev, cgtod(cg, fs), BSIZE); - if (bp->b_flags & B_ERROR) - return (0); + fs = ip->i_fs; + if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) + return (NULL); +#ifdef SECSIZE + bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, + fs->fs_dbsize); +#else SECSIZE + error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), + (int)fs->fs_cgsize, NOCRED, &bp); + if (error) { + brelse(bp); + return (NULL); + } +#endif SECSIZE cgp = bp->b_un.b_cg; - if (size == BSIZE) { - bno = alloccgblk(dev, fs, cgp, bpref); + if (!cg_chkmagic(cgp) || + (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { + brelse(bp); + return (NULL); + } + cgp->cg_time = time.tv_sec; + if (size == fs->fs_bsize) { + bno = ffs_alloccgblk(fs, cgp, bpref); bdwrite(bp); return (bno); } @@ -329,39 +628,43 @@ alloccg(dev, fs, cg, bpref, size) * allocsiz is the size which will be allocated, hacking * it down to a smaller size if necessary */ - frags = size / FSIZE; - for (allocsiz = frags; allocsiz < FRAG; allocsiz++) + frags = numfrags(fs, size); + for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) if (cgp->cg_frsum[allocsiz] != 0) break; - if (allocsiz == FRAG) { + if (allocsiz == fs->fs_frag) { /* * no fragments were available, so a block will be * allocated, and hacked up */ if (cgp->cg_cs.cs_nbfree == 0) { brelse(bp); - return (0); + return (NULL); } - bno = alloccgblk(dev, fs, cgp, bpref); - bpref = bno % fs->fs_fpg; - for (i = frags; i < FRAG; i++) - setbit(cgp->cg_free, bpref + i); - i = FRAG - frags; + bno = ffs_alloccgblk(fs, cgp, bpref); + bpref = dtogd(fs, bno); + for (i = frags; i < fs->fs_frag; i++) + setbit(cg_blksfree(cgp), bpref + i); + i = fs->fs_frag - frags; cgp->cg_cs.cs_nffree += i; fs->fs_cstotal.cs_nffree += i; - fs->fs_cs(cg).cs_nffree += i; + fs->fs_cs(fs, cg).cs_nffree += i; + fs->fs_fmod = 1; cgp->cg_frsum[i]++; bdwrite(bp); return (bno); } - bno = mapsearch(fs, cgp, bpref, allocsiz); - if (bno == 0) - return (0); + bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); + if (bno < 0) { + brelse(bp); + return (NULL); + } for (i = 0; i < frags; i++) - clrbit(cgp->cg_free, bno + i); + clrbit(cg_blksfree(cgp), bno + i); cgp->cg_cs.cs_nffree -= frags; fs->fs_cstotal.cs_nffree -= frags; - fs->fs_cs(cg).cs_nffree -= frags; + fs->fs_cs(fs, cg).cs_nffree -= frags; + fs->fs_fmod = 1; cgp->cg_frsum[allocsiz]--; if (frags != allocsiz) cgp->cg_frsum[allocsiz - frags]++; @@ -369,241 +672,382 @@ alloccg(dev, fs, cg, bpref, size) return (cg * fs->fs_fpg + bno); } -daddr_t -alloccgblk(dev, fs, cgp, bpref) - dev_t dev; - struct fs *fs; +/* + * Allocate a block in a cylinder group. + * + * This algorithm implements the following policy: + * 1) allocate the requested block. + * 2) allocate a rotationally optimal block in the same cylinder. + * 3) allocate the next available block on the block rotor for the + * specified cylinder group. + * Note that this routine only allocates fs_bsize blocks; these + * blocks may be fragmented by the routine that allocates them. + */ +static daddr_t +ffs_alloccgblk(fs, cgp, bpref) + register struct fs *fs; register struct cg *cgp; daddr_t bpref; { daddr_t bno; - int cylno, pos; + int cylno, pos, delta; short *cylbp; - int i, j; + register int i; if (bpref == 0) { bpref = cgp->cg_rotor; - } else { - bpref &= ~(FRAG - 1); - bpref %= fs->fs_fpg; - /* - * if the requested block is available, use it - */ - if (isblock(cgp->cg_free, bpref/FRAG)) { - bno = bpref; - goto gotit; - } + goto norot; + } + bpref = blknum(fs, bpref); + bpref = dtogd(fs, bpref); + /* + * if the requested block is available, use it + */ + if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) { + bno = bpref; + goto gotit; + } + /* + * check for a block available on the same cylinder + */ + cylno = cbtocylno(fs, bpref); + if (cg_blktot(cgp)[cylno] == 0) + goto norot; + if (fs->fs_cpc == 0) { /* - * check for a block available on the same cylinder - * beginning with one which is rotationally optimal + * block layout info is not available, so just have + * to take any block in this cylinder. */ - i = bpref * NSPF; - cylno = i / fs->fs_spc; - cylbp = cgp->cg_b[cylno]; - pos = (i + (ROTDELAY == 0) ? - 0 : 1 + ROTDELAY * HZ * fs->fs_nsect / (NSPF * 1000)) % - fs->fs_nsect * NRPOS / fs->fs_nsect; - for (i = pos; i < NRPOS; i++) + bpref = howmany(fs->fs_spc * cylno, NSPF(fs)); + goto norot; + } + /* + * check the summary information to see if a block is + * available in the requested cylinder starting at the + * requested rotational position and proceeding around. + */ + cylbp = cg_blks(fs, cgp, cylno); + pos = cbtorpos(fs, bpref); + for (i = pos; i < fs->fs_nrpos; i++) + if (cylbp[i] > 0) + break; + if (i == fs->fs_nrpos) + for (i = 0; i < pos; i++) if (cylbp[i] > 0) break; - if (i == NRPOS) - for (i = 0; i < pos; i++) - if (cylbp[i] > 0) - break; - if (cylbp[i] > 0) { - bpref = cylno * fs->fs_spc / (NSPF * FRAG); - for (j = fs->fs_postbl[i]; j > -1; j = fs->fs_rotbl[j]) { - if (isblock(cgp->cg_free, bpref + j)) { - bno = (bpref + j) * FRAG; - goto gotit; - } + if (cylbp[i] > 0) { + /* + * found a rotational position, now find the actual + * block. A panic if none is actually there. + */ + pos = cylno % fs->fs_cpc; + bno = (cylno - pos) * fs->fs_spc / NSPB(fs); + if (fs_postbl(fs, pos)[i] == -1) { + printf("pos = %d, i = %d, fs = %s\n", + pos, i, fs->fs_fsmnt); + panic("ffs_alloccgblk: cyl groups corrupted"); + } + for (i = fs_postbl(fs, pos)[i];; ) { + if (ffs_isblock(fs, cg_blksfree(cgp), bno + i)) { + bno = blkstofrags(fs, (bno + i)); + goto gotit; } - panic("alloccgblk: can't find blk in cyl"); + delta = fs_rotbl(fs)[i]; + if (delta <= 0 || + delta + i > fragstoblks(fs, fs->fs_fpg)) + break; + i += delta; } + printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); + panic("ffs_alloccgblk: can't find blk in cyl"); } - bno = mapsearch(fs, cgp, bpref, FRAG); - if (bno == 0) - return (0); +norot: + /* + * no blocks in the requested cylinder, so take next + * available one in this cylinder group. + */ + bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); + if (bno < 0) + return (NULL); cgp->cg_rotor = bno; gotit: - clrblock(cgp->cg_free, bno/FRAG); + ffs_clrblock(fs, cg_blksfree(cgp), (long)fragstoblks(fs, bno)); cgp->cg_cs.cs_nbfree--; fs->fs_cstotal.cs_nbfree--; - fs->fs_cs(cgp->cg_cgx).cs_nbfree--; - i = bno * NSPF; - cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]--; - fs->fs_fmod++; + fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; + cylno = cbtocylno(fs, bno); + cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; + cg_blktot(cgp)[cylno]--; + fs->fs_fmod = 1; return (cgp->cg_cgx * fs->fs_fpg + bno); } - -long -ialloccg(dev, fs, cg, ipref, mode) - dev_t dev; - register struct fs *fs; + +/* + * Determine whether an inode can be allocated. + * + * Check to see if an inode is available, and if it is, + * allocate it using the following policy: + * 1) allocate the requested inode. + * 2) allocate the next available inode after the requested + * inode in the specified cylinder group. + */ +static ino_t +ffs_ialloccg(ip, cg, ipref, mode) + struct inode *ip; int cg; daddr_t ipref; int mode; { - register struct buf *bp; + register struct fs *fs; register struct cg *cgp; - int i; + struct buf *bp; + int error, start, len, loc, map, i; - if (fs->fs_cs(cg).cs_nifree == 0) - return (0); - bp = bread(dev, cgtod(cg, fs), BSIZE); - if (bp->b_flags & B_ERROR) - return (0); + fs = ip->i_fs; + if (fs->fs_cs(fs, cg).cs_nifree == 0) + return (NULL); +#ifdef SECSIZE + bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, + fs->fs_dbsize); +#else SECSIZE + error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), + (int)fs->fs_cgsize, NOCRED, &bp); + if (error) { + brelse(bp); + return (NULL); + } +#endif SECSIZE cgp = bp->b_un.b_cg; + if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { + brelse(bp); + return (NULL); + } + cgp->cg_time = time.tv_sec; if (ipref) { ipref %= fs->fs_ipg; - if (isclr(cgp->cg_iused, ipref)) + if (isclr(cg_inosused(cgp), ipref)) goto gotit; - } else - ipref = cgp->cg_irotor; - for (i = 0; i < fs->fs_ipg; i++) { - ipref++; - if (ipref >= fs->fs_ipg) - ipref = 0; - if (isclr(cgp->cg_iused, ipref)) { + } + start = cgp->cg_irotor / NBBY; + len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); + loc = skpc(0xff, len, &cg_inosused(cgp)[start]); + if (loc == 0) { + len = start + 1; + start = 0; + loc = skpc(0xff, len, &cg_inosused(cgp)[0]); + if (loc == 0) { + printf("cg = %s, irotor = %d, fs = %s\n", + cg, cgp->cg_irotor, fs->fs_fsmnt); + panic("ffs_ialloccg: map corrupted"); + /* NOTREACHED */ + } + } + i = start + len - loc; + map = cg_inosused(cgp)[i]; + ipref = i * NBBY; + for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { + if ((map & i) == 0) { cgp->cg_irotor = ipref; goto gotit; } } - brelse(bp); - return (0); + printf("fs = %s\n", fs->fs_fsmnt); + panic("ffs_ialloccg: block not in map"); + /* NOTREACHED */ gotit: - setbit(cgp->cg_iused, ipref); + setbit(cg_inosused(cgp), ipref); cgp->cg_cs.cs_nifree--; fs->fs_cstotal.cs_nifree--; - fs->fs_cs(cg).cs_nifree--; - fs->fs_fmod++; + fs->fs_cs(fs, cg).cs_nifree--; + fs->fs_fmod = 1; if ((mode & IFMT) == IFDIR) { cgp->cg_cs.cs_ndir++; fs->fs_cstotal.cs_ndir++; - fs->fs_cs(cg).cs_ndir++; + fs->fs_cs(fs, cg).cs_ndir++; } bdwrite(bp); return (cg * fs->fs_ipg + ipref); } -fre(dev, bno, size) - dev_t dev; +/* + * Free a block or fragment. + * + * The specified block or fragment is placed back in the + * free map. If a fragment is deallocated, a possible + * block reassembly is checked. + */ +ffs_blkfree(ip, bno, size) + register struct inode *ip; daddr_t bno; - int size; + off_t size; { register struct fs *fs; register struct cg *cgp; - register struct buf *bp; - int cg, blk, frags, bbase; + struct buf *bp; + int error, cg, blk, frags, bbase; register int i; + struct ucred *cred = curproc->p_ucred; /* XXX */ - if ((unsigned)size > BSIZE || size % FSIZE != 0) - panic("free: bad size"); - fs = getfs(dev); - cg = dtog(bno, fs); - if (badblock(fs, bno)) + fs = ip->i_fs; + if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) { + printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", + ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); + panic("blkfree: bad size"); + } + cg = dtog(fs, bno); + if ((unsigned)bno >= fs->fs_size) { + printf("bad block %d, ino %d\n", bno, ip->i_number); + ffs_fserr(fs, cred->cr_uid, "bad block"); return; - bp = bread(dev, cgtod(cg, fs), BSIZE); - if (bp->b_flags & B_ERROR) + } +#ifdef SECSIZE + bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, + fs->fs_dbsize); +#else SECSIZE + error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), + (int)fs->fs_cgsize, NOCRED, &bp); + if (error) { + brelse(bp); return; + } +#endif SECSIZE cgp = bp->b_un.b_cg; - bno %= fs->fs_fpg; - if (size == BSIZE) { - if (isblock(cgp->cg_free, bno/FRAG)) - panic("free: freeing free block"); - setblock(cgp->cg_free, bno/FRAG); + if (!cg_chkmagic(cgp)) { + brelse(bp); + return; + } + cgp->cg_time = time.tv_sec; + bno = dtogd(fs, bno); + if (size == fs->fs_bsize) { + if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno))) { + printf("dev = 0x%x, block = %d, fs = %s\n", + ip->i_dev, bno, fs->fs_fsmnt); + panic("blkfree: freeing free block"); + } + ffs_setblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno)); cgp->cg_cs.cs_nbfree++; fs->fs_cstotal.cs_nbfree++; - fs->fs_cs(cg).cs_nbfree++; - i = bno * NSPF; - cgp->cg_b[i/fs->fs_spc][i%fs->fs_nsect*NRPOS/fs->fs_nsect]++; + fs->fs_cs(fs, cg).cs_nbfree++; + i = cbtocylno(fs, bno); + cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; + cg_blktot(cgp)[i]++; } else { - bbase = bno - (bno % FRAG); + bbase = bno - fragnum(fs, bno); /* * decrement the counts associated with the old frags */ - blk = ((cgp->cg_free[bbase / NBBY] >> (bbase % NBBY)) & - (0xff >> (NBBY - FRAG))); - fragacct(blk, cgp->cg_frsum, -1); + blk = blkmap(fs, cg_blksfree(cgp), bbase); + ffs_fragacct(fs, blk, cgp->cg_frsum, -1); /* * deallocate the fragment */ - frags = size / FSIZE; + frags = numfrags(fs, size); for (i = 0; i < frags; i++) { - if (isset(cgp->cg_free, bno + i)) - panic("free: freeing free frag"); - setbit(cgp->cg_free, bno + i); - cgp->cg_cs.cs_nffree++; - fs->fs_cstotal.cs_nffree++; - fs->fs_cs(cg).cs_nffree++; + if (isset(cg_blksfree(cgp), bno + i)) { + printf("dev = 0x%x, block = %d, fs = %s\n", + ip->i_dev, bno + i, fs->fs_fsmnt); + panic("blkfree: freeing free frag"); + } + setbit(cg_blksfree(cgp), bno + i); } + cgp->cg_cs.cs_nffree += i; + fs->fs_cstotal.cs_nffree += i; + fs->fs_cs(fs, cg).cs_nffree += i; /* * add back in counts associated with the new frags */ - blk = ((cgp->cg_free[bbase / NBBY] >> (bbase % NBBY)) & - (0xff >> (NBBY - FRAG))); - fragacct(blk, cgp->cg_frsum, 1); + blk = blkmap(fs, cg_blksfree(cgp), bbase); + ffs_fragacct(fs, blk, cgp->cg_frsum, 1); /* * if a complete block has been reassembled, account for it */ - if (isblock(cgp->cg_free, bbase / FRAG)) { - cgp->cg_cs.cs_nffree -= FRAG; - fs->fs_cstotal.cs_nffree -= FRAG; - fs->fs_cs(cg).cs_nffree -= FRAG; + if (ffs_isblock(fs, cg_blksfree(cgp), + (daddr_t)fragstoblks(fs, bbase))) { + cgp->cg_cs.cs_nffree -= fs->fs_frag; + fs->fs_cstotal.cs_nffree -= fs->fs_frag; + fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; cgp->cg_cs.cs_nbfree++; fs->fs_cstotal.cs_nbfree++; - fs->fs_cs(cg).cs_nbfree++; - i = bbase * NSPF; - cgp->cg_b[i / fs->fs_spc] - [i % fs->fs_nsect * NRPOS / fs->fs_nsect]++; + fs->fs_cs(fs, cg).cs_nbfree++; + i = cbtocylno(fs, bbase); + cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; + cg_blktot(cgp)[i]++; } } - fs->fs_fmod++; + fs->fs_fmod = 1; bdwrite(bp); } -ifree(dev, ino, mode) - dev_t dev; +/* + * Free an inode. + * + * The specified inode is placed back in the free map. + */ +void +ffs_vfree(pvp, ino, mode) + struct vnode *pvp; ino_t ino; int mode; { register struct fs *fs; register struct cg *cgp; - register struct buf *bp; - int i; - int cg; + register struct inode *pip; + struct buf *bp; + int error, cg; - fs = getfs(dev); - if ((unsigned)ino >= fs->fs_ipg*fs->fs_ncg) - panic("ifree: range"); - cg = itog(ino, fs); - bp = bread(dev, cgtod(cg, fs), BSIZE); - if (bp->b_flags & B_ERROR) + pip = VTOI(pvp); + fs = pip->i_fs; + if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) + panic("ifree: range: dev = 0x%x, ino = %d, fs = %s\n", + pip->i_dev, ino, fs->fs_fsmnt); + cg = itog(fs, ino); +#ifdef SECSIZE + bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, + fs->fs_dbsize); +#else SECSIZE + error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), + (int)fs->fs_cgsize, NOCRED, &bp); + if (error) { + brelse(bp); return; + } +#endif SECSIZE cgp = bp->b_un.b_cg; + if (!cg_chkmagic(cgp)) { + brelse(bp); + return; + } + cgp->cg_time = time.tv_sec; ino %= fs->fs_ipg; - if (isclr(cgp->cg_iused, ino)) - panic("ifree: freeing free inode"); - clrbit(cgp->cg_iused, ino); + if (isclr(cg_inosused(cgp), ino)) { + printf("dev = 0x%x, ino = %d, fs = %s\n", + pip->i_dev, ino, fs->fs_fsmnt); + if (fs->fs_ronly == 0) + panic("ifree: freeing free inode"); + } + clrbit(cg_inosused(cgp), ino); + if (ino < cgp->cg_irotor) + cgp->cg_irotor = ino; cgp->cg_cs.cs_nifree++; fs->fs_cstotal.cs_nifree++; - fs->fs_cs(cg).cs_nifree++; + fs->fs_cs(fs, cg).cs_nifree++; if ((mode & IFMT) == IFDIR) { cgp->cg_cs.cs_ndir--; fs->fs_cstotal.cs_ndir--; - fs->fs_cs(cg).cs_ndir--; + fs->fs_cs(fs, cg).cs_ndir--; } - fs->fs_fmod++; + fs->fs_fmod = 1; bdwrite(bp); } /* - * find a block of the specified size in the specified cylinder group + * Find a block of the specified size in the specified cylinder group. + * * It is a panic if a request is made to find a block if none are * available. */ -daddr_t -mapsearch(fs, cgp, bpref, allocsiz) +static daddr_t +ffs_mapsearch(fs, cgp, bpref, allocsiz) register struct fs *fs; register struct cg *cgp; daddr_t bpref; @@ -618,20 +1062,24 @@ mapsearch(fs, cgp, bpref, allocsiz) * map for an appropriate bit pattern */ if (bpref) - start = bpref % fs->fs_fpg / NBBY; + start = dtogd(fs, bpref) / NBBY; else start = cgp->cg_frotor / NBBY; - len = roundup(fs->fs_fpg - 1, NBBY) / NBBY - start; - loc = scanc(len, &cgp->cg_free[start], fragtbl, 1 << (allocsiz - 1)); + len = howmany(fs->fs_fpg, NBBY) - start; + loc = scanc((unsigned)len, (u_char *)&cg_blksfree(cgp)[start], + (u_char *)fragtbl[fs->fs_frag], + (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); if (loc == 0) { - len = start - 1; - start = (cgdmin(cgp->cg_cgx, fs) - - cgbase(cgp->cg_cgx, fs)) / NBBY; - loc = scanc(len, &cgp->cg_free[start], fragtbl, - 1 << (allocsiz - 1)); + len = start + 1; + start = 0; + loc = scanc((unsigned)len, (u_char *)&cg_blksfree(cgp)[0], + (u_char *)fragtbl[fs->fs_frag], + (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); if (loc == 0) { - panic("alloccg: map corrupted"); - return (0); + printf("start = %d, len = %d, fs = %s\n", + start, len, fs->fs_fsmnt); + panic("ffs_alloccg: map corrupted"); + /* NOTREACHED */ } } bno = (start + len - loc) * NBBY; @@ -640,194 +1088,35 @@ mapsearch(fs, cgp, bpref, allocsiz) * found the byte in the map * sift through the bits to find the selected frag */ - for (i = 0; i < NBBY; i += FRAG) { - blk = (cgp->cg_free[bno / NBBY] >> i) & (0xff >> NBBY - FRAG); + for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { + blk = blkmap(fs, cg_blksfree(cgp), bno); blk <<= 1; field = around[allocsiz]; subfield = inside[allocsiz]; - for (pos = 0; pos <= FRAG - allocsiz; pos++) { - if ((blk & field) == subfield) { - return (bno + i + pos); - } - field <<= 1; - subfield <<= 1; - } - } - panic("alloccg: block not in map"); - return (0); -} - -/* - * update the frsum fields to reflect addition or deletion - * of some frags - */ -fragacct(fragmap, fraglist, cnt) - int fragmap; - long fraglist[]; - int cnt; -{ - int inblk; - register int field, subfield; - register int siz, pos; - - inblk = (int)(fragtbl[fragmap]) << 1; - fragmap <<= 1; - for (siz = 1; siz < FRAG; siz++) { - if (((1 << siz) & inblk) == 0) - continue; - field = around[siz]; - subfield = inside[siz]; - for (pos = siz; pos <= FRAG; pos++) { - if ((fragmap & field) == subfield) { - fraglist[siz] += cnt; - pos += siz; - field <<= siz; - subfield <<= siz; - } + for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { + if ((blk & field) == subfield) + return (bno + pos); field <<= 1; subfield <<= 1; } } -} - -badblock(fs, bn) - register struct fs *fs; - daddr_t bn; -{ - - if ((unsigned)bn >= fs->fs_size || bn < cgdmin(dtog(bn, fs), fs)) { - fserr(fs, "bad block"); - return (1); - } - return (0); -} - -/* - * getfs maps a device number into - * a pointer to the incore super - * block. The algorithm is a linear - * search through the mount table. - * A consistency check of the - * in core free-block and i-node - * counts is performed. - * - * panic: no fs -- the device is not mounted. - * this "cannot happen" - */ -struct fs * -getfs(dev) - dev_t dev; -{ - register struct mount *mp; - register struct fs *fs; - - for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++) - if (mp->m_bufp != NULL && mp->m_dev == dev) { - fs = mp->m_bufp->b_un.b_fs; - if (fs->fs_magic != FS_MAGIC) - panic("getfs: bad magic"); - return (fs); - } - panic("getfs: no fs"); - return (NULL); + printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt); + panic("ffs_alloccg: block not in map"); + return (-1); } /* - * Fserr prints the name of a file system - * with an error diagnostic, in the form + * Fserr prints the name of a file system with an error diagnostic. + * + * The form of the error message is: * fs: error message */ -fserr(fs, cp) +static void +ffs_fserr(fs, uid, cp) struct fs *fs; + u_int uid; char *cp; { - printf("%s: %s\n", fs->fs_fsmnt, cp); -} - -/* - * Getfsx returns the index in the file system - * table of the specified device. The swap device - * is also assigned a pseudo-index. The index may - * be used as a compressed indication of the location - * of a block, recording - * - * rather than - * - * provided the information need remain valid only - * as long as the file system is mounted. - */ -getfsx(dev) - dev_t dev; -{ - register struct mount *mp; - - if (dev == swapdev) - return (MSWAPX); - for(mp = &mount[0]; mp < &mount[NMOUNT]; mp++) - if (mp->m_dev == dev) - return (mp - &mount[0]); - return (-1); -} - -/* - * Update is the internal name of 'sync'. It goes through the disk - * queues to initiate sandbagged IO; goes through the inodes to write - * modified nodes; and it goes through the mount table to initiate modified - * super blocks. - */ -update() -{ - register struct inode *ip; - register struct mount *mp; - register struct buf *bp; - struct fs *fs; - time_t tim; - int i, blks; - - if (updlock) - return; - updlock++; - /* - * Write back modified superblocks. - * Consistency check that the superblock - * of each file system is still in the buffer cache. - */ - for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++) - if (mp->m_bufp != NULL) { - fs = mp->m_bufp->b_un.b_fs; - if (fs->fs_fmod == 0) - continue; - if (fs->fs_ronly != 0) - panic("update: rofs mod"); - bp = getblk(mp->m_dev, SBLOCK, BSIZE); - fs->fs_fmod = 0; - fs->fs_time = TIME; - if (bp->b_un.b_fs != fs) - panic("update: bad b_fs"); - bwrite(bp); - blks = howmany(cssize(fs), BSIZE); - for (i = 0; i < blks; i++) { - bp = getblk(mp->m_dev, csaddr(fs) + (i * FRAG), - BSIZE); - bwrite(bp); - } - } - /* - * Write back each (modified) inode. - */ - for (ip = inode; ip < inodeNINODE; ip++) - if((ip->i_flag&ILOCK)==0 && ip->i_count) { - ip->i_flag |= ILOCK; - ip->i_count++; - tim = TIME; - iupdat(ip, &tim, &tim, 0); - iput(ip); - } - updlock = 0; - /* - * Force stale buffer cache information to be flushed, - * for all devices. - */ - bflush(NODEV); + log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->fs_fsmnt, cp); }