52 53#include <ufs/ffs/fs.h> 54#include <ufs/ffs/ffs_extern.h> 55 56typedef ufs_daddr_t allocfcn_t __P((struct inode *ip, int cg, ufs_daddr_t bpref, 57 int size)); 58 59static ufs_daddr_t ffs_alloccg __P((struct inode *, int, ufs_daddr_t, int)); 60static ufs_daddr_t ffs_alloccgblk __P((struct fs *, struct cg *, ufs_daddr_t)); 61static void ffs_clusteracct __P((struct fs *, struct cg *, ufs_daddr_t, 62 int)); 63static ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t, 64 int)); 65static ino_t ffs_dirpref __P((struct fs *)); 66static ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 67static void ffs_fserr __P((struct fs *, u_int, char *)); 68static u_long ffs_hashalloc 69 __P((struct inode *, int, long, int, allocfcn_t *)); 70static ino_t ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int)); 71static ufs_daddr_t ffs_mapsearch __P((struct fs *, struct cg *, ufs_daddr_t, 72 int)); 73 74/* 75 * Allocate a block in the file system. 76 * 77 * The size of the requested block is given, which must be some 78 * multiple of fs_fsize and <= fs_bsize. 79 * A preference may be optionally specified. If a preference is given 80 * the following hierarchy is used to allocate a block: 81 * 1) allocate the requested block. 82 * 2) allocate a rotationally optimal block in the same cylinder. 83 * 3) allocate a block in the same cylinder group. 84 * 4) quadradically rehash into other cylinder groups, until an 85 * available block is located. 86 * If no block preference is given the following heirarchy is used 87 * to allocate a block: 88 * 1) allocate a block in the cylinder group that contains the 89 * inode for the file. 90 * 2) quadradically rehash into other cylinder groups, until an 91 * available block is located. 92 */ 93int 94ffs_alloc(ip, lbn, bpref, size, cred, bnp) 95 register struct inode *ip; 96 ufs_daddr_t lbn, bpref; 97 int size; 98 struct ucred *cred; 99 ufs_daddr_t *bnp; 100{ 101 register struct fs *fs; 102 ufs_daddr_t bno; 103 int cg; 104#ifdef QUOTA 105 int error; 106#endif 107 108 *bnp = 0; 109 fs = ip->i_fs; 110#ifdef DIAGNOSTIC 111 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 112 printf("dev = 0x%lx, bsize = %ld, size = %d, fs = %s\n", 113 (u_long)ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 114 panic("ffs_alloc: bad size"); 115 } 116 if (cred == NOCRED) 117 panic("ffs_alloc: missing credential"); 118#endif /* DIAGNOSTIC */ 119 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 120 goto nospace; 121 if (cred->cr_uid != 0 && 122 freespace(fs, fs->fs_minfree) - numfrags(fs, size) < 0) 123 goto nospace; 124#ifdef QUOTA 125 error = chkdq(ip, (long)btodb(size), cred, 0); 126 if (error) 127 return (error); 128#endif 129 if (bpref >= fs->fs_size) 130 bpref = 0; 131 if (bpref == 0) 132 cg = ino_to_cg(fs, ip->i_number); 133 else 134 cg = dtog(fs, bpref); 135 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 136 ffs_alloccg); 137 if (bno > 0) { 138 ip->i_blocks += btodb(size); 139 ip->i_flag |= IN_CHANGE | IN_UPDATE; 140 *bnp = bno; 141 return (0); 142 } 143#ifdef QUOTA 144 /* 145 * Restore user's disk quota because allocation failed. 146 */ 147 (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 148#endif 149nospace: 150 ffs_fserr(fs, cred->cr_uid, "file system full"); 151 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 152 return (ENOSPC); 153} 154 155/* 156 * Reallocate a fragment to a bigger size 157 * 158 * The number and size of the old block is given, and a preference 159 * and new size is also specified. The allocator attempts to extend 160 * the original block. Failing that, the regular block allocator is 161 * invoked to get an appropriate block. 162 */ 163int 164ffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp) 165 register struct inode *ip; 166 ufs_daddr_t lbprev; 167 ufs_daddr_t bpref; 168 int osize, nsize; 169 struct ucred *cred; 170 struct buf **bpp; 171{ 172 register struct fs *fs; 173 struct buf *bp; 174 int cg, request, error; 175 ufs_daddr_t bprev, bno; 176 177 *bpp = 0; 178 fs = ip->i_fs; 179#ifdef DIAGNOSTIC 180 if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 181 (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 182 printf( 183 "dev = 0x%lx, bsize = %ld, osize = %d, " 184 "nsize = %d, fs = %s\n", 185 (u_long)ip->i_dev, fs->fs_bsize, osize, 186 nsize, fs->fs_fsmnt); 187 panic("ffs_realloccg: bad size"); 188 } 189 if (cred == NOCRED) 190 panic("ffs_realloccg: missing credential"); 191#endif /* DIAGNOSTIC */ 192 if (cred->cr_uid != 0 && 193 freespace(fs, fs->fs_minfree) - numfrags(fs, nsize - osize) < 0) 194 goto nospace; 195 if ((bprev = ip->i_db[lbprev]) == 0) { 196 printf("dev = 0x%lx, bsize = %ld, bprev = %ld, fs = %s\n", 197 (u_long) ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt); 198 panic("ffs_realloccg: bad bprev"); 199 } 200 /* 201 * Allocate the extra space in the buffer. 202 */ 203 error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp); 204 if (error) { 205 brelse(bp); 206 return (error); 207 } 208 209 if( bp->b_blkno == bp->b_lblkno) { 210 if( lbprev >= NDADDR) 211 panic("ffs_realloccg: lbprev out of range"); 212 bp->b_blkno = fsbtodb(fs, bprev); 213 } 214 215#ifdef QUOTA 216 error = chkdq(ip, (long)btodb(nsize - osize), cred, 0); 217 if (error) { 218 brelse(bp); 219 return (error); 220 } 221#endif 222 /* 223 * Check for extension in the existing location. 224 */ 225 cg = dtog(fs, bprev); 226 bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize); 227 if (bno) { 228 if (bp->b_blkno != fsbtodb(fs, bno)) 229 panic("ffs_realloccg: bad blockno"); 230 ip->i_blocks += btodb(nsize - osize); 231 ip->i_flag |= IN_CHANGE | IN_UPDATE; 232 allocbuf(bp, nsize); 233 bp->b_flags |= B_DONE; 234 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 235 *bpp = bp; 236 return (0); 237 } 238 /* 239 * Allocate a new disk location. 240 */ 241 if (bpref >= fs->fs_size) 242 bpref = 0; 243 switch ((int)fs->fs_optim) { 244 case FS_OPTSPACE: 245 /* 246 * Allocate an exact sized fragment. Although this makes 247 * best use of space, we will waste time relocating it if 248 * the file continues to grow. If the fragmentation is 249 * less than half of the minimum free reserve, we choose 250 * to begin optimizing for time. 251 */ 252 request = nsize; 253 if (fs->fs_minfree <= 5 || 254 fs->fs_cstotal.cs_nffree > 255 fs->fs_dsize * fs->fs_minfree / (2 * 100)) 256 break; 257 log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 258 fs->fs_fsmnt); 259 fs->fs_optim = FS_OPTTIME; 260 break; 261 case FS_OPTTIME: 262 /* 263 * At this point we have discovered a file that is trying to 264 * grow a small fragment to a larger fragment. To save time, 265 * we allocate a full sized block, then free the unused portion. 266 * If the file continues to grow, the `ffs_fragextend' call 267 * above will be able to grow it in place without further 268 * copying. If aberrant programs cause disk fragmentation to 269 * grow within 2% of the free reserve, we choose to begin 270 * optimizing for space. 271 */ 272 request = fs->fs_bsize; 273 if (fs->fs_cstotal.cs_nffree < 274 fs->fs_dsize * (fs->fs_minfree - 2) / 100) 275 break; 276 log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 277 fs->fs_fsmnt); 278 fs->fs_optim = FS_OPTSPACE; 279 break; 280 default: 281 printf("dev = 0x%lx, optim = %ld, fs = %s\n", 282 (u_long)ip->i_dev, fs->fs_optim, fs->fs_fsmnt); 283 panic("ffs_realloccg: bad optim"); 284 /* NOTREACHED */ 285 } 286 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 287 ffs_alloccg); 288 if (bno > 0) { 289 bp->b_blkno = fsbtodb(fs, bno); 290 ffs_blkfree(ip, bprev, (long)osize); 291 if (nsize < request) 292 ffs_blkfree(ip, bno + numfrags(fs, nsize), 293 (long)(request - nsize)); 294 ip->i_blocks += btodb(nsize - osize); 295 ip->i_flag |= IN_CHANGE | IN_UPDATE; 296 allocbuf(bp, nsize); 297 bp->b_flags |= B_DONE; 298 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 299 *bpp = bp; 300 return (0); 301 } 302#ifdef QUOTA 303 /* 304 * Restore user's disk quota because allocation failed. 305 */ 306 (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 307#endif 308 brelse(bp); 309nospace: 310 /* 311 * no space available 312 */ 313 ffs_fserr(fs, cred->cr_uid, "file system full"); 314 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 315 return (ENOSPC); 316} 317 318/* 319 * Reallocate a sequence of blocks into a contiguous sequence of blocks. 320 * 321 * The vnode and an array of buffer pointers for a range of sequential 322 * logical blocks to be made contiguous is given. The allocator attempts 323 * to find a range of sequential blocks starting as close as possible to 324 * an fs_rotdelay offset from the end of the allocation for the logical 325 * block immediately preceeding the current range. If successful, the 326 * physical block numbers in the buffer pointers and in the inode are 327 * changed to reflect the new allocation. If unsuccessful, the allocation 328 * is left unchanged. The success in doing the reallocation is returned. 329 * Note that the error return is not reflected back to the user. Rather 330 * the previous block allocation will be used. 331 */ 332static int doasyncfree = 1; 333SYSCTL_INT(_vfs_ffs, FFS_ASYNCFREE, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, ""); 334 335int doreallocblks = 1; 336SYSCTL_INT(_vfs_ffs, FFS_REALLOCBLKS, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, ""); 337 338static int prtrealloc = 0; 339 340int 341ffs_reallocblks(ap) 342 struct vop_reallocblks_args /* { 343 struct vnode *a_vp; 344 struct cluster_save *a_buflist; 345 } */ *ap; 346{ 347#if !defined (not_yes) 348 return (ENOSPC); 349#else 350 struct fs *fs; 351 struct inode *ip; 352 struct vnode *vp; 353 struct buf *sbp, *ebp; 354 ufs_daddr_t *bap, *sbap, *ebap = 0; 355 struct cluster_save *buflist; 356 ufs_daddr_t start_lbn, end_lbn, soff, newblk, blkno; 357 struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 358 int i, len, start_lvl, end_lvl, pref, ssize; 359 struct timeval tv; 360 361 if (doreallocblks == 0) 362 return (ENOSPC); 363 vp = ap->a_vp; 364 ip = VTOI(vp); 365 fs = ip->i_fs; 366 if (fs->fs_contigsumsize <= 0) 367 return (ENOSPC); 368 buflist = ap->a_buflist; 369 len = buflist->bs_nchildren; 370 start_lbn = buflist->bs_children[0]->b_lblkno; 371 end_lbn = start_lbn + len - 1; 372#ifdef DIAGNOSTIC 373 for (i = 0; i < len; i++) 374 if (!ffs_checkblk(ip, 375 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 376 panic("ffs_reallocblks: unallocated block 1"); 377 for (i = 1; i < len; i++) 378 if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 379 panic("ffs_reallocblks: non-logical cluster"); 380 blkno = buflist->bs_children[0]->b_blkno; 381 ssize = fsbtodb(fs, fs->fs_frag); 382 for (i = 1; i < len - 1; i++) 383 if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize)) 384 panic("ffs_reallocblks: non-physical cluster %d", i); 385#endif 386 /* 387 * If the latest allocation is in a new cylinder group, assume that 388 * the filesystem has decided to move and do not force it back to 389 * the previous cylinder group. 390 */ 391 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 392 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 393 return (ENOSPC); 394 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 395 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 396 return (ENOSPC); 397 /* 398 * Get the starting offset and block map for the first block. 399 */ 400 if (start_lvl == 0) { 401 sbap = &ip->i_db[0]; 402 soff = start_lbn; 403 } else { 404 idp = &start_ap[start_lvl - 1]; 405 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 406 brelse(sbp); 407 return (ENOSPC); 408 } 409 sbap = (ufs_daddr_t *)sbp->b_data; 410 soff = idp->in_off; 411 } 412 /* 413 * Find the preferred location for the cluster. 414 */ 415 pref = ffs_blkpref(ip, start_lbn, soff, sbap); 416 /* 417 * If the block range spans two block maps, get the second map. 418 */ 419 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 420 ssize = len; 421 } else { 422#ifdef DIAGNOSTIC 423 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 424 panic("ffs_reallocblk: start == end"); 425#endif 426 ssize = len - (idp->in_off + 1); 427 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 428 goto fail; 429 ebap = (ufs_daddr_t *)ebp->b_data; 430 } 431 /* 432 * Search the block map looking for an allocation of the desired size. 433 */ 434 if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref, 435 len, ffs_clusteralloc)) == 0) 436 goto fail; 437 /* 438 * We have found a new contiguous block. 439 * 440 * First we have to replace the old block pointers with the new 441 * block pointers in the inode and indirect blocks associated 442 * with the file. 443 */ 444#ifdef DEBUG 445 if (prtrealloc) 446 printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number, 447 start_lbn, end_lbn); 448#endif 449 blkno = newblk; 450 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 451 if (i == ssize) 452 bap = ebap; 453#ifdef DIAGNOSTIC 454 if (!ffs_checkblk(ip, 455 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 456 panic("ffs_reallocblks: unallocated block 2"); 457 if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap) 458 panic("ffs_reallocblks: alloc mismatch"); 459#endif 460#ifdef DEBUG 461 if (prtrealloc) 462 printf(" %d,", *bap); 463#endif 464 *bap++ = blkno; 465 } 466 /* 467 * Next we must write out the modified inode and indirect blocks. 468 * For strict correctness, the writes should be synchronous since 469 * the old block values may have been written to disk. In practise 470 * they are almost never written, but if we are concerned about 471 * strict correctness, the `doasyncfree' flag should be set to zero. 472 * 473 * The test on `doasyncfree' should be changed to test a flag 474 * that shows whether the associated buffers and inodes have 475 * been written. The flag should be set when the cluster is 476 * started and cleared whenever the buffer or inode is flushed. 477 * We can then check below to see if it is set, and do the 478 * synchronous write only when it has been cleared. 479 */ 480 if (sbap != &ip->i_db[0]) { 481 if (doasyncfree) 482 bdwrite(sbp); 483 else 484 bwrite(sbp); 485 } else { 486 ip->i_flag |= IN_CHANGE | IN_UPDATE; 487 if (!doasyncfree) { 488 gettime(&tv); 489 VOP_UPDATE(vp, &tv, &tv, 1); 490 } 491 } 492 if (ssize < len) 493 if (doasyncfree) 494 bdwrite(ebp); 495 else 496 bwrite(ebp); 497 /* 498 * Last, free the old blocks and assign the new blocks to the buffers. 499 */ 500#ifdef DEBUG 501 if (prtrealloc) 502 printf("\n\tnew:"); 503#endif 504 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 505 ffs_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno), 506 fs->fs_bsize); 507 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 508#ifdef DEBUG 509 if (!ffs_checkblk(ip, 510 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 511 panic("ffs_reallocblks: unallocated block 3"); 512 if (prtrealloc) 513 printf(" %d,", blkno); 514#endif 515 } 516#ifdef DEBUG 517 if (prtrealloc) { 518 prtrealloc--; 519 printf("\n"); 520 } 521#endif 522 return (0); 523 524fail: 525 if (ssize < len) 526 brelse(ebp); 527 if (sbap != &ip->i_db[0]) 528 brelse(sbp); 529 return (ENOSPC); 530#endif 531} 532 533/* 534 * Allocate an inode in the file system. 535 * 536 * If allocating a directory, use ffs_dirpref to select the inode. 537 * If allocating in a directory, the following hierarchy is followed: 538 * 1) allocate the preferred inode. 539 * 2) allocate an inode in the same cylinder group. 540 * 3) quadradically rehash into other cylinder groups, until an 541 * available inode is located. 542 * If no inode preference is given the following heirarchy is used 543 * to allocate an inode: 544 * 1) allocate an inode in cylinder group 0. 545 * 2) quadradically rehash into other cylinder groups, until an 546 * available inode is located. 547 */ 548int 549ffs_valloc(ap) 550 struct vop_valloc_args /* { 551 struct vnode *a_pvp; 552 int a_mode; 553 struct ucred *a_cred; 554 struct vnode **a_vpp; 555 } */ *ap; 556{ 557 register struct vnode *pvp = ap->a_pvp; 558 register struct inode *pip; 559 register struct fs *fs; 560 register struct inode *ip; 561 mode_t mode = ap->a_mode; 562 ino_t ino, ipref; 563 int cg, error; 564 565 *ap->a_vpp = NULL; 566 pip = VTOI(pvp); 567 fs = pip->i_fs; 568 if (fs->fs_cstotal.cs_nifree == 0) 569 goto noinodes; 570 571 if ((mode & IFMT) == IFDIR) 572 ipref = ffs_dirpref(fs); 573 else 574 ipref = pip->i_number; 575 if (ipref >= fs->fs_ncg * fs->fs_ipg) 576 ipref = 0; 577 cg = ino_to_cg(fs, ipref); 578 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, 579 (allocfcn_t *)ffs_nodealloccg); 580 if (ino == 0) 581 goto noinodes; 582 error = VFS_VGET(pvp->v_mount, ino, ap->a_vpp); 583 if (error) { 584 VOP_VFREE(pvp, ino, mode); 585 return (error); 586 } 587 ip = VTOI(*ap->a_vpp); 588 if (ip->i_mode) { 589 printf("mode = 0%o, inum = %ld, fs = %s\n", 590 ip->i_mode, ip->i_number, fs->fs_fsmnt); 591 panic("ffs_valloc: dup alloc"); 592 } 593 if (ip->i_blocks) { /* XXX */ 594 printf("free inode %s/%ld had %ld blocks\n", 595 fs->fs_fsmnt, ino, ip->i_blocks); 596 ip->i_blocks = 0; 597 } 598 ip->i_flags = 0; 599 /* 600 * Set up a new generation number for this inode. 601 */ 602 if (ip->i_gen == 0 || ++(ip->i_gen) == 0) 603 ip->i_gen = random() / 2 + 1; 604 return (0); 605noinodes: 606 ffs_fserr(fs, ap->a_cred->cr_uid, "out of inodes"); 607 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 608 return (ENOSPC); 609} 610 611/* 612 * Find a cylinder to place a directory. 613 * 614 * The policy implemented by this algorithm is to select from 615 * among those cylinder groups with above the average number of 616 * free inodes, the one with the smallest number of directories. 617 */ 618static ino_t 619ffs_dirpref(fs) 620 register struct fs *fs; 621{ 622 int cg, minndir, mincg, avgifree; 623 624 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 625 minndir = fs->fs_ipg; 626 mincg = 0; 627 for (cg = 0; cg < fs->fs_ncg; cg++) 628 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 629 fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 630 mincg = cg; 631 minndir = fs->fs_cs(fs, cg).cs_ndir; 632 } 633 return ((ino_t)(fs->fs_ipg * mincg)); 634} 635 636/* 637 * Select the desired position for the next block in a file. The file is 638 * logically divided into sections. The first section is composed of the 639 * direct blocks. Each additional section contains fs_maxbpg blocks. 640 * 641 * If no blocks have been allocated in the first section, the policy is to 642 * request a block in the same cylinder group as the inode that describes 643 * the file. If no blocks have been allocated in any other section, the 644 * policy is to place the section in a cylinder group with a greater than 645 * average number of free blocks. An appropriate cylinder group is found 646 * by using a rotor that sweeps the cylinder groups. When a new group of 647 * blocks is needed, the sweep begins in the cylinder group following the 648 * cylinder group from which the previous allocation was made. The sweep 649 * continues until a cylinder group with greater than the average number 650 * of free blocks is found. If the allocation is for the first block in an 651 * indirect block, the information on the previous allocation is unavailable; 652 * here a best guess is made based upon the logical block number being 653 * allocated. 654 * 655 * If a section is already partially allocated, the policy is to 656 * contiguously allocate fs_maxcontig blocks. The end of one of these 657 * contiguous blocks and the beginning of the next is physically separated 658 * so that the disk head will be in transit between them for at least 659 * fs_rotdelay milliseconds. This is to allow time for the processor to 660 * schedule another I/O transfer. 661 */ 662ufs_daddr_t 663ffs_blkpref(ip, lbn, indx, bap) 664 struct inode *ip; 665 ufs_daddr_t lbn; 666 int indx; 667 ufs_daddr_t *bap; 668{ 669 register struct fs *fs; 670 register int cg; 671 int avgbfree, startcg; 672 ufs_daddr_t nextblk; 673 674 fs = ip->i_fs; 675 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 676 if (lbn < NDADDR) { 677 cg = ino_to_cg(fs, ip->i_number); 678 return (fs->fs_fpg * cg + fs->fs_frag); 679 } 680 /* 681 * Find a cylinder with greater than average number of 682 * unused data blocks. 683 */ 684 if (indx == 0 || bap[indx - 1] == 0) 685 startcg = 686 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 687 else 688 startcg = dtog(fs, bap[indx - 1]) + 1; 689 startcg %= fs->fs_ncg; 690 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 691 for (cg = startcg; cg < fs->fs_ncg; cg++) 692 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 693 fs->fs_cgrotor = cg; 694 return (fs->fs_fpg * cg + fs->fs_frag); 695 } 696 for (cg = 0; cg <= startcg; cg++) 697 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 698 fs->fs_cgrotor = cg; 699 return (fs->fs_fpg * cg + fs->fs_frag); 700 } 701 return (0); 702 } 703 /* 704 * One or more previous blocks have been laid out. If less 705 * than fs_maxcontig previous blocks are contiguous, the 706 * next block is requested contiguously, otherwise it is 707 * requested rotationally delayed by fs_rotdelay milliseconds. 708 */ 709 nextblk = bap[indx - 1] + fs->fs_frag; 710 if (fs->fs_rotdelay == 0 || indx < fs->fs_maxcontig || 711 bap[indx - fs->fs_maxcontig] + 712 blkstofrags(fs, fs->fs_maxcontig) != nextblk) 713 return (nextblk); 714 /* 715 * Here we convert ms of delay to frags as: 716 * (frags) = (ms) * (rev/sec) * (sect/rev) / 717 * ((sect/frag) * (ms/sec)) 718 * then round up to the next block. 719 */ 720 nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 721 (NSPF(fs) * 1000), fs->fs_frag); 722 return (nextblk); 723} 724 725/* 726 * Implement the cylinder overflow algorithm. 727 * 728 * The policy implemented by this algorithm is: 729 * 1) allocate the block in its requested cylinder group. 730 * 2) quadradically rehash on the cylinder group number. 731 * 3) brute force search for a free block. 732 */ 733/*VARARGS5*/ 734static u_long 735ffs_hashalloc(ip, cg, pref, size, allocator) 736 struct inode *ip; 737 int cg; 738 long pref; 739 int size; /* size for data blocks, mode for inodes */ 740 allocfcn_t *allocator; 741{ 742 register struct fs *fs; 743 long result; /* XXX why not same type as we return? */ 744 int i, icg = cg; 745 746 fs = ip->i_fs; 747 /* 748 * 1: preferred cylinder group 749 */ 750 result = (*allocator)(ip, cg, pref, size); 751 if (result) 752 return (result); 753 /* 754 * 2: quadratic rehash 755 */ 756 for (i = 1; i < fs->fs_ncg; i *= 2) { 757 cg += i; 758 if (cg >= fs->fs_ncg) 759 cg -= fs->fs_ncg; 760 result = (*allocator)(ip, cg, 0, size); 761 if (result) 762 return (result); 763 } 764 /* 765 * 3: brute force search 766 * Note that we start at i == 2, since 0 was checked initially, 767 * and 1 is always checked in the quadratic rehash. 768 */ 769 cg = (icg + 2) % fs->fs_ncg; 770 for (i = 2; i < fs->fs_ncg; i++) { 771 result = (*allocator)(ip, cg, 0, size); 772 if (result) 773 return (result); 774 cg++; 775 if (cg == fs->fs_ncg) 776 cg = 0; 777 } 778 return (0); 779} 780 781/* 782 * Determine whether a fragment can be extended. 783 * 784 * Check to see if the necessary fragments are available, and 785 * if they are, allocate them. 786 */ 787static ufs_daddr_t 788ffs_fragextend(ip, cg, bprev, osize, nsize) 789 struct inode *ip; 790 int cg; 791 long bprev; 792 int osize, nsize; 793{ 794 register struct fs *fs; 795 register struct cg *cgp; 796 struct buf *bp; 797 long bno; 798 int frags, bbase; 799 int i, error; 800 801 fs = ip->i_fs; 802 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 803 return (0); 804 frags = numfrags(fs, nsize); 805 bbase = fragnum(fs, bprev); 806 if (bbase > fragnum(fs, (bprev + frags - 1))) { 807 /* cannot extend across a block boundary */ 808 return (0); 809 } 810 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 811 (int)fs->fs_cgsize, NOCRED, &bp); 812 if (error) { 813 brelse(bp); 814 return (0); 815 } 816 cgp = (struct cg *)bp->b_data; 817 if (!cg_chkmagic(cgp)) { 818 brelse(bp); 819 return (0); 820 } 821 cgp->cg_time = time.tv_sec; 822 bno = dtogd(fs, bprev); 823 for (i = numfrags(fs, osize); i < frags; i++) 824 if (isclr(cg_blksfree(cgp), bno + i)) { 825 brelse(bp); 826 return (0); 827 } 828 /* 829 * the current fragment can be extended 830 * deduct the count on fragment being extended into 831 * increase the count on the remaining fragment (if any) 832 * allocate the extended piece 833 */ 834 for (i = frags; i < fs->fs_frag - bbase; i++) 835 if (isclr(cg_blksfree(cgp), bno + i)) 836 break; 837 cgp->cg_frsum[i - numfrags(fs, osize)]--; 838 if (i != frags) 839 cgp->cg_frsum[i - frags]++; 840 for (i = numfrags(fs, osize); i < frags; i++) { 841 clrbit(cg_blksfree(cgp), bno + i); 842 cgp->cg_cs.cs_nffree--; 843 fs->fs_cstotal.cs_nffree--; 844 fs->fs_cs(fs, cg).cs_nffree--; 845 } 846 fs->fs_fmod = 1; 847 bdwrite(bp); 848 return (bprev); 849} 850 851/* 852 * Determine whether a block can be allocated. 853 * 854 * Check to see if a block of the appropriate size is available, 855 * and if it is, allocate it. 856 */ 857static ufs_daddr_t 858ffs_alloccg(ip, cg, bpref, size) 859 struct inode *ip; 860 int cg; 861 ufs_daddr_t bpref; 862 int size; 863{ 864 register struct fs *fs; 865 register struct cg *cgp; 866 struct buf *bp; 867 register int i; 868 int error, bno, frags, allocsiz; 869 870 fs = ip->i_fs; 871 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 872 return (0); 873 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 874 (int)fs->fs_cgsize, NOCRED, &bp); 875 if (error) { 876 brelse(bp); 877 return (0); 878 } 879 cgp = (struct cg *)bp->b_data; 880 if (!cg_chkmagic(cgp) || 881 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 882 brelse(bp); 883 return (0); 884 } 885 cgp->cg_time = time.tv_sec; 886 if (size == fs->fs_bsize) { 887 bno = ffs_alloccgblk(fs, cgp, bpref); 888 bdwrite(bp); 889 return (bno); 890 } 891 /* 892 * check to see if any fragments are already available 893 * allocsiz is the size which will be allocated, hacking 894 * it down to a smaller size if necessary 895 */ 896 frags = numfrags(fs, size); 897 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 898 if (cgp->cg_frsum[allocsiz] != 0) 899 break; 900 if (allocsiz == fs->fs_frag) { 901 /* 902 * no fragments were available, so a block will be 903 * allocated, and hacked up 904 */ 905 if (cgp->cg_cs.cs_nbfree == 0) { 906 brelse(bp); 907 return (0); 908 } 909 bno = ffs_alloccgblk(fs, cgp, bpref); 910 bpref = dtogd(fs, bno); 911 for (i = frags; i < fs->fs_frag; i++) 912 setbit(cg_blksfree(cgp), bpref + i); 913 i = fs->fs_frag - frags; 914 cgp->cg_cs.cs_nffree += i; 915 fs->fs_cstotal.cs_nffree += i; 916 fs->fs_cs(fs, cg).cs_nffree += i; 917 fs->fs_fmod = 1; 918 cgp->cg_frsum[i]++; 919 bdwrite(bp); 920 return (bno); 921 } 922 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 923 if (bno < 0) { 924 brelse(bp); 925 return (0); 926 } 927 for (i = 0; i < frags; i++) 928 clrbit(cg_blksfree(cgp), bno + i); 929 cgp->cg_cs.cs_nffree -= frags; 930 fs->fs_cstotal.cs_nffree -= frags; 931 fs->fs_cs(fs, cg).cs_nffree -= frags; 932 fs->fs_fmod = 1; 933 cgp->cg_frsum[allocsiz]--; 934 if (frags != allocsiz) 935 cgp->cg_frsum[allocsiz - frags]++; 936 bdwrite(bp); 937 return (cg * fs->fs_fpg + bno); 938} 939 940/* 941 * Allocate a block in a cylinder group. 942 * 943 * This algorithm implements the following policy: 944 * 1) allocate the requested block. 945 * 2) allocate a rotationally optimal block in the same cylinder. 946 * 3) allocate the next available block on the block rotor for the 947 * specified cylinder group. 948 * Note that this routine only allocates fs_bsize blocks; these 949 * blocks may be fragmented by the routine that allocates them. 950 */ 951static ufs_daddr_t 952ffs_alloccgblk(fs, cgp, bpref) 953 register struct fs *fs; 954 register struct cg *cgp; 955 ufs_daddr_t bpref; 956{ 957 ufs_daddr_t bno, blkno; 958 int cylno, pos, delta; 959 short *cylbp; 960 register int i; 961 962 if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) { 963 bpref = cgp->cg_rotor; 964 goto norot; 965 } 966 bpref = blknum(fs, bpref); 967 bpref = dtogd(fs, bpref); 968 /* 969 * if the requested block is available, use it 970 */ 971 if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) { 972 bno = bpref; 973 goto gotit; 974 } 975 if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) { 976 /* 977 * Block layout information is not available. 978 * Leaving bpref unchanged means we take the 979 * next available free block following the one 980 * we just allocated. Hopefully this will at 981 * least hit a track cache on drives of unknown 982 * geometry (e.g. SCSI). 983 */ 984 goto norot; 985 } 986 /* 987 * check for a block available on the same cylinder 988 */ 989 cylno = cbtocylno(fs, bpref); 990 if (cg_blktot(cgp)[cylno] == 0) 991 goto norot; 992 /* 993 * check the summary information to see if a block is 994 * available in the requested cylinder starting at the 995 * requested rotational position and proceeding around. 996 */ 997 cylbp = cg_blks(fs, cgp, cylno); 998 pos = cbtorpos(fs, bpref); 999 for (i = pos; i < fs->fs_nrpos; i++) 1000 if (cylbp[i] > 0) 1001 break; 1002 if (i == fs->fs_nrpos) 1003 for (i = 0; i < pos; i++) 1004 if (cylbp[i] > 0) 1005 break; 1006 if (cylbp[i] > 0) { 1007 /* 1008 * found a rotational position, now find the actual 1009 * block. A panic if none is actually there. 1010 */ 1011 pos = cylno % fs->fs_cpc; 1012 bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 1013 if (fs_postbl(fs, pos)[i] == -1) { 1014 printf("pos = %d, i = %d, fs = %s\n", 1015 pos, i, fs->fs_fsmnt); 1016 panic("ffs_alloccgblk: cyl groups corrupted"); 1017 } 1018 for (i = fs_postbl(fs, pos)[i];; ) { 1019 if (ffs_isblock(fs, cg_blksfree(cgp), bno + i)) { 1020 bno = blkstofrags(fs, (bno + i)); 1021 goto gotit; 1022 } 1023 delta = fs_rotbl(fs)[i]; 1024 if (delta <= 0 || 1025 delta + i > fragstoblks(fs, fs->fs_fpg)) 1026 break; 1027 i += delta; 1028 } 1029 printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 1030 panic("ffs_alloccgblk: can't find blk in cyl"); 1031 } 1032norot: 1033 /* 1034 * no blocks in the requested cylinder, so take next 1035 * available one in this cylinder group. 1036 */ 1037 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 1038 if (bno < 0) 1039 return (0); 1040 cgp->cg_rotor = bno; 1041gotit: 1042 blkno = fragstoblks(fs, bno); 1043 ffs_clrblock(fs, cg_blksfree(cgp), (long)blkno); 1044 ffs_clusteracct(fs, cgp, blkno, -1); 1045 cgp->cg_cs.cs_nbfree--; 1046 fs->fs_cstotal.cs_nbfree--; 1047 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 1048 cylno = cbtocylno(fs, bno); 1049 cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 1050 cg_blktot(cgp)[cylno]--; 1051 fs->fs_fmod = 1; 1052 return (cgp->cg_cgx * fs->fs_fpg + bno); 1053} 1054 1055#ifdef notyet 1056/* 1057 * Determine whether a cluster can be allocated. 1058 * 1059 * We do not currently check for optimal rotational layout if there 1060 * are multiple choices in the same cylinder group. Instead we just 1061 * take the first one that we find following bpref. 1062 */ 1063static ufs_daddr_t 1064ffs_clusteralloc(ip, cg, bpref, len) 1065 struct inode *ip; 1066 int cg; 1067 ufs_daddr_t bpref; 1068 int len; 1069{ 1070 register struct fs *fs; 1071 register struct cg *cgp; 1072 struct buf *bp; 1073 int i, got, run, bno, bit, map; 1074 u_char *mapp; 1075 int32_t *lp; 1076 1077 fs = ip->i_fs; 1078 if (fs->fs_maxcluster[cg] < len) 1079 return (NULL); 1080 if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 1081 NOCRED, &bp)) 1082 goto fail; 1083 cgp = (struct cg *)bp->b_data; 1084 if (!cg_chkmagic(cgp)) 1085 goto fail; 1086 /* 1087 * Check to see if a cluster of the needed size (or bigger) is 1088 * available in this cylinder group. 1089 */ 1090 lp = &cg_clustersum(cgp)[len]; 1091 for (i = len; i <= fs->fs_contigsumsize; i++) 1092 if (*lp++ > 0) 1093 break; 1094 if (i > fs->fs_contigsumsize) { 1095 /* 1096 * This is the first time looking for a cluster in this 1097 * cylinder group. Update the cluster summary information 1098 * to reflect the true maximum sized cluster so that 1099 * future cluster allocation requests can avoid reading 1100 * the cylinder group map only to find no clusters. 1101 */ 1102 lp = &cg_clustersum(cgp)[len - 1]; 1103 for (i = len - 1; i > 0; i--) 1104 if (*lp-- > 0) 1105 break; 1106 fs->fs_maxcluster[cg] = i; 1107 goto fail; 1108 } 1109 /* 1110 * Search the cluster map to find a big enough cluster. 1111 * We take the first one that we find, even if it is larger 1112 * than we need as we prefer to get one close to the previous 1113 * block allocation. We do not search before the current 1114 * preference point as we do not want to allocate a block 1115 * that is allocated before the previous one (as we will 1116 * then have to wait for another pass of the elevator 1117 * algorithm before it will be read). We prefer to fail and 1118 * be recalled to try an allocation in the next cylinder group. 1119 */ 1120 if (dtog(fs, bpref) != cg) 1121 bpref = 0; 1122 else 1123 bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 1124 mapp = &cg_clustersfree(cgp)[bpref / NBBY]; 1125 map = *mapp++; 1126 bit = 1 << (bpref % NBBY); 1127 for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) { 1128 if ((map & bit) == 0) { 1129 run = 0; 1130 } else { 1131 run++; 1132 if (run == len) 1133 break; 1134 } 1135 if ((got & (NBBY - 1)) != (NBBY - 1)) { 1136 bit <<= 1; 1137 } else { 1138 map = *mapp++; 1139 bit = 1; 1140 } 1141 } 1142 if (got >= cgp->cg_nclusterblks) 1143 goto fail; 1144 /* 1145 * Allocate the cluster that we have found. 1146 */ 1147 for (i = 1; i <= len; i++) 1148 if (!ffs_isblock(fs, cg_blksfree(cgp), got - run + i)) 1149 panic("ffs_clusteralloc: map mismatch"); 1150 bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1); 1151 if (dtog(fs, bno) != cg) 1152 panic("ffs_clusteralloc: allocated out of group"); 1153 len = blkstofrags(fs, len); 1154 for (i = 0; i < len; i += fs->fs_frag) 1155 if ((got = ffs_alloccgblk(fs, cgp, bno + i)) != bno + i) 1156 panic("ffs_clusteralloc: lost block"); 1157 bdwrite(bp); 1158 return (bno); 1159 1160fail: 1161 brelse(bp); 1162 return (0); 1163} 1164#endif 1165 1166/* 1167 * Determine whether an inode can be allocated. 1168 * 1169 * Check to see if an inode is available, and if it is, 1170 * allocate it using the following policy: 1171 * 1) allocate the requested inode. 1172 * 2) allocate the next available inode after the requested 1173 * inode in the specified cylinder group. 1174 */ 1175static ino_t 1176ffs_nodealloccg(ip, cg, ipref, mode) 1177 struct inode *ip; 1178 int cg; 1179 ufs_daddr_t ipref; 1180 int mode; 1181{ 1182 register struct fs *fs; 1183 register struct cg *cgp; 1184 struct buf *bp; 1185 int error, start, len, loc, map, i; 1186 1187 fs = ip->i_fs; 1188 if (fs->fs_cs(fs, cg).cs_nifree == 0) 1189 return (0); 1190 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1191 (int)fs->fs_cgsize, NOCRED, &bp); 1192 if (error) { 1193 brelse(bp); 1194 return (0); 1195 } 1196 cgp = (struct cg *)bp->b_data; 1197 if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 1198 brelse(bp); 1199 return (0); 1200 } 1201 cgp->cg_time = time.tv_sec; 1202 if (ipref) { 1203 ipref %= fs->fs_ipg; 1204 if (isclr(cg_inosused(cgp), ipref)) 1205 goto gotit; 1206 } 1207 start = cgp->cg_irotor / NBBY; 1208 len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 1209 loc = skpc(0xff, len, &cg_inosused(cgp)[start]); 1210 if (loc == 0) { 1211 len = start + 1; 1212 start = 0; 1213 loc = skpc(0xff, len, &cg_inosused(cgp)[0]); 1214 if (loc == 0) { 1215 printf("cg = %d, irotor = %ld, fs = %s\n", 1216 cg, cgp->cg_irotor, fs->fs_fsmnt); 1217 panic("ffs_nodealloccg: map corrupted"); 1218 /* NOTREACHED */ 1219 } 1220 } 1221 i = start + len - loc; 1222 map = cg_inosused(cgp)[i]; 1223 ipref = i * NBBY; 1224 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 1225 if ((map & i) == 0) { 1226 cgp->cg_irotor = ipref; 1227 goto gotit; 1228 } 1229 } 1230 printf("fs = %s\n", fs->fs_fsmnt); 1231 panic("ffs_nodealloccg: block not in map"); 1232 /* NOTREACHED */ 1233gotit: 1234 setbit(cg_inosused(cgp), ipref); 1235 cgp->cg_cs.cs_nifree--; 1236 fs->fs_cstotal.cs_nifree--; 1237 fs->fs_cs(fs, cg).cs_nifree--; 1238 fs->fs_fmod = 1; 1239 if ((mode & IFMT) == IFDIR) { 1240 cgp->cg_cs.cs_ndir++; 1241 fs->fs_cstotal.cs_ndir++; 1242 fs->fs_cs(fs, cg).cs_ndir++; 1243 } 1244 bdwrite(bp); 1245 return (cg * fs->fs_ipg + ipref); 1246} 1247 1248/* 1249 * Free a block or fragment. 1250 * 1251 * The specified block or fragment is placed back in the 1252 * free map. If a fragment is deallocated, a possible 1253 * block reassembly is checked. 1254 */ 1255void 1256ffs_blkfree(ip, bno, size) 1257 register struct inode *ip; 1258 ufs_daddr_t bno; 1259 long size; 1260{ 1261 register struct fs *fs; 1262 register struct cg *cgp; 1263 struct buf *bp; 1264 ufs_daddr_t blkno; 1265 int i, error, cg, blk, frags, bbase; 1266 1267 fs = ip->i_fs; 1268 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1269 printf("dev = 0x%lx, bsize = %ld, size = %ld, fs = %s\n", 1270 (u_long)ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 1271 panic("ffs_blkfree: bad size"); 1272 } 1273 cg = dtog(fs, bno); 1274 if ((u_int)bno >= fs->fs_size) { 1275 printf("bad block %ld, ino %ld\n", bno, ip->i_number); 1276 ffs_fserr(fs, ip->i_uid, "bad block"); 1277 return; 1278 } 1279 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1280 (int)fs->fs_cgsize, NOCRED, &bp); 1281 if (error) { 1282 brelse(bp); 1283 return; 1284 } 1285 cgp = (struct cg *)bp->b_data; 1286 if (!cg_chkmagic(cgp)) { 1287 brelse(bp); 1288 return; 1289 } 1290 cgp->cg_time = time.tv_sec; 1291 bno = dtogd(fs, bno); 1292 if (size == fs->fs_bsize) { 1293 blkno = fragstoblks(fs, bno); 1294 if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 1295 printf("dev = 0x%lx, block = %ld, fs = %s\n", 1296 (u_long) ip->i_dev, bno, fs->fs_fsmnt); 1297 panic("ffs_blkfree: freeing free block"); 1298 } 1299 ffs_setblock(fs, cg_blksfree(cgp), blkno); 1300 ffs_clusteracct(fs, cgp, blkno, 1); 1301 cgp->cg_cs.cs_nbfree++; 1302 fs->fs_cstotal.cs_nbfree++; 1303 fs->fs_cs(fs, cg).cs_nbfree++; 1304 i = cbtocylno(fs, bno); 1305 cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; 1306 cg_blktot(cgp)[i]++; 1307 } else { 1308 bbase = bno - fragnum(fs, bno); 1309 /* 1310 * decrement the counts associated with the old frags 1311 */ 1312 blk = blkmap(fs, cg_blksfree(cgp), bbase); 1313 ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 1314 /* 1315 * deallocate the fragment 1316 */ 1317 frags = numfrags(fs, size); 1318 for (i = 0; i < frags; i++) { 1319 if (isset(cg_blksfree(cgp), bno + i)) { 1320 printf("dev = 0x%lx, block = %ld, fs = %s\n", 1321 (u_long) ip->i_dev, bno + i, fs->fs_fsmnt); 1322 panic("ffs_blkfree: freeing free frag"); 1323 } 1324 setbit(cg_blksfree(cgp), bno + i); 1325 } 1326 cgp->cg_cs.cs_nffree += i; 1327 fs->fs_cstotal.cs_nffree += i; 1328 fs->fs_cs(fs, cg).cs_nffree += i; 1329 /* 1330 * add back in counts associated with the new frags 1331 */ 1332 blk = blkmap(fs, cg_blksfree(cgp), bbase); 1333 ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 1334 /* 1335 * if a complete block has been reassembled, account for it 1336 */ 1337 blkno = fragstoblks(fs, bbase); 1338 if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 1339 cgp->cg_cs.cs_nffree -= fs->fs_frag; 1340 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 1341 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 1342 ffs_clusteracct(fs, cgp, blkno, 1); 1343 cgp->cg_cs.cs_nbfree++; 1344 fs->fs_cstotal.cs_nbfree++; 1345 fs->fs_cs(fs, cg).cs_nbfree++; 1346 i = cbtocylno(fs, bbase); 1347 cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 1348 cg_blktot(cgp)[i]++; 1349 } 1350 } 1351 fs->fs_fmod = 1; 1352 bdwrite(bp); 1353} 1354 1355#ifdef DIAGNOSTIC 1356/* 1357 * Verify allocation of a block or fragment. Returns true if block or 1358 * fragment is allocated, false if it is free. 1359 */ 1360int 1361ffs_checkblk(ip, bno, size) 1362 struct inode *ip; 1363 ufs_daddr_t bno; 1364 long size; 1365{ 1366 struct fs *fs; 1367 struct cg *cgp; 1368 struct buf *bp; 1369 int i, error, frags, free; 1370 1371 fs = ip->i_fs; 1372 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1373 printf("bsize = %d, size = %d, fs = %s\n", 1374 fs->fs_bsize, size, fs->fs_fsmnt); 1375 panic("ffs_checkblk: bad size"); 1376 } 1377 if ((u_int)bno >= fs->fs_size) 1378 panic("ffs_checkblk: bad block %d", bno); 1379 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))), 1380 (int)fs->fs_cgsize, NOCRED, &bp); 1381 if (error) 1382 panic("ffs_checkblk: cg bread failed"); 1383 cgp = (struct cg *)bp->b_data; 1384 if (!cg_chkmagic(cgp)) 1385 panic("ffs_checkblk: cg magic mismatch"); 1386 bno = dtogd(fs, bno); 1387 if (size == fs->fs_bsize) { 1388 free = ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno)); 1389 } else { 1390 frags = numfrags(fs, size); 1391 for (free = 0, i = 0; i < frags; i++) 1392 if (isset(cg_blksfree(cgp), bno + i)) 1393 free++; 1394 if (free != 0 && free != frags) 1395 panic("ffs_checkblk: partially free fragment"); 1396 } 1397 brelse(bp); 1398 return (!free); 1399} 1400#endif /* DIAGNOSTIC */ 1401 1402/* 1403 * Free an inode. 1404 * 1405 * The specified inode is placed back in the free map. 1406 */ 1407int 1408ffs_vfree(ap) 1409 struct vop_vfree_args /* { 1410 struct vnode *a_pvp; 1411 ino_t a_ino; 1412 int a_mode; 1413 } */ *ap; 1414{ 1415 register struct fs *fs; 1416 register struct cg *cgp; 1417 register struct inode *pip; 1418 ino_t ino = ap->a_ino; 1419 struct buf *bp; 1420 int error, cg; 1421 1422 pip = VTOI(ap->a_pvp);
| 51 52#include <ufs/ffs/fs.h> 53#include <ufs/ffs/ffs_extern.h> 54 55typedef ufs_daddr_t allocfcn_t __P((struct inode *ip, int cg, ufs_daddr_t bpref, 56 int size)); 57 58static ufs_daddr_t ffs_alloccg __P((struct inode *, int, ufs_daddr_t, int)); 59static ufs_daddr_t ffs_alloccgblk __P((struct fs *, struct cg *, ufs_daddr_t)); 60static void ffs_clusteracct __P((struct fs *, struct cg *, ufs_daddr_t, 61 int)); 62static ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t, 63 int)); 64static ino_t ffs_dirpref __P((struct fs *)); 65static ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 66static void ffs_fserr __P((struct fs *, u_int, char *)); 67static u_long ffs_hashalloc 68 __P((struct inode *, int, long, int, allocfcn_t *)); 69static ino_t ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int)); 70static ufs_daddr_t ffs_mapsearch __P((struct fs *, struct cg *, ufs_daddr_t, 71 int)); 72 73/* 74 * Allocate a block in the file system. 75 * 76 * The size of the requested block is given, which must be some 77 * multiple of fs_fsize and <= fs_bsize. 78 * A preference may be optionally specified. If a preference is given 79 * the following hierarchy is used to allocate a block: 80 * 1) allocate the requested block. 81 * 2) allocate a rotationally optimal block in the same cylinder. 82 * 3) allocate a block in the same cylinder group. 83 * 4) quadradically rehash into other cylinder groups, until an 84 * available block is located. 85 * If no block preference is given the following heirarchy is used 86 * to allocate a block: 87 * 1) allocate a block in the cylinder group that contains the 88 * inode for the file. 89 * 2) quadradically rehash into other cylinder groups, until an 90 * available block is located. 91 */ 92int 93ffs_alloc(ip, lbn, bpref, size, cred, bnp) 94 register struct inode *ip; 95 ufs_daddr_t lbn, bpref; 96 int size; 97 struct ucred *cred; 98 ufs_daddr_t *bnp; 99{ 100 register struct fs *fs; 101 ufs_daddr_t bno; 102 int cg; 103#ifdef QUOTA 104 int error; 105#endif 106 107 *bnp = 0; 108 fs = ip->i_fs; 109#ifdef DIAGNOSTIC 110 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 111 printf("dev = 0x%lx, bsize = %ld, size = %d, fs = %s\n", 112 (u_long)ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 113 panic("ffs_alloc: bad size"); 114 } 115 if (cred == NOCRED) 116 panic("ffs_alloc: missing credential"); 117#endif /* DIAGNOSTIC */ 118 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 119 goto nospace; 120 if (cred->cr_uid != 0 && 121 freespace(fs, fs->fs_minfree) - numfrags(fs, size) < 0) 122 goto nospace; 123#ifdef QUOTA 124 error = chkdq(ip, (long)btodb(size), cred, 0); 125 if (error) 126 return (error); 127#endif 128 if (bpref >= fs->fs_size) 129 bpref = 0; 130 if (bpref == 0) 131 cg = ino_to_cg(fs, ip->i_number); 132 else 133 cg = dtog(fs, bpref); 134 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 135 ffs_alloccg); 136 if (bno > 0) { 137 ip->i_blocks += btodb(size); 138 ip->i_flag |= IN_CHANGE | IN_UPDATE; 139 *bnp = bno; 140 return (0); 141 } 142#ifdef QUOTA 143 /* 144 * Restore user's disk quota because allocation failed. 145 */ 146 (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 147#endif 148nospace: 149 ffs_fserr(fs, cred->cr_uid, "file system full"); 150 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 151 return (ENOSPC); 152} 153 154/* 155 * Reallocate a fragment to a bigger size 156 * 157 * The number and size of the old block is given, and a preference 158 * and new size is also specified. The allocator attempts to extend 159 * the original block. Failing that, the regular block allocator is 160 * invoked to get an appropriate block. 161 */ 162int 163ffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp) 164 register struct inode *ip; 165 ufs_daddr_t lbprev; 166 ufs_daddr_t bpref; 167 int osize, nsize; 168 struct ucred *cred; 169 struct buf **bpp; 170{ 171 register struct fs *fs; 172 struct buf *bp; 173 int cg, request, error; 174 ufs_daddr_t bprev, bno; 175 176 *bpp = 0; 177 fs = ip->i_fs; 178#ifdef DIAGNOSTIC 179 if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 180 (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 181 printf( 182 "dev = 0x%lx, bsize = %ld, osize = %d, " 183 "nsize = %d, fs = %s\n", 184 (u_long)ip->i_dev, fs->fs_bsize, osize, 185 nsize, fs->fs_fsmnt); 186 panic("ffs_realloccg: bad size"); 187 } 188 if (cred == NOCRED) 189 panic("ffs_realloccg: missing credential"); 190#endif /* DIAGNOSTIC */ 191 if (cred->cr_uid != 0 && 192 freespace(fs, fs->fs_minfree) - numfrags(fs, nsize - osize) < 0) 193 goto nospace; 194 if ((bprev = ip->i_db[lbprev]) == 0) { 195 printf("dev = 0x%lx, bsize = %ld, bprev = %ld, fs = %s\n", 196 (u_long) ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt); 197 panic("ffs_realloccg: bad bprev"); 198 } 199 /* 200 * Allocate the extra space in the buffer. 201 */ 202 error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp); 203 if (error) { 204 brelse(bp); 205 return (error); 206 } 207 208 if( bp->b_blkno == bp->b_lblkno) { 209 if( lbprev >= NDADDR) 210 panic("ffs_realloccg: lbprev out of range"); 211 bp->b_blkno = fsbtodb(fs, bprev); 212 } 213 214#ifdef QUOTA 215 error = chkdq(ip, (long)btodb(nsize - osize), cred, 0); 216 if (error) { 217 brelse(bp); 218 return (error); 219 } 220#endif 221 /* 222 * Check for extension in the existing location. 223 */ 224 cg = dtog(fs, bprev); 225 bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize); 226 if (bno) { 227 if (bp->b_blkno != fsbtodb(fs, bno)) 228 panic("ffs_realloccg: bad blockno"); 229 ip->i_blocks += btodb(nsize - osize); 230 ip->i_flag |= IN_CHANGE | IN_UPDATE; 231 allocbuf(bp, nsize); 232 bp->b_flags |= B_DONE; 233 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 234 *bpp = bp; 235 return (0); 236 } 237 /* 238 * Allocate a new disk location. 239 */ 240 if (bpref >= fs->fs_size) 241 bpref = 0; 242 switch ((int)fs->fs_optim) { 243 case FS_OPTSPACE: 244 /* 245 * Allocate an exact sized fragment. Although this makes 246 * best use of space, we will waste time relocating it if 247 * the file continues to grow. If the fragmentation is 248 * less than half of the minimum free reserve, we choose 249 * to begin optimizing for time. 250 */ 251 request = nsize; 252 if (fs->fs_minfree <= 5 || 253 fs->fs_cstotal.cs_nffree > 254 fs->fs_dsize * fs->fs_minfree / (2 * 100)) 255 break; 256 log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 257 fs->fs_fsmnt); 258 fs->fs_optim = FS_OPTTIME; 259 break; 260 case FS_OPTTIME: 261 /* 262 * At this point we have discovered a file that is trying to 263 * grow a small fragment to a larger fragment. To save time, 264 * we allocate a full sized block, then free the unused portion. 265 * If the file continues to grow, the `ffs_fragextend' call 266 * above will be able to grow it in place without further 267 * copying. If aberrant programs cause disk fragmentation to 268 * grow within 2% of the free reserve, we choose to begin 269 * optimizing for space. 270 */ 271 request = fs->fs_bsize; 272 if (fs->fs_cstotal.cs_nffree < 273 fs->fs_dsize * (fs->fs_minfree - 2) / 100) 274 break; 275 log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 276 fs->fs_fsmnt); 277 fs->fs_optim = FS_OPTSPACE; 278 break; 279 default: 280 printf("dev = 0x%lx, optim = %ld, fs = %s\n", 281 (u_long)ip->i_dev, fs->fs_optim, fs->fs_fsmnt); 282 panic("ffs_realloccg: bad optim"); 283 /* NOTREACHED */ 284 } 285 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 286 ffs_alloccg); 287 if (bno > 0) { 288 bp->b_blkno = fsbtodb(fs, bno); 289 ffs_blkfree(ip, bprev, (long)osize); 290 if (nsize < request) 291 ffs_blkfree(ip, bno + numfrags(fs, nsize), 292 (long)(request - nsize)); 293 ip->i_blocks += btodb(nsize - osize); 294 ip->i_flag |= IN_CHANGE | IN_UPDATE; 295 allocbuf(bp, nsize); 296 bp->b_flags |= B_DONE; 297 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 298 *bpp = bp; 299 return (0); 300 } 301#ifdef QUOTA 302 /* 303 * Restore user's disk quota because allocation failed. 304 */ 305 (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 306#endif 307 brelse(bp); 308nospace: 309 /* 310 * no space available 311 */ 312 ffs_fserr(fs, cred->cr_uid, "file system full"); 313 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 314 return (ENOSPC); 315} 316 317/* 318 * Reallocate a sequence of blocks into a contiguous sequence of blocks. 319 * 320 * The vnode and an array of buffer pointers for a range of sequential 321 * logical blocks to be made contiguous is given. The allocator attempts 322 * to find a range of sequential blocks starting as close as possible to 323 * an fs_rotdelay offset from the end of the allocation for the logical 324 * block immediately preceeding the current range. If successful, the 325 * physical block numbers in the buffer pointers and in the inode are 326 * changed to reflect the new allocation. If unsuccessful, the allocation 327 * is left unchanged. The success in doing the reallocation is returned. 328 * Note that the error return is not reflected back to the user. Rather 329 * the previous block allocation will be used. 330 */ 331static int doasyncfree = 1; 332SYSCTL_INT(_vfs_ffs, FFS_ASYNCFREE, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, ""); 333 334int doreallocblks = 1; 335SYSCTL_INT(_vfs_ffs, FFS_REALLOCBLKS, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, ""); 336 337static int prtrealloc = 0; 338 339int 340ffs_reallocblks(ap) 341 struct vop_reallocblks_args /* { 342 struct vnode *a_vp; 343 struct cluster_save *a_buflist; 344 } */ *ap; 345{ 346#if !defined (not_yes) 347 return (ENOSPC); 348#else 349 struct fs *fs; 350 struct inode *ip; 351 struct vnode *vp; 352 struct buf *sbp, *ebp; 353 ufs_daddr_t *bap, *sbap, *ebap = 0; 354 struct cluster_save *buflist; 355 ufs_daddr_t start_lbn, end_lbn, soff, newblk, blkno; 356 struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 357 int i, len, start_lvl, end_lvl, pref, ssize; 358 struct timeval tv; 359 360 if (doreallocblks == 0) 361 return (ENOSPC); 362 vp = ap->a_vp; 363 ip = VTOI(vp); 364 fs = ip->i_fs; 365 if (fs->fs_contigsumsize <= 0) 366 return (ENOSPC); 367 buflist = ap->a_buflist; 368 len = buflist->bs_nchildren; 369 start_lbn = buflist->bs_children[0]->b_lblkno; 370 end_lbn = start_lbn + len - 1; 371#ifdef DIAGNOSTIC 372 for (i = 0; i < len; i++) 373 if (!ffs_checkblk(ip, 374 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 375 panic("ffs_reallocblks: unallocated block 1"); 376 for (i = 1; i < len; i++) 377 if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 378 panic("ffs_reallocblks: non-logical cluster"); 379 blkno = buflist->bs_children[0]->b_blkno; 380 ssize = fsbtodb(fs, fs->fs_frag); 381 for (i = 1; i < len - 1; i++) 382 if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize)) 383 panic("ffs_reallocblks: non-physical cluster %d", i); 384#endif 385 /* 386 * If the latest allocation is in a new cylinder group, assume that 387 * the filesystem has decided to move and do not force it back to 388 * the previous cylinder group. 389 */ 390 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 391 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 392 return (ENOSPC); 393 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 394 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 395 return (ENOSPC); 396 /* 397 * Get the starting offset and block map for the first block. 398 */ 399 if (start_lvl == 0) { 400 sbap = &ip->i_db[0]; 401 soff = start_lbn; 402 } else { 403 idp = &start_ap[start_lvl - 1]; 404 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 405 brelse(sbp); 406 return (ENOSPC); 407 } 408 sbap = (ufs_daddr_t *)sbp->b_data; 409 soff = idp->in_off; 410 } 411 /* 412 * Find the preferred location for the cluster. 413 */ 414 pref = ffs_blkpref(ip, start_lbn, soff, sbap); 415 /* 416 * If the block range spans two block maps, get the second map. 417 */ 418 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 419 ssize = len; 420 } else { 421#ifdef DIAGNOSTIC 422 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 423 panic("ffs_reallocblk: start == end"); 424#endif 425 ssize = len - (idp->in_off + 1); 426 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 427 goto fail; 428 ebap = (ufs_daddr_t *)ebp->b_data; 429 } 430 /* 431 * Search the block map looking for an allocation of the desired size. 432 */ 433 if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref, 434 len, ffs_clusteralloc)) == 0) 435 goto fail; 436 /* 437 * We have found a new contiguous block. 438 * 439 * First we have to replace the old block pointers with the new 440 * block pointers in the inode and indirect blocks associated 441 * with the file. 442 */ 443#ifdef DEBUG 444 if (prtrealloc) 445 printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number, 446 start_lbn, end_lbn); 447#endif 448 blkno = newblk; 449 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 450 if (i == ssize) 451 bap = ebap; 452#ifdef DIAGNOSTIC 453 if (!ffs_checkblk(ip, 454 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 455 panic("ffs_reallocblks: unallocated block 2"); 456 if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap) 457 panic("ffs_reallocblks: alloc mismatch"); 458#endif 459#ifdef DEBUG 460 if (prtrealloc) 461 printf(" %d,", *bap); 462#endif 463 *bap++ = blkno; 464 } 465 /* 466 * Next we must write out the modified inode and indirect blocks. 467 * For strict correctness, the writes should be synchronous since 468 * the old block values may have been written to disk. In practise 469 * they are almost never written, but if we are concerned about 470 * strict correctness, the `doasyncfree' flag should be set to zero. 471 * 472 * The test on `doasyncfree' should be changed to test a flag 473 * that shows whether the associated buffers and inodes have 474 * been written. The flag should be set when the cluster is 475 * started and cleared whenever the buffer or inode is flushed. 476 * We can then check below to see if it is set, and do the 477 * synchronous write only when it has been cleared. 478 */ 479 if (sbap != &ip->i_db[0]) { 480 if (doasyncfree) 481 bdwrite(sbp); 482 else 483 bwrite(sbp); 484 } else { 485 ip->i_flag |= IN_CHANGE | IN_UPDATE; 486 if (!doasyncfree) { 487 gettime(&tv); 488 VOP_UPDATE(vp, &tv, &tv, 1); 489 } 490 } 491 if (ssize < len) 492 if (doasyncfree) 493 bdwrite(ebp); 494 else 495 bwrite(ebp); 496 /* 497 * Last, free the old blocks and assign the new blocks to the buffers. 498 */ 499#ifdef DEBUG 500 if (prtrealloc) 501 printf("\n\tnew:"); 502#endif 503 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 504 ffs_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno), 505 fs->fs_bsize); 506 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 507#ifdef DEBUG 508 if (!ffs_checkblk(ip, 509 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 510 panic("ffs_reallocblks: unallocated block 3"); 511 if (prtrealloc) 512 printf(" %d,", blkno); 513#endif 514 } 515#ifdef DEBUG 516 if (prtrealloc) { 517 prtrealloc--; 518 printf("\n"); 519 } 520#endif 521 return (0); 522 523fail: 524 if (ssize < len) 525 brelse(ebp); 526 if (sbap != &ip->i_db[0]) 527 brelse(sbp); 528 return (ENOSPC); 529#endif 530} 531 532/* 533 * Allocate an inode in the file system. 534 * 535 * If allocating a directory, use ffs_dirpref to select the inode. 536 * If allocating in a directory, the following hierarchy is followed: 537 * 1) allocate the preferred inode. 538 * 2) allocate an inode in the same cylinder group. 539 * 3) quadradically rehash into other cylinder groups, until an 540 * available inode is located. 541 * If no inode preference is given the following heirarchy is used 542 * to allocate an inode: 543 * 1) allocate an inode in cylinder group 0. 544 * 2) quadradically rehash into other cylinder groups, until an 545 * available inode is located. 546 */ 547int 548ffs_valloc(ap) 549 struct vop_valloc_args /* { 550 struct vnode *a_pvp; 551 int a_mode; 552 struct ucred *a_cred; 553 struct vnode **a_vpp; 554 } */ *ap; 555{ 556 register struct vnode *pvp = ap->a_pvp; 557 register struct inode *pip; 558 register struct fs *fs; 559 register struct inode *ip; 560 mode_t mode = ap->a_mode; 561 ino_t ino, ipref; 562 int cg, error; 563 564 *ap->a_vpp = NULL; 565 pip = VTOI(pvp); 566 fs = pip->i_fs; 567 if (fs->fs_cstotal.cs_nifree == 0) 568 goto noinodes; 569 570 if ((mode & IFMT) == IFDIR) 571 ipref = ffs_dirpref(fs); 572 else 573 ipref = pip->i_number; 574 if (ipref >= fs->fs_ncg * fs->fs_ipg) 575 ipref = 0; 576 cg = ino_to_cg(fs, ipref); 577 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, 578 (allocfcn_t *)ffs_nodealloccg); 579 if (ino == 0) 580 goto noinodes; 581 error = VFS_VGET(pvp->v_mount, ino, ap->a_vpp); 582 if (error) { 583 VOP_VFREE(pvp, ino, mode); 584 return (error); 585 } 586 ip = VTOI(*ap->a_vpp); 587 if (ip->i_mode) { 588 printf("mode = 0%o, inum = %ld, fs = %s\n", 589 ip->i_mode, ip->i_number, fs->fs_fsmnt); 590 panic("ffs_valloc: dup alloc"); 591 } 592 if (ip->i_blocks) { /* XXX */ 593 printf("free inode %s/%ld had %ld blocks\n", 594 fs->fs_fsmnt, ino, ip->i_blocks); 595 ip->i_blocks = 0; 596 } 597 ip->i_flags = 0; 598 /* 599 * Set up a new generation number for this inode. 600 */ 601 if (ip->i_gen == 0 || ++(ip->i_gen) == 0) 602 ip->i_gen = random() / 2 + 1; 603 return (0); 604noinodes: 605 ffs_fserr(fs, ap->a_cred->cr_uid, "out of inodes"); 606 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 607 return (ENOSPC); 608} 609 610/* 611 * Find a cylinder to place a directory. 612 * 613 * The policy implemented by this algorithm is to select from 614 * among those cylinder groups with above the average number of 615 * free inodes, the one with the smallest number of directories. 616 */ 617static ino_t 618ffs_dirpref(fs) 619 register struct fs *fs; 620{ 621 int cg, minndir, mincg, avgifree; 622 623 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 624 minndir = fs->fs_ipg; 625 mincg = 0; 626 for (cg = 0; cg < fs->fs_ncg; cg++) 627 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 628 fs->fs_cs(fs, cg).cs_nifree >= avgifree) { 629 mincg = cg; 630 minndir = fs->fs_cs(fs, cg).cs_ndir; 631 } 632 return ((ino_t)(fs->fs_ipg * mincg)); 633} 634 635/* 636 * Select the desired position for the next block in a file. The file is 637 * logically divided into sections. The first section is composed of the 638 * direct blocks. Each additional section contains fs_maxbpg blocks. 639 * 640 * If no blocks have been allocated in the first section, the policy is to 641 * request a block in the same cylinder group as the inode that describes 642 * the file. If no blocks have been allocated in any other section, the 643 * policy is to place the section in a cylinder group with a greater than 644 * average number of free blocks. An appropriate cylinder group is found 645 * by using a rotor that sweeps the cylinder groups. When a new group of 646 * blocks is needed, the sweep begins in the cylinder group following the 647 * cylinder group from which the previous allocation was made. The sweep 648 * continues until a cylinder group with greater than the average number 649 * of free blocks is found. If the allocation is for the first block in an 650 * indirect block, the information on the previous allocation is unavailable; 651 * here a best guess is made based upon the logical block number being 652 * allocated. 653 * 654 * If a section is already partially allocated, the policy is to 655 * contiguously allocate fs_maxcontig blocks. The end of one of these 656 * contiguous blocks and the beginning of the next is physically separated 657 * so that the disk head will be in transit between them for at least 658 * fs_rotdelay milliseconds. This is to allow time for the processor to 659 * schedule another I/O transfer. 660 */ 661ufs_daddr_t 662ffs_blkpref(ip, lbn, indx, bap) 663 struct inode *ip; 664 ufs_daddr_t lbn; 665 int indx; 666 ufs_daddr_t *bap; 667{ 668 register struct fs *fs; 669 register int cg; 670 int avgbfree, startcg; 671 ufs_daddr_t nextblk; 672 673 fs = ip->i_fs; 674 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 675 if (lbn < NDADDR) { 676 cg = ino_to_cg(fs, ip->i_number); 677 return (fs->fs_fpg * cg + fs->fs_frag); 678 } 679 /* 680 * Find a cylinder with greater than average number of 681 * unused data blocks. 682 */ 683 if (indx == 0 || bap[indx - 1] == 0) 684 startcg = 685 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 686 else 687 startcg = dtog(fs, bap[indx - 1]) + 1; 688 startcg %= fs->fs_ncg; 689 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 690 for (cg = startcg; cg < fs->fs_ncg; cg++) 691 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 692 fs->fs_cgrotor = cg; 693 return (fs->fs_fpg * cg + fs->fs_frag); 694 } 695 for (cg = 0; cg <= startcg; cg++) 696 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 697 fs->fs_cgrotor = cg; 698 return (fs->fs_fpg * cg + fs->fs_frag); 699 } 700 return (0); 701 } 702 /* 703 * One or more previous blocks have been laid out. If less 704 * than fs_maxcontig previous blocks are contiguous, the 705 * next block is requested contiguously, otherwise it is 706 * requested rotationally delayed by fs_rotdelay milliseconds. 707 */ 708 nextblk = bap[indx - 1] + fs->fs_frag; 709 if (fs->fs_rotdelay == 0 || indx < fs->fs_maxcontig || 710 bap[indx - fs->fs_maxcontig] + 711 blkstofrags(fs, fs->fs_maxcontig) != nextblk) 712 return (nextblk); 713 /* 714 * Here we convert ms of delay to frags as: 715 * (frags) = (ms) * (rev/sec) * (sect/rev) / 716 * ((sect/frag) * (ms/sec)) 717 * then round up to the next block. 718 */ 719 nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 720 (NSPF(fs) * 1000), fs->fs_frag); 721 return (nextblk); 722} 723 724/* 725 * Implement the cylinder overflow algorithm. 726 * 727 * The policy implemented by this algorithm is: 728 * 1) allocate the block in its requested cylinder group. 729 * 2) quadradically rehash on the cylinder group number. 730 * 3) brute force search for a free block. 731 */ 732/*VARARGS5*/ 733static u_long 734ffs_hashalloc(ip, cg, pref, size, allocator) 735 struct inode *ip; 736 int cg; 737 long pref; 738 int size; /* size for data blocks, mode for inodes */ 739 allocfcn_t *allocator; 740{ 741 register struct fs *fs; 742 long result; /* XXX why not same type as we return? */ 743 int i, icg = cg; 744 745 fs = ip->i_fs; 746 /* 747 * 1: preferred cylinder group 748 */ 749 result = (*allocator)(ip, cg, pref, size); 750 if (result) 751 return (result); 752 /* 753 * 2: quadratic rehash 754 */ 755 for (i = 1; i < fs->fs_ncg; i *= 2) { 756 cg += i; 757 if (cg >= fs->fs_ncg) 758 cg -= fs->fs_ncg; 759 result = (*allocator)(ip, cg, 0, size); 760 if (result) 761 return (result); 762 } 763 /* 764 * 3: brute force search 765 * Note that we start at i == 2, since 0 was checked initially, 766 * and 1 is always checked in the quadratic rehash. 767 */ 768 cg = (icg + 2) % fs->fs_ncg; 769 for (i = 2; i < fs->fs_ncg; i++) { 770 result = (*allocator)(ip, cg, 0, size); 771 if (result) 772 return (result); 773 cg++; 774 if (cg == fs->fs_ncg) 775 cg = 0; 776 } 777 return (0); 778} 779 780/* 781 * Determine whether a fragment can be extended. 782 * 783 * Check to see if the necessary fragments are available, and 784 * if they are, allocate them. 785 */ 786static ufs_daddr_t 787ffs_fragextend(ip, cg, bprev, osize, nsize) 788 struct inode *ip; 789 int cg; 790 long bprev; 791 int osize, nsize; 792{ 793 register struct fs *fs; 794 register struct cg *cgp; 795 struct buf *bp; 796 long bno; 797 int frags, bbase; 798 int i, error; 799 800 fs = ip->i_fs; 801 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 802 return (0); 803 frags = numfrags(fs, nsize); 804 bbase = fragnum(fs, bprev); 805 if (bbase > fragnum(fs, (bprev + frags - 1))) { 806 /* cannot extend across a block boundary */ 807 return (0); 808 } 809 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 810 (int)fs->fs_cgsize, NOCRED, &bp); 811 if (error) { 812 brelse(bp); 813 return (0); 814 } 815 cgp = (struct cg *)bp->b_data; 816 if (!cg_chkmagic(cgp)) { 817 brelse(bp); 818 return (0); 819 } 820 cgp->cg_time = time.tv_sec; 821 bno = dtogd(fs, bprev); 822 for (i = numfrags(fs, osize); i < frags; i++) 823 if (isclr(cg_blksfree(cgp), bno + i)) { 824 brelse(bp); 825 return (0); 826 } 827 /* 828 * the current fragment can be extended 829 * deduct the count on fragment being extended into 830 * increase the count on the remaining fragment (if any) 831 * allocate the extended piece 832 */ 833 for (i = frags; i < fs->fs_frag - bbase; i++) 834 if (isclr(cg_blksfree(cgp), bno + i)) 835 break; 836 cgp->cg_frsum[i - numfrags(fs, osize)]--; 837 if (i != frags) 838 cgp->cg_frsum[i - frags]++; 839 for (i = numfrags(fs, osize); i < frags; i++) { 840 clrbit(cg_blksfree(cgp), bno + i); 841 cgp->cg_cs.cs_nffree--; 842 fs->fs_cstotal.cs_nffree--; 843 fs->fs_cs(fs, cg).cs_nffree--; 844 } 845 fs->fs_fmod = 1; 846 bdwrite(bp); 847 return (bprev); 848} 849 850/* 851 * Determine whether a block can be allocated. 852 * 853 * Check to see if a block of the appropriate size is available, 854 * and if it is, allocate it. 855 */ 856static ufs_daddr_t 857ffs_alloccg(ip, cg, bpref, size) 858 struct inode *ip; 859 int cg; 860 ufs_daddr_t bpref; 861 int size; 862{ 863 register struct fs *fs; 864 register struct cg *cgp; 865 struct buf *bp; 866 register int i; 867 int error, bno, frags, allocsiz; 868 869 fs = ip->i_fs; 870 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 871 return (0); 872 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 873 (int)fs->fs_cgsize, NOCRED, &bp); 874 if (error) { 875 brelse(bp); 876 return (0); 877 } 878 cgp = (struct cg *)bp->b_data; 879 if (!cg_chkmagic(cgp) || 880 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 881 brelse(bp); 882 return (0); 883 } 884 cgp->cg_time = time.tv_sec; 885 if (size == fs->fs_bsize) { 886 bno = ffs_alloccgblk(fs, cgp, bpref); 887 bdwrite(bp); 888 return (bno); 889 } 890 /* 891 * check to see if any fragments are already available 892 * allocsiz is the size which will be allocated, hacking 893 * it down to a smaller size if necessary 894 */ 895 frags = numfrags(fs, size); 896 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 897 if (cgp->cg_frsum[allocsiz] != 0) 898 break; 899 if (allocsiz == fs->fs_frag) { 900 /* 901 * no fragments were available, so a block will be 902 * allocated, and hacked up 903 */ 904 if (cgp->cg_cs.cs_nbfree == 0) { 905 brelse(bp); 906 return (0); 907 } 908 bno = ffs_alloccgblk(fs, cgp, bpref); 909 bpref = dtogd(fs, bno); 910 for (i = frags; i < fs->fs_frag; i++) 911 setbit(cg_blksfree(cgp), bpref + i); 912 i = fs->fs_frag - frags; 913 cgp->cg_cs.cs_nffree += i; 914 fs->fs_cstotal.cs_nffree += i; 915 fs->fs_cs(fs, cg).cs_nffree += i; 916 fs->fs_fmod = 1; 917 cgp->cg_frsum[i]++; 918 bdwrite(bp); 919 return (bno); 920 } 921 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 922 if (bno < 0) { 923 brelse(bp); 924 return (0); 925 } 926 for (i = 0; i < frags; i++) 927 clrbit(cg_blksfree(cgp), bno + i); 928 cgp->cg_cs.cs_nffree -= frags; 929 fs->fs_cstotal.cs_nffree -= frags; 930 fs->fs_cs(fs, cg).cs_nffree -= frags; 931 fs->fs_fmod = 1; 932 cgp->cg_frsum[allocsiz]--; 933 if (frags != allocsiz) 934 cgp->cg_frsum[allocsiz - frags]++; 935 bdwrite(bp); 936 return (cg * fs->fs_fpg + bno); 937} 938 939/* 940 * Allocate a block in a cylinder group. 941 * 942 * This algorithm implements the following policy: 943 * 1) allocate the requested block. 944 * 2) allocate a rotationally optimal block in the same cylinder. 945 * 3) allocate the next available block on the block rotor for the 946 * specified cylinder group. 947 * Note that this routine only allocates fs_bsize blocks; these 948 * blocks may be fragmented by the routine that allocates them. 949 */ 950static ufs_daddr_t 951ffs_alloccgblk(fs, cgp, bpref) 952 register struct fs *fs; 953 register struct cg *cgp; 954 ufs_daddr_t bpref; 955{ 956 ufs_daddr_t bno, blkno; 957 int cylno, pos, delta; 958 short *cylbp; 959 register int i; 960 961 if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) { 962 bpref = cgp->cg_rotor; 963 goto norot; 964 } 965 bpref = blknum(fs, bpref); 966 bpref = dtogd(fs, bpref); 967 /* 968 * if the requested block is available, use it 969 */ 970 if (ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bpref))) { 971 bno = bpref; 972 goto gotit; 973 } 974 if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) { 975 /* 976 * Block layout information is not available. 977 * Leaving bpref unchanged means we take the 978 * next available free block following the one 979 * we just allocated. Hopefully this will at 980 * least hit a track cache on drives of unknown 981 * geometry (e.g. SCSI). 982 */ 983 goto norot; 984 } 985 /* 986 * check for a block available on the same cylinder 987 */ 988 cylno = cbtocylno(fs, bpref); 989 if (cg_blktot(cgp)[cylno] == 0) 990 goto norot; 991 /* 992 * check the summary information to see if a block is 993 * available in the requested cylinder starting at the 994 * requested rotational position and proceeding around. 995 */ 996 cylbp = cg_blks(fs, cgp, cylno); 997 pos = cbtorpos(fs, bpref); 998 for (i = pos; i < fs->fs_nrpos; i++) 999 if (cylbp[i] > 0) 1000 break; 1001 if (i == fs->fs_nrpos) 1002 for (i = 0; i < pos; i++) 1003 if (cylbp[i] > 0) 1004 break; 1005 if (cylbp[i] > 0) { 1006 /* 1007 * found a rotational position, now find the actual 1008 * block. A panic if none is actually there. 1009 */ 1010 pos = cylno % fs->fs_cpc; 1011 bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 1012 if (fs_postbl(fs, pos)[i] == -1) { 1013 printf("pos = %d, i = %d, fs = %s\n", 1014 pos, i, fs->fs_fsmnt); 1015 panic("ffs_alloccgblk: cyl groups corrupted"); 1016 } 1017 for (i = fs_postbl(fs, pos)[i];; ) { 1018 if (ffs_isblock(fs, cg_blksfree(cgp), bno + i)) { 1019 bno = blkstofrags(fs, (bno + i)); 1020 goto gotit; 1021 } 1022 delta = fs_rotbl(fs)[i]; 1023 if (delta <= 0 || 1024 delta + i > fragstoblks(fs, fs->fs_fpg)) 1025 break; 1026 i += delta; 1027 } 1028 printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 1029 panic("ffs_alloccgblk: can't find blk in cyl"); 1030 } 1031norot: 1032 /* 1033 * no blocks in the requested cylinder, so take next 1034 * available one in this cylinder group. 1035 */ 1036 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 1037 if (bno < 0) 1038 return (0); 1039 cgp->cg_rotor = bno; 1040gotit: 1041 blkno = fragstoblks(fs, bno); 1042 ffs_clrblock(fs, cg_blksfree(cgp), (long)blkno); 1043 ffs_clusteracct(fs, cgp, blkno, -1); 1044 cgp->cg_cs.cs_nbfree--; 1045 fs->fs_cstotal.cs_nbfree--; 1046 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 1047 cylno = cbtocylno(fs, bno); 1048 cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 1049 cg_blktot(cgp)[cylno]--; 1050 fs->fs_fmod = 1; 1051 return (cgp->cg_cgx * fs->fs_fpg + bno); 1052} 1053 1054#ifdef notyet 1055/* 1056 * Determine whether a cluster can be allocated. 1057 * 1058 * We do not currently check for optimal rotational layout if there 1059 * are multiple choices in the same cylinder group. Instead we just 1060 * take the first one that we find following bpref. 1061 */ 1062static ufs_daddr_t 1063ffs_clusteralloc(ip, cg, bpref, len) 1064 struct inode *ip; 1065 int cg; 1066 ufs_daddr_t bpref; 1067 int len; 1068{ 1069 register struct fs *fs; 1070 register struct cg *cgp; 1071 struct buf *bp; 1072 int i, got, run, bno, bit, map; 1073 u_char *mapp; 1074 int32_t *lp; 1075 1076 fs = ip->i_fs; 1077 if (fs->fs_maxcluster[cg] < len) 1078 return (NULL); 1079 if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 1080 NOCRED, &bp)) 1081 goto fail; 1082 cgp = (struct cg *)bp->b_data; 1083 if (!cg_chkmagic(cgp)) 1084 goto fail; 1085 /* 1086 * Check to see if a cluster of the needed size (or bigger) is 1087 * available in this cylinder group. 1088 */ 1089 lp = &cg_clustersum(cgp)[len]; 1090 for (i = len; i <= fs->fs_contigsumsize; i++) 1091 if (*lp++ > 0) 1092 break; 1093 if (i > fs->fs_contigsumsize) { 1094 /* 1095 * This is the first time looking for a cluster in this 1096 * cylinder group. Update the cluster summary information 1097 * to reflect the true maximum sized cluster so that 1098 * future cluster allocation requests can avoid reading 1099 * the cylinder group map only to find no clusters. 1100 */ 1101 lp = &cg_clustersum(cgp)[len - 1]; 1102 for (i = len - 1; i > 0; i--) 1103 if (*lp-- > 0) 1104 break; 1105 fs->fs_maxcluster[cg] = i; 1106 goto fail; 1107 } 1108 /* 1109 * Search the cluster map to find a big enough cluster. 1110 * We take the first one that we find, even if it is larger 1111 * than we need as we prefer to get one close to the previous 1112 * block allocation. We do not search before the current 1113 * preference point as we do not want to allocate a block 1114 * that is allocated before the previous one (as we will 1115 * then have to wait for another pass of the elevator 1116 * algorithm before it will be read). We prefer to fail and 1117 * be recalled to try an allocation in the next cylinder group. 1118 */ 1119 if (dtog(fs, bpref) != cg) 1120 bpref = 0; 1121 else 1122 bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 1123 mapp = &cg_clustersfree(cgp)[bpref / NBBY]; 1124 map = *mapp++; 1125 bit = 1 << (bpref % NBBY); 1126 for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) { 1127 if ((map & bit) == 0) { 1128 run = 0; 1129 } else { 1130 run++; 1131 if (run == len) 1132 break; 1133 } 1134 if ((got & (NBBY - 1)) != (NBBY - 1)) { 1135 bit <<= 1; 1136 } else { 1137 map = *mapp++; 1138 bit = 1; 1139 } 1140 } 1141 if (got >= cgp->cg_nclusterblks) 1142 goto fail; 1143 /* 1144 * Allocate the cluster that we have found. 1145 */ 1146 for (i = 1; i <= len; i++) 1147 if (!ffs_isblock(fs, cg_blksfree(cgp), got - run + i)) 1148 panic("ffs_clusteralloc: map mismatch"); 1149 bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1); 1150 if (dtog(fs, bno) != cg) 1151 panic("ffs_clusteralloc: allocated out of group"); 1152 len = blkstofrags(fs, len); 1153 for (i = 0; i < len; i += fs->fs_frag) 1154 if ((got = ffs_alloccgblk(fs, cgp, bno + i)) != bno + i) 1155 panic("ffs_clusteralloc: lost block"); 1156 bdwrite(bp); 1157 return (bno); 1158 1159fail: 1160 brelse(bp); 1161 return (0); 1162} 1163#endif 1164 1165/* 1166 * Determine whether an inode can be allocated. 1167 * 1168 * Check to see if an inode is available, and if it is, 1169 * allocate it using the following policy: 1170 * 1) allocate the requested inode. 1171 * 2) allocate the next available inode after the requested 1172 * inode in the specified cylinder group. 1173 */ 1174static ino_t 1175ffs_nodealloccg(ip, cg, ipref, mode) 1176 struct inode *ip; 1177 int cg; 1178 ufs_daddr_t ipref; 1179 int mode; 1180{ 1181 register struct fs *fs; 1182 register struct cg *cgp; 1183 struct buf *bp; 1184 int error, start, len, loc, map, i; 1185 1186 fs = ip->i_fs; 1187 if (fs->fs_cs(fs, cg).cs_nifree == 0) 1188 return (0); 1189 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1190 (int)fs->fs_cgsize, NOCRED, &bp); 1191 if (error) { 1192 brelse(bp); 1193 return (0); 1194 } 1195 cgp = (struct cg *)bp->b_data; 1196 if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 1197 brelse(bp); 1198 return (0); 1199 } 1200 cgp->cg_time = time.tv_sec; 1201 if (ipref) { 1202 ipref %= fs->fs_ipg; 1203 if (isclr(cg_inosused(cgp), ipref)) 1204 goto gotit; 1205 } 1206 start = cgp->cg_irotor / NBBY; 1207 len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 1208 loc = skpc(0xff, len, &cg_inosused(cgp)[start]); 1209 if (loc == 0) { 1210 len = start + 1; 1211 start = 0; 1212 loc = skpc(0xff, len, &cg_inosused(cgp)[0]); 1213 if (loc == 0) { 1214 printf("cg = %d, irotor = %ld, fs = %s\n", 1215 cg, cgp->cg_irotor, fs->fs_fsmnt); 1216 panic("ffs_nodealloccg: map corrupted"); 1217 /* NOTREACHED */ 1218 } 1219 } 1220 i = start + len - loc; 1221 map = cg_inosused(cgp)[i]; 1222 ipref = i * NBBY; 1223 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 1224 if ((map & i) == 0) { 1225 cgp->cg_irotor = ipref; 1226 goto gotit; 1227 } 1228 } 1229 printf("fs = %s\n", fs->fs_fsmnt); 1230 panic("ffs_nodealloccg: block not in map"); 1231 /* NOTREACHED */ 1232gotit: 1233 setbit(cg_inosused(cgp), ipref); 1234 cgp->cg_cs.cs_nifree--; 1235 fs->fs_cstotal.cs_nifree--; 1236 fs->fs_cs(fs, cg).cs_nifree--; 1237 fs->fs_fmod = 1; 1238 if ((mode & IFMT) == IFDIR) { 1239 cgp->cg_cs.cs_ndir++; 1240 fs->fs_cstotal.cs_ndir++; 1241 fs->fs_cs(fs, cg).cs_ndir++; 1242 } 1243 bdwrite(bp); 1244 return (cg * fs->fs_ipg + ipref); 1245} 1246 1247/* 1248 * Free a block or fragment. 1249 * 1250 * The specified block or fragment is placed back in the 1251 * free map. If a fragment is deallocated, a possible 1252 * block reassembly is checked. 1253 */ 1254void 1255ffs_blkfree(ip, bno, size) 1256 register struct inode *ip; 1257 ufs_daddr_t bno; 1258 long size; 1259{ 1260 register struct fs *fs; 1261 register struct cg *cgp; 1262 struct buf *bp; 1263 ufs_daddr_t blkno; 1264 int i, error, cg, blk, frags, bbase; 1265 1266 fs = ip->i_fs; 1267 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1268 printf("dev = 0x%lx, bsize = %ld, size = %ld, fs = %s\n", 1269 (u_long)ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 1270 panic("ffs_blkfree: bad size"); 1271 } 1272 cg = dtog(fs, bno); 1273 if ((u_int)bno >= fs->fs_size) { 1274 printf("bad block %ld, ino %ld\n", bno, ip->i_number); 1275 ffs_fserr(fs, ip->i_uid, "bad block"); 1276 return; 1277 } 1278 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1279 (int)fs->fs_cgsize, NOCRED, &bp); 1280 if (error) { 1281 brelse(bp); 1282 return; 1283 } 1284 cgp = (struct cg *)bp->b_data; 1285 if (!cg_chkmagic(cgp)) { 1286 brelse(bp); 1287 return; 1288 } 1289 cgp->cg_time = time.tv_sec; 1290 bno = dtogd(fs, bno); 1291 if (size == fs->fs_bsize) { 1292 blkno = fragstoblks(fs, bno); 1293 if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 1294 printf("dev = 0x%lx, block = %ld, fs = %s\n", 1295 (u_long) ip->i_dev, bno, fs->fs_fsmnt); 1296 panic("ffs_blkfree: freeing free block"); 1297 } 1298 ffs_setblock(fs, cg_blksfree(cgp), blkno); 1299 ffs_clusteracct(fs, cgp, blkno, 1); 1300 cgp->cg_cs.cs_nbfree++; 1301 fs->fs_cstotal.cs_nbfree++; 1302 fs->fs_cs(fs, cg).cs_nbfree++; 1303 i = cbtocylno(fs, bno); 1304 cg_blks(fs, cgp, i)[cbtorpos(fs, bno)]++; 1305 cg_blktot(cgp)[i]++; 1306 } else { 1307 bbase = bno - fragnum(fs, bno); 1308 /* 1309 * decrement the counts associated with the old frags 1310 */ 1311 blk = blkmap(fs, cg_blksfree(cgp), bbase); 1312 ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 1313 /* 1314 * deallocate the fragment 1315 */ 1316 frags = numfrags(fs, size); 1317 for (i = 0; i < frags; i++) { 1318 if (isset(cg_blksfree(cgp), bno + i)) { 1319 printf("dev = 0x%lx, block = %ld, fs = %s\n", 1320 (u_long) ip->i_dev, bno + i, fs->fs_fsmnt); 1321 panic("ffs_blkfree: freeing free frag"); 1322 } 1323 setbit(cg_blksfree(cgp), bno + i); 1324 } 1325 cgp->cg_cs.cs_nffree += i; 1326 fs->fs_cstotal.cs_nffree += i; 1327 fs->fs_cs(fs, cg).cs_nffree += i; 1328 /* 1329 * add back in counts associated with the new frags 1330 */ 1331 blk = blkmap(fs, cg_blksfree(cgp), bbase); 1332 ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 1333 /* 1334 * if a complete block has been reassembled, account for it 1335 */ 1336 blkno = fragstoblks(fs, bbase); 1337 if (ffs_isblock(fs, cg_blksfree(cgp), blkno)) { 1338 cgp->cg_cs.cs_nffree -= fs->fs_frag; 1339 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 1340 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 1341 ffs_clusteracct(fs, cgp, blkno, 1); 1342 cgp->cg_cs.cs_nbfree++; 1343 fs->fs_cstotal.cs_nbfree++; 1344 fs->fs_cs(fs, cg).cs_nbfree++; 1345 i = cbtocylno(fs, bbase); 1346 cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 1347 cg_blktot(cgp)[i]++; 1348 } 1349 } 1350 fs->fs_fmod = 1; 1351 bdwrite(bp); 1352} 1353 1354#ifdef DIAGNOSTIC 1355/* 1356 * Verify allocation of a block or fragment. Returns true if block or 1357 * fragment is allocated, false if it is free. 1358 */ 1359int 1360ffs_checkblk(ip, bno, size) 1361 struct inode *ip; 1362 ufs_daddr_t bno; 1363 long size; 1364{ 1365 struct fs *fs; 1366 struct cg *cgp; 1367 struct buf *bp; 1368 int i, error, frags, free; 1369 1370 fs = ip->i_fs; 1371 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1372 printf("bsize = %d, size = %d, fs = %s\n", 1373 fs->fs_bsize, size, fs->fs_fsmnt); 1374 panic("ffs_checkblk: bad size"); 1375 } 1376 if ((u_int)bno >= fs->fs_size) 1377 panic("ffs_checkblk: bad block %d", bno); 1378 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))), 1379 (int)fs->fs_cgsize, NOCRED, &bp); 1380 if (error) 1381 panic("ffs_checkblk: cg bread failed"); 1382 cgp = (struct cg *)bp->b_data; 1383 if (!cg_chkmagic(cgp)) 1384 panic("ffs_checkblk: cg magic mismatch"); 1385 bno = dtogd(fs, bno); 1386 if (size == fs->fs_bsize) { 1387 free = ffs_isblock(fs, cg_blksfree(cgp), fragstoblks(fs, bno)); 1388 } else { 1389 frags = numfrags(fs, size); 1390 for (free = 0, i = 0; i < frags; i++) 1391 if (isset(cg_blksfree(cgp), bno + i)) 1392 free++; 1393 if (free != 0 && free != frags) 1394 panic("ffs_checkblk: partially free fragment"); 1395 } 1396 brelse(bp); 1397 return (!free); 1398} 1399#endif /* DIAGNOSTIC */ 1400 1401/* 1402 * Free an inode. 1403 * 1404 * The specified inode is placed back in the free map. 1405 */ 1406int 1407ffs_vfree(ap) 1408 struct vop_vfree_args /* { 1409 struct vnode *a_pvp; 1410 ino_t a_ino; 1411 int a_mode; 1412 } */ *ap; 1413{ 1414 register struct fs *fs; 1415 register struct cg *cgp; 1416 register struct inode *pip; 1417 ino_t ino = ap->a_ino; 1418 struct buf *bp; 1419 int error, cg; 1420 1421 pip = VTOI(ap->a_pvp);
|