Home | History | Annotate | Line # | Download | only in ffs
ffs_alloc.c revision 1.106.10.2
      1  1.106.10.2      yamt /*	$NetBSD: ffs_alloc.c,v 1.106.10.2 2008/06/04 02:05:53 yamt Exp $	*/
      2         1.2       cgd 
      3         1.1   mycroft /*
      4        1.60      fvdl  * Copyright (c) 2002 Networks Associates Technology, Inc.
      5        1.60      fvdl  * All rights reserved.
      6        1.60      fvdl  *
      7        1.60      fvdl  * This software was developed for the FreeBSD Project by Marshall
      8        1.60      fvdl  * Kirk McKusick and Network Associates Laboratories, the Security
      9        1.60      fvdl  * Research Division of Network Associates, Inc. under DARPA/SPAWAR
     10        1.60      fvdl  * contract N66001-01-C-8035 ("CBOSS"), as part of the DARPA CHATS
     11        1.60      fvdl  * research program
     12        1.60      fvdl  *
     13         1.1   mycroft  * Copyright (c) 1982, 1986, 1989, 1993
     14         1.1   mycroft  *	The Regents of the University of California.  All rights reserved.
     15         1.1   mycroft  *
     16         1.1   mycroft  * Redistribution and use in source and binary forms, with or without
     17         1.1   mycroft  * modification, are permitted provided that the following conditions
     18         1.1   mycroft  * are met:
     19         1.1   mycroft  * 1. Redistributions of source code must retain the above copyright
     20         1.1   mycroft  *    notice, this list of conditions and the following disclaimer.
     21         1.1   mycroft  * 2. Redistributions in binary form must reproduce the above copyright
     22         1.1   mycroft  *    notice, this list of conditions and the following disclaimer in the
     23         1.1   mycroft  *    documentation and/or other materials provided with the distribution.
     24        1.69       agc  * 3. Neither the name of the University nor the names of its contributors
     25         1.1   mycroft  *    may be used to endorse or promote products derived from this software
     26         1.1   mycroft  *    without specific prior written permission.
     27         1.1   mycroft  *
     28         1.1   mycroft  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     29         1.1   mycroft  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     30         1.1   mycroft  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     31         1.1   mycroft  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     32         1.1   mycroft  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     33         1.1   mycroft  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     34         1.1   mycroft  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     35         1.1   mycroft  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     36         1.1   mycroft  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     37         1.1   mycroft  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     38         1.1   mycroft  * SUCH DAMAGE.
     39         1.1   mycroft  *
     40        1.18      fvdl  *	@(#)ffs_alloc.c	8.19 (Berkeley) 7/13/95
     41         1.1   mycroft  */
     42        1.53     lukem 
     43        1.53     lukem #include <sys/cdefs.h>
     44  1.106.10.2      yamt __KERNEL_RCSID(0, "$NetBSD: ffs_alloc.c,v 1.106.10.2 2008/06/04 02:05:53 yamt Exp $");
     45        1.17       mrg 
     46        1.43       mrg #if defined(_KERNEL_OPT)
     47        1.27   thorpej #include "opt_ffs.h"
     48        1.21    scottr #include "opt_quota.h"
     49        1.22    scottr #endif
     50         1.1   mycroft 
     51         1.1   mycroft #include <sys/param.h>
     52         1.1   mycroft #include <sys/systm.h>
     53         1.1   mycroft #include <sys/buf.h>
     54         1.1   mycroft #include <sys/proc.h>
     55         1.1   mycroft #include <sys/vnode.h>
     56         1.1   mycroft #include <sys/mount.h>
     57         1.1   mycroft #include <sys/kernel.h>
     58         1.1   mycroft #include <sys/syslog.h>
     59        1.91      elad #include <sys/kauth.h>
     60  1.106.10.1      yamt #include <sys/fstrans.h>
     61        1.29       mrg 
     62        1.76   hannken #include <miscfs/specfs/specdev.h>
     63         1.1   mycroft #include <ufs/ufs/quota.h>
     64        1.19    bouyer #include <ufs/ufs/ufsmount.h>
     65         1.1   mycroft #include <ufs/ufs/inode.h>
     66         1.9  christos #include <ufs/ufs/ufs_extern.h>
     67        1.19    bouyer #include <ufs/ufs/ufs_bswap.h>
     68         1.1   mycroft 
     69         1.1   mycroft #include <ufs/ffs/fs.h>
     70         1.1   mycroft #include <ufs/ffs/ffs_extern.h>
     71         1.1   mycroft 
     72        1.85   thorpej static daddr_t ffs_alloccg(struct inode *, int, daddr_t, int);
     73        1.85   thorpej static daddr_t ffs_alloccgblk(struct inode *, struct buf *, daddr_t);
     74        1.55      matt #ifdef XXXUBC
     75        1.85   thorpej static daddr_t ffs_clusteralloc(struct inode *, int, daddr_t, int);
     76        1.55      matt #endif
     77        1.85   thorpej static ino_t ffs_dirpref(struct inode *);
     78        1.85   thorpej static daddr_t ffs_fragextend(struct inode *, int, daddr_t, int, int);
     79        1.85   thorpej static void ffs_fserr(struct fs *, u_int, const char *);
     80        1.85   thorpej static daddr_t ffs_hashalloc(struct inode *, int, daddr_t, int,
     81        1.85   thorpej     daddr_t (*)(struct inode *, int, daddr_t, int));
     82        1.85   thorpej static daddr_t ffs_nodealloccg(struct inode *, int, daddr_t, int);
     83        1.85   thorpej static int32_t ffs_mapsearch(struct fs *, struct cg *,
     84        1.85   thorpej 				      daddr_t, int);
     85        1.18      fvdl #if defined(DIAGNOSTIC) || defined(DEBUG)
     86        1.55      matt #ifdef XXXUBC
     87        1.85   thorpej static int ffs_checkblk(struct inode *, daddr_t, long size);
     88        1.18      fvdl #endif
     89        1.55      matt #endif
     90        1.23  drochner 
     91        1.34  jdolecek /* if 1, changes in optimalization strategy are logged */
     92        1.34  jdolecek int ffs_log_changeopt = 0;
     93        1.34  jdolecek 
     94        1.23  drochner /* in ffs_tables.c */
     95        1.40  jdolecek extern const int inside[], around[];
     96        1.40  jdolecek extern const u_char * const fragtbl[];
     97         1.1   mycroft 
     98         1.1   mycroft /*
     99         1.1   mycroft  * Allocate a block in the file system.
    100        1.81     perry  *
    101         1.1   mycroft  * The size of the requested block is given, which must be some
    102         1.1   mycroft  * multiple of fs_fsize and <= fs_bsize.
    103         1.1   mycroft  * A preference may be optionally specified. If a preference is given
    104         1.1   mycroft  * the following hierarchy is used to allocate a block:
    105         1.1   mycroft  *   1) allocate the requested block.
    106         1.1   mycroft  *   2) allocate a rotationally optimal block in the same cylinder.
    107         1.1   mycroft  *   3) allocate a block in the same cylinder group.
    108         1.1   mycroft  *   4) quadradically rehash into other cylinder groups, until an
    109         1.1   mycroft  *      available block is located.
    110        1.47       wiz  * If no block preference is given the following hierarchy is used
    111         1.1   mycroft  * to allocate a block:
    112         1.1   mycroft  *   1) allocate a block in the cylinder group that contains the
    113         1.1   mycroft  *      inode for the file.
    114         1.1   mycroft  *   2) quadradically rehash into other cylinder groups, until an
    115         1.1   mycroft  *      available block is located.
    116       1.106     pooka  *
    117       1.106     pooka  * => called with um_lock held
    118       1.106     pooka  * => releases um_lock before returning
    119         1.1   mycroft  */
    120         1.9  christos int
    121        1.96  christos ffs_alloc(struct inode *ip, daddr_t lbn, daddr_t bpref, int size,
    122        1.91      elad     kauth_cred_t cred, daddr_t *bnp)
    123         1.1   mycroft {
    124       1.101        ad 	struct ufsmount *ump;
    125        1.62      fvdl 	struct fs *fs;
    126        1.58      fvdl 	daddr_t bno;
    127         1.9  christos 	int cg;
    128         1.9  christos #ifdef QUOTA
    129         1.9  christos 	int error;
    130         1.9  christos #endif
    131        1.81     perry 
    132        1.62      fvdl 	fs = ip->i_fs;
    133       1.101        ad 	ump = ip->i_ump;
    134       1.101        ad 
    135       1.101        ad 	KASSERT(mutex_owned(&ump->um_lock));
    136        1.62      fvdl 
    137        1.37       chs #ifdef UVM_PAGE_TRKOWN
    138        1.51       chs 	if (ITOV(ip)->v_type == VREG &&
    139        1.51       chs 	    lblktosize(fs, (voff_t)lbn) < round_page(ITOV(ip)->v_size)) {
    140        1.37       chs 		struct vm_page *pg;
    141        1.51       chs 		struct uvm_object *uobj = &ITOV(ip)->v_uobj;
    142        1.49     lukem 		voff_t off = trunc_page(lblktosize(fs, lbn));
    143        1.49     lukem 		voff_t endoff = round_page(lblktosize(fs, lbn) + size);
    144        1.37       chs 
    145       1.105        ad 		mutex_enter(&uobj->vmobjlock);
    146        1.37       chs 		while (off < endoff) {
    147        1.37       chs 			pg = uvm_pagelookup(uobj, off);
    148        1.37       chs 			KASSERT(pg != NULL);
    149        1.37       chs 			KASSERT(pg->owner == curproc->p_pid);
    150        1.37       chs 			off += PAGE_SIZE;
    151        1.37       chs 		}
    152       1.105        ad 		mutex_exit(&uobj->vmobjlock);
    153        1.37       chs 	}
    154        1.37       chs #endif
    155        1.37       chs 
    156         1.1   mycroft 	*bnp = 0;
    157         1.1   mycroft #ifdef DIAGNOSTIC
    158         1.1   mycroft 	if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) {
    159        1.13  christos 		printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n",
    160         1.1   mycroft 		    ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt);
    161         1.1   mycroft 		panic("ffs_alloc: bad size");
    162         1.1   mycroft 	}
    163         1.1   mycroft 	if (cred == NOCRED)
    164        1.56    provos 		panic("ffs_alloc: missing credential");
    165         1.1   mycroft #endif /* DIAGNOSTIC */
    166         1.1   mycroft 	if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0)
    167         1.1   mycroft 		goto nospace;
    168        1.99     pooka 	if (freespace(fs, fs->fs_minfree) <= 0 &&
    169        1.99     pooka 	    kauth_authorize_generic(cred, KAUTH_GENERIC_ISSUSER, NULL) != 0)
    170         1.1   mycroft 		goto nospace;
    171         1.1   mycroft #ifdef QUOTA
    172       1.101        ad 	mutex_exit(&ump->um_lock);
    173        1.60      fvdl 	if ((error = chkdq(ip, btodb(size), cred, 0)) != 0)
    174         1.1   mycroft 		return (error);
    175       1.101        ad 	mutex_enter(&ump->um_lock);
    176         1.1   mycroft #endif
    177         1.1   mycroft 	if (bpref >= fs->fs_size)
    178         1.1   mycroft 		bpref = 0;
    179         1.1   mycroft 	if (bpref == 0)
    180         1.1   mycroft 		cg = ino_to_cg(fs, ip->i_number);
    181         1.1   mycroft 	else
    182         1.1   mycroft 		cg = dtog(fs, bpref);
    183        1.84       dbj 	bno = ffs_hashalloc(ip, cg, bpref, size, ffs_alloccg);
    184         1.1   mycroft 	if (bno > 0) {
    185        1.65  kristerw 		DIP_ADD(ip, blocks, btodb(size));
    186         1.1   mycroft 		ip->i_flag |= IN_CHANGE | IN_UPDATE;
    187         1.1   mycroft 		*bnp = bno;
    188         1.1   mycroft 		return (0);
    189         1.1   mycroft 	}
    190         1.1   mycroft #ifdef QUOTA
    191         1.1   mycroft 	/*
    192         1.1   mycroft 	 * Restore user's disk quota because allocation failed.
    193         1.1   mycroft 	 */
    194        1.60      fvdl 	(void) chkdq(ip, -btodb(size), cred, FORCE);
    195         1.1   mycroft #endif
    196         1.1   mycroft nospace:
    197       1.101        ad 	mutex_exit(&ump->um_lock);
    198        1.91      elad 	ffs_fserr(fs, kauth_cred_geteuid(cred), "file system full");
    199         1.1   mycroft 	uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
    200         1.1   mycroft 	return (ENOSPC);
    201         1.1   mycroft }
    202         1.1   mycroft 
    203         1.1   mycroft /*
    204         1.1   mycroft  * Reallocate a fragment to a bigger size
    205         1.1   mycroft  *
    206         1.1   mycroft  * The number and size of the old block is given, and a preference
    207         1.1   mycroft  * and new size is also specified. The allocator attempts to extend
    208         1.1   mycroft  * the original block. Failing that, the regular block allocator is
    209         1.1   mycroft  * invoked to get an appropriate block.
    210       1.106     pooka  *
    211       1.106     pooka  * => called with um_lock held
    212       1.106     pooka  * => return with um_lock released
    213         1.1   mycroft  */
    214         1.9  christos int
    215        1.85   thorpej ffs_realloccg(struct inode *ip, daddr_t lbprev, daddr_t bpref, int osize,
    216        1.91      elad     int nsize, kauth_cred_t cred, struct buf **bpp, daddr_t *blknop)
    217         1.1   mycroft {
    218       1.101        ad 	struct ufsmount *ump;
    219        1.62      fvdl 	struct fs *fs;
    220         1.1   mycroft 	struct buf *bp;
    221         1.1   mycroft 	int cg, request, error;
    222        1.58      fvdl 	daddr_t bprev, bno;
    223        1.25   thorpej 
    224        1.62      fvdl 	fs = ip->i_fs;
    225       1.101        ad 	ump = ip->i_ump;
    226       1.101        ad 
    227       1.101        ad 	KASSERT(mutex_owned(&ump->um_lock));
    228       1.101        ad 
    229        1.37       chs #ifdef UVM_PAGE_TRKOWN
    230        1.37       chs 	if (ITOV(ip)->v_type == VREG) {
    231        1.37       chs 		struct vm_page *pg;
    232        1.51       chs 		struct uvm_object *uobj = &ITOV(ip)->v_uobj;
    233        1.49     lukem 		voff_t off = trunc_page(lblktosize(fs, lbprev));
    234        1.49     lukem 		voff_t endoff = round_page(lblktosize(fs, lbprev) + osize);
    235        1.37       chs 
    236       1.105        ad 		mutex_enter(&uobj->vmobjlock);
    237        1.37       chs 		while (off < endoff) {
    238        1.37       chs 			pg = uvm_pagelookup(uobj, off);
    239        1.37       chs 			KASSERT(pg != NULL);
    240        1.37       chs 			KASSERT(pg->owner == curproc->p_pid);
    241        1.37       chs 			KASSERT((pg->flags & PG_CLEAN) == 0);
    242        1.37       chs 			off += PAGE_SIZE;
    243        1.37       chs 		}
    244       1.105        ad 		mutex_exit(&uobj->vmobjlock);
    245        1.37       chs 	}
    246        1.37       chs #endif
    247        1.37       chs 
    248         1.1   mycroft #ifdef DIAGNOSTIC
    249         1.1   mycroft 	if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 ||
    250         1.1   mycroft 	    (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) {
    251        1.13  christos 		printf(
    252         1.1   mycroft 		    "dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n",
    253         1.1   mycroft 		    ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt);
    254         1.1   mycroft 		panic("ffs_realloccg: bad size");
    255         1.1   mycroft 	}
    256         1.1   mycroft 	if (cred == NOCRED)
    257        1.56    provos 		panic("ffs_realloccg: missing credential");
    258         1.1   mycroft #endif /* DIAGNOSTIC */
    259        1.99     pooka 	if (freespace(fs, fs->fs_minfree) <= 0 &&
    260       1.101        ad 	    kauth_authorize_generic(cred, KAUTH_GENERIC_ISSUSER, NULL) != 0) {
    261       1.101        ad 		mutex_exit(&ump->um_lock);
    262         1.1   mycroft 		goto nospace;
    263       1.101        ad 	}
    264        1.60      fvdl 	if (fs->fs_magic == FS_UFS2_MAGIC)
    265        1.60      fvdl 		bprev = ufs_rw64(ip->i_ffs2_db[lbprev], UFS_FSNEEDSWAP(fs));
    266        1.60      fvdl 	else
    267        1.60      fvdl 		bprev = ufs_rw32(ip->i_ffs1_db[lbprev], UFS_FSNEEDSWAP(fs));
    268        1.60      fvdl 
    269        1.60      fvdl 	if (bprev == 0) {
    270        1.59   tsutsui 		printf("dev = 0x%x, bsize = %d, bprev = %" PRId64 ", fs = %s\n",
    271        1.59   tsutsui 		    ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt);
    272         1.1   mycroft 		panic("ffs_realloccg: bad bprev");
    273         1.1   mycroft 	}
    274       1.101        ad 	mutex_exit(&ump->um_lock);
    275       1.101        ad 
    276         1.1   mycroft 	/*
    277         1.1   mycroft 	 * Allocate the extra space in the buffer.
    278         1.1   mycroft 	 */
    279        1.37       chs 	if (bpp != NULL &&
    280  1.106.10.1      yamt 	    (error = bread(ITOV(ip), lbprev, osize, NOCRED, 0, &bp)) != 0) {
    281       1.101        ad 		brelse(bp, 0);
    282         1.1   mycroft 		return (error);
    283         1.1   mycroft 	}
    284         1.1   mycroft #ifdef QUOTA
    285        1.60      fvdl 	if ((error = chkdq(ip, btodb(nsize - osize), cred, 0)) != 0) {
    286        1.44       chs 		if (bpp != NULL) {
    287       1.101        ad 			brelse(bp, 0);
    288        1.44       chs 		}
    289         1.1   mycroft 		return (error);
    290         1.1   mycroft 	}
    291         1.1   mycroft #endif
    292         1.1   mycroft 	/*
    293         1.1   mycroft 	 * Check for extension in the existing location.
    294         1.1   mycroft 	 */
    295         1.1   mycroft 	cg = dtog(fs, bprev);
    296       1.101        ad 	mutex_enter(&ump->um_lock);
    297        1.60      fvdl 	if ((bno = ffs_fragextend(ip, cg, bprev, osize, nsize)) != 0) {
    298        1.65  kristerw 		DIP_ADD(ip, blocks, btodb(nsize - osize));
    299         1.1   mycroft 		ip->i_flag |= IN_CHANGE | IN_UPDATE;
    300        1.37       chs 
    301        1.37       chs 		if (bpp != NULL) {
    302        1.37       chs 			if (bp->b_blkno != fsbtodb(fs, bno))
    303        1.37       chs 				panic("bad blockno");
    304        1.72        pk 			allocbuf(bp, nsize, 1);
    305        1.98  christos 			memset((char *)bp->b_data + osize, 0, nsize - osize);
    306       1.105        ad 			mutex_enter(bp->b_objlock);
    307       1.105        ad 			bp->b_oflags |= BO_DONE;
    308       1.105        ad 			mutex_exit(bp->b_objlock);
    309        1.37       chs 			*bpp = bp;
    310        1.37       chs 		}
    311        1.37       chs 		if (blknop != NULL) {
    312        1.37       chs 			*blknop = bno;
    313        1.37       chs 		}
    314         1.1   mycroft 		return (0);
    315         1.1   mycroft 	}
    316         1.1   mycroft 	/*
    317         1.1   mycroft 	 * Allocate a new disk location.
    318         1.1   mycroft 	 */
    319         1.1   mycroft 	if (bpref >= fs->fs_size)
    320         1.1   mycroft 		bpref = 0;
    321         1.1   mycroft 	switch ((int)fs->fs_optim) {
    322         1.1   mycroft 	case FS_OPTSPACE:
    323         1.1   mycroft 		/*
    324        1.81     perry 		 * Allocate an exact sized fragment. Although this makes
    325        1.81     perry 		 * best use of space, we will waste time relocating it if
    326         1.1   mycroft 		 * the file continues to grow. If the fragmentation is
    327         1.1   mycroft 		 * less than half of the minimum free reserve, we choose
    328         1.1   mycroft 		 * to begin optimizing for time.
    329         1.1   mycroft 		 */
    330         1.1   mycroft 		request = nsize;
    331         1.1   mycroft 		if (fs->fs_minfree < 5 ||
    332         1.1   mycroft 		    fs->fs_cstotal.cs_nffree >
    333         1.1   mycroft 		    fs->fs_dsize * fs->fs_minfree / (2 * 100))
    334         1.1   mycroft 			break;
    335        1.34  jdolecek 
    336        1.34  jdolecek 		if (ffs_log_changeopt) {
    337        1.34  jdolecek 			log(LOG_NOTICE,
    338        1.34  jdolecek 				"%s: optimization changed from SPACE to TIME\n",
    339        1.34  jdolecek 				fs->fs_fsmnt);
    340        1.34  jdolecek 		}
    341        1.34  jdolecek 
    342         1.1   mycroft 		fs->fs_optim = FS_OPTTIME;
    343         1.1   mycroft 		break;
    344         1.1   mycroft 	case FS_OPTTIME:
    345         1.1   mycroft 		/*
    346         1.1   mycroft 		 * At this point we have discovered a file that is trying to
    347         1.1   mycroft 		 * grow a small fragment to a larger fragment. To save time,
    348         1.1   mycroft 		 * we allocate a full sized block, then free the unused portion.
    349         1.1   mycroft 		 * If the file continues to grow, the `ffs_fragextend' call
    350         1.1   mycroft 		 * above will be able to grow it in place without further
    351         1.1   mycroft 		 * copying. If aberrant programs cause disk fragmentation to
    352         1.1   mycroft 		 * grow within 2% of the free reserve, we choose to begin
    353         1.1   mycroft 		 * optimizing for space.
    354         1.1   mycroft 		 */
    355         1.1   mycroft 		request = fs->fs_bsize;
    356         1.1   mycroft 		if (fs->fs_cstotal.cs_nffree <
    357         1.1   mycroft 		    fs->fs_dsize * (fs->fs_minfree - 2) / 100)
    358         1.1   mycroft 			break;
    359        1.34  jdolecek 
    360        1.34  jdolecek 		if (ffs_log_changeopt) {
    361        1.34  jdolecek 			log(LOG_NOTICE,
    362        1.34  jdolecek 				"%s: optimization changed from TIME to SPACE\n",
    363        1.34  jdolecek 				fs->fs_fsmnt);
    364        1.34  jdolecek 		}
    365        1.34  jdolecek 
    366         1.1   mycroft 		fs->fs_optim = FS_OPTSPACE;
    367         1.1   mycroft 		break;
    368         1.1   mycroft 	default:
    369        1.13  christos 		printf("dev = 0x%x, optim = %d, fs = %s\n",
    370         1.1   mycroft 		    ip->i_dev, fs->fs_optim, fs->fs_fsmnt);
    371         1.1   mycroft 		panic("ffs_realloccg: bad optim");
    372         1.1   mycroft 		/* NOTREACHED */
    373         1.1   mycroft 	}
    374        1.58      fvdl 	bno = ffs_hashalloc(ip, cg, bpref, request, ffs_alloccg);
    375         1.1   mycroft 	if (bno > 0) {
    376        1.30      fvdl 		if (!DOINGSOFTDEP(ITOV(ip)))
    377        1.76   hannken 			ffs_blkfree(fs, ip->i_devvp, bprev, (long)osize,
    378        1.76   hannken 			    ip->i_number);
    379         1.1   mycroft 		if (nsize < request)
    380        1.76   hannken 			ffs_blkfree(fs, ip->i_devvp, bno + numfrags(fs, nsize),
    381        1.76   hannken 			    (long)(request - nsize), ip->i_number);
    382        1.65  kristerw 		DIP_ADD(ip, blocks, btodb(nsize - osize));
    383         1.1   mycroft 		ip->i_flag |= IN_CHANGE | IN_UPDATE;
    384        1.37       chs 		if (bpp != NULL) {
    385        1.37       chs 			bp->b_blkno = fsbtodb(fs, bno);
    386        1.72        pk 			allocbuf(bp, nsize, 1);
    387        1.98  christos 			memset((char *)bp->b_data + osize, 0, (u_int)nsize - osize);
    388       1.105        ad 			mutex_enter(bp->b_objlock);
    389       1.105        ad 			bp->b_oflags |= BO_DONE;
    390       1.105        ad 			mutex_exit(bp->b_objlock);
    391        1.37       chs 			*bpp = bp;
    392        1.37       chs 		}
    393        1.37       chs 		if (blknop != NULL) {
    394        1.37       chs 			*blknop = bno;
    395        1.37       chs 		}
    396         1.1   mycroft 		return (0);
    397         1.1   mycroft 	}
    398       1.101        ad 	mutex_exit(&ump->um_lock);
    399       1.101        ad 
    400         1.1   mycroft #ifdef QUOTA
    401         1.1   mycroft 	/*
    402         1.1   mycroft 	 * Restore user's disk quota because allocation failed.
    403         1.1   mycroft 	 */
    404        1.60      fvdl 	(void) chkdq(ip, -btodb(nsize - osize), cred, FORCE);
    405         1.1   mycroft #endif
    406        1.37       chs 	if (bpp != NULL) {
    407       1.101        ad 		brelse(bp, 0);
    408        1.37       chs 	}
    409        1.37       chs 
    410         1.1   mycroft nospace:
    411         1.1   mycroft 	/*
    412         1.1   mycroft 	 * no space available
    413         1.1   mycroft 	 */
    414        1.91      elad 	ffs_fserr(fs, kauth_cred_geteuid(cred), "file system full");
    415         1.1   mycroft 	uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt);
    416         1.1   mycroft 	return (ENOSPC);
    417         1.1   mycroft }
    418         1.1   mycroft 
    419        1.88      yamt #if 0
    420         1.1   mycroft /*
    421         1.1   mycroft  * Reallocate a sequence of blocks into a contiguous sequence of blocks.
    422         1.1   mycroft  *
    423         1.1   mycroft  * The vnode and an array of buffer pointers for a range of sequential
    424         1.1   mycroft  * logical blocks to be made contiguous is given. The allocator attempts
    425        1.60      fvdl  * to find a range of sequential blocks starting as close as possible
    426        1.60      fvdl  * from the end of the allocation for the logical block immediately
    427        1.60      fvdl  * preceding the current range. If successful, the physical block numbers
    428        1.60      fvdl  * in the buffer pointers and in the inode are changed to reflect the new
    429        1.60      fvdl  * allocation. If unsuccessful, the allocation is left unchanged. The
    430        1.60      fvdl  * success in doing the reallocation is returned. Note that the error
    431        1.60      fvdl  * return is not reflected back to the user. Rather the previous block
    432        1.60      fvdl  * allocation will be used.
    433        1.60      fvdl 
    434         1.1   mycroft  */
    435        1.55      matt #ifdef XXXUBC
    436         1.3   mycroft #ifdef DEBUG
    437         1.1   mycroft #include <sys/sysctl.h>
    438         1.5   mycroft int prtrealloc = 0;
    439         1.5   mycroft struct ctldebug debug15 = { "prtrealloc", &prtrealloc };
    440         1.1   mycroft #endif
    441        1.55      matt #endif
    442         1.1   mycroft 
    443        1.60      fvdl /*
    444        1.60      fvdl  * NOTE: when re-enabling this, it must be updated for UFS2.
    445        1.60      fvdl  */
    446        1.60      fvdl 
    447        1.18      fvdl int doasyncfree = 1;
    448        1.18      fvdl 
    449         1.1   mycroft int
    450        1.85   thorpej ffs_reallocblks(void *v)
    451         1.9  christos {
    452        1.55      matt #ifdef XXXUBC
    453         1.1   mycroft 	struct vop_reallocblks_args /* {
    454         1.1   mycroft 		struct vnode *a_vp;
    455         1.1   mycroft 		struct cluster_save *a_buflist;
    456         1.9  christos 	} */ *ap = v;
    457         1.1   mycroft 	struct fs *fs;
    458         1.1   mycroft 	struct inode *ip;
    459         1.1   mycroft 	struct vnode *vp;
    460         1.1   mycroft 	struct buf *sbp, *ebp;
    461        1.58      fvdl 	int32_t *bap, *ebap = NULL, *sbap;	/* XXX ondisk32 */
    462         1.1   mycroft 	struct cluster_save *buflist;
    463        1.58      fvdl 	daddr_t start_lbn, end_lbn, soff, newblk, blkno;
    464         1.1   mycroft 	struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp;
    465         1.1   mycroft 	int i, len, start_lvl, end_lvl, pref, ssize;
    466       1.101        ad 	struct ufsmount *ump;
    467        1.55      matt #endif /* XXXUBC */
    468         1.1   mycroft 
    469        1.37       chs 	/* XXXUBC don't reallocblks for now */
    470        1.37       chs 	return ENOSPC;
    471        1.37       chs 
    472        1.55      matt #ifdef XXXUBC
    473         1.1   mycroft 	vp = ap->a_vp;
    474         1.1   mycroft 	ip = VTOI(vp);
    475         1.1   mycroft 	fs = ip->i_fs;
    476       1.101        ad 	ump = ip->i_ump;
    477         1.1   mycroft 	if (fs->fs_contigsumsize <= 0)
    478         1.1   mycroft 		return (ENOSPC);
    479         1.1   mycroft 	buflist = ap->a_buflist;
    480         1.1   mycroft 	len = buflist->bs_nchildren;
    481         1.1   mycroft 	start_lbn = buflist->bs_children[0]->b_lblkno;
    482         1.1   mycroft 	end_lbn = start_lbn + len - 1;
    483         1.1   mycroft #ifdef DIAGNOSTIC
    484        1.18      fvdl 	for (i = 0; i < len; i++)
    485        1.18      fvdl 		if (!ffs_checkblk(ip,
    486        1.18      fvdl 		   dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
    487        1.18      fvdl 			panic("ffs_reallocblks: unallocated block 1");
    488         1.1   mycroft 	for (i = 1; i < len; i++)
    489         1.1   mycroft 		if (buflist->bs_children[i]->b_lblkno != start_lbn + i)
    490        1.18      fvdl 			panic("ffs_reallocblks: non-logical cluster");
    491        1.18      fvdl 	blkno = buflist->bs_children[0]->b_blkno;
    492        1.18      fvdl 	ssize = fsbtodb(fs, fs->fs_frag);
    493        1.18      fvdl 	for (i = 1; i < len - 1; i++)
    494        1.18      fvdl 		if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize))
    495        1.18      fvdl 			panic("ffs_reallocblks: non-physical cluster %d", i);
    496         1.1   mycroft #endif
    497         1.1   mycroft 	/*
    498         1.1   mycroft 	 * If the latest allocation is in a new cylinder group, assume that
    499         1.1   mycroft 	 * the filesystem has decided to move and do not force it back to
    500         1.1   mycroft 	 * the previous cylinder group.
    501         1.1   mycroft 	 */
    502         1.1   mycroft 	if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) !=
    503         1.1   mycroft 	    dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno)))
    504         1.1   mycroft 		return (ENOSPC);
    505         1.1   mycroft 	if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) ||
    506         1.1   mycroft 	    ufs_getlbns(vp, end_lbn, end_ap, &end_lvl))
    507         1.1   mycroft 		return (ENOSPC);
    508         1.1   mycroft 	/*
    509         1.1   mycroft 	 * Get the starting offset and block map for the first block.
    510         1.1   mycroft 	 */
    511         1.1   mycroft 	if (start_lvl == 0) {
    512        1.60      fvdl 		sbap = &ip->i_ffs1_db[0];
    513         1.1   mycroft 		soff = start_lbn;
    514         1.1   mycroft 	} else {
    515         1.1   mycroft 		idp = &start_ap[start_lvl - 1];
    516  1.106.10.1      yamt 		if (bread(vp, idp->in_lbn, (int)fs->fs_bsize,
    517  1.106.10.1      yamt 		    NOCRED, B_MODIFY, &sbp)) {
    518       1.101        ad 			brelse(sbp, 0);
    519         1.1   mycroft 			return (ENOSPC);
    520         1.1   mycroft 		}
    521        1.60      fvdl 		sbap = (int32_t *)sbp->b_data;
    522         1.1   mycroft 		soff = idp->in_off;
    523         1.1   mycroft 	}
    524         1.1   mycroft 	/*
    525         1.1   mycroft 	 * Find the preferred location for the cluster.
    526         1.1   mycroft 	 */
    527       1.101        ad 	mutex_enter(&ump->um_lock);
    528         1.1   mycroft 	pref = ffs_blkpref(ip, start_lbn, soff, sbap);
    529         1.1   mycroft 	/*
    530         1.1   mycroft 	 * If the block range spans two block maps, get the second map.
    531         1.1   mycroft 	 */
    532         1.1   mycroft 	if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
    533         1.1   mycroft 		ssize = len;
    534         1.1   mycroft 	} else {
    535         1.1   mycroft #ifdef DIAGNOSTIC
    536         1.1   mycroft 		if (start_ap[start_lvl-1].in_lbn == idp->in_lbn)
    537         1.1   mycroft 			panic("ffs_reallocblk: start == end");
    538         1.1   mycroft #endif
    539         1.1   mycroft 		ssize = len - (idp->in_off + 1);
    540  1.106.10.1      yamt 		if (bread(vp, idp->in_lbn, (int)fs->fs_bsize,
    541  1.106.10.1      yamt 		    NOCRED, B_MODIFY, &ebp))
    542         1.1   mycroft 			goto fail;
    543        1.58      fvdl 		ebap = (int32_t *)ebp->b_data;	/* XXX ondisk32 */
    544         1.1   mycroft 	}
    545         1.1   mycroft 	/*
    546         1.1   mycroft 	 * Search the block map looking for an allocation of the desired size.
    547         1.1   mycroft 	 */
    548        1.58      fvdl 	if ((newblk = (daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref,
    549       1.101        ad 	    len, ffs_clusteralloc)) == 0) {
    550       1.101        ad 		mutex_exit(&ump->um_lock);
    551         1.1   mycroft 		goto fail;
    552       1.101        ad 	}
    553         1.1   mycroft 	/*
    554         1.1   mycroft 	 * We have found a new contiguous block.
    555         1.1   mycroft 	 *
    556         1.1   mycroft 	 * First we have to replace the old block pointers with the new
    557         1.1   mycroft 	 * block pointers in the inode and indirect blocks associated
    558         1.1   mycroft 	 * with the file.
    559         1.1   mycroft 	 */
    560         1.5   mycroft #ifdef DEBUG
    561         1.5   mycroft 	if (prtrealloc)
    562        1.13  christos 		printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number,
    563         1.5   mycroft 		    start_lbn, end_lbn);
    564         1.5   mycroft #endif
    565         1.1   mycroft 	blkno = newblk;
    566         1.1   mycroft 	for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) {
    567        1.58      fvdl 		daddr_t ba;
    568        1.30      fvdl 
    569        1.30      fvdl 		if (i == ssize) {
    570         1.1   mycroft 			bap = ebap;
    571        1.30      fvdl 			soff = -i;
    572        1.30      fvdl 		}
    573        1.58      fvdl 		/* XXX ondisk32 */
    574        1.30      fvdl 		ba = ufs_rw32(*bap, UFS_FSNEEDSWAP(fs));
    575         1.1   mycroft #ifdef DIAGNOSTIC
    576        1.18      fvdl 		if (!ffs_checkblk(ip,
    577        1.18      fvdl 		   dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
    578        1.18      fvdl 			panic("ffs_reallocblks: unallocated block 2");
    579        1.30      fvdl 		if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != ba)
    580         1.1   mycroft 			panic("ffs_reallocblks: alloc mismatch");
    581         1.1   mycroft #endif
    582         1.5   mycroft #ifdef DEBUG
    583         1.5   mycroft 		if (prtrealloc)
    584        1.30      fvdl 			printf(" %d,", ba);
    585         1.5   mycroft #endif
    586        1.30      fvdl  		if (DOINGSOFTDEP(vp)) {
    587        1.60      fvdl  			if (sbap == &ip->i_ffs1_db[0] && i < ssize)
    588        1.30      fvdl  				softdep_setup_allocdirect(ip, start_lbn + i,
    589        1.30      fvdl  				    blkno, ba, fs->fs_bsize, fs->fs_bsize,
    590        1.30      fvdl  				    buflist->bs_children[i]);
    591        1.30      fvdl  			else
    592        1.30      fvdl  				softdep_setup_allocindir_page(ip, start_lbn + i,
    593        1.30      fvdl  				    i < ssize ? sbp : ebp, soff + i, blkno,
    594        1.30      fvdl  				    ba, buflist->bs_children[i]);
    595        1.30      fvdl  		}
    596        1.58      fvdl 		/* XXX ondisk32 */
    597        1.80   mycroft 		*bap++ = ufs_rw32((u_int32_t)blkno, UFS_FSNEEDSWAP(fs));
    598         1.1   mycroft 	}
    599         1.1   mycroft 	/*
    600         1.1   mycroft 	 * Next we must write out the modified inode and indirect blocks.
    601         1.1   mycroft 	 * For strict correctness, the writes should be synchronous since
    602         1.1   mycroft 	 * the old block values may have been written to disk. In practise
    603        1.81     perry 	 * they are almost never written, but if we are concerned about
    604         1.1   mycroft 	 * strict correctness, the `doasyncfree' flag should be set to zero.
    605         1.1   mycroft 	 *
    606         1.1   mycroft 	 * The test on `doasyncfree' should be changed to test a flag
    607         1.1   mycroft 	 * that shows whether the associated buffers and inodes have
    608         1.1   mycroft 	 * been written. The flag should be set when the cluster is
    609         1.1   mycroft 	 * started and cleared whenever the buffer or inode is flushed.
    610         1.1   mycroft 	 * We can then check below to see if it is set, and do the
    611         1.1   mycroft 	 * synchronous write only when it has been cleared.
    612         1.1   mycroft 	 */
    613        1.60      fvdl 	if (sbap != &ip->i_ffs1_db[0]) {
    614         1.1   mycroft 		if (doasyncfree)
    615         1.1   mycroft 			bdwrite(sbp);
    616         1.1   mycroft 		else
    617         1.1   mycroft 			bwrite(sbp);
    618         1.1   mycroft 	} else {
    619         1.1   mycroft 		ip->i_flag |= IN_CHANGE | IN_UPDATE;
    620        1.28   mycroft 		if (!doasyncfree)
    621        1.88      yamt 			ffs_update(vp, NULL, NULL, 1);
    622         1.1   mycroft 	}
    623        1.25   thorpej 	if (ssize < len) {
    624         1.1   mycroft 		if (doasyncfree)
    625         1.1   mycroft 			bdwrite(ebp);
    626         1.1   mycroft 		else
    627         1.1   mycroft 			bwrite(ebp);
    628        1.25   thorpej 	}
    629         1.1   mycroft 	/*
    630         1.1   mycroft 	 * Last, free the old blocks and assign the new blocks to the buffers.
    631         1.1   mycroft 	 */
    632         1.5   mycroft #ifdef DEBUG
    633         1.5   mycroft 	if (prtrealloc)
    634        1.13  christos 		printf("\n\tnew:");
    635         1.5   mycroft #endif
    636         1.1   mycroft 	for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) {
    637        1.30      fvdl 		if (!DOINGSOFTDEP(vp))
    638        1.76   hannken 			ffs_blkfree(fs, ip->i_devvp,
    639        1.30      fvdl 			    dbtofsb(fs, buflist->bs_children[i]->b_blkno),
    640        1.76   hannken 			    fs->fs_bsize, ip->i_number);
    641         1.1   mycroft 		buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno);
    642         1.5   mycroft #ifdef DEBUG
    643        1.18      fvdl 		if (!ffs_checkblk(ip,
    644        1.18      fvdl 		   dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize))
    645        1.18      fvdl 			panic("ffs_reallocblks: unallocated block 3");
    646         1.5   mycroft 		if (prtrealloc)
    647        1.13  christos 			printf(" %d,", blkno);
    648         1.5   mycroft #endif
    649         1.5   mycroft 	}
    650         1.5   mycroft #ifdef DEBUG
    651         1.5   mycroft 	if (prtrealloc) {
    652         1.5   mycroft 		prtrealloc--;
    653        1.13  christos 		printf("\n");
    654         1.1   mycroft 	}
    655         1.5   mycroft #endif
    656         1.1   mycroft 	return (0);
    657         1.1   mycroft 
    658         1.1   mycroft fail:
    659         1.1   mycroft 	if (ssize < len)
    660       1.101        ad 		brelse(ebp, 0);
    661        1.60      fvdl 	if (sbap != &ip->i_ffs1_db[0])
    662       1.101        ad 		brelse(sbp, 0);
    663         1.1   mycroft 	return (ENOSPC);
    664        1.55      matt #endif /* XXXUBC */
    665         1.1   mycroft }
    666        1.88      yamt #endif /* 0 */
    667         1.1   mycroft 
    668         1.1   mycroft /*
    669         1.1   mycroft  * Allocate an inode in the file system.
    670        1.81     perry  *
    671         1.1   mycroft  * If allocating a directory, use ffs_dirpref to select the inode.
    672         1.1   mycroft  * If allocating in a directory, the following hierarchy is followed:
    673         1.1   mycroft  *   1) allocate the preferred inode.
    674         1.1   mycroft  *   2) allocate an inode in the same cylinder group.
    675         1.1   mycroft  *   3) quadradically rehash into other cylinder groups, until an
    676         1.1   mycroft  *      available inode is located.
    677        1.47       wiz  * If no inode preference is given the following hierarchy is used
    678         1.1   mycroft  * to allocate an inode:
    679         1.1   mycroft  *   1) allocate an inode in cylinder group 0.
    680         1.1   mycroft  *   2) quadradically rehash into other cylinder groups, until an
    681         1.1   mycroft  *      available inode is located.
    682       1.106     pooka  *
    683       1.106     pooka  * => um_lock not held upon entry or return
    684         1.1   mycroft  */
    685         1.9  christos int
    686        1.91      elad ffs_valloc(struct vnode *pvp, int mode, kauth_cred_t cred,
    687        1.88      yamt     struct vnode **vpp)
    688         1.9  christos {
    689       1.101        ad 	struct ufsmount *ump;
    690        1.33  augustss 	struct inode *pip;
    691        1.33  augustss 	struct fs *fs;
    692        1.33  augustss 	struct inode *ip;
    693        1.60      fvdl 	struct timespec ts;
    694         1.1   mycroft 	ino_t ino, ipref;
    695         1.1   mycroft 	int cg, error;
    696        1.81     perry 
    697        1.88      yamt 	*vpp = NULL;
    698         1.1   mycroft 	pip = VTOI(pvp);
    699         1.1   mycroft 	fs = pip->i_fs;
    700       1.101        ad 	ump = pip->i_ump;
    701       1.101        ad 
    702       1.101        ad 	mutex_enter(&ump->um_lock);
    703         1.1   mycroft 	if (fs->fs_cstotal.cs_nifree == 0)
    704         1.1   mycroft 		goto noinodes;
    705         1.1   mycroft 
    706         1.1   mycroft 	if ((mode & IFMT) == IFDIR)
    707        1.50     lukem 		ipref = ffs_dirpref(pip);
    708        1.50     lukem 	else
    709        1.50     lukem 		ipref = pip->i_number;
    710         1.1   mycroft 	if (ipref >= fs->fs_ncg * fs->fs_ipg)
    711         1.1   mycroft 		ipref = 0;
    712         1.1   mycroft 	cg = ino_to_cg(fs, ipref);
    713        1.50     lukem 	/*
    714        1.50     lukem 	 * Track number of dirs created one after another
    715        1.50     lukem 	 * in a same cg without intervening by files.
    716        1.50     lukem 	 */
    717        1.50     lukem 	if ((mode & IFMT) == IFDIR) {
    718        1.63      fvdl 		if (fs->fs_contigdirs[cg] < 255)
    719        1.50     lukem 			fs->fs_contigdirs[cg]++;
    720        1.50     lukem 	} else {
    721        1.50     lukem 		if (fs->fs_contigdirs[cg] > 0)
    722        1.50     lukem 			fs->fs_contigdirs[cg]--;
    723        1.50     lukem 	}
    724        1.60      fvdl 	ino = (ino_t)ffs_hashalloc(pip, cg, ipref, mode, ffs_nodealloccg);
    725         1.1   mycroft 	if (ino == 0)
    726         1.1   mycroft 		goto noinodes;
    727        1.88      yamt 	error = VFS_VGET(pvp->v_mount, ino, vpp);
    728         1.1   mycroft 	if (error) {
    729        1.88      yamt 		ffs_vfree(pvp, ino, mode);
    730         1.1   mycroft 		return (error);
    731         1.1   mycroft 	}
    732        1.90      yamt 	KASSERT((*vpp)->v_type == VNON);
    733        1.88      yamt 	ip = VTOI(*vpp);
    734        1.60      fvdl 	if (ip->i_mode) {
    735        1.60      fvdl #if 0
    736        1.13  christos 		printf("mode = 0%o, inum = %d, fs = %s\n",
    737        1.60      fvdl 		    ip->i_mode, ip->i_number, fs->fs_fsmnt);
    738        1.60      fvdl #else
    739        1.60      fvdl 		printf("dmode %x mode %x dgen %x gen %x\n",
    740        1.60      fvdl 		    DIP(ip, mode), ip->i_mode,
    741        1.60      fvdl 		    DIP(ip, gen), ip->i_gen);
    742        1.60      fvdl 		printf("size %llx blocks %llx\n",
    743        1.60      fvdl 		    (long long)DIP(ip, size), (long long)DIP(ip, blocks));
    744        1.86  christos 		printf("ino %llu ipref %llu\n", (unsigned long long)ino,
    745        1.86  christos 		    (unsigned long long)ipref);
    746        1.60      fvdl #if 0
    747        1.60      fvdl 		error = bread(ump->um_devvp, fsbtodb(fs, ino_to_fsba(fs, ino)),
    748  1.106.10.1      yamt 		    (int)fs->fs_bsize, NOCRED, 0, &bp);
    749        1.60      fvdl #endif
    750        1.60      fvdl 
    751        1.60      fvdl #endif
    752         1.1   mycroft 		panic("ffs_valloc: dup alloc");
    753         1.1   mycroft 	}
    754        1.60      fvdl 	if (DIP(ip, blocks)) {				/* XXX */
    755        1.86  christos 		printf("free inode %s/%llu had %" PRId64 " blocks\n",
    756        1.86  christos 		    fs->fs_fsmnt, (unsigned long long)ino, DIP(ip, blocks));
    757        1.65  kristerw 		DIP_ASSIGN(ip, blocks, 0);
    758         1.1   mycroft 	}
    759        1.57   hannken 	ip->i_flag &= ~IN_SPACECOUNTED;
    760        1.61      fvdl 	ip->i_flags = 0;
    761        1.65  kristerw 	DIP_ASSIGN(ip, flags, 0);
    762         1.1   mycroft 	/*
    763         1.1   mycroft 	 * Set up a new generation number for this inode.
    764         1.1   mycroft 	 */
    765        1.60      fvdl 	ip->i_gen++;
    766        1.65  kristerw 	DIP_ASSIGN(ip, gen, ip->i_gen);
    767        1.60      fvdl 	if (fs->fs_magic == FS_UFS2_MAGIC) {
    768        1.93      yamt 		vfs_timestamp(&ts);
    769        1.60      fvdl 		ip->i_ffs2_birthtime = ts.tv_sec;
    770        1.60      fvdl 		ip->i_ffs2_birthnsec = ts.tv_nsec;
    771        1.60      fvdl 	}
    772         1.1   mycroft 	return (0);
    773         1.1   mycroft noinodes:
    774       1.101        ad 	mutex_exit(&ump->um_lock);
    775        1.91      elad 	ffs_fserr(fs, kauth_cred_geteuid(cred), "out of inodes");
    776         1.1   mycroft 	uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt);
    777         1.1   mycroft 	return (ENOSPC);
    778         1.1   mycroft }
    779         1.1   mycroft 
    780         1.1   mycroft /*
    781        1.50     lukem  * Find a cylinder group in which to place a directory.
    782        1.42  sommerfe  *
    783        1.50     lukem  * The policy implemented by this algorithm is to allocate a
    784        1.50     lukem  * directory inode in the same cylinder group as its parent
    785        1.50     lukem  * directory, but also to reserve space for its files inodes
    786        1.50     lukem  * and data. Restrict the number of directories which may be
    787        1.50     lukem  * allocated one after another in the same cylinder group
    788        1.50     lukem  * without intervening allocation of files.
    789        1.42  sommerfe  *
    790        1.50     lukem  * If we allocate a first level directory then force allocation
    791        1.50     lukem  * in another cylinder group.
    792         1.1   mycroft  */
    793         1.1   mycroft static ino_t
    794        1.85   thorpej ffs_dirpref(struct inode *pip)
    795         1.1   mycroft {
    796        1.50     lukem 	register struct fs *fs;
    797        1.74     soren 	int cg, prefcg;
    798        1.89       dsl 	int64_t dirsize, cgsize, curdsz;
    799        1.89       dsl 	int avgifree, avgbfree, avgndir;
    800        1.50     lukem 	int minifree, minbfree, maxndir;
    801        1.50     lukem 	int mincg, minndir;
    802        1.50     lukem 	int maxcontigdirs;
    803        1.50     lukem 
    804       1.101        ad 	KASSERT(mutex_owned(&pip->i_ump->um_lock));
    805       1.101        ad 
    806        1.50     lukem 	fs = pip->i_fs;
    807         1.1   mycroft 
    808         1.1   mycroft 	avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg;
    809        1.50     lukem 	avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
    810        1.50     lukem 	avgndir = fs->fs_cstotal.cs_ndir / fs->fs_ncg;
    811        1.50     lukem 
    812        1.50     lukem 	/*
    813        1.50     lukem 	 * Force allocation in another cg if creating a first level dir.
    814        1.50     lukem 	 */
    815       1.102        ad 	if (ITOV(pip)->v_vflag & VV_ROOT) {
    816        1.71   mycroft 		prefcg = random() % fs->fs_ncg;
    817        1.50     lukem 		mincg = prefcg;
    818        1.50     lukem 		minndir = fs->fs_ipg;
    819        1.50     lukem 		for (cg = prefcg; cg < fs->fs_ncg; cg++)
    820        1.50     lukem 			if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
    821        1.50     lukem 			    fs->fs_cs(fs, cg).cs_nifree >= avgifree &&
    822        1.50     lukem 			    fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
    823        1.42  sommerfe 				mincg = cg;
    824        1.50     lukem 				minndir = fs->fs_cs(fs, cg).cs_ndir;
    825        1.42  sommerfe 			}
    826        1.50     lukem 		for (cg = 0; cg < prefcg; cg++)
    827        1.50     lukem 			if (fs->fs_cs(fs, cg).cs_ndir < minndir &&
    828        1.50     lukem 			    fs->fs_cs(fs, cg).cs_nifree >= avgifree &&
    829        1.50     lukem 			    fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
    830        1.50     lukem 				mincg = cg;
    831        1.50     lukem 				minndir = fs->fs_cs(fs, cg).cs_ndir;
    832        1.42  sommerfe 			}
    833        1.50     lukem 		return ((ino_t)(fs->fs_ipg * mincg));
    834        1.42  sommerfe 	}
    835        1.50     lukem 
    836        1.50     lukem 	/*
    837        1.50     lukem 	 * Count various limits which used for
    838        1.50     lukem 	 * optimal allocation of a directory inode.
    839        1.50     lukem 	 */
    840        1.50     lukem 	maxndir = min(avgndir + fs->fs_ipg / 16, fs->fs_ipg);
    841        1.50     lukem 	minifree = avgifree - fs->fs_ipg / 4;
    842        1.50     lukem 	if (minifree < 0)
    843        1.50     lukem 		minifree = 0;
    844        1.54   mycroft 	minbfree = avgbfree - fragstoblks(fs, fs->fs_fpg) / 4;
    845        1.50     lukem 	if (minbfree < 0)
    846        1.50     lukem 		minbfree = 0;
    847        1.89       dsl 	cgsize = (int64_t)fs->fs_fsize * fs->fs_fpg;
    848        1.89       dsl 	dirsize = (int64_t)fs->fs_avgfilesize * fs->fs_avgfpdir;
    849        1.89       dsl 	if (avgndir != 0) {
    850        1.89       dsl 		curdsz = (cgsize - (int64_t)avgbfree * fs->fs_bsize) / avgndir;
    851        1.89       dsl 		if (dirsize < curdsz)
    852        1.89       dsl 			dirsize = curdsz;
    853        1.89       dsl 	}
    854        1.89       dsl 	if (cgsize < dirsize * 255)
    855        1.89       dsl 		maxcontigdirs = cgsize / dirsize;
    856        1.89       dsl 	else
    857        1.89       dsl 		maxcontigdirs = 255;
    858        1.50     lukem 	if (fs->fs_avgfpdir > 0)
    859        1.50     lukem 		maxcontigdirs = min(maxcontigdirs,
    860        1.50     lukem 				    fs->fs_ipg / fs->fs_avgfpdir);
    861        1.50     lukem 	if (maxcontigdirs == 0)
    862        1.50     lukem 		maxcontigdirs = 1;
    863        1.50     lukem 
    864        1.50     lukem 	/*
    865        1.81     perry 	 * Limit number of dirs in one cg and reserve space for
    866        1.50     lukem 	 * regular files, but only if we have no deficit in
    867        1.50     lukem 	 * inodes or space.
    868        1.50     lukem 	 */
    869        1.50     lukem 	prefcg = ino_to_cg(fs, pip->i_number);
    870        1.50     lukem 	for (cg = prefcg; cg < fs->fs_ncg; cg++)
    871        1.50     lukem 		if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
    872        1.50     lukem 		    fs->fs_cs(fs, cg).cs_nifree >= minifree &&
    873        1.50     lukem 	    	    fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
    874        1.50     lukem 			if (fs->fs_contigdirs[cg] < maxcontigdirs)
    875        1.50     lukem 				return ((ino_t)(fs->fs_ipg * cg));
    876        1.50     lukem 		}
    877        1.50     lukem 	for (cg = 0; cg < prefcg; cg++)
    878        1.50     lukem 		if (fs->fs_cs(fs, cg).cs_ndir < maxndir &&
    879        1.50     lukem 		    fs->fs_cs(fs, cg).cs_nifree >= minifree &&
    880        1.50     lukem 	    	    fs->fs_cs(fs, cg).cs_nbfree >= minbfree) {
    881        1.50     lukem 			if (fs->fs_contigdirs[cg] < maxcontigdirs)
    882        1.50     lukem 				return ((ino_t)(fs->fs_ipg * cg));
    883        1.50     lukem 		}
    884        1.50     lukem 	/*
    885        1.50     lukem 	 * This is a backstop when we are deficient in space.
    886        1.50     lukem 	 */
    887        1.50     lukem 	for (cg = prefcg; cg < fs->fs_ncg; cg++)
    888        1.50     lukem 		if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
    889        1.50     lukem 			return ((ino_t)(fs->fs_ipg * cg));
    890        1.50     lukem 	for (cg = 0; cg < prefcg; cg++)
    891        1.50     lukem 		if (fs->fs_cs(fs, cg).cs_nifree >= avgifree)
    892        1.50     lukem 			break;
    893        1.50     lukem 	return ((ino_t)(fs->fs_ipg * cg));
    894         1.1   mycroft }
    895         1.1   mycroft 
    896         1.1   mycroft /*
    897         1.1   mycroft  * Select the desired position for the next block in a file.  The file is
    898         1.1   mycroft  * logically divided into sections. The first section is composed of the
    899         1.1   mycroft  * direct blocks. Each additional section contains fs_maxbpg blocks.
    900        1.81     perry  *
    901         1.1   mycroft  * If no blocks have been allocated in the first section, the policy is to
    902         1.1   mycroft  * request a block in the same cylinder group as the inode that describes
    903         1.1   mycroft  * the file. If no blocks have been allocated in any other section, the
    904         1.1   mycroft  * policy is to place the section in a cylinder group with a greater than
    905         1.1   mycroft  * average number of free blocks.  An appropriate cylinder group is found
    906         1.1   mycroft  * by using a rotor that sweeps the cylinder groups. When a new group of
    907         1.1   mycroft  * blocks is needed, the sweep begins in the cylinder group following the
    908         1.1   mycroft  * cylinder group from which the previous allocation was made. The sweep
    909         1.1   mycroft  * continues until a cylinder group with greater than the average number
    910         1.1   mycroft  * of free blocks is found. If the allocation is for the first block in an
    911         1.1   mycroft  * indirect block, the information on the previous allocation is unavailable;
    912         1.1   mycroft  * here a best guess is made based upon the logical block number being
    913         1.1   mycroft  * allocated.
    914        1.81     perry  *
    915         1.1   mycroft  * If a section is already partially allocated, the policy is to
    916         1.1   mycroft  * contiguously allocate fs_maxcontig blocks.  The end of one of these
    917        1.60      fvdl  * contiguous blocks and the beginning of the next is laid out
    918        1.60      fvdl  * contigously if possible.
    919       1.106     pooka  *
    920       1.106     pooka  * => um_lock held on entry and exit
    921         1.1   mycroft  */
    922        1.58      fvdl daddr_t
    923        1.85   thorpej ffs_blkpref_ufs1(struct inode *ip, daddr_t lbn, int indx,
    924        1.85   thorpej     int32_t *bap /* XXX ondisk32 */)
    925         1.1   mycroft {
    926        1.33  augustss 	struct fs *fs;
    927        1.33  augustss 	int cg;
    928         1.1   mycroft 	int avgbfree, startcg;
    929         1.1   mycroft 
    930       1.101        ad 	KASSERT(mutex_owned(&ip->i_ump->um_lock));
    931       1.101        ad 
    932         1.1   mycroft 	fs = ip->i_fs;
    933         1.1   mycroft 	if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) {
    934        1.31      fvdl 		if (lbn < NDADDR + NINDIR(fs)) {
    935         1.1   mycroft 			cg = ino_to_cg(fs, ip->i_number);
    936         1.1   mycroft 			return (fs->fs_fpg * cg + fs->fs_frag);
    937         1.1   mycroft 		}
    938         1.1   mycroft 		/*
    939         1.1   mycroft 		 * Find a cylinder with greater than average number of
    940         1.1   mycroft 		 * unused data blocks.
    941         1.1   mycroft 		 */
    942         1.1   mycroft 		if (indx == 0 || bap[indx - 1] == 0)
    943         1.1   mycroft 			startcg =
    944         1.1   mycroft 			    ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg;
    945         1.1   mycroft 		else
    946        1.19    bouyer 			startcg = dtog(fs,
    947        1.30      fvdl 				ufs_rw32(bap[indx - 1], UFS_FSNEEDSWAP(fs)) + 1);
    948         1.1   mycroft 		startcg %= fs->fs_ncg;
    949         1.1   mycroft 		avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
    950         1.1   mycroft 		for (cg = startcg; cg < fs->fs_ncg; cg++)
    951         1.1   mycroft 			if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
    952         1.1   mycroft 				return (fs->fs_fpg * cg + fs->fs_frag);
    953         1.1   mycroft 			}
    954        1.52     lukem 		for (cg = 0; cg < startcg; cg++)
    955         1.1   mycroft 			if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
    956         1.1   mycroft 				return (fs->fs_fpg * cg + fs->fs_frag);
    957         1.1   mycroft 			}
    958        1.35   thorpej 		return (0);
    959         1.1   mycroft 	}
    960         1.1   mycroft 	/*
    961        1.60      fvdl 	 * We just always try to lay things out contiguously.
    962        1.60      fvdl 	 */
    963        1.60      fvdl 	return ufs_rw32(bap[indx - 1], UFS_FSNEEDSWAP(fs)) + fs->fs_frag;
    964        1.60      fvdl }
    965        1.60      fvdl 
    966        1.60      fvdl daddr_t
    967        1.85   thorpej ffs_blkpref_ufs2(struct inode *ip, daddr_t lbn, int indx, int64_t *bap)
    968        1.60      fvdl {
    969        1.60      fvdl 	struct fs *fs;
    970        1.60      fvdl 	int cg;
    971        1.60      fvdl 	int avgbfree, startcg;
    972        1.60      fvdl 
    973       1.101        ad 	KASSERT(mutex_owned(&ip->i_ump->um_lock));
    974       1.101        ad 
    975        1.60      fvdl 	fs = ip->i_fs;
    976        1.60      fvdl 	if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) {
    977        1.60      fvdl 		if (lbn < NDADDR + NINDIR(fs)) {
    978        1.60      fvdl 			cg = ino_to_cg(fs, ip->i_number);
    979        1.60      fvdl 			return (fs->fs_fpg * cg + fs->fs_frag);
    980        1.60      fvdl 		}
    981         1.1   mycroft 		/*
    982        1.60      fvdl 		 * Find a cylinder with greater than average number of
    983        1.60      fvdl 		 * unused data blocks.
    984         1.1   mycroft 		 */
    985        1.60      fvdl 		if (indx == 0 || bap[indx - 1] == 0)
    986        1.60      fvdl 			startcg =
    987        1.60      fvdl 			    ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg;
    988        1.60      fvdl 		else
    989        1.60      fvdl 			startcg = dtog(fs,
    990        1.60      fvdl 				ufs_rw64(bap[indx - 1], UFS_FSNEEDSWAP(fs)) + 1);
    991        1.60      fvdl 		startcg %= fs->fs_ncg;
    992        1.60      fvdl 		avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg;
    993        1.60      fvdl 		for (cg = startcg; cg < fs->fs_ncg; cg++)
    994        1.60      fvdl 			if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
    995        1.60      fvdl 				return (fs->fs_fpg * cg + fs->fs_frag);
    996        1.60      fvdl 			}
    997        1.60      fvdl 		for (cg = 0; cg < startcg; cg++)
    998        1.60      fvdl 			if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) {
    999        1.60      fvdl 				return (fs->fs_fpg * cg + fs->fs_frag);
   1000        1.60      fvdl 			}
   1001        1.60      fvdl 		return (0);
   1002        1.60      fvdl 	}
   1003        1.60      fvdl 	/*
   1004        1.60      fvdl 	 * We just always try to lay things out contiguously.
   1005        1.60      fvdl 	 */
   1006        1.60      fvdl 	return ufs_rw64(bap[indx - 1], UFS_FSNEEDSWAP(fs)) + fs->fs_frag;
   1007         1.1   mycroft }
   1008         1.1   mycroft 
   1009        1.60      fvdl 
   1010         1.1   mycroft /*
   1011         1.1   mycroft  * Implement the cylinder overflow algorithm.
   1012         1.1   mycroft  *
   1013         1.1   mycroft  * The policy implemented by this algorithm is:
   1014         1.1   mycroft  *   1) allocate the block in its requested cylinder group.
   1015         1.1   mycroft  *   2) quadradically rehash on the cylinder group number.
   1016         1.1   mycroft  *   3) brute force search for a free block.
   1017       1.106     pooka  *
   1018       1.106     pooka  * => called with um_lock held
   1019       1.106     pooka  * => returns with um_lock released on success, held on failure
   1020       1.106     pooka  *    (*allocator releases lock on success, retains lock on failure)
   1021         1.1   mycroft  */
   1022         1.1   mycroft /*VARARGS5*/
   1023        1.58      fvdl static daddr_t
   1024        1.85   thorpej ffs_hashalloc(struct inode *ip, int cg, daddr_t pref,
   1025        1.85   thorpej     int size /* size for data blocks, mode for inodes */,
   1026        1.85   thorpej     daddr_t (*allocator)(struct inode *, int, daddr_t, int))
   1027         1.1   mycroft {
   1028        1.33  augustss 	struct fs *fs;
   1029        1.58      fvdl 	daddr_t result;
   1030         1.1   mycroft 	int i, icg = cg;
   1031         1.1   mycroft 
   1032         1.1   mycroft 	fs = ip->i_fs;
   1033         1.1   mycroft 	/*
   1034         1.1   mycroft 	 * 1: preferred cylinder group
   1035         1.1   mycroft 	 */
   1036         1.1   mycroft 	result = (*allocator)(ip, cg, pref, size);
   1037         1.1   mycroft 	if (result)
   1038         1.1   mycroft 		return (result);
   1039         1.1   mycroft 	/*
   1040         1.1   mycroft 	 * 2: quadratic rehash
   1041         1.1   mycroft 	 */
   1042         1.1   mycroft 	for (i = 1; i < fs->fs_ncg; i *= 2) {
   1043         1.1   mycroft 		cg += i;
   1044         1.1   mycroft 		if (cg >= fs->fs_ncg)
   1045         1.1   mycroft 			cg -= fs->fs_ncg;
   1046         1.1   mycroft 		result = (*allocator)(ip, cg, 0, size);
   1047         1.1   mycroft 		if (result)
   1048         1.1   mycroft 			return (result);
   1049         1.1   mycroft 	}
   1050         1.1   mycroft 	/*
   1051         1.1   mycroft 	 * 3: brute force search
   1052         1.1   mycroft 	 * Note that we start at i == 2, since 0 was checked initially,
   1053         1.1   mycroft 	 * and 1 is always checked in the quadratic rehash.
   1054         1.1   mycroft 	 */
   1055         1.1   mycroft 	cg = (icg + 2) % fs->fs_ncg;
   1056         1.1   mycroft 	for (i = 2; i < fs->fs_ncg; i++) {
   1057         1.1   mycroft 		result = (*allocator)(ip, cg, 0, size);
   1058         1.1   mycroft 		if (result)
   1059         1.1   mycroft 			return (result);
   1060         1.1   mycroft 		cg++;
   1061         1.1   mycroft 		if (cg == fs->fs_ncg)
   1062         1.1   mycroft 			cg = 0;
   1063         1.1   mycroft 	}
   1064        1.35   thorpej 	return (0);
   1065         1.1   mycroft }
   1066         1.1   mycroft 
   1067         1.1   mycroft /*
   1068         1.1   mycroft  * Determine whether a fragment can be extended.
   1069         1.1   mycroft  *
   1070        1.81     perry  * Check to see if the necessary fragments are available, and
   1071         1.1   mycroft  * if they are, allocate them.
   1072       1.106     pooka  *
   1073       1.106     pooka  * => called with um_lock held
   1074       1.106     pooka  * => returns with um_lock released on success, held on failure
   1075         1.1   mycroft  */
   1076        1.58      fvdl static daddr_t
   1077        1.85   thorpej ffs_fragextend(struct inode *ip, int cg, daddr_t bprev, int osize, int nsize)
   1078         1.1   mycroft {
   1079       1.101        ad 	struct ufsmount *ump;
   1080        1.33  augustss 	struct fs *fs;
   1081        1.33  augustss 	struct cg *cgp;
   1082         1.1   mycroft 	struct buf *bp;
   1083        1.58      fvdl 	daddr_t bno;
   1084         1.1   mycroft 	int frags, bbase;
   1085         1.1   mycroft 	int i, error;
   1086        1.62      fvdl 	u_int8_t *blksfree;
   1087         1.1   mycroft 
   1088         1.1   mycroft 	fs = ip->i_fs;
   1089       1.101        ad 	ump = ip->i_ump;
   1090       1.101        ad 
   1091       1.101        ad 	KASSERT(mutex_owned(&ump->um_lock));
   1092       1.101        ad 
   1093         1.1   mycroft 	if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize))
   1094        1.35   thorpej 		return (0);
   1095         1.1   mycroft 	frags = numfrags(fs, nsize);
   1096         1.1   mycroft 	bbase = fragnum(fs, bprev);
   1097         1.1   mycroft 	if (bbase > fragnum(fs, (bprev + frags - 1))) {
   1098         1.1   mycroft 		/* cannot extend across a block boundary */
   1099        1.35   thorpej 		return (0);
   1100         1.1   mycroft 	}
   1101       1.101        ad 	mutex_exit(&ump->um_lock);
   1102         1.1   mycroft 	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
   1103  1.106.10.1      yamt 		(int)fs->fs_cgsize, NOCRED, B_MODIFY, &bp);
   1104       1.101        ad 	if (error)
   1105       1.101        ad 		goto fail;
   1106         1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1107       1.101        ad 	if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs)))
   1108       1.101        ad 		goto fail;
   1109        1.92    kardel 	cgp->cg_old_time = ufs_rw32(time_second, UFS_FSNEEDSWAP(fs));
   1110        1.73       dbj 	if ((fs->fs_magic != FS_UFS1_MAGIC) ||
   1111        1.73       dbj 	    (fs->fs_old_flags & FS_FLAGS_UPDATED))
   1112        1.92    kardel 		cgp->cg_time = ufs_rw64(time_second, UFS_FSNEEDSWAP(fs));
   1113         1.1   mycroft 	bno = dtogd(fs, bprev);
   1114        1.62      fvdl 	blksfree = cg_blksfree(cgp, UFS_FSNEEDSWAP(fs));
   1115         1.1   mycroft 	for (i = numfrags(fs, osize); i < frags; i++)
   1116       1.101        ad 		if (isclr(blksfree, bno + i))
   1117       1.101        ad 			goto fail;
   1118         1.1   mycroft 	/*
   1119         1.1   mycroft 	 * the current fragment can be extended
   1120         1.1   mycroft 	 * deduct the count on fragment being extended into
   1121         1.1   mycroft 	 * increase the count on the remaining fragment (if any)
   1122         1.1   mycroft 	 * allocate the extended piece
   1123         1.1   mycroft 	 */
   1124         1.1   mycroft 	for (i = frags; i < fs->fs_frag - bbase; i++)
   1125        1.62      fvdl 		if (isclr(blksfree, bno + i))
   1126         1.1   mycroft 			break;
   1127        1.30      fvdl 	ufs_add32(cgp->cg_frsum[i - numfrags(fs, osize)], -1, UFS_FSNEEDSWAP(fs));
   1128         1.1   mycroft 	if (i != frags)
   1129        1.30      fvdl 		ufs_add32(cgp->cg_frsum[i - frags], 1, UFS_FSNEEDSWAP(fs));
   1130       1.101        ad 	mutex_enter(&ump->um_lock);
   1131         1.1   mycroft 	for (i = numfrags(fs, osize); i < frags; i++) {
   1132        1.62      fvdl 		clrbit(blksfree, bno + i);
   1133        1.30      fvdl 		ufs_add32(cgp->cg_cs.cs_nffree, -1, UFS_FSNEEDSWAP(fs));
   1134         1.1   mycroft 		fs->fs_cstotal.cs_nffree--;
   1135         1.1   mycroft 		fs->fs_cs(fs, cg).cs_nffree--;
   1136         1.1   mycroft 	}
   1137         1.1   mycroft 	fs->fs_fmod = 1;
   1138       1.101        ad 	ACTIVECG_CLR(fs, cg);
   1139       1.101        ad 	mutex_exit(&ump->um_lock);
   1140        1.30      fvdl 	if (DOINGSOFTDEP(ITOV(ip)))
   1141        1.30      fvdl 		softdep_setup_blkmapdep(bp, fs, bprev);
   1142         1.1   mycroft 	bdwrite(bp);
   1143         1.1   mycroft 	return (bprev);
   1144       1.101        ad 
   1145       1.101        ad  fail:
   1146       1.101        ad  	brelse(bp, 0);
   1147       1.101        ad  	mutex_enter(&ump->um_lock);
   1148       1.101        ad  	return (0);
   1149         1.1   mycroft }
   1150         1.1   mycroft 
   1151         1.1   mycroft /*
   1152         1.1   mycroft  * Determine whether a block can be allocated.
   1153         1.1   mycroft  *
   1154         1.1   mycroft  * Check to see if a block of the appropriate size is available,
   1155         1.1   mycroft  * and if it is, allocate it.
   1156         1.1   mycroft  */
   1157        1.58      fvdl static daddr_t
   1158        1.85   thorpej ffs_alloccg(struct inode *ip, int cg, daddr_t bpref, int size)
   1159         1.1   mycroft {
   1160       1.101        ad 	struct ufsmount *ump;
   1161        1.62      fvdl 	struct fs *fs = ip->i_fs;
   1162        1.30      fvdl 	struct cg *cgp;
   1163         1.1   mycroft 	struct buf *bp;
   1164        1.60      fvdl 	int32_t bno;
   1165        1.60      fvdl 	daddr_t blkno;
   1166        1.30      fvdl 	int error, frags, allocsiz, i;
   1167        1.62      fvdl 	u_int8_t *blksfree;
   1168        1.30      fvdl #ifdef FFS_EI
   1169        1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   1170        1.30      fvdl #endif
   1171         1.1   mycroft 
   1172       1.101        ad 	ump = ip->i_ump;
   1173       1.101        ad 
   1174       1.101        ad 	KASSERT(mutex_owned(&ump->um_lock));
   1175       1.101        ad 
   1176         1.1   mycroft 	if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize)
   1177        1.35   thorpej 		return (0);
   1178       1.101        ad 	mutex_exit(&ump->um_lock);
   1179         1.1   mycroft 	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
   1180  1.106.10.1      yamt 		(int)fs->fs_cgsize, NOCRED, B_MODIFY, &bp);
   1181       1.101        ad 	if (error)
   1182       1.101        ad 		goto fail;
   1183         1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1184        1.19    bouyer 	if (!cg_chkmagic(cgp, needswap) ||
   1185       1.101        ad 	    (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize))
   1186       1.101        ad 		goto fail;
   1187        1.92    kardel 	cgp->cg_old_time = ufs_rw32(time_second, needswap);
   1188        1.73       dbj 	if ((fs->fs_magic != FS_UFS1_MAGIC) ||
   1189        1.73       dbj 	    (fs->fs_old_flags & FS_FLAGS_UPDATED))
   1190        1.92    kardel 		cgp->cg_time = ufs_rw64(time_second, needswap);
   1191         1.1   mycroft 	if (size == fs->fs_bsize) {
   1192       1.101        ad 		mutex_enter(&ump->um_lock);
   1193        1.60      fvdl 		blkno = ffs_alloccgblk(ip, bp, bpref);
   1194        1.76   hannken 		ACTIVECG_CLR(fs, cg);
   1195       1.101        ad 		mutex_exit(&ump->um_lock);
   1196         1.1   mycroft 		bdwrite(bp);
   1197        1.60      fvdl 		return (blkno);
   1198         1.1   mycroft 	}
   1199         1.1   mycroft 	/*
   1200         1.1   mycroft 	 * check to see if any fragments are already available
   1201         1.1   mycroft 	 * allocsiz is the size which will be allocated, hacking
   1202         1.1   mycroft 	 * it down to a smaller size if necessary
   1203         1.1   mycroft 	 */
   1204        1.62      fvdl 	blksfree = cg_blksfree(cgp, needswap);
   1205         1.1   mycroft 	frags = numfrags(fs, size);
   1206         1.1   mycroft 	for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++)
   1207         1.1   mycroft 		if (cgp->cg_frsum[allocsiz] != 0)
   1208         1.1   mycroft 			break;
   1209         1.1   mycroft 	if (allocsiz == fs->fs_frag) {
   1210         1.1   mycroft 		/*
   1211        1.81     perry 		 * no fragments were available, so a block will be
   1212         1.1   mycroft 		 * allocated, and hacked up
   1213         1.1   mycroft 		 */
   1214       1.101        ad 		if (cgp->cg_cs.cs_nbfree == 0)
   1215       1.101        ad 			goto fail;
   1216       1.101        ad 		mutex_enter(&ump->um_lock);
   1217        1.60      fvdl 		blkno = ffs_alloccgblk(ip, bp, bpref);
   1218        1.60      fvdl 		bno = dtogd(fs, blkno);
   1219         1.1   mycroft 		for (i = frags; i < fs->fs_frag; i++)
   1220        1.62      fvdl 			setbit(blksfree, bno + i);
   1221         1.1   mycroft 		i = fs->fs_frag - frags;
   1222        1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_nffree, i, needswap);
   1223         1.1   mycroft 		fs->fs_cstotal.cs_nffree += i;
   1224        1.30      fvdl 		fs->fs_cs(fs, cg).cs_nffree += i;
   1225         1.1   mycroft 		fs->fs_fmod = 1;
   1226        1.19    bouyer 		ufs_add32(cgp->cg_frsum[i], 1, needswap);
   1227        1.76   hannken 		ACTIVECG_CLR(fs, cg);
   1228       1.101        ad 		mutex_exit(&ump->um_lock);
   1229         1.1   mycroft 		bdwrite(bp);
   1230        1.60      fvdl 		return (blkno);
   1231         1.1   mycroft 	}
   1232        1.30      fvdl 	bno = ffs_mapsearch(fs, cgp, bpref, allocsiz);
   1233        1.30      fvdl #if 0
   1234        1.30      fvdl 	/*
   1235        1.30      fvdl 	 * XXX fvdl mapsearch will panic, and never return -1
   1236        1.58      fvdl 	 *          also: returning NULL as daddr_t ?
   1237        1.30      fvdl 	 */
   1238       1.101        ad 	if (bno < 0)
   1239       1.101        ad 		goto fail;
   1240        1.30      fvdl #endif
   1241         1.1   mycroft 	for (i = 0; i < frags; i++)
   1242        1.62      fvdl 		clrbit(blksfree, bno + i);
   1243       1.101        ad 	mutex_enter(&ump->um_lock);
   1244        1.19    bouyer 	ufs_add32(cgp->cg_cs.cs_nffree, -frags, needswap);
   1245         1.1   mycroft 	fs->fs_cstotal.cs_nffree -= frags;
   1246         1.1   mycroft 	fs->fs_cs(fs, cg).cs_nffree -= frags;
   1247         1.1   mycroft 	fs->fs_fmod = 1;
   1248        1.19    bouyer 	ufs_add32(cgp->cg_frsum[allocsiz], -1, needswap);
   1249         1.1   mycroft 	if (frags != allocsiz)
   1250        1.19    bouyer 		ufs_add32(cgp->cg_frsum[allocsiz - frags], 1, needswap);
   1251        1.30      fvdl 	blkno = cg * fs->fs_fpg + bno;
   1252       1.101        ad 	ACTIVECG_CLR(fs, cg);
   1253       1.101        ad 	mutex_exit(&ump->um_lock);
   1254        1.30      fvdl 	if (DOINGSOFTDEP(ITOV(ip)))
   1255        1.30      fvdl 		softdep_setup_blkmapdep(bp, fs, blkno);
   1256         1.1   mycroft 	bdwrite(bp);
   1257        1.30      fvdl 	return blkno;
   1258       1.101        ad 
   1259       1.101        ad  fail:
   1260       1.101        ad  	brelse(bp, 0);
   1261       1.101        ad  	mutex_enter(&ump->um_lock);
   1262       1.101        ad  	return (0);
   1263         1.1   mycroft }
   1264         1.1   mycroft 
   1265         1.1   mycroft /*
   1266         1.1   mycroft  * Allocate a block in a cylinder group.
   1267         1.1   mycroft  *
   1268         1.1   mycroft  * This algorithm implements the following policy:
   1269         1.1   mycroft  *   1) allocate the requested block.
   1270         1.1   mycroft  *   2) allocate a rotationally optimal block in the same cylinder.
   1271         1.1   mycroft  *   3) allocate the next available block on the block rotor for the
   1272         1.1   mycroft  *      specified cylinder group.
   1273         1.1   mycroft  * Note that this routine only allocates fs_bsize blocks; these
   1274         1.1   mycroft  * blocks may be fragmented by the routine that allocates them.
   1275         1.1   mycroft  */
   1276        1.58      fvdl static daddr_t
   1277        1.85   thorpej ffs_alloccgblk(struct inode *ip, struct buf *bp, daddr_t bpref)
   1278         1.1   mycroft {
   1279       1.101        ad 	struct ufsmount *ump;
   1280        1.62      fvdl 	struct fs *fs = ip->i_fs;
   1281        1.30      fvdl 	struct cg *cgp;
   1282        1.60      fvdl 	daddr_t blkno;
   1283        1.60      fvdl 	int32_t bno;
   1284        1.60      fvdl 	u_int8_t *blksfree;
   1285        1.30      fvdl #ifdef FFS_EI
   1286        1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   1287        1.30      fvdl #endif
   1288         1.1   mycroft 
   1289       1.101        ad 	ump = ip->i_ump;
   1290       1.101        ad 
   1291       1.101        ad 	KASSERT(mutex_owned(&ump->um_lock));
   1292       1.101        ad 
   1293        1.30      fvdl 	cgp = (struct cg *)bp->b_data;
   1294        1.60      fvdl 	blksfree = cg_blksfree(cgp, needswap);
   1295        1.30      fvdl 	if (bpref == 0 || dtog(fs, bpref) != ufs_rw32(cgp->cg_cgx, needswap)) {
   1296        1.19    bouyer 		bpref = ufs_rw32(cgp->cg_rotor, needswap);
   1297        1.60      fvdl 	} else {
   1298        1.60      fvdl 		bpref = blknum(fs, bpref);
   1299        1.60      fvdl 		bno = dtogd(fs, bpref);
   1300         1.1   mycroft 		/*
   1301        1.60      fvdl 		 * if the requested block is available, use it
   1302         1.1   mycroft 		 */
   1303        1.60      fvdl 		if (ffs_isblock(fs, blksfree, fragstoblks(fs, bno)))
   1304        1.60      fvdl 			goto gotit;
   1305         1.1   mycroft 	}
   1306         1.1   mycroft 	/*
   1307        1.60      fvdl 	 * Take the next available block in this cylinder group.
   1308         1.1   mycroft 	 */
   1309        1.30      fvdl 	bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag);
   1310         1.1   mycroft 	if (bno < 0)
   1311        1.35   thorpej 		return (0);
   1312        1.60      fvdl 	cgp->cg_rotor = ufs_rw32(bno, needswap);
   1313         1.1   mycroft gotit:
   1314         1.1   mycroft 	blkno = fragstoblks(fs, bno);
   1315        1.60      fvdl 	ffs_clrblock(fs, blksfree, blkno);
   1316        1.30      fvdl 	ffs_clusteracct(fs, cgp, blkno, -1);
   1317        1.19    bouyer 	ufs_add32(cgp->cg_cs.cs_nbfree, -1, needswap);
   1318         1.1   mycroft 	fs->fs_cstotal.cs_nbfree--;
   1319        1.19    bouyer 	fs->fs_cs(fs, ufs_rw32(cgp->cg_cgx, needswap)).cs_nbfree--;
   1320        1.73       dbj 	if ((fs->fs_magic == FS_UFS1_MAGIC) &&
   1321        1.73       dbj 	    ((fs->fs_old_flags & FS_FLAGS_UPDATED) == 0)) {
   1322        1.73       dbj 		int cylno;
   1323        1.73       dbj 		cylno = old_cbtocylno(fs, bno);
   1324        1.75       dbj 		KASSERT(cylno >= 0);
   1325        1.75       dbj 		KASSERT(cylno < fs->fs_old_ncyl);
   1326        1.75       dbj 		KASSERT(old_cbtorpos(fs, bno) >= 0);
   1327        1.75       dbj 		KASSERT(fs->fs_old_nrpos == 0 || old_cbtorpos(fs, bno) < fs->fs_old_nrpos);
   1328        1.73       dbj 		ufs_add16(old_cg_blks(fs, cgp, cylno, needswap)[old_cbtorpos(fs, bno)], -1,
   1329        1.73       dbj 		    needswap);
   1330        1.73       dbj 		ufs_add32(old_cg_blktot(cgp, needswap)[cylno], -1, needswap);
   1331        1.73       dbj 	}
   1332         1.1   mycroft 	fs->fs_fmod = 1;
   1333        1.30      fvdl 	blkno = ufs_rw32(cgp->cg_cgx, needswap) * fs->fs_fpg + bno;
   1334       1.101        ad 	if (DOINGSOFTDEP(ITOV(ip))) {
   1335       1.101        ad 		mutex_exit(&ump->um_lock);
   1336        1.30      fvdl 		softdep_setup_blkmapdep(bp, fs, blkno);
   1337       1.101        ad 		mutex_enter(&ump->um_lock);
   1338       1.101        ad 	}
   1339        1.30      fvdl 	return (blkno);
   1340         1.1   mycroft }
   1341         1.1   mycroft 
   1342        1.55      matt #ifdef XXXUBC
   1343         1.1   mycroft /*
   1344         1.1   mycroft  * Determine whether a cluster can be allocated.
   1345         1.1   mycroft  *
   1346         1.1   mycroft  * We do not currently check for optimal rotational layout if there
   1347         1.1   mycroft  * are multiple choices in the same cylinder group. Instead we just
   1348         1.1   mycroft  * take the first one that we find following bpref.
   1349         1.1   mycroft  */
   1350        1.60      fvdl 
   1351        1.60      fvdl /*
   1352        1.60      fvdl  * This function must be fixed for UFS2 if re-enabled.
   1353        1.60      fvdl  */
   1354        1.58      fvdl static daddr_t
   1355        1.85   thorpej ffs_clusteralloc(struct inode *ip, int cg, daddr_t bpref, int len)
   1356         1.1   mycroft {
   1357       1.101        ad 	struct ufsmount *ump;
   1358        1.33  augustss 	struct fs *fs;
   1359        1.33  augustss 	struct cg *cgp;
   1360         1.1   mycroft 	struct buf *bp;
   1361        1.18      fvdl 	int i, got, run, bno, bit, map;
   1362         1.1   mycroft 	u_char *mapp;
   1363         1.5   mycroft 	int32_t *lp;
   1364         1.1   mycroft 
   1365         1.1   mycroft 	fs = ip->i_fs;
   1366       1.101        ad 	ump = ip->i_ump;
   1367       1.101        ad 
   1368       1.101        ad 	KASSERT(mutex_owned(&ump->um_lock));
   1369         1.5   mycroft 	if (fs->fs_maxcluster[cg] < len)
   1370        1.35   thorpej 		return (0);
   1371       1.101        ad 	mutex_exit(&ump->um_lock);
   1372         1.1   mycroft 	if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize,
   1373  1.106.10.1      yamt 	    NOCRED, 0, &bp))
   1374         1.1   mycroft 		goto fail;
   1375         1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1376        1.30      fvdl 	if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs)))
   1377         1.1   mycroft 		goto fail;
   1378         1.1   mycroft 	/*
   1379         1.1   mycroft 	 * Check to see if a cluster of the needed size (or bigger) is
   1380         1.1   mycroft 	 * available in this cylinder group.
   1381         1.1   mycroft 	 */
   1382        1.30      fvdl 	lp = &cg_clustersum(cgp, UFS_FSNEEDSWAP(fs))[len];
   1383         1.1   mycroft 	for (i = len; i <= fs->fs_contigsumsize; i++)
   1384        1.30      fvdl 		if (ufs_rw32(*lp++, UFS_FSNEEDSWAP(fs)) > 0)
   1385         1.1   mycroft 			break;
   1386         1.5   mycroft 	if (i > fs->fs_contigsumsize) {
   1387         1.5   mycroft 		/*
   1388         1.5   mycroft 		 * This is the first time looking for a cluster in this
   1389         1.5   mycroft 		 * cylinder group. Update the cluster summary information
   1390         1.5   mycroft 		 * to reflect the true maximum sized cluster so that
   1391         1.5   mycroft 		 * future cluster allocation requests can avoid reading
   1392         1.5   mycroft 		 * the cylinder group map only to find no clusters.
   1393         1.5   mycroft 		 */
   1394        1.30      fvdl 		lp = &cg_clustersum(cgp, UFS_FSNEEDSWAP(fs))[len - 1];
   1395         1.5   mycroft 		for (i = len - 1; i > 0; i--)
   1396        1.30      fvdl 			if (ufs_rw32(*lp--, UFS_FSNEEDSWAP(fs)) > 0)
   1397         1.5   mycroft 				break;
   1398       1.101        ad 		mutex_enter(&ump->um_lock);
   1399         1.5   mycroft 		fs->fs_maxcluster[cg] = i;
   1400       1.101        ad 		mutex_exit(&ump->um_lock);
   1401         1.1   mycroft 		goto fail;
   1402         1.5   mycroft 	}
   1403         1.1   mycroft 	/*
   1404         1.1   mycroft 	 * Search the cluster map to find a big enough cluster.
   1405         1.1   mycroft 	 * We take the first one that we find, even if it is larger
   1406         1.1   mycroft 	 * than we need as we prefer to get one close to the previous
   1407         1.1   mycroft 	 * block allocation. We do not search before the current
   1408         1.1   mycroft 	 * preference point as we do not want to allocate a block
   1409         1.1   mycroft 	 * that is allocated before the previous one (as we will
   1410         1.1   mycroft 	 * then have to wait for another pass of the elevator
   1411         1.1   mycroft 	 * algorithm before it will be read). We prefer to fail and
   1412         1.1   mycroft 	 * be recalled to try an allocation in the next cylinder group.
   1413         1.1   mycroft 	 */
   1414         1.1   mycroft 	if (dtog(fs, bpref) != cg)
   1415         1.1   mycroft 		bpref = 0;
   1416         1.1   mycroft 	else
   1417         1.1   mycroft 		bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref)));
   1418        1.30      fvdl 	mapp = &cg_clustersfree(cgp, UFS_FSNEEDSWAP(fs))[bpref / NBBY];
   1419         1.1   mycroft 	map = *mapp++;
   1420         1.1   mycroft 	bit = 1 << (bpref % NBBY);
   1421        1.19    bouyer 	for (run = 0, got = bpref;
   1422        1.30      fvdl 		got < ufs_rw32(cgp->cg_nclusterblks, UFS_FSNEEDSWAP(fs)); got++) {
   1423         1.1   mycroft 		if ((map & bit) == 0) {
   1424         1.1   mycroft 			run = 0;
   1425         1.1   mycroft 		} else {
   1426         1.1   mycroft 			run++;
   1427         1.1   mycroft 			if (run == len)
   1428         1.1   mycroft 				break;
   1429         1.1   mycroft 		}
   1430        1.18      fvdl 		if ((got & (NBBY - 1)) != (NBBY - 1)) {
   1431         1.1   mycroft 			bit <<= 1;
   1432         1.1   mycroft 		} else {
   1433         1.1   mycroft 			map = *mapp++;
   1434         1.1   mycroft 			bit = 1;
   1435         1.1   mycroft 		}
   1436         1.1   mycroft 	}
   1437        1.30      fvdl 	if (got == ufs_rw32(cgp->cg_nclusterblks, UFS_FSNEEDSWAP(fs)))
   1438         1.1   mycroft 		goto fail;
   1439         1.1   mycroft 	/*
   1440         1.1   mycroft 	 * Allocate the cluster that we have found.
   1441         1.1   mycroft 	 */
   1442        1.30      fvdl #ifdef DIAGNOSTIC
   1443        1.18      fvdl 	for (i = 1; i <= len; i++)
   1444        1.30      fvdl 		if (!ffs_isblock(fs, cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)),
   1445        1.30      fvdl 		    got - run + i))
   1446        1.18      fvdl 			panic("ffs_clusteralloc: map mismatch");
   1447        1.30      fvdl #endif
   1448        1.18      fvdl 	bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1);
   1449        1.18      fvdl 	if (dtog(fs, bno) != cg)
   1450        1.18      fvdl 		panic("ffs_clusteralloc: allocated out of group");
   1451         1.1   mycroft 	len = blkstofrags(fs, len);
   1452       1.101        ad 	mutex_enter(&ump->um_lock);
   1453         1.1   mycroft 	for (i = 0; i < len; i += fs->fs_frag)
   1454        1.30      fvdl 		if ((got = ffs_alloccgblk(ip, bp, bno + i)) != bno + i)
   1455         1.1   mycroft 			panic("ffs_clusteralloc: lost block");
   1456        1.76   hannken 	ACTIVECG_CLR(fs, cg);
   1457       1.101        ad 	mutex_exit(&ump->um_lock);
   1458         1.8       cgd 	bdwrite(bp);
   1459         1.1   mycroft 	return (bno);
   1460         1.1   mycroft 
   1461         1.1   mycroft fail:
   1462       1.101        ad 	brelse(bp, 0);
   1463       1.101        ad 	mutex_enter(&ump->um_lock);
   1464         1.1   mycroft 	return (0);
   1465         1.1   mycroft }
   1466        1.55      matt #endif /* XXXUBC */
   1467         1.1   mycroft 
   1468         1.1   mycroft /*
   1469         1.1   mycroft  * Determine whether an inode can be allocated.
   1470         1.1   mycroft  *
   1471         1.1   mycroft  * Check to see if an inode is available, and if it is,
   1472         1.1   mycroft  * allocate it using the following policy:
   1473         1.1   mycroft  *   1) allocate the requested inode.
   1474         1.1   mycroft  *   2) allocate the next available inode after the requested
   1475         1.1   mycroft  *      inode in the specified cylinder group.
   1476         1.1   mycroft  */
   1477        1.58      fvdl static daddr_t
   1478        1.85   thorpej ffs_nodealloccg(struct inode *ip, int cg, daddr_t ipref, int mode)
   1479         1.1   mycroft {
   1480       1.101        ad 	struct ufsmount *ump = ip->i_ump;
   1481        1.62      fvdl 	struct fs *fs = ip->i_fs;
   1482        1.33  augustss 	struct cg *cgp;
   1483        1.60      fvdl 	struct buf *bp, *ibp;
   1484        1.60      fvdl 	u_int8_t *inosused;
   1485         1.1   mycroft 	int error, start, len, loc, map, i;
   1486        1.60      fvdl 	int32_t initediblk;
   1487        1.60      fvdl 	struct ufs2_dinode *dp2;
   1488        1.19    bouyer #ifdef FFS_EI
   1489        1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   1490        1.19    bouyer #endif
   1491         1.1   mycroft 
   1492       1.101        ad 	KASSERT(mutex_owned(&ump->um_lock));
   1493       1.101        ad 
   1494         1.1   mycroft 	if (fs->fs_cs(fs, cg).cs_nifree == 0)
   1495        1.35   thorpej 		return (0);
   1496       1.101        ad 	mutex_exit(&ump->um_lock);
   1497         1.1   mycroft 	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)),
   1498  1.106.10.1      yamt 		(int)fs->fs_cgsize, NOCRED, B_MODIFY, &bp);
   1499       1.101        ad 	if (error)
   1500       1.101        ad 		goto fail;
   1501         1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1502       1.101        ad 	if (!cg_chkmagic(cgp, needswap) || cgp->cg_cs.cs_nifree == 0)
   1503       1.101        ad 		goto fail;
   1504        1.92    kardel 	cgp->cg_old_time = ufs_rw32(time_second, needswap);
   1505        1.73       dbj 	if ((fs->fs_magic != FS_UFS1_MAGIC) ||
   1506        1.73       dbj 	    (fs->fs_old_flags & FS_FLAGS_UPDATED))
   1507        1.92    kardel 		cgp->cg_time = ufs_rw64(time_second, needswap);
   1508        1.60      fvdl 	inosused = cg_inosused(cgp, needswap);
   1509         1.1   mycroft 	if (ipref) {
   1510         1.1   mycroft 		ipref %= fs->fs_ipg;
   1511        1.60      fvdl 		if (isclr(inosused, ipref))
   1512         1.1   mycroft 			goto gotit;
   1513         1.1   mycroft 	}
   1514        1.19    bouyer 	start = ufs_rw32(cgp->cg_irotor, needswap) / NBBY;
   1515        1.19    bouyer 	len = howmany(fs->fs_ipg - ufs_rw32(cgp->cg_irotor, needswap),
   1516        1.19    bouyer 		NBBY);
   1517        1.60      fvdl 	loc = skpc(0xff, len, &inosused[start]);
   1518         1.1   mycroft 	if (loc == 0) {
   1519         1.1   mycroft 		len = start + 1;
   1520         1.1   mycroft 		start = 0;
   1521        1.60      fvdl 		loc = skpc(0xff, len, &inosused[0]);
   1522         1.1   mycroft 		if (loc == 0) {
   1523        1.13  christos 			printf("cg = %d, irotor = %d, fs = %s\n",
   1524        1.19    bouyer 			    cg, ufs_rw32(cgp->cg_irotor, needswap),
   1525        1.19    bouyer 				fs->fs_fsmnt);
   1526         1.1   mycroft 			panic("ffs_nodealloccg: map corrupted");
   1527         1.1   mycroft 			/* NOTREACHED */
   1528         1.1   mycroft 		}
   1529         1.1   mycroft 	}
   1530         1.1   mycroft 	i = start + len - loc;
   1531        1.60      fvdl 	map = inosused[i];
   1532         1.1   mycroft 	ipref = i * NBBY;
   1533         1.1   mycroft 	for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) {
   1534         1.1   mycroft 		if ((map & i) == 0) {
   1535        1.19    bouyer 			cgp->cg_irotor = ufs_rw32(ipref, needswap);
   1536         1.1   mycroft 			goto gotit;
   1537         1.1   mycroft 		}
   1538         1.1   mycroft 	}
   1539        1.13  christos 	printf("fs = %s\n", fs->fs_fsmnt);
   1540         1.1   mycroft 	panic("ffs_nodealloccg: block not in map");
   1541         1.1   mycroft 	/* NOTREACHED */
   1542         1.1   mycroft gotit:
   1543        1.60      fvdl 	/*
   1544        1.60      fvdl 	 * Check to see if we need to initialize more inodes.
   1545        1.60      fvdl 	 */
   1546        1.60      fvdl 	initediblk = ufs_rw32(cgp->cg_initediblk, needswap);
   1547       1.104   hannken 	ibp = NULL;
   1548        1.60      fvdl 	if (fs->fs_magic == FS_UFS2_MAGIC &&
   1549        1.60      fvdl 	    ipref + INOPB(fs) > initediblk &&
   1550        1.60      fvdl 	    initediblk < ufs_rw32(cgp->cg_niblk, needswap)) {
   1551  1.106.10.2      yamt 		if (ffs_getblk(ip->i_devvp, fsbtodb(fs,
   1552        1.60      fvdl 		    ino_to_fsba(fs, cg * fs->fs_ipg + initediblk)),
   1553  1.106.10.2      yamt 		    FFS_NOBLK, fs->fs_bsize, false, &ibp) != 0)
   1554  1.106.10.2      yamt 			goto fail;
   1555  1.106.10.2      yamt 		memset(ibp->b_data, 0, fs->fs_bsize);
   1556  1.106.10.2      yamt 		dp2 = (struct ufs2_dinode *)(ibp->b_data);
   1557  1.106.10.2      yamt 		for (i = 0; i < INOPB(fs); i++) {
   1558        1.60      fvdl 			/*
   1559        1.60      fvdl 			 * Don't bother to swap, it's supposed to be
   1560        1.60      fvdl 			 * random, after all.
   1561        1.60      fvdl 			 */
   1562        1.70    itojun 			dp2->di_gen = (arc4random() & INT32_MAX) / 2 + 1;
   1563        1.60      fvdl 			dp2++;
   1564        1.60      fvdl 		}
   1565        1.60      fvdl 		initediblk += INOPB(fs);
   1566        1.60      fvdl 		cgp->cg_initediblk = ufs_rw32(initediblk, needswap);
   1567        1.60      fvdl 	}
   1568        1.60      fvdl 
   1569       1.101        ad 	mutex_enter(&ump->um_lock);
   1570        1.76   hannken 	ACTIVECG_CLR(fs, cg);
   1571       1.101        ad 	setbit(inosused, ipref);
   1572       1.101        ad 	ufs_add32(cgp->cg_cs.cs_nifree, -1, needswap);
   1573       1.101        ad 	fs->fs_cstotal.cs_nifree--;
   1574       1.101        ad 	fs->fs_cs(fs, cg).cs_nifree--;
   1575       1.101        ad 	fs->fs_fmod = 1;
   1576       1.101        ad 	if ((mode & IFMT) == IFDIR) {
   1577       1.101        ad 		ufs_add32(cgp->cg_cs.cs_ndir, 1, needswap);
   1578       1.101        ad 		fs->fs_cstotal.cs_ndir++;
   1579       1.101        ad 		fs->fs_cs(fs, cg).cs_ndir++;
   1580       1.101        ad 	}
   1581       1.101        ad 	mutex_exit(&ump->um_lock);
   1582       1.101        ad 	if (DOINGSOFTDEP(ITOV(ip)))
   1583       1.101        ad 		softdep_setup_inomapdep(bp, ip, cg * fs->fs_ipg + ipref);
   1584         1.1   mycroft 	bdwrite(bp);
   1585       1.104   hannken 	if (ibp != NULL)
   1586       1.104   hannken 		bawrite(ibp);
   1587         1.1   mycroft 	return (cg * fs->fs_ipg + ipref);
   1588       1.101        ad  fail:
   1589       1.101        ad 	brelse(bp, 0);
   1590       1.101        ad 	mutex_enter(&ump->um_lock);
   1591       1.101        ad 	return (0);
   1592         1.1   mycroft }
   1593         1.1   mycroft 
   1594         1.1   mycroft /*
   1595         1.1   mycroft  * Free a block or fragment.
   1596         1.1   mycroft  *
   1597         1.1   mycroft  * The specified block or fragment is placed back in the
   1598        1.81     perry  * free map. If a fragment is deallocated, a possible
   1599         1.1   mycroft  * block reassembly is checked.
   1600       1.106     pooka  *
   1601       1.106     pooka  * => um_lock not held on entry or exit
   1602         1.1   mycroft  */
   1603         1.9  christos void
   1604        1.85   thorpej ffs_blkfree(struct fs *fs, struct vnode *devvp, daddr_t bno, long size,
   1605        1.85   thorpej     ino_t inum)
   1606         1.1   mycroft {
   1607        1.33  augustss 	struct cg *cgp;
   1608         1.1   mycroft 	struct buf *bp;
   1609        1.76   hannken 	struct ufsmount *ump;
   1610        1.60      fvdl 	int32_t fragno, cgbno;
   1611        1.76   hannken 	daddr_t cgblkno;
   1612         1.1   mycroft 	int i, error, cg, blk, frags, bbase;
   1613        1.62      fvdl 	u_int8_t *blksfree;
   1614        1.76   hannken 	dev_t dev;
   1615        1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   1616         1.1   mycroft 
   1617        1.76   hannken 	cg = dtog(fs, bno);
   1618        1.77   hannken 	if (devvp->v_type != VBLK) {
   1619        1.77   hannken 		/* devvp is a snapshot */
   1620        1.76   hannken 		dev = VTOI(devvp)->i_devvp->v_rdev;
   1621       1.103   hannken 		ump = VFSTOUFS(devvp->v_mount);
   1622        1.76   hannken 		cgblkno = fragstoblks(fs, cgtod(fs, cg));
   1623        1.76   hannken 	} else {
   1624        1.76   hannken 		dev = devvp->v_rdev;
   1625       1.103   hannken 		ump = VFSTOUFS(devvp->v_specmountpoint);
   1626        1.76   hannken 		cgblkno = fsbtodb(fs, cgtod(fs, cg));
   1627       1.100   hannken 		if (ffs_snapblkfree(fs, devvp, bno, size, inum))
   1628        1.76   hannken 			return;
   1629        1.76   hannken 	}
   1630        1.30      fvdl 	if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0 ||
   1631        1.30      fvdl 	    fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) {
   1632        1.59   tsutsui 		printf("dev = 0x%x, bno = %" PRId64 " bsize = %d, "
   1633        1.58      fvdl 		       "size = %ld, fs = %s\n",
   1634        1.76   hannken 		    dev, bno, fs->fs_bsize, size, fs->fs_fsmnt);
   1635         1.1   mycroft 		panic("blkfree: bad size");
   1636         1.1   mycroft 	}
   1637        1.76   hannken 
   1638        1.60      fvdl 	if (bno >= fs->fs_size) {
   1639        1.86  christos 		printf("bad block %" PRId64 ", ino %llu\n", bno,
   1640        1.86  christos 		    (unsigned long long)inum);
   1641        1.76   hannken 		ffs_fserr(fs, inum, "bad block");
   1642         1.1   mycroft 		return;
   1643         1.1   mycroft 	}
   1644  1.106.10.1      yamt 	error = bread(devvp, cgblkno, (int)fs->fs_cgsize,
   1645  1.106.10.1      yamt 	    NOCRED, B_MODIFY, &bp);
   1646         1.1   mycroft 	if (error) {
   1647       1.101        ad 		brelse(bp, 0);
   1648         1.1   mycroft 		return;
   1649         1.1   mycroft 	}
   1650         1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1651        1.19    bouyer 	if (!cg_chkmagic(cgp, needswap)) {
   1652       1.101        ad 		brelse(bp, 0);
   1653         1.1   mycroft 		return;
   1654         1.1   mycroft 	}
   1655        1.92    kardel 	cgp->cg_old_time = ufs_rw32(time_second, needswap);
   1656        1.73       dbj 	if ((fs->fs_magic != FS_UFS1_MAGIC) ||
   1657        1.73       dbj 	    (fs->fs_old_flags & FS_FLAGS_UPDATED))
   1658        1.92    kardel 		cgp->cg_time = ufs_rw64(time_second, needswap);
   1659        1.60      fvdl 	cgbno = dtogd(fs, bno);
   1660        1.62      fvdl 	blksfree = cg_blksfree(cgp, needswap);
   1661       1.101        ad 	mutex_enter(&ump->um_lock);
   1662         1.1   mycroft 	if (size == fs->fs_bsize) {
   1663        1.60      fvdl 		fragno = fragstoblks(fs, cgbno);
   1664        1.62      fvdl 		if (!ffs_isfreeblock(fs, blksfree, fragno)) {
   1665        1.77   hannken 			if (devvp->v_type != VBLK) {
   1666        1.77   hannken 				/* devvp is a snapshot */
   1667       1.101        ad 				mutex_exit(&ump->um_lock);
   1668       1.101        ad 				brelse(bp, 0);
   1669        1.76   hannken 				return;
   1670        1.76   hannken 			}
   1671        1.59   tsutsui 			printf("dev = 0x%x, block = %" PRId64 ", fs = %s\n",
   1672        1.76   hannken 			    dev, bno, fs->fs_fsmnt);
   1673         1.1   mycroft 			panic("blkfree: freeing free block");
   1674         1.1   mycroft 		}
   1675        1.62      fvdl 		ffs_setblock(fs, blksfree, fragno);
   1676        1.60      fvdl 		ffs_clusteracct(fs, cgp, fragno, 1);
   1677        1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_nbfree, 1, needswap);
   1678         1.1   mycroft 		fs->fs_cstotal.cs_nbfree++;
   1679         1.1   mycroft 		fs->fs_cs(fs, cg).cs_nbfree++;
   1680        1.73       dbj 		if ((fs->fs_magic == FS_UFS1_MAGIC) &&
   1681        1.73       dbj 		    ((fs->fs_old_flags & FS_FLAGS_UPDATED) == 0)) {
   1682        1.73       dbj 			i = old_cbtocylno(fs, cgbno);
   1683        1.75       dbj 			KASSERT(i >= 0);
   1684        1.75       dbj 			KASSERT(i < fs->fs_old_ncyl);
   1685        1.75       dbj 			KASSERT(old_cbtorpos(fs, cgbno) >= 0);
   1686        1.75       dbj 			KASSERT(fs->fs_old_nrpos == 0 || old_cbtorpos(fs, cgbno) < fs->fs_old_nrpos);
   1687        1.73       dbj 			ufs_add16(old_cg_blks(fs, cgp, i, needswap)[old_cbtorpos(fs, cgbno)], 1,
   1688        1.73       dbj 			    needswap);
   1689        1.73       dbj 			ufs_add32(old_cg_blktot(cgp, needswap)[i], 1, needswap);
   1690        1.73       dbj 		}
   1691         1.1   mycroft 	} else {
   1692        1.60      fvdl 		bbase = cgbno - fragnum(fs, cgbno);
   1693         1.1   mycroft 		/*
   1694         1.1   mycroft 		 * decrement the counts associated with the old frags
   1695         1.1   mycroft 		 */
   1696        1.62      fvdl 		blk = blkmap(fs, blksfree, bbase);
   1697        1.19    bouyer 		ffs_fragacct(fs, blk, cgp->cg_frsum, -1, needswap);
   1698         1.1   mycroft 		/*
   1699         1.1   mycroft 		 * deallocate the fragment
   1700         1.1   mycroft 		 */
   1701         1.1   mycroft 		frags = numfrags(fs, size);
   1702         1.1   mycroft 		for (i = 0; i < frags; i++) {
   1703        1.62      fvdl 			if (isset(blksfree, cgbno + i)) {
   1704        1.59   tsutsui 				printf("dev = 0x%x, block = %" PRId64
   1705        1.59   tsutsui 				       ", fs = %s\n",
   1706        1.76   hannken 				    dev, bno + i, fs->fs_fsmnt);
   1707         1.1   mycroft 				panic("blkfree: freeing free frag");
   1708         1.1   mycroft 			}
   1709        1.62      fvdl 			setbit(blksfree, cgbno + i);
   1710         1.1   mycroft 		}
   1711        1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_nffree, i, needswap);
   1712         1.1   mycroft 		fs->fs_cstotal.cs_nffree += i;
   1713        1.30      fvdl 		fs->fs_cs(fs, cg).cs_nffree += i;
   1714         1.1   mycroft 		/*
   1715         1.1   mycroft 		 * add back in counts associated with the new frags
   1716         1.1   mycroft 		 */
   1717        1.62      fvdl 		blk = blkmap(fs, blksfree, bbase);
   1718        1.19    bouyer 		ffs_fragacct(fs, blk, cgp->cg_frsum, 1, needswap);
   1719         1.1   mycroft 		/*
   1720         1.1   mycroft 		 * if a complete block has been reassembled, account for it
   1721         1.1   mycroft 		 */
   1722        1.60      fvdl 		fragno = fragstoblks(fs, bbase);
   1723        1.62      fvdl 		if (ffs_isblock(fs, blksfree, fragno)) {
   1724        1.19    bouyer 			ufs_add32(cgp->cg_cs.cs_nffree, -fs->fs_frag, needswap);
   1725         1.1   mycroft 			fs->fs_cstotal.cs_nffree -= fs->fs_frag;
   1726         1.1   mycroft 			fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag;
   1727        1.60      fvdl 			ffs_clusteracct(fs, cgp, fragno, 1);
   1728        1.19    bouyer 			ufs_add32(cgp->cg_cs.cs_nbfree, 1, needswap);
   1729         1.1   mycroft 			fs->fs_cstotal.cs_nbfree++;
   1730         1.1   mycroft 			fs->fs_cs(fs, cg).cs_nbfree++;
   1731        1.73       dbj 			if ((fs->fs_magic == FS_UFS1_MAGIC) &&
   1732        1.73       dbj 			    ((fs->fs_old_flags & FS_FLAGS_UPDATED) == 0)) {
   1733        1.73       dbj 				i = old_cbtocylno(fs, bbase);
   1734        1.75       dbj 				KASSERT(i >= 0);
   1735        1.75       dbj 				KASSERT(i < fs->fs_old_ncyl);
   1736        1.75       dbj 				KASSERT(old_cbtorpos(fs, bbase) >= 0);
   1737        1.75       dbj 				KASSERT(fs->fs_old_nrpos == 0 || old_cbtorpos(fs, bbase) < fs->fs_old_nrpos);
   1738        1.73       dbj 				ufs_add16(old_cg_blks(fs, cgp, i, needswap)[old_cbtorpos(fs,
   1739        1.73       dbj 				    bbase)], 1, needswap);
   1740        1.73       dbj 				ufs_add32(old_cg_blktot(cgp, needswap)[i], 1, needswap);
   1741        1.73       dbj 			}
   1742         1.1   mycroft 		}
   1743         1.1   mycroft 	}
   1744         1.1   mycroft 	fs->fs_fmod = 1;
   1745        1.76   hannken 	ACTIVECG_CLR(fs, cg);
   1746       1.101        ad 	mutex_exit(&ump->um_lock);
   1747         1.1   mycroft 	bdwrite(bp);
   1748         1.1   mycroft }
   1749         1.1   mycroft 
   1750        1.18      fvdl #if defined(DIAGNOSTIC) || defined(DEBUG)
   1751        1.55      matt #ifdef XXXUBC
   1752        1.18      fvdl /*
   1753        1.18      fvdl  * Verify allocation of a block or fragment. Returns true if block or
   1754        1.18      fvdl  * fragment is allocated, false if it is free.
   1755        1.18      fvdl  */
   1756        1.18      fvdl static int
   1757        1.85   thorpej ffs_checkblk(struct inode *ip, daddr_t bno, long size)
   1758        1.18      fvdl {
   1759        1.18      fvdl 	struct fs *fs;
   1760        1.18      fvdl 	struct cg *cgp;
   1761        1.18      fvdl 	struct buf *bp;
   1762        1.18      fvdl 	int i, error, frags, free;
   1763        1.18      fvdl 
   1764        1.18      fvdl 	fs = ip->i_fs;
   1765        1.18      fvdl 	if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) {
   1766        1.18      fvdl 		printf("bsize = %d, size = %ld, fs = %s\n",
   1767        1.18      fvdl 		    fs->fs_bsize, size, fs->fs_fsmnt);
   1768        1.18      fvdl 		panic("checkblk: bad size");
   1769        1.18      fvdl 	}
   1770        1.60      fvdl 	if (bno >= fs->fs_size)
   1771        1.18      fvdl 		panic("checkblk: bad block %d", bno);
   1772        1.18      fvdl 	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))),
   1773  1.106.10.1      yamt 		(int)fs->fs_cgsize, NOCRED, 0, &bp);
   1774        1.18      fvdl 	if (error) {
   1775       1.101        ad 		brelse(bp, 0);
   1776        1.18      fvdl 		return 0;
   1777        1.18      fvdl 	}
   1778        1.18      fvdl 	cgp = (struct cg *)bp->b_data;
   1779        1.30      fvdl 	if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs))) {
   1780       1.101        ad 		brelse(bp, 0);
   1781        1.18      fvdl 		return 0;
   1782        1.18      fvdl 	}
   1783        1.18      fvdl 	bno = dtogd(fs, bno);
   1784        1.18      fvdl 	if (size == fs->fs_bsize) {
   1785        1.30      fvdl 		free = ffs_isblock(fs, cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)),
   1786        1.19    bouyer 			fragstoblks(fs, bno));
   1787        1.18      fvdl 	} else {
   1788        1.18      fvdl 		frags = numfrags(fs, size);
   1789        1.18      fvdl 		for (free = 0, i = 0; i < frags; i++)
   1790        1.30      fvdl 			if (isset(cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)), bno + i))
   1791        1.18      fvdl 				free++;
   1792        1.18      fvdl 		if (free != 0 && free != frags)
   1793        1.18      fvdl 			panic("checkblk: partially free fragment");
   1794        1.18      fvdl 	}
   1795       1.101        ad 	brelse(bp, 0);
   1796        1.18      fvdl 	return (!free);
   1797        1.18      fvdl }
   1798        1.55      matt #endif /* XXXUBC */
   1799        1.18      fvdl #endif /* DIAGNOSTIC */
   1800        1.18      fvdl 
   1801         1.1   mycroft /*
   1802         1.1   mycroft  * Free an inode.
   1803        1.30      fvdl  */
   1804        1.30      fvdl int
   1805        1.88      yamt ffs_vfree(struct vnode *vp, ino_t ino, int mode)
   1806        1.30      fvdl {
   1807        1.30      fvdl 
   1808        1.88      yamt 	if (DOINGSOFTDEP(vp)) {
   1809        1.88      yamt 		softdep_freefile(vp, ino, mode);
   1810        1.30      fvdl 		return (0);
   1811        1.30      fvdl 	}
   1812        1.88      yamt 	return ffs_freefile(VTOI(vp)->i_fs, VTOI(vp)->i_devvp, ino, mode);
   1813        1.30      fvdl }
   1814        1.30      fvdl 
   1815        1.30      fvdl /*
   1816        1.30      fvdl  * Do the actual free operation.
   1817         1.1   mycroft  * The specified inode is placed back in the free map.
   1818         1.1   mycroft  */
   1819         1.1   mycroft int
   1820        1.85   thorpej ffs_freefile(struct fs *fs, struct vnode *devvp, ino_t ino, int mode)
   1821         1.9  christos {
   1822       1.101        ad 	struct ufsmount *ump;
   1823        1.33  augustss 	struct cg *cgp;
   1824         1.1   mycroft 	struct buf *bp;
   1825         1.1   mycroft 	int error, cg;
   1826        1.76   hannken 	daddr_t cgbno;
   1827        1.62      fvdl 	u_int8_t *inosused;
   1828        1.78   hannken 	dev_t dev;
   1829        1.19    bouyer #ifdef FFS_EI
   1830        1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   1831        1.19    bouyer #endif
   1832         1.1   mycroft 
   1833        1.76   hannken 	cg = ino_to_cg(fs, ino);
   1834        1.78   hannken 	if (devvp->v_type != VBLK) {
   1835        1.78   hannken 		/* devvp is a snapshot */
   1836        1.78   hannken 		dev = VTOI(devvp)->i_devvp->v_rdev;
   1837       1.103   hannken 		ump = VFSTOUFS(devvp->v_mount);
   1838        1.76   hannken 		cgbno = fragstoblks(fs, cgtod(fs, cg));
   1839        1.76   hannken 	} else {
   1840        1.78   hannken 		dev = devvp->v_rdev;
   1841       1.103   hannken 		ump = VFSTOUFS(devvp->v_specmountpoint);
   1842        1.76   hannken 		cgbno = fsbtodb(fs, cgtod(fs, cg));
   1843        1.76   hannken 	}
   1844         1.1   mycroft 	if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg)
   1845        1.86  christos 		panic("ifree: range: dev = 0x%x, ino = %llu, fs = %s",
   1846        1.86  christos 		    dev, (unsigned long long)ino, fs->fs_fsmnt);
   1847  1.106.10.1      yamt 	error = bread(devvp, cgbno, (int)fs->fs_cgsize,
   1848  1.106.10.1      yamt 	    NOCRED, B_MODIFY, &bp);
   1849         1.1   mycroft 	if (error) {
   1850       1.101        ad 		brelse(bp, 0);
   1851        1.30      fvdl 		return (error);
   1852         1.1   mycroft 	}
   1853         1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1854        1.19    bouyer 	if (!cg_chkmagic(cgp, needswap)) {
   1855       1.101        ad 		brelse(bp, 0);
   1856         1.1   mycroft 		return (0);
   1857         1.1   mycroft 	}
   1858        1.92    kardel 	cgp->cg_old_time = ufs_rw32(time_second, needswap);
   1859        1.73       dbj 	if ((fs->fs_magic != FS_UFS1_MAGIC) ||
   1860        1.73       dbj 	    (fs->fs_old_flags & FS_FLAGS_UPDATED))
   1861        1.92    kardel 		cgp->cg_time = ufs_rw64(time_second, needswap);
   1862        1.62      fvdl 	inosused = cg_inosused(cgp, needswap);
   1863         1.1   mycroft 	ino %= fs->fs_ipg;
   1864        1.62      fvdl 	if (isclr(inosused, ino)) {
   1865        1.86  christos 		printf("ifree: dev = 0x%x, ino = %llu, fs = %s\n",
   1866        1.86  christos 		    dev, (unsigned long long)ino + cg * fs->fs_ipg,
   1867        1.86  christos 		    fs->fs_fsmnt);
   1868         1.1   mycroft 		if (fs->fs_ronly == 0)
   1869         1.1   mycroft 			panic("ifree: freeing free inode");
   1870         1.1   mycroft 	}
   1871        1.62      fvdl 	clrbit(inosused, ino);
   1872        1.19    bouyer 	if (ino < ufs_rw32(cgp->cg_irotor, needswap))
   1873        1.19    bouyer 		cgp->cg_irotor = ufs_rw32(ino, needswap);
   1874        1.19    bouyer 	ufs_add32(cgp->cg_cs.cs_nifree, 1, needswap);
   1875       1.101        ad 	mutex_enter(&ump->um_lock);
   1876         1.1   mycroft 	fs->fs_cstotal.cs_nifree++;
   1877         1.1   mycroft 	fs->fs_cs(fs, cg).cs_nifree++;
   1878        1.78   hannken 	if ((mode & IFMT) == IFDIR) {
   1879        1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_ndir, -1, needswap);
   1880         1.1   mycroft 		fs->fs_cstotal.cs_ndir--;
   1881         1.1   mycroft 		fs->fs_cs(fs, cg).cs_ndir--;
   1882         1.1   mycroft 	}
   1883         1.1   mycroft 	fs->fs_fmod = 1;
   1884        1.82   hannken 	ACTIVECG_CLR(fs, cg);
   1885       1.101        ad 	mutex_exit(&ump->um_lock);
   1886         1.1   mycroft 	bdwrite(bp);
   1887         1.1   mycroft 	return (0);
   1888         1.1   mycroft }
   1889         1.1   mycroft 
   1890         1.1   mycroft /*
   1891        1.76   hannken  * Check to see if a file is free.
   1892        1.76   hannken  */
   1893        1.76   hannken int
   1894        1.85   thorpej ffs_checkfreefile(struct fs *fs, struct vnode *devvp, ino_t ino)
   1895        1.76   hannken {
   1896        1.76   hannken 	struct cg *cgp;
   1897        1.76   hannken 	struct buf *bp;
   1898        1.76   hannken 	daddr_t cgbno;
   1899        1.76   hannken 	int ret, cg;
   1900        1.76   hannken 	u_int8_t *inosused;
   1901        1.76   hannken 
   1902        1.76   hannken 	cg = ino_to_cg(fs, ino);
   1903        1.77   hannken 	if (devvp->v_type != VBLK) {
   1904        1.77   hannken 		/* devvp is a snapshot */
   1905        1.76   hannken 		cgbno = fragstoblks(fs, cgtod(fs, cg));
   1906        1.77   hannken 	} else
   1907        1.76   hannken 		cgbno = fsbtodb(fs, cgtod(fs, cg));
   1908        1.76   hannken 	if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg)
   1909        1.76   hannken 		return 1;
   1910  1.106.10.1      yamt 	if (bread(devvp, cgbno, (int)fs->fs_cgsize, NOCRED, 0, &bp)) {
   1911       1.101        ad 		brelse(bp, 0);
   1912        1.76   hannken 		return 1;
   1913        1.76   hannken 	}
   1914        1.76   hannken 	cgp = (struct cg *)bp->b_data;
   1915        1.76   hannken 	if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs))) {
   1916       1.101        ad 		brelse(bp, 0);
   1917        1.76   hannken 		return 1;
   1918        1.76   hannken 	}
   1919        1.76   hannken 	inosused = cg_inosused(cgp, UFS_FSNEEDSWAP(fs));
   1920        1.76   hannken 	ino %= fs->fs_ipg;
   1921        1.76   hannken 	ret = isclr(inosused, ino);
   1922       1.101        ad 	brelse(bp, 0);
   1923        1.76   hannken 	return ret;
   1924        1.76   hannken }
   1925        1.76   hannken 
   1926        1.76   hannken /*
   1927         1.1   mycroft  * Find a block of the specified size in the specified cylinder group.
   1928         1.1   mycroft  *
   1929         1.1   mycroft  * It is a panic if a request is made to find a block if none are
   1930         1.1   mycroft  * available.
   1931         1.1   mycroft  */
   1932        1.60      fvdl static int32_t
   1933        1.85   thorpej ffs_mapsearch(struct fs *fs, struct cg *cgp, daddr_t bpref, int allocsiz)
   1934         1.1   mycroft {
   1935        1.60      fvdl 	int32_t bno;
   1936         1.1   mycroft 	int start, len, loc, i;
   1937         1.1   mycroft 	int blk, field, subfield, pos;
   1938        1.19    bouyer 	int ostart, olen;
   1939        1.62      fvdl 	u_int8_t *blksfree;
   1940        1.30      fvdl #ifdef FFS_EI
   1941        1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   1942        1.30      fvdl #endif
   1943         1.1   mycroft 
   1944       1.101        ad 	/* KASSERT(mutex_owned(&ump->um_lock)); */
   1945       1.101        ad 
   1946         1.1   mycroft 	/*
   1947         1.1   mycroft 	 * find the fragment by searching through the free block
   1948         1.1   mycroft 	 * map for an appropriate bit pattern
   1949         1.1   mycroft 	 */
   1950         1.1   mycroft 	if (bpref)
   1951         1.1   mycroft 		start = dtogd(fs, bpref) / NBBY;
   1952         1.1   mycroft 	else
   1953        1.19    bouyer 		start = ufs_rw32(cgp->cg_frotor, needswap) / NBBY;
   1954        1.62      fvdl 	blksfree = cg_blksfree(cgp, needswap);
   1955         1.1   mycroft 	len = howmany(fs->fs_fpg, NBBY) - start;
   1956        1.19    bouyer 	ostart = start;
   1957        1.19    bouyer 	olen = len;
   1958        1.45     lukem 	loc = scanc((u_int)len,
   1959        1.62      fvdl 		(const u_char *)&blksfree[start],
   1960        1.45     lukem 		(const u_char *)fragtbl[fs->fs_frag],
   1961        1.54   mycroft 		(1 << (allocsiz - 1 + (fs->fs_frag & (NBBY - 1)))));
   1962         1.1   mycroft 	if (loc == 0) {
   1963         1.1   mycroft 		len = start + 1;
   1964         1.1   mycroft 		start = 0;
   1965        1.45     lukem 		loc = scanc((u_int)len,
   1966        1.62      fvdl 			(const u_char *)&blksfree[0],
   1967        1.45     lukem 			(const u_char *)fragtbl[fs->fs_frag],
   1968        1.54   mycroft 			(1 << (allocsiz - 1 + (fs->fs_frag & (NBBY - 1)))));
   1969         1.1   mycroft 		if (loc == 0) {
   1970        1.13  christos 			printf("start = %d, len = %d, fs = %s\n",
   1971        1.19    bouyer 			    ostart, olen, fs->fs_fsmnt);
   1972        1.20      ross 			printf("offset=%d %ld\n",
   1973        1.19    bouyer 				ufs_rw32(cgp->cg_freeoff, needswap),
   1974        1.62      fvdl 				(long)blksfree - (long)cgp);
   1975        1.62      fvdl 			printf("cg %d\n", cgp->cg_cgx);
   1976         1.1   mycroft 			panic("ffs_alloccg: map corrupted");
   1977         1.1   mycroft 			/* NOTREACHED */
   1978         1.1   mycroft 		}
   1979         1.1   mycroft 	}
   1980         1.1   mycroft 	bno = (start + len - loc) * NBBY;
   1981        1.19    bouyer 	cgp->cg_frotor = ufs_rw32(bno, needswap);
   1982         1.1   mycroft 	/*
   1983         1.1   mycroft 	 * found the byte in the map
   1984         1.1   mycroft 	 * sift through the bits to find the selected frag
   1985         1.1   mycroft 	 */
   1986         1.1   mycroft 	for (i = bno + NBBY; bno < i; bno += fs->fs_frag) {
   1987        1.62      fvdl 		blk = blkmap(fs, blksfree, bno);
   1988         1.1   mycroft 		blk <<= 1;
   1989         1.1   mycroft 		field = around[allocsiz];
   1990         1.1   mycroft 		subfield = inside[allocsiz];
   1991         1.1   mycroft 		for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) {
   1992         1.1   mycroft 			if ((blk & field) == subfield)
   1993         1.1   mycroft 				return (bno + pos);
   1994         1.1   mycroft 			field <<= 1;
   1995         1.1   mycroft 			subfield <<= 1;
   1996         1.1   mycroft 		}
   1997         1.1   mycroft 	}
   1998        1.60      fvdl 	printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt);
   1999         1.1   mycroft 	panic("ffs_alloccg: block not in map");
   2000        1.58      fvdl 	/* return (-1); */
   2001         1.1   mycroft }
   2002         1.1   mycroft 
   2003         1.1   mycroft /*
   2004         1.1   mycroft  * Update the cluster map because of an allocation or free.
   2005         1.1   mycroft  *
   2006         1.1   mycroft  * Cnt == 1 means free; cnt == -1 means allocating.
   2007         1.1   mycroft  */
   2008         1.9  christos void
   2009        1.85   thorpej ffs_clusteracct(struct fs *fs, struct cg *cgp, int32_t blkno, int cnt)
   2010         1.1   mycroft {
   2011         1.4       cgd 	int32_t *sump;
   2012         1.5   mycroft 	int32_t *lp;
   2013         1.1   mycroft 	u_char *freemapp, *mapp;
   2014         1.1   mycroft 	int i, start, end, forw, back, map, bit;
   2015        1.30      fvdl #ifdef FFS_EI
   2016        1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   2017        1.30      fvdl #endif
   2018         1.1   mycroft 
   2019       1.101        ad 	/* KASSERT(mutex_owned(&ump->um_lock)); */
   2020       1.101        ad 
   2021         1.1   mycroft 	if (fs->fs_contigsumsize <= 0)
   2022         1.1   mycroft 		return;
   2023        1.19    bouyer 	freemapp = cg_clustersfree(cgp, needswap);
   2024        1.19    bouyer 	sump = cg_clustersum(cgp, needswap);
   2025         1.1   mycroft 	/*
   2026         1.1   mycroft 	 * Allocate or clear the actual block.
   2027         1.1   mycroft 	 */
   2028         1.1   mycroft 	if (cnt > 0)
   2029         1.1   mycroft 		setbit(freemapp, blkno);
   2030         1.1   mycroft 	else
   2031         1.1   mycroft 		clrbit(freemapp, blkno);
   2032         1.1   mycroft 	/*
   2033         1.1   mycroft 	 * Find the size of the cluster going forward.
   2034         1.1   mycroft 	 */
   2035         1.1   mycroft 	start = blkno + 1;
   2036         1.1   mycroft 	end = start + fs->fs_contigsumsize;
   2037        1.19    bouyer 	if (end >= ufs_rw32(cgp->cg_nclusterblks, needswap))
   2038        1.19    bouyer 		end = ufs_rw32(cgp->cg_nclusterblks, needswap);
   2039         1.1   mycroft 	mapp = &freemapp[start / NBBY];
   2040         1.1   mycroft 	map = *mapp++;
   2041         1.1   mycroft 	bit = 1 << (start % NBBY);
   2042         1.1   mycroft 	for (i = start; i < end; i++) {
   2043         1.1   mycroft 		if ((map & bit) == 0)
   2044         1.1   mycroft 			break;
   2045         1.1   mycroft 		if ((i & (NBBY - 1)) != (NBBY - 1)) {
   2046         1.1   mycroft 			bit <<= 1;
   2047         1.1   mycroft 		} else {
   2048         1.1   mycroft 			map = *mapp++;
   2049         1.1   mycroft 			bit = 1;
   2050         1.1   mycroft 		}
   2051         1.1   mycroft 	}
   2052         1.1   mycroft 	forw = i - start;
   2053         1.1   mycroft 	/*
   2054         1.1   mycroft 	 * Find the size of the cluster going backward.
   2055         1.1   mycroft 	 */
   2056         1.1   mycroft 	start = blkno - 1;
   2057         1.1   mycroft 	end = start - fs->fs_contigsumsize;
   2058         1.1   mycroft 	if (end < 0)
   2059         1.1   mycroft 		end = -1;
   2060         1.1   mycroft 	mapp = &freemapp[start / NBBY];
   2061         1.1   mycroft 	map = *mapp--;
   2062         1.1   mycroft 	bit = 1 << (start % NBBY);
   2063         1.1   mycroft 	for (i = start; i > end; i--) {
   2064         1.1   mycroft 		if ((map & bit) == 0)
   2065         1.1   mycroft 			break;
   2066         1.1   mycroft 		if ((i & (NBBY - 1)) != 0) {
   2067         1.1   mycroft 			bit >>= 1;
   2068         1.1   mycroft 		} else {
   2069         1.1   mycroft 			map = *mapp--;
   2070         1.1   mycroft 			bit = 1 << (NBBY - 1);
   2071         1.1   mycroft 		}
   2072         1.1   mycroft 	}
   2073         1.1   mycroft 	back = start - i;
   2074         1.1   mycroft 	/*
   2075         1.1   mycroft 	 * Account for old cluster and the possibly new forward and
   2076         1.1   mycroft 	 * back clusters.
   2077         1.1   mycroft 	 */
   2078         1.1   mycroft 	i = back + forw + 1;
   2079         1.1   mycroft 	if (i > fs->fs_contigsumsize)
   2080         1.1   mycroft 		i = fs->fs_contigsumsize;
   2081        1.19    bouyer 	ufs_add32(sump[i], cnt, needswap);
   2082         1.1   mycroft 	if (back > 0)
   2083        1.19    bouyer 		ufs_add32(sump[back], -cnt, needswap);
   2084         1.1   mycroft 	if (forw > 0)
   2085        1.19    bouyer 		ufs_add32(sump[forw], -cnt, needswap);
   2086        1.19    bouyer 
   2087         1.5   mycroft 	/*
   2088         1.5   mycroft 	 * Update cluster summary information.
   2089         1.5   mycroft 	 */
   2090         1.5   mycroft 	lp = &sump[fs->fs_contigsumsize];
   2091         1.5   mycroft 	for (i = fs->fs_contigsumsize; i > 0; i--)
   2092        1.19    bouyer 		if (ufs_rw32(*lp--, needswap) > 0)
   2093         1.5   mycroft 			break;
   2094        1.19    bouyer 	fs->fs_maxcluster[ufs_rw32(cgp->cg_cgx, needswap)] = i;
   2095         1.1   mycroft }
   2096         1.1   mycroft 
   2097         1.1   mycroft /*
   2098         1.1   mycroft  * Fserr prints the name of a file system with an error diagnostic.
   2099        1.81     perry  *
   2100         1.1   mycroft  * The form of the error message is:
   2101         1.1   mycroft  *	fs: error message
   2102         1.1   mycroft  */
   2103         1.1   mycroft static void
   2104        1.85   thorpej ffs_fserr(struct fs *fs, u_int uid, const char *cp)
   2105         1.1   mycroft {
   2106         1.1   mycroft 
   2107        1.64  gmcgarry 	log(LOG_ERR, "uid %d, pid %d, command %s, on %s: %s\n",
   2108        1.64  gmcgarry 	    uid, curproc->p_pid, curproc->p_comm, fs->fs_fsmnt, cp);
   2109         1.1   mycroft }
   2110