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.5 (Berkeley) 01/13/94 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_nodealloccg __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 register struct fs *fs; 66 daddr_t bno; 67 int cg, error; 68 69 *bnp = 0; 70 fs = ip->i_fs; 71 #ifdef DIAGNOSTIC 72 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 73 printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", 74 ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 75 panic("ffs_alloc: bad size"); 76 } 77 if (cred == NOCRED) 78 panic("ffs_alloc: missing credential\n"); 79 #endif /* DIAGNOSTIC */ 80 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 81 goto nospace; 82 if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) 83 goto nospace; 84 #ifdef QUOTA 85 if (error = chkdq(ip, (long)btodb(size), cred, 0)) 86 return (error); 87 #endif 88 if (bpref >= fs->fs_size) 89 bpref = 0; 90 if (bpref == 0) 91 cg = ino_to_cg(fs, ip->i_number); 92 else 93 cg = dtog(fs, bpref); 94 bno = (daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 95 (u_long (*)())ffs_alloccg); 96 if (bno > 0) { 97 ip->i_blocks += btodb(size); 98 ip->i_flag |= IN_CHANGE | IN_UPDATE; 99 *bnp = bno; 100 return (0); 101 } 102 #ifdef QUOTA 103 /* 104 * Restore user's disk quota because allocation failed. 105 */ 106 (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 107 #endif 108 nospace: 109 ffs_fserr(fs, cred->cr_uid, "file system full"); 110 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 111 return (ENOSPC); 112 } 113 114 /* 115 * Reallocate a fragment to a bigger size 116 * 117 * The number and size of the old block is given, and a preference 118 * and new size is also specified. The allocator attempts to extend 119 * the original block. Failing that, the regular block allocator is 120 * invoked to get an appropriate block. 121 */ 122 ffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp) 123 register struct inode *ip; 124 daddr_t lbprev; 125 daddr_t bpref; 126 int osize, nsize; 127 struct ucred *cred; 128 struct buf **bpp; 129 { 130 register struct fs *fs; 131 struct buf *bp; 132 int cg, request, error; 133 daddr_t bprev, bno; 134 135 *bpp = 0; 136 fs = ip->i_fs; 137 #ifdef DIAGNOSTIC 138 if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 139 (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 140 printf( 141 "dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n", 142 ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt); 143 panic("ffs_realloccg: bad size"); 144 } 145 if (cred == NOCRED) 146 panic("ffs_realloccg: missing credential\n"); 147 #endif /* DIAGNOSTIC */ 148 if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) 149 goto nospace; 150 if ((bprev = ip->i_db[lbprev]) == 0) { 151 printf("dev = 0x%x, bsize = %d, bprev = %d, fs = %s\n", 152 ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt); 153 panic("ffs_realloccg: bad bprev"); 154 } 155 /* 156 * Allocate the extra space in the buffer. 157 */ 158 if (error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp)) { 159 brelse(bp); 160 return (error); 161 } 162 #ifdef QUOTA 163 if (error = chkdq(ip, (long)btodb(nsize - osize), cred, 0)) { 164 brelse(bp); 165 return (error); 166 } 167 #endif 168 /* 169 * Check for extension in the existing location. 170 */ 171 cg = dtog(fs, bprev); 172 if (bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize)) { 173 if (bp->b_blkno != fsbtodb(fs, bno)) 174 panic("bad blockno"); 175 ip->i_blocks += btodb(nsize - osize); 176 ip->i_flag |= IN_CHANGE | IN_UPDATE; 177 allocbuf(bp, nsize); 178 bp->b_flags |= B_DONE; 179 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 180 *bpp = bp; 181 return (0); 182 } 183 /* 184 * Allocate a new disk location. 185 */ 186 if (bpref >= fs->fs_size) 187 bpref = 0; 188 switch ((int)fs->fs_optim) { 189 case FS_OPTSPACE: 190 /* 191 * Allocate an exact sized fragment. Although this makes 192 * best use of space, we will waste time relocating it if 193 * the file continues to grow. If the fragmentation is 194 * less than half of the minimum free reserve, we choose 195 * to begin optimizing for time. 196 */ 197 request = nsize; 198 if (fs->fs_minfree < 5 || 199 fs->fs_cstotal.cs_nffree > 200 fs->fs_dsize * fs->fs_minfree / (2 * 100)) 201 break; 202 log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 203 fs->fs_fsmnt); 204 fs->fs_optim = FS_OPTTIME; 205 break; 206 case FS_OPTTIME: 207 /* 208 * At this point we have discovered a file that is trying to 209 * grow a small fragment to a larger fragment. To save time, 210 * we allocate a full sized block, then free the unused portion. 211 * If the file continues to grow, the `ffs_fragextend' call 212 * above will be able to grow it in place without further 213 * copying. If aberrant programs cause disk fragmentation to 214 * grow within 2% of the free reserve, we choose to begin 215 * optimizing for space. 216 */ 217 request = fs->fs_bsize; 218 if (fs->fs_cstotal.cs_nffree < 219 fs->fs_dsize * (fs->fs_minfree - 2) / 100) 220 break; 221 log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 222 fs->fs_fsmnt); 223 fs->fs_optim = FS_OPTSPACE; 224 break; 225 default: 226 printf("dev = 0x%x, optim = %d, fs = %s\n", 227 ip->i_dev, fs->fs_optim, fs->fs_fsmnt); 228 panic("ffs_realloccg: bad optim"); 229 /* NOTREACHED */ 230 } 231 bno = (daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 232 (u_long (*)())ffs_alloccg); 233 if (bno > 0) { 234 bp->b_blkno = fsbtodb(fs, bno); 235 (void) vnode_pager_uncache(ITOV(ip)); 236 ffs_blkfree(ip, bprev, (long)osize); 237 if (nsize < request) 238 ffs_blkfree(ip, bno + numfrags(fs, nsize), 239 (long)(request - nsize)); 240 ip->i_blocks += btodb(nsize - osize); 241 ip->i_flag |= IN_CHANGE | IN_UPDATE; 242 allocbuf(bp, nsize); 243 bp->b_flags |= B_DONE; 244 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 245 *bpp = bp; 246 return (0); 247 } 248 #ifdef QUOTA 249 /* 250 * Restore user's disk quota because allocation failed. 251 */ 252 (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 253 #endif 254 brelse(bp); 255 nospace: 256 /* 257 * no space available 258 */ 259 ffs_fserr(fs, cred->cr_uid, "file system full"); 260 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 261 return (ENOSPC); 262 } 263 264 /* 265 * Allocate an inode in the file system. 266 * 267 * If allocating a directory, use ffs_dirpref to select the inode. 268 * If allocating in a directory, the following hierarchy is followed: 269 * 1) allocate the preferred inode. 270 * 2) allocate an inode in the same cylinder group. 271 * 3) quadradically rehash into other cylinder groups, until an 272 * available inode is located. 273 * If no inode preference is given the following heirarchy is used 274 * to allocate an inode: 275 * 1) allocate an inode in cylinder group 0. 276 * 2) quadradically rehash into other cylinder groups, until an 277 * available inode is located. 278 */ 279 ffs_valloc(ap) 280 struct vop_valloc_args /* { 281 struct vnode *a_pvp; 282 int a_mode; 283 struct ucred *a_cred; 284 struct vnode **a_vpp; 285 } */ *ap; 286 { 287 register struct vnode *pvp = ap->a_pvp; 288 register struct inode *pip; 289 register struct fs *fs; 290 register struct inode *ip; 291 mode_t mode = ap->a_mode; 292 ino_t ino, ipref; 293 int cg, error; 294 295 *ap->a_vpp = NULL; 296 pip = VTOI(pvp); 297 fs = pip->i_fs; 298 if (fs->fs_cstotal.cs_nifree == 0) 299 goto noinodes; 300 301 if ((mode & IFMT) == IFDIR) 302 ipref = ffs_dirpref(fs); 303 else 304 ipref = pip->i_number; 305 if (ipref >= fs->fs_ncg * fs->fs_ipg) 306 ipref = 0; 307 cg = ino_to_cg(fs, ipref); 308 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, ffs_nodealloccg); 309 if (ino == 0) 310 goto noinodes; 311 error = VFS_VGET(pvp->v_mount, ino, ap->a_vpp); 312 if (error) { 313 VOP_VFREE(pvp, ino, mode); 314 return (error); 315 } 316 ip = VTOI(*ap->a_vpp); 317 if (ip->i_mode) { 318 printf("mode = 0%o, inum = %d, fs = %s\n", 319 ip->i_mode, ip->i_number, fs->fs_fsmnt); 320 panic("ffs_valloc: dup alloc"); 321 } 322 if (ip->i_blocks) { /* XXX */ 323 printf("free inode %s/%d had %d blocks\n", 324 fs->fs_fsmnt, ino, ip->i_blocks); 325 ip->i_blocks = 0; 326 } 327 ip->i_flags = 0; 328 /* 329 * Set up a new generation number for this inode. 330 */ 331 if (++nextgennumber < (u_long)time.tv_sec) 332 nextgennumber = time.tv_sec; 333 ip->i_gen = nextgennumber; 334 return (0); 335 noinodes: 336 ffs_fserr(fs, ap->a_cred->cr_uid, "out of inodes"); 337 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 338 return (ENOSPC); 339 } 340 341 /* 342 * Find a cylinder to place a directory. 343 * 344 * The policy implemented by this algorithm is to select from 345 * among those cylinder groups with above the average number of 346 * free inodes, the one with the smallest number of directories. 347 */ 348 static ino_t 349 ffs_dirpref(fs) 350 register struct fs *fs; 351 { 352 int cg, minndir, mincg, avgifree; 353 354 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 355 minndir = fs->fs_ipg; 356 mincg = 0; 357 for (cg = 0; cg < fs->fs_ncg; cg++) 358 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 359 fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 360 mincg = cg; 361 minndir = fs->fs_cs(fs, cg).cs_ndir; 362 } 363 return ((ino_t)(fs->fs_ipg * mincg)); 364 } 365 366 /* 367 * Select the desired position for the next block in a file. The file is 368 * logically divided into sections. The first section is composed of the 369 * direct blocks. Each additional section contains fs_maxbpg blocks. 370 * 371 * If no blocks have been allocated in the first section, the policy is to 372 * request a block in the same cylinder group as the inode that describes 373 * the file. If no blocks have been allocated in any other section, the 374 * policy is to place the section in a cylinder group with a greater than 375 * average number of free blocks. An appropriate cylinder group is found 376 * by using a rotor that sweeps the cylinder groups. When a new group of 377 * blocks is needed, the sweep begins in the cylinder group following the 378 * cylinder group from which the previous allocation was made. The sweep 379 * continues until a cylinder group with greater than the average number 380 * of free blocks is found. If the allocation is for the first block in an 381 * indirect block, the information on the previous allocation is unavailable; 382 * here a best guess is made based upon the logical block number being 383 * allocated. 384 * 385 * If a section is already partially allocated, the policy is to 386 * contiguously allocate fs_maxcontig blocks. The end of one of these 387 * contiguous blocks and the beginning of the next is physically separated 388 * so that the disk head will be in transit between them for at least 389 * fs_rotdelay milliseconds. This is to allow time for the processor to 390 * schedule another I/O transfer. 391 */ 392 daddr_t 393 ffs_blkpref(ip, lbn, indx, bap) 394 struct inode *ip; 395 daddr_t lbn; 396 int indx; 397 daddr_t *bap; 398 { 399 register struct fs *fs; 400 register int cg; 401 int avgbfree, startcg; 402 daddr_t nextblk; 403 404 fs = ip->i_fs; 405 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 406 if (lbn < NDADDR) { 407 cg = ino_to_cg(fs, ip->i_number); 408 return (fs->fs_fpg * cg + fs->fs_frag); 409 } 410 /* 411 * Find a cylinder with greater than average number of 412 * unused data blocks. 413 */ 414 if (indx == 0 || bap[indx - 1] == 0) 415 startcg = 416 ino_to_cg(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 = (struct cg *)bp->b_data; 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 appropriate 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 = (struct cg *)bp->b_data; 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_nodealloccg(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 = (struct cg *)bp->b_data; 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 = %d, irotor = %d, fs = %s\n", 833 cg, cgp->cg_irotor, fs->fs_fsmnt); 834 panic("ffs_nodealloccg: 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_nodealloccg: 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 ((u_int)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 ((u_int)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 = (struct cg *)bp->b_data; 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 = ino_to_cg(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 = (struct cg *)bp->b_data; 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((u_int)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((u_int)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