1 /* $NetBSD: ffs_alloc.c,v 1.55 2002/05/14 02:46:22 matt Exp $ */ 2 3 /* 4 * Copyright (c) 1982, 1986, 1989, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by the University of 18 * California, Berkeley and its contributors. 19 * 4. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 * 35 * @(#)ffs_alloc.c 8.19 (Berkeley) 7/13/95 36 */ 37 38 #include <sys/cdefs.h> 39 __KERNEL_RCSID(0, "$NetBSD: ffs_alloc.c,v 1.55 2002/05/14 02:46:22 matt Exp $"); 40 41 #if defined(_KERNEL_OPT) 42 #include "opt_ffs.h" 43 #include "opt_quota.h" 44 #endif 45 46 #include <sys/param.h> 47 #include <sys/systm.h> 48 #include <sys/buf.h> 49 #include <sys/proc.h> 50 #include <sys/vnode.h> 51 #include <sys/mount.h> 52 #include <sys/kernel.h> 53 #include <sys/syslog.h> 54 55 #include <ufs/ufs/quota.h> 56 #include <ufs/ufs/ufsmount.h> 57 #include <ufs/ufs/inode.h> 58 #include <ufs/ufs/ufs_extern.h> 59 #include <ufs/ufs/ufs_bswap.h> 60 61 #include <ufs/ffs/fs.h> 62 #include <ufs/ffs/ffs_extern.h> 63 64 static ufs_daddr_t ffs_alloccg __P((struct inode *, int, ufs_daddr_t, int)); 65 static ufs_daddr_t ffs_alloccgblk __P((struct inode *, struct buf *, ufs_daddr_t)); 66 #ifdef XXXUBC 67 static ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t, int)); 68 #endif 69 static ino_t ffs_dirpref __P((struct inode *)); 70 static ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 71 static void ffs_fserr __P((struct fs *, u_int, char *)); 72 static u_long ffs_hashalloc __P((struct inode *, int, long, int, 73 ufs_daddr_t (*)(struct inode *, int, ufs_daddr_t, int))); 74 static ufs_daddr_t ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int)); 75 static ufs_daddr_t ffs_mapsearch __P((struct fs *, struct cg *, 76 ufs_daddr_t, int)); 77 #if defined(DIAGNOSTIC) || defined(DEBUG) 78 #ifdef XXXUBC 79 static int ffs_checkblk __P((struct inode *, ufs_daddr_t, long size)); 80 #endif 81 #endif 82 83 /* if 1, changes in optimalization strategy are logged */ 84 int ffs_log_changeopt = 0; 85 86 /* in ffs_tables.c */ 87 extern const int inside[], around[]; 88 extern const u_char * const fragtbl[]; 89 90 /* 91 * Allocate a block in the file system. 92 * 93 * The size of the requested block is given, which must be some 94 * multiple of fs_fsize and <= fs_bsize. 95 * A preference may be optionally specified. If a preference is given 96 * the following hierarchy is used to allocate a block: 97 * 1) allocate the requested block. 98 * 2) allocate a rotationally optimal block in the same cylinder. 99 * 3) allocate a block in the same cylinder group. 100 * 4) quadradically rehash into other cylinder groups, until an 101 * available block is located. 102 * If no block preference is given the following hierarchy is used 103 * to allocate a block: 104 * 1) allocate a block in the cylinder group that contains the 105 * inode for the file. 106 * 2) quadradically rehash into other cylinder groups, until an 107 * available block is located. 108 */ 109 int 110 ffs_alloc(ip, lbn, bpref, size, cred, bnp) 111 struct inode *ip; 112 ufs_daddr_t lbn, bpref; 113 int size; 114 struct ucred *cred; 115 ufs_daddr_t *bnp; 116 { 117 struct fs *fs = ip->i_fs; 118 ufs_daddr_t bno; 119 int cg; 120 #ifdef QUOTA 121 int error; 122 #endif 123 124 #ifdef UVM_PAGE_TRKOWN 125 if (ITOV(ip)->v_type == VREG && 126 lblktosize(fs, (voff_t)lbn) < round_page(ITOV(ip)->v_size)) { 127 struct vm_page *pg; 128 struct uvm_object *uobj = &ITOV(ip)->v_uobj; 129 voff_t off = trunc_page(lblktosize(fs, lbn)); 130 voff_t endoff = round_page(lblktosize(fs, lbn) + size); 131 132 simple_lock(&uobj->vmobjlock); 133 while (off < endoff) { 134 pg = uvm_pagelookup(uobj, off); 135 KASSERT(pg != NULL); 136 KASSERT(pg->owner == curproc->p_pid); 137 KASSERT((pg->flags & PG_CLEAN) == 0); 138 off += PAGE_SIZE; 139 } 140 simple_unlock(&uobj->vmobjlock); 141 } 142 #endif 143 144 *bnp = 0; 145 #ifdef DIAGNOSTIC 146 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 147 printf("dev = 0x%x, bsize = %d, size = %d, fs = %s\n", 148 ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 149 panic("ffs_alloc: bad size"); 150 } 151 if (cred == NOCRED) 152 panic("ffs_alloc: missing credential\n"); 153 #endif /* DIAGNOSTIC */ 154 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 155 goto nospace; 156 if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) 157 goto nospace; 158 #ifdef QUOTA 159 if ((error = chkdq(ip, (long)btodb(size), cred, 0)) != 0) 160 return (error); 161 #endif 162 if (bpref >= fs->fs_size) 163 bpref = 0; 164 if (bpref == 0) 165 cg = ino_to_cg(fs, ip->i_number); 166 else 167 cg = dtog(fs, bpref); 168 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 169 ffs_alloccg); 170 if (bno > 0) { 171 ip->i_ffs_blocks += btodb(size); 172 ip->i_flag |= IN_CHANGE | IN_UPDATE; 173 *bnp = bno; 174 return (0); 175 } 176 #ifdef QUOTA 177 /* 178 * Restore user's disk quota because allocation failed. 179 */ 180 (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 181 #endif 182 nospace: 183 ffs_fserr(fs, cred->cr_uid, "file system full"); 184 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 185 return (ENOSPC); 186 } 187 188 /* 189 * Reallocate a fragment to a bigger size 190 * 191 * The number and size of the old block is given, and a preference 192 * and new size is also specified. The allocator attempts to extend 193 * the original block. Failing that, the regular block allocator is 194 * invoked to get an appropriate block. 195 */ 196 int 197 ffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp, blknop) 198 struct inode *ip; 199 ufs_daddr_t lbprev; 200 ufs_daddr_t bpref; 201 int osize, nsize; 202 struct ucred *cred; 203 struct buf **bpp; 204 ufs_daddr_t *blknop; 205 { 206 struct fs *fs = ip->i_fs; 207 struct buf *bp; 208 int cg, request, error; 209 ufs_daddr_t bprev, bno; 210 211 #ifdef UVM_PAGE_TRKOWN 212 if (ITOV(ip)->v_type == VREG) { 213 struct vm_page *pg; 214 struct uvm_object *uobj = &ITOV(ip)->v_uobj; 215 voff_t off = trunc_page(lblktosize(fs, lbprev)); 216 voff_t endoff = round_page(lblktosize(fs, lbprev) + osize); 217 218 simple_lock(&uobj->vmobjlock); 219 while (off < endoff) { 220 pg = uvm_pagelookup(uobj, off); 221 KASSERT(pg != NULL); 222 KASSERT(pg->owner == curproc->p_pid); 223 KASSERT((pg->flags & PG_CLEAN) == 0); 224 off += PAGE_SIZE; 225 } 226 simple_unlock(&uobj->vmobjlock); 227 } 228 #endif 229 230 #ifdef DIAGNOSTIC 231 if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 232 (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 233 printf( 234 "dev = 0x%x, bsize = %d, osize = %d, nsize = %d, fs = %s\n", 235 ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt); 236 panic("ffs_realloccg: bad size"); 237 } 238 if (cred == NOCRED) 239 panic("ffs_realloccg: missing credential\n"); 240 #endif /* DIAGNOSTIC */ 241 if (cred->cr_uid != 0 && freespace(fs, fs->fs_minfree) <= 0) 242 goto nospace; 243 if ((bprev = ufs_rw32(ip->i_ffs_db[lbprev], UFS_FSNEEDSWAP(fs))) == 0) { 244 printf("dev = 0x%x, bsize = %d, bprev = %d, fs = %s\n", 245 ip->i_dev, fs->fs_bsize, bprev, fs->fs_fsmnt); 246 panic("ffs_realloccg: bad bprev"); 247 } 248 /* 249 * Allocate the extra space in the buffer. 250 */ 251 if (bpp != NULL && 252 (error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp)) != 0) { 253 brelse(bp); 254 return (error); 255 } 256 #ifdef QUOTA 257 if ((error = chkdq(ip, (long)btodb(nsize - osize), cred, 0)) != 0) { 258 if (bpp != NULL) { 259 brelse(bp); 260 } 261 return (error); 262 } 263 #endif 264 /* 265 * Check for extension in the existing location. 266 */ 267 cg = dtog(fs, bprev); 268 if ((bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize)) != 0) { 269 ip->i_ffs_blocks += btodb(nsize - osize); 270 ip->i_flag |= IN_CHANGE | IN_UPDATE; 271 272 if (bpp != NULL) { 273 if (bp->b_blkno != fsbtodb(fs, bno)) 274 panic("bad blockno"); 275 allocbuf(bp, nsize); 276 bp->b_flags |= B_DONE; 277 memset(bp->b_data + osize, 0, nsize - osize); 278 *bpp = bp; 279 } 280 if (blknop != NULL) { 281 *blknop = bno; 282 } 283 return (0); 284 } 285 /* 286 * Allocate a new disk location. 287 */ 288 if (bpref >= fs->fs_size) 289 bpref = 0; 290 switch ((int)fs->fs_optim) { 291 case FS_OPTSPACE: 292 /* 293 * Allocate an exact sized fragment. Although this makes 294 * best use of space, we will waste time relocating it if 295 * the file continues to grow. If the fragmentation is 296 * less than half of the minimum free reserve, we choose 297 * to begin optimizing for time. 298 */ 299 request = nsize; 300 if (fs->fs_minfree < 5 || 301 fs->fs_cstotal.cs_nffree > 302 fs->fs_dsize * fs->fs_minfree / (2 * 100)) 303 break; 304 305 if (ffs_log_changeopt) { 306 log(LOG_NOTICE, 307 "%s: optimization changed from SPACE to TIME\n", 308 fs->fs_fsmnt); 309 } 310 311 fs->fs_optim = FS_OPTTIME; 312 break; 313 case FS_OPTTIME: 314 /* 315 * At this point we have discovered a file that is trying to 316 * grow a small fragment to a larger fragment. To save time, 317 * we allocate a full sized block, then free the unused portion. 318 * If the file continues to grow, the `ffs_fragextend' call 319 * above will be able to grow it in place without further 320 * copying. If aberrant programs cause disk fragmentation to 321 * grow within 2% of the free reserve, we choose to begin 322 * optimizing for space. 323 */ 324 request = fs->fs_bsize; 325 if (fs->fs_cstotal.cs_nffree < 326 fs->fs_dsize * (fs->fs_minfree - 2) / 100) 327 break; 328 329 if (ffs_log_changeopt) { 330 log(LOG_NOTICE, 331 "%s: optimization changed from TIME to SPACE\n", 332 fs->fs_fsmnt); 333 } 334 335 fs->fs_optim = FS_OPTSPACE; 336 break; 337 default: 338 printf("dev = 0x%x, optim = %d, fs = %s\n", 339 ip->i_dev, fs->fs_optim, fs->fs_fsmnt); 340 panic("ffs_realloccg: bad optim"); 341 /* NOTREACHED */ 342 } 343 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 344 ffs_alloccg); 345 if (bno > 0) { 346 if (!DOINGSOFTDEP(ITOV(ip))) 347 ffs_blkfree(ip, bprev, (long)osize); 348 if (nsize < request) 349 ffs_blkfree(ip, bno + numfrags(fs, nsize), 350 (long)(request - nsize)); 351 ip->i_ffs_blocks += btodb(nsize - osize); 352 ip->i_flag |= IN_CHANGE | IN_UPDATE; 353 if (bpp != NULL) { 354 bp->b_blkno = fsbtodb(fs, bno); 355 allocbuf(bp, nsize); 356 bp->b_flags |= B_DONE; 357 memset(bp->b_data + osize, 0, (u_int)nsize - osize); 358 *bpp = bp; 359 } 360 if (blknop != NULL) { 361 *blknop = bno; 362 } 363 return (0); 364 } 365 #ifdef QUOTA 366 /* 367 * Restore user's disk quota because allocation failed. 368 */ 369 (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 370 #endif 371 if (bpp != NULL) { 372 brelse(bp); 373 } 374 375 nospace: 376 /* 377 * no space available 378 */ 379 ffs_fserr(fs, cred->cr_uid, "file system full"); 380 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 381 return (ENOSPC); 382 } 383 384 /* 385 * Reallocate a sequence of blocks into a contiguous sequence of blocks. 386 * 387 * The vnode and an array of buffer pointers for a range of sequential 388 * logical blocks to be made contiguous is given. The allocator attempts 389 * to find a range of sequential blocks starting as close as possible to 390 * an fs_rotdelay offset from the end of the allocation for the logical 391 * block immediately preceding the current range. If successful, the 392 * physical block numbers in the buffer pointers and in the inode are 393 * changed to reflect the new allocation. If unsuccessful, the allocation 394 * is left unchanged. The success in doing the reallocation is returned. 395 * Note that the error return is not reflected back to the user. Rather 396 * the previous block allocation will be used. 397 */ 398 #ifdef XXXUBC 399 #ifdef DEBUG 400 #include <sys/sysctl.h> 401 int prtrealloc = 0; 402 struct ctldebug debug15 = { "prtrealloc", &prtrealloc }; 403 #endif 404 #endif 405 406 int doasyncfree = 1; 407 408 int 409 ffs_reallocblks(v) 410 void *v; 411 { 412 #ifdef XXXUBC 413 struct vop_reallocblks_args /* { 414 struct vnode *a_vp; 415 struct cluster_save *a_buflist; 416 } */ *ap = v; 417 struct fs *fs; 418 struct inode *ip; 419 struct vnode *vp; 420 struct buf *sbp, *ebp; 421 ufs_daddr_t *bap, *sbap, *ebap = NULL; 422 struct cluster_save *buflist; 423 ufs_daddr_t start_lbn, end_lbn, soff, newblk, blkno; 424 struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 425 int i, len, start_lvl, end_lvl, pref, ssize; 426 #endif /* XXXUBC */ 427 428 /* XXXUBC don't reallocblks for now */ 429 return ENOSPC; 430 431 #ifdef XXXUBC 432 vp = ap->a_vp; 433 ip = VTOI(vp); 434 fs = ip->i_fs; 435 if (fs->fs_contigsumsize <= 0) 436 return (ENOSPC); 437 buflist = ap->a_buflist; 438 len = buflist->bs_nchildren; 439 start_lbn = buflist->bs_children[0]->b_lblkno; 440 end_lbn = start_lbn + len - 1; 441 #ifdef DIAGNOSTIC 442 for (i = 0; i < len; i++) 443 if (!ffs_checkblk(ip, 444 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 445 panic("ffs_reallocblks: unallocated block 1"); 446 for (i = 1; i < len; i++) 447 if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 448 panic("ffs_reallocblks: non-logical cluster"); 449 blkno = buflist->bs_children[0]->b_blkno; 450 ssize = fsbtodb(fs, fs->fs_frag); 451 for (i = 1; i < len - 1; i++) 452 if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize)) 453 panic("ffs_reallocblks: non-physical cluster %d", i); 454 #endif 455 /* 456 * If the latest allocation is in a new cylinder group, assume that 457 * the filesystem has decided to move and do not force it back to 458 * the previous cylinder group. 459 */ 460 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 461 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 462 return (ENOSPC); 463 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 464 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 465 return (ENOSPC); 466 /* 467 * Get the starting offset and block map for the first block. 468 */ 469 if (start_lvl == 0) { 470 sbap = &ip->i_ffs_db[0]; 471 soff = start_lbn; 472 } else { 473 idp = &start_ap[start_lvl - 1]; 474 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 475 brelse(sbp); 476 return (ENOSPC); 477 } 478 sbap = (ufs_daddr_t *)sbp->b_data; 479 soff = idp->in_off; 480 } 481 /* 482 * Find the preferred location for the cluster. 483 */ 484 pref = ffs_blkpref(ip, start_lbn, soff, sbap); 485 /* 486 * If the block range spans two block maps, get the second map. 487 */ 488 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 489 ssize = len; 490 } else { 491 #ifdef DIAGNOSTIC 492 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 493 panic("ffs_reallocblk: start == end"); 494 #endif 495 ssize = len - (idp->in_off + 1); 496 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 497 goto fail; 498 ebap = (ufs_daddr_t *)ebp->b_data; 499 } 500 /* 501 * Search the block map looking for an allocation of the desired size. 502 */ 503 if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref, 504 len, ffs_clusteralloc)) == 0) 505 goto fail; 506 /* 507 * We have found a new contiguous block. 508 * 509 * First we have to replace the old block pointers with the new 510 * block pointers in the inode and indirect blocks associated 511 * with the file. 512 */ 513 #ifdef DEBUG 514 if (prtrealloc) 515 printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number, 516 start_lbn, end_lbn); 517 #endif 518 blkno = newblk; 519 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 520 ufs_daddr_t ba; 521 522 if (i == ssize) { 523 bap = ebap; 524 soff = -i; 525 } 526 ba = ufs_rw32(*bap, UFS_FSNEEDSWAP(fs)); 527 #ifdef DIAGNOSTIC 528 if (!ffs_checkblk(ip, 529 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 530 panic("ffs_reallocblks: unallocated block 2"); 531 if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != ba) 532 panic("ffs_reallocblks: alloc mismatch"); 533 #endif 534 #ifdef DEBUG 535 if (prtrealloc) 536 printf(" %d,", ba); 537 #endif 538 if (DOINGSOFTDEP(vp)) { 539 if (sbap == &ip->i_ffs_db[0] && i < ssize) 540 softdep_setup_allocdirect(ip, start_lbn + i, 541 blkno, ba, fs->fs_bsize, fs->fs_bsize, 542 buflist->bs_children[i]); 543 else 544 softdep_setup_allocindir_page(ip, start_lbn + i, 545 i < ssize ? sbp : ebp, soff + i, blkno, 546 ba, buflist->bs_children[i]); 547 } 548 *bap++ = ufs_rw32(blkno, UFS_FSNEEDSWAP(fs)); 549 } 550 /* 551 * Next we must write out the modified inode and indirect blocks. 552 * For strict correctness, the writes should be synchronous since 553 * the old block values may have been written to disk. In practise 554 * they are almost never written, but if we are concerned about 555 * strict correctness, the `doasyncfree' flag should be set to zero. 556 * 557 * The test on `doasyncfree' should be changed to test a flag 558 * that shows whether the associated buffers and inodes have 559 * been written. The flag should be set when the cluster is 560 * started and cleared whenever the buffer or inode is flushed. 561 * We can then check below to see if it is set, and do the 562 * synchronous write only when it has been cleared. 563 */ 564 if (sbap != &ip->i_ffs_db[0]) { 565 if (doasyncfree) 566 bdwrite(sbp); 567 else 568 bwrite(sbp); 569 } else { 570 ip->i_flag |= IN_CHANGE | IN_UPDATE; 571 if (!doasyncfree) 572 VOP_UPDATE(vp, NULL, NULL, 1); 573 } 574 if (ssize < len) { 575 if (doasyncfree) 576 bdwrite(ebp); 577 else 578 bwrite(ebp); 579 } 580 /* 581 * Last, free the old blocks and assign the new blocks to the buffers. 582 */ 583 #ifdef DEBUG 584 if (prtrealloc) 585 printf("\n\tnew:"); 586 #endif 587 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 588 if (!DOINGSOFTDEP(vp)) 589 ffs_blkfree(ip, 590 dbtofsb(fs, buflist->bs_children[i]->b_blkno), 591 fs->fs_bsize); 592 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 593 #ifdef DEBUG 594 if (!ffs_checkblk(ip, 595 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 596 panic("ffs_reallocblks: unallocated block 3"); 597 if (prtrealloc) 598 printf(" %d,", blkno); 599 #endif 600 } 601 #ifdef DEBUG 602 if (prtrealloc) { 603 prtrealloc--; 604 printf("\n"); 605 } 606 #endif 607 return (0); 608 609 fail: 610 if (ssize < len) 611 brelse(ebp); 612 if (sbap != &ip->i_ffs_db[0]) 613 brelse(sbp); 614 return (ENOSPC); 615 #endif /* XXXUBC */ 616 } 617 618 /* 619 * Allocate an inode in the file system. 620 * 621 * If allocating a directory, use ffs_dirpref to select the inode. 622 * If allocating in a directory, the following hierarchy is followed: 623 * 1) allocate the preferred inode. 624 * 2) allocate an inode in the same cylinder group. 625 * 3) quadradically rehash into other cylinder groups, until an 626 * available inode is located. 627 * If no inode preference is given the following hierarchy is used 628 * to allocate an inode: 629 * 1) allocate an inode in cylinder group 0. 630 * 2) quadradically rehash into other cylinder groups, until an 631 * available inode is located. 632 */ 633 int 634 ffs_valloc(v) 635 void *v; 636 { 637 struct vop_valloc_args /* { 638 struct vnode *a_pvp; 639 int a_mode; 640 struct ucred *a_cred; 641 struct vnode **a_vpp; 642 } */ *ap = v; 643 struct vnode *pvp = ap->a_pvp; 644 struct inode *pip; 645 struct fs *fs; 646 struct inode *ip; 647 mode_t mode = ap->a_mode; 648 ino_t ino, ipref; 649 int cg, error; 650 651 *ap->a_vpp = NULL; 652 pip = VTOI(pvp); 653 fs = pip->i_fs; 654 if (fs->fs_cstotal.cs_nifree == 0) 655 goto noinodes; 656 657 if ((mode & IFMT) == IFDIR) 658 ipref = ffs_dirpref(pip); 659 else 660 ipref = pip->i_number; 661 if (ipref >= fs->fs_ncg * fs->fs_ipg) 662 ipref = 0; 663 cg = ino_to_cg(fs, ipref); 664 /* 665 * Track number of dirs created one after another 666 * in a same cg without intervening by files. 667 */ 668 if ((mode & IFMT) == IFDIR) { 669 if (fs->fs_contigdirs[cg] < 65535) 670 fs->fs_contigdirs[cg]++; 671 } else { 672 if (fs->fs_contigdirs[cg] > 0) 673 fs->fs_contigdirs[cg]--; 674 } 675 ino = (ino_t)ffs_hashalloc(pip, cg, (long)ipref, mode, ffs_nodealloccg); 676 if (ino == 0) 677 goto noinodes; 678 error = VFS_VGET(pvp->v_mount, ino, ap->a_vpp); 679 if (error) { 680 VOP_VFREE(pvp, ino, mode); 681 return (error); 682 } 683 ip = VTOI(*ap->a_vpp); 684 if (ip->i_ffs_mode) { 685 printf("mode = 0%o, inum = %d, fs = %s\n", 686 ip->i_ffs_mode, ip->i_number, fs->fs_fsmnt); 687 panic("ffs_valloc: dup alloc"); 688 } 689 if (ip->i_ffs_blocks) { /* XXX */ 690 printf("free inode %s/%d had %d blocks\n", 691 fs->fs_fsmnt, ino, ip->i_ffs_blocks); 692 ip->i_ffs_blocks = 0; 693 } 694 ip->i_ffs_flags = 0; 695 /* 696 * Set up a new generation number for this inode. 697 */ 698 ip->i_ffs_gen++; 699 return (0); 700 noinodes: 701 ffs_fserr(fs, ap->a_cred->cr_uid, "out of inodes"); 702 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 703 return (ENOSPC); 704 } 705 706 /* 707 * Find a cylinder group in which to place a directory. 708 * 709 * The policy implemented by this algorithm is to allocate a 710 * directory inode in the same cylinder group as its parent 711 * directory, but also to reserve space for its files inodes 712 * and data. Restrict the number of directories which may be 713 * allocated one after another in the same cylinder group 714 * without intervening allocation of files. 715 * 716 * If we allocate a first level directory then force allocation 717 * in another cylinder group. 718 */ 719 static ino_t 720 ffs_dirpref(pip) 721 struct inode *pip; 722 { 723 register struct fs *fs; 724 int cg, prefcg, dirsize, cgsize; 725 int avgifree, avgbfree, avgndir, curdirsize; 726 int minifree, minbfree, maxndir; 727 int mincg, minndir; 728 int maxcontigdirs; 729 730 fs = pip->i_fs; 731 732 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 733 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 734 avgndir = fs->fs_cstotal.cs_ndir / fs->fs_ncg; 735 736 /* 737 * Force allocation in another cg if creating a first level dir. 738 */ 739 if (ITOV(pip)->v_flag & VROOT) { 740 prefcg = random() % fs->fs_ncg; 741 mincg = prefcg; 742 minndir = fs->fs_ipg; 743 for (cg = prefcg; cg < fs->fs_ncg; cg++) 744 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 745 fs->fs_cs(fs, cg).cs_nifree >= avgifree && 746 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 747 mincg = cg; 748 minndir = fs->fs_cs(fs, cg).cs_ndir; 749 } 750 for (cg = 0; cg < prefcg; cg++) 751 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 752 fs->fs_cs(fs, cg).cs_nifree >= avgifree && 753 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 754 mincg = cg; 755 minndir = fs->fs_cs(fs, cg).cs_ndir; 756 } 757 return ((ino_t)(fs->fs_ipg * mincg)); 758 } 759 760 /* 761 * Count various limits which used for 762 * optimal allocation of a directory inode. 763 */ 764 maxndir = min(avgndir + fs->fs_ipg / 16, fs->fs_ipg); 765 minifree = avgifree - fs->fs_ipg / 4; 766 if (minifree < 0) 767 minifree = 0; 768 minbfree = avgbfree - fragstoblks(fs, fs->fs_fpg) / 4; 769 if (minbfree < 0) 770 minbfree = 0; 771 cgsize = fs->fs_fsize * fs->fs_fpg; 772 dirsize = fs->fs_avgfilesize * fs->fs_avgfpdir; 773 curdirsize = avgndir ? (cgsize - avgbfree * fs->fs_bsize) / avgndir : 0; 774 if (dirsize < curdirsize) 775 dirsize = curdirsize; 776 maxcontigdirs = min(cgsize / dirsize, 255); 777 if (fs->fs_avgfpdir > 0) 778 maxcontigdirs = min(maxcontigdirs, 779 fs->fs_ipg / fs->fs_avgfpdir); 780 if (maxcontigdirs == 0) 781 maxcontigdirs = 1; 782 783 /* 784 * Limit number of dirs in one cg and reserve space for 785 * regular files, but only if we have no deficit in 786 * inodes or space. 787 */ 788 prefcg = ino_to_cg(fs, pip->i_number); 789 for (cg = prefcg; cg < fs->fs_ncg; cg++) 790 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 791 fs->fs_cs(fs, cg).cs_nifree >= minifree && 792 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 793 if (fs->fs_contigdirs[cg] < maxcontigdirs) 794 return ((ino_t)(fs->fs_ipg * cg)); 795 } 796 for (cg = 0; cg < prefcg; cg++) 797 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 798 fs->fs_cs(fs, cg).cs_nifree >= minifree && 799 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 800 if (fs->fs_contigdirs[cg] < maxcontigdirs) 801 return ((ino_t)(fs->fs_ipg * cg)); 802 } 803 /* 804 * This is a backstop when we are deficient in space. 805 */ 806 for (cg = prefcg; cg < fs->fs_ncg; cg++) 807 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 808 return ((ino_t)(fs->fs_ipg * cg)); 809 for (cg = 0; cg < prefcg; cg++) 810 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 811 break; 812 return ((ino_t)(fs->fs_ipg * cg)); 813 } 814 815 /* 816 * Select the desired position for the next block in a file. The file is 817 * logically divided into sections. The first section is composed of the 818 * direct blocks. Each additional section contains fs_maxbpg blocks. 819 * 820 * If no blocks have been allocated in the first section, the policy is to 821 * request a block in the same cylinder group as the inode that describes 822 * the file. If no blocks have been allocated in any other section, the 823 * policy is to place the section in a cylinder group with a greater than 824 * average number of free blocks. An appropriate cylinder group is found 825 * by using a rotor that sweeps the cylinder groups. When a new group of 826 * blocks is needed, the sweep begins in the cylinder group following the 827 * cylinder group from which the previous allocation was made. The sweep 828 * continues until a cylinder group with greater than the average number 829 * of free blocks is found. If the allocation is for the first block in an 830 * indirect block, the information on the previous allocation is unavailable; 831 * here a best guess is made based upon the logical block number being 832 * allocated. 833 * 834 * If a section is already partially allocated, the policy is to 835 * contiguously allocate fs_maxcontig blocks. The end of one of these 836 * contiguous blocks and the beginning of the next is physically separated 837 * so that the disk head will be in transit between them for at least 838 * fs_rotdelay milliseconds. This is to allow time for the processor to 839 * schedule another I/O transfer. 840 */ 841 ufs_daddr_t 842 ffs_blkpref(ip, lbn, indx, bap) 843 struct inode *ip; 844 ufs_daddr_t lbn; 845 int indx; 846 ufs_daddr_t *bap; 847 { 848 struct fs *fs; 849 int cg; 850 int avgbfree, startcg; 851 ufs_daddr_t nextblk; 852 853 fs = ip->i_fs; 854 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 855 if (lbn < NDADDR + NINDIR(fs)) { 856 cg = ino_to_cg(fs, ip->i_number); 857 return (fs->fs_fpg * cg + fs->fs_frag); 858 } 859 /* 860 * Find a cylinder with greater than average number of 861 * unused data blocks. 862 */ 863 if (indx == 0 || bap[indx - 1] == 0) 864 startcg = 865 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 866 else 867 startcg = dtog(fs, 868 ufs_rw32(bap[indx - 1], UFS_FSNEEDSWAP(fs)) + 1); 869 startcg %= fs->fs_ncg; 870 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 871 for (cg = startcg; cg < fs->fs_ncg; cg++) 872 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 873 return (fs->fs_fpg * cg + fs->fs_frag); 874 } 875 for (cg = 0; cg < startcg; cg++) 876 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 877 return (fs->fs_fpg * cg + fs->fs_frag); 878 } 879 return (0); 880 } 881 /* 882 * One or more previous blocks have been laid out. If less 883 * than fs_maxcontig previous blocks are contiguous, the 884 * next block is requested contiguously, otherwise it is 885 * requested rotationally delayed by fs_rotdelay milliseconds. 886 */ 887 nextblk = ufs_rw32(bap[indx - 1], UFS_FSNEEDSWAP(fs)) + fs->fs_frag; 888 if (indx < fs->fs_maxcontig || 889 ufs_rw32(bap[indx - fs->fs_maxcontig], UFS_FSNEEDSWAP(fs)) + 890 blkstofrags(fs, fs->fs_maxcontig) != nextblk) 891 return (nextblk); 892 if (fs->fs_rotdelay != 0) 893 /* 894 * Here we convert ms of delay to frags as: 895 * (frags) = (ms) * (rev/sec) * (sect/rev) / 896 * ((sect/frag) * (ms/sec)) 897 * then round up to the next block. 898 */ 899 nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 900 (NSPF(fs) * 1000), fs->fs_frag); 901 return (nextblk); 902 } 903 904 /* 905 * Implement the cylinder overflow algorithm. 906 * 907 * The policy implemented by this algorithm is: 908 * 1) allocate the block in its requested cylinder group. 909 * 2) quadradically rehash on the cylinder group number. 910 * 3) brute force search for a free block. 911 */ 912 /*VARARGS5*/ 913 static u_long 914 ffs_hashalloc(ip, cg, pref, size, allocator) 915 struct inode *ip; 916 int cg; 917 long pref; 918 int size; /* size for data blocks, mode for inodes */ 919 ufs_daddr_t (*allocator) __P((struct inode *, int, ufs_daddr_t, int)); 920 { 921 struct fs *fs; 922 long result; 923 int i, icg = cg; 924 925 fs = ip->i_fs; 926 /* 927 * 1: preferred cylinder group 928 */ 929 result = (*allocator)(ip, cg, pref, size); 930 if (result) 931 return (result); 932 /* 933 * 2: quadratic rehash 934 */ 935 for (i = 1; i < fs->fs_ncg; i *= 2) { 936 cg += i; 937 if (cg >= fs->fs_ncg) 938 cg -= fs->fs_ncg; 939 result = (*allocator)(ip, cg, 0, size); 940 if (result) 941 return (result); 942 } 943 /* 944 * 3: brute force search 945 * Note that we start at i == 2, since 0 was checked initially, 946 * and 1 is always checked in the quadratic rehash. 947 */ 948 cg = (icg + 2) % fs->fs_ncg; 949 for (i = 2; i < fs->fs_ncg; i++) { 950 result = (*allocator)(ip, cg, 0, size); 951 if (result) 952 return (result); 953 cg++; 954 if (cg == fs->fs_ncg) 955 cg = 0; 956 } 957 return (0); 958 } 959 960 /* 961 * Determine whether a fragment can be extended. 962 * 963 * Check to see if the necessary fragments are available, and 964 * if they are, allocate them. 965 */ 966 static ufs_daddr_t 967 ffs_fragextend(ip, cg, bprev, osize, nsize) 968 struct inode *ip; 969 int cg; 970 long bprev; 971 int osize, nsize; 972 { 973 struct fs *fs; 974 struct cg *cgp; 975 struct buf *bp; 976 long bno; 977 int frags, bbase; 978 int i, error; 979 980 fs = ip->i_fs; 981 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 982 return (0); 983 frags = numfrags(fs, nsize); 984 bbase = fragnum(fs, bprev); 985 if (bbase > fragnum(fs, (bprev + frags - 1))) { 986 /* cannot extend across a block boundary */ 987 return (0); 988 } 989 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 990 (int)fs->fs_cgsize, NOCRED, &bp); 991 if (error) { 992 brelse(bp); 993 return (0); 994 } 995 cgp = (struct cg *)bp->b_data; 996 if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs))) { 997 brelse(bp); 998 return (0); 999 } 1000 cgp->cg_time = ufs_rw32(time.tv_sec, UFS_FSNEEDSWAP(fs)); 1001 bno = dtogd(fs, bprev); 1002 for (i = numfrags(fs, osize); i < frags; i++) 1003 if (isclr(cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)), bno + i)) { 1004 brelse(bp); 1005 return (0); 1006 } 1007 /* 1008 * the current fragment can be extended 1009 * deduct the count on fragment being extended into 1010 * increase the count on the remaining fragment (if any) 1011 * allocate the extended piece 1012 */ 1013 for (i = frags; i < fs->fs_frag - bbase; i++) 1014 if (isclr(cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)), bno + i)) 1015 break; 1016 ufs_add32(cgp->cg_frsum[i - numfrags(fs, osize)], -1, UFS_FSNEEDSWAP(fs)); 1017 if (i != frags) 1018 ufs_add32(cgp->cg_frsum[i - frags], 1, UFS_FSNEEDSWAP(fs)); 1019 for (i = numfrags(fs, osize); i < frags; i++) { 1020 clrbit(cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)), bno + i); 1021 ufs_add32(cgp->cg_cs.cs_nffree, -1, UFS_FSNEEDSWAP(fs)); 1022 fs->fs_cstotal.cs_nffree--; 1023 fs->fs_cs(fs, cg).cs_nffree--; 1024 } 1025 fs->fs_fmod = 1; 1026 if (DOINGSOFTDEP(ITOV(ip))) 1027 softdep_setup_blkmapdep(bp, fs, bprev); 1028 bdwrite(bp); 1029 return (bprev); 1030 } 1031 1032 /* 1033 * Determine whether a block can be allocated. 1034 * 1035 * Check to see if a block of the appropriate size is available, 1036 * and if it is, allocate it. 1037 */ 1038 static ufs_daddr_t 1039 ffs_alloccg(ip, cg, bpref, size) 1040 struct inode *ip; 1041 int cg; 1042 ufs_daddr_t bpref; 1043 int size; 1044 { 1045 struct cg *cgp; 1046 struct buf *bp; 1047 ufs_daddr_t bno, blkno; 1048 int error, frags, allocsiz, i; 1049 struct fs *fs = ip->i_fs; 1050 #ifdef FFS_EI 1051 const int needswap = UFS_FSNEEDSWAP(fs); 1052 #endif 1053 1054 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 1055 return (0); 1056 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1057 (int)fs->fs_cgsize, NOCRED, &bp); 1058 if (error) { 1059 brelse(bp); 1060 return (0); 1061 } 1062 cgp = (struct cg *)bp->b_data; 1063 if (!cg_chkmagic(cgp, needswap) || 1064 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 1065 brelse(bp); 1066 return (0); 1067 } 1068 cgp->cg_time = ufs_rw32(time.tv_sec, needswap); 1069 if (size == fs->fs_bsize) { 1070 bno = ffs_alloccgblk(ip, bp, bpref); 1071 bdwrite(bp); 1072 return (bno); 1073 } 1074 /* 1075 * check to see if any fragments are already available 1076 * allocsiz is the size which will be allocated, hacking 1077 * it down to a smaller size if necessary 1078 */ 1079 frags = numfrags(fs, size); 1080 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 1081 if (cgp->cg_frsum[allocsiz] != 0) 1082 break; 1083 if (allocsiz == fs->fs_frag) { 1084 /* 1085 * no fragments were available, so a block will be 1086 * allocated, and hacked up 1087 */ 1088 if (cgp->cg_cs.cs_nbfree == 0) { 1089 brelse(bp); 1090 return (0); 1091 } 1092 bno = ffs_alloccgblk(ip, bp, bpref); 1093 bpref = dtogd(fs, bno); 1094 for (i = frags; i < fs->fs_frag; i++) 1095 setbit(cg_blksfree(cgp, needswap), bpref + i); 1096 i = fs->fs_frag - frags; 1097 ufs_add32(cgp->cg_cs.cs_nffree, i, needswap); 1098 fs->fs_cstotal.cs_nffree += i; 1099 fs->fs_cs(fs, cg).cs_nffree += i; 1100 fs->fs_fmod = 1; 1101 ufs_add32(cgp->cg_frsum[i], 1, needswap); 1102 bdwrite(bp); 1103 return (bno); 1104 } 1105 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 1106 #if 0 1107 /* 1108 * XXX fvdl mapsearch will panic, and never return -1 1109 * also: returning NULL as ufs_daddr_t ? 1110 */ 1111 if (bno < 0) { 1112 brelse(bp); 1113 return (0); 1114 } 1115 #endif 1116 for (i = 0; i < frags; i++) 1117 clrbit(cg_blksfree(cgp, needswap), bno + i); 1118 ufs_add32(cgp->cg_cs.cs_nffree, -frags, needswap); 1119 fs->fs_cstotal.cs_nffree -= frags; 1120 fs->fs_cs(fs, cg).cs_nffree -= frags; 1121 fs->fs_fmod = 1; 1122 ufs_add32(cgp->cg_frsum[allocsiz], -1, needswap); 1123 if (frags != allocsiz) 1124 ufs_add32(cgp->cg_frsum[allocsiz - frags], 1, needswap); 1125 blkno = cg * fs->fs_fpg + bno; 1126 if (DOINGSOFTDEP(ITOV(ip))) 1127 softdep_setup_blkmapdep(bp, fs, blkno); 1128 bdwrite(bp); 1129 return blkno; 1130 } 1131 1132 /* 1133 * Allocate a block in a cylinder group. 1134 * 1135 * This algorithm implements the following policy: 1136 * 1) allocate the requested block. 1137 * 2) allocate a rotationally optimal block in the same cylinder. 1138 * 3) allocate the next available block on the block rotor for the 1139 * specified cylinder group. 1140 * Note that this routine only allocates fs_bsize blocks; these 1141 * blocks may be fragmented by the routine that allocates them. 1142 */ 1143 static ufs_daddr_t 1144 ffs_alloccgblk(ip, bp, bpref) 1145 struct inode *ip; 1146 struct buf *bp; 1147 ufs_daddr_t bpref; 1148 { 1149 struct cg *cgp; 1150 ufs_daddr_t bno, blkno; 1151 int cylno, pos, delta; 1152 short *cylbp; 1153 int i; 1154 struct fs *fs = ip->i_fs; 1155 #ifdef FFS_EI 1156 const int needswap = UFS_FSNEEDSWAP(fs); 1157 #endif 1158 1159 cgp = (struct cg *)bp->b_data; 1160 if (bpref == 0 || dtog(fs, bpref) != ufs_rw32(cgp->cg_cgx, needswap)) { 1161 bpref = ufs_rw32(cgp->cg_rotor, needswap); 1162 goto norot; 1163 } 1164 bpref = blknum(fs, bpref); 1165 bpref = dtogd(fs, bpref); 1166 /* 1167 * if the requested block is available, use it 1168 */ 1169 if (ffs_isblock(fs, cg_blksfree(cgp, needswap), 1170 fragstoblks(fs, bpref))) { 1171 bno = bpref; 1172 goto gotit; 1173 } 1174 if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) { 1175 /* 1176 * Block layout information is not available. 1177 * Leaving bpref unchanged means we take the 1178 * next available free block following the one 1179 * we just allocated. Hopefully this will at 1180 * least hit a track cache on drives of unknown 1181 * geometry (e.g. SCSI). 1182 */ 1183 goto norot; 1184 } 1185 /* 1186 * check for a block available on the same cylinder 1187 */ 1188 cylno = cbtocylno(fs, bpref); 1189 if (cg_blktot(cgp, needswap)[cylno] == 0) 1190 goto norot; 1191 /* 1192 * check the summary information to see if a block is 1193 * available in the requested cylinder starting at the 1194 * requested rotational position and proceeding around. 1195 */ 1196 cylbp = cg_blks(fs, cgp, cylno, needswap); 1197 pos = cbtorpos(fs, bpref); 1198 for (i = pos; i < fs->fs_nrpos; i++) 1199 if (ufs_rw16(cylbp[i], needswap) > 0) 1200 break; 1201 if (i == fs->fs_nrpos) 1202 for (i = 0; i < pos; i++) 1203 if (ufs_rw16(cylbp[i], needswap) > 0) 1204 break; 1205 if (ufs_rw16(cylbp[i], needswap) > 0) { 1206 /* 1207 * found a rotational position, now find the actual 1208 * block. A panic if none is actually there. 1209 */ 1210 pos = cylno % fs->fs_cpc; 1211 bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 1212 if (fs_postbl(fs, pos)[i] == -1) { 1213 printf("pos = %d, i = %d, fs = %s\n", 1214 pos, i, fs->fs_fsmnt); 1215 panic("ffs_alloccgblk: cyl groups corrupted"); 1216 } 1217 for (i = fs_postbl(fs, pos)[i];; ) { 1218 if (ffs_isblock(fs, cg_blksfree(cgp, needswap), bno + i)) { 1219 bno = blkstofrags(fs, (bno + i)); 1220 goto gotit; 1221 } 1222 delta = fs_rotbl(fs)[i]; 1223 if (delta <= 0 || 1224 delta + i > fragstoblks(fs, fs->fs_fpg)) 1225 break; 1226 i += delta; 1227 } 1228 printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 1229 panic("ffs_alloccgblk: can't find blk in cyl"); 1230 } 1231 norot: 1232 /* 1233 * no blocks in the requested cylinder, so take next 1234 * available one in this cylinder group. 1235 */ 1236 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 1237 if (bno < 0) 1238 return (0); 1239 cgp->cg_rotor = ufs_rw32(bno, needswap); 1240 gotit: 1241 blkno = fragstoblks(fs, bno); 1242 ffs_clrblock(fs, cg_blksfree(cgp, needswap), (long)blkno); 1243 ffs_clusteracct(fs, cgp, blkno, -1); 1244 ufs_add32(cgp->cg_cs.cs_nbfree, -1, needswap); 1245 fs->fs_cstotal.cs_nbfree--; 1246 fs->fs_cs(fs, ufs_rw32(cgp->cg_cgx, needswap)).cs_nbfree--; 1247 cylno = cbtocylno(fs, bno); 1248 ufs_add16(cg_blks(fs, cgp, cylno, needswap)[cbtorpos(fs, bno)], -1, 1249 needswap); 1250 ufs_add32(cg_blktot(cgp, needswap)[cylno], -1, needswap); 1251 fs->fs_fmod = 1; 1252 blkno = ufs_rw32(cgp->cg_cgx, needswap) * fs->fs_fpg + bno; 1253 if (DOINGSOFTDEP(ITOV(ip))) 1254 softdep_setup_blkmapdep(bp, fs, blkno); 1255 return (blkno); 1256 } 1257 1258 #ifdef XXXUBC 1259 /* 1260 * Determine whether a cluster can be allocated. 1261 * 1262 * We do not currently check for optimal rotational layout if there 1263 * are multiple choices in the same cylinder group. Instead we just 1264 * take the first one that we find following bpref. 1265 */ 1266 static ufs_daddr_t 1267 ffs_clusteralloc(ip, cg, bpref, len) 1268 struct inode *ip; 1269 int cg; 1270 ufs_daddr_t bpref; 1271 int len; 1272 { 1273 struct fs *fs; 1274 struct cg *cgp; 1275 struct buf *bp; 1276 int i, got, run, bno, bit, map; 1277 u_char *mapp; 1278 int32_t *lp; 1279 1280 fs = ip->i_fs; 1281 if (fs->fs_maxcluster[cg] < len) 1282 return (0); 1283 if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 1284 NOCRED, &bp)) 1285 goto fail; 1286 cgp = (struct cg *)bp->b_data; 1287 if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs))) 1288 goto fail; 1289 /* 1290 * Check to see if a cluster of the needed size (or bigger) is 1291 * available in this cylinder group. 1292 */ 1293 lp = &cg_clustersum(cgp, UFS_FSNEEDSWAP(fs))[len]; 1294 for (i = len; i <= fs->fs_contigsumsize; i++) 1295 if (ufs_rw32(*lp++, UFS_FSNEEDSWAP(fs)) > 0) 1296 break; 1297 if (i > fs->fs_contigsumsize) { 1298 /* 1299 * This is the first time looking for a cluster in this 1300 * cylinder group. Update the cluster summary information 1301 * to reflect the true maximum sized cluster so that 1302 * future cluster allocation requests can avoid reading 1303 * the cylinder group map only to find no clusters. 1304 */ 1305 lp = &cg_clustersum(cgp, UFS_FSNEEDSWAP(fs))[len - 1]; 1306 for (i = len - 1; i > 0; i--) 1307 if (ufs_rw32(*lp--, UFS_FSNEEDSWAP(fs)) > 0) 1308 break; 1309 fs->fs_maxcluster[cg] = i; 1310 goto fail; 1311 } 1312 /* 1313 * Search the cluster map to find a big enough cluster. 1314 * We take the first one that we find, even if it is larger 1315 * than we need as we prefer to get one close to the previous 1316 * block allocation. We do not search before the current 1317 * preference point as we do not want to allocate a block 1318 * that is allocated before the previous one (as we will 1319 * then have to wait for another pass of the elevator 1320 * algorithm before it will be read). We prefer to fail and 1321 * be recalled to try an allocation in the next cylinder group. 1322 */ 1323 if (dtog(fs, bpref) != cg) 1324 bpref = 0; 1325 else 1326 bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 1327 mapp = &cg_clustersfree(cgp, UFS_FSNEEDSWAP(fs))[bpref / NBBY]; 1328 map = *mapp++; 1329 bit = 1 << (bpref % NBBY); 1330 for (run = 0, got = bpref; 1331 got < ufs_rw32(cgp->cg_nclusterblks, UFS_FSNEEDSWAP(fs)); got++) { 1332 if ((map & bit) == 0) { 1333 run = 0; 1334 } else { 1335 run++; 1336 if (run == len) 1337 break; 1338 } 1339 if ((got & (NBBY - 1)) != (NBBY - 1)) { 1340 bit <<= 1; 1341 } else { 1342 map = *mapp++; 1343 bit = 1; 1344 } 1345 } 1346 if (got == ufs_rw32(cgp->cg_nclusterblks, UFS_FSNEEDSWAP(fs))) 1347 goto fail; 1348 /* 1349 * Allocate the cluster that we have found. 1350 */ 1351 #ifdef DIAGNOSTIC 1352 for (i = 1; i <= len; i++) 1353 if (!ffs_isblock(fs, cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)), 1354 got - run + i)) 1355 panic("ffs_clusteralloc: map mismatch"); 1356 #endif 1357 bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1); 1358 if (dtog(fs, bno) != cg) 1359 panic("ffs_clusteralloc: allocated out of group"); 1360 len = blkstofrags(fs, len); 1361 for (i = 0; i < len; i += fs->fs_frag) 1362 if ((got = ffs_alloccgblk(ip, bp, bno + i)) != bno + i) 1363 panic("ffs_clusteralloc: lost block"); 1364 bdwrite(bp); 1365 return (bno); 1366 1367 fail: 1368 brelse(bp); 1369 return (0); 1370 } 1371 #endif /* XXXUBC */ 1372 1373 /* 1374 * Determine whether an inode can be allocated. 1375 * 1376 * Check to see if an inode is available, and if it is, 1377 * allocate it using the following policy: 1378 * 1) allocate the requested inode. 1379 * 2) allocate the next available inode after the requested 1380 * inode in the specified cylinder group. 1381 */ 1382 static ufs_daddr_t 1383 ffs_nodealloccg(ip, cg, ipref, mode) 1384 struct inode *ip; 1385 int cg; 1386 ufs_daddr_t ipref; 1387 int mode; 1388 { 1389 struct cg *cgp; 1390 struct buf *bp; 1391 int error, start, len, loc, map, i; 1392 struct fs *fs = ip->i_fs; 1393 #ifdef FFS_EI 1394 const int needswap = UFS_FSNEEDSWAP(fs); 1395 #endif 1396 1397 if (fs->fs_cs(fs, cg).cs_nifree == 0) 1398 return (0); 1399 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1400 (int)fs->fs_cgsize, NOCRED, &bp); 1401 if (error) { 1402 brelse(bp); 1403 return (0); 1404 } 1405 cgp = (struct cg *)bp->b_data; 1406 if (!cg_chkmagic(cgp, needswap) || cgp->cg_cs.cs_nifree == 0) { 1407 brelse(bp); 1408 return (0); 1409 } 1410 cgp->cg_time = ufs_rw32(time.tv_sec, needswap); 1411 if (ipref) { 1412 ipref %= fs->fs_ipg; 1413 if (isclr(cg_inosused(cgp, needswap), ipref)) 1414 goto gotit; 1415 } 1416 start = ufs_rw32(cgp->cg_irotor, needswap) / NBBY; 1417 len = howmany(fs->fs_ipg - ufs_rw32(cgp->cg_irotor, needswap), 1418 NBBY); 1419 loc = skpc(0xff, len, &cg_inosused(cgp, needswap)[start]); 1420 if (loc == 0) { 1421 len = start + 1; 1422 start = 0; 1423 loc = skpc(0xff, len, &cg_inosused(cgp, needswap)[0]); 1424 if (loc == 0) { 1425 printf("cg = %d, irotor = %d, fs = %s\n", 1426 cg, ufs_rw32(cgp->cg_irotor, needswap), 1427 fs->fs_fsmnt); 1428 panic("ffs_nodealloccg: map corrupted"); 1429 /* NOTREACHED */ 1430 } 1431 } 1432 i = start + len - loc; 1433 map = cg_inosused(cgp, needswap)[i]; 1434 ipref = i * NBBY; 1435 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 1436 if ((map & i) == 0) { 1437 cgp->cg_irotor = ufs_rw32(ipref, needswap); 1438 goto gotit; 1439 } 1440 } 1441 printf("fs = %s\n", fs->fs_fsmnt); 1442 panic("ffs_nodealloccg: block not in map"); 1443 /* NOTREACHED */ 1444 gotit: 1445 if (DOINGSOFTDEP(ITOV(ip))) 1446 softdep_setup_inomapdep(bp, ip, cg * fs->fs_ipg + ipref); 1447 setbit(cg_inosused(cgp, needswap), ipref); 1448 ufs_add32(cgp->cg_cs.cs_nifree, -1, needswap); 1449 fs->fs_cstotal.cs_nifree--; 1450 fs->fs_cs(fs, cg).cs_nifree--; 1451 fs->fs_fmod = 1; 1452 if ((mode & IFMT) == IFDIR) { 1453 ufs_add32(cgp->cg_cs.cs_ndir, 1, needswap); 1454 fs->fs_cstotal.cs_ndir++; 1455 fs->fs_cs(fs, cg).cs_ndir++; 1456 } 1457 bdwrite(bp); 1458 return (cg * fs->fs_ipg + ipref); 1459 } 1460 1461 /* 1462 * Free a block or fragment. 1463 * 1464 * The specified block or fragment is placed back in the 1465 * free map. If a fragment is deallocated, a possible 1466 * block reassembly is checked. 1467 */ 1468 void 1469 ffs_blkfree(ip, bno, size) 1470 struct inode *ip; 1471 ufs_daddr_t bno; 1472 long size; 1473 { 1474 struct cg *cgp; 1475 struct buf *bp; 1476 ufs_daddr_t blkno; 1477 int i, error, cg, blk, frags, bbase; 1478 struct fs *fs = ip->i_fs; 1479 const int needswap = UFS_FSNEEDSWAP(fs); 1480 1481 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0 || 1482 fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) { 1483 printf("dev = 0x%x, bno = %u bsize = %d, size = %ld, fs = %s\n", 1484 ip->i_dev, bno, fs->fs_bsize, size, fs->fs_fsmnt); 1485 panic("blkfree: bad size"); 1486 } 1487 cg = dtog(fs, bno); 1488 if ((u_int)bno >= fs->fs_size) { 1489 printf("bad block %d, ino %d\n", bno, ip->i_number); 1490 ffs_fserr(fs, ip->i_ffs_uid, "bad block"); 1491 return; 1492 } 1493 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1494 (int)fs->fs_cgsize, NOCRED, &bp); 1495 if (error) { 1496 brelse(bp); 1497 return; 1498 } 1499 cgp = (struct cg *)bp->b_data; 1500 if (!cg_chkmagic(cgp, needswap)) { 1501 brelse(bp); 1502 return; 1503 } 1504 cgp->cg_time = ufs_rw32(time.tv_sec, needswap); 1505 bno = dtogd(fs, bno); 1506 if (size == fs->fs_bsize) { 1507 blkno = fragstoblks(fs, bno); 1508 if (!ffs_isfreeblock(fs, cg_blksfree(cgp, needswap), blkno)) { 1509 printf("dev = 0x%x, block = %d, fs = %s\n", 1510 ip->i_dev, bno, fs->fs_fsmnt); 1511 panic("blkfree: freeing free block"); 1512 } 1513 ffs_setblock(fs, cg_blksfree(cgp, needswap), blkno); 1514 ffs_clusteracct(fs, cgp, blkno, 1); 1515 ufs_add32(cgp->cg_cs.cs_nbfree, 1, needswap); 1516 fs->fs_cstotal.cs_nbfree++; 1517 fs->fs_cs(fs, cg).cs_nbfree++; 1518 i = cbtocylno(fs, bno); 1519 ufs_add16(cg_blks(fs, cgp, i, needswap)[cbtorpos(fs, bno)], 1, 1520 needswap); 1521 ufs_add32(cg_blktot(cgp, needswap)[i], 1, needswap); 1522 } else { 1523 bbase = bno - fragnum(fs, bno); 1524 /* 1525 * decrement the counts associated with the old frags 1526 */ 1527 blk = blkmap(fs, cg_blksfree(cgp, needswap), bbase); 1528 ffs_fragacct(fs, blk, cgp->cg_frsum, -1, needswap); 1529 /* 1530 * deallocate the fragment 1531 */ 1532 frags = numfrags(fs, size); 1533 for (i = 0; i < frags; i++) { 1534 if (isset(cg_blksfree(cgp, needswap), bno + i)) { 1535 printf("dev = 0x%x, block = %d, fs = %s\n", 1536 ip->i_dev, bno + i, fs->fs_fsmnt); 1537 panic("blkfree: freeing free frag"); 1538 } 1539 setbit(cg_blksfree(cgp, needswap), bno + i); 1540 } 1541 ufs_add32(cgp->cg_cs.cs_nffree, i, needswap); 1542 fs->fs_cstotal.cs_nffree += i; 1543 fs->fs_cs(fs, cg).cs_nffree += i; 1544 /* 1545 * add back in counts associated with the new frags 1546 */ 1547 blk = blkmap(fs, cg_blksfree(cgp, needswap), bbase); 1548 ffs_fragacct(fs, blk, cgp->cg_frsum, 1, needswap); 1549 /* 1550 * if a complete block has been reassembled, account for it 1551 */ 1552 blkno = fragstoblks(fs, bbase); 1553 if (ffs_isblock(fs, cg_blksfree(cgp, needswap), blkno)) { 1554 ufs_add32(cgp->cg_cs.cs_nffree, -fs->fs_frag, needswap); 1555 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 1556 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 1557 ffs_clusteracct(fs, cgp, blkno, 1); 1558 ufs_add32(cgp->cg_cs.cs_nbfree, 1, needswap); 1559 fs->fs_cstotal.cs_nbfree++; 1560 fs->fs_cs(fs, cg).cs_nbfree++; 1561 i = cbtocylno(fs, bbase); 1562 ufs_add16(cg_blks(fs, cgp, i, needswap)[cbtorpos(fs, 1563 bbase)], 1, 1564 needswap); 1565 ufs_add32(cg_blktot(cgp, needswap)[i], 1, needswap); 1566 } 1567 } 1568 fs->fs_fmod = 1; 1569 bdwrite(bp); 1570 } 1571 1572 #if defined(DIAGNOSTIC) || defined(DEBUG) 1573 #ifdef XXXUBC 1574 /* 1575 * Verify allocation of a block or fragment. Returns true if block or 1576 * fragment is allocated, false if it is free. 1577 */ 1578 static int 1579 ffs_checkblk(ip, bno, size) 1580 struct inode *ip; 1581 ufs_daddr_t bno; 1582 long size; 1583 { 1584 struct fs *fs; 1585 struct cg *cgp; 1586 struct buf *bp; 1587 int i, error, frags, free; 1588 1589 fs = ip->i_fs; 1590 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1591 printf("bsize = %d, size = %ld, fs = %s\n", 1592 fs->fs_bsize, size, fs->fs_fsmnt); 1593 panic("checkblk: bad size"); 1594 } 1595 if ((u_int)bno >= fs->fs_size) 1596 panic("checkblk: bad block %d", bno); 1597 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))), 1598 (int)fs->fs_cgsize, NOCRED, &bp); 1599 if (error) { 1600 brelse(bp); 1601 return 0; 1602 } 1603 cgp = (struct cg *)bp->b_data; 1604 if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs))) { 1605 brelse(bp); 1606 return 0; 1607 } 1608 bno = dtogd(fs, bno); 1609 if (size == fs->fs_bsize) { 1610 free = ffs_isblock(fs, cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)), 1611 fragstoblks(fs, bno)); 1612 } else { 1613 frags = numfrags(fs, size); 1614 for (free = 0, i = 0; i < frags; i++) 1615 if (isset(cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)), bno + i)) 1616 free++; 1617 if (free != 0 && free != frags) 1618 panic("checkblk: partially free fragment"); 1619 } 1620 brelse(bp); 1621 return (!free); 1622 } 1623 #endif /* XXXUBC */ 1624 #endif /* DIAGNOSTIC */ 1625 1626 /* 1627 * Free an inode. 1628 */ 1629 int 1630 ffs_vfree(v) 1631 void *v; 1632 { 1633 struct vop_vfree_args /* { 1634 struct vnode *a_pvp; 1635 ino_t a_ino; 1636 int a_mode; 1637 } */ *ap = v; 1638 1639 if (DOINGSOFTDEP(ap->a_pvp)) { 1640 softdep_freefile(ap); 1641 return (0); 1642 } 1643 return (ffs_freefile(ap)); 1644 } 1645 1646 /* 1647 * Do the actual free operation. 1648 * The specified inode is placed back in the free map. 1649 */ 1650 int 1651 ffs_freefile(v) 1652 void *v; 1653 { 1654 struct vop_vfree_args /* { 1655 struct vnode *a_pvp; 1656 ino_t a_ino; 1657 int a_mode; 1658 } */ *ap = v; 1659 struct cg *cgp; 1660 struct inode *pip = VTOI(ap->a_pvp); 1661 struct fs *fs = pip->i_fs; 1662 ino_t ino = ap->a_ino; 1663 struct buf *bp; 1664 int error, cg; 1665 #ifdef FFS_EI 1666 const int needswap = UFS_FSNEEDSWAP(fs); 1667 #endif 1668 1669 if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 1670 panic("ifree: range: dev = 0x%x, ino = %d, fs = %s\n", 1671 pip->i_dev, ino, fs->fs_fsmnt); 1672 cg = ino_to_cg(fs, ino); 1673 error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1674 (int)fs->fs_cgsize, NOCRED, &bp); 1675 if (error) { 1676 brelse(bp); 1677 return (error); 1678 } 1679 cgp = (struct cg *)bp->b_data; 1680 if (!cg_chkmagic(cgp, needswap)) { 1681 brelse(bp); 1682 return (0); 1683 } 1684 cgp->cg_time = ufs_rw32(time.tv_sec, needswap); 1685 ino %= fs->fs_ipg; 1686 if (isclr(cg_inosused(cgp, needswap), ino)) { 1687 printf("dev = 0x%x, ino = %d, fs = %s\n", 1688 pip->i_dev, ino, fs->fs_fsmnt); 1689 if (fs->fs_ronly == 0) 1690 panic("ifree: freeing free inode"); 1691 } 1692 clrbit(cg_inosused(cgp, needswap), ino); 1693 if (ino < ufs_rw32(cgp->cg_irotor, needswap)) 1694 cgp->cg_irotor = ufs_rw32(ino, needswap); 1695 ufs_add32(cgp->cg_cs.cs_nifree, 1, needswap); 1696 fs->fs_cstotal.cs_nifree++; 1697 fs->fs_cs(fs, cg).cs_nifree++; 1698 if ((ap->a_mode & IFMT) == IFDIR) { 1699 ufs_add32(cgp->cg_cs.cs_ndir, -1, needswap); 1700 fs->fs_cstotal.cs_ndir--; 1701 fs->fs_cs(fs, cg).cs_ndir--; 1702 } 1703 fs->fs_fmod = 1; 1704 bdwrite(bp); 1705 return (0); 1706 } 1707 1708 /* 1709 * Find a block of the specified size in the specified cylinder group. 1710 * 1711 * It is a panic if a request is made to find a block if none are 1712 * available. 1713 */ 1714 static ufs_daddr_t 1715 ffs_mapsearch(fs, cgp, bpref, allocsiz) 1716 struct fs *fs; 1717 struct cg *cgp; 1718 ufs_daddr_t bpref; 1719 int allocsiz; 1720 { 1721 ufs_daddr_t bno; 1722 int start, len, loc, i; 1723 int blk, field, subfield, pos; 1724 int ostart, olen; 1725 #ifdef FFS_EI 1726 const int needswap = UFS_FSNEEDSWAP(fs); 1727 #endif 1728 1729 /* 1730 * find the fragment by searching through the free block 1731 * map for an appropriate bit pattern 1732 */ 1733 if (bpref) 1734 start = dtogd(fs, bpref) / NBBY; 1735 else 1736 start = ufs_rw32(cgp->cg_frotor, needswap) / NBBY; 1737 len = howmany(fs->fs_fpg, NBBY) - start; 1738 ostart = start; 1739 olen = len; 1740 loc = scanc((u_int)len, 1741 (const u_char *)&cg_blksfree(cgp, needswap)[start], 1742 (const u_char *)fragtbl[fs->fs_frag], 1743 (1 << (allocsiz - 1 + (fs->fs_frag & (NBBY - 1))))); 1744 if (loc == 0) { 1745 len = start + 1; 1746 start = 0; 1747 loc = scanc((u_int)len, 1748 (const u_char *)&cg_blksfree(cgp, needswap)[0], 1749 (const u_char *)fragtbl[fs->fs_frag], 1750 (1 << (allocsiz - 1 + (fs->fs_frag & (NBBY - 1))))); 1751 if (loc == 0) { 1752 printf("start = %d, len = %d, fs = %s\n", 1753 ostart, olen, fs->fs_fsmnt); 1754 printf("offset=%d %ld\n", 1755 ufs_rw32(cgp->cg_freeoff, needswap), 1756 (long)cg_blksfree(cgp, needswap) - (long)cgp); 1757 panic("ffs_alloccg: map corrupted"); 1758 /* NOTREACHED */ 1759 } 1760 } 1761 bno = (start + len - loc) * NBBY; 1762 cgp->cg_frotor = ufs_rw32(bno, needswap); 1763 /* 1764 * found the byte in the map 1765 * sift through the bits to find the selected frag 1766 */ 1767 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 1768 blk = blkmap(fs, cg_blksfree(cgp, needswap), bno); 1769 blk <<= 1; 1770 field = around[allocsiz]; 1771 subfield = inside[allocsiz]; 1772 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 1773 if ((blk & field) == subfield) 1774 return (bno + pos); 1775 field <<= 1; 1776 subfield <<= 1; 1777 } 1778 } 1779 printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt); 1780 panic("ffs_alloccg: block not in map"); 1781 return (-1); 1782 } 1783 1784 /* 1785 * Update the cluster map because of an allocation or free. 1786 * 1787 * Cnt == 1 means free; cnt == -1 means allocating. 1788 */ 1789 void 1790 ffs_clusteracct(fs, cgp, blkno, cnt) 1791 struct fs *fs; 1792 struct cg *cgp; 1793 ufs_daddr_t blkno; 1794 int cnt; 1795 { 1796 int32_t *sump; 1797 int32_t *lp; 1798 u_char *freemapp, *mapp; 1799 int i, start, end, forw, back, map, bit; 1800 #ifdef FFS_EI 1801 const int needswap = UFS_FSNEEDSWAP(fs); 1802 #endif 1803 1804 if (fs->fs_contigsumsize <= 0) 1805 return; 1806 freemapp = cg_clustersfree(cgp, needswap); 1807 sump = cg_clustersum(cgp, needswap); 1808 /* 1809 * Allocate or clear the actual block. 1810 */ 1811 if (cnt > 0) 1812 setbit(freemapp, blkno); 1813 else 1814 clrbit(freemapp, blkno); 1815 /* 1816 * Find the size of the cluster going forward. 1817 */ 1818 start = blkno + 1; 1819 end = start + fs->fs_contigsumsize; 1820 if (end >= ufs_rw32(cgp->cg_nclusterblks, needswap)) 1821 end = ufs_rw32(cgp->cg_nclusterblks, needswap); 1822 mapp = &freemapp[start / NBBY]; 1823 map = *mapp++; 1824 bit = 1 << (start % NBBY); 1825 for (i = start; i < end; i++) { 1826 if ((map & bit) == 0) 1827 break; 1828 if ((i & (NBBY - 1)) != (NBBY - 1)) { 1829 bit <<= 1; 1830 } else { 1831 map = *mapp++; 1832 bit = 1; 1833 } 1834 } 1835 forw = i - start; 1836 /* 1837 * Find the size of the cluster going backward. 1838 */ 1839 start = blkno - 1; 1840 end = start - fs->fs_contigsumsize; 1841 if (end < 0) 1842 end = -1; 1843 mapp = &freemapp[start / NBBY]; 1844 map = *mapp--; 1845 bit = 1 << (start % NBBY); 1846 for (i = start; i > end; i--) { 1847 if ((map & bit) == 0) 1848 break; 1849 if ((i & (NBBY - 1)) != 0) { 1850 bit >>= 1; 1851 } else { 1852 map = *mapp--; 1853 bit = 1 << (NBBY - 1); 1854 } 1855 } 1856 back = start - i; 1857 /* 1858 * Account for old cluster and the possibly new forward and 1859 * back clusters. 1860 */ 1861 i = back + forw + 1; 1862 if (i > fs->fs_contigsumsize) 1863 i = fs->fs_contigsumsize; 1864 ufs_add32(sump[i], cnt, needswap); 1865 if (back > 0) 1866 ufs_add32(sump[back], -cnt, needswap); 1867 if (forw > 0) 1868 ufs_add32(sump[forw], -cnt, needswap); 1869 1870 /* 1871 * Update cluster summary information. 1872 */ 1873 lp = &sump[fs->fs_contigsumsize]; 1874 for (i = fs->fs_contigsumsize; i > 0; i--) 1875 if (ufs_rw32(*lp--, needswap) > 0) 1876 break; 1877 fs->fs_maxcluster[ufs_rw32(cgp->cg_cgx, needswap)] = i; 1878 } 1879 1880 /* 1881 * Fserr prints the name of a file system with an error diagnostic. 1882 * 1883 * The form of the error message is: 1884 * fs: error message 1885 */ 1886 static void 1887 ffs_fserr(fs, uid, cp) 1888 struct fs *fs; 1889 u_int uid; 1890 char *cp; 1891 { 1892 1893 log(LOG_ERR, "uid %d comm %s on %s: %s\n", 1894 uid, curproc->p_comm, fs->fs_fsmnt, cp); 1895 } 1896