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