Home | History | Annotate | Line # | Download | only in ffs
ffs_alloc.c revision 1.26.2.3
      1  1.26.2.3       chs /*	$NetBSD: ffs_alloc.c,v 1.26.2.3 1999/04/09 04:33:22 chs Exp $	*/
      2       1.2       cgd 
      3       1.1   mycroft /*
      4       1.1   mycroft  * Copyright (c) 1982, 1986, 1989, 1993
      5       1.1   mycroft  *	The Regents of the University of California.  All rights reserved.
      6       1.1   mycroft  *
      7       1.1   mycroft  * Redistribution and use in source and binary forms, with or without
      8       1.1   mycroft  * modification, are permitted provided that the following conditions
      9       1.1   mycroft  * are met:
     10       1.1   mycroft  * 1. Redistributions of source code must retain the above copyright
     11       1.1   mycroft  *    notice, this list of conditions and the following disclaimer.
     12       1.1   mycroft  * 2. Redistributions in binary form must reproduce the above copyright
     13       1.1   mycroft  *    notice, this list of conditions and the following disclaimer in the
     14       1.1   mycroft  *    documentation and/or other materials provided with the distribution.
     15       1.1   mycroft  * 3. All advertising materials mentioning features or use of this software
     16       1.1   mycroft  *    must display the following acknowledgement:
     17       1.1   mycroft  *	This product includes software developed by the University of
     18       1.1   mycroft  *	California, Berkeley and its contributors.
     19       1.1   mycroft  * 4. Neither the name of the University nor the names of its contributors
     20       1.1   mycroft  *    may be used to endorse or promote products derived from this software
     21       1.1   mycroft  *    without specific prior written permission.
     22       1.1   mycroft  *
     23       1.1   mycroft  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     24       1.1   mycroft  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     25       1.1   mycroft  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     26       1.1   mycroft  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     27       1.1   mycroft  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     28       1.1   mycroft  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     29       1.1   mycroft  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     30       1.1   mycroft  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     31       1.1   mycroft  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     32       1.1   mycroft  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     33       1.1   mycroft  * SUCH DAMAGE.
     34       1.1   mycroft  *
     35      1.18      fvdl  *	@(#)ffs_alloc.c	8.19 (Berkeley) 7/13/95
     36       1.1   mycroft  */
     37      1.17       mrg 
     38      1.22    scottr #if defined(_KERNEL) && !defined(_LKM)
     39      1.21    scottr #include "opt_quota.h"
     40      1.17       mrg #include "opt_uvm.h"
     41      1.22    scottr #endif
     42       1.1   mycroft 
     43       1.1   mycroft #include <sys/param.h>
     44       1.1   mycroft #include <sys/systm.h>
     45       1.1   mycroft #include <sys/buf.h>
     46       1.1   mycroft #include <sys/proc.h>
     47       1.1   mycroft #include <sys/vnode.h>
     48       1.1   mycroft #include <sys/mount.h>
     49       1.1   mycroft #include <sys/kernel.h>
     50       1.1   mycroft #include <sys/syslog.h>
     51       1.1   mycroft 
     52       1.1   mycroft #include <vm/vm.h>
     53  1.26.2.1       chs #ifdef UBC
     54  1.26.2.1       chs #include <uvm/uvm.h>
     55  1.26.2.1       chs #endif
     56       1.1   mycroft 
     57       1.1   mycroft #include <ufs/ufs/quota.h>
     58      1.19    bouyer #include <ufs/ufs/ufsmount.h>
     59       1.1   mycroft #include <ufs/ufs/inode.h>
     60       1.9  christos #include <ufs/ufs/ufs_extern.h>
     61      1.19    bouyer #include <ufs/ufs/ufs_bswap.h>
     62       1.1   mycroft 
     63       1.1   mycroft #include <ufs/ffs/fs.h>
     64       1.1   mycroft #include <ufs/ffs/ffs_extern.h>
     65       1.1   mycroft 
     66      1.19    bouyer static ufs_daddr_t	ffs_alloccg __P((struct inode *, int, ufs_daddr_t, int));
     67      1.19    bouyer static ufs_daddr_t	ffs_alloccgblk __P((struct mount *, struct fs *,
     68      1.19    bouyer 	struct cg *, ufs_daddr_t));
     69      1.19    bouyer static ufs_daddr_t	ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t, int));
     70      1.19    bouyer static ino_t	ffs_dirpref __P((struct fs *));
     71      1.19    bouyer static ufs_daddr_t	ffs_fragextend __P((struct inode *, int, long, int, int));
     72      1.19    bouyer static void	ffs_fserr __P((struct fs *, u_int, char *));
     73      1.19    bouyer static u_long	ffs_hashalloc __P((struct inode *, int, long, int,
     74      1.19    bouyer 				   ufs_daddr_t (*)(struct inode *, int, ufs_daddr_t,
     75      1.19    bouyer 					       int)));
     76      1.19    bouyer static ufs_daddr_t	ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int));
     77      1.19    bouyer static ufs_daddr_t	ffs_mapsearch __P((int, struct fs *, struct cg *,
     78      1.19    bouyer 					ufs_daddr_t, int));
     79      1.18      fvdl #if defined(DIAGNOSTIC) || defined(DEBUG)
     80      1.18      fvdl static int ffs_checkblk __P((struct inode *, ufs_daddr_t, long size));
     81      1.18      fvdl #endif
     82      1.23  drochner 
     83      1.23  drochner /* in ffs_tables.c */
     84      1.23  drochner extern int inside[], around[];
     85      1.23  drochner extern u_char *fragtbl[];
     86       1.1   mycroft 
     87       1.1   mycroft /*
     88       1.1   mycroft  * Allocate a block in the file system.
     89       1.1   mycroft  *
     90       1.1   mycroft  * The size of the requested block is given, which must be some
     91       1.1   mycroft  * multiple of fs_fsize and <= fs_bsize.
     92       1.1   mycroft  * A preference may be optionally specified. If a preference is given
     93       1.1   mycroft  * the following hierarchy is used to allocate a block:
     94       1.1   mycroft  *   1) allocate the requested block.
     95       1.1   mycroft  *   2) allocate a rotationally optimal block in the same cylinder.
     96       1.1   mycroft  *   3) allocate a block in the same cylinder group.
     97       1.1   mycroft  *   4) quadradically rehash into other cylinder groups, until an
     98       1.1   mycroft  *      available block is located.
     99       1.1   mycroft  * If no block preference is given the following heirarchy is used
    100       1.1   mycroft  * to allocate a block:
    101       1.1   mycroft  *   1) allocate a block in the cylinder group that contains the
    102       1.1   mycroft  *      inode for the file.
    103       1.1   mycroft  *   2) quadradically rehash into other cylinder groups, until an
    104       1.1   mycroft  *      available block is located.
    105       1.1   mycroft  */
    106       1.9  christos int
    107       1.1   mycroft ffs_alloc(ip, lbn, bpref, size, cred, bnp)
    108       1.1   mycroft 	register struct inode *ip;
    109      1.18      fvdl 	ufs_daddr_t lbn, bpref;
    110       1.1   mycroft 	int size;
    111       1.1   mycroft 	struct ucred *cred;
    112      1.18      fvdl 	ufs_daddr_t *bnp;
    113       1.1   mycroft {
    114       1.1   mycroft 	register struct fs *fs;
    115      1.18      fvdl 	ufs_daddr_t bno;
    116       1.9  christos 	int cg;
    117       1.9  christos #ifdef QUOTA
    118       1.9  christos 	int error;
    119       1.9  christos #endif
    120       1.1   mycroft 
    121       1.1   mycroft 	*bnp = 0;
    122       1.1   mycroft 	fs = ip->i_fs;
    123       1.1   mycroft #ifdef DIAGNOSTIC
    124       1.1   mycroft 	if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) {
    125      1.13  christos 		printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n",
    126       1.1   mycroft 		    ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt);
    127       1.1   mycroft 		panic("ffs_alloc: bad size");
    128       1.1   mycroft 	}
    129       1.1   mycroft 	if (cred == NOCRED)
    130       1.1   mycroft 		panic("ffs_alloc: missing credential\n");
    131       1.1   mycroft #endif /* DIAGNOSTIC */
    132       1.1   mycroft 	if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0)
    133       1.1   mycroft 		goto nospace;
    134       1.1   mycroft 	if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0)
    135       1.1   mycroft 		goto nospace;
    136       1.1   mycroft #ifdef QUOTA
    137       1.9  christos 	if ((error = chkdq(ip, (long)btodb(size), cred, 0)) != 0)
    138       1.1   mycroft 		return (error);
    139       1.1   mycroft #endif
    140       1.1   mycroft 	if (bpref >= fs->fs_size)
    141       1.1   mycroft 		bpref = 0;
    142       1.1   mycroft 	if (bpref == 0)
    143       1.1   mycroft 		cg = ino_to_cg(fs, ip->i_number);
    144       1.1   mycroft 	else
    145       1.1   mycroft 		cg = dtog(fs, bpref);
    146      1.18      fvdl 	bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size,
    147       1.9  christos 	    			     ffs_alloccg);
    148       1.1   mycroft 	if (bno > 0) {
    149      1.15    bouyer 		ip->i_ffs_blocks += btodb(size);
    150       1.1   mycroft 		ip->i_flag |= IN_CHANGE | IN_UPDATE;
    151       1.1   mycroft 		*bnp = bno;
    152       1.1   mycroft 		return (0);
    153       1.1   mycroft 	}
    154       1.1   mycroft #ifdef QUOTA
    155       1.1   mycroft 	/*
    156       1.1   mycroft 	 * Restore user's disk quota because allocation failed.
    157       1.1   mycroft 	 */
    158       1.1   mycroft 	(void) chkdq(ip, (long)-btodb(size), cred, FORCE);
    159       1.1   mycroft #endif
    160       1.1   mycroft nospace:
    161       1.1   mycroft 	ffs_fserr(fs, cred->cr_uid, "file system full");
    162       1.1   mycroft 	uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
    163       1.1   mycroft 	return (ENOSPC);
    164       1.1   mycroft }
    165       1.1   mycroft 
    166       1.1   mycroft /*
    167       1.1   mycroft  * Reallocate a fragment to a bigger size
    168       1.1   mycroft  *
    169       1.1   mycroft  * The number and size of the old block is given, and a preference
    170       1.1   mycroft  * and new size is also specified. The allocator attempts to extend
    171       1.1   mycroft  * the original block. Failing that, the regular block allocator is
    172       1.1   mycroft  * invoked to get an appropriate block.
    173       1.1   mycroft  */
    174       1.9  christos int
    175  1.26.2.1       chs ffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp, blknop)
    176       1.1   mycroft 	register struct inode *ip;
    177      1.18      fvdl 	ufs_daddr_t lbprev;
    178      1.18      fvdl 	ufs_daddr_t bpref;
    179       1.1   mycroft 	int osize, nsize;
    180       1.1   mycroft 	struct ucred *cred;
    181       1.1   mycroft 	struct buf **bpp;
    182  1.26.2.1       chs 	ufs_daddr_t *blknop;
    183       1.1   mycroft {
    184       1.1   mycroft 	register struct fs *fs;
    185       1.1   mycroft 	struct buf *bp;
    186       1.1   mycroft 	int cg, request, error;
    187      1.18      fvdl 	ufs_daddr_t bprev, bno;
    188      1.25   thorpej 
    189  1.26.2.3       chs 	if (bpp != NULL) {
    190  1.26.2.3       chs 		*bpp = 0;
    191  1.26.2.3       chs 	}
    192       1.1   mycroft 	fs = ip->i_fs;
    193       1.1   mycroft #ifdef DIAGNOSTIC
    194       1.1   mycroft 	if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 ||
    195       1.1   mycroft 	    (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) {
    196      1.13  christos 		printf(
    197       1.1   mycroft 		    "dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n",
    198       1.1   mycroft 		    ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt);
    199       1.1   mycroft 		panic("ffs_realloccg: bad size");
    200       1.1   mycroft 	}
    201       1.1   mycroft 	if (cred == NOCRED)
    202       1.1   mycroft 		panic("ffs_realloccg: missing credential\n");
    203       1.1   mycroft #endif /* DIAGNOSTIC */
    204       1.1   mycroft 	if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0)
    205       1.1   mycroft 		goto nospace;
    206      1.19    bouyer 	if ((bprev = ufs_rw32(ip->i_ffs_db[lbprev], UFS_IPNEEDSWAP(ip))) == 0) {
    207      1.13  christos 		printf("dev = 0x%x, bsize = %d, bprev = %d, fs = %s\n",
    208       1.1   mycroft 		    ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt);
    209       1.1   mycroft 		panic("ffs_realloccg: bad bprev");
    210       1.1   mycroft 	}
    211  1.26.2.1       chs 
    212  1.26.2.1       chs #ifdef QUOTA
    213  1.26.2.1       chs 	if ((error = chkdq(ip, (long)btodb(nsize - osize), cred, 0)) != 0) {
    214  1.26.2.1       chs 		return (error);
    215  1.26.2.1       chs 	}
    216  1.26.2.1       chs #endif
    217  1.26.2.1       chs 
    218       1.1   mycroft 	/*
    219       1.1   mycroft 	 * Allocate the extra space in the buffer.
    220       1.1   mycroft 	 */
    221  1.26.2.1       chs 	if (bpp != NULL &&
    222  1.26.2.1       chs 	    (error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp)) != 0) {
    223       1.1   mycroft 		brelse(bp);
    224       1.1   mycroft 		return (error);
    225       1.1   mycroft 	}
    226  1.26.2.1       chs 
    227       1.1   mycroft 	/*
    228       1.1   mycroft 	 * Check for extension in the existing location.
    229       1.1   mycroft 	 */
    230       1.1   mycroft 	cg = dtog(fs, bprev);
    231       1.9  christos 	if ((bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize)) != 0) {
    232      1.15    bouyer 		ip->i_ffs_blocks += btodb(nsize - osize);
    233       1.1   mycroft 		ip->i_flag |= IN_CHANGE | IN_UPDATE;
    234  1.26.2.1       chs 
    235  1.26.2.1       chs 		if (bpp != NULL) {
    236  1.26.2.1       chs 			if (bp->b_blkno != fsbtodb(fs, bno))
    237  1.26.2.1       chs 				panic("bad blockno");
    238  1.26.2.1       chs 			allocbuf(bp, nsize);
    239  1.26.2.1       chs 			bp->b_flags |= B_DONE;
    240  1.26.2.1       chs 			memset(bp->b_data + osize, 0, nsize - osize);
    241  1.26.2.1       chs 			*bpp = bp;
    242  1.26.2.1       chs 		}
    243  1.26.2.1       chs 		else {
    244  1.26.2.1       chs 			/*
    245  1.26.2.1       chs 			 * XXX do page-cache stuff.
    246  1.26.2.1       chs 			 * I think we don't need to do anything,
    247  1.26.2.1       chs 			 * assuming pages are always zeroed when alloc'd.
    248  1.26.2.1       chs 			 */
    249  1.26.2.1       chs 		}
    250  1.26.2.1       chs 
    251  1.26.2.1       chs 		*blknop = bno;
    252       1.1   mycroft 		return (0);
    253       1.1   mycroft 	}
    254       1.1   mycroft 	/*
    255       1.1   mycroft 	 * Allocate a new disk location.
    256       1.1   mycroft 	 */
    257       1.1   mycroft 	if (bpref >= fs->fs_size)
    258       1.1   mycroft 		bpref = 0;
    259       1.1   mycroft 	switch ((int)fs->fs_optim) {
    260       1.1   mycroft 	case FS_OPTSPACE:
    261       1.1   mycroft 		/*
    262       1.1   mycroft 		 * Allocate an exact sized fragment. Although this makes
    263       1.1   mycroft 		 * best use of space, we will waste time relocating it if
    264       1.1   mycroft 		 * the file continues to grow. If the fragmentation is
    265       1.1   mycroft 		 * less than half of the minimum free reserve, we choose
    266       1.1   mycroft 		 * to begin optimizing for time.
    267       1.1   mycroft 		 */
    268       1.1   mycroft 		request = nsize;
    269       1.1   mycroft 		if (fs->fs_minfree < 5 ||
    270       1.1   mycroft 		    fs->fs_cstotal.cs_nffree >
    271       1.1   mycroft 		    fs->fs_dsize * fs->fs_minfree / (2 * 100))
    272       1.1   mycroft 			break;
    273       1.1   mycroft 		log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n",
    274       1.1   mycroft 			fs->fs_fsmnt);
    275       1.1   mycroft 		fs->fs_optim = FS_OPTTIME;
    276       1.1   mycroft 		break;
    277       1.1   mycroft 	case FS_OPTTIME:
    278       1.1   mycroft 		/*
    279       1.1   mycroft 		 * At this point we have discovered a file that is trying to
    280       1.1   mycroft 		 * grow a small fragment to a larger fragment. To save time,
    281       1.1   mycroft 		 * we allocate a full sized block, then free the unused portion.
    282       1.1   mycroft 		 * If the file continues to grow, the `ffs_fragextend' call
    283       1.1   mycroft 		 * above will be able to grow it in place without further
    284       1.1   mycroft 		 * copying. If aberrant programs cause disk fragmentation to
    285       1.1   mycroft 		 * grow within 2% of the free reserve, we choose to begin
    286       1.1   mycroft 		 * optimizing for space.
    287       1.1   mycroft 		 */
    288       1.1   mycroft 		request = fs->fs_bsize;
    289       1.1   mycroft 		if (fs->fs_cstotal.cs_nffree <
    290       1.1   mycroft 		    fs->fs_dsize * (fs->fs_minfree - 2) / 100)
    291       1.1   mycroft 			break;
    292       1.1   mycroft 		log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n",
    293       1.1   mycroft 			fs->fs_fsmnt);
    294       1.1   mycroft 		fs->fs_optim = FS_OPTSPACE;
    295       1.1   mycroft 		break;
    296       1.1   mycroft 	default:
    297      1.13  christos 		printf("dev = 0x%x, optim = %d, fs = %s\n",
    298       1.1   mycroft 		    ip->i_dev, fs->fs_optim, fs->fs_fsmnt);
    299       1.1   mycroft 		panic("ffs_realloccg: bad optim");
    300       1.1   mycroft 		/* NOTREACHED */
    301       1.1   mycroft 	}
    302      1.18      fvdl 	bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request,
    303       1.9  christos 	    			     ffs_alloccg);
    304       1.1   mycroft 	if (bno > 0) {
    305  1.26.2.1       chs 
    306  1.26.2.1       chs 		if (bpp != NULL) {
    307  1.26.2.1       chs 			bp->b_blkno = fsbtodb(fs, bno);
    308  1.26.2.1       chs 		}
    309  1.26.2.1       chs 		else {
    310  1.26.2.1       chs 			/*
    311  1.26.2.1       chs 			 * re-label cached pages, if any
    312  1.26.2.1       chs 			 */
    313  1.26.2.2       chs 			uvm_vnp_setpageblknos(ITOV(ip), lblktosize(fs, lbprev),
    314  1.26.2.2       chs 					      blkoff(fs, ip->i_ffs_size),
    315  1.26.2.2       chs 					      fsbtodb(fs, bno), UFP_NOALLOC,
    316  1.26.2.2       chs 					      FALSE);
    317  1.26.2.1       chs 		}
    318  1.26.2.1       chs 
    319      1.16       mrg #if defined(UVM)
    320      1.16       mrg 		(void) uvm_vnp_uncache(ITOV(ip));
    321      1.16       mrg #else
    322       1.1   mycroft 		(void) vnode_pager_uncache(ITOV(ip));
    323      1.16       mrg #endif
    324  1.26.2.1       chs 
    325       1.1   mycroft 		ffs_blkfree(ip, bprev, (long)osize);
    326       1.1   mycroft 		if (nsize < request)
    327       1.1   mycroft 			ffs_blkfree(ip, bno + numfrags(fs, nsize),
    328       1.1   mycroft 			    (long)(request - nsize));
    329      1.15    bouyer 		ip->i_ffs_blocks += btodb(nsize - osize);
    330       1.1   mycroft 		ip->i_flag |= IN_CHANGE | IN_UPDATE;
    331  1.26.2.1       chs 
    332  1.26.2.1       chs 		if (bpp != NULL) {
    333  1.26.2.1       chs 			allocbuf(bp, nsize);
    334  1.26.2.1       chs 			bp->b_flags |= B_DONE;
    335  1.26.2.1       chs 			memset(bp->b_data + osize, 0, (u_int)nsize - osize);
    336  1.26.2.1       chs 			*bpp = bp;
    337  1.26.2.1       chs 		}
    338  1.26.2.1       chs 
    339  1.26.2.1       chs 		*blknop = bno;
    340       1.1   mycroft 		return (0);
    341       1.1   mycroft 	}
    342       1.1   mycroft #ifdef QUOTA
    343       1.1   mycroft 	/*
    344       1.1   mycroft 	 * Restore user's disk quota because allocation failed.
    345       1.1   mycroft 	 */
    346       1.1   mycroft 	(void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE);
    347       1.1   mycroft #endif
    348  1.26.2.1       chs 
    349  1.26.2.1       chs 	if (bpp != NULL) {
    350  1.26.2.1       chs 		brelse(bp);
    351  1.26.2.1       chs 	}
    352  1.26.2.1       chs 
    353       1.1   mycroft nospace:
    354       1.1   mycroft 	/*
    355       1.1   mycroft 	 * no space available
    356       1.1   mycroft 	 */
    357       1.1   mycroft 	ffs_fserr(fs, cred->cr_uid, "file system full");
    358       1.1   mycroft 	uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
    359       1.1   mycroft 	return (ENOSPC);
    360       1.1   mycroft }
    361       1.1   mycroft 
    362       1.1   mycroft /*
    363       1.1   mycroft  * Reallocate a sequence of blocks into a contiguous sequence of blocks.
    364       1.1   mycroft  *
    365       1.1   mycroft  * The vnode and an array of buffer pointers for a range of sequential
    366       1.1   mycroft  * logical blocks to be made contiguous is given. The allocator attempts
    367       1.1   mycroft  * to find a range of sequential blocks starting as close as possible to
    368       1.1   mycroft  * an fs_rotdelay offset from the end of the allocation for the logical
    369       1.1   mycroft  * block immediately preceeding the current range. If successful, the
    370       1.1   mycroft  * physical block numbers in the buffer pointers and in the inode are
    371       1.1   mycroft  * changed to reflect the new allocation. If unsuccessful, the allocation
    372       1.1   mycroft  * is left unchanged. The success in doing the reallocation is returned.
    373       1.1   mycroft  * Note that the error return is not reflected back to the user. Rather
    374       1.1   mycroft  * the previous block allocation will be used.
    375       1.1   mycroft  */
    376       1.3   mycroft #ifdef DEBUG
    377       1.1   mycroft #include <sys/sysctl.h>
    378       1.5   mycroft int prtrealloc = 0;
    379       1.5   mycroft struct ctldebug debug15 = { "prtrealloc", &prtrealloc };
    380       1.1   mycroft #endif
    381       1.1   mycroft 
    382      1.18      fvdl int doasyncfree = 1;
    383      1.18      fvdl extern int doreallocblks;
    384      1.18      fvdl 
    385       1.1   mycroft int
    386       1.9  christos ffs_reallocblks(v)
    387       1.9  christos 	void *v;
    388       1.9  christos {
    389       1.1   mycroft 	struct vop_reallocblks_args /* {
    390       1.1   mycroft 		struct vnode *a_vp;
    391       1.1   mycroft 		struct cluster_save *a_buflist;
    392       1.9  christos 	} */ *ap = v;
    393       1.1   mycroft 	struct fs *fs;
    394       1.1   mycroft 	struct inode *ip;
    395       1.1   mycroft 	struct vnode *vp;
    396       1.1   mycroft 	struct buf *sbp, *ebp;
    397      1.18      fvdl 	ufs_daddr_t *bap, *sbap, *ebap = NULL;
    398       1.1   mycroft 	struct cluster_save *buflist;
    399      1.18      fvdl 	ufs_daddr_t start_lbn, end_lbn, soff, newblk, blkno;
    400       1.1   mycroft 	struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp;
    401       1.1   mycroft 	int i, len, start_lvl, end_lvl, pref, ssize;
    402      1.11   mycroft 	struct timespec ts;
    403  1.26.2.1       chs 
    404  1.26.2.1       chs #ifdef UBC
    405  1.26.2.1       chs 	/* XXX don't do this for now */
    406  1.26.2.1       chs 	return ENOSPC;
    407  1.26.2.1       chs #endif
    408       1.1   mycroft 
    409       1.1   mycroft 	vp = ap->a_vp;
    410       1.1   mycroft 	ip = VTOI(vp);
    411       1.1   mycroft 	fs = ip->i_fs;
    412       1.1   mycroft 	if (fs->fs_contigsumsize <= 0)
    413       1.1   mycroft 		return (ENOSPC);
    414       1.1   mycroft 	buflist = ap->a_buflist;
    415       1.1   mycroft 	len = buflist->bs_nchildren;
    416       1.1   mycroft 	start_lbn = buflist->bs_children[0]->b_lblkno;
    417       1.1   mycroft 	end_lbn = start_lbn + len - 1;
    418       1.1   mycroft #ifdef DIAGNOSTIC
    419      1.18      fvdl 	for (i = 0; i < len; i++)
    420      1.18      fvdl 		if (!ffs_checkblk(ip,
    421      1.18      fvdl 		   dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
    422      1.18      fvdl 			panic("ffs_reallocblks: unallocated block 1");
    423       1.1   mycroft 	for (i = 1; i < len; i++)
    424       1.1   mycroft 		if (buflist->bs_children[i]->b_lblkno != start_lbn + i)
    425      1.18      fvdl 			panic("ffs_reallocblks: non-logical cluster");
    426      1.18      fvdl 	blkno = buflist->bs_children[0]->b_blkno;
    427      1.18      fvdl 	ssize = fsbtodb(fs, fs->fs_frag);
    428      1.18      fvdl 	for (i = 1; i < len - 1; i++)
    429      1.18      fvdl 		if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize))
    430      1.18      fvdl 			panic("ffs_reallocblks: non-physical cluster %d", i);
    431       1.1   mycroft #endif
    432       1.1   mycroft 	/*
    433       1.1   mycroft 	 * If the latest allocation is in a new cylinder group, assume that
    434       1.1   mycroft 	 * the filesystem has decided to move and do not force it back to
    435       1.1   mycroft 	 * the previous cylinder group.
    436       1.1   mycroft 	 */
    437       1.1   mycroft 	if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) !=
    438       1.1   mycroft 	    dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno)))
    439       1.1   mycroft 		return (ENOSPC);
    440       1.1   mycroft 	if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) ||
    441       1.1   mycroft 	    ufs_getlbns(vp, end_lbn, end_ap, &end_lvl))
    442       1.1   mycroft 		return (ENOSPC);
    443       1.1   mycroft 	/*
    444       1.1   mycroft 	 * Get the starting offset and block map for the first block.
    445       1.1   mycroft 	 */
    446       1.1   mycroft 	if (start_lvl == 0) {
    447      1.15    bouyer 		sbap = &ip->i_ffs_db[0];
    448       1.1   mycroft 		soff = start_lbn;
    449       1.1   mycroft 	} else {
    450       1.1   mycroft 		idp = &start_ap[start_lvl - 1];
    451       1.1   mycroft 		if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) {
    452       1.1   mycroft 			brelse(sbp);
    453       1.1   mycroft 			return (ENOSPC);
    454       1.1   mycroft 		}
    455      1.18      fvdl 		sbap = (ufs_daddr_t *)sbp->b_data;
    456       1.1   mycroft 		soff = idp->in_off;
    457       1.1   mycroft 	}
    458       1.1   mycroft 	/*
    459       1.1   mycroft 	 * Find the preferred location for the cluster.
    460       1.1   mycroft 	 */
    461       1.1   mycroft 	pref = ffs_blkpref(ip, start_lbn, soff, sbap);
    462       1.1   mycroft 	/*
    463       1.1   mycroft 	 * If the block range spans two block maps, get the second map.
    464       1.1   mycroft 	 */
    465       1.1   mycroft 	if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
    466       1.1   mycroft 		ssize = len;
    467       1.1   mycroft 	} else {
    468       1.1   mycroft #ifdef DIAGNOSTIC
    469       1.1   mycroft 		if (start_ap[start_lvl-1].in_lbn == idp->in_lbn)
    470       1.1   mycroft 			panic("ffs_reallocblk: start == end");
    471       1.1   mycroft #endif
    472       1.1   mycroft 		ssize = len - (idp->in_off + 1);
    473       1.1   mycroft 		if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp))
    474       1.1   mycroft 			goto fail;
    475      1.18      fvdl 		ebap = (ufs_daddr_t *)ebp->b_data;
    476       1.1   mycroft 	}
    477       1.1   mycroft 	/*
    478       1.1   mycroft 	 * Search the block map looking for an allocation of the desired size.
    479       1.1   mycroft 	 */
    480      1.18      fvdl 	if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref,
    481       1.9  christos 	    len, ffs_clusteralloc)) == 0)
    482       1.1   mycroft 		goto fail;
    483       1.1   mycroft 	/*
    484       1.1   mycroft 	 * We have found a new contiguous block.
    485       1.1   mycroft 	 *
    486       1.1   mycroft 	 * First we have to replace the old block pointers with the new
    487       1.1   mycroft 	 * block pointers in the inode and indirect blocks associated
    488       1.1   mycroft 	 * with the file.
    489       1.1   mycroft 	 */
    490       1.5   mycroft #ifdef DEBUG
    491       1.5   mycroft 	if (prtrealloc)
    492      1.13  christos 		printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number,
    493       1.5   mycroft 		    start_lbn, end_lbn);
    494       1.5   mycroft #endif
    495       1.1   mycroft 	blkno = newblk;
    496       1.1   mycroft 	for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) {
    497       1.1   mycroft 		if (i == ssize)
    498       1.1   mycroft 			bap = ebap;
    499       1.1   mycroft #ifdef DIAGNOSTIC
    500      1.18      fvdl 		if (!ffs_checkblk(ip,
    501      1.18      fvdl 		   dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
    502      1.18      fvdl 			panic("ffs_reallocblks: unallocated block 2");
    503      1.19    bouyer 		if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) !=
    504      1.19    bouyer 			ufs_rw32(*bap, UFS_MPNEEDSWAP(vp->v_mount)))
    505       1.1   mycroft 			panic("ffs_reallocblks: alloc mismatch");
    506       1.1   mycroft #endif
    507       1.5   mycroft #ifdef DEBUG
    508       1.5   mycroft 		if (prtrealloc)
    509      1.19    bouyer 			printf(" %d,", ufs_rw32(*bap, UFS_MPNEEDSWAP(vp->v_mount)));
    510       1.5   mycroft #endif
    511      1.19    bouyer 		*bap++ = ufs_rw32(blkno, UFS_MPNEEDSWAP(vp->v_mount));
    512       1.1   mycroft 	}
    513       1.1   mycroft 	/*
    514       1.1   mycroft 	 * Next we must write out the modified inode and indirect blocks.
    515       1.1   mycroft 	 * For strict correctness, the writes should be synchronous since
    516       1.1   mycroft 	 * the old block values may have been written to disk. In practise
    517       1.1   mycroft 	 * they are almost never written, but if we are concerned about
    518       1.1   mycroft 	 * strict correctness, the `doasyncfree' flag should be set to zero.
    519       1.1   mycroft 	 *
    520       1.1   mycroft 	 * The test on `doasyncfree' should be changed to test a flag
    521       1.1   mycroft 	 * that shows whether the associated buffers and inodes have
    522       1.1   mycroft 	 * been written. The flag should be set when the cluster is
    523       1.1   mycroft 	 * started and cleared whenever the buffer or inode is flushed.
    524       1.1   mycroft 	 * We can then check below to see if it is set, and do the
    525       1.1   mycroft 	 * synchronous write only when it has been cleared.
    526       1.1   mycroft 	 */
    527      1.15    bouyer 	if (sbap != &ip->i_ffs_db[0]) {
    528       1.1   mycroft 		if (doasyncfree)
    529       1.1   mycroft 			bdwrite(sbp);
    530       1.1   mycroft 		else
    531       1.1   mycroft 			bwrite(sbp);
    532       1.1   mycroft 	} else {
    533       1.1   mycroft 		ip->i_flag |= IN_CHANGE | IN_UPDATE;
    534      1.11   mycroft 		if (!doasyncfree) {
    535      1.11   mycroft 			TIMEVAL_TO_TIMESPEC(&time, &ts);
    536      1.11   mycroft 			VOP_UPDATE(vp, &ts, &ts, 1);
    537      1.11   mycroft 		}
    538       1.1   mycroft 	}
    539      1.25   thorpej 	if (ssize < len) {
    540       1.1   mycroft 		if (doasyncfree)
    541       1.1   mycroft 			bdwrite(ebp);
    542       1.1   mycroft 		else
    543       1.1   mycroft 			bwrite(ebp);
    544      1.25   thorpej 	}
    545       1.1   mycroft 	/*
    546       1.1   mycroft 	 * Last, free the old blocks and assign the new blocks to the buffers.
    547       1.1   mycroft 	 */
    548       1.5   mycroft #ifdef DEBUG
    549       1.5   mycroft 	if (prtrealloc)
    550      1.13  christos 		printf("\n\tnew:");
    551       1.5   mycroft #endif
    552       1.1   mycroft 	for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) {
    553       1.1   mycroft 		ffs_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno),
    554       1.1   mycroft 		    fs->fs_bsize);
    555       1.1   mycroft 		buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno);
    556       1.5   mycroft #ifdef DEBUG
    557      1.18      fvdl 		if (!ffs_checkblk(ip,
    558      1.18      fvdl 		   dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
    559      1.18      fvdl 			panic("ffs_reallocblks: unallocated block 3");
    560       1.5   mycroft 		if (prtrealloc)
    561      1.13  christos 			printf(" %d,", blkno);
    562       1.5   mycroft #endif
    563       1.5   mycroft 	}
    564       1.5   mycroft #ifdef DEBUG
    565       1.5   mycroft 	if (prtrealloc) {
    566       1.5   mycroft 		prtrealloc--;
    567      1.13  christos 		printf("\n");
    568       1.1   mycroft 	}
    569       1.5   mycroft #endif
    570       1.1   mycroft 	return (0);
    571       1.1   mycroft 
    572       1.1   mycroft fail:
    573       1.1   mycroft 	if (ssize < len)
    574       1.1   mycroft 		brelse(ebp);
    575      1.15    bouyer 	if (sbap != &ip->i_ffs_db[0])
    576       1.1   mycroft 		brelse(sbp);
    577       1.1   mycroft 	return (ENOSPC);
    578       1.1   mycroft }
    579       1.1   mycroft 
    580       1.1   mycroft /*
    581       1.1   mycroft  * Allocate an inode in the file system.
    582       1.1   mycroft  *
    583       1.1   mycroft  * If allocating a directory, use ffs_dirpref to select the inode.
    584       1.1   mycroft  * If allocating in a directory, the following hierarchy is followed:
    585       1.1   mycroft  *   1) allocate the preferred inode.
    586       1.1   mycroft  *   2) allocate an inode in the same cylinder group.
    587       1.1   mycroft  *   3) quadradically rehash into other cylinder groups, until an
    588       1.1   mycroft  *      available inode is located.
    589       1.1   mycroft  * If no inode preference is given the following heirarchy is used
    590       1.1   mycroft  * to allocate an inode:
    591       1.1   mycroft  *   1) allocate an inode in cylinder group 0.
    592       1.1   mycroft  *   2) quadradically rehash into other cylinder groups, until an
    593       1.1   mycroft  *      available inode is located.
    594       1.1   mycroft  */
    595       1.9  christos int
    596       1.9  christos ffs_valloc(v)
    597       1.9  christos 	void *v;
    598       1.9  christos {
    599       1.1   mycroft 	struct vop_valloc_args /* {
    600       1.1   mycroft 		struct vnode *a_pvp;
    601       1.1   mycroft 		int a_mode;
    602       1.1   mycroft 		struct ucred *a_cred;
    603       1.1   mycroft 		struct vnode **a_vpp;
    604       1.9  christos 	} */ *ap = v;
    605       1.1   mycroft 	register struct vnode *pvp = ap->a_pvp;
    606       1.1   mycroft 	register struct inode *pip;
    607       1.1   mycroft 	register struct fs *fs;
    608       1.1   mycroft 	register struct inode *ip;
    609       1.1   mycroft 	mode_t mode = ap->a_mode;
    610       1.1   mycroft 	ino_t ino, ipref;
    611       1.1   mycroft 	int cg, error;
    612       1.1   mycroft 
    613       1.1   mycroft 	*ap->a_vpp = NULL;
    614       1.1   mycroft 	pip = VTOI(pvp);
    615       1.1   mycroft 	fs = pip->i_fs;
    616       1.1   mycroft 	if (fs->fs_cstotal.cs_nifree == 0)
    617       1.1   mycroft 		goto noinodes;
    618       1.1   mycroft 
    619       1.1   mycroft 	if ((mode & IFMT) == IFDIR)
    620       1.1   mycroft 		ipref = ffs_dirpref(fs);
    621       1.1   mycroft 	else
    622       1.1   mycroft 		ipref = pip->i_number;
    623       1.1   mycroft 	if (ipref >= fs->fs_ncg * fs->fs_ipg)
    624       1.1   mycroft 		ipref = 0;
    625       1.1   mycroft 	cg = ino_to_cg(fs, ipref);
    626       1.1   mycroft 	ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, ffs_nodealloccg);
    627       1.1   mycroft 	if (ino == 0)
    628       1.1   mycroft 		goto noinodes;
    629       1.1   mycroft 	error = VFS_VGET(pvp->v_mount, ino, ap->a_vpp);
    630       1.1   mycroft 	if (error) {
    631       1.1   mycroft 		VOP_VFREE(pvp, ino, mode);
    632       1.1   mycroft 		return (error);
    633       1.1   mycroft 	}
    634       1.1   mycroft 	ip = VTOI(*ap->a_vpp);
    635      1.15    bouyer 	if (ip->i_ffs_mode) {
    636      1.13  christos 		printf("mode = 0%o, inum = %d, fs = %s\n",
    637      1.15    bouyer 		    ip->i_ffs_mode, ip->i_number, fs->fs_fsmnt);
    638       1.1   mycroft 		panic("ffs_valloc: dup alloc");
    639       1.1   mycroft 	}
    640      1.15    bouyer 	if (ip->i_ffs_blocks) {				/* XXX */
    641      1.13  christos 		printf("free inode %s/%d had %d blocks\n",
    642      1.15    bouyer 		    fs->fs_fsmnt, ino, ip->i_ffs_blocks);
    643      1.15    bouyer 		ip->i_ffs_blocks = 0;
    644       1.1   mycroft 	}
    645      1.15    bouyer 	ip->i_ffs_flags = 0;
    646       1.1   mycroft 	/*
    647       1.1   mycroft 	 * Set up a new generation number for this inode.
    648       1.1   mycroft 	 */
    649      1.15    bouyer 	ip->i_ffs_gen++;
    650       1.1   mycroft 	return (0);
    651       1.1   mycroft noinodes:
    652       1.1   mycroft 	ffs_fserr(fs, ap->a_cred->cr_uid, "out of inodes");
    653       1.1   mycroft 	uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt);
    654       1.1   mycroft 	return (ENOSPC);
    655       1.1   mycroft }
    656       1.1   mycroft 
    657       1.1   mycroft /*
    658       1.1   mycroft  * Find a cylinder to place a directory.
    659       1.1   mycroft  *
    660       1.1   mycroft  * The policy implemented by this algorithm is to select from
    661       1.1   mycroft  * among those cylinder groups with above the average number of
    662       1.1   mycroft  * free inodes, the one with the smallest number of directories.
    663       1.1   mycroft  */
    664       1.1   mycroft static ino_t
    665       1.1   mycroft ffs_dirpref(fs)
    666       1.1   mycroft 	register struct fs *fs;
    667       1.1   mycroft {
    668       1.1   mycroft 	int cg, minndir, mincg, avgifree;
    669       1.1   mycroft 
    670       1.1   mycroft 	avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg;
    671       1.1   mycroft 	minndir = fs->fs_ipg;
    672       1.1   mycroft 	mincg = 0;
    673       1.1   mycroft 	for (cg = 0; cg < fs->fs_ncg; cg++)
    674       1.1   mycroft 		if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
    675       1.1   mycroft 		    fs->fs_cs(fs, cg).cs_nifree >= avgifree) {
    676       1.1   mycroft 			mincg = cg;
    677       1.1   mycroft 			minndir = fs->fs_cs(fs, cg).cs_ndir;
    678       1.1   mycroft 		}
    679       1.1   mycroft 	return ((ino_t)(fs->fs_ipg * mincg));
    680       1.1   mycroft }
    681       1.1   mycroft 
    682       1.1   mycroft /*
    683       1.1   mycroft  * Select the desired position for the next block in a file.  The file is
    684       1.1   mycroft  * logically divided into sections. The first section is composed of the
    685       1.1   mycroft  * direct blocks. Each additional section contains fs_maxbpg blocks.
    686       1.1   mycroft  *
    687       1.1   mycroft  * If no blocks have been allocated in the first section, the policy is to
    688       1.1   mycroft  * request a block in the same cylinder group as the inode that describes
    689       1.1   mycroft  * the file. If no blocks have been allocated in any other section, the
    690       1.1   mycroft  * policy is to place the section in a cylinder group with a greater than
    691       1.1   mycroft  * average number of free blocks.  An appropriate cylinder group is found
    692       1.1   mycroft  * by using a rotor that sweeps the cylinder groups. When a new group of
    693       1.1   mycroft  * blocks is needed, the sweep begins in the cylinder group following the
    694       1.1   mycroft  * cylinder group from which the previous allocation was made. The sweep
    695       1.1   mycroft  * continues until a cylinder group with greater than the average number
    696       1.1   mycroft  * of free blocks is found. If the allocation is for the first block in an
    697       1.1   mycroft  * indirect block, the information on the previous allocation is unavailable;
    698       1.1   mycroft  * here a best guess is made based upon the logical block number being
    699       1.1   mycroft  * allocated.
    700       1.1   mycroft  *
    701       1.1   mycroft  * If a section is already partially allocated, the policy is to
    702       1.1   mycroft  * contiguously allocate fs_maxcontig blocks.  The end of one of these
    703       1.1   mycroft  * contiguous blocks and the beginning of the next is physically separated
    704       1.1   mycroft  * so that the disk head will be in transit between them for at least
    705       1.1   mycroft  * fs_rotdelay milliseconds.  This is to allow time for the processor to
    706       1.1   mycroft  * schedule another I/O transfer.
    707       1.1   mycroft  */
    708      1.18      fvdl ufs_daddr_t
    709       1.1   mycroft ffs_blkpref(ip, lbn, indx, bap)
    710       1.1   mycroft 	struct inode *ip;
    711      1.18      fvdl 	ufs_daddr_t lbn;
    712       1.1   mycroft 	int indx;
    713      1.18      fvdl 	ufs_daddr_t *bap;
    714       1.1   mycroft {
    715       1.1   mycroft 	register struct fs *fs;
    716       1.1   mycroft 	register int cg;
    717       1.1   mycroft 	int avgbfree, startcg;
    718      1.18      fvdl 	ufs_daddr_t nextblk;
    719       1.1   mycroft 
    720       1.1   mycroft 	fs = ip->i_fs;
    721       1.1   mycroft 	if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) {
    722       1.1   mycroft 		if (lbn < NDADDR) {
    723       1.1   mycroft 			cg = ino_to_cg(fs, ip->i_number);
    724       1.1   mycroft 			return (fs->fs_fpg * cg + fs->fs_frag);
    725       1.1   mycroft 		}
    726       1.1   mycroft 		/*
    727       1.1   mycroft 		 * Find a cylinder with greater than average number of
    728       1.1   mycroft 		 * unused data blocks.
    729       1.1   mycroft 		 */
    730       1.1   mycroft 		if (indx == 0 || bap[indx - 1] == 0)
    731       1.1   mycroft 			startcg =
    732       1.1   mycroft 			    ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg;
    733       1.1   mycroft 		else
    734      1.19    bouyer 			startcg = dtog(fs,
    735      1.19    bouyer 				ufs_rw32(bap[indx - 1], UFS_IPNEEDSWAP(ip)) + 1);
    736       1.1   mycroft 		startcg %= fs->fs_ncg;
    737       1.1   mycroft 		avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
    738       1.1   mycroft 		for (cg = startcg; cg < fs->fs_ncg; cg++)
    739       1.1   mycroft 			if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
    740       1.1   mycroft 				fs->fs_cgrotor = cg;
    741       1.1   mycroft 				return (fs->fs_fpg * cg + fs->fs_frag);
    742       1.1   mycroft 			}
    743       1.1   mycroft 		for (cg = 0; cg <= startcg; cg++)
    744       1.1   mycroft 			if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
    745       1.1   mycroft 				fs->fs_cgrotor = cg;
    746       1.1   mycroft 				return (fs->fs_fpg * cg + fs->fs_frag);
    747       1.1   mycroft 			}
    748       1.1   mycroft 		return (NULL);
    749       1.1   mycroft 	}
    750       1.1   mycroft 	/*
    751       1.1   mycroft 	 * One or more previous blocks have been laid out. If less
    752       1.1   mycroft 	 * than fs_maxcontig previous blocks are contiguous, the
    753       1.1   mycroft 	 * next block is requested contiguously, otherwise it is
    754       1.1   mycroft 	 * requested rotationally delayed by fs_rotdelay milliseconds.
    755       1.1   mycroft 	 */
    756      1.19    bouyer 	nextblk = ufs_rw32(bap[indx - 1], UFS_IPNEEDSWAP(ip)) + fs->fs_frag;
    757      1.19    bouyer 	if (indx < fs->fs_maxcontig ||
    758      1.19    bouyer 		ufs_rw32(bap[indx - fs->fs_maxcontig], UFS_IPNEEDSWAP(ip)) +
    759       1.1   mycroft 	    blkstofrags(fs, fs->fs_maxcontig) != nextblk)
    760       1.1   mycroft 		return (nextblk);
    761       1.1   mycroft 	if (fs->fs_rotdelay != 0)
    762       1.1   mycroft 		/*
    763       1.1   mycroft 		 * Here we convert ms of delay to frags as:
    764       1.1   mycroft 		 * (frags) = (ms) * (rev/sec) * (sect/rev) /
    765       1.1   mycroft 		 *	((sect/frag) * (ms/sec))
    766       1.1   mycroft 		 * then round up to the next block.
    767       1.1   mycroft 		 */
    768       1.1   mycroft 		nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect /
    769       1.1   mycroft 		    (NSPF(fs) * 1000), fs->fs_frag);
    770       1.1   mycroft 	return (nextblk);
    771       1.1   mycroft }
    772       1.1   mycroft 
    773       1.1   mycroft /*
    774       1.1   mycroft  * Implement the cylinder overflow algorithm.
    775       1.1   mycroft  *
    776       1.1   mycroft  * The policy implemented by this algorithm is:
    777       1.1   mycroft  *   1) allocate the block in its requested cylinder group.
    778       1.1   mycroft  *   2) quadradically rehash on the cylinder group number.
    779       1.1   mycroft  *   3) brute force search for a free block.
    780       1.1   mycroft  */
    781       1.1   mycroft /*VARARGS5*/
    782       1.1   mycroft static u_long
    783       1.1   mycroft ffs_hashalloc(ip, cg, pref, size, allocator)
    784       1.1   mycroft 	struct inode *ip;
    785       1.1   mycroft 	int cg;
    786       1.1   mycroft 	long pref;
    787       1.1   mycroft 	int size;	/* size for data blocks, mode for inodes */
    788      1.18      fvdl 	ufs_daddr_t (*allocator) __P((struct inode *, int, ufs_daddr_t, int));
    789       1.1   mycroft {
    790       1.1   mycroft 	register struct fs *fs;
    791       1.1   mycroft 	long result;
    792       1.1   mycroft 	int i, icg = cg;
    793       1.1   mycroft 
    794       1.1   mycroft 	fs = ip->i_fs;
    795       1.1   mycroft 	/*
    796       1.1   mycroft 	 * 1: preferred cylinder group
    797       1.1   mycroft 	 */
    798       1.1   mycroft 	result = (*allocator)(ip, cg, pref, size);
    799       1.1   mycroft 	if (result)
    800       1.1   mycroft 		return (result);
    801       1.1   mycroft 	/*
    802       1.1   mycroft 	 * 2: quadratic rehash
    803       1.1   mycroft 	 */
    804       1.1   mycroft 	for (i = 1; i < fs->fs_ncg; i *= 2) {
    805       1.1   mycroft 		cg += i;
    806       1.1   mycroft 		if (cg >= fs->fs_ncg)
    807       1.1   mycroft 			cg -= fs->fs_ncg;
    808       1.1   mycroft 		result = (*allocator)(ip, cg, 0, size);
    809       1.1   mycroft 		if (result)
    810       1.1   mycroft 			return (result);
    811       1.1   mycroft 	}
    812       1.1   mycroft 	/*
    813       1.1   mycroft 	 * 3: brute force search
    814       1.1   mycroft 	 * Note that we start at i == 2, since 0 was checked initially,
    815       1.1   mycroft 	 * and 1 is always checked in the quadratic rehash.
    816       1.1   mycroft 	 */
    817       1.1   mycroft 	cg = (icg + 2) % fs->fs_ncg;
    818       1.1   mycroft 	for (i = 2; i < fs->fs_ncg; i++) {
    819       1.1   mycroft 		result = (*allocator)(ip, cg, 0, size);
    820       1.1   mycroft 		if (result)
    821       1.1   mycroft 			return (result);
    822       1.1   mycroft 		cg++;
    823       1.1   mycroft 		if (cg == fs->fs_ncg)
    824       1.1   mycroft 			cg = 0;
    825       1.1   mycroft 	}
    826       1.1   mycroft 	return (NULL);
    827       1.1   mycroft }
    828       1.1   mycroft 
    829       1.1   mycroft /*
    830       1.1   mycroft  * Determine whether a fragment can be extended.
    831       1.1   mycroft  *
    832       1.1   mycroft  * Check to see if the necessary fragments are available, and
    833       1.1   mycroft  * if they are, allocate them.
    834       1.1   mycroft  */
    835      1.18      fvdl static ufs_daddr_t
    836       1.1   mycroft ffs_fragextend(ip, cg, bprev, osize, nsize)
    837       1.1   mycroft 	struct inode *ip;
    838       1.1   mycroft 	int cg;
    839       1.1   mycroft 	long bprev;
    840       1.1   mycroft 	int osize, nsize;
    841       1.1   mycroft {
    842       1.1   mycroft 	register struct fs *fs;
    843       1.1   mycroft 	register struct cg *cgp;
    844       1.1   mycroft 	struct buf *bp;
    845       1.1   mycroft 	long bno;
    846       1.1   mycroft 	int frags, bbase;
    847       1.1   mycroft 	int i, error;
    848       1.1   mycroft 
    849       1.1   mycroft 	fs = ip->i_fs;
    850       1.1   mycroft 	if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize))
    851       1.1   mycroft 		return (NULL);
    852       1.1   mycroft 	frags = numfrags(fs, nsize);
    853       1.1   mycroft 	bbase = fragnum(fs, bprev);
    854       1.1   mycroft 	if (bbase > fragnum(fs, (bprev + frags - 1))) {
    855       1.1   mycroft 		/* cannot extend across a block boundary */
    856       1.1   mycroft 		return (NULL);
    857       1.1   mycroft 	}
    858       1.1   mycroft 	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
    859       1.1   mycroft 		(int)fs->fs_cgsize, NOCRED, &bp);
    860       1.1   mycroft 	if (error) {
    861       1.1   mycroft 		brelse(bp);
    862       1.1   mycroft 		return (NULL);
    863       1.1   mycroft 	}
    864       1.1   mycroft 	cgp = (struct cg *)bp->b_data;
    865      1.19    bouyer 	if (!cg_chkmagic(cgp, UFS_IPNEEDSWAP(ip))) {
    866       1.1   mycroft 		brelse(bp);
    867       1.1   mycroft 		return (NULL);
    868       1.1   mycroft 	}
    869      1.19    bouyer 	cgp->cg_time = ufs_rw32(time.tv_sec, UFS_IPNEEDSWAP(ip));
    870       1.1   mycroft 	bno = dtogd(fs, bprev);
    871       1.1   mycroft 	for (i = numfrags(fs, osize); i < frags; i++)
    872      1.19    bouyer 		if (isclr(cg_blksfree(cgp, UFS_IPNEEDSWAP(ip)), bno + i)) {
    873       1.1   mycroft 			brelse(bp);
    874       1.1   mycroft 			return (NULL);
    875       1.1   mycroft 		}
    876       1.1   mycroft 	/*
    877       1.1   mycroft 	 * the current fragment can be extended
    878       1.1   mycroft 	 * deduct the count on fragment being extended into
    879       1.1   mycroft 	 * increase the count on the remaining fragment (if any)
    880       1.1   mycroft 	 * allocate the extended piece
    881       1.1   mycroft 	 */
    882       1.1   mycroft 	for (i = frags; i < fs->fs_frag - bbase; i++)
    883      1.19    bouyer 		if (isclr(cg_blksfree(cgp, UFS_IPNEEDSWAP(ip)), bno + i))
    884       1.1   mycroft 			break;
    885      1.19    bouyer 	ufs_add32(cgp->cg_frsum[i - numfrags(fs, osize)], -1, UFS_IPNEEDSWAP(ip));
    886       1.1   mycroft 	if (i != frags)
    887      1.19    bouyer 		ufs_add32(cgp->cg_frsum[i - frags], 1, UFS_IPNEEDSWAP(ip));
    888       1.1   mycroft 	for (i = numfrags(fs, osize); i < frags; i++) {
    889      1.19    bouyer 		clrbit(cg_blksfree(cgp, UFS_IPNEEDSWAP(ip)), bno + i);
    890      1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_nffree, -1, UFS_IPNEEDSWAP(ip));
    891       1.1   mycroft 		fs->fs_cstotal.cs_nffree--;
    892       1.1   mycroft 		fs->fs_cs(fs, cg).cs_nffree--;
    893       1.1   mycroft 	}
    894       1.1   mycroft 	fs->fs_fmod = 1;
    895       1.1   mycroft 	bdwrite(bp);
    896       1.1   mycroft 	return (bprev);
    897       1.1   mycroft }
    898       1.1   mycroft 
    899       1.1   mycroft /*
    900       1.1   mycroft  * Determine whether a block can be allocated.
    901       1.1   mycroft  *
    902       1.1   mycroft  * Check to see if a block of the appropriate size is available,
    903       1.1   mycroft  * and if it is, allocate it.
    904       1.1   mycroft  */
    905      1.18      fvdl static ufs_daddr_t
    906       1.1   mycroft ffs_alloccg(ip, cg, bpref, size)
    907       1.1   mycroft 	struct inode *ip;
    908       1.1   mycroft 	int cg;
    909      1.18      fvdl 	ufs_daddr_t bpref;
    910       1.1   mycroft 	int size;
    911       1.1   mycroft {
    912       1.1   mycroft 	register struct fs *fs;
    913       1.1   mycroft 	register struct cg *cgp;
    914       1.1   mycroft 	struct buf *bp;
    915       1.1   mycroft 	register int i;
    916       1.1   mycroft 	int error, bno, frags, allocsiz;
    917      1.19    bouyer 	const int needswap = UFS_IPNEEDSWAP(ip);
    918       1.1   mycroft 
    919       1.1   mycroft 	fs = ip->i_fs;
    920       1.1   mycroft 	if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize)
    921       1.1   mycroft 		return (NULL);
    922       1.1   mycroft 	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
    923       1.1   mycroft 		(int)fs->fs_cgsize, NOCRED, &bp);
    924       1.1   mycroft 	if (error) {
    925       1.1   mycroft 		brelse(bp);
    926       1.1   mycroft 		return (NULL);
    927       1.1   mycroft 	}
    928       1.1   mycroft 	cgp = (struct cg *)bp->b_data;
    929      1.19    bouyer 	if (!cg_chkmagic(cgp, needswap) ||
    930       1.1   mycroft 	    (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) {
    931       1.1   mycroft 		brelse(bp);
    932       1.1   mycroft 		return (NULL);
    933       1.1   mycroft 	}
    934      1.19    bouyer 	cgp->cg_time = ufs_rw32(time.tv_sec, needswap);
    935       1.1   mycroft 	if (size == fs->fs_bsize) {
    936      1.19    bouyer 		bno = ffs_alloccgblk(ITOV(ip)->v_mount, fs, cgp, bpref);
    937       1.1   mycroft 		bdwrite(bp);
    938       1.1   mycroft 		return (bno);
    939       1.1   mycroft 	}
    940       1.1   mycroft 	/*
    941       1.1   mycroft 	 * check to see if any fragments are already available
    942       1.1   mycroft 	 * allocsiz is the size which will be allocated, hacking
    943       1.1   mycroft 	 * it down to a smaller size if necessary
    944       1.1   mycroft 	 */
    945       1.1   mycroft 	frags = numfrags(fs, size);
    946       1.1   mycroft 	for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++)
    947       1.1   mycroft 		if (cgp->cg_frsum[allocsiz] != 0)
    948       1.1   mycroft 			break;
    949       1.1   mycroft 	if (allocsiz == fs->fs_frag) {
    950       1.1   mycroft 		/*
    951       1.1   mycroft 		 * no fragments were available, so a block will be
    952       1.1   mycroft 		 * allocated, and hacked up
    953       1.1   mycroft 		 */
    954       1.1   mycroft 		if (cgp->cg_cs.cs_nbfree == 0) {
    955       1.1   mycroft 			brelse(bp);
    956       1.1   mycroft 			return (NULL);
    957       1.1   mycroft 		}
    958      1.19    bouyer 		bno = ffs_alloccgblk(ITOV(ip)->v_mount, fs, cgp, bpref);
    959       1.1   mycroft 		bpref = dtogd(fs, bno);
    960       1.1   mycroft 		for (i = frags; i < fs->fs_frag; i++)
    961      1.19    bouyer 			setbit(cg_blksfree(cgp, needswap), bpref + i);
    962       1.1   mycroft 		i = fs->fs_frag - frags;
    963      1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_nffree, i, needswap);
    964       1.1   mycroft 		fs->fs_cstotal.cs_nffree += i;
    965      1.19    bouyer 		fs->fs_cs(fs, cg).cs_nffree +=i;
    966       1.1   mycroft 		fs->fs_fmod = 1;
    967      1.19    bouyer 		ufs_add32(cgp->cg_frsum[i], 1, needswap);
    968       1.1   mycroft 		bdwrite(bp);
    969       1.1   mycroft 		return (bno);
    970       1.1   mycroft 	}
    971      1.19    bouyer 	bno = ffs_mapsearch(needswap, fs, cgp, bpref, allocsiz);
    972       1.1   mycroft 	if (bno < 0) {
    973       1.1   mycroft 		brelse(bp);
    974       1.1   mycroft 		return (NULL);
    975       1.1   mycroft 	}
    976       1.1   mycroft 	for (i = 0; i < frags; i++)
    977      1.19    bouyer 		clrbit(cg_blksfree(cgp, needswap), bno + i);
    978      1.19    bouyer 	ufs_add32(cgp->cg_cs.cs_nffree, -frags, needswap);
    979       1.1   mycroft 	fs->fs_cstotal.cs_nffree -= frags;
    980       1.1   mycroft 	fs->fs_cs(fs, cg).cs_nffree -= frags;
    981       1.1   mycroft 	fs->fs_fmod = 1;
    982      1.19    bouyer 	ufs_add32(cgp->cg_frsum[allocsiz], -1, needswap);
    983       1.1   mycroft 	if (frags != allocsiz)
    984      1.19    bouyer 		ufs_add32(cgp->cg_frsum[allocsiz - frags], 1, needswap);
    985       1.1   mycroft 	bdwrite(bp);
    986       1.1   mycroft 	return (cg * fs->fs_fpg + bno);
    987       1.1   mycroft }
    988       1.1   mycroft 
    989       1.1   mycroft /*
    990       1.1   mycroft  * Allocate a block in a cylinder group.
    991       1.1   mycroft  *
    992       1.1   mycroft  * This algorithm implements the following policy:
    993       1.1   mycroft  *   1) allocate the requested block.
    994       1.1   mycroft  *   2) allocate a rotationally optimal block in the same cylinder.
    995       1.1   mycroft  *   3) allocate the next available block on the block rotor for the
    996       1.1   mycroft  *      specified cylinder group.
    997       1.1   mycroft  * Note that this routine only allocates fs_bsize blocks; these
    998       1.1   mycroft  * blocks may be fragmented by the routine that allocates them.
    999       1.1   mycroft  */
   1000      1.18      fvdl static ufs_daddr_t
   1001      1.19    bouyer ffs_alloccgblk(mp, fs, cgp, bpref)
   1002      1.19    bouyer 	struct  mount *mp;
   1003       1.1   mycroft 	register struct fs *fs;
   1004       1.1   mycroft 	register struct cg *cgp;
   1005      1.18      fvdl 	ufs_daddr_t bpref;
   1006       1.1   mycroft {
   1007      1.18      fvdl 	ufs_daddr_t bno, blkno;
   1008       1.1   mycroft 	int cylno, pos, delta;
   1009       1.1   mycroft 	short *cylbp;
   1010       1.1   mycroft 	register int i;
   1011      1.19    bouyer 	const int needswap = UFS_MPNEEDSWAP(mp);
   1012       1.1   mycroft 
   1013      1.19    bouyer 	if (bpref == 0 ||
   1014      1.19    bouyer 		dtog(fs, bpref) != ufs_rw32(cgp->cg_cgx, needswap)) {
   1015      1.19    bouyer 		bpref = ufs_rw32(cgp->cg_rotor, needswap);
   1016       1.1   mycroft 		goto norot;
   1017       1.1   mycroft 	}
   1018       1.1   mycroft 	bpref = blknum(fs, bpref);
   1019       1.1   mycroft 	bpref = dtogd(fs, bpref);
   1020       1.1   mycroft 	/*
   1021       1.1   mycroft 	 * if the requested block is available, use it
   1022       1.1   mycroft 	 */
   1023      1.19    bouyer 	if (ffs_isblock(fs, cg_blksfree(cgp, needswap),
   1024      1.19    bouyer 		fragstoblks(fs, bpref))) {
   1025       1.1   mycroft 		bno = bpref;
   1026       1.1   mycroft 		goto gotit;
   1027       1.1   mycroft 	}
   1028      1.18      fvdl 	if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) {
   1029       1.1   mycroft 		/*
   1030       1.1   mycroft 		 * Block layout information is not available.
   1031       1.1   mycroft 		 * Leaving bpref unchanged means we take the
   1032       1.1   mycroft 		 * next available free block following the one
   1033       1.1   mycroft 		 * we just allocated. Hopefully this will at
   1034       1.1   mycroft 		 * least hit a track cache on drives of unknown
   1035       1.1   mycroft 		 * geometry (e.g. SCSI).
   1036       1.1   mycroft 		 */
   1037       1.1   mycroft 		goto norot;
   1038       1.1   mycroft 	}
   1039       1.6   mycroft 	/*
   1040       1.6   mycroft 	 * check for a block available on the same cylinder
   1041       1.6   mycroft 	 */
   1042       1.6   mycroft 	cylno = cbtocylno(fs, bpref);
   1043      1.19    bouyer 	if (cg_blktot(cgp, needswap)[cylno] == 0)
   1044       1.6   mycroft 		goto norot;
   1045       1.1   mycroft 	/*
   1046       1.1   mycroft 	 * check the summary information to see if a block is
   1047       1.1   mycroft 	 * available in the requested cylinder starting at the
   1048       1.1   mycroft 	 * requested rotational position and proceeding around.
   1049       1.1   mycroft 	 */
   1050      1.19    bouyer 	cylbp = cg_blks(fs, cgp, cylno, needswap);
   1051       1.1   mycroft 	pos = cbtorpos(fs, bpref);
   1052       1.1   mycroft 	for (i = pos; i < fs->fs_nrpos; i++)
   1053      1.19    bouyer 		if (ufs_rw16(cylbp[i], needswap) > 0)
   1054       1.1   mycroft 			break;
   1055       1.1   mycroft 	if (i == fs->fs_nrpos)
   1056       1.1   mycroft 		for (i = 0; i < pos; i++)
   1057      1.19    bouyer 			if (ufs_rw16(cylbp[i], needswap) > 0)
   1058       1.1   mycroft 				break;
   1059      1.19    bouyer 	if (ufs_rw16(cylbp[i], needswap) > 0) {
   1060       1.1   mycroft 		/*
   1061       1.1   mycroft 		 * found a rotational position, now find the actual
   1062       1.1   mycroft 		 * block. A panic if none is actually there.
   1063       1.1   mycroft 		 */
   1064       1.1   mycroft 		pos = cylno % fs->fs_cpc;
   1065       1.1   mycroft 		bno = (cylno - pos) * fs->fs_spc / NSPB(fs);
   1066       1.1   mycroft 		if (fs_postbl(fs, pos)[i] == -1) {
   1067      1.13  christos 			printf("pos = %d, i = %d, fs = %s\n",
   1068       1.1   mycroft 			    pos, i, fs->fs_fsmnt);
   1069       1.1   mycroft 			panic("ffs_alloccgblk: cyl groups corrupted");
   1070       1.1   mycroft 		}
   1071       1.1   mycroft 		for (i = fs_postbl(fs, pos)[i];; ) {
   1072      1.19    bouyer 			if (ffs_isblock(fs, cg_blksfree(cgp, needswap), bno + i)) {
   1073       1.1   mycroft 				bno = blkstofrags(fs, (bno + i));
   1074       1.1   mycroft 				goto gotit;
   1075       1.1   mycroft 			}
   1076       1.1   mycroft 			delta = fs_rotbl(fs)[i];
   1077       1.1   mycroft 			if (delta <= 0 ||
   1078       1.1   mycroft 			    delta + i > fragstoblks(fs, fs->fs_fpg))
   1079       1.1   mycroft 				break;
   1080       1.1   mycroft 			i += delta;
   1081       1.1   mycroft 		}
   1082      1.13  christos 		printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt);
   1083       1.1   mycroft 		panic("ffs_alloccgblk: can't find blk in cyl");
   1084       1.1   mycroft 	}
   1085       1.1   mycroft norot:
   1086       1.1   mycroft 	/*
   1087       1.1   mycroft 	 * no blocks in the requested cylinder, so take next
   1088       1.1   mycroft 	 * available one in this cylinder group.
   1089       1.1   mycroft 	 */
   1090      1.19    bouyer 	bno = ffs_mapsearch(needswap, fs, cgp, bpref, (int)fs->fs_frag);
   1091       1.1   mycroft 	if (bno < 0)
   1092       1.1   mycroft 		return (NULL);
   1093      1.19    bouyer 	cgp->cg_rotor = ufs_rw32(bno, needswap);
   1094       1.1   mycroft gotit:
   1095       1.1   mycroft 	blkno = fragstoblks(fs, bno);
   1096      1.19    bouyer 	ffs_clrblock(fs, cg_blksfree(cgp, needswap), (long)blkno);
   1097      1.19    bouyer 	ffs_clusteracct(needswap, fs, cgp, blkno, -1);
   1098      1.19    bouyer 	ufs_add32(cgp->cg_cs.cs_nbfree, -1, needswap);
   1099       1.1   mycroft 	fs->fs_cstotal.cs_nbfree--;
   1100      1.19    bouyer 	fs->fs_cs(fs, ufs_rw32(cgp->cg_cgx, needswap)).cs_nbfree--;
   1101       1.1   mycroft 	cylno = cbtocylno(fs, bno);
   1102      1.19    bouyer 	ufs_add16(cg_blks(fs, cgp, cylno, needswap)[cbtorpos(fs, bno)], -1,
   1103      1.19    bouyer 		needswap);
   1104      1.19    bouyer 	ufs_add32(cg_blktot(cgp, needswap)[cylno], -1, needswap);
   1105       1.1   mycroft 	fs->fs_fmod = 1;
   1106      1.19    bouyer 	return (ufs_rw32(cgp->cg_cgx, needswap) * fs->fs_fpg + bno);
   1107       1.1   mycroft }
   1108       1.1   mycroft 
   1109       1.1   mycroft /*
   1110       1.1   mycroft  * Determine whether a cluster can be allocated.
   1111       1.1   mycroft  *
   1112       1.1   mycroft  * We do not currently check for optimal rotational layout if there
   1113       1.1   mycroft  * are multiple choices in the same cylinder group. Instead we just
   1114       1.1   mycroft  * take the first one that we find following bpref.
   1115       1.1   mycroft  */
   1116      1.18      fvdl static ufs_daddr_t
   1117       1.1   mycroft ffs_clusteralloc(ip, cg, bpref, len)
   1118       1.1   mycroft 	struct inode *ip;
   1119       1.1   mycroft 	int cg;
   1120      1.18      fvdl 	ufs_daddr_t bpref;
   1121       1.1   mycroft 	int len;
   1122       1.1   mycroft {
   1123       1.1   mycroft 	register struct fs *fs;
   1124       1.1   mycroft 	register struct cg *cgp;
   1125       1.1   mycroft 	struct buf *bp;
   1126      1.18      fvdl 	int i, got, run, bno, bit, map;
   1127       1.1   mycroft 	u_char *mapp;
   1128       1.5   mycroft 	int32_t *lp;
   1129       1.1   mycroft 
   1130       1.1   mycroft 	fs = ip->i_fs;
   1131       1.5   mycroft 	if (fs->fs_maxcluster[cg] < len)
   1132       1.1   mycroft 		return (NULL);
   1133       1.1   mycroft 	if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize,
   1134       1.1   mycroft 	    NOCRED, &bp))
   1135       1.1   mycroft 		goto fail;
   1136       1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1137      1.19    bouyer 	if (!cg_chkmagic(cgp, UFS_IPNEEDSWAP(ip)))
   1138       1.1   mycroft 		goto fail;
   1139       1.1   mycroft 	/*
   1140       1.1   mycroft 	 * Check to see if a cluster of the needed size (or bigger) is
   1141       1.1   mycroft 	 * available in this cylinder group.
   1142       1.1   mycroft 	 */
   1143      1.19    bouyer 	lp = &cg_clustersum(cgp, UFS_IPNEEDSWAP(ip))[len];
   1144       1.1   mycroft 	for (i = len; i <= fs->fs_contigsumsize; i++)
   1145      1.19    bouyer 		if (ufs_rw32(*lp++, UFS_IPNEEDSWAP(ip)) > 0)
   1146       1.1   mycroft 			break;
   1147       1.5   mycroft 	if (i > fs->fs_contigsumsize) {
   1148       1.5   mycroft 		/*
   1149       1.5   mycroft 		 * This is the first time looking for a cluster in this
   1150       1.5   mycroft 		 * cylinder group. Update the cluster summary information
   1151       1.5   mycroft 		 * to reflect the true maximum sized cluster so that
   1152       1.5   mycroft 		 * future cluster allocation requests can avoid reading
   1153       1.5   mycroft 		 * the cylinder group map only to find no clusters.
   1154       1.5   mycroft 		 */
   1155      1.19    bouyer 		lp = &cg_clustersum(cgp, UFS_IPNEEDSWAP(ip))[len - 1];
   1156       1.5   mycroft 		for (i = len - 1; i > 0; i--)
   1157      1.19    bouyer 			if (ufs_rw32(*lp--, UFS_IPNEEDSWAP(ip)) > 0)
   1158       1.5   mycroft 				break;
   1159       1.5   mycroft 		fs->fs_maxcluster[cg] = i;
   1160       1.1   mycroft 		goto fail;
   1161       1.5   mycroft 	}
   1162       1.1   mycroft 	/*
   1163       1.1   mycroft 	 * Search the cluster map to find a big enough cluster.
   1164       1.1   mycroft 	 * We take the first one that we find, even if it is larger
   1165       1.1   mycroft 	 * than we need as we prefer to get one close to the previous
   1166       1.1   mycroft 	 * block allocation. We do not search before the current
   1167       1.1   mycroft 	 * preference point as we do not want to allocate a block
   1168       1.1   mycroft 	 * that is allocated before the previous one (as we will
   1169       1.1   mycroft 	 * then have to wait for another pass of the elevator
   1170       1.1   mycroft 	 * algorithm before it will be read). We prefer to fail and
   1171       1.1   mycroft 	 * be recalled to try an allocation in the next cylinder group.
   1172       1.1   mycroft 	 */
   1173       1.1   mycroft 	if (dtog(fs, bpref) != cg)
   1174       1.1   mycroft 		bpref = 0;
   1175       1.1   mycroft 	else
   1176       1.1   mycroft 		bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref)));
   1177      1.19    bouyer 	mapp = &cg_clustersfree(cgp, UFS_IPNEEDSWAP(ip))[bpref / NBBY];
   1178       1.1   mycroft 	map = *mapp++;
   1179       1.1   mycroft 	bit = 1 << (bpref % NBBY);
   1180      1.19    bouyer 	for (run = 0, got = bpref;
   1181      1.19    bouyer 		got < ufs_rw32(cgp->cg_nclusterblks, UFS_IPNEEDSWAP(ip)); got++) {
   1182       1.1   mycroft 		if ((map & bit) == 0) {
   1183       1.1   mycroft 			run = 0;
   1184       1.1   mycroft 		} else {
   1185       1.1   mycroft 			run++;
   1186       1.1   mycroft 			if (run == len)
   1187       1.1   mycroft 				break;
   1188       1.1   mycroft 		}
   1189      1.18      fvdl 		if ((got & (NBBY - 1)) != (NBBY - 1)) {
   1190       1.1   mycroft 			bit <<= 1;
   1191       1.1   mycroft 		} else {
   1192       1.1   mycroft 			map = *mapp++;
   1193       1.1   mycroft 			bit = 1;
   1194       1.1   mycroft 		}
   1195       1.1   mycroft 	}
   1196      1.19    bouyer 	if (got == ufs_rw32(cgp->cg_nclusterblks, UFS_IPNEEDSWAP(ip)))
   1197       1.1   mycroft 		goto fail;
   1198       1.1   mycroft 	/*
   1199       1.1   mycroft 	 * Allocate the cluster that we have found.
   1200       1.1   mycroft 	 */
   1201      1.18      fvdl 	for (i = 1; i <= len; i++)
   1202      1.19    bouyer 		if (!ffs_isblock(fs, cg_blksfree(cgp, UFS_IPNEEDSWAP(ip)),
   1203      1.19    bouyer 			got - run + i))
   1204      1.18      fvdl 			panic("ffs_clusteralloc: map mismatch");
   1205      1.18      fvdl 	bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1);
   1206      1.18      fvdl 	if (dtog(fs, bno) != cg)
   1207      1.18      fvdl 		panic("ffs_clusteralloc: allocated out of group");
   1208       1.1   mycroft 	len = blkstofrags(fs, len);
   1209       1.1   mycroft 	for (i = 0; i < len; i += fs->fs_frag)
   1210      1.19    bouyer 		if ((got = ffs_alloccgblk(ITOV(ip)->v_mount, fs, cgp, bno + i))
   1211      1.19    bouyer 			!= bno + i)
   1212       1.1   mycroft 			panic("ffs_clusteralloc: lost block");
   1213       1.8       cgd 	bdwrite(bp);
   1214       1.1   mycroft 	return (bno);
   1215       1.1   mycroft 
   1216       1.1   mycroft fail:
   1217       1.1   mycroft 	brelse(bp);
   1218       1.1   mycroft 	return (0);
   1219       1.1   mycroft }
   1220       1.1   mycroft 
   1221       1.1   mycroft /*
   1222       1.1   mycroft  * Determine whether an inode can be allocated.
   1223       1.1   mycroft  *
   1224       1.1   mycroft  * Check to see if an inode is available, and if it is,
   1225       1.1   mycroft  * allocate it using the following policy:
   1226       1.1   mycroft  *   1) allocate the requested inode.
   1227       1.1   mycroft  *   2) allocate the next available inode after the requested
   1228       1.1   mycroft  *      inode in the specified cylinder group.
   1229       1.1   mycroft  */
   1230      1.18      fvdl static ufs_daddr_t
   1231       1.1   mycroft ffs_nodealloccg(ip, cg, ipref, mode)
   1232       1.1   mycroft 	struct inode *ip;
   1233       1.1   mycroft 	int cg;
   1234      1.18      fvdl 	ufs_daddr_t ipref;
   1235       1.1   mycroft 	int mode;
   1236       1.1   mycroft {
   1237       1.1   mycroft 	register struct fs *fs;
   1238       1.1   mycroft 	register struct cg *cgp;
   1239       1.1   mycroft 	struct buf *bp;
   1240       1.1   mycroft 	int error, start, len, loc, map, i;
   1241      1.19    bouyer #ifdef FFS_EI
   1242      1.19    bouyer 	const int needswap = UFS_IPNEEDSWAP(ip);
   1243      1.19    bouyer #endif
   1244       1.1   mycroft 
   1245       1.1   mycroft 	fs = ip->i_fs;
   1246       1.1   mycroft 	if (fs->fs_cs(fs, cg).cs_nifree == 0)
   1247       1.1   mycroft 		return (NULL);
   1248       1.1   mycroft 	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
   1249       1.1   mycroft 		(int)fs->fs_cgsize, NOCRED, &bp);
   1250       1.1   mycroft 	if (error) {
   1251       1.1   mycroft 		brelse(bp);
   1252       1.1   mycroft 		return (NULL);
   1253       1.1   mycroft 	}
   1254       1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1255      1.19    bouyer 	if (!cg_chkmagic(cgp, needswap) || cgp->cg_cs.cs_nifree == 0) {
   1256       1.1   mycroft 		brelse(bp);
   1257       1.1   mycroft 		return (NULL);
   1258       1.1   mycroft 	}
   1259      1.19    bouyer 	cgp->cg_time = ufs_rw32(time.tv_sec, needswap);
   1260       1.1   mycroft 	if (ipref) {
   1261       1.1   mycroft 		ipref %= fs->fs_ipg;
   1262      1.19    bouyer 		if (isclr(cg_inosused(cgp, needswap), ipref))
   1263       1.1   mycroft 			goto gotit;
   1264       1.1   mycroft 	}
   1265      1.19    bouyer 	start = ufs_rw32(cgp->cg_irotor, needswap) / NBBY;
   1266      1.19    bouyer 	len = howmany(fs->fs_ipg - ufs_rw32(cgp->cg_irotor, needswap),
   1267      1.19    bouyer 		NBBY);
   1268      1.19    bouyer 	loc = skpc(0xff, len, &cg_inosused(cgp, needswap)[start]);
   1269       1.1   mycroft 	if (loc == 0) {
   1270       1.1   mycroft 		len = start + 1;
   1271       1.1   mycroft 		start = 0;
   1272      1.19    bouyer 		loc = skpc(0xff, len, &cg_inosused(cgp, needswap)[0]);
   1273       1.1   mycroft 		if (loc == 0) {
   1274      1.13  christos 			printf("cg = %d, irotor = %d, fs = %s\n",
   1275      1.19    bouyer 			    cg, ufs_rw32(cgp->cg_irotor, needswap),
   1276      1.19    bouyer 				fs->fs_fsmnt);
   1277       1.1   mycroft 			panic("ffs_nodealloccg: map corrupted");
   1278       1.1   mycroft 			/* NOTREACHED */
   1279       1.1   mycroft 		}
   1280       1.1   mycroft 	}
   1281       1.1   mycroft 	i = start + len - loc;
   1282      1.19    bouyer 	map = cg_inosused(cgp, needswap)[i];
   1283       1.1   mycroft 	ipref = i * NBBY;
   1284       1.1   mycroft 	for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) {
   1285       1.1   mycroft 		if ((map & i) == 0) {
   1286      1.19    bouyer 			cgp->cg_irotor = ufs_rw32(ipref, needswap);
   1287       1.1   mycroft 			goto gotit;
   1288       1.1   mycroft 		}
   1289       1.1   mycroft 	}
   1290      1.13  christos 	printf("fs = %s\n", fs->fs_fsmnt);
   1291       1.1   mycroft 	panic("ffs_nodealloccg: block not in map");
   1292       1.1   mycroft 	/* NOTREACHED */
   1293       1.1   mycroft gotit:
   1294      1.19    bouyer 	setbit(cg_inosused(cgp, needswap), ipref);
   1295      1.19    bouyer 	ufs_add32(cgp->cg_cs.cs_nifree, -1, needswap);
   1296       1.1   mycroft 	fs->fs_cstotal.cs_nifree--;
   1297      1.19    bouyer 	fs->fs_cs(fs, cg).cs_nifree --;
   1298       1.1   mycroft 	fs->fs_fmod = 1;
   1299       1.1   mycroft 	if ((mode & IFMT) == IFDIR) {
   1300      1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_ndir, 1, needswap);
   1301       1.1   mycroft 		fs->fs_cstotal.cs_ndir++;
   1302       1.1   mycroft 		fs->fs_cs(fs, cg).cs_ndir++;
   1303       1.1   mycroft 	}
   1304       1.1   mycroft 	bdwrite(bp);
   1305       1.1   mycroft 	return (cg * fs->fs_ipg + ipref);
   1306       1.1   mycroft }
   1307       1.1   mycroft 
   1308       1.1   mycroft /*
   1309       1.1   mycroft  * Free a block or fragment.
   1310       1.1   mycroft  *
   1311       1.1   mycroft  * The specified block or fragment is placed back in the
   1312       1.1   mycroft  * free map. If a fragment is deallocated, a possible
   1313       1.1   mycroft  * block reassembly is checked.
   1314       1.1   mycroft  */
   1315       1.9  christos void
   1316       1.1   mycroft ffs_blkfree(ip, bno, size)
   1317       1.1   mycroft 	register struct inode *ip;
   1318      1.18      fvdl 	ufs_daddr_t bno;
   1319       1.1   mycroft 	long size;
   1320       1.1   mycroft {
   1321       1.1   mycroft 	register struct fs *fs;
   1322       1.1   mycroft 	register struct cg *cgp;
   1323       1.1   mycroft 	struct buf *bp;
   1324      1.18      fvdl 	ufs_daddr_t blkno;
   1325       1.1   mycroft 	int i, error, cg, blk, frags, bbase;
   1326      1.19    bouyer 	const int needswap = UFS_MPNEEDSWAP(ITOV(ip)->v_mount);
   1327       1.1   mycroft 
   1328       1.1   mycroft 	fs = ip->i_fs;
   1329       1.1   mycroft 	if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) {
   1330      1.13  christos 		printf("dev = 0x%x, bsize = %d, size = %ld, fs = %s\n",
   1331       1.1   mycroft 		    ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt);
   1332       1.1   mycroft 		panic("blkfree: bad size");
   1333       1.1   mycroft 	}
   1334       1.1   mycroft 	cg = dtog(fs, bno);
   1335       1.1   mycroft 	if ((u_int)bno >= fs->fs_size) {
   1336      1.13  christos 		printf("bad block %d, ino %d\n", bno, ip->i_number);
   1337      1.15    bouyer 		ffs_fserr(fs, ip->i_ffs_uid, "bad block");
   1338       1.1   mycroft 		return;
   1339       1.1   mycroft 	}
   1340       1.1   mycroft 	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
   1341       1.1   mycroft 		(int)fs->fs_cgsize, NOCRED, &bp);
   1342       1.1   mycroft 	if (error) {
   1343       1.1   mycroft 		brelse(bp);
   1344       1.1   mycroft 		return;
   1345       1.1   mycroft 	}
   1346       1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1347      1.19    bouyer 	if (!cg_chkmagic(cgp, needswap)) {
   1348       1.1   mycroft 		brelse(bp);
   1349       1.1   mycroft 		return;
   1350       1.1   mycroft 	}
   1351      1.19    bouyer 	cgp->cg_time = ufs_rw32(time.tv_sec, needswap);
   1352       1.1   mycroft 	bno = dtogd(fs, bno);
   1353       1.1   mycroft 	if (size == fs->fs_bsize) {
   1354       1.1   mycroft 		blkno = fragstoblks(fs, bno);
   1355      1.19    bouyer 		if (ffs_isblock(fs, cg_blksfree(cgp, needswap), blkno)) {
   1356      1.13  christos 			printf("dev = 0x%x, block = %d, fs = %s\n",
   1357       1.1   mycroft 			    ip->i_dev, bno, fs->fs_fsmnt);
   1358       1.1   mycroft 			panic("blkfree: freeing free block");
   1359       1.1   mycroft 		}
   1360      1.19    bouyer 		ffs_setblock(fs, cg_blksfree(cgp, needswap), blkno);
   1361      1.19    bouyer 		ffs_clusteracct(needswap, fs, cgp, blkno, 1);
   1362      1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_nbfree, 1, needswap);
   1363       1.1   mycroft 		fs->fs_cstotal.cs_nbfree++;
   1364       1.1   mycroft 		fs->fs_cs(fs, cg).cs_nbfree++;
   1365       1.1   mycroft 		i = cbtocylno(fs, bno);
   1366      1.19    bouyer 		ufs_add16(cg_blks(fs, cgp, i, needswap)[cbtorpos(fs, bno)], 1,
   1367      1.19    bouyer 			needswap);
   1368      1.19    bouyer 		ufs_add32(cg_blktot(cgp, needswap)[i], 1, needswap);
   1369       1.1   mycroft 	} else {
   1370       1.1   mycroft 		bbase = bno - fragnum(fs, bno);
   1371       1.1   mycroft 		/*
   1372       1.1   mycroft 		 * decrement the counts associated with the old frags
   1373       1.1   mycroft 		 */
   1374      1.19    bouyer 		blk = blkmap(fs, cg_blksfree(cgp, needswap), bbase);
   1375      1.19    bouyer 		ffs_fragacct(fs, blk, cgp->cg_frsum, -1, needswap);
   1376       1.1   mycroft 		/*
   1377       1.1   mycroft 		 * deallocate the fragment
   1378       1.1   mycroft 		 */
   1379       1.1   mycroft 		frags = numfrags(fs, size);
   1380       1.1   mycroft 		for (i = 0; i < frags; i++) {
   1381      1.19    bouyer 			if (isset(cg_blksfree(cgp, needswap), bno + i)) {
   1382      1.13  christos 				printf("dev = 0x%x, block = %d, fs = %s\n",
   1383       1.1   mycroft 				    ip->i_dev, bno + i, fs->fs_fsmnt);
   1384       1.1   mycroft 				panic("blkfree: freeing free frag");
   1385       1.1   mycroft 			}
   1386      1.19    bouyer 			setbit(cg_blksfree(cgp, needswap), bno + i);
   1387       1.1   mycroft 		}
   1388      1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_nffree, i, needswap);
   1389       1.1   mycroft 		fs->fs_cstotal.cs_nffree += i;
   1390      1.19    bouyer 		fs->fs_cs(fs, cg).cs_nffree +=i;
   1391       1.1   mycroft 		/*
   1392       1.1   mycroft 		 * add back in counts associated with the new frags
   1393       1.1   mycroft 		 */
   1394      1.19    bouyer 		blk = blkmap(fs, cg_blksfree(cgp, needswap), bbase);
   1395      1.19    bouyer 		ffs_fragacct(fs, blk, cgp->cg_frsum, 1, needswap);
   1396       1.1   mycroft 		/*
   1397       1.1   mycroft 		 * if a complete block has been reassembled, account for it
   1398       1.1   mycroft 		 */
   1399       1.1   mycroft 		blkno = fragstoblks(fs, bbase);
   1400      1.19    bouyer 		if (ffs_isblock(fs, cg_blksfree(cgp, needswap), blkno)) {
   1401      1.19    bouyer 			ufs_add32(cgp->cg_cs.cs_nffree, -fs->fs_frag, needswap);
   1402       1.1   mycroft 			fs->fs_cstotal.cs_nffree -= fs->fs_frag;
   1403       1.1   mycroft 			fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag;
   1404      1.19    bouyer 			ffs_clusteracct(needswap, fs, cgp, blkno, 1);
   1405      1.19    bouyer 			ufs_add32(cgp->cg_cs.cs_nbfree, 1, needswap);
   1406       1.1   mycroft 			fs->fs_cstotal.cs_nbfree++;
   1407       1.1   mycroft 			fs->fs_cs(fs, cg).cs_nbfree++;
   1408       1.1   mycroft 			i = cbtocylno(fs, bbase);
   1409      1.19    bouyer 			ufs_add16(cg_blks(fs, cgp, i, needswap)[cbtorpos(fs, bbase)], 1,
   1410      1.19    bouyer 				needswap);
   1411      1.19    bouyer 			ufs_add32(cg_blktot(cgp, needswap)[i], 1, needswap);
   1412       1.1   mycroft 		}
   1413       1.1   mycroft 	}
   1414       1.1   mycroft 	fs->fs_fmod = 1;
   1415       1.1   mycroft 	bdwrite(bp);
   1416       1.1   mycroft }
   1417       1.1   mycroft 
   1418      1.18      fvdl #if defined(DIAGNOSTIC) || defined(DEBUG)
   1419      1.18      fvdl /*
   1420      1.18      fvdl  * Verify allocation of a block or fragment. Returns true if block or
   1421      1.18      fvdl  * fragment is allocated, false if it is free.
   1422      1.18      fvdl  */
   1423      1.18      fvdl static int
   1424      1.18      fvdl ffs_checkblk(ip, bno, size)
   1425      1.18      fvdl 	struct inode *ip;
   1426      1.18      fvdl 	ufs_daddr_t bno;
   1427      1.18      fvdl 	long size;
   1428      1.18      fvdl {
   1429      1.18      fvdl 	struct fs *fs;
   1430      1.18      fvdl 	struct cg *cgp;
   1431      1.18      fvdl 	struct buf *bp;
   1432      1.18      fvdl 	int i, error, frags, free;
   1433      1.18      fvdl 
   1434      1.18      fvdl 	fs = ip->i_fs;
   1435      1.18      fvdl 	if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) {
   1436      1.18      fvdl 		printf("bsize = %d, size = %ld, fs = %s\n",
   1437      1.18      fvdl 		    fs->fs_bsize, size, fs->fs_fsmnt);
   1438      1.18      fvdl 		panic("checkblk: bad size");
   1439      1.18      fvdl 	}
   1440      1.18      fvdl 	if ((u_int)bno >= fs->fs_size)
   1441      1.18      fvdl 		panic("checkblk: bad block %d", bno);
   1442      1.18      fvdl 	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))),
   1443      1.18      fvdl 		(int)fs->fs_cgsize, NOCRED, &bp);
   1444      1.18      fvdl 	if (error) {
   1445      1.18      fvdl 		brelse(bp);
   1446      1.18      fvdl 		return 0;
   1447      1.18      fvdl 	}
   1448      1.18      fvdl 	cgp = (struct cg *)bp->b_data;
   1449      1.19    bouyer 	if (!cg_chkmagic(cgp, UFS_IPNEEDSWAP(ip))) {
   1450      1.18      fvdl 		brelse(bp);
   1451      1.18      fvdl 		return 0;
   1452      1.18      fvdl 	}
   1453      1.18      fvdl 	bno = dtogd(fs, bno);
   1454      1.18      fvdl 	if (size == fs->fs_bsize) {
   1455      1.19    bouyer 		free = ffs_isblock(fs, cg_blksfree(cgp, UFS_IPNEEDSWAP(ip)),
   1456      1.19    bouyer 			fragstoblks(fs, bno));
   1457      1.18      fvdl 	} else {
   1458      1.18      fvdl 		frags = numfrags(fs, size);
   1459      1.18      fvdl 		for (free = 0, i = 0; i < frags; i++)
   1460      1.19    bouyer 			if (isset(cg_blksfree(cgp, UFS_IPNEEDSWAP(ip)), bno + i))
   1461      1.18      fvdl 				free++;
   1462      1.18      fvdl 		if (free != 0 && free != frags)
   1463      1.18      fvdl 			panic("checkblk: partially free fragment");
   1464      1.18      fvdl 	}
   1465      1.18      fvdl 	brelse(bp);
   1466      1.18      fvdl 	return (!free);
   1467      1.18      fvdl }
   1468      1.18      fvdl #endif /* DIAGNOSTIC */
   1469      1.18      fvdl 
   1470       1.1   mycroft /*
   1471       1.1   mycroft  * Free an inode.
   1472       1.1   mycroft  *
   1473       1.1   mycroft  * The specified inode is placed back in the free map.
   1474       1.1   mycroft  */
   1475       1.1   mycroft int
   1476       1.9  christos ffs_vfree(v)
   1477       1.9  christos 	void *v;
   1478       1.9  christos {
   1479       1.1   mycroft 	struct vop_vfree_args /* {
   1480       1.1   mycroft 		struct vnode *a_pvp;
   1481       1.1   mycroft 		ino_t a_ino;
   1482       1.1   mycroft 		int a_mode;
   1483       1.9  christos 	} */ *ap = v;
   1484       1.1   mycroft 	register struct fs *fs;
   1485       1.1   mycroft 	register struct cg *cgp;
   1486       1.1   mycroft 	register struct inode *pip;
   1487       1.1   mycroft 	ino_t ino = ap->a_ino;
   1488       1.1   mycroft 	struct buf *bp;
   1489       1.1   mycroft 	int error, cg;
   1490      1.19    bouyer #ifdef FFS_EI
   1491      1.19    bouyer 	const int needswap = UFS_MPNEEDSWAP(ap->a_pvp->v_mount);
   1492      1.19    bouyer #endif
   1493       1.1   mycroft 
   1494       1.1   mycroft 	pip = VTOI(ap->a_pvp);
   1495       1.1   mycroft 	fs = pip->i_fs;
   1496       1.1   mycroft 	if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg)
   1497       1.1   mycroft 		panic("ifree: range: dev = 0x%x, ino = %d, fs = %s\n",
   1498       1.1   mycroft 		    pip->i_dev, ino, fs->fs_fsmnt);
   1499       1.1   mycroft 	cg = ino_to_cg(fs, ino);
   1500       1.1   mycroft 	error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
   1501       1.1   mycroft 		(int)fs->fs_cgsize, NOCRED, &bp);
   1502       1.1   mycroft 	if (error) {
   1503       1.1   mycroft 		brelse(bp);
   1504       1.1   mycroft 		return (0);
   1505       1.1   mycroft 	}
   1506       1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1507      1.19    bouyer 	if (!cg_chkmagic(cgp, needswap)) {
   1508       1.1   mycroft 		brelse(bp);
   1509       1.1   mycroft 		return (0);
   1510       1.1   mycroft 	}
   1511      1.19    bouyer 	cgp->cg_time = ufs_rw32(time.tv_sec, needswap);
   1512       1.1   mycroft 	ino %= fs->fs_ipg;
   1513      1.19    bouyer 	if (isclr(cg_inosused(cgp, needswap), ino)) {
   1514      1.13  christos 		printf("dev = 0x%x, ino = %d, fs = %s\n",
   1515       1.1   mycroft 		    pip->i_dev, ino, fs->fs_fsmnt);
   1516       1.1   mycroft 		if (fs->fs_ronly == 0)
   1517       1.1   mycroft 			panic("ifree: freeing free inode");
   1518       1.1   mycroft 	}
   1519      1.19    bouyer 	clrbit(cg_inosused(cgp, needswap), ino);
   1520      1.19    bouyer 	if (ino < ufs_rw32(cgp->cg_irotor, needswap))
   1521      1.19    bouyer 		cgp->cg_irotor = ufs_rw32(ino, needswap);
   1522      1.19    bouyer 	ufs_add32(cgp->cg_cs.cs_nifree, 1, needswap);
   1523       1.1   mycroft 	fs->fs_cstotal.cs_nifree++;
   1524       1.1   mycroft 	fs->fs_cs(fs, cg).cs_nifree++;
   1525       1.1   mycroft 	if ((ap->a_mode & IFMT) == IFDIR) {
   1526      1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_ndir, -1, needswap);
   1527       1.1   mycroft 		fs->fs_cstotal.cs_ndir--;
   1528       1.1   mycroft 		fs->fs_cs(fs, cg).cs_ndir--;
   1529       1.1   mycroft 	}
   1530       1.1   mycroft 	fs->fs_fmod = 1;
   1531       1.1   mycroft 	bdwrite(bp);
   1532       1.1   mycroft 	return (0);
   1533       1.1   mycroft }
   1534       1.1   mycroft 
   1535       1.1   mycroft /*
   1536       1.1   mycroft  * Find a block of the specified size in the specified cylinder group.
   1537       1.1   mycroft  *
   1538       1.1   mycroft  * It is a panic if a request is made to find a block if none are
   1539       1.1   mycroft  * available.
   1540       1.1   mycroft  */
   1541      1.18      fvdl static ufs_daddr_t
   1542      1.19    bouyer ffs_mapsearch(needswap, fs, cgp, bpref, allocsiz)
   1543      1.19    bouyer 	int needswap;
   1544       1.1   mycroft 	register struct fs *fs;
   1545       1.1   mycroft 	register struct cg *cgp;
   1546      1.18      fvdl 	ufs_daddr_t bpref;
   1547       1.1   mycroft 	int allocsiz;
   1548       1.1   mycroft {
   1549      1.18      fvdl 	ufs_daddr_t bno;
   1550       1.1   mycroft 	int start, len, loc, i;
   1551       1.1   mycroft 	int blk, field, subfield, pos;
   1552      1.19    bouyer 	int ostart, olen;
   1553       1.1   mycroft 
   1554       1.1   mycroft 	/*
   1555       1.1   mycroft 	 * find the fragment by searching through the free block
   1556       1.1   mycroft 	 * map for an appropriate bit pattern
   1557       1.1   mycroft 	 */
   1558       1.1   mycroft 	if (bpref)
   1559       1.1   mycroft 		start = dtogd(fs, bpref) / NBBY;
   1560       1.1   mycroft 	else
   1561      1.19    bouyer 		start = ufs_rw32(cgp->cg_frotor, needswap) / NBBY;
   1562       1.1   mycroft 	len = howmany(fs->fs_fpg, NBBY) - start;
   1563      1.19    bouyer 	ostart = start;
   1564      1.19    bouyer 	olen = len;
   1565      1.19    bouyer 	loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp, needswap)[start],
   1566       1.1   mycroft 		(u_char *)fragtbl[fs->fs_frag],
   1567       1.1   mycroft 		(u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
   1568       1.1   mycroft 	if (loc == 0) {
   1569       1.1   mycroft 		len = start + 1;
   1570       1.1   mycroft 		start = 0;
   1571      1.19    bouyer 		loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp, needswap)[0],
   1572       1.1   mycroft 			(u_char *)fragtbl[fs->fs_frag],
   1573       1.1   mycroft 			(u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY))));
   1574       1.1   mycroft 		if (loc == 0) {
   1575      1.13  christos 			printf("start = %d, len = %d, fs = %s\n",
   1576      1.19    bouyer 			    ostart, olen, fs->fs_fsmnt);
   1577      1.20      ross 			printf("offset=%d %ld\n",
   1578      1.19    bouyer 				ufs_rw32(cgp->cg_freeoff, needswap),
   1579      1.20      ross 				(long)cg_blksfree(cgp, needswap) - (long)cgp);
   1580       1.1   mycroft 			panic("ffs_alloccg: map corrupted");
   1581       1.1   mycroft 			/* NOTREACHED */
   1582       1.1   mycroft 		}
   1583       1.1   mycroft 	}
   1584       1.1   mycroft 	bno = (start + len - loc) * NBBY;
   1585      1.19    bouyer 	cgp->cg_frotor = ufs_rw32(bno, needswap);
   1586       1.1   mycroft 	/*
   1587       1.1   mycroft 	 * found the byte in the map
   1588       1.1   mycroft 	 * sift through the bits to find the selected frag
   1589       1.1   mycroft 	 */
   1590       1.1   mycroft 	for (i = bno + NBBY; bno < i; bno += fs->fs_frag) {
   1591      1.19    bouyer 		blk = blkmap(fs, cg_blksfree(cgp, needswap), bno);
   1592       1.1   mycroft 		blk <<= 1;
   1593       1.1   mycroft 		field = around[allocsiz];
   1594       1.1   mycroft 		subfield = inside[allocsiz];
   1595       1.1   mycroft 		for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) {
   1596       1.1   mycroft 			if ((blk & field) == subfield)
   1597       1.1   mycroft 				return (bno + pos);
   1598       1.1   mycroft 			field <<= 1;
   1599       1.1   mycroft 			subfield <<= 1;
   1600       1.1   mycroft 		}
   1601       1.1   mycroft 	}
   1602      1.13  christos 	printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt);
   1603       1.1   mycroft 	panic("ffs_alloccg: block not in map");
   1604       1.1   mycroft 	return (-1);
   1605       1.1   mycroft }
   1606       1.1   mycroft 
   1607       1.1   mycroft /*
   1608       1.1   mycroft  * Update the cluster map because of an allocation or free.
   1609       1.1   mycroft  *
   1610       1.1   mycroft  * Cnt == 1 means free; cnt == -1 means allocating.
   1611       1.1   mycroft  */
   1612       1.9  christos void
   1613      1.19    bouyer ffs_clusteracct(needswap, fs, cgp, blkno, cnt)
   1614      1.19    bouyer 	int needswap;
   1615       1.1   mycroft 	struct fs *fs;
   1616       1.1   mycroft 	struct cg *cgp;
   1617      1.18      fvdl 	ufs_daddr_t blkno;
   1618       1.1   mycroft 	int cnt;
   1619       1.1   mycroft {
   1620       1.4       cgd 	int32_t *sump;
   1621       1.5   mycroft 	int32_t *lp;
   1622       1.1   mycroft 	u_char *freemapp, *mapp;
   1623       1.1   mycroft 	int i, start, end, forw, back, map, bit;
   1624       1.1   mycroft 
   1625       1.1   mycroft 	if (fs->fs_contigsumsize <= 0)
   1626       1.1   mycroft 		return;
   1627      1.19    bouyer 	freemapp = cg_clustersfree(cgp, needswap);
   1628      1.19    bouyer 	sump = cg_clustersum(cgp, needswap);
   1629       1.1   mycroft 	/*
   1630       1.1   mycroft 	 * Allocate or clear the actual block.
   1631       1.1   mycroft 	 */
   1632       1.1   mycroft 	if (cnt > 0)
   1633       1.1   mycroft 		setbit(freemapp, blkno);
   1634       1.1   mycroft 	else
   1635       1.1   mycroft 		clrbit(freemapp, blkno);
   1636       1.1   mycroft 	/*
   1637       1.1   mycroft 	 * Find the size of the cluster going forward.
   1638       1.1   mycroft 	 */
   1639       1.1   mycroft 	start = blkno + 1;
   1640       1.1   mycroft 	end = start + fs->fs_contigsumsize;
   1641      1.19    bouyer 	if (end >= ufs_rw32(cgp->cg_nclusterblks, needswap))
   1642      1.19    bouyer 		end = ufs_rw32(cgp->cg_nclusterblks, needswap);
   1643       1.1   mycroft 	mapp = &freemapp[start / NBBY];
   1644       1.1   mycroft 	map = *mapp++;
   1645       1.1   mycroft 	bit = 1 << (start % NBBY);
   1646       1.1   mycroft 	for (i = start; i < end; i++) {
   1647       1.1   mycroft 		if ((map & bit) == 0)
   1648       1.1   mycroft 			break;
   1649       1.1   mycroft 		if ((i & (NBBY - 1)) != (NBBY - 1)) {
   1650       1.1   mycroft 			bit <<= 1;
   1651       1.1   mycroft 		} else {
   1652       1.1   mycroft 			map = *mapp++;
   1653       1.1   mycroft 			bit = 1;
   1654       1.1   mycroft 		}
   1655       1.1   mycroft 	}
   1656       1.1   mycroft 	forw = i - start;
   1657       1.1   mycroft 	/*
   1658       1.1   mycroft 	 * Find the size of the cluster going backward.
   1659       1.1   mycroft 	 */
   1660       1.1   mycroft 	start = blkno - 1;
   1661       1.1   mycroft 	end = start - fs->fs_contigsumsize;
   1662       1.1   mycroft 	if (end < 0)
   1663       1.1   mycroft 		end = -1;
   1664       1.1   mycroft 	mapp = &freemapp[start / NBBY];
   1665       1.1   mycroft 	map = *mapp--;
   1666       1.1   mycroft 	bit = 1 << (start % NBBY);
   1667       1.1   mycroft 	for (i = start; i > end; i--) {
   1668       1.1   mycroft 		if ((map & bit) == 0)
   1669       1.1   mycroft 			break;
   1670       1.1   mycroft 		if ((i & (NBBY - 1)) != 0) {
   1671       1.1   mycroft 			bit >>= 1;
   1672       1.1   mycroft 		} else {
   1673       1.1   mycroft 			map = *mapp--;
   1674       1.1   mycroft 			bit = 1 << (NBBY - 1);
   1675       1.1   mycroft 		}
   1676       1.1   mycroft 	}
   1677       1.1   mycroft 	back = start - i;
   1678       1.1   mycroft 	/*
   1679       1.1   mycroft 	 * Account for old cluster and the possibly new forward and
   1680       1.1   mycroft 	 * back clusters.
   1681       1.1   mycroft 	 */
   1682       1.1   mycroft 	i = back + forw + 1;
   1683       1.1   mycroft 	if (i > fs->fs_contigsumsize)
   1684       1.1   mycroft 		i = fs->fs_contigsumsize;
   1685      1.19    bouyer 	ufs_add32(sump[i], cnt, needswap);
   1686       1.1   mycroft 	if (back > 0)
   1687      1.19    bouyer 		ufs_add32(sump[back], -cnt, needswap);
   1688       1.1   mycroft 	if (forw > 0)
   1689      1.19    bouyer 		ufs_add32(sump[forw], -cnt, needswap);
   1690      1.19    bouyer 
   1691       1.5   mycroft 	/*
   1692       1.5   mycroft 	 * Update cluster summary information.
   1693       1.5   mycroft 	 */
   1694       1.5   mycroft 	lp = &sump[fs->fs_contigsumsize];
   1695       1.5   mycroft 	for (i = fs->fs_contigsumsize; i > 0; i--)
   1696      1.19    bouyer 		if (ufs_rw32(*lp--, needswap) > 0)
   1697       1.5   mycroft 			break;
   1698      1.19    bouyer 	fs->fs_maxcluster[ufs_rw32(cgp->cg_cgx, needswap)] = i;
   1699       1.1   mycroft }
   1700       1.1   mycroft 
   1701       1.1   mycroft /*
   1702       1.1   mycroft  * Fserr prints the name of a file system with an error diagnostic.
   1703       1.1   mycroft  *
   1704       1.1   mycroft  * The form of the error message is:
   1705       1.1   mycroft  *	fs: error message
   1706       1.1   mycroft  */
   1707       1.1   mycroft static void
   1708       1.1   mycroft ffs_fserr(fs, uid, cp)
   1709       1.1   mycroft 	struct fs *fs;
   1710       1.1   mycroft 	u_int uid;
   1711       1.1   mycroft 	char *cp;
   1712       1.1   mycroft {
   1713       1.1   mycroft 
   1714       1.1   mycroft 	log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->fs_fsmnt, cp);
   1715       1.1   mycroft }
   1716