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