Home | History | Annotate | Line # | Download | only in ffs
ffs_alloc.c revision 1.106.6.1
      1  1.106.6.1       mjf /*	$NetBSD: ffs_alloc.c,v 1.106.6.1 2008/06/02 13:24:35 mjf 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.6.1       mjf __KERNEL_RCSID(0, "$NetBSD: ffs_alloc.c,v 1.106.6.1 2008/06/02 13:24:35 mjf 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.6.1       mjf #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.6.1       mjf 	    (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.6.1       mjf 		if (bread(vp, idp->in_lbn, (int)fs->fs_bsize,
    517  1.106.6.1       mjf 		    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.6.1       mjf 		if (bread(vp, idp->in_lbn, (int)fs->fs_bsize,
    541  1.106.6.1       mjf 		    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.6.1       mjf 		    (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.6.1       mjf 		(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.6.1       mjf 		(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.6.1       mjf 	    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.6.1       mjf 		(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.60      fvdl 		ibp = getblk(ip->i_devvp, fsbtodb(fs,
   1552       1.60      fvdl 		    ino_to_fsba(fs, cg * fs->fs_ipg + initediblk)),
   1553       1.60      fvdl 		    (int)fs->fs_bsize, 0, 0);
   1554       1.60      fvdl 		    memset(ibp->b_data, 0, fs->fs_bsize);
   1555       1.60      fvdl 		    dp2 = (struct ufs2_dinode *)(ibp->b_data);
   1556       1.60      fvdl 		    for (i = 0; i < INOPB(fs); i++) {
   1557       1.60      fvdl 			/*
   1558       1.60      fvdl 			 * Don't bother to swap, it's supposed to be
   1559       1.60      fvdl 			 * random, after all.
   1560       1.60      fvdl 			 */
   1561       1.70    itojun 			dp2->di_gen = (arc4random() & INT32_MAX) / 2 + 1;
   1562       1.60      fvdl 			dp2++;
   1563       1.60      fvdl 		}
   1564       1.60      fvdl 		initediblk += INOPB(fs);
   1565       1.60      fvdl 		cgp->cg_initediblk = ufs_rw32(initediblk, needswap);
   1566       1.60      fvdl 	}
   1567       1.60      fvdl 
   1568      1.101        ad 	mutex_enter(&ump->um_lock);
   1569       1.76   hannken 	ACTIVECG_CLR(fs, cg);
   1570      1.101        ad 	setbit(inosused, ipref);
   1571      1.101        ad 	ufs_add32(cgp->cg_cs.cs_nifree, -1, needswap);
   1572      1.101        ad 	fs->fs_cstotal.cs_nifree--;
   1573      1.101        ad 	fs->fs_cs(fs, cg).cs_nifree--;
   1574      1.101        ad 	fs->fs_fmod = 1;
   1575      1.101        ad 	if ((mode & IFMT) == IFDIR) {
   1576      1.101        ad 		ufs_add32(cgp->cg_cs.cs_ndir, 1, needswap);
   1577      1.101        ad 		fs->fs_cstotal.cs_ndir++;
   1578      1.101        ad 		fs->fs_cs(fs, cg).cs_ndir++;
   1579      1.101        ad 	}
   1580      1.101        ad 	mutex_exit(&ump->um_lock);
   1581      1.101        ad 	if (DOINGSOFTDEP(ITOV(ip)))
   1582      1.101        ad 		softdep_setup_inomapdep(bp, ip, cg * fs->fs_ipg + ipref);
   1583        1.1   mycroft 	bdwrite(bp);
   1584      1.104   hannken 	if (ibp != NULL)
   1585      1.104   hannken 		bawrite(ibp);
   1586        1.1   mycroft 	return (cg * fs->fs_ipg + ipref);
   1587      1.101        ad  fail:
   1588      1.101        ad 	brelse(bp, 0);
   1589      1.101        ad 	mutex_enter(&ump->um_lock);
   1590      1.101        ad 	return (0);
   1591        1.1   mycroft }
   1592        1.1   mycroft 
   1593        1.1   mycroft /*
   1594        1.1   mycroft  * Free a block or fragment.
   1595        1.1   mycroft  *
   1596        1.1   mycroft  * The specified block or fragment is placed back in the
   1597       1.81     perry  * free map. If a fragment is deallocated, a possible
   1598        1.1   mycroft  * block reassembly is checked.
   1599      1.106     pooka  *
   1600      1.106     pooka  * => um_lock not held on entry or exit
   1601        1.1   mycroft  */
   1602        1.9  christos void
   1603       1.85   thorpej ffs_blkfree(struct fs *fs, struct vnode *devvp, daddr_t bno, long size,
   1604       1.85   thorpej     ino_t inum)
   1605        1.1   mycroft {
   1606       1.33  augustss 	struct cg *cgp;
   1607        1.1   mycroft 	struct buf *bp;
   1608       1.76   hannken 	struct ufsmount *ump;
   1609       1.60      fvdl 	int32_t fragno, cgbno;
   1610       1.76   hannken 	daddr_t cgblkno;
   1611        1.1   mycroft 	int i, error, cg, blk, frags, bbase;
   1612       1.62      fvdl 	u_int8_t *blksfree;
   1613       1.76   hannken 	dev_t dev;
   1614       1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   1615        1.1   mycroft 
   1616       1.76   hannken 	cg = dtog(fs, bno);
   1617       1.77   hannken 	if (devvp->v_type != VBLK) {
   1618       1.77   hannken 		/* devvp is a snapshot */
   1619       1.76   hannken 		dev = VTOI(devvp)->i_devvp->v_rdev;
   1620      1.103   hannken 		ump = VFSTOUFS(devvp->v_mount);
   1621       1.76   hannken 		cgblkno = fragstoblks(fs, cgtod(fs, cg));
   1622       1.76   hannken 	} else {
   1623       1.76   hannken 		dev = devvp->v_rdev;
   1624      1.103   hannken 		ump = VFSTOUFS(devvp->v_specmountpoint);
   1625       1.76   hannken 		cgblkno = fsbtodb(fs, cgtod(fs, cg));
   1626      1.100   hannken 		if (ffs_snapblkfree(fs, devvp, bno, size, inum))
   1627       1.76   hannken 			return;
   1628       1.76   hannken 	}
   1629       1.30      fvdl 	if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0 ||
   1630       1.30      fvdl 	    fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) {
   1631       1.59   tsutsui 		printf("dev = 0x%x, bno = %" PRId64 " bsize = %d, "
   1632       1.58      fvdl 		       "size = %ld, fs = %s\n",
   1633       1.76   hannken 		    dev, bno, fs->fs_bsize, size, fs->fs_fsmnt);
   1634        1.1   mycroft 		panic("blkfree: bad size");
   1635        1.1   mycroft 	}
   1636       1.76   hannken 
   1637       1.60      fvdl 	if (bno >= fs->fs_size) {
   1638       1.86  christos 		printf("bad block %" PRId64 ", ino %llu\n", bno,
   1639       1.86  christos 		    (unsigned long long)inum);
   1640       1.76   hannken 		ffs_fserr(fs, inum, "bad block");
   1641        1.1   mycroft 		return;
   1642        1.1   mycroft 	}
   1643  1.106.6.1       mjf 	error = bread(devvp, cgblkno, (int)fs->fs_cgsize,
   1644  1.106.6.1       mjf 	    NOCRED, B_MODIFY, &bp);
   1645        1.1   mycroft 	if (error) {
   1646      1.101        ad 		brelse(bp, 0);
   1647        1.1   mycroft 		return;
   1648        1.1   mycroft 	}
   1649        1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1650       1.19    bouyer 	if (!cg_chkmagic(cgp, needswap)) {
   1651      1.101        ad 		brelse(bp, 0);
   1652        1.1   mycroft 		return;
   1653        1.1   mycroft 	}
   1654       1.92    kardel 	cgp->cg_old_time = ufs_rw32(time_second, needswap);
   1655       1.73       dbj 	if ((fs->fs_magic != FS_UFS1_MAGIC) ||
   1656       1.73       dbj 	    (fs->fs_old_flags & FS_FLAGS_UPDATED))
   1657       1.92    kardel 		cgp->cg_time = ufs_rw64(time_second, needswap);
   1658       1.60      fvdl 	cgbno = dtogd(fs, bno);
   1659       1.62      fvdl 	blksfree = cg_blksfree(cgp, needswap);
   1660      1.101        ad 	mutex_enter(&ump->um_lock);
   1661        1.1   mycroft 	if (size == fs->fs_bsize) {
   1662       1.60      fvdl 		fragno = fragstoblks(fs, cgbno);
   1663       1.62      fvdl 		if (!ffs_isfreeblock(fs, blksfree, fragno)) {
   1664       1.77   hannken 			if (devvp->v_type != VBLK) {
   1665       1.77   hannken 				/* devvp is a snapshot */
   1666      1.101        ad 				mutex_exit(&ump->um_lock);
   1667      1.101        ad 				brelse(bp, 0);
   1668       1.76   hannken 				return;
   1669       1.76   hannken 			}
   1670       1.59   tsutsui 			printf("dev = 0x%x, block = %" PRId64 ", fs = %s\n",
   1671       1.76   hannken 			    dev, bno, fs->fs_fsmnt);
   1672        1.1   mycroft 			panic("blkfree: freeing free block");
   1673        1.1   mycroft 		}
   1674       1.62      fvdl 		ffs_setblock(fs, blksfree, fragno);
   1675       1.60      fvdl 		ffs_clusteracct(fs, cgp, fragno, 1);
   1676       1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_nbfree, 1, needswap);
   1677        1.1   mycroft 		fs->fs_cstotal.cs_nbfree++;
   1678        1.1   mycroft 		fs->fs_cs(fs, cg).cs_nbfree++;
   1679       1.73       dbj 		if ((fs->fs_magic == FS_UFS1_MAGIC) &&
   1680       1.73       dbj 		    ((fs->fs_old_flags & FS_FLAGS_UPDATED) == 0)) {
   1681       1.73       dbj 			i = old_cbtocylno(fs, cgbno);
   1682       1.75       dbj 			KASSERT(i >= 0);
   1683       1.75       dbj 			KASSERT(i < fs->fs_old_ncyl);
   1684       1.75       dbj 			KASSERT(old_cbtorpos(fs, cgbno) >= 0);
   1685       1.75       dbj 			KASSERT(fs->fs_old_nrpos == 0 || old_cbtorpos(fs, cgbno) < fs->fs_old_nrpos);
   1686       1.73       dbj 			ufs_add16(old_cg_blks(fs, cgp, i, needswap)[old_cbtorpos(fs, cgbno)], 1,
   1687       1.73       dbj 			    needswap);
   1688       1.73       dbj 			ufs_add32(old_cg_blktot(cgp, needswap)[i], 1, needswap);
   1689       1.73       dbj 		}
   1690        1.1   mycroft 	} else {
   1691       1.60      fvdl 		bbase = cgbno - fragnum(fs, cgbno);
   1692        1.1   mycroft 		/*
   1693        1.1   mycroft 		 * decrement the counts associated with the old frags
   1694        1.1   mycroft 		 */
   1695       1.62      fvdl 		blk = blkmap(fs, blksfree, bbase);
   1696       1.19    bouyer 		ffs_fragacct(fs, blk, cgp->cg_frsum, -1, needswap);
   1697        1.1   mycroft 		/*
   1698        1.1   mycroft 		 * deallocate the fragment
   1699        1.1   mycroft 		 */
   1700        1.1   mycroft 		frags = numfrags(fs, size);
   1701        1.1   mycroft 		for (i = 0; i < frags; i++) {
   1702       1.62      fvdl 			if (isset(blksfree, cgbno + i)) {
   1703       1.59   tsutsui 				printf("dev = 0x%x, block = %" PRId64
   1704       1.59   tsutsui 				       ", fs = %s\n",
   1705       1.76   hannken 				    dev, bno + i, fs->fs_fsmnt);
   1706        1.1   mycroft 				panic("blkfree: freeing free frag");
   1707        1.1   mycroft 			}
   1708       1.62      fvdl 			setbit(blksfree, cgbno + i);
   1709        1.1   mycroft 		}
   1710       1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_nffree, i, needswap);
   1711        1.1   mycroft 		fs->fs_cstotal.cs_nffree += i;
   1712       1.30      fvdl 		fs->fs_cs(fs, cg).cs_nffree += i;
   1713        1.1   mycroft 		/*
   1714        1.1   mycroft 		 * add back in counts associated with the new frags
   1715        1.1   mycroft 		 */
   1716       1.62      fvdl 		blk = blkmap(fs, blksfree, bbase);
   1717       1.19    bouyer 		ffs_fragacct(fs, blk, cgp->cg_frsum, 1, needswap);
   1718        1.1   mycroft 		/*
   1719        1.1   mycroft 		 * if a complete block has been reassembled, account for it
   1720        1.1   mycroft 		 */
   1721       1.60      fvdl 		fragno = fragstoblks(fs, bbase);
   1722       1.62      fvdl 		if (ffs_isblock(fs, blksfree, fragno)) {
   1723       1.19    bouyer 			ufs_add32(cgp->cg_cs.cs_nffree, -fs->fs_frag, needswap);
   1724        1.1   mycroft 			fs->fs_cstotal.cs_nffree -= fs->fs_frag;
   1725        1.1   mycroft 			fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag;
   1726       1.60      fvdl 			ffs_clusteracct(fs, cgp, fragno, 1);
   1727       1.19    bouyer 			ufs_add32(cgp->cg_cs.cs_nbfree, 1, needswap);
   1728        1.1   mycroft 			fs->fs_cstotal.cs_nbfree++;
   1729        1.1   mycroft 			fs->fs_cs(fs, cg).cs_nbfree++;
   1730       1.73       dbj 			if ((fs->fs_magic == FS_UFS1_MAGIC) &&
   1731       1.73       dbj 			    ((fs->fs_old_flags & FS_FLAGS_UPDATED) == 0)) {
   1732       1.73       dbj 				i = old_cbtocylno(fs, bbase);
   1733       1.75       dbj 				KASSERT(i >= 0);
   1734       1.75       dbj 				KASSERT(i < fs->fs_old_ncyl);
   1735       1.75       dbj 				KASSERT(old_cbtorpos(fs, bbase) >= 0);
   1736       1.75       dbj 				KASSERT(fs->fs_old_nrpos == 0 || old_cbtorpos(fs, bbase) < fs->fs_old_nrpos);
   1737       1.73       dbj 				ufs_add16(old_cg_blks(fs, cgp, i, needswap)[old_cbtorpos(fs,
   1738       1.73       dbj 				    bbase)], 1, needswap);
   1739       1.73       dbj 				ufs_add32(old_cg_blktot(cgp, needswap)[i], 1, needswap);
   1740       1.73       dbj 			}
   1741        1.1   mycroft 		}
   1742        1.1   mycroft 	}
   1743        1.1   mycroft 	fs->fs_fmod = 1;
   1744       1.76   hannken 	ACTIVECG_CLR(fs, cg);
   1745      1.101        ad 	mutex_exit(&ump->um_lock);
   1746        1.1   mycroft 	bdwrite(bp);
   1747        1.1   mycroft }
   1748        1.1   mycroft 
   1749       1.18      fvdl #if defined(DIAGNOSTIC) || defined(DEBUG)
   1750       1.55      matt #ifdef XXXUBC
   1751       1.18      fvdl /*
   1752       1.18      fvdl  * Verify allocation of a block or fragment. Returns true if block or
   1753       1.18      fvdl  * fragment is allocated, false if it is free.
   1754       1.18      fvdl  */
   1755       1.18      fvdl static int
   1756       1.85   thorpej ffs_checkblk(struct inode *ip, daddr_t bno, long size)
   1757       1.18      fvdl {
   1758       1.18      fvdl 	struct fs *fs;
   1759       1.18      fvdl 	struct cg *cgp;
   1760       1.18      fvdl 	struct buf *bp;
   1761       1.18      fvdl 	int i, error, frags, free;
   1762       1.18      fvdl 
   1763       1.18      fvdl 	fs = ip->i_fs;
   1764       1.18      fvdl 	if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) {
   1765       1.18      fvdl 		printf("bsize = %d, size = %ld, fs = %s\n",
   1766       1.18      fvdl 		    fs->fs_bsize, size, fs->fs_fsmnt);
   1767       1.18      fvdl 		panic("checkblk: bad size");
   1768       1.18      fvdl 	}
   1769       1.60      fvdl 	if (bno >= fs->fs_size)
   1770       1.18      fvdl 		panic("checkblk: bad block %d", bno);
   1771       1.18      fvdl 	error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))),
   1772  1.106.6.1       mjf 		(int)fs->fs_cgsize, NOCRED, 0, &bp);
   1773       1.18      fvdl 	if (error) {
   1774      1.101        ad 		brelse(bp, 0);
   1775       1.18      fvdl 		return 0;
   1776       1.18      fvdl 	}
   1777       1.18      fvdl 	cgp = (struct cg *)bp->b_data;
   1778       1.30      fvdl 	if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs))) {
   1779      1.101        ad 		brelse(bp, 0);
   1780       1.18      fvdl 		return 0;
   1781       1.18      fvdl 	}
   1782       1.18      fvdl 	bno = dtogd(fs, bno);
   1783       1.18      fvdl 	if (size == fs->fs_bsize) {
   1784       1.30      fvdl 		free = ffs_isblock(fs, cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)),
   1785       1.19    bouyer 			fragstoblks(fs, bno));
   1786       1.18      fvdl 	} else {
   1787       1.18      fvdl 		frags = numfrags(fs, size);
   1788       1.18      fvdl 		for (free = 0, i = 0; i < frags; i++)
   1789       1.30      fvdl 			if (isset(cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)), bno + i))
   1790       1.18      fvdl 				free++;
   1791       1.18      fvdl 		if (free != 0 && free != frags)
   1792       1.18      fvdl 			panic("checkblk: partially free fragment");
   1793       1.18      fvdl 	}
   1794      1.101        ad 	brelse(bp, 0);
   1795       1.18      fvdl 	return (!free);
   1796       1.18      fvdl }
   1797       1.55      matt #endif /* XXXUBC */
   1798       1.18      fvdl #endif /* DIAGNOSTIC */
   1799       1.18      fvdl 
   1800        1.1   mycroft /*
   1801        1.1   mycroft  * Free an inode.
   1802       1.30      fvdl  */
   1803       1.30      fvdl int
   1804       1.88      yamt ffs_vfree(struct vnode *vp, ino_t ino, int mode)
   1805       1.30      fvdl {
   1806       1.30      fvdl 
   1807       1.88      yamt 	if (DOINGSOFTDEP(vp)) {
   1808       1.88      yamt 		softdep_freefile(vp, ino, mode);
   1809       1.30      fvdl 		return (0);
   1810       1.30      fvdl 	}
   1811       1.88      yamt 	return ffs_freefile(VTOI(vp)->i_fs, VTOI(vp)->i_devvp, ino, mode);
   1812       1.30      fvdl }
   1813       1.30      fvdl 
   1814       1.30      fvdl /*
   1815       1.30      fvdl  * Do the actual free operation.
   1816        1.1   mycroft  * The specified inode is placed back in the free map.
   1817        1.1   mycroft  */
   1818        1.1   mycroft int
   1819       1.85   thorpej ffs_freefile(struct fs *fs, struct vnode *devvp, ino_t ino, int mode)
   1820        1.9  christos {
   1821      1.101        ad 	struct ufsmount *ump;
   1822       1.33  augustss 	struct cg *cgp;
   1823        1.1   mycroft 	struct buf *bp;
   1824        1.1   mycroft 	int error, cg;
   1825       1.76   hannken 	daddr_t cgbno;
   1826       1.62      fvdl 	u_int8_t *inosused;
   1827       1.78   hannken 	dev_t dev;
   1828       1.19    bouyer #ifdef FFS_EI
   1829       1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   1830       1.19    bouyer #endif
   1831        1.1   mycroft 
   1832       1.76   hannken 	cg = ino_to_cg(fs, ino);
   1833       1.78   hannken 	if (devvp->v_type != VBLK) {
   1834       1.78   hannken 		/* devvp is a snapshot */
   1835       1.78   hannken 		dev = VTOI(devvp)->i_devvp->v_rdev;
   1836      1.103   hannken 		ump = VFSTOUFS(devvp->v_mount);
   1837       1.76   hannken 		cgbno = fragstoblks(fs, cgtod(fs, cg));
   1838       1.76   hannken 	} else {
   1839       1.78   hannken 		dev = devvp->v_rdev;
   1840      1.103   hannken 		ump = VFSTOUFS(devvp->v_specmountpoint);
   1841       1.76   hannken 		cgbno = fsbtodb(fs, cgtod(fs, cg));
   1842       1.76   hannken 	}
   1843        1.1   mycroft 	if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg)
   1844       1.86  christos 		panic("ifree: range: dev = 0x%x, ino = %llu, fs = %s",
   1845       1.86  christos 		    dev, (unsigned long long)ino, fs->fs_fsmnt);
   1846  1.106.6.1       mjf 	error = bread(devvp, cgbno, (int)fs->fs_cgsize,
   1847  1.106.6.1       mjf 	    NOCRED, B_MODIFY, &bp);
   1848        1.1   mycroft 	if (error) {
   1849      1.101        ad 		brelse(bp, 0);
   1850       1.30      fvdl 		return (error);
   1851        1.1   mycroft 	}
   1852        1.1   mycroft 	cgp = (struct cg *)bp->b_data;
   1853       1.19    bouyer 	if (!cg_chkmagic(cgp, needswap)) {
   1854      1.101        ad 		brelse(bp, 0);
   1855        1.1   mycroft 		return (0);
   1856        1.1   mycroft 	}
   1857       1.92    kardel 	cgp->cg_old_time = ufs_rw32(time_second, needswap);
   1858       1.73       dbj 	if ((fs->fs_magic != FS_UFS1_MAGIC) ||
   1859       1.73       dbj 	    (fs->fs_old_flags & FS_FLAGS_UPDATED))
   1860       1.92    kardel 		cgp->cg_time = ufs_rw64(time_second, needswap);
   1861       1.62      fvdl 	inosused = cg_inosused(cgp, needswap);
   1862        1.1   mycroft 	ino %= fs->fs_ipg;
   1863       1.62      fvdl 	if (isclr(inosused, ino)) {
   1864       1.86  christos 		printf("ifree: dev = 0x%x, ino = %llu, fs = %s\n",
   1865       1.86  christos 		    dev, (unsigned long long)ino + cg * fs->fs_ipg,
   1866       1.86  christos 		    fs->fs_fsmnt);
   1867        1.1   mycroft 		if (fs->fs_ronly == 0)
   1868        1.1   mycroft 			panic("ifree: freeing free inode");
   1869        1.1   mycroft 	}
   1870       1.62      fvdl 	clrbit(inosused, ino);
   1871       1.19    bouyer 	if (ino < ufs_rw32(cgp->cg_irotor, needswap))
   1872       1.19    bouyer 		cgp->cg_irotor = ufs_rw32(ino, needswap);
   1873       1.19    bouyer 	ufs_add32(cgp->cg_cs.cs_nifree, 1, needswap);
   1874      1.101        ad 	mutex_enter(&ump->um_lock);
   1875        1.1   mycroft 	fs->fs_cstotal.cs_nifree++;
   1876        1.1   mycroft 	fs->fs_cs(fs, cg).cs_nifree++;
   1877       1.78   hannken 	if ((mode & IFMT) == IFDIR) {
   1878       1.19    bouyer 		ufs_add32(cgp->cg_cs.cs_ndir, -1, needswap);
   1879        1.1   mycroft 		fs->fs_cstotal.cs_ndir--;
   1880        1.1   mycroft 		fs->fs_cs(fs, cg).cs_ndir--;
   1881        1.1   mycroft 	}
   1882        1.1   mycroft 	fs->fs_fmod = 1;
   1883       1.82   hannken 	ACTIVECG_CLR(fs, cg);
   1884      1.101        ad 	mutex_exit(&ump->um_lock);
   1885        1.1   mycroft 	bdwrite(bp);
   1886        1.1   mycroft 	return (0);
   1887        1.1   mycroft }
   1888        1.1   mycroft 
   1889        1.1   mycroft /*
   1890       1.76   hannken  * Check to see if a file is free.
   1891       1.76   hannken  */
   1892       1.76   hannken int
   1893       1.85   thorpej ffs_checkfreefile(struct fs *fs, struct vnode *devvp, ino_t ino)
   1894       1.76   hannken {
   1895       1.76   hannken 	struct cg *cgp;
   1896       1.76   hannken 	struct buf *bp;
   1897       1.76   hannken 	daddr_t cgbno;
   1898       1.76   hannken 	int ret, cg;
   1899       1.76   hannken 	u_int8_t *inosused;
   1900       1.76   hannken 
   1901       1.76   hannken 	cg = ino_to_cg(fs, ino);
   1902       1.77   hannken 	if (devvp->v_type != VBLK) {
   1903       1.77   hannken 		/* devvp is a snapshot */
   1904       1.76   hannken 		cgbno = fragstoblks(fs, cgtod(fs, cg));
   1905       1.77   hannken 	} else
   1906       1.76   hannken 		cgbno = fsbtodb(fs, cgtod(fs, cg));
   1907       1.76   hannken 	if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg)
   1908       1.76   hannken 		return 1;
   1909  1.106.6.1       mjf 	if (bread(devvp, cgbno, (int)fs->fs_cgsize, NOCRED, 0, &bp)) {
   1910      1.101        ad 		brelse(bp, 0);
   1911       1.76   hannken 		return 1;
   1912       1.76   hannken 	}
   1913       1.76   hannken 	cgp = (struct cg *)bp->b_data;
   1914       1.76   hannken 	if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs))) {
   1915      1.101        ad 		brelse(bp, 0);
   1916       1.76   hannken 		return 1;
   1917       1.76   hannken 	}
   1918       1.76   hannken 	inosused = cg_inosused(cgp, UFS_FSNEEDSWAP(fs));
   1919       1.76   hannken 	ino %= fs->fs_ipg;
   1920       1.76   hannken 	ret = isclr(inosused, ino);
   1921      1.101        ad 	brelse(bp, 0);
   1922       1.76   hannken 	return ret;
   1923       1.76   hannken }
   1924       1.76   hannken 
   1925       1.76   hannken /*
   1926        1.1   mycroft  * Find a block of the specified size in the specified cylinder group.
   1927        1.1   mycroft  *
   1928        1.1   mycroft  * It is a panic if a request is made to find a block if none are
   1929        1.1   mycroft  * available.
   1930        1.1   mycroft  */
   1931       1.60      fvdl static int32_t
   1932       1.85   thorpej ffs_mapsearch(struct fs *fs, struct cg *cgp, daddr_t bpref, int allocsiz)
   1933        1.1   mycroft {
   1934       1.60      fvdl 	int32_t bno;
   1935        1.1   mycroft 	int start, len, loc, i;
   1936        1.1   mycroft 	int blk, field, subfield, pos;
   1937       1.19    bouyer 	int ostart, olen;
   1938       1.62      fvdl 	u_int8_t *blksfree;
   1939       1.30      fvdl #ifdef FFS_EI
   1940       1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   1941       1.30      fvdl #endif
   1942        1.1   mycroft 
   1943      1.101        ad 	/* KASSERT(mutex_owned(&ump->um_lock)); */
   1944      1.101        ad 
   1945        1.1   mycroft 	/*
   1946        1.1   mycroft 	 * find the fragment by searching through the free block
   1947        1.1   mycroft 	 * map for an appropriate bit pattern
   1948        1.1   mycroft 	 */
   1949        1.1   mycroft 	if (bpref)
   1950        1.1   mycroft 		start = dtogd(fs, bpref) / NBBY;
   1951        1.1   mycroft 	else
   1952       1.19    bouyer 		start = ufs_rw32(cgp->cg_frotor, needswap) / NBBY;
   1953       1.62      fvdl 	blksfree = cg_blksfree(cgp, needswap);
   1954        1.1   mycroft 	len = howmany(fs->fs_fpg, NBBY) - start;
   1955       1.19    bouyer 	ostart = start;
   1956       1.19    bouyer 	olen = len;
   1957       1.45     lukem 	loc = scanc((u_int)len,
   1958       1.62      fvdl 		(const u_char *)&blksfree[start],
   1959       1.45     lukem 		(const u_char *)fragtbl[fs->fs_frag],
   1960       1.54   mycroft 		(1 << (allocsiz - 1 + (fs->fs_frag & (NBBY - 1)))));
   1961        1.1   mycroft 	if (loc == 0) {
   1962        1.1   mycroft 		len = start + 1;
   1963        1.1   mycroft 		start = 0;
   1964       1.45     lukem 		loc = scanc((u_int)len,
   1965       1.62      fvdl 			(const u_char *)&blksfree[0],
   1966       1.45     lukem 			(const u_char *)fragtbl[fs->fs_frag],
   1967       1.54   mycroft 			(1 << (allocsiz - 1 + (fs->fs_frag & (NBBY - 1)))));
   1968        1.1   mycroft 		if (loc == 0) {
   1969       1.13  christos 			printf("start = %d, len = %d, fs = %s\n",
   1970       1.19    bouyer 			    ostart, olen, fs->fs_fsmnt);
   1971       1.20      ross 			printf("offset=%d %ld\n",
   1972       1.19    bouyer 				ufs_rw32(cgp->cg_freeoff, needswap),
   1973       1.62      fvdl 				(long)blksfree - (long)cgp);
   1974       1.62      fvdl 			printf("cg %d\n", cgp->cg_cgx);
   1975        1.1   mycroft 			panic("ffs_alloccg: map corrupted");
   1976        1.1   mycroft 			/* NOTREACHED */
   1977        1.1   mycroft 		}
   1978        1.1   mycroft 	}
   1979        1.1   mycroft 	bno = (start + len - loc) * NBBY;
   1980       1.19    bouyer 	cgp->cg_frotor = ufs_rw32(bno, needswap);
   1981        1.1   mycroft 	/*
   1982        1.1   mycroft 	 * found the byte in the map
   1983        1.1   mycroft 	 * sift through the bits to find the selected frag
   1984        1.1   mycroft 	 */
   1985        1.1   mycroft 	for (i = bno + NBBY; bno < i; bno += fs->fs_frag) {
   1986       1.62      fvdl 		blk = blkmap(fs, blksfree, bno);
   1987        1.1   mycroft 		blk <<= 1;
   1988        1.1   mycroft 		field = around[allocsiz];
   1989        1.1   mycroft 		subfield = inside[allocsiz];
   1990        1.1   mycroft 		for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) {
   1991        1.1   mycroft 			if ((blk & field) == subfield)
   1992        1.1   mycroft 				return (bno + pos);
   1993        1.1   mycroft 			field <<= 1;
   1994        1.1   mycroft 			subfield <<= 1;
   1995        1.1   mycroft 		}
   1996        1.1   mycroft 	}
   1997       1.60      fvdl 	printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt);
   1998        1.1   mycroft 	panic("ffs_alloccg: block not in map");
   1999       1.58      fvdl 	/* return (-1); */
   2000        1.1   mycroft }
   2001        1.1   mycroft 
   2002        1.1   mycroft /*
   2003        1.1   mycroft  * Update the cluster map because of an allocation or free.
   2004        1.1   mycroft  *
   2005        1.1   mycroft  * Cnt == 1 means free; cnt == -1 means allocating.
   2006        1.1   mycroft  */
   2007        1.9  christos void
   2008       1.85   thorpej ffs_clusteracct(struct fs *fs, struct cg *cgp, int32_t blkno, int cnt)
   2009        1.1   mycroft {
   2010        1.4       cgd 	int32_t *sump;
   2011        1.5   mycroft 	int32_t *lp;
   2012        1.1   mycroft 	u_char *freemapp, *mapp;
   2013        1.1   mycroft 	int i, start, end, forw, back, map, bit;
   2014       1.30      fvdl #ifdef FFS_EI
   2015       1.30      fvdl 	const int needswap = UFS_FSNEEDSWAP(fs);
   2016       1.30      fvdl #endif
   2017        1.1   mycroft 
   2018      1.101        ad 	/* KASSERT(mutex_owned(&ump->um_lock)); */
   2019      1.101        ad 
   2020        1.1   mycroft 	if (fs->fs_contigsumsize <= 0)
   2021        1.1   mycroft 		return;
   2022       1.19    bouyer 	freemapp = cg_clustersfree(cgp, needswap);
   2023       1.19    bouyer 	sump = cg_clustersum(cgp, needswap);
   2024        1.1   mycroft 	/*
   2025        1.1   mycroft 	 * Allocate or clear the actual block.
   2026        1.1   mycroft 	 */
   2027        1.1   mycroft 	if (cnt > 0)
   2028        1.1   mycroft 		setbit(freemapp, blkno);
   2029        1.1   mycroft 	else
   2030        1.1   mycroft 		clrbit(freemapp, blkno);
   2031        1.1   mycroft 	/*
   2032        1.1   mycroft 	 * Find the size of the cluster going forward.
   2033        1.1   mycroft 	 */
   2034        1.1   mycroft 	start = blkno + 1;
   2035        1.1   mycroft 	end = start + fs->fs_contigsumsize;
   2036       1.19    bouyer 	if (end >= ufs_rw32(cgp->cg_nclusterblks, needswap))
   2037       1.19    bouyer 		end = ufs_rw32(cgp->cg_nclusterblks, needswap);
   2038        1.1   mycroft 	mapp = &freemapp[start / NBBY];
   2039        1.1   mycroft 	map = *mapp++;
   2040        1.1   mycroft 	bit = 1 << (start % NBBY);
   2041        1.1   mycroft 	for (i = start; i < end; i++) {
   2042        1.1   mycroft 		if ((map & bit) == 0)
   2043        1.1   mycroft 			break;
   2044        1.1   mycroft 		if ((i & (NBBY - 1)) != (NBBY - 1)) {
   2045        1.1   mycroft 			bit <<= 1;
   2046        1.1   mycroft 		} else {
   2047        1.1   mycroft 			map = *mapp++;
   2048        1.1   mycroft 			bit = 1;
   2049        1.1   mycroft 		}
   2050        1.1   mycroft 	}
   2051        1.1   mycroft 	forw = i - start;
   2052        1.1   mycroft 	/*
   2053        1.1   mycroft 	 * Find the size of the cluster going backward.
   2054        1.1   mycroft 	 */
   2055        1.1   mycroft 	start = blkno - 1;
   2056        1.1   mycroft 	end = start - fs->fs_contigsumsize;
   2057        1.1   mycroft 	if (end < 0)
   2058        1.1   mycroft 		end = -1;
   2059        1.1   mycroft 	mapp = &freemapp[start / NBBY];
   2060        1.1   mycroft 	map = *mapp--;
   2061        1.1   mycroft 	bit = 1 << (start % NBBY);
   2062        1.1   mycroft 	for (i = start; i > end; i--) {
   2063        1.1   mycroft 		if ((map & bit) == 0)
   2064        1.1   mycroft 			break;
   2065        1.1   mycroft 		if ((i & (NBBY - 1)) != 0) {
   2066        1.1   mycroft 			bit >>= 1;
   2067        1.1   mycroft 		} else {
   2068        1.1   mycroft 			map = *mapp--;
   2069        1.1   mycroft 			bit = 1 << (NBBY - 1);
   2070        1.1   mycroft 		}
   2071        1.1   mycroft 	}
   2072        1.1   mycroft 	back = start - i;
   2073        1.1   mycroft 	/*
   2074        1.1   mycroft 	 * Account for old cluster and the possibly new forward and
   2075        1.1   mycroft 	 * back clusters.
   2076        1.1   mycroft 	 */
   2077        1.1   mycroft 	i = back + forw + 1;
   2078        1.1   mycroft 	if (i > fs->fs_contigsumsize)
   2079        1.1   mycroft 		i = fs->fs_contigsumsize;
   2080       1.19    bouyer 	ufs_add32(sump[i], cnt, needswap);
   2081        1.1   mycroft 	if (back > 0)
   2082       1.19    bouyer 		ufs_add32(sump[back], -cnt, needswap);
   2083        1.1   mycroft 	if (forw > 0)
   2084       1.19    bouyer 		ufs_add32(sump[forw], -cnt, needswap);
   2085       1.19    bouyer 
   2086        1.5   mycroft 	/*
   2087        1.5   mycroft 	 * Update cluster summary information.
   2088        1.5   mycroft 	 */
   2089        1.5   mycroft 	lp = &sump[fs->fs_contigsumsize];
   2090        1.5   mycroft 	for (i = fs->fs_contigsumsize; i > 0; i--)
   2091       1.19    bouyer 		if (ufs_rw32(*lp--, needswap) > 0)
   2092        1.5   mycroft 			break;
   2093       1.19    bouyer 	fs->fs_maxcluster[ufs_rw32(cgp->cg_cgx, needswap)] = i;
   2094        1.1   mycroft }
   2095        1.1   mycroft 
   2096        1.1   mycroft /*
   2097        1.1   mycroft  * Fserr prints the name of a file system with an error diagnostic.
   2098       1.81     perry  *
   2099        1.1   mycroft  * The form of the error message is:
   2100        1.1   mycroft  *	fs: error message
   2101        1.1   mycroft  */
   2102        1.1   mycroft static void
   2103       1.85   thorpej ffs_fserr(struct fs *fs, u_int uid, const char *cp)
   2104        1.1   mycroft {
   2105        1.1   mycroft 
   2106       1.64  gmcgarry 	log(LOG_ERR, "uid %d, pid %d, command %s, on %s: %s\n",
   2107       1.64  gmcgarry 	    uid, curproc->p_pid, curproc->p_comm, fs->fs_fsmnt, cp);
   2108        1.1   mycroft }
   2109