1 /* Copyright (c) 1981 Regents of the University of California */ 2 3 static char vers[] = "@(#)lfs_alloc.c 2.1 03/25/82"; 4 5 /* alloc.c 4.8 81/03/08 */ 6 7 #include "../h/param.h" 8 #include "../h/systm.h" 9 #include "../h/mount.h" 10 #include "../h/fs.h" 11 #include "../h/conf.h" 12 #include "../h/buf.h" 13 #include "../h/inode.h" 14 #include "../h/ndir.h" 15 #include "../h/user.h" 16 17 extern u_long hashalloc(); 18 extern ino_t ialloccg(); 19 extern daddr_t alloccg(); 20 extern daddr_t alloccgblk(); 21 extern daddr_t fragextend(); 22 extern daddr_t blkpref(); 23 extern daddr_t mapsearch(); 24 extern int inside[], around[]; 25 extern unsigned char *fragtbl[]; 26 27 /* 28 * Allocate a block in the file system. 29 * 30 * The size of the requested block is given, which must be some 31 * multiple of fs_fsize and <= fs_bsize. 32 * A preference may be optionally specified. If a preference is given 33 * the following hierarchy is used to allocate a block: 34 * 1) allocate the requested block. 35 * 2) allocate a rotationally optimal block in the same cylinder. 36 * 3) allocate a block in the same cylinder group. 37 * 4) quadradically rehash into other cylinder groups, until an 38 * available block is located. 39 * If no block preference is given the following heirarchy is used 40 * to allocate a block: 41 * 1) allocate a block in the cylinder group that contains the 42 * inode for the file. 43 * 2) quadradically rehash into other cylinder groups, until an 44 * available block is located. 45 */ 46 struct buf * 47 alloc(ip, bpref, size) 48 register struct inode *ip; 49 daddr_t bpref; 50 int size; 51 { 52 daddr_t bno; 53 register struct fs *fs; 54 register struct buf *bp; 55 int cg; 56 57 fs = ip->i_fs; 58 if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) 59 panic("alloc: bad size"); 60 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 61 goto nospace; 62 if (u.u_uid != 0 && 63 fs->fs_cstotal.cs_nbfree * fs->fs_frag + fs->fs_cstotal.cs_nffree < 64 fs->fs_dsize * fs->fs_minfree / 100) 65 goto nospace; 66 if (bpref >= fs->fs_size) 67 bpref = 0; 68 if (bpref == 0) 69 cg = itog(fs, ip->i_number); 70 else 71 cg = dtog(fs, bpref); 72 bno = (daddr_t)hashalloc(ip, cg, (long)bpref, size, alloccg); 73 if (bno == 0) 74 goto nospace; 75 bp = getblk(ip->i_dev, fsbtodb(fs, bno), size); 76 clrbuf(bp); 77 return (bp); 78 nospace: 79 fserr(fs, "file system full"); 80 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 81 u.u_error = ENOSPC; 82 return (NULL); 83 } 84 85 /* 86 * Reallocate a fragment to a bigger size 87 * 88 * The number and size of the old block is given, and a preference 89 * and new size is also specified. The allocator attempts to extend 90 * the original block. Failing that, the regular block allocator is 91 * invoked to get an appropriate block. 92 */ 93 struct buf * 94 realloccg(ip, bprev, bpref, osize, nsize) 95 register struct inode *ip; 96 daddr_t bprev, bpref; 97 int osize, nsize; 98 { 99 daddr_t bno; 100 register struct fs *fs; 101 register struct buf *bp, *obp; 102 caddr_t cp; 103 int cg; 104 105 fs = ip->i_fs; 106 if ((unsigned)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 107 (unsigned)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) 108 panic("realloccg: bad size"); 109 if (u.u_uid != 0 && 110 fs->fs_cstotal.cs_nbfree * fs->fs_frag + fs->fs_cstotal.cs_nffree < 111 fs->fs_dsize * fs->fs_minfree / 100) 112 goto nospace; 113 if (bprev == 0) 114 panic("realloccg: bad bprev"); 115 cg = dtog(fs, bprev); 116 bno = fragextend(ip, cg, (long)bprev, osize, nsize); 117 if (bno != 0) { 118 bp = bread(ip->i_dev, fsbtodb(fs, bno), osize); 119 if (bp->b_flags & B_ERROR) { 120 brelse(bp); 121 return (NULL); 122 } 123 bp->b_bcount = nsize; 124 blkclr(bp->b_un.b_addr + osize, nsize - osize); 125 return (bp); 126 } 127 if (bpref >= fs->fs_size) 128 bpref = 0; 129 bno = (daddr_t)hashalloc(ip, cg, (long)bpref, nsize, alloccg); 130 if (bno != 0) { 131 /* 132 * make a new copy 133 */ 134 obp = bread(ip->i_dev, fsbtodb(fs, bprev), osize); 135 if (obp->b_flags & B_ERROR) { 136 brelse(obp); 137 return (NULL); 138 } 139 bp = getblk(ip->i_dev, fsbtodb(fs, bno), nsize); 140 cp = bp->b_un.b_addr; 141 bp->b_un.b_addr = obp->b_un.b_addr; 142 obp->b_un.b_addr = cp; 143 obp->b_flags |= B_INVAL; 144 brelse(obp); 145 fre(ip, bprev, (off_t)osize); 146 blkclr(bp->b_un.b_addr + osize, nsize - osize); 147 return (bp); 148 } 149 nospace: 150 /* 151 * no space available 152 */ 153 fserr(fs, "file system full"); 154 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 155 u.u_error = ENOSPC; 156 return (NULL); 157 } 158 159 /* 160 * Allocate an inode in the file system. 161 * 162 * A preference may be optionally specified. If a preference is given 163 * the following hierarchy is used to allocate an inode: 164 * 1) allocate the requested inode. 165 * 2) allocate an inode in the same cylinder group. 166 * 3) quadradically rehash into other cylinder groups, until an 167 * available inode is located. 168 * If no inode preference is given the following heirarchy is used 169 * to allocate an inode: 170 * 1) allocate an inode in cylinder group 0. 171 * 2) quadradically rehash into other cylinder groups, until an 172 * available inode is located. 173 */ 174 struct inode * 175 ialloc(pip, ipref, mode) 176 register struct inode *pip; 177 ino_t ipref; 178 int mode; 179 { 180 ino_t ino; 181 register struct fs *fs; 182 register struct inode *ip; 183 int cg; 184 185 fs = pip->i_fs; 186 if (fs->fs_cstotal.cs_nifree == 0) 187 goto noinodes; 188 if (ipref >= fs->fs_ncg * fs->fs_ipg) 189 ipref = 0; 190 cg = itog(fs, ipref); 191 ino = (ino_t)hashalloc(pip, cg, (long)ipref, mode, ialloccg); 192 if (ino == 0) 193 goto noinodes; 194 ip = iget(pip->i_dev, pip->i_fs, ino); 195 if (ip == NULL) { 196 ifree(ip, ino, 0); 197 return (NULL); 198 } 199 if (ip->i_mode) 200 panic("ialloc: dup alloc"); 201 return (ip); 202 noinodes: 203 fserr(fs, "out of inodes"); 204 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 205 u.u_error = ENOSPC; 206 return (NULL); 207 } 208 209 /* 210 * Find a cylinder to place a directory. 211 * 212 * The policy implemented by this algorithm is to select from 213 * among those cylinder groups with above the average number of 214 * free inodes, the one with the smallest number of directories. 215 */ 216 dirpref(fs) 217 register struct fs *fs; 218 { 219 int cg, minndir, mincg, avgifree; 220 221 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 222 minndir = fs->fs_ipg; 223 mincg = 0; 224 for (cg = 0; cg < fs->fs_ncg; cg++) 225 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 226 fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 227 mincg = cg; 228 minndir = fs->fs_cs(fs, cg).cs_ndir; 229 } 230 return (fs->fs_ipg * mincg); 231 } 232 233 /* 234 * Select a cylinder to place a large block of data. 235 * 236 * The policy implemented by this algorithm is to maintain a 237 * rotor that sweeps the cylinder groups. When a block is 238 * needed, the rotor is advanced until a cylinder group with 239 * greater than the average number of free blocks is found. 240 */ 241 daddr_t 242 blkpref(fs) 243 register struct fs *fs; 244 { 245 int cg, avgbfree; 246 247 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 248 for (cg = fs->fs_cgrotor + 1; cg < fs->fs_ncg; cg++) 249 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 250 fs->fs_cgrotor = cg; 251 return (fs->fs_fpg * cg + fs->fs_frag); 252 } 253 for (cg = 0; cg <= fs->fs_cgrotor; cg++) 254 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 255 fs->fs_cgrotor = cg; 256 return (fs->fs_fpg * cg + fs->fs_frag); 257 } 258 return (NULL); 259 } 260 261 /* 262 * Implement the cylinder overflow algorithm. 263 * 264 * The policy implemented by this algorithm is: 265 * 1) allocate the block in its requested cylinder group. 266 * 2) quadradically rehash on the cylinder group number. 267 * 3) brute force search for a free block. 268 */ 269 /*VARARGS5*/ 270 u_long 271 hashalloc(ip, cg, pref, size, allocator) 272 struct inode *ip; 273 int cg; 274 long pref; 275 int size; /* size for data blocks, mode for inodes */ 276 u_long (*allocator)(); 277 { 278 register struct fs *fs; 279 long result; 280 int i, icg = cg; 281 282 fs = ip->i_fs; 283 /* 284 * 1: preferred cylinder group 285 */ 286 result = (*allocator)(ip, cg, pref, size); 287 if (result) 288 return (result); 289 /* 290 * 2: quadratic rehash 291 */ 292 for (i = 1; i < fs->fs_ncg; i *= 2) { 293 cg += i; 294 if (cg >= fs->fs_ncg) 295 cg -= fs->fs_ncg; 296 result = (*allocator)(ip, cg, 0, size); 297 if (result) 298 return (result); 299 } 300 /* 301 * 3: brute force search 302 */ 303 cg = icg; 304 for (i = 0; i < fs->fs_ncg; i++) { 305 result = (*allocator)(ip, cg, 0, size); 306 if (result) 307 return (result); 308 cg++; 309 if (cg == fs->fs_ncg) 310 cg = 0; 311 } 312 return (NULL); 313 } 314 315 /* 316 * Determine whether a fragment can be extended. 317 * 318 * Check to see if the necessary fragments are available, and 319 * if they are, allocate them. 320 */ 321 daddr_t 322 fragextend(ip, cg, bprev, osize, nsize) 323 struct inode *ip; 324 int cg; 325 long bprev; 326 int osize, nsize; 327 { 328 register struct fs *fs; 329 register struct buf *bp; 330 register struct cg *cgp; 331 long bno; 332 int frags, bbase; 333 int i; 334 335 fs = ip->i_fs; 336 frags = numfrags(fs, nsize); 337 bbase = fragoff(fs, bprev); 338 if (bbase > (bprev + frags - 1) % fs->fs_frag) { 339 /* cannot extend across a block boundry */ 340 return (NULL); 341 } 342 bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), fs->fs_bsize); 343 if (bp->b_flags & B_ERROR) { 344 brelse(bp); 345 return (NULL); 346 } 347 cgp = bp->b_un.b_cg; 348 bno = dtogd(fs, bprev); 349 for (i = numfrags(fs, osize); i < frags; i++) 350 if (isclr(cgp->cg_free, bno + i)) { 351 brelse(bp); 352 return (NULL); 353 } 354 /* 355 * the current fragment can be extended 356 * deduct the count on fragment being extended into 357 * increase the count on the remaining fragment (if any) 358 * allocate the extended piece 359 */ 360 for (i = frags; i < fs->fs_frag - bbase; i++) 361 if (isclr(cgp->cg_free, bno + i)) 362 break; 363 cgp->cg_frsum[i - numfrags(fs, osize)]--; 364 if (i != frags) 365 cgp->cg_frsum[i - frags]++; 366 for (i = numfrags(fs, osize); i < frags; i++) { 367 clrbit(cgp->cg_free, bno + i); 368 cgp->cg_cs.cs_nffree--; 369 fs->fs_cstotal.cs_nffree--; 370 fs->fs_cs(fs, cg).cs_nffree--; 371 } 372 fs->fs_fmod++; 373 bdwrite(bp); 374 return (bprev); 375 } 376 377 /* 378 * Determine whether a block can be allocated. 379 * 380 * Check to see if a block of the apprpriate size is available, 381 * and if it is, allocate it. 382 */ 383 daddr_t 384 alloccg(ip, cg, bpref, size) 385 struct inode *ip; 386 int cg; 387 daddr_t bpref; 388 int size; 389 { 390 register struct fs *fs; 391 register struct buf *bp; 392 register struct cg *cgp; 393 int bno, frags; 394 int allocsiz; 395 register int i; 396 397 fs = ip->i_fs; 398 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 399 return (NULL); 400 bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), fs->fs_bsize); 401 if (bp->b_flags & B_ERROR) { 402 brelse(bp); 403 return (NULL); 404 } 405 cgp = bp->b_un.b_cg; 406 if (size == fs->fs_bsize) { 407 bno = alloccgblk(fs, cgp, bpref); 408 bdwrite(bp); 409 return (bno); 410 } 411 /* 412 * check to see if any fragments are already available 413 * allocsiz is the size which will be allocated, hacking 414 * it down to a smaller size if necessary 415 */ 416 frags = numfrags(fs, size); 417 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 418 if (cgp->cg_frsum[allocsiz] != 0) 419 break; 420 if (allocsiz == fs->fs_frag) { 421 /* 422 * no fragments were available, so a block will be 423 * allocated, and hacked up 424 */ 425 if (cgp->cg_cs.cs_nbfree == 0) { 426 brelse(bp); 427 return (NULL); 428 } 429 bno = alloccgblk(fs, cgp, bpref); 430 bpref = dtogd(fs, bno); 431 for (i = frags; i < fs->fs_frag; i++) 432 setbit(cgp->cg_free, bpref + i); 433 i = fs->fs_frag - frags; 434 cgp->cg_cs.cs_nffree += i; 435 fs->fs_cstotal.cs_nffree += i; 436 fs->fs_cs(fs, cg).cs_nffree += i; 437 cgp->cg_frsum[i]++; 438 bdwrite(bp); 439 return (bno); 440 } 441 bno = mapsearch(fs, cgp, bpref, allocsiz); 442 if (bno == 0) 443 return (NULL); 444 for (i = 0; i < frags; i++) 445 clrbit(cgp->cg_free, bno + i); 446 cgp->cg_cs.cs_nffree -= frags; 447 fs->fs_cstotal.cs_nffree -= frags; 448 fs->fs_cs(fs, cg).cs_nffree -= frags; 449 cgp->cg_frsum[allocsiz]--; 450 if (frags != allocsiz) 451 cgp->cg_frsum[allocsiz - frags]++; 452 bdwrite(bp); 453 return (cg * fs->fs_fpg + bno); 454 } 455 456 /* 457 * Allocate a block in a cylinder group. 458 * 459 * This algorithm implements the following policy: 460 * 1) allocate the requested block. 461 * 2) allocate a rotationally optimal block in the same cylinder. 462 * 3) allocate the next available block on the block rotor for the 463 * specified cylinder group. 464 * Note that this routine only allocates fs_bsize blocks; these 465 * blocks may be fragmented by the routine that allocates them. 466 */ 467 daddr_t 468 alloccgblk(fs, cgp, bpref) 469 register struct fs *fs; 470 register struct cg *cgp; 471 daddr_t bpref; 472 { 473 daddr_t bno; 474 int cylno, pos, delta; 475 short *cylbp; 476 register int i; 477 478 if (bpref == 0) { 479 bpref = cgp->cg_rotor; 480 goto norot; 481 } 482 bpref &= ~(fs->fs_frag - 1); 483 bpref = dtogd(fs, bpref); 484 /* 485 * if the requested block is available, use it 486 */ 487 if (isblock(fs, cgp->cg_free, bpref/fs->fs_frag)) { 488 bno = bpref; 489 goto gotit; 490 } 491 /* 492 * check for a block available on the same cylinder 493 */ 494 cylno = cbtocylno(fs, bpref); 495 if (cgp->cg_btot[cylno] == 0) 496 goto norot; 497 if (fs->fs_cpc == 0) { 498 /* 499 * block layout info is not available, so just have 500 * to take any block in this cylinder. 501 */ 502 bpref = howmany(fs->fs_spc * cylno, NSPF(fs)); 503 goto norot; 504 } 505 /* 506 * find a block that is rotationally optimal 507 */ 508 cylbp = cgp->cg_b[cylno]; 509 if (fs->fs_rotdelay == 0) { 510 pos = cbtorpos(fs, bpref); 511 } else { 512 /* 513 * here we convert ms of delay to frags as: 514 * (frags) = (ms) * (rev/sec) * (sect/rev) / 515 * ((sect/frag) * (ms/sec)) 516 * then round up to the next rotational position 517 */ 518 bpref += fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 519 (NSPF(fs) * 1000); 520 pos = cbtorpos(fs, bpref); 521 pos = (pos + 1) % NRPOS; 522 } 523 /* 524 * check the summary information to see if a block is 525 * available in the requested cylinder starting at the 526 * optimal rotational position and proceeding around. 527 */ 528 for (i = pos; i < NRPOS; i++) 529 if (cylbp[i] > 0) 530 break; 531 if (i == NRPOS) 532 for (i = 0; i < pos; i++) 533 if (cylbp[i] > 0) 534 break; 535 if (cylbp[i] > 0) { 536 /* 537 * found a rotational position, now find the actual 538 * block. A panic if none is actually there. 539 */ 540 pos = cylno % fs->fs_cpc; 541 bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 542 if (fs->fs_postbl[pos][i] == -1) 543 panic("alloccgblk: cyl groups corrupted"); 544 for (i = fs->fs_postbl[pos][i];; ) { 545 if (isblock(fs, cgp->cg_free, bno + i)) { 546 bno = (bno + i) * fs->fs_frag; 547 goto gotit; 548 } 549 delta = fs->fs_rotbl[i]; 550 if (delta <= 0 || delta > MAXBPC - i) 551 break; 552 i += delta; 553 } 554 panic("alloccgblk: can't find blk in cyl"); 555 } 556 norot: 557 /* 558 * no blocks in the requested cylinder, so take next 559 * available one in this cylinder group. 560 */ 561 bno = mapsearch(fs, cgp, bpref, fs->fs_frag); 562 if (bno == 0) 563 return (NULL); 564 cgp->cg_rotor = bno; 565 gotit: 566 clrblock(fs, cgp->cg_free, bno/fs->fs_frag); 567 cgp->cg_cs.cs_nbfree--; 568 fs->fs_cstotal.cs_nbfree--; 569 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 570 cylno = cbtocylno(fs, bno); 571 cgp->cg_b[cylno][cbtorpos(fs, bno)]--; 572 cgp->cg_btot[cylno]--; 573 fs->fs_fmod++; 574 return (cgp->cg_cgx * fs->fs_fpg + bno); 575 } 576 577 /* 578 * Determine whether an inode can be allocated. 579 * 580 * Check to see if an inode is available, and if it is, 581 * allocate it using the following policy: 582 * 1) allocate the requested inode. 583 * 2) allocate the next available inode after the requested 584 * inode in the specified cylinder group. 585 */ 586 ino_t 587 ialloccg(ip, cg, ipref, mode) 588 struct inode *ip; 589 int cg; 590 daddr_t ipref; 591 int mode; 592 { 593 register struct fs *fs; 594 register struct buf *bp; 595 register struct cg *cgp; 596 int i; 597 598 fs = ip->i_fs; 599 if (fs->fs_cs(fs, cg).cs_nifree == 0) 600 return (NULL); 601 bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), fs->fs_bsize); 602 if (bp->b_flags & B_ERROR) { 603 brelse(bp); 604 return (NULL); 605 } 606 cgp = bp->b_un.b_cg; 607 if (ipref) { 608 ipref %= fs->fs_ipg; 609 if (isclr(cgp->cg_iused, ipref)) 610 goto gotit; 611 } else 612 ipref = cgp->cg_irotor; 613 for (i = 0; i < fs->fs_ipg; i++) { 614 ipref++; 615 if (ipref >= fs->fs_ipg) 616 ipref = 0; 617 if (isclr(cgp->cg_iused, ipref)) { 618 cgp->cg_irotor = ipref; 619 goto gotit; 620 } 621 } 622 brelse(bp); 623 return (NULL); 624 gotit: 625 setbit(cgp->cg_iused, ipref); 626 cgp->cg_cs.cs_nifree--; 627 fs->fs_cstotal.cs_nifree--; 628 fs->fs_cs(fs, cg).cs_nifree--; 629 fs->fs_fmod++; 630 if ((mode & IFMT) == IFDIR) { 631 cgp->cg_cs.cs_ndir++; 632 fs->fs_cstotal.cs_ndir++; 633 fs->fs_cs(fs, cg).cs_ndir++; 634 } 635 bdwrite(bp); 636 return (cg * fs->fs_ipg + ipref); 637 } 638 639 /* 640 * Free a block or fragment. 641 * 642 * The specified block or fragment is placed back in the 643 * free map. If a fragment is deallocated, a possible 644 * block reassembly is checked. 645 */ 646 fre(ip, bno, size) 647 register struct inode *ip; 648 daddr_t bno; 649 off_t size; 650 { 651 register struct fs *fs; 652 register struct cg *cgp; 653 register struct buf *bp; 654 int cg, blk, frags, bbase; 655 register int i; 656 657 fs = ip->i_fs; 658 if ((unsigned)size > fs->fs_bsize || fragoff(fs, size) != 0) 659 panic("free: bad size"); 660 cg = dtog(fs, bno); 661 if (badblock(fs, bno)) 662 return; 663 bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), fs->fs_bsize); 664 if (bp->b_flags & B_ERROR) { 665 brelse(bp); 666 return; 667 } 668 cgp = bp->b_un.b_cg; 669 bno = dtogd(fs, bno); 670 if (size == fs->fs_bsize) { 671 if (isblock(fs, cgp->cg_free, bno/fs->fs_frag)) 672 panic("free: freeing free block"); 673 setblock(fs, cgp->cg_free, bno/fs->fs_frag); 674 cgp->cg_cs.cs_nbfree++; 675 fs->fs_cstotal.cs_nbfree++; 676 fs->fs_cs(fs, cg).cs_nbfree++; 677 i = cbtocylno(fs, bno); 678 cgp->cg_b[i][cbtorpos(fs, bno)]++; 679 cgp->cg_btot[i]++; 680 } else { 681 bbase = bno - (bno % fs->fs_frag); 682 /* 683 * decrement the counts associated with the old frags 684 */ 685 blk = blkmap(fs, cgp->cg_free, bbase); 686 fragacct(fs, blk, cgp->cg_frsum, -1); 687 /* 688 * deallocate the fragment 689 */ 690 frags = numfrags(fs, size); 691 for (i = 0; i < frags; i++) { 692 if (isset(cgp->cg_free, bno + i)) 693 panic("free: freeing free frag"); 694 setbit(cgp->cg_free, bno + i); 695 } 696 cgp->cg_cs.cs_nffree += i; 697 fs->fs_cstotal.cs_nffree += i; 698 fs->fs_cs(fs, cg).cs_nffree += i; 699 /* 700 * add back in counts associated with the new frags 701 */ 702 blk = blkmap(fs, cgp->cg_free, bbase); 703 fragacct(fs, blk, cgp->cg_frsum, 1); 704 /* 705 * if a complete block has been reassembled, account for it 706 */ 707 if (isblock(fs, cgp->cg_free, bbase / fs->fs_frag)) { 708 cgp->cg_cs.cs_nffree -= fs->fs_frag; 709 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 710 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 711 cgp->cg_cs.cs_nbfree++; 712 fs->fs_cstotal.cs_nbfree++; 713 fs->fs_cs(fs, cg).cs_nbfree++; 714 i = cbtocylno(fs, bbase); 715 cgp->cg_b[i][cbtorpos(fs, bbase)]++; 716 cgp->cg_btot[i]++; 717 } 718 } 719 fs->fs_fmod++; 720 bdwrite(bp); 721 } 722 723 /* 724 * Free an inode. 725 * 726 * The specified inode is placed back in the free map. 727 */ 728 ifree(ip, ino, mode) 729 struct inode *ip; 730 ino_t ino; 731 int mode; 732 { 733 register struct fs *fs; 734 register struct cg *cgp; 735 register struct buf *bp; 736 int cg; 737 738 fs = ip->i_fs; 739 if ((unsigned)ino >= fs->fs_ipg*fs->fs_ncg) 740 panic("ifree: range"); 741 cg = itog(fs, ino); 742 bp = bread(ip->i_dev, fsbtodb(fs, cgtod(fs, cg)), fs->fs_bsize); 743 if (bp->b_flags & B_ERROR) { 744 brelse(bp); 745 return; 746 } 747 cgp = bp->b_un.b_cg; 748 ino %= fs->fs_ipg; 749 if (isclr(cgp->cg_iused, ino)) 750 panic("ifree: freeing free inode"); 751 clrbit(cgp->cg_iused, ino); 752 cgp->cg_cs.cs_nifree++; 753 fs->fs_cstotal.cs_nifree++; 754 fs->fs_cs(fs, cg).cs_nifree++; 755 if ((mode & IFMT) == IFDIR) { 756 cgp->cg_cs.cs_ndir--; 757 fs->fs_cstotal.cs_ndir--; 758 fs->fs_cs(fs, cg).cs_ndir--; 759 } 760 fs->fs_fmod++; 761 bdwrite(bp); 762 } 763 764 /* 765 * Find a block of the specified size in the specified cylinder group. 766 * 767 * It is a panic if a request is made to find a block if none are 768 * available. 769 */ 770 daddr_t 771 mapsearch(fs, cgp, bpref, allocsiz) 772 register struct fs *fs; 773 register struct cg *cgp; 774 daddr_t bpref; 775 int allocsiz; 776 { 777 daddr_t bno; 778 int start, len, loc, i; 779 int blk, field, subfield, pos; 780 781 /* 782 * find the fragment by searching through the free block 783 * map for an appropriate bit pattern 784 */ 785 if (bpref) 786 start = dtogd(fs, bpref) / NBBY; 787 else 788 start = cgp->cg_frotor / NBBY; 789 len = howmany(fs->fs_fpg, NBBY) - start; 790 loc = scanc(len, &cgp->cg_free[start], fragtbl[fs->fs_frag], 791 1 << (allocsiz - 1 + (fs->fs_frag % NBBY))); 792 if (loc == 0) { 793 loc = fs->fs_dblkno / NBBY; 794 len = start - loc + 1; 795 start = loc; 796 loc = scanc(len, &cgp->cg_free[start], fragtbl[fs->fs_frag], 797 1 << (allocsiz - 1 + (fs->fs_frag % NBBY))); 798 if (loc == 0) { 799 panic("alloccg: map corrupted"); 800 return (NULL); 801 } 802 } 803 bno = (start + len - loc) * NBBY; 804 cgp->cg_frotor = bno; 805 /* 806 * found the byte in the map 807 * sift through the bits to find the selected frag 808 */ 809 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 810 blk = blkmap(fs, cgp->cg_free, bno); 811 blk <<= 1; 812 field = around[allocsiz]; 813 subfield = inside[allocsiz]; 814 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 815 if ((blk & field) == subfield) 816 return (bno + pos); 817 field <<= 1; 818 subfield <<= 1; 819 } 820 } 821 panic("alloccg: block not in map"); 822 return (NULL); 823 } 824 825 /* 826 * Update the frsum fields to reflect addition or deletion 827 * of some frags. 828 */ 829 fragacct(fs, fragmap, fraglist, cnt) 830 struct fs *fs; 831 int fragmap; 832 long fraglist[]; 833 int cnt; 834 { 835 int inblk; 836 register int field, subfield; 837 register int siz, pos; 838 839 inblk = (int)(fragtbl[fs->fs_frag][fragmap]) << 1; 840 fragmap <<= 1; 841 for (siz = 1; siz < fs->fs_frag; siz++) { 842 if ((inblk & (1 << (siz + (fs->fs_frag % NBBY)))) == 0) 843 continue; 844 field = around[siz]; 845 subfield = inside[siz]; 846 for (pos = siz; pos <= fs->fs_frag; pos++) { 847 if ((fragmap & field) == subfield) { 848 fraglist[siz] += cnt; 849 pos += siz; 850 field <<= siz; 851 subfield <<= siz; 852 } 853 field <<= 1; 854 subfield <<= 1; 855 } 856 } 857 } 858 859 /* 860 * Check that a specified block number is in range. 861 */ 862 badblock(fs, bn) 863 register struct fs *fs; 864 daddr_t bn; 865 { 866 867 if ((unsigned)bn >= fs->fs_size || bn < cgdmin(fs, dtog(fs, bn))) { 868 fserr(fs, "bad block"); 869 return (1); 870 } 871 return (0); 872 } 873 874 /* 875 * Getfs maps a device number into a pointer to the incore super block. 876 * 877 * The algorithm is a linear search through the mount table. A 878 * consistency check of the super block magic number is performed. 879 * 880 * panic: no fs -- the device is not mounted. 881 * this "cannot happen" 882 */ 883 struct fs * 884 getfs(dev) 885 dev_t dev; 886 { 887 register struct mount *mp; 888 register struct fs *fs; 889 890 for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++) { 891 if (mp->m_bufp == NULL || mp->m_dev != dev) 892 continue; 893 fs = mp->m_bufp->b_un.b_fs; 894 if (fs->fs_magic != FS_MAGIC) 895 panic("getfs: bad magic"); 896 return (fs); 897 } 898 panic("getfs: no fs"); 899 return (NULL); 900 } 901 902 /* 903 * Fserr prints the name of a file system with an error diagnostic. 904 * 905 * The form of the error message is: 906 * fs: error message 907 */ 908 fserr(fs, cp) 909 struct fs *fs; 910 char *cp; 911 { 912 913 printf("%s: %s\n", fs->fs_fsmnt, cp); 914 } 915 916 /* 917 * Getfsx returns the index in the file system 918 * table of the specified device. The swap device 919 * is also assigned a pseudo-index. The index may 920 * be used as a compressed indication of the location 921 * of a block, recording 922 * <getfsx(dev),blkno> 923 * rather than 924 * <dev, blkno> 925 * provided the information need remain valid only 926 * as long as the file system is mounted. 927 */ 928 getfsx(dev) 929 dev_t dev; 930 { 931 register struct mount *mp; 932 933 if (dev == swapdev) 934 return (MSWAPX); 935 for(mp = &mount[0]; mp < &mount[NMOUNT]; mp++) 936 if (mp->m_dev == dev) 937 return (mp - &mount[0]); 938 return (-1); 939 } 940 941 /* 942 * Update is the internal name of 'sync'. It goes through the disk 943 * queues to initiate sandbagged IO; goes through the inodes to write 944 * modified nodes; and it goes through the mount table to initiate 945 * the writing of the modified super blocks. 946 */ 947 update(flag) 948 int flag; 949 { 950 register struct inode *ip; 951 register struct mount *mp; 952 register struct buf *bp; 953 struct fs *fs; 954 int i, blks; 955 956 if (updlock) 957 return; 958 updlock++; 959 /* 960 * Write back modified superblocks. 961 * Consistency check that the superblock 962 * of each file system is still in the buffer cache. 963 */ 964 for (mp = &mount[0]; mp < &mount[NMOUNT]; mp++) { 965 if (mp->m_bufp == NULL) 966 continue; 967 fs = mp->m_bufp->b_un.b_fs; 968 if (fs->fs_fmod == 0) 969 continue; 970 if (fs->fs_ronly != 0) 971 panic("update: rofs mod"); 972 bp = getblk(mp->m_dev, SBLOCK, SBSIZE); 973 fs->fs_fmod = 0; 974 fs->fs_time = time; 975 if (bp->b_un.b_fs != fs) 976 panic("update: bad b_fs"); 977 bwrite(bp); 978 blks = howmany(fs->fs_cssize, fs->fs_bsize); 979 for (i = 0; i < blks; i++) { 980 bp = getblk(mp->m_dev, 981 fsbtodb(fs, fs->fs_csaddr + (i * fs->fs_frag)), 982 fs->fs_bsize); 983 bwrite(bp); 984 } 985 } 986 /* 987 * Write back each (modified) inode. 988 */ 989 for (ip = inode; ip < inodeNINODE; ip++) { 990 if ((ip->i_flag & ILOCK) != 0 || ip->i_count == 0) 991 continue; 992 ip->i_flag |= ILOCK; 993 ip->i_count++; 994 iupdat(ip, &time, &time, 0); 995 iput(ip); 996 } 997 updlock = 0; 998 /* 999 * Force stale buffer cache information to be flushed, 1000 * for all devices. 1001 */ 1002 bflush(NODEV); 1003 } 1004 1005 /* 1006 * block operations 1007 * 1008 * check if a block is available 1009 */ 1010 isblock(fs, cp, h) 1011 struct fs *fs; 1012 unsigned char *cp; 1013 int h; 1014 { 1015 unsigned char mask; 1016 1017 switch (fs->fs_frag) { 1018 case 8: 1019 return (cp[h] == 0xff); 1020 case 4: 1021 mask = 0x0f << ((h & 0x1) << 2); 1022 return ((cp[h >> 1] & mask) == mask); 1023 case 2: 1024 mask = 0x03 << ((h & 0x3) << 1); 1025 return ((cp[h >> 2] & mask) == mask); 1026 case 1: 1027 mask = 0x01 << (h & 0x7); 1028 return ((cp[h >> 3] & mask) == mask); 1029 default: 1030 panic("isblock"); 1031 return (NULL); 1032 } 1033 } 1034 1035 /* 1036 * take a block out of the map 1037 */ 1038 clrblock(fs, cp, h) 1039 struct fs *fs; 1040 unsigned char *cp; 1041 int h; 1042 { 1043 switch ((fs)->fs_frag) { 1044 case 8: 1045 cp[h] = 0; 1046 return; 1047 case 4: 1048 cp[h >> 1] &= ~(0x0f << ((h & 0x1) << 2)); 1049 return; 1050 case 2: 1051 cp[h >> 2] &= ~(0x03 << ((h & 0x3) << 1)); 1052 return; 1053 case 1: 1054 cp[h >> 3] &= ~(0x01 << (h & 0x7)); 1055 return; 1056 default: 1057 panic("clrblock"); 1058 return; 1059 } 1060 } 1061 1062 /* 1063 * put a block into the map 1064 */ 1065 setblock(fs, cp, h) 1066 struct fs *fs; 1067 unsigned char *cp; 1068 int h; 1069 { 1070 switch (fs->fs_frag) { 1071 case 8: 1072 cp[h] = 0xff; 1073 return; 1074 case 4: 1075 cp[h >> 1] |= (0x0f << ((h & 0x1) << 2)); 1076 return; 1077 case 2: 1078 cp[h >> 2] |= (0x03 << ((h & 0x3) << 1)); 1079 return; 1080 case 1: 1081 cp[h >> 3] |= (0x01 << (h & 0x7)); 1082 return; 1083 default: 1084 panic("setblock"); 1085 return; 1086 } 1087 } 1088