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