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