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