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