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