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