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