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