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.3 (Berkeley) 09/23/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_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 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 ((u_int)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 = ino_to_cg(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 |= IN_CHANGE | IN_UPDATE; 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 ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 140 (u_int)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 |= IN_CHANGE | IN_UPDATE; 178 allocbuf(bp, nsize); 179 bp->b_flags |= B_DONE; 180 bzero((char *)bp->b_data + osize, (u_int)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 |= IN_CHANGE | IN_UPDATE; 243 allocbuf(bp, nsize); 244 bp->b_flags |= B_DONE; 245 bzero((char *)bp->b_data + osize, (u_int)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 = ino_to_cg(fs, ipref); 309 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, ffs_nodealloccg); 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 = ino_to_cg(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 = 417 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 418 else 419 startcg = dtog(fs, bap[indx - 1]) + 1; 420 startcg %= fs->fs_ncg; 421 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 422 for (cg = startcg; cg < fs->fs_ncg; cg++) 423 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 424 fs->fs_cgrotor = cg; 425 return (fs->fs_fpg * cg + fs->fs_frag); 426 } 427 for (cg = 0; cg <= startcg; cg++) 428 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 429 fs->fs_cgrotor = cg; 430 return (fs->fs_fpg * cg + fs->fs_frag); 431 } 432 return (NULL); 433 } 434 /* 435 * One or more previous blocks have been laid out. If less 436 * than fs_maxcontig previous blocks are contiguous, the 437 * next block is requested contiguously, otherwise it is 438 * requested rotationally delayed by fs_rotdelay milliseconds. 439 */ 440 nextblk = bap[indx - 1] + fs->fs_frag; 441 if (indx < fs->fs_maxcontig || bap[indx - fs->fs_maxcontig] + 442 blkstofrags(fs, fs->fs_maxcontig) != nextblk) 443 return (nextblk); 444 if (fs->fs_rotdelay != 0) 445 /* 446 * Here we convert ms of delay to frags as: 447 * (frags) = (ms) * (rev/sec) * (sect/rev) / 448 * ((sect/frag) * (ms/sec)) 449 * then round up to the next block. 450 */ 451 nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 452 (NSPF(fs) * 1000), fs->fs_frag); 453 return (nextblk); 454 } 455 456 /* 457 * Implement the cylinder overflow algorithm. 458 * 459 * The policy implemented by this algorithm is: 460 * 1) allocate the block in its requested cylinder group. 461 * 2) quadradically rehash on the cylinder group number. 462 * 3) brute force search for a free block. 463 */ 464 /*VARARGS5*/ 465 static u_long 466 ffs_hashalloc(ip, cg, pref, size, allocator) 467 struct inode *ip; 468 int cg; 469 long pref; 470 int size; /* size for data blocks, mode for inodes */ 471 u_long (*allocator)(); 472 { 473 register struct fs *fs; 474 long result; 475 int i, icg = cg; 476 477 fs = ip->i_fs; 478 /* 479 * 1: preferred cylinder group 480 */ 481 result = (*allocator)(ip, cg, pref, size); 482 if (result) 483 return (result); 484 /* 485 * 2: quadratic rehash 486 */ 487 for (i = 1; i < fs->fs_ncg; i *= 2) { 488 cg += i; 489 if (cg >= fs->fs_ncg) 490 cg -= fs->fs_ncg; 491 result = (*allocator)(ip, cg, 0, size); 492 if (result) 493 return (result); 494 } 495 /* 496 * 3: brute force search 497 * Note that we start at i == 2, since 0 was checked initially, 498 * and 1 is always checked in the quadratic rehash. 499 */ 500 cg = (icg + 2) % fs->fs_ncg; 501 for (i = 2; i < fs->fs_ncg; i++) { 502 result = (*allocator)(ip, cg, 0, size); 503 if (result) 504 return (result); 505 cg++; 506 if (cg == fs->fs_ncg) 507 cg = 0; 508 } 509 return (NULL); 510 } 511 512 /* 513 * Determine whether a fragment can be extended. 514 * 515 * Check to see if the necessary fragments are available, and 516 * if they are, allocate them. 517 */ 518 static daddr_t 519 ffs_fragextend(ip, cg, bprev, osize, nsize) 520 struct inode *ip; 521 int cg; 522 long bprev; 523 int osize, nsize; 524 { 525 register struct fs *fs; 526 register struct cg *cgp; 527 struct buf *bp; 528 long bno; 529 int frags, bbase; 530 int i, error; 531 532 fs = ip->i_fs; 533 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 534 return (NULL); 535 frags = numfrags(fs, nsize); 536 bbase = fragnum(fs, bprev); 537 if (bbase > fragnum(fs, (bprev + frags - 1))) { 538 /* cannot extend across a block boundary */ 539 return (NULL); 540 } 541 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 542 (int)fs->fs_cgsize, NOCRED, &bp); 543 if (error) { 544 brelse(bp); 545 return (NULL); 546 } 547 cgp = (struct cg *)bp->b_data; 548 if (!cg_chkmagic(cgp)) { 549 brelse(bp); 550 return (NULL); 551 } 552 cgp->cg_time = time.tv_sec; 553 bno = dtogd(fs, bprev); 554 for (i = numfrags(fs, osize); i < frags; i++) 555 if (isclr(cg_blksfree(cgp), bno + i)) { 556 brelse(bp); 557 return (NULL); 558 } 559 /* 560 * the current fragment can be extended 561 * deduct the count on fragment being extended into 562 * increase the count on the remaining fragment (if any) 563 * allocate the extended piece 564 */ 565 for (i = frags; i < fs->fs_frag - bbase; i++) 566 if (isclr(cg_blksfree(cgp), bno + i)) 567 break; 568 cgp->cg_frsum[i - numfrags(fs, osize)]--; 569 if (i != frags) 570 cgp->cg_frsum[i - frags]++; 571 for (i = numfrags(fs, osize); i < frags; i++) { 572 clrbit(cg_blksfree(cgp), bno + i); 573 cgp->cg_cs.cs_nffree--; 574 fs->fs_cstotal.cs_nffree--; 575 fs->fs_cs(fs, cg).cs_nffree--; 576 } 577 fs->fs_fmod = 1; 578 bdwrite(bp); 579 return (bprev); 580 } 581 582 /* 583 * Determine whether a block can be allocated. 584 * 585 * Check to see if a block of the appropriate size is available, 586 * and if it is, allocate it. 587 */ 588 static daddr_t 589 ffs_alloccg(ip, cg, bpref, size) 590 struct inode *ip; 591 int cg; 592 daddr_t bpref; 593 int size; 594 { 595 register struct fs *fs; 596 register struct cg *cgp; 597 struct buf *bp; 598 register int i; 599 int error, bno, frags, allocsiz; 600 601 fs = ip->i_fs; 602 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 603 return (NULL); 604 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 605 (int)fs->fs_cgsize, NOCRED, &bp); 606 if (error) { 607 brelse(bp); 608 return (NULL); 609 } 610 cgp = (struct cg *)bp->b_data; 611 if (!cg_chkmagic(cgp) || 612 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 613 brelse(bp); 614 return (NULL); 615 } 616 cgp->cg_time = time.tv_sec; 617 if (size == fs->fs_bsize) { 618 bno = ffs_alloccgblk(fs, cgp, bpref); 619 bdwrite(bp); 620 return (bno); 621 } 622 /* 623 * check to see if any fragments are already available 624 * allocsiz is the size which will be allocated, hacking 625 * it down to a smaller size if necessary 626 */ 627 frags = numfrags(fs, size); 628 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 629 if (cgp->cg_frsum[allocsiz] != 0) 630 break; 631 if (allocsiz == fs->fs_frag) { 632 /* 633 * no fragments were available, so a block will be 634 * allocated, and hacked up 635 */ 636 if (cgp->cg_cs.cs_nbfree == 0) { 637 brelse(bp); 638 return (NULL); 639 } 640 bno = ffs_alloccgblk(fs, cgp, bpref); 641 bpref = dtogd(fs, bno); 642 for (i = frags; i < fs->fs_frag; i++) 643 setbit(cg_blksfree(cgp), bpref + i); 644 i = fs->fs_frag - frags; 645 cgp->cg_cs.cs_nffree += i; 646 fs->fs_cstotal.cs_nffree += i; 647 fs->fs_cs(fs, cg).cs_nffree += i; 648 fs->fs_fmod = 1; 649 cgp->cg_frsum[i]++; 650 bdwrite(bp); 651 return (bno); 652 } 653 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 654 if (bno < 0) { 655 brelse(bp); 656 return (NULL); 657 } 658 for (i = 0; i < frags; i++) 659 clrbit(cg_blksfree(cgp), bno + i); 660 cgp->cg_cs.cs_nffree -= frags; 661 fs->fs_cstotal.cs_nffree -= frags; 662 fs->fs_cs(fs, cg).cs_nffree -= frags; 663 fs->fs_fmod = 1; 664 cgp->cg_frsum[allocsiz]--; 665 if (frags != allocsiz) 666 cgp->cg_frsum[allocsiz - frags]++; 667 bdwrite(bp); 668 return (cg * fs->fs_fpg + bno); 669 } 670 671 /* 672 * Allocate a block in a cylinder group. 673 * 674 * This algorithm implements the following policy: 675 * 1) allocate the requested block. 676 * 2) allocate a rotationally optimal block in the same cylinder. 677 * 3) allocate the next available block on the block rotor for the 678 * specified cylinder group. 679 * Note that this routine only allocates fs_bsize blocks; these 680 * blocks may be fragmented by the routine that allocates them. 681 */ 682 static daddr_t 683 ffs_alloccgblk(fs, cgp, bpref) 684 register struct fs *fs; 685 register struct cg *cgp; 686 daddr_t bpref; 687 { 688 daddr_t bno; 689 int cylno, pos, delta; 690 short *cylbp; 691 register int i; 692 693 if (bpref == 0) { 694 bpref = cgp->cg_rotor; 695 goto norot; 696 } 697 bpref = blknum(fs, bpref); 698 bpref = dtogd(fs, bpref); 699 /* 700 * if the requested block is available, use it 701 */ 702 if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) { 703 bno = bpref; 704 goto gotit; 705 } 706 /* 707 * check for a block available on the same cylinder 708 */ 709 cylno = cbtocylno(fs, bpref); 710 if (cg_blktot(cgp)[cylno] == 0) 711 goto norot; 712 if (fs->fs_cpc == 0) { 713 /* 714 * Block layout information is not available. 715 * Leaving bpref unchanged means we take the 716 * next available free block following the one 717 * we just allocated. Hopefully this will at 718 * least hit a track cache on drives of unknown 719 * geometry (e.g. SCSI). 720 */ 721 goto norot; 722 } 723 /* 724 * check the summary information to see if a block is 725 * available in the requested cylinder starting at the 726 * requested rotational position and proceeding around. 727 */ 728 cylbp = cg_blks(fs, cgp, cylno); 729 pos = cbtorpos(fs, bpref); 730 for (i = pos; i < fs->fs_nrpos; i++) 731 if (cylbp[i] > 0) 732 break; 733 if (i == fs->fs_nrpos) 734 for (i = 0; i < pos; i++) 735 if (cylbp[i] > 0) 736 break; 737 if (cylbp[i] > 0) { 738 /* 739 * found a rotational position, now find the actual 740 * block. A panic if none is actually there. 741 */ 742 pos = cylno % fs->fs_cpc; 743 bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 744 if (fs_postbl(fs, pos)[i] == -1) { 745 printf("pos = %d, i = %d, fs = %s\n", 746 pos, i, fs->fs_fsmnt); 747 panic("ffs_alloccgblk: cyl groups corrupted"); 748 } 749 for (i = fs_postbl(fs, pos)[i];; ) { 750 if (ffs_isblock(fs, cg_blksfree(cgp), bno + i)) { 751 bno = blkstofrags(fs, (bno + i)); 752 goto gotit; 753 } 754 delta = fs_rotbl(fs)[i]; 755 if (delta <= 0 || 756 delta + i > fragstoblks(fs, fs->fs_fpg)) 757 break; 758 i += delta; 759 } 760 printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 761 panic("ffs_alloccgblk: can't find blk in cyl"); 762 } 763 norot: 764 /* 765 * no blocks in the requested cylinder, so take next 766 * available one in this cylinder group. 767 */ 768 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 769 if (bno < 0) 770 return (NULL); 771 cgp->cg_rotor = bno; 772 gotit: 773 ffs_clrblock(fs, cg_blksfree(cgp), (long)fragstoblks(fs, bno)); 774 cgp->cg_cs.cs_nbfree--; 775 fs->fs_cstotal.cs_nbfree--; 776 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 777 cylno = cbtocylno(fs, bno); 778 cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 779 cg_blktot(cgp)[cylno]--; 780 fs->fs_fmod = 1; 781 return (cgp->cg_cgx * fs->fs_fpg + bno); 782 } 783 784 /* 785 * Determine whether an inode can be allocated. 786 * 787 * Check to see if an inode is available, and if it is, 788 * allocate it using the following policy: 789 * 1) allocate the requested inode. 790 * 2) allocate the next available inode after the requested 791 * inode in the specified cylinder group. 792 */ 793 static ino_t 794 ffs_nodealloccg(ip, cg, ipref, mode) 795 struct inode *ip; 796 int cg; 797 daddr_t ipref; 798 int mode; 799 { 800 register struct fs *fs; 801 register struct cg *cgp; 802 struct buf *bp; 803 int error, start, len, loc, map, i; 804 805 fs = ip->i_fs; 806 if (fs->fs_cs(fs, cg).cs_nifree == 0) 807 return (NULL); 808 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 809 (int)fs->fs_cgsize, NOCRED, &bp); 810 if (error) { 811 brelse(bp); 812 return (NULL); 813 } 814 cgp = (struct cg *)bp->b_data; 815 if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 816 brelse(bp); 817 return (NULL); 818 } 819 cgp->cg_time = time.tv_sec; 820 if (ipref) { 821 ipref %= fs->fs_ipg; 822 if (isclr(cg_inosused(cgp), ipref)) 823 goto gotit; 824 } 825 start = cgp->cg_irotor / NBBY; 826 len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 827 loc = skpc(0xff, len, &cg_inosused(cgp)[start]); 828 if (loc == 0) { 829 len = start + 1; 830 start = 0; 831 loc = skpc(0xff, len, &cg_inosused(cgp)[0]); 832 if (loc == 0) { 833 printf("cg = %s, irotor = %d, fs = %s\n", 834 cg, cgp->cg_irotor, fs->fs_fsmnt); 835 panic("ffs_nodealloccg: map corrupted"); 836 /* NOTREACHED */ 837 } 838 } 839 i = start + len - loc; 840 map = cg_inosused(cgp)[i]; 841 ipref = i * NBBY; 842 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 843 if ((map & i) == 0) { 844 cgp->cg_irotor = ipref; 845 goto gotit; 846 } 847 } 848 printf("fs = %s\n", fs->fs_fsmnt); 849 panic("ffs_nodealloccg: block not in map"); 850 /* NOTREACHED */ 851 gotit: 852 setbit(cg_inosused(cgp), ipref); 853 cgp->cg_cs.cs_nifree--; 854 fs->fs_cstotal.cs_nifree--; 855 fs->fs_cs(fs, cg).cs_nifree--; 856 fs->fs_fmod = 1; 857 if ((mode & IFMT) == IFDIR) { 858 cgp->cg_cs.cs_ndir++; 859 fs->fs_cstotal.cs_ndir++; 860 fs->fs_cs(fs, cg).cs_ndir++; 861 } 862 bdwrite(bp); 863 return (cg * fs->fs_ipg + ipref); 864 } 865 866 /* 867 * Free a block or fragment. 868 * 869 * The specified block or fragment is placed back in the 870 * free map. If a fragment is deallocated, a possible 871 * block reassembly is checked. 872 */ 873 ffs_blkfree(ip, bno, size) 874 register struct inode *ip; 875 daddr_t bno; 876 long size; 877 { 878 register struct fs *fs; 879 register struct cg *cgp; 880 struct buf *bp; 881 int error, cg, blk, frags, bbase; 882 register int i; 883 884 fs = ip->i_fs; 885 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 886 printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", 887 ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 888 panic("blkfree: bad size"); 889 } 890 cg = dtog(fs, bno); 891 if ((u_int)bno >= fs->fs_size) { 892 printf("bad block %d, ino %d\n", bno, ip->i_number); 893 ffs_fserr(fs, ip->i_uid, "bad block"); 894 return; 895 } 896 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 897 (int)fs->fs_cgsize, NOCRED, &bp); 898 if (error) { 899 brelse(bp); 900 return; 901 } 902 cgp = (struct cg *)bp->b_data; 903 if (!cg_chkmagic(cgp)) { 904 brelse(bp); 905 return; 906 } 907 cgp->cg_time = time.tv_sec; 908 bno = dtogd(fs, bno); 909 if (size == fs->fs_bsize) { 910 if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno))) { 911 printf("dev = 0x%x, block = %d, fs = %s\n", 912 ip->i_dev, bno, fs->fs_fsmnt); 913 panic("blkfree: freeing free block"); 914 } 915 ffs_setblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno)); 916 cgp->cg_cs.cs_nbfree++; 917 fs->fs_cstotal.cs_nbfree++; 918 fs->fs_cs(fs, cg).cs_nbfree++; 919 i = cbtocylno(fs, bno); 920 cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; 921 cg_blktot(cgp)[i]++; 922 } else { 923 bbase = bno - fragnum(fs, bno); 924 /* 925 * decrement the counts associated with the old frags 926 */ 927 blk = blkmap(fs, cg_blksfree(cgp), bbase); 928 ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 929 /* 930 * deallocate the fragment 931 */ 932 frags = numfrags(fs, size); 933 for (i = 0; i < frags; i++) { 934 if (isset(cg_blksfree(cgp), bno + i)) { 935 printf("dev = 0x%x, block = %d, fs = %s\n", 936 ip->i_dev, bno + i, fs->fs_fsmnt); 937 panic("blkfree: freeing free frag"); 938 } 939 setbit(cg_blksfree(cgp), bno + i); 940 } 941 cgp->cg_cs.cs_nffree += i; 942 fs->fs_cstotal.cs_nffree += i; 943 fs->fs_cs(fs, cg).cs_nffree += i; 944 /* 945 * add back in counts associated with the new frags 946 */ 947 blk = blkmap(fs, cg_blksfree(cgp), bbase); 948 ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 949 /* 950 * if a complete block has been reassembled, account for it 951 */ 952 if (ffs_isblock(fs, cg_blksfree(cgp), 953 (daddr_t)fragstoblks(fs, bbase))) { 954 cgp->cg_cs.cs_nffree -= fs->fs_frag; 955 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 956 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 957 cgp->cg_cs.cs_nbfree++; 958 fs->fs_cstotal.cs_nbfree++; 959 fs->fs_cs(fs, cg).cs_nbfree++; 960 i = cbtocylno(fs, bbase); 961 cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 962 cg_blktot(cgp)[i]++; 963 } 964 } 965 fs->fs_fmod = 1; 966 bdwrite(bp); 967 } 968 969 /* 970 * Free an inode. 971 * 972 * The specified inode is placed back in the free map. 973 */ 974 int 975 ffs_vfree(ap) 976 struct vop_vfree_args /* { 977 struct vnode *a_pvp; 978 ino_t a_ino; 979 int a_mode; 980 } */ *ap; 981 { 982 register struct fs *fs; 983 register struct cg *cgp; 984 register struct inode *pip; 985 ino_t ino = ap->a_ino; 986 struct buf *bp; 987 int error, cg; 988 989 pip = VTOI(ap->a_pvp); 990 fs = pip->i_fs; 991 if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 992 panic("ifree: range: dev = 0x%x, ino = %d, fs = %s\n", 993 pip->i_dev, ino, fs->fs_fsmnt); 994 cg = ino_to_cg(fs, ino); 995 error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 996 (int)fs->fs_cgsize, NOCRED, &bp); 997 if (error) { 998 brelse(bp); 999 return (0); 1000 } 1001 cgp = (struct cg *)bp->b_data; 1002 if (!cg_chkmagic(cgp)) { 1003 brelse(bp); 1004 return (0); 1005 } 1006 cgp->cg_time = time.tv_sec; 1007 ino %= fs->fs_ipg; 1008 if (isclr(cg_inosused(cgp), ino)) { 1009 printf("dev = 0x%x, ino = %d, fs = %s\n", 1010 pip->i_dev, ino, fs->fs_fsmnt); 1011 if (fs->fs_ronly == 0) 1012 panic("ifree: freeing free inode"); 1013 } 1014 clrbit(cg_inosused(cgp), ino); 1015 if (ino < cgp->cg_irotor) 1016 cgp->cg_irotor = ino; 1017 cgp->cg_cs.cs_nifree++; 1018 fs->fs_cstotal.cs_nifree++; 1019 fs->fs_cs(fs, cg).cs_nifree++; 1020 if ((ap->a_mode & IFMT) == IFDIR) { 1021 cgp->cg_cs.cs_ndir--; 1022 fs->fs_cstotal.cs_ndir--; 1023 fs->fs_cs(fs, cg).cs_ndir--; 1024 } 1025 fs->fs_fmod = 1; 1026 bdwrite(bp); 1027 return (0); 1028 } 1029 1030 /* 1031 * Find a block of the specified size in the specified cylinder group. 1032 * 1033 * It is a panic if a request is made to find a block if none are 1034 * available. 1035 */ 1036 static daddr_t 1037 ffs_mapsearch(fs, cgp, bpref, allocsiz) 1038 register struct fs *fs; 1039 register struct cg *cgp; 1040 daddr_t bpref; 1041 int allocsiz; 1042 { 1043 daddr_t bno; 1044 int start, len, loc, i; 1045 int blk, field, subfield, pos; 1046 1047 /* 1048 * find the fragment by searching through the free block 1049 * map for an appropriate bit pattern 1050 */ 1051 if (bpref) 1052 start = dtogd(fs, bpref) / NBBY; 1053 else 1054 start = cgp->cg_frotor / NBBY; 1055 len = howmany(fs->fs_fpg, NBBY) - start; 1056 loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[start], 1057 (u_char *)fragtbl[fs->fs_frag], 1058 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 1059 if (loc == 0) { 1060 len = start + 1; 1061 start = 0; 1062 loc = scanc((u_int)len, (u_char *)&cg_blksfree(cgp)[0], 1063 (u_char *)fragtbl[fs->fs_frag], 1064 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 1065 if (loc == 0) { 1066 printf("start = %d, len = %d, fs = %s\n", 1067 start, len, fs->fs_fsmnt); 1068 panic("ffs_alloccg: map corrupted"); 1069 /* NOTREACHED */ 1070 } 1071 } 1072 bno = (start + len - loc) * NBBY; 1073 cgp->cg_frotor = bno; 1074 /* 1075 * found the byte in the map 1076 * sift through the bits to find the selected frag 1077 */ 1078 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 1079 blk = blkmap(fs, cg_blksfree(cgp), bno); 1080 blk <<= 1; 1081 field = around[allocsiz]; 1082 subfield = inside[allocsiz]; 1083 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 1084 if ((blk & field) == subfield) 1085 return (bno + pos); 1086 field <<= 1; 1087 subfield <<= 1; 1088 } 1089 } 1090 printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt); 1091 panic("ffs_alloccg: block not in map"); 1092 return (-1); 1093 } 1094 1095 /* 1096 * Fserr prints the name of a file system with an error diagnostic. 1097 * 1098 * The form of the error message is: 1099 * fs: error message 1100 */ 1101 static void 1102 ffs_fserr(fs, uid, cp) 1103 struct fs *fs; 1104 u_int uid; 1105 char *cp; 1106 { 1107 1108 log(LOG_ERR, "uid %d on %s: %s\n", uid, fs->fs_fsmnt, cp); 1109 } 1110