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