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