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