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