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