![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ufs_alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / sys / ufs|
Return to ufs_alloc.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / sys / ufs |
1.1 ! root 1: /* ! 2: * Copyright (c) 1982, 1986, 1989 Regents of the University of California. ! 3: * All rights reserved. ! 4: * ! 5: * Redistribution is only permitted until one year after the first shipment ! 6: * of 4.4BSD by the Regents. Otherwise, redistribution and use in source and ! 7: * binary forms are permitted provided that: (1) source distributions retain ! 8: * this entire copyright notice and comment, and (2) distributions including ! 9: * binaries display the following acknowledgement: This product includes ! 10: * software developed by the University of California, Berkeley and its ! 11: * contributors'' in the documentation or other materials provided with the ! 12: * distribution and in all advertising materials mentioning features or use ! 13: * of this software. Neither the name of the University nor the names of ! 14: * its contributors may be used to endorse or promote products derived from ! 15: * this software without specific prior written permission. ! 16: * THIS SOFTWARE IS PROVIDED AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED ! 17: * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF ! 18: * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. ! 19: * ! 20: * @(#)ufs_alloc.c 7.20 (Berkeley) 6/28/90 ! 21: */ ! 22: ! 23: #include "param.h" ! 24: #include "systm.h" ! 25: #include "buf.h" ! 26: #include "user.h" ! 27: #include "vnode.h" ! 28: #include "kernel.h" ! 29: #include "syslog.h" ! 30: #include "cmap.h" ! 31: #include "../ufs/quota.h" ! 32: #include "../ufs/inode.h" ! 33: #include "../ufs/fs.h" ! 34: ! 35: extern u_long hashalloc(); ! 36: extern ino_t ialloccg(); ! 37: extern daddr_t alloccg(); ! 38: extern daddr_t alloccgblk(); ! 39: extern daddr_t fragextend(); ! 40: extern daddr_t blkpref(); ! 41: extern daddr_t mapsearch(); ! 42: extern int inside[], around[]; ! 43: extern unsigned char *fragtbl[]; ! 44: ! 45: /* ! 46: * Allocate a block in the file system. ! 47: * ! 48: * The size of the requested block is given, which must be some ! 49: * multiple of fs_fsize and <= fs_bsize. ! 50: * A preference may be optionally specified. If a preference is given ! 51: * the following hierarchy is used to allocate a block: ! 52: * 1) allocate the requested block. ! 53: * 2) allocate a rotationally optimal block in the same cylinder. ! 54: * 3) allocate a block in the same cylinder group. ! 55: * 4) quadradically rehash into other cylinder groups, until an ! 56: * available block is located. ! 57: * If no block preference is given the following heirarchy is used ! 58: * to allocate a block: ! 59: * 1) allocate a block in the cylinder group that contains the ! 60: * inode for the file. ! 61: * 2) quadradically rehash into other cylinder groups, until an ! 62: * available block is located. ! 63: */ ! 64: alloc(ip, lbn, bpref, size, bnp) ! 65: register struct inode *ip; ! 66: daddr_t lbn, bpref; ! 67: int size; ! 68: daddr_t *bnp; ! 69: { ! 70: daddr_t bno; ! 71: register struct fs *fs; ! 72: register struct buf *bp; ! 73: int cg, error; ! 74: struct ucred *cred = u.u_cred; /* XXX */ ! 75: ! 76: *bnp = 0; ! 77: fs = ip->i_fs; ! 78: if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) { ! 79: printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", ! 80: ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); ! 81: panic("alloc: bad size"); ! 82: } ! 83: if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) ! 84: goto nospace; ! 85: if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) ! 86: goto nospace; ! 87: #ifdef QUOTA ! 88: if (error = chkdq(ip, (long)btodb(size), cred, 0)) ! 89: return (error); ! 90: #endif ! 91: if (bpref >= fs->fs_size) ! 92: bpref = 0; ! 93: if (bpref == 0) ! 94: cg = itog(fs, ip->i_number); ! 95: else ! 96: cg = dtog(fs, bpref); ! 97: bno = (daddr_t)hashalloc(ip, cg, (long)bpref, size, ! 98: (u_long (*)())alloccg); ! 99: if (bno > 0) { ! 100: ip->i_blocks += btodb(size); ! 101: ip->i_flag |= IUPD|ICHG; ! 102: *bnp = bno; ! 103: return (0); ! 104: } ! 105: nospace: ! 106: fserr(fs, cred->cr_uid, "file system full"); ! 107: uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); ! 108: return (ENOSPC); ! 109: } ! 110: ! 111: /* ! 112: * Reallocate a fragment to a bigger size ! 113: * ! 114: * The number and size of the old block is given, and a preference ! 115: * and new size is also specified. The allocator attempts to extend ! 116: * the original block. Failing that, the regular block allocator is ! 117: * invoked to get an appropriate block. ! 118: */ ! 119: realloccg(ip, lbprev, bpref, osize, nsize, bpp) ! 120: register struct inode *ip; ! 121: off_t lbprev; ! 122: daddr_t bpref; ! 123: int osize, nsize; ! 124: struct buf **bpp; ! 125: { ! 126: register struct fs *fs; ! 127: struct buf *bp, *obp; ! 128: int cg, request; ! 129: daddr_t bprev, bno, bn; ! 130: int i, error, count; ! 131: struct ucred *cred = u.u_cred; /* XXX */ ! 132: ! 133: *bpp = 0; ! 134: fs = ip->i_fs; ! 135: if ((unsigned)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || ! 136: (unsigned)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { ! 137: printf("dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n", ! 138: ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt); ! 139: panic("realloccg: bad size"); ! 140: } ! 141: if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) ! 142: goto nospace; ! 143: if ((bprev = ip->i_db[lbprev]) == 0) { ! 144: printf("dev = 0x%x, bsize = %d, bprev = %d, fs = %s\n", ! 145: ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt); ! 146: panic("realloccg: bad bprev"); ! 147: } ! 148: #ifdef QUOTA ! 149: if (error = chkdq(ip, (long)btodb(nsize - osize), cred, 0)) ! 150: return (error); ! 151: #endif ! 152: /* ! 153: * Allocate the extra space in the buffer. ! 154: */ ! 155: if (error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp)) { ! 156: brelse(bp); ! 157: return (error); ! 158: } ! 159: brealloc(bp, nsize); ! 160: bp->b_flags |= B_DONE; ! 161: bzero(bp->b_un.b_addr + osize, (unsigned)nsize - osize); ! 162: /* ! 163: * Check for extension in the existing location. ! 164: */ ! 165: cg = dtog(fs, bprev); ! 166: if (bno = fragextend(ip, cg, (long)bprev, osize, nsize)) { ! 167: if (bp->b_blkno != fsbtodb(fs, bno)) ! 168: panic("bad blockno"); ! 169: ip->i_blocks += btodb(nsize - osize); ! 170: ip->i_flag |= IUPD|ICHG; ! 171: *bpp = bp; ! 172: return (0); ! 173: } ! 174: /* ! 175: * Allocate a new disk location. ! 176: */ ! 177: if (bpref >= fs->fs_size) ! 178: bpref = 0; ! 179: switch ((int)fs->fs_optim) { ! 180: case FS_OPTSPACE: ! 181: /* ! 182: * Allocate an exact sized fragment. Although this makes ! 183: * best use of space, we will waste time relocating it if ! 184: * the file continues to grow. If the fragmentation is ! 185: * less than half of the minimum free reserve, we choose ! 186: * to begin optimizing for time. ! 187: */ ! 188: request = nsize; ! 189: if (fs->fs_minfree < 5 || ! 190: fs->fs_cstotal.cs_nffree > ! 191: fs->fs_dsize * fs->fs_minfree / (2 * 100)) ! 192: break; ! 193: log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", ! 194: fs->fs_fsmnt); ! 195: fs->fs_optim = FS_OPTTIME; ! 196: break; ! 197: case FS_OPTTIME: ! 198: /* ! 199: * At this point we have discovered a file that is trying ! 200: * to grow a small fragment to a larger fragment. To save ! 201: * time, we allocate a full sized block, then free the ! 202: * unused portion. If the file continues to grow, the ! 203: * `fragextend' call above will be able to grow it in place ! 204: * without further copying. If aberrant programs cause ! 205: * disk fragmentation to grow within 2% of the free reserve, ! 206: * we choose to begin optimizing for space. ! 207: */ ! 208: request = fs->fs_bsize; ! 209: if (fs->fs_cstotal.cs_nffree < ! 210: fs->fs_dsize * (fs->fs_minfree - 2) / 100) ! 211: break; ! 212: log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", ! 213: fs->fs_fsmnt); ! 214: fs->fs_optim = FS_OPTSPACE; ! 215: break; ! 216: default: ! 217: printf("dev = 0x%x, optim = %d, fs = %s\n", ! 218: ip->i_dev, fs->fs_optim, fs->fs_fsmnt); ! 219: panic("realloccg: bad optim"); ! 220: /* NOTREACHED */ ! 221: } ! 222: bno = (daddr_t)hashalloc(ip, cg, (long)bpref, request, ! 223: (u_long (*)())alloccg); ! 224: if (bno > 0) { ! 225: bp->b_blkno = bn = fsbtodb(fs, bno); ! 226: count = howmany(osize, CLBYTES); ! 227: for (i = 0; i < count; i++) ! 228: munhash(ip->i_devvp, bn + i * CLBYTES / DEV_BSIZE); ! 229: blkfree(ip, bprev, (off_t)osize); ! 230: if (nsize < request) ! 231: blkfree(ip, bno + numfrags(fs, nsize), ! 232: (off_t)(request - nsize)); ! 233: ip->i_blocks += btodb(nsize - osize); ! 234: ip->i_flag |= IUPD|ICHG; ! 235: *bpp = bp; ! 236: return (0); ! 237: } ! 238: brelse(bp); ! 239: nospace: ! 240: /* ! 241: * no space available ! 242: */ ! 243: fserr(fs, cred->cr_uid, "file system full"); ! 244: uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); ! 245: return (ENOSPC); ! 246: } ! 247: ! 248: /* ! 249: * Allocate an inode in the file system. ! 250: * ! 251: * A preference may be optionally specified. If a preference is given ! 252: * the following hierarchy is used to allocate an inode: ! 253: * 1) allocate the requested inode. ! 254: * 2) allocate an inode in the same cylinder group. ! 255: * 3) quadradically rehash into other cylinder groups, until an ! 256: * available inode is located. ! 257: * If no inode preference is given the following heirarchy is used ! 258: * to allocate an inode: ! 259: * 1) allocate an inode in cylinder group 0. ! 260: * 2) quadradically rehash into other cylinder groups, until an ! 261: * available inode is located. ! 262: */ ! 263: ialloc(pip, ipref, mode, cred, ipp) ! 264: register struct inode *pip; ! 265: ino_t ipref; ! 266: int mode; ! 267: struct ucred *cred; ! 268: struct inode **ipp; ! 269: { ! 270: ino_t ino; ! 271: register struct fs *fs; ! 272: register struct inode *ip; ! 273: int cg, error; ! 274: ! 275: *ipp = 0; ! 276: fs = pip->i_fs; ! 277: if (fs->fs_cstotal.cs_nifree == 0) ! 278: goto noinodes; ! 279: if (ipref >= fs->fs_ncg * fs->fs_ipg) ! 280: ipref = 0; ! 281: cg = itog(fs, ipref); ! 282: ino = (ino_t)hashalloc(pip, cg, (long)ipref, mode, ialloccg); ! 283: if (ino == 0) ! 284: goto noinodes; ! 285: error = iget(pip, ino, ipp); ! 286: if (error) { ! 287: ifree(pip, ino, mode); ! 288: return (error); ! 289: } ! 290: ip = *ipp; ! 291: if (ip->i_mode) { ! 292: printf("mode = 0%o, inum = %d, fs = %s\n", ! 293: ip->i_mode, ip->i_number, fs->fs_fsmnt); ! 294: panic("ialloc: dup alloc"); ! 295: } ! 296: if (ip->i_blocks) { /* XXX */ ! 297: printf("free inode %s/%d had %d blocks\n", ! 298: fs->fs_fsmnt, ino, ip->i_blocks); ! 299: ip->i_blocks = 0; ! 300: } ! 301: ip->i_flags = 0; ! 302: /* ! 303: * Set up a new generation number for this inode. ! 304: */ ! 305: if (++nextgennumber < (u_long)time.tv_sec) ! 306: nextgennumber = time.tv_sec; ! 307: ip->i_gen = nextgennumber; ! 308: return (0); ! 309: noinodes: ! 310: fserr(fs, cred->cr_uid, "out of inodes"); ! 311: uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); ! 312: return (ENOSPC); ! 313: } ! 314: ! 315: /* ! 316: * Find a cylinder to place a directory. ! 317: * ! 318: * The policy implemented by this algorithm is to select from ! 319: * among those cylinder groups with above the average number of ! 320: * free inodes, the one with the smallest number of directories. ! 321: */ ! 322: ino_t ! 323: dirpref(fs) ! 324: register struct fs *fs; ! 325: { ! 326: int cg, minndir, mincg, avgifree; ! 327: ! 328: avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; ! 329: minndir = fs->fs_ipg; ! 330: mincg = 0; ! 331: for (cg = 0; cg < fs->fs_ncg; cg++) ! 332: if (fs->fs_cs(fs, cg).cs_ndir < minndir && ! 333: fs->fs_cs(fs, cg).cs_nifree >= avgifree) { ! 334: mincg = cg; ! 335: minndir = fs->fs_cs(fs, cg).cs_ndir; ! 336: } ! 337: return ((ino_t)(fs->fs_ipg * mincg)); ! 338: } ! 339: ! 340: /* ! 341: * Select the desired position for the next block in a file. The file is ! 342: * logically divided into sections. The first section is composed of the ! 343: * direct blocks. Each additional section contains fs_maxbpg blocks. ! 344: * ! 345: * If no blocks have been allocated in the first section, the policy is to ! 346: * request a block in the same cylinder group as the inode that describes ! 347: * the file. If no blocks have been allocated in any other section, the ! 348: * policy is to place the section in a cylinder group with a greater than ! 349: * average number of free blocks. An appropriate cylinder group is found ! 350: * by using a rotor that sweeps the cylinder groups. When a new group of ! 351: * blocks is needed, the sweep begins in the cylinder group following the ! 352: * cylinder group from which the previous allocation was made. The sweep ! 353: * continues until a cylinder group with greater than the average number ! 354: * of free blocks is found. If the allocation is for the first block in an ! 355: * indirect block, the information on the previous allocation is unavailable; ! 356: * here a best guess is made based upon the logical block number being ! 357: * allocated. ! 358: * ! 359: * If a section is already partially allocated, the policy is to ! 360: * contiguously allocate fs_maxcontig blocks. The end of one of these ! 361: * contiguous blocks and the beginning of the next is physically separated ! 362: * so that the disk head will be in transit between them for at least ! 363: * fs_rotdelay milliseconds. This is to allow time for the processor to ! 364: * schedule another I/O transfer. ! 365: */ ! 366: daddr_t ! 367: blkpref(ip, lbn, indx, bap) ! 368: struct inode *ip; ! 369: daddr_t lbn; ! 370: int indx; ! 371: daddr_t *bap; ! 372: { ! 373: register struct fs *fs; ! 374: register int cg; ! 375: int avgbfree, startcg; ! 376: daddr_t nextblk; ! 377: ! 378: fs = ip->i_fs; ! 379: if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { ! 380: if (lbn < NDADDR) { ! 381: cg = itog(fs, ip->i_number); ! 382: return (fs->fs_fpg * cg + fs->fs_frag); ! 383: } ! 384: /* ! 385: * Find a cylinder with greater than average number of ! 386: * unused data blocks. ! 387: */ ! 388: if (indx == 0 || bap[indx - 1] == 0) ! 389: startcg = itog(fs, ip->i_number) + lbn / fs->fs_maxbpg; ! 390: else ! 391: startcg = dtog(fs, bap[indx - 1]) + 1; ! 392: startcg %= fs->fs_ncg; ! 393: avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; ! 394: for (cg = startcg; cg < fs->fs_ncg; cg++) ! 395: if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { ! 396: fs->fs_cgrotor = cg; ! 397: return (fs->fs_fpg * cg + fs->fs_frag); ! 398: } ! 399: for (cg = 0; cg <= startcg; cg++) ! 400: if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { ! 401: fs->fs_cgrotor = cg; ! 402: return (fs->fs_fpg * cg + fs->fs_frag); ! 403: } ! 404: return (NULL); ! 405: } ! 406: /* ! 407: * One or more previous blocks have been laid out. If less ! 408: * than fs_maxcontig previous blocks are contiguous, the ! 409: * next block is requested contiguously, otherwise it is ! 410: * requested rotationally delayed by fs_rotdelay milliseconds. ! 411: */ ! 412: nextblk = bap[indx - 1] + fs->fs_frag; ! 413: if (indx > fs->fs_maxcontig && ! 414: bap[indx - fs->fs_maxcontig] + blkstofrags(fs, fs->fs_maxcontig) ! 415: != nextblk) ! 416: return (nextblk); ! 417: if (fs->fs_rotdelay != 0) ! 418: /* ! 419: * Here we convert ms of delay to frags as: ! 420: * (frags) = (ms) * (rev/sec) * (sect/rev) / ! 421: * ((sect/frag) * (ms/sec)) ! 422: * then round up to the next block. ! 423: */ ! 424: nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / ! 425: (NSPF(fs) * 1000), fs->fs_frag); ! 426: return (nextblk); ! 427: } ! 428: ! 429: /* ! 430: * Implement the cylinder overflow algorithm. ! 431: * ! 432: * The policy implemented by this algorithm is: ! 433: * 1) allocate the block in its requested cylinder group. ! 434: * 2) quadradically rehash on the cylinder group number. ! 435: * 3) brute force search for a free block. ! 436: */ ! 437: /*VARARGS5*/ ! 438: u_long ! 439: hashalloc(ip, cg, pref, size, allocator) ! 440: struct inode *ip; ! 441: int cg; ! 442: long pref; ! 443: int size; /* size for data blocks, mode for inodes */ ! 444: u_long (*allocator)(); ! 445: { ! 446: register struct fs *fs; ! 447: long result; ! 448: int i, icg = cg; ! 449: ! 450: fs = ip->i_fs; ! 451: /* ! 452: * 1: preferred cylinder group ! 453: */ ! 454: result = (*allocator)(ip, cg, pref, size); ! 455: if (result) ! 456: return (result); ! 457: /* ! 458: * 2: quadratic rehash ! 459: */ ! 460: for (i = 1; i < fs->fs_ncg; i *= 2) { ! 461: cg += i; ! 462: if (cg >= fs->fs_ncg) ! 463: cg -= fs->fs_ncg; ! 464: result = (*allocator)(ip, cg, 0, size); ! 465: if (result) ! 466: return (result); ! 467: } ! 468: /* ! 469: * 3: brute force search ! 470: * Note that we start at i == 2, since 0 was checked initially, ! 471: * and 1 is always checked in the quadratic rehash. ! 472: */ ! 473: cg = (icg + 2) % fs->fs_ncg; ! 474: for (i = 2; i < fs->fs_ncg; i++) { ! 475: result = (*allocator)(ip, cg, 0, size); ! 476: if (result) ! 477: return (result); ! 478: cg++; ! 479: if (cg == fs->fs_ncg) ! 480: cg = 0; ! 481: } ! 482: return (NULL); ! 483: } ! 484: ! 485: /* ! 486: * Determine whether a fragment can be extended. ! 487: * ! 488: * Check to see if the necessary fragments are available, and ! 489: * if they are, allocate them. ! 490: */ ! 491: daddr_t ! 492: fragextend(ip, cg, bprev, osize, nsize) ! 493: struct inode *ip; ! 494: int cg; ! 495: long bprev; ! 496: int osize, nsize; ! 497: { ! 498: register struct fs *fs; ! 499: register struct cg *cgp; ! 500: struct buf *bp; ! 501: long bno; ! 502: int frags, bbase; ! 503: int i, error; ! 504: ! 505: fs = ip->i_fs; ! 506: if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) ! 507: return (NULL); ! 508: frags = numfrags(fs, nsize); ! 509: bbase = fragnum(fs, bprev); ! 510: if (bbase > fragnum(fs, (bprev + frags - 1))) { ! 511: /* cannot extend across a block boundary */ ! 512: return (NULL); ! 513: } ! 514: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), ! 515: (int)fs->fs_cgsize, NOCRED, &bp); ! 516: if (error) { ! 517: brelse(bp); ! 518: return (NULL); ! 519: } ! 520: cgp = bp->b_un.b_cg; ! 521: if (!cg_chkmagic(cgp)) { ! 522: brelse(bp); ! 523: return (NULL); ! 524: } ! 525: cgp->cg_time = time.tv_sec; ! 526: bno = dtogd(fs, bprev); ! 527: for (i = numfrags(fs, osize); i < frags; i++) ! 528: if (isclr(cg_blksfree(cgp), bno + i)) { ! 529: brelse(bp); ! 530: return (NULL); ! 531: } ! 532: /* ! 533: * the current fragment can be extended ! 534: * deduct the count on fragment being extended into ! 535: * increase the count on the remaining fragment (if any) ! 536: * allocate the extended piece ! 537: */ ! 538: for (i = frags; i < fs->fs_frag - bbase; i++) ! 539: if (isclr(cg_blksfree(cgp), bno + i)) ! 540: break; ! 541: cgp->cg_frsum[i - numfrags(fs, osize)]--; ! 542: if (i != frags) ! 543: cgp->cg_frsum[i - frags]++; ! 544: for (i = numfrags(fs, osize); i < frags; i++) { ! 545: clrbit(cg_blksfree(cgp), bno + i); ! 546: cgp->cg_cs.cs_nffree--; ! 547: fs->fs_cstotal.cs_nffree--; ! 548: fs->fs_cs(fs, cg).cs_nffree--; ! 549: } ! 550: fs->fs_fmod++; ! 551: bdwrite(bp); ! 552: return (bprev); ! 553: } ! 554: ! 555: /* ! 556: * Determine whether a block can be allocated. ! 557: * ! 558: * Check to see if a block of the apprpriate size is available, ! 559: * and if it is, allocate it. ! 560: */ ! 561: daddr_t ! 562: alloccg(ip, cg, bpref, size) ! 563: struct inode *ip; ! 564: int cg; ! 565: daddr_t bpref; ! 566: int size; ! 567: { ! 568: register struct fs *fs; ! 569: register struct cg *cgp; ! 570: struct buf *bp; ! 571: register int i; ! 572: int error, bno, frags, allocsiz; ! 573: ! 574: fs = ip->i_fs; ! 575: if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) ! 576: return (NULL); ! 577: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), ! 578: (int)fs->fs_cgsize, NOCRED, &bp); ! 579: if (error) { ! 580: brelse(bp); ! 581: return (NULL); ! 582: } ! 583: cgp = bp->b_un.b_cg; ! 584: if (!cg_chkmagic(cgp) || ! 585: (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { ! 586: brelse(bp); ! 587: return (NULL); ! 588: } ! 589: cgp->cg_time = time.tv_sec; ! 590: if (size == fs->fs_bsize) { ! 591: bno = alloccgblk(fs, cgp, bpref); ! 592: bdwrite(bp); ! 593: return (bno); ! 594: } ! 595: /* ! 596: * check to see if any fragments are already available ! 597: * allocsiz is the size which will be allocated, hacking ! 598: * it down to a smaller size if necessary ! 599: */ ! 600: frags = numfrags(fs, size); ! 601: for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) ! 602: if (cgp->cg_frsum[allocsiz] != 0) ! 603: break; ! 604: if (allocsiz == fs->fs_frag) { ! 605: /* ! 606: * no fragments were available, so a block will be ! 607: * allocated, and hacked up ! 608: */ ! 609: if (cgp->cg_cs.cs_nbfree == 0) { ! 610: brelse(bp); ! 611: return (NULL); ! 612: } ! 613: bno = alloccgblk(fs, cgp, bpref); ! 614: bpref = dtogd(fs, bno); ! 615: for (i = frags; i < fs->fs_frag; i++) ! 616: setbit(cg_blksfree(cgp), bpref + i); ! 617: i = fs->fs_frag - frags; ! 618: cgp->cg_cs.cs_nffree += i; ! 619: fs->fs_cstotal.cs_nffree += i; ! 620: fs->fs_cs(fs, cg).cs_nffree += i; ! 621: fs->fs_fmod++; ! 622: cgp->cg_frsum[i]++; ! 623: bdwrite(bp); ! 624: return (bno); ! 625: } ! 626: bno = mapsearch(fs, cgp, bpref, allocsiz); ! 627: if (bno < 0) { ! 628: brelse(bp); ! 629: return (NULL); ! 630: } ! 631: for (i = 0; i < frags; i++) ! 632: clrbit(cg_blksfree(cgp), bno + i); ! 633: cgp->cg_cs.cs_nffree -= frags; ! 634: fs->fs_cstotal.cs_nffree -= frags; ! 635: fs->fs_cs(fs, cg).cs_nffree -= frags; ! 636: fs->fs_fmod++; ! 637: cgp->cg_frsum[allocsiz]--; ! 638: if (frags != allocsiz) ! 639: cgp->cg_frsum[allocsiz - frags]++; ! 640: bdwrite(bp); ! 641: return (cg * fs->fs_fpg + bno); ! 642: } ! 643: ! 644: /* ! 645: * Allocate a block in a cylinder group. ! 646: * ! 647: * This algorithm implements the following policy: ! 648: * 1) allocate the requested block. ! 649: * 2) allocate a rotationally optimal block in the same cylinder. ! 650: * 3) allocate the next available block on the block rotor for the ! 651: * specified cylinder group. ! 652: * Note that this routine only allocates fs_bsize blocks; these ! 653: * blocks may be fragmented by the routine that allocates them. ! 654: */ ! 655: daddr_t ! 656: alloccgblk(fs, cgp, bpref) ! 657: register struct fs *fs; ! 658: register struct cg *cgp; ! 659: daddr_t bpref; ! 660: { ! 661: daddr_t bno; ! 662: int cylno, pos, delta; ! 663: short *cylbp; ! 664: register int i; ! 665: ! 666: if (bpref == 0) { ! 667: bpref = cgp->cg_rotor; ! 668: goto norot; ! 669: } ! 670: bpref = blknum(fs, bpref); ! 671: bpref = dtogd(fs, bpref); ! 672: /* ! 673: * if the requested block is available, use it ! 674: */ ! 675: if (isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) { ! 676: bno = bpref; ! 677: goto gotit; ! 678: } ! 679: /* ! 680: * check for a block available on the same cylinder ! 681: */ ! 682: cylno = cbtocylno(fs, bpref); ! 683: if (cg_blktot(cgp)[cylno] == 0) ! 684: goto norot; ! 685: if (fs->fs_cpc == 0) { ! 686: /* ! 687: * block layout info is not available, so just have ! 688: * to take any block in this cylinder. ! 689: */ ! 690: bpref = howmany(fs->fs_spc * cylno, NSPF(fs)); ! 691: goto norot; ! 692: } ! 693: /* ! 694: * check the summary information to see if a block is ! 695: * available in the requested cylinder starting at the ! 696: * requested rotational position and proceeding around. ! 697: */ ! 698: cylbp = cg_blks(fs, cgp, cylno); ! 699: pos = cbtorpos(fs, bpref); ! 700: for (i = pos; i < fs->fs_nrpos; i++) ! 701: if (cylbp[i] > 0) ! 702: break; ! 703: if (i == fs->fs_nrpos) ! 704: for (i = 0; i < pos; i++) ! 705: if (cylbp[i] > 0) ! 706: break; ! 707: if (cylbp[i] > 0) { ! 708: /* ! 709: * found a rotational position, now find the actual ! 710: * block. A panic if none is actually there. ! 711: */ ! 712: pos = cylno % fs->fs_cpc; ! 713: bno = (cylno - pos) * fs->fs_spc / NSPB(fs); ! 714: if (fs_postbl(fs, pos)[i] == -1) { ! 715: printf("pos = %d, i = %d, fs = %s\n", ! 716: pos, i, fs->fs_fsmnt); ! 717: panic("alloccgblk: cyl groups corrupted"); ! 718: } ! 719: for (i = fs_postbl(fs, pos)[i];; ) { ! 720: if (isblock(fs, cg_blksfree(cgp), bno + i)) { ! 721: bno = blkstofrags(fs, (bno + i)); ! 722: goto gotit; ! 723: } ! 724: delta = fs_rotbl(fs)[i]; ! 725: if (delta <= 0 || ! 726: delta + i > fragstoblks(fs, fs->fs_fpg)) ! 727: break; ! 728: i += delta; ! 729: } ! 730: printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); ! 731: panic("alloccgblk: can't find blk in cyl"); ! 732: } ! 733: norot: ! 734: /* ! 735: * no blocks in the requested cylinder, so take next ! 736: * available one in this cylinder group. ! 737: */ ! 738: bno = mapsearch(fs, cgp, bpref, (int)fs->fs_frag); ! 739: if (bno < 0) ! 740: return (NULL); ! 741: cgp->cg_rotor = bno; ! 742: gotit: ! 743: clrblock(fs, cg_blksfree(cgp), (long)fragstoblks(fs, bno)); ! 744: cgp->cg_cs.cs_nbfree--; ! 745: fs->fs_cstotal.cs_nbfree--; ! 746: fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; ! 747: cylno = cbtocylno(fs, bno); ! 748: cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; ! 749: cg_blktot(cgp)[cylno]--; ! 750: fs->fs_fmod++; ! 751: return (cgp->cg_cgx * fs->fs_fpg + bno); ! 752: } ! 753: ! 754: /* ! 755: * Determine whether an inode can be allocated. ! 756: * ! 757: * Check to see if an inode is available, and if it is, ! 758: * allocate it using the following policy: ! 759: * 1) allocate the requested inode. ! 760: * 2) allocate the next available inode after the requested ! 761: * inode in the specified cylinder group. ! 762: */ ! 763: ino_t ! 764: ialloccg(ip, cg, ipref, mode) ! 765: struct inode *ip; ! 766: int cg; ! 767: daddr_t ipref; ! 768: int mode; ! 769: { ! 770: register struct fs *fs; ! 771: register struct cg *cgp; ! 772: struct buf *bp; ! 773: int error, start, len, loc, map, i; ! 774: ! 775: fs = ip->i_fs; ! 776: if (fs->fs_cs(fs, cg).cs_nifree == 0) ! 777: return (NULL); ! 778: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), ! 779: (int)fs->fs_cgsize, NOCRED, &bp); ! 780: if (error) { ! 781: brelse(bp); ! 782: return (NULL); ! 783: } ! 784: cgp = bp->b_un.b_cg; ! 785: if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { ! 786: brelse(bp); ! 787: return (NULL); ! 788: } ! 789: cgp->cg_time = time.tv_sec; ! 790: if (ipref) { ! 791: ipref %= fs->fs_ipg; ! 792: if (isclr(cg_inosused(cgp), ipref)) ! 793: goto gotit; ! 794: } ! 795: start = cgp->cg_irotor / NBBY; ! 796: len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); ! 797: loc = skpc(0xff, len, &cg_inosused(cgp)[start]); ! 798: if (loc == 0) { ! 799: len = start + 1; ! 800: start = 0; ! 801: loc = skpc(0xff, len, &cg_inosused(cgp)[0]); ! 802: if (loc == 0) { ! 803: printf("cg = %s, irotor = %d, fs = %s\n", ! 804: cg, cgp->cg_irotor, fs->fs_fsmnt); ! 805: panic("ialloccg: map corrupted"); ! 806: /* NOTREACHED */ ! 807: } ! 808: } ! 809: i = start + len - loc; ! 810: map = cg_inosused(cgp)[i]; ! 811: ipref = i * NBBY; ! 812: for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { ! 813: if ((map & i) == 0) { ! 814: cgp->cg_irotor = ipref; ! 815: goto gotit; ! 816: } ! 817: } ! 818: printf("fs = %s\n", fs->fs_fsmnt); ! 819: panic("ialloccg: block not in map"); ! 820: /* NOTREACHED */ ! 821: gotit: ! 822: setbit(cg_inosused(cgp), ipref); ! 823: cgp->cg_cs.cs_nifree--; ! 824: fs->fs_cstotal.cs_nifree--; ! 825: fs->fs_cs(fs, cg).cs_nifree--; ! 826: fs->fs_fmod++; ! 827: if ((mode & IFMT) == IFDIR) { ! 828: cgp->cg_cs.cs_ndir++; ! 829: fs->fs_cstotal.cs_ndir++; ! 830: fs->fs_cs(fs, cg).cs_ndir++; ! 831: } ! 832: bdwrite(bp); ! 833: return (cg * fs->fs_ipg + ipref); ! 834: } ! 835: ! 836: /* ! 837: * Free a block or fragment. ! 838: * ! 839: * The specified block or fragment is placed back in the ! 840: * free map. If a fragment is deallocated, a possible ! 841: * block reassembly is checked. ! 842: */ ! 843: blkfree(ip, bno, size) ! 844: register struct inode *ip; ! 845: daddr_t bno; ! 846: off_t size; ! 847: { ! 848: register struct fs *fs; ! 849: register struct cg *cgp; ! 850: struct buf *bp; ! 851: int error, cg, blk, frags, bbase; ! 852: register int i; ! 853: struct ucred *cred = u.u_cred; /* XXX */ ! 854: ! 855: fs = ip->i_fs; ! 856: if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) { ! 857: printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", ! 858: ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); ! 859: panic("blkfree: bad size"); ! 860: } ! 861: cg = dtog(fs, bno); ! 862: if ((unsigned)bno >= fs->fs_size) { ! 863: printf("bad block %d, ino %d\n", bno, ip->i_number); ! 864: fserr(fs, cred->cr_uid, "bad block"); ! 865: return; ! 866: } ! 867: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), ! 868: (int)fs->fs_cgsize, NOCRED, &bp); ! 869: if (error) { ! 870: brelse(bp); ! 871: return; ! 872: } ! 873: cgp = bp->b_un.b_cg; ! 874: if (!cg_chkmagic(cgp)) { ! 875: brelse(bp); ! 876: return; ! 877: } ! 878: cgp->cg_time = time.tv_sec; ! 879: bno = dtogd(fs, bno); ! 880: if (size == fs->fs_bsize) { ! 881: if (isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno))) { ! 882: printf("dev = 0x%x, block = %d, fs = %s\n", ! 883: ip->i_dev, bno, fs->fs_fsmnt); ! 884: panic("blkfree: freeing free block"); ! 885: } ! 886: setblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno)); ! 887: cgp->cg_cs.cs_nbfree++; ! 888: fs->fs_cstotal.cs_nbfree++; ! 889: fs->fs_cs(fs, cg).cs_nbfree++; ! 890: i = cbtocylno(fs, bno); ! 891: cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; ! 892: cg_blktot(cgp)[i]++; ! 893: } else { ! 894: bbase = bno - fragnum(fs, bno); ! 895: /* ! 896: * decrement the counts associated with the old frags ! 897: */ ! 898: blk = blkmap(fs, cg_blksfree(cgp), bbase); ! 899: fragacct(fs, blk, cgp->cg_frsum, -1); ! 900: /* ! 901: * deallocate the fragment ! 902: */ ! 903: frags = numfrags(fs, size); ! 904: for (i = 0; i < frags; i++) { ! 905: if (isset(cg_blksfree(cgp), bno + i)) { ! 906: printf("dev = 0x%x, block = %d, fs = %s\n", ! 907: ip->i_dev, bno + i, fs->fs_fsmnt); ! 908: panic("blkfree: freeing free frag"); ! 909: } ! 910: setbit(cg_blksfree(cgp), bno + i); ! 911: } ! 912: cgp->cg_cs.cs_nffree += i; ! 913: fs->fs_cstotal.cs_nffree += i; ! 914: fs->fs_cs(fs, cg).cs_nffree += i; ! 915: /* ! 916: * add back in counts associated with the new frags ! 917: */ ! 918: blk = blkmap(fs, cg_blksfree(cgp), bbase); ! 919: fragacct(fs, blk, cgp->cg_frsum, 1); ! 920: /* ! 921: * if a complete block has been reassembled, account for it ! 922: */ ! 923: if (isblock(fs, cg_blksfree(cgp), ! 924: (daddr_t)fragstoblks(fs, bbase))) { ! 925: cgp->cg_cs.cs_nffree -= fs->fs_frag; ! 926: fs->fs_cstotal.cs_nffree -= fs->fs_frag; ! 927: fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; ! 928: cgp->cg_cs.cs_nbfree++; ! 929: fs->fs_cstotal.cs_nbfree++; ! 930: fs->fs_cs(fs, cg).cs_nbfree++; ! 931: i = cbtocylno(fs, bbase); ! 932: cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; ! 933: cg_blktot(cgp)[i]++; ! 934: } ! 935: } ! 936: fs->fs_fmod++; ! 937: bdwrite(bp); ! 938: } ! 939: ! 940: /* ! 941: * Free an inode. ! 942: * ! 943: * The specified inode is placed back in the free map. ! 944: */ ! 945: ifree(ip, ino, mode) ! 946: struct inode *ip; ! 947: ino_t ino; ! 948: int mode; ! 949: { ! 950: register struct fs *fs; ! 951: register struct cg *cgp; ! 952: struct buf *bp; ! 953: int error, cg; ! 954: ! 955: fs = ip->i_fs; ! 956: if ((unsigned)ino >= fs->fs_ipg*fs->fs_ncg) { ! 957: printf("dev = 0x%x, ino = %d, fs = %s\n", ! 958: ip->i_dev, ino, fs->fs_fsmnt); ! 959: panic("ifree: range"); ! 960: } ! 961: cg = itog(fs, ino); ! 962: error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), ! 963: (int)fs->fs_cgsize, NOCRED, &bp); ! 964: if (error) { ! 965: brelse(bp); ! 966: return; ! 967: } ! 968: cgp = bp->b_un.b_cg; ! 969: if (!cg_chkmagic(cgp)) { ! 970: brelse(bp); ! 971: return; ! 972: } ! 973: cgp->cg_time = time.tv_sec; ! 974: ino %= fs->fs_ipg; ! 975: if (isclr(cg_inosused(cgp), ino)) { ! 976: printf("dev = 0x%x, ino = %d, fs = %s\n", ! 977: ip->i_dev, ino, fs->fs_fsmnt); ! 978: panic("ifree: freeing free inode"); ! 979: } ! 980: clrbit(cg_inosused(cgp), ino); ! 981: if (ino < cgp->cg_irotor) ! 982: cgp->cg_irotor = ino; ! 983: cgp->cg_cs.cs_nifree++; ! 984: fs->fs_cstotal.cs_nifree++; ! 985: fs->fs_cs(fs, cg).cs_nifree++; ! 986: if ((mode & IFMT) == IFDIR) { ! 987: cgp->cg_cs.cs_ndir--; ! 988: fs->fs_cstotal.cs_ndir--; ! 989: fs->fs_cs(fs, cg).cs_ndir--; ! 990: } ! 991: fs->fs_fmod++; ! 992: bdwrite(bp); ! 993: } ! 994: ! 995: /* ! 996: * Find a block of the specified size in the specified cylinder group. ! 997: * ! 998: * It is a panic if a request is made to find a block if none are ! 999: * available. ! 1000: */ ! 1001: daddr_t ! 1002: mapsearch(fs, cgp, bpref, allocsiz) ! 1003: register struct fs *fs; ! 1004: register struct cg *cgp; ! 1005: daddr_t bpref; ! 1006: int allocsiz; ! 1007: { ! 1008: daddr_t bno; ! 1009: int start, len, loc, i; ! 1010: int blk, field, subfield, pos; ! 1011: ! 1012: /* ! 1013: * find the fragment by searching through the free block ! 1014: * map for an appropriate bit pattern ! 1015: */ ! 1016: if (bpref) ! 1017: start = dtogd(fs, bpref) / NBBY; ! 1018: else ! 1019: start = cgp->cg_frotor / NBBY; ! 1020: len = howmany(fs->fs_fpg, NBBY) - start; ! 1021: loc = scanc((unsigned)len, (u_char *)&cg_blksfree(cgp)[start], ! 1022: (u_char *)fragtbl[fs->fs_frag], ! 1023: (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); ! 1024: if (loc == 0) { ! 1025: len = start + 1; ! 1026: start = 0; ! 1027: loc = scanc((unsigned)len, (u_char *)&cg_blksfree(cgp)[0], ! 1028: (u_char *)fragtbl[fs->fs_frag], ! 1029: (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); ! 1030: if (loc == 0) { ! 1031: printf("start = %d, len = %d, fs = %s\n", ! 1032: start, len, fs->fs_fsmnt); ! 1033: panic("alloccg: map corrupted"); ! 1034: /* NOTREACHED */ ! 1035: } ! 1036: } ! 1037: bno = (start + len - loc) * NBBY; ! 1038: cgp->cg_frotor = bno; ! 1039: /* ! 1040: * found the byte in the map ! 1041: * sift through the bits to find the selected frag ! 1042: */ ! 1043: for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { ! 1044: blk = blkmap(fs, cg_blksfree(cgp), bno); ! 1045: blk <<= 1; ! 1046: field = around[allocsiz]; ! 1047: subfield = inside[allocsiz]; ! 1048: for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { ! 1049: if ((blk & field) == subfield) ! 1050: return (bno + pos); ! 1051: field <<= 1; ! 1052: subfield <<= 1; ! 1053: } ! 1054: } ! 1055: printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt); ! 1056: panic("alloccg: block not in map"); ! 1057: return (-1); ! 1058: } ! 1059: ! 1060: /* ! 1061: * Fserr prints the name of a file system with an error diagnostic. ! 1062: * ! 1063: * The form of the error message is: ! 1064: * fs: error message ! 1065: */ ! 1066: fserr(fs, uid, cp) ! 1067: struct fs *fs; ! 1068: uid_t uid; ! 1069: char *cp; ! 1070: { ! 1071: ! 1072: log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->fs_fsmnt, cp); ! 1073: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.