ffs_alloc.c revision 88138
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: head/sys/ufs/ffs/ffs_alloc.c 88138 2001-12-18 18:05:17Z mckusick $ 35 */ 36 37#include "opt_quota.h" 38 39#include <sys/param.h> 40#include <sys/systm.h> 41#include <sys/bio.h> 42#include <sys/buf.h> 43#include <sys/conf.h> 44#include <sys/file.h> 45#include <sys/proc.h> 46#include <sys/vnode.h> 47#include <sys/mount.h> 48#include <sys/kernel.h> 49#include <sys/sysctl.h> 50#include <sys/syslog.h> 51 52#include <ufs/ufs/extattr.h> 53#include <ufs/ufs/quota.h> 54#include <ufs/ufs/inode.h> 55#include <ufs/ufs/ufs_extern.h> 56#include <ufs/ufs/ufsmount.h> 57 58#include <ufs/ffs/fs.h> 59#include <ufs/ffs/ffs_extern.h> 60 61typedef ufs_daddr_t allocfcn_t __P((struct inode *ip, int cg, ufs_daddr_t bpref, 62 int size)); 63 64static ufs_daddr_t ffs_alloccg __P((struct inode *, int, ufs_daddr_t, int)); 65static ufs_daddr_t 66 ffs_alloccgblk __P((struct inode *, struct buf *, ufs_daddr_t)); 67#ifdef DIAGNOSTIC 68static int ffs_checkblk __P((struct inode *, ufs_daddr_t, long)); 69#endif 70static ufs_daddr_t ffs_clusteralloc __P((struct inode *, int, ufs_daddr_t, 71 int)); 72static ino_t ffs_dirpref __P((struct inode *)); 73static ufs_daddr_t ffs_fragextend __P((struct inode *, int, long, int, int)); 74static void ffs_fserr __P((struct fs *, u_int, char *)); 75static u_long ffs_hashalloc 76 __P((struct inode *, int, long, int, allocfcn_t *)); 77static ino_t ffs_nodealloccg __P((struct inode *, int, ufs_daddr_t, int)); 78static ufs_daddr_t ffs_mapsearch __P((struct fs *, struct cg *, ufs_daddr_t, 79 int)); 80 81/* 82 * Allocate a block in the file system. 83 * 84 * The size of the requested block is given, which must be some 85 * multiple of fs_fsize and <= fs_bsize. 86 * A preference may be optionally specified. If a preference is given 87 * the following hierarchy is used to allocate a block: 88 * 1) allocate the requested block. 89 * 2) allocate a rotationally optimal block in the same cylinder. 90 * 3) allocate a block in the same cylinder group. 91 * 4) quadradically rehash into other cylinder groups, until an 92 * available block is located. 93 * If no block preference is given the following heirarchy is used 94 * to allocate a block: 95 * 1) allocate a block in the cylinder group that contains the 96 * inode for the file. 97 * 2) quadradically rehash into other cylinder groups, until an 98 * available block is located. 99 */ 100int 101ffs_alloc(ip, lbn, bpref, size, cred, bnp) 102 register struct inode *ip; 103 ufs_daddr_t lbn, bpref; 104 int size; 105 struct ucred *cred; 106 ufs_daddr_t *bnp; 107{ 108 register struct fs *fs; 109 ufs_daddr_t bno; 110 int cg; 111#ifdef QUOTA 112 int error; 113#endif 114 115 *bnp = 0; 116 fs = ip->i_fs; 117#ifdef DIAGNOSTIC 118 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 119 printf("dev = %s, bsize = %ld, size = %d, fs = %s\n", 120 devtoname(ip->i_dev), (long)fs->fs_bsize, size, 121 fs->fs_fsmnt); 122 panic("ffs_alloc: bad size"); 123 } 124 if (cred == NOCRED) 125 panic("ffs_alloc: missing credential"); 126#endif /* DIAGNOSTIC */ 127 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 128 goto nospace; 129 if (suser_xxx(cred, NULL, PRISON_ROOT) && 130 freespace(fs, fs->fs_minfree) - numfrags(fs, size) < 0) 131 goto nospace; 132#ifdef QUOTA 133 error = chkdq(ip, (long)btodb(size), cred, 0); 134 if (error) 135 return (error); 136#endif 137 if (bpref >= fs->fs_size) 138 bpref = 0; 139 if (bpref == 0) 140 cg = ino_to_cg(fs, ip->i_number); 141 else 142 cg = dtog(fs, bpref); 143 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, size, 144 ffs_alloccg); 145 if (bno > 0) { 146 ip->i_blocks += btodb(size); 147 ip->i_flag |= IN_CHANGE | IN_UPDATE; 148 *bnp = bno; 149 return (0); 150 } 151#ifdef QUOTA 152 /* 153 * Restore user's disk quota because allocation failed. 154 */ 155 (void) chkdq(ip, (long)-btodb(size), cred, FORCE); 156#endif 157nospace: 158 ffs_fserr(fs, cred->cr_uid, "file system full"); 159 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 160 return (ENOSPC); 161} 162 163/* 164 * Reallocate a fragment to a bigger size 165 * 166 * The number and size of the old block is given, and a preference 167 * and new size is also specified. The allocator attempts to extend 168 * the original block. Failing that, the regular block allocator is 169 * invoked to get an appropriate block. 170 */ 171int 172ffs_realloccg(ip, lbprev, bpref, osize, nsize, cred, bpp) 173 register struct inode *ip; 174 ufs_daddr_t lbprev; 175 ufs_daddr_t bpref; 176 int osize, nsize; 177 struct ucred *cred; 178 struct buf **bpp; 179{ 180 register struct fs *fs; 181 struct buf *bp; 182 int cg, request, error; 183 ufs_daddr_t bprev, bno; 184 185 *bpp = 0; 186 fs = ip->i_fs; 187#ifdef DIAGNOSTIC 188 if (ITOV(ip)->v_mount->mnt_kern_flag & MNTK_SUSPENDED) 189 panic("ffs_realloccg: allocation on suspended filesystem"); 190 if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 191 (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 192 printf( 193 "dev = %s, bsize = %ld, osize = %d, nsize = %d, fs = %s\n", 194 devtoname(ip->i_dev), (long)fs->fs_bsize, osize, 195 nsize, fs->fs_fsmnt); 196 panic("ffs_realloccg: bad size"); 197 } 198 if (cred == NOCRED) 199 panic("ffs_realloccg: missing credential"); 200#endif /* DIAGNOSTIC */ 201 if (suser_xxx(cred, NULL, PRISON_ROOT) && 202 freespace(fs, fs->fs_minfree) - numfrags(fs, nsize - osize) < 0) 203 goto nospace; 204 if ((bprev = ip->i_db[lbprev]) == 0) { 205 printf("dev = %s, bsize = %ld, bprev = %ld, fs = %s\n", 206 devtoname(ip->i_dev), (long)fs->fs_bsize, (long)bprev, 207 fs->fs_fsmnt); 208 panic("ffs_realloccg: bad bprev"); 209 } 210 /* 211 * Allocate the extra space in the buffer. 212 */ 213 error = bread(ITOV(ip), lbprev, osize, NOCRED, &bp); 214 if (error) { 215 brelse(bp); 216 return (error); 217 } 218 219 if( bp->b_blkno == bp->b_lblkno) { 220 if( lbprev >= NDADDR) 221 panic("ffs_realloccg: lbprev out of range"); 222 bp->b_blkno = fsbtodb(fs, bprev); 223 } 224 225#ifdef QUOTA 226 error = chkdq(ip, (long)btodb(nsize - osize), cred, 0); 227 if (error) { 228 brelse(bp); 229 return (error); 230 } 231#endif 232 /* 233 * Check for extension in the existing location. 234 */ 235 cg = dtog(fs, bprev); 236 bno = ffs_fragextend(ip, cg, (long)bprev, osize, nsize); 237 if (bno) { 238 if (bp->b_blkno != fsbtodb(fs, bno)) 239 panic("ffs_realloccg: bad blockno"); 240 ip->i_blocks += btodb(nsize - osize); 241 ip->i_flag |= IN_CHANGE | IN_UPDATE; 242 allocbuf(bp, nsize); 243 bp->b_flags |= B_DONE; 244 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 245 *bpp = bp; 246 return (0); 247 } 248 /* 249 * Allocate a new disk location. 250 */ 251 if (bpref >= fs->fs_size) 252 bpref = 0; 253 switch ((int)fs->fs_optim) { 254 case FS_OPTSPACE: 255 /* 256 * Allocate an exact sized fragment. Although this makes 257 * best use of space, we will waste time relocating it if 258 * the file continues to grow. If the fragmentation is 259 * less than half of the minimum free reserve, we choose 260 * to begin optimizing for time. 261 */ 262 request = nsize; 263 if (fs->fs_minfree <= 5 || 264 fs->fs_cstotal.cs_nffree > 265 (off_t)fs->fs_dsize * fs->fs_minfree / (2 * 100)) 266 break; 267 log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 268 fs->fs_fsmnt); 269 fs->fs_optim = FS_OPTTIME; 270 break; 271 case FS_OPTTIME: 272 /* 273 * At this point we have discovered a file that is trying to 274 * grow a small fragment to a larger fragment. To save time, 275 * we allocate a full sized block, then free the unused portion. 276 * If the file continues to grow, the `ffs_fragextend' call 277 * above will be able to grow it in place without further 278 * copying. If aberrant programs cause disk fragmentation to 279 * grow within 2% of the free reserve, we choose to begin 280 * optimizing for space. 281 */ 282 request = fs->fs_bsize; 283 if (fs->fs_cstotal.cs_nffree < 284 (off_t)fs->fs_dsize * (fs->fs_minfree - 2) / 100) 285 break; 286 log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 287 fs->fs_fsmnt); 288 fs->fs_optim = FS_OPTSPACE; 289 break; 290 default: 291 printf("dev = %s, optim = %ld, fs = %s\n", 292 devtoname(ip->i_dev), (long)fs->fs_optim, fs->fs_fsmnt); 293 panic("ffs_realloccg: bad optim"); 294 /* NOTREACHED */ 295 } 296 bno = (ufs_daddr_t)ffs_hashalloc(ip, cg, (long)bpref, request, 297 ffs_alloccg); 298 if (bno > 0) { 299 bp->b_blkno = fsbtodb(fs, bno); 300 if (!DOINGSOFTDEP(ITOV(ip))) 301 ffs_blkfree(ip, bprev, (long)osize); 302 if (nsize < request) 303 ffs_blkfree(ip, bno + numfrags(fs, nsize), 304 (long)(request - nsize)); 305 ip->i_blocks += btodb(nsize - osize); 306 ip->i_flag |= IN_CHANGE | IN_UPDATE; 307 allocbuf(bp, nsize); 308 bp->b_flags |= B_DONE; 309 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 310 *bpp = bp; 311 return (0); 312 } 313#ifdef QUOTA 314 /* 315 * Restore user's disk quota because allocation failed. 316 */ 317 (void) chkdq(ip, (long)-btodb(nsize - osize), cred, FORCE); 318#endif 319 brelse(bp); 320nospace: 321 /* 322 * no space available 323 */ 324 ffs_fserr(fs, cred->cr_uid, "file system full"); 325 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 326 return (ENOSPC); 327} 328 329/* 330 * Reallocate a sequence of blocks into a contiguous sequence of blocks. 331 * 332 * The vnode and an array of buffer pointers for a range of sequential 333 * logical blocks to be made contiguous is given. The allocator attempts 334 * to find a range of sequential blocks starting as close as possible to 335 * an fs_rotdelay offset from the end of the allocation for the logical 336 * block immediately preceding the current range. If successful, the 337 * physical block numbers in the buffer pointers and in the inode are 338 * changed to reflect the new allocation. If unsuccessful, the allocation 339 * is left unchanged. The success in doing the reallocation is returned. 340 * Note that the error return is not reflected back to the user. Rather 341 * the previous block allocation will be used. 342 */ 343 344SYSCTL_NODE(_vfs, OID_AUTO, ffs, CTLFLAG_RW, 0, "FFS filesystem"); 345 346static int doasyncfree = 1; 347SYSCTL_INT(_vfs_ffs, OID_AUTO, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, ""); 348 349static int doreallocblks = 1; 350SYSCTL_INT(_vfs_ffs, OID_AUTO, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, ""); 351 352#ifdef DEBUG 353static volatile int prtrealloc = 0; 354#endif 355 356int 357ffs_reallocblks(ap) 358 struct vop_reallocblks_args /* { 359 struct vnode *a_vp; 360 struct cluster_save *a_buflist; 361 } */ *ap; 362{ 363 struct fs *fs; 364 struct inode *ip; 365 struct vnode *vp; 366 struct buf *sbp, *ebp; 367 ufs_daddr_t *bap, *sbap, *ebap = 0; 368 struct cluster_save *buflist; 369 ufs_daddr_t start_lbn, end_lbn, soff, newblk, blkno; 370 struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 371 int i, len, start_lvl, end_lvl, pref, ssize; 372 373 if (doreallocblks == 0) 374 return (ENOSPC); 375 vp = ap->a_vp; 376 ip = VTOI(vp); 377 fs = ip->i_fs; 378 if (fs->fs_contigsumsize <= 0) 379 return (ENOSPC); 380 buflist = ap->a_buflist; 381 len = buflist->bs_nchildren; 382 start_lbn = buflist->bs_children[0]->b_lblkno; 383 end_lbn = start_lbn + len - 1; 384#ifdef DIAGNOSTIC 385 for (i = 0; i < len; i++) 386 if (!ffs_checkblk(ip, 387 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 388 panic("ffs_reallocblks: unallocated block 1"); 389 for (i = 1; i < len; i++) 390 if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 391 panic("ffs_reallocblks: non-logical cluster"); 392 blkno = buflist->bs_children[0]->b_blkno; 393 ssize = fsbtodb(fs, fs->fs_frag); 394 for (i = 1; i < len - 1; i++) 395 if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize)) 396 panic("ffs_reallocblks: non-physical cluster %d", i); 397#endif 398 /* 399 * If the latest allocation is in a new cylinder group, assume that 400 * the filesystem has decided to move and do not force it back to 401 * the previous cylinder group. 402 */ 403 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 404 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 405 return (ENOSPC); 406 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 407 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 408 return (ENOSPC); 409 /* 410 * Get the starting offset and block map for the first block. 411 */ 412 if (start_lvl == 0) { 413 sbap = &ip->i_db[0]; 414 soff = start_lbn; 415 } else { 416 idp = &start_ap[start_lvl - 1]; 417 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 418 brelse(sbp); 419 return (ENOSPC); 420 } 421 sbap = (ufs_daddr_t *)sbp->b_data; 422 soff = idp->in_off; 423 } 424 /* 425 * Find the preferred location for the cluster. 426 */ 427 pref = ffs_blkpref(ip, start_lbn, soff, sbap); 428 /* 429 * If the block range spans two block maps, get the second map. 430 */ 431 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 432 ssize = len; 433 } else { 434#ifdef DIAGNOSTIC 435 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 436 panic("ffs_reallocblk: start == end"); 437#endif 438 ssize = len - (idp->in_off + 1); 439 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 440 goto fail; 441 ebap = (ufs_daddr_t *)ebp->b_data; 442 } 443 /* 444 * Search the block map looking for an allocation of the desired size. 445 */ 446 if ((newblk = (ufs_daddr_t)ffs_hashalloc(ip, dtog(fs, pref), (long)pref, 447 len, ffs_clusteralloc)) == 0) 448 goto fail; 449 /* 450 * We have found a new contiguous block. 451 * 452 * First we have to replace the old block pointers with the new 453 * block pointers in the inode and indirect blocks associated 454 * with the file. 455 */ 456#ifdef DEBUG 457 if (prtrealloc) 458 printf("realloc: ino %d, lbns %d-%d\n\told:", ip->i_number, 459 start_lbn, end_lbn); 460#endif 461 blkno = newblk; 462 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 463 if (i == ssize) { 464 bap = ebap; 465 soff = -i; 466 } 467#ifdef DIAGNOSTIC 468 if (!ffs_checkblk(ip, 469 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 470 panic("ffs_reallocblks: unallocated block 2"); 471 if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap) 472 panic("ffs_reallocblks: alloc mismatch"); 473#endif 474#ifdef DEBUG 475 if (prtrealloc) 476 printf(" %d,", *bap); 477#endif 478 if (DOINGSOFTDEP(vp)) { 479 if (sbap == &ip->i_db[0] && i < ssize) 480 softdep_setup_allocdirect(ip, start_lbn + i, 481 blkno, *bap, fs->fs_bsize, fs->fs_bsize, 482 buflist->bs_children[i]); 483 else 484 softdep_setup_allocindir_page(ip, start_lbn + i, 485 i < ssize ? sbp : ebp, soff + i, blkno, 486 *bap, buflist->bs_children[i]); 487 } 488 *bap++ = blkno; 489 } 490 /* 491 * Next we must write out the modified inode and indirect blocks. 492 * For strict correctness, the writes should be synchronous since 493 * the old block values may have been written to disk. In practise 494 * they are almost never written, but if we are concerned about 495 * strict correctness, the `doasyncfree' flag should be set to zero. 496 * 497 * The test on `doasyncfree' should be changed to test a flag 498 * that shows whether the associated buffers and inodes have 499 * been written. The flag should be set when the cluster is 500 * started and cleared whenever the buffer or inode is flushed. 501 * We can then check below to see if it is set, and do the 502 * synchronous write only when it has been cleared. 503 */ 504 if (sbap != &ip->i_db[0]) { 505 if (doasyncfree) 506 bdwrite(sbp); 507 else 508 bwrite(sbp); 509 } else { 510 ip->i_flag |= IN_CHANGE | IN_UPDATE; 511 if (!doasyncfree) 512 UFS_UPDATE(vp, 1); 513 } 514 if (ssize < len) { 515 if (doasyncfree) 516 bdwrite(ebp); 517 else 518 bwrite(ebp); 519 } 520 /* 521 * Last, free the old blocks and assign the new blocks to the buffers. 522 */ 523#ifdef DEBUG 524 if (prtrealloc) 525 printf("\n\tnew:"); 526#endif 527 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 528 if (!DOINGSOFTDEP(vp)) 529 ffs_blkfree(ip, 530 dbtofsb(fs, buflist->bs_children[i]->b_blkno), 531 fs->fs_bsize); 532 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 533#ifdef DIAGNOSTIC 534 if (!ffs_checkblk(ip, 535 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 536 panic("ffs_reallocblks: unallocated block 3"); 537#endif 538#ifdef DEBUG 539 if (prtrealloc) 540 printf(" %d,", blkno); 541#endif 542 } 543#ifdef DEBUG 544 if (prtrealloc) { 545 prtrealloc--; 546 printf("\n"); 547 } 548#endif 549 return (0); 550 551fail: 552 if (ssize < len) 553 brelse(ebp); 554 if (sbap != &ip->i_db[0]) 555 brelse(sbp); 556 return (ENOSPC); 557} 558 559/* 560 * Allocate an inode in the file system. 561 * 562 * If allocating a directory, use ffs_dirpref to select the inode. 563 * If allocating in a directory, the following hierarchy is followed: 564 * 1) allocate the preferred inode. 565 * 2) allocate an inode in the same cylinder group. 566 * 3) quadradically rehash into other cylinder groups, until an 567 * available inode is located. 568 * If no inode preference is given the following heirarchy is used 569 * to allocate an inode: 570 * 1) allocate an inode in cylinder group 0. 571 * 2) quadradically rehash into other cylinder groups, until an 572 * available inode is located. 573 */ 574int 575ffs_valloc(pvp, mode, cred, vpp) 576 struct vnode *pvp; 577 int mode; 578 struct ucred *cred; 579 struct vnode **vpp; 580{ 581 register struct inode *pip; 582 register struct fs *fs; 583 register 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 && (fs->fs_flags & FS_UNCLEAN) == 0) { /* 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); 638noinodes: 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 */ 657static ino_t 658ffs_dirpref(pip) 659 struct inode *pip; 660{ 661 register struct fs *fs; 662 int cg, prefcg, dirsize, cgsize; 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 - fs->fs_ipg / 4; 704 if (minifree < 0) 705 minifree = 0; 706 minbfree = avgbfree - fs->fs_fpg / fs->fs_frag / 4; 707 if (minbfree < 0) 708 minbfree = 0; 709 cgsize = fs->fs_fsize * fs->fs_fpg; 710 dirsize = fs->fs_avgfilesize * fs->fs_avgfpdir; 711 curdirsize = avgndir ? (cgsize - avgbfree * fs->fs_bsize) / avgndir : 0; 712 if (dirsize < curdirsize) 713 dirsize = curdirsize; 714 maxcontigdirs = min(cgsize / dirsize, 255); 715 if (fs->fs_avgfpdir > 0) 716 maxcontigdirs = min(maxcontigdirs, 717 fs->fs_ipg / fs->fs_avgfpdir); 718 if (maxcontigdirs == 0) 719 maxcontigdirs = 1; 720 721 /* 722 * Limit number of dirs in one cg and reserve space for 723 * regular files, but only if we have no deficit in 724 * inodes or space. 725 */ 726 prefcg = ino_to_cg(fs, pip->i_number); 727 for (cg = prefcg; cg < fs->fs_ncg; cg++) 728 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 729 fs->fs_cs(fs, cg).cs_nifree >= minifree && 730 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 731 if (fs->fs_contigdirs[cg] < maxcontigdirs) 732 return ((ino_t)(fs->fs_ipg * cg)); 733 } 734 for (cg = 0; cg < prefcg; cg++) 735 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 736 fs->fs_cs(fs, cg).cs_nifree >= minifree && 737 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 738 if (fs->fs_contigdirs[cg] < maxcontigdirs) 739 return ((ino_t)(fs->fs_ipg * cg)); 740 } 741 /* 742 * This is a backstop when we have deficit in space. 743 */ 744 for (cg = prefcg; cg < fs->fs_ncg; cg++) 745 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 746 return ((ino_t)(fs->fs_ipg * cg)); 747 for (cg = 0; cg < prefcg; cg++) 748 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 749 break; 750 return ((ino_t)(fs->fs_ipg * cg)); 751} 752 753/* 754 * Select the desired position for the next block in a file. The file is 755 * logically divided into sections. The first section is composed of the 756 * direct blocks. Each additional section contains fs_maxbpg blocks. 757 * 758 * If no blocks have been allocated in the first section, the policy is to 759 * request a block in the same cylinder group as the inode that describes 760 * the file. If no blocks have been allocated in any other section, the 761 * policy is to place the section in a cylinder group with a greater than 762 * average number of free blocks. An appropriate cylinder group is found 763 * by using a rotor that sweeps the cylinder groups. When a new group of 764 * blocks is needed, the sweep begins in the cylinder group following the 765 * cylinder group from which the previous allocation was made. The sweep 766 * continues until a cylinder group with greater than the average number 767 * of free blocks is found. If the allocation is for the first block in an 768 * indirect block, the information on the previous allocation is unavailable; 769 * here a best guess is made based upon the logical block number being 770 * allocated. 771 * 772 * If a section is already partially allocated, the policy is to 773 * contiguously allocate fs_maxcontig blocks. The end of one of these 774 * contiguous blocks and the beginning of the next is physically separated 775 * so that the disk head will be in transit between them for at least 776 * fs_rotdelay milliseconds. This is to allow time for the processor to 777 * schedule another I/O transfer. 778 */ 779ufs_daddr_t 780ffs_blkpref(ip, lbn, indx, bap) 781 struct inode *ip; 782 ufs_daddr_t lbn; 783 int indx; 784 ufs_daddr_t *bap; 785{ 786 register struct fs *fs; 787 register int cg; 788 int avgbfree, startcg; 789 ufs_daddr_t nextblk; 790 791 fs = ip->i_fs; 792 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 793 if (lbn < NDADDR + NINDIR(fs)) { 794 cg = ino_to_cg(fs, ip->i_number); 795 return (fs->fs_fpg * cg + fs->fs_frag); 796 } 797 /* 798 * Find a cylinder with greater than average number of 799 * unused data blocks. 800 */ 801 if (indx == 0 || bap[indx - 1] == 0) 802 startcg = 803 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 804 else 805 startcg = dtog(fs, bap[indx - 1]) + 1; 806 startcg %= fs->fs_ncg; 807 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 808 for (cg = startcg; cg < fs->fs_ncg; cg++) 809 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 810 fs->fs_cgrotor = cg; 811 return (fs->fs_fpg * cg + fs->fs_frag); 812 } 813 for (cg = 0; cg <= startcg; cg++) 814 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 815 fs->fs_cgrotor = cg; 816 return (fs->fs_fpg * cg + fs->fs_frag); 817 } 818 return (0); 819 } 820 /* 821 * One or more previous blocks have been laid out. If less 822 * than fs_maxcontig previous blocks are contiguous, the 823 * next block is requested contiguously, otherwise it is 824 * requested rotationally delayed by fs_rotdelay milliseconds. 825 */ 826 nextblk = bap[indx - 1] + fs->fs_frag; 827 if (fs->fs_rotdelay == 0 || indx < fs->fs_maxcontig || 828 bap[indx - fs->fs_maxcontig] + 829 blkstofrags(fs, fs->fs_maxcontig) != nextblk) 830 return (nextblk); 831 /* 832 * Here we convert ms of delay to frags as: 833 * (frags) = (ms) * (rev/sec) * (sect/rev) / 834 * ((sect/frag) * (ms/sec)) 835 * then round up to the next block. 836 */ 837 nextblk += roundup(fs->fs_rotdelay * fs->fs_rps * fs->fs_nsect / 838 (NSPF(fs) * 1000), fs->fs_frag); 839 return (nextblk); 840} 841 842/* 843 * Implement the cylinder overflow algorithm. 844 * 845 * The policy implemented by this algorithm is: 846 * 1) allocate the block in its requested cylinder group. 847 * 2) quadradically rehash on the cylinder group number. 848 * 3) brute force search for a free block. 849 */ 850/*VARARGS5*/ 851static u_long 852ffs_hashalloc(ip, cg, pref, size, allocator) 853 struct inode *ip; 854 int cg; 855 long pref; 856 int size; /* size for data blocks, mode for inodes */ 857 allocfcn_t *allocator; 858{ 859 register struct fs *fs; 860 long result; /* XXX why not same type as we return? */ 861 int i, icg = cg; 862 863#ifdef DIAGNOSTIC 864 if (ITOV(ip)->v_mount->mnt_kern_flag & MNTK_SUSPENDED) 865 panic("ffs_hashalloc: allocation on suspended filesystem"); 866#endif 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 */ 908static ufs_daddr_t 909ffs_fragextend(ip, cg, bprev, osize, nsize) 910 struct inode *ip; 911 int cg; 912 long bprev; 913 int osize, nsize; 914{ 915 register struct fs *fs; 916 register struct cg *cgp; 917 struct buf *bp; 918 long bno; 919 int frags, bbase; 920 int i, error; 921 u_int8_t *blksfree; 922 923 fs = ip->i_fs; 924 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 925 return (0); 926 frags = numfrags(fs, nsize); 927 bbase = fragnum(fs, bprev); 928 if (bbase > fragnum(fs, (bprev + frags - 1))) { 929 /* cannot extend across a block boundary */ 930 return (0); 931 } 932 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 933 (int)fs->fs_cgsize, NOCRED, &bp); 934 if (error) { 935 brelse(bp); 936 return (0); 937 } 938 cgp = (struct cg *)bp->b_data; 939 if (!cg_chkmagic(cgp)) { 940 brelse(bp); 941 return (0); 942 } 943 bp->b_xflags |= BX_BKGRDWRITE; 944 cgp->cg_time = time_second; 945 bno = dtogd(fs, bprev); 946 blksfree = cg_blksfree(cgp); 947 for (i = numfrags(fs, osize); i < frags; i++) 948 if (isclr(blksfree, bno + i)) { 949 brelse(bp); 950 return (0); 951 } 952 /* 953 * the current fragment can be extended 954 * deduct the count on fragment being extended into 955 * increase the count on the remaining fragment (if any) 956 * allocate the extended piece 957 */ 958 for (i = frags; i < fs->fs_frag - bbase; i++) 959 if (isclr(blksfree, bno + i)) 960 break; 961 cgp->cg_frsum[i - numfrags(fs, osize)]--; 962 if (i != frags) 963 cgp->cg_frsum[i - frags]++; 964 for (i = numfrags(fs, osize); i < frags; i++) { 965 clrbit(blksfree, bno + i); 966 cgp->cg_cs.cs_nffree--; 967 fs->fs_cstotal.cs_nffree--; 968 fs->fs_cs(fs, cg).cs_nffree--; 969 } 970 fs->fs_fmod = 1; 971 if (DOINGSOFTDEP(ITOV(ip))) 972 softdep_setup_blkmapdep(bp, fs, bprev); 973 if (fs->fs_active != 0) 974 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 975 bdwrite(bp); 976 return (bprev); 977} 978 979/* 980 * Determine whether a block can be allocated. 981 * 982 * Check to see if a block of the appropriate size is available, 983 * and if it is, allocate it. 984 */ 985static ufs_daddr_t 986ffs_alloccg(ip, cg, bpref, size) 987 struct inode *ip; 988 int cg; 989 ufs_daddr_t bpref; 990 int size; 991{ 992 register struct fs *fs; 993 register struct cg *cgp; 994 struct buf *bp; 995 register int i; 996 ufs_daddr_t bno, blkno; 997 int allocsiz, error, frags; 998 u_int8_t *blksfree; 999 1000 fs = ip->i_fs; 1001 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 1002 return (0); 1003 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1004 (int)fs->fs_cgsize, NOCRED, &bp); 1005 if (error) { 1006 brelse(bp); 1007 return (0); 1008 } 1009 cgp = (struct cg *)bp->b_data; 1010 if (!cg_chkmagic(cgp) || 1011 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 1012 brelse(bp); 1013 return (0); 1014 } 1015 bp->b_xflags |= BX_BKGRDWRITE; 1016 cgp->cg_time = time_second; 1017 if (size == fs->fs_bsize) { 1018 bno = ffs_alloccgblk(ip, bp, bpref); 1019 if (fs->fs_active != 0) 1020 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1021 bdwrite(bp); 1022 return (bno); 1023 } 1024 /* 1025 * check to see if any fragments are already available 1026 * allocsiz is the size which will be allocated, hacking 1027 * it down to a smaller size if necessary 1028 */ 1029 blksfree = cg_blksfree(cgp); 1030 frags = numfrags(fs, size); 1031 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 1032 if (cgp->cg_frsum[allocsiz] != 0) 1033 break; 1034 if (allocsiz == fs->fs_frag) { 1035 /* 1036 * no fragments were available, so a block will be 1037 * allocated, and hacked up 1038 */ 1039 if (cgp->cg_cs.cs_nbfree == 0) { 1040 brelse(bp); 1041 return (0); 1042 } 1043 bno = ffs_alloccgblk(ip, bp, bpref); 1044 bpref = dtogd(fs, bno); 1045 for (i = frags; i < fs->fs_frag; i++) 1046 setbit(blksfree, bpref + i); 1047 i = fs->fs_frag - frags; 1048 cgp->cg_cs.cs_nffree += i; 1049 fs->fs_cstotal.cs_nffree += i; 1050 fs->fs_cs(fs, cg).cs_nffree += i; 1051 fs->fs_fmod = 1; 1052 cgp->cg_frsum[i]++; 1053 if (fs->fs_active != 0) 1054 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1055 bdwrite(bp); 1056 return (bno); 1057 } 1058 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 1059 if (bno < 0) { 1060 brelse(bp); 1061 return (0); 1062 } 1063 for (i = 0; i < frags; i++) 1064 clrbit(blksfree, bno + i); 1065 cgp->cg_cs.cs_nffree -= frags; 1066 fs->fs_cstotal.cs_nffree -= frags; 1067 fs->fs_cs(fs, cg).cs_nffree -= frags; 1068 fs->fs_fmod = 1; 1069 cgp->cg_frsum[allocsiz]--; 1070 if (frags != allocsiz) 1071 cgp->cg_frsum[allocsiz - frags]++; 1072 blkno = cg * fs->fs_fpg + bno; 1073 if (DOINGSOFTDEP(ITOV(ip))) 1074 softdep_setup_blkmapdep(bp, fs, blkno); 1075 if (fs->fs_active != 0) 1076 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1077 bdwrite(bp); 1078 return ((u_long)blkno); 1079} 1080 1081/* 1082 * Allocate a block in a cylinder group. 1083 * 1084 * This algorithm implements the following policy: 1085 * 1) allocate the requested block. 1086 * 2) allocate a rotationally optimal block in the same cylinder. 1087 * 3) allocate the next available block on the block rotor for the 1088 * specified cylinder group. 1089 * Note that this routine only allocates fs_bsize blocks; these 1090 * blocks may be fragmented by the routine that allocates them. 1091 */ 1092static ufs_daddr_t 1093ffs_alloccgblk(ip, bp, bpref) 1094 struct inode *ip; 1095 struct buf *bp; 1096 ufs_daddr_t bpref; 1097{ 1098 struct fs *fs; 1099 struct cg *cgp; 1100 ufs_daddr_t bno, blkno; 1101 int cylno, pos, delta; 1102 short *cylbp; 1103 register int i; 1104 u_int8_t *blksfree; 1105 1106 fs = ip->i_fs; 1107 cgp = (struct cg *)bp->b_data; 1108 blksfree = cg_blksfree(cgp); 1109 if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) { 1110 bpref = cgp->cg_rotor; 1111 goto norot; 1112 } 1113 bpref = blknum(fs, bpref); 1114 bpref = dtogd(fs, bpref); 1115 /* 1116 * if the requested block is available, use it 1117 */ 1118 if (ffs_isblock(fs, blksfree, fragstoblks(fs, bpref))) { 1119 bno = bpref; 1120 goto gotit; 1121 } 1122 if (fs->fs_nrpos <= 1 || fs->fs_cpc == 0) { 1123 /* 1124 * Block layout information is not available. 1125 * Leaving bpref unchanged means we take the 1126 * next available free block following the one 1127 * we just allocated. Hopefully this will at 1128 * least hit a track cache on drives of unknown 1129 * geometry (e.g. SCSI). 1130 */ 1131 goto norot; 1132 } 1133 /* 1134 * check for a block available on the same cylinder 1135 */ 1136 cylno = cbtocylno(fs, bpref); 1137 if (cg_blktot(cgp)[cylno] == 0) 1138 goto norot; 1139 /* 1140 * check the summary information to see if a block is 1141 * available in the requested cylinder starting at the 1142 * requested rotational position and proceeding around. 1143 */ 1144 cylbp = cg_blks(fs, cgp, cylno); 1145 pos = cbtorpos(fs, bpref); 1146 for (i = pos; i < fs->fs_nrpos; i++) 1147 if (cylbp[i] > 0) 1148 break; 1149 if (i == fs->fs_nrpos) 1150 for (i = 0; i < pos; i++) 1151 if (cylbp[i] > 0) 1152 break; 1153 if (cylbp[i] > 0) { 1154 /* 1155 * found a rotational position, now find the actual 1156 * block. A panic if none is actually there. 1157 */ 1158 pos = cylno % fs->fs_cpc; 1159 bno = (cylno - pos) * fs->fs_spc / NSPB(fs); 1160 if (fs_postbl(fs, pos)[i] == -1) { 1161 printf("pos = %d, i = %d, fs = %s\n", 1162 pos, i, fs->fs_fsmnt); 1163 panic("ffs_alloccgblk: cyl groups corrupted"); 1164 } 1165 for (i = fs_postbl(fs, pos)[i];; ) { 1166 if (ffs_isblock(fs, blksfree, bno + i)) { 1167 bno = blkstofrags(fs, (bno + i)); 1168 goto gotit; 1169 } 1170 delta = fs_rotbl(fs)[i]; 1171 if (delta <= 0 || 1172 delta + i > fragstoblks(fs, fs->fs_fpg)) 1173 break; 1174 i += delta; 1175 } 1176 printf("pos = %d, i = %d, fs = %s\n", pos, i, fs->fs_fsmnt); 1177 panic("ffs_alloccgblk: can't find blk in cyl"); 1178 } 1179norot: 1180 /* 1181 * no blocks in the requested cylinder, so take next 1182 * available one in this cylinder group. 1183 */ 1184 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 1185 if (bno < 0) 1186 return (0); 1187 cgp->cg_rotor = bno; 1188gotit: 1189 blkno = fragstoblks(fs, bno); 1190 ffs_clrblock(fs, blksfree, (long)blkno); 1191 ffs_clusteracct(fs, cgp, blkno, -1); 1192 cgp->cg_cs.cs_nbfree--; 1193 fs->fs_cstotal.cs_nbfree--; 1194 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 1195 cylno = cbtocylno(fs, bno); 1196 cg_blks(fs, cgp, cylno)[cbtorpos(fs, bno)]--; 1197 cg_blktot(cgp)[cylno]--; 1198 fs->fs_fmod = 1; 1199 blkno = cgp->cg_cgx * fs->fs_fpg + bno; 1200 if (DOINGSOFTDEP(ITOV(ip))) 1201 softdep_setup_blkmapdep(bp, fs, blkno); 1202 return (blkno); 1203} 1204 1205/* 1206 * Determine whether a cluster can be allocated. 1207 * 1208 * We do not currently check for optimal rotational layout if there 1209 * are multiple choices in the same cylinder group. Instead we just 1210 * take the first one that we find following bpref. 1211 */ 1212static ufs_daddr_t 1213ffs_clusteralloc(ip, cg, bpref, len) 1214 struct inode *ip; 1215 int cg; 1216 ufs_daddr_t bpref; 1217 int len; 1218{ 1219 register struct fs *fs; 1220 register struct cg *cgp; 1221 struct buf *bp; 1222 int i, got, run, bno, bit, map; 1223 u_char *mapp; 1224 int32_t *lp; 1225 u_int8_t *blksfree; 1226 1227 fs = ip->i_fs; 1228 if (fs->fs_maxcluster[cg] < len) 1229 return (0); 1230 if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 1231 NOCRED, &bp)) 1232 goto fail; 1233 cgp = (struct cg *)bp->b_data; 1234 if (!cg_chkmagic(cgp)) 1235 goto fail; 1236 bp->b_xflags |= BX_BKGRDWRITE; 1237 /* 1238 * Check to see if a cluster of the needed size (or bigger) is 1239 * available in this cylinder group. 1240 */ 1241 lp = &cg_clustersum(cgp)[len]; 1242 for (i = len; i <= fs->fs_contigsumsize; i++) 1243 if (*lp++ > 0) 1244 break; 1245 if (i > fs->fs_contigsumsize) { 1246 /* 1247 * This is the first time looking for a cluster in this 1248 * cylinder group. Update the cluster summary information 1249 * to reflect the true maximum sized cluster so that 1250 * future cluster allocation requests can avoid reading 1251 * the cylinder group map only to find no clusters. 1252 */ 1253 lp = &cg_clustersum(cgp)[len - 1]; 1254 for (i = len - 1; i > 0; i--) 1255 if (*lp-- > 0) 1256 break; 1257 fs->fs_maxcluster[cg] = i; 1258 goto fail; 1259 } 1260 /* 1261 * Search the cluster map to find a big enough cluster. 1262 * We take the first one that we find, even if it is larger 1263 * than we need as we prefer to get one close to the previous 1264 * block allocation. We do not search before the current 1265 * preference point as we do not want to allocate a block 1266 * that is allocated before the previous one (as we will 1267 * then have to wait for another pass of the elevator 1268 * algorithm before it will be read). We prefer to fail and 1269 * be recalled to try an allocation in the next cylinder group. 1270 */ 1271 if (dtog(fs, bpref) != cg) 1272 bpref = 0; 1273 else 1274 bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 1275 mapp = &cg_clustersfree(cgp)[bpref / NBBY]; 1276 map = *mapp++; 1277 bit = 1 << (bpref % NBBY); 1278 for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) { 1279 if ((map & bit) == 0) { 1280 run = 0; 1281 } else { 1282 run++; 1283 if (run == len) 1284 break; 1285 } 1286 if ((got & (NBBY - 1)) != (NBBY - 1)) { 1287 bit <<= 1; 1288 } else { 1289 map = *mapp++; 1290 bit = 1; 1291 } 1292 } 1293 if (got >= cgp->cg_nclusterblks) 1294 goto fail; 1295 /* 1296 * Allocate the cluster that we have found. 1297 */ 1298 blksfree = cg_blksfree(cgp); 1299 for (i = 1; i <= len; i++) 1300 if (!ffs_isblock(fs, blksfree, got - run + i)) 1301 panic("ffs_clusteralloc: map mismatch"); 1302 bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1); 1303 if (dtog(fs, bno) != cg) 1304 panic("ffs_clusteralloc: allocated out of group"); 1305 len = blkstofrags(fs, len); 1306 for (i = 0; i < len; i += fs->fs_frag) 1307 if ((got = ffs_alloccgblk(ip, bp, bno + i)) != bno + i) 1308 panic("ffs_clusteralloc: lost block"); 1309 if (fs->fs_active != 0) 1310 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1311 bdwrite(bp); 1312 return (bno); 1313 1314fail: 1315 brelse(bp); 1316 return (0); 1317} 1318 1319/* 1320 * Determine whether an inode can be allocated. 1321 * 1322 * Check to see if an inode is available, and if it is, 1323 * allocate it using the following policy: 1324 * 1) allocate the requested inode. 1325 * 2) allocate the next available inode after the requested 1326 * inode in the specified cylinder group. 1327 */ 1328static ino_t 1329ffs_nodealloccg(ip, cg, ipref, mode) 1330 struct inode *ip; 1331 int cg; 1332 ufs_daddr_t ipref; 1333 int mode; 1334{ 1335 register struct fs *fs; 1336 register struct cg *cgp; 1337 struct buf *bp; 1338 u_int8_t *inosused; 1339 int error, start, len, loc, map, i; 1340 1341 fs = ip->i_fs; 1342 if (fs->fs_cs(fs, cg).cs_nifree == 0) 1343 return (0); 1344 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1345 (int)fs->fs_cgsize, NOCRED, &bp); 1346 if (error) { 1347 brelse(bp); 1348 return (0); 1349 } 1350 cgp = (struct cg *)bp->b_data; 1351 if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 1352 brelse(bp); 1353 return (0); 1354 } 1355 bp->b_xflags |= BX_BKGRDWRITE; 1356 cgp->cg_time = time_second; 1357 inosused = cg_inosused(cgp); 1358 if (ipref) { 1359 ipref %= fs->fs_ipg; 1360 if (isclr(inosused, ipref)) 1361 goto gotit; 1362 } 1363 start = cgp->cg_irotor / NBBY; 1364 len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 1365 loc = skpc(0xff, len, &inosused[start]); 1366 if (loc == 0) { 1367 len = start + 1; 1368 start = 0; 1369 loc = skpc(0xff, len, &inosused[0]); 1370 if (loc == 0) { 1371 printf("cg = %d, irotor = %ld, fs = %s\n", 1372 cg, (long)cgp->cg_irotor, fs->fs_fsmnt); 1373 panic("ffs_nodealloccg: map corrupted"); 1374 /* NOTREACHED */ 1375 } 1376 } 1377 i = start + len - loc; 1378 map = inosused[i]; 1379 ipref = i * NBBY; 1380 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 1381 if ((map & i) == 0) { 1382 cgp->cg_irotor = ipref; 1383 goto gotit; 1384 } 1385 } 1386 printf("fs = %s\n", fs->fs_fsmnt); 1387 panic("ffs_nodealloccg: block not in map"); 1388 /* NOTREACHED */ 1389gotit: 1390 if (DOINGSOFTDEP(ITOV(ip))) 1391 softdep_setup_inomapdep(bp, ip, cg * fs->fs_ipg + ipref); 1392 setbit(inosused, ipref); 1393 cgp->cg_cs.cs_nifree--; 1394 fs->fs_cstotal.cs_nifree--; 1395 fs->fs_cs(fs, cg).cs_nifree--; 1396 fs->fs_fmod = 1; 1397 if ((mode & IFMT) == IFDIR) { 1398 cgp->cg_cs.cs_ndir++; 1399 fs->fs_cstotal.cs_ndir++; 1400 fs->fs_cs(fs, cg).cs_ndir++; 1401 } 1402 bdwrite(bp); 1403 return (cg * fs->fs_ipg + ipref); 1404} 1405 1406/* 1407 * Free a block or fragment. 1408 * 1409 * The specified block or fragment is placed back in the 1410 * free map. If a fragment is deallocated, a possible 1411 * block reassembly is checked. 1412 */ 1413void 1414ffs_blkfree(ip, bno, size) 1415 register struct inode *ip; 1416 ufs_daddr_t bno; 1417 long size; 1418{ 1419 register struct fs *fs; 1420 register struct cg *cgp; 1421 struct buf *bp; 1422 ufs_daddr_t fragno, cgbno; 1423 int i, error, cg, blk, frags, bbase; 1424 u_int8_t *blksfree; 1425#ifdef DIAGNOSTIC 1426 struct vnode *vp; 1427#endif 1428 1429 fs = ip->i_fs; 1430#ifdef DIAGNOSTIC 1431 if ((vp = ITOV(ip)) != NULL && vp->v_mount != NULL && 1432 (vp->v_mount->mnt_kern_flag & MNTK_SUSPENDED)) 1433 panic("ffs_blkfree: deallocation on suspended filesystem"); 1434 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0 || 1435 fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) { 1436 printf("dev=%s, bno = %ld, bsize = %ld, size = %ld, fs = %s\n", 1437 devtoname(ip->i_dev), (long)bno, (long)fs->fs_bsize, size, 1438 fs->fs_fsmnt); 1439 panic("ffs_blkfree: bad size"); 1440 } 1441#endif 1442 if ((ip->i_devvp->v_flag & VCOPYONWRITE) && 1443 ffs_snapblkfree(ip, bno, size)) 1444 return; 1445 VOP_FREEBLKS(ip->i_devvp, fsbtodb(fs, bno), size); 1446 cg = dtog(fs, bno); 1447 if ((u_int)bno >= fs->fs_size) { 1448 printf("bad block %ld, ino %lu\n", 1449 (long)bno, (u_long)ip->i_number); 1450 ffs_fserr(fs, ip->i_uid, "bad block"); 1451 return; 1452 } 1453 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1454 (int)fs->fs_cgsize, NOCRED, &bp); 1455 if (error) { 1456 brelse(bp); 1457 return; 1458 } 1459 cgp = (struct cg *)bp->b_data; 1460 if (!cg_chkmagic(cgp)) { 1461 brelse(bp); 1462 return; 1463 } 1464 bp->b_xflags |= BX_BKGRDWRITE; 1465 cgp->cg_time = time_second; 1466 cgbno = dtogd(fs, bno); 1467 blksfree = cg_blksfree(cgp); 1468 if (size == fs->fs_bsize) { 1469 fragno = fragstoblks(fs, cgbno); 1470 if (!ffs_isfreeblock(fs, blksfree, fragno)) { 1471 printf("dev = %s, block = %ld, fs = %s\n", 1472 devtoname(ip->i_dev), (long)bno, fs->fs_fsmnt); 1473 panic("ffs_blkfree: freeing free block"); 1474 } 1475 ffs_setblock(fs, blksfree, fragno); 1476 ffs_clusteracct(fs, cgp, fragno, 1); 1477 cgp->cg_cs.cs_nbfree++; 1478 fs->fs_cstotal.cs_nbfree++; 1479 fs->fs_cs(fs, cg).cs_nbfree++; 1480 i = cbtocylno(fs, cgbno); 1481 cg_blks(fs, cgp, i)[cbtorpos(fs, cgbno)]++; 1482 cg_blktot(cgp)[i]++; 1483 } else { 1484 bbase = cgbno - fragnum(fs, cgbno); 1485 /* 1486 * decrement the counts associated with the old frags 1487 */ 1488 blk = blkmap(fs, blksfree, bbase); 1489 ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 1490 /* 1491 * deallocate the fragment 1492 */ 1493 frags = numfrags(fs, size); 1494 for (i = 0; i < frags; i++) { 1495 if (isset(blksfree, cgbno + i)) { 1496 printf("dev = %s, block = %ld, fs = %s\n", 1497 devtoname(ip->i_dev), (long)(bno + i), 1498 fs->fs_fsmnt); 1499 panic("ffs_blkfree: freeing free frag"); 1500 } 1501 setbit(blksfree, cgbno + i); 1502 } 1503 cgp->cg_cs.cs_nffree += i; 1504 fs->fs_cstotal.cs_nffree += i; 1505 fs->fs_cs(fs, cg).cs_nffree += i; 1506 /* 1507 * add back in counts associated with the new frags 1508 */ 1509 blk = blkmap(fs, blksfree, bbase); 1510 ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 1511 /* 1512 * if a complete block has been reassembled, account for it 1513 */ 1514 fragno = fragstoblks(fs, bbase); 1515 if (ffs_isblock(fs, blksfree, fragno)) { 1516 cgp->cg_cs.cs_nffree -= fs->fs_frag; 1517 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 1518 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 1519 ffs_clusteracct(fs, cgp, fragno, 1); 1520 cgp->cg_cs.cs_nbfree++; 1521 fs->fs_cstotal.cs_nbfree++; 1522 fs->fs_cs(fs, cg).cs_nbfree++; 1523 i = cbtocylno(fs, bbase); 1524 cg_blks(fs, cgp, i)[cbtorpos(fs, bbase)]++; 1525 cg_blktot(cgp)[i]++; 1526 } 1527 } 1528 fs->fs_fmod = 1; 1529 if (fs->fs_active != 0) 1530 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1531 bdwrite(bp); 1532} 1533 1534#ifdef DIAGNOSTIC 1535/* 1536 * Verify allocation of a block or fragment. Returns true if block or 1537 * fragment is allocated, false if it is free. 1538 */ 1539static int 1540ffs_checkblk(ip, bno, size) 1541 struct inode *ip; 1542 ufs_daddr_t bno; 1543 long size; 1544{ 1545 struct fs *fs; 1546 struct cg *cgp; 1547 struct buf *bp; 1548 int i, error, frags, free; 1549 u_int8_t *blksfree; 1550 1551 fs = ip->i_fs; 1552 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1553 printf("bsize = %ld, size = %ld, fs = %s\n", 1554 (long)fs->fs_bsize, size, fs->fs_fsmnt); 1555 panic("ffs_checkblk: bad size"); 1556 } 1557 if ((u_int)bno >= fs->fs_size) 1558 panic("ffs_checkblk: bad block %d", bno); 1559 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))), 1560 (int)fs->fs_cgsize, NOCRED, &bp); 1561 if (error) 1562 panic("ffs_checkblk: cg bread failed"); 1563 cgp = (struct cg *)bp->b_data; 1564 if (!cg_chkmagic(cgp)) 1565 panic("ffs_checkblk: cg magic mismatch"); 1566 bp->b_xflags |= BX_BKGRDWRITE; 1567 blksfree = cg_blksfree(cgp); 1568 bno = dtogd(fs, bno); 1569 if (size == fs->fs_bsize) { 1570 free = ffs_isblock(fs, blksfree, fragstoblks(fs, bno)); 1571 } else { 1572 frags = numfrags(fs, size); 1573 for (free = 0, i = 0; i < frags; i++) 1574 if (isset(blksfree, bno + i)) 1575 free++; 1576 if (free != 0 && free != frags) 1577 panic("ffs_checkblk: partially free fragment"); 1578 } 1579 brelse(bp); 1580 return (!free); 1581} 1582#endif /* DIAGNOSTIC */ 1583 1584/* 1585 * Free an inode. 1586 */ 1587int 1588ffs_vfree(pvp, ino, mode) 1589 struct vnode *pvp; 1590 ino_t ino; 1591 int mode; 1592{ 1593 if (DOINGSOFTDEP(pvp)) { 1594 softdep_freefile(pvp, ino, mode); 1595 return (0); 1596 } 1597 return (ffs_freefile(VTOI(pvp), ino, mode)); 1598} 1599 1600/* 1601 * Do the actual free operation. 1602 * The specified inode is placed back in the free map. 1603 */ 1604int 1605ffs_freefile(pip, ino, mode) 1606 struct inode *pip; 1607 ino_t ino; 1608 int mode; 1609{ 1610 register struct fs *fs; 1611 register struct cg *cgp; 1612 struct buf *bp; 1613 int error, cg; 1614 u_int8_t *inosused; 1615 1616 fs = pip->i_fs; 1617 if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 1618 panic("ffs_vfree: range: dev = (%d,%d), ino = %d, fs = %s", 1619 major(pip->i_dev), minor(pip->i_dev), ino, fs->fs_fsmnt); 1620 cg = ino_to_cg(fs, ino); 1621 error = bread(pip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1622 (int)fs->fs_cgsize, NOCRED, &bp); 1623 if (error) { 1624 brelse(bp); 1625 return (error); 1626 } 1627 cgp = (struct cg *)bp->b_data; 1628 if (!cg_chkmagic(cgp)) { 1629 brelse(bp); 1630 return (0); 1631 } 1632 bp->b_xflags |= BX_BKGRDWRITE; 1633 cgp->cg_time = time_second; 1634 inosused = cg_inosused(cgp); 1635 ino %= fs->fs_ipg; 1636 if (isclr(inosused, ino)) { 1637 printf("dev = %s, ino = %lu, fs = %s\n", devtoname(pip->i_dev), 1638 (u_long)ino + cg * fs->fs_ipg, fs->fs_fsmnt); 1639 if (fs->fs_ronly == 0) 1640 panic("ffs_vfree: freeing free inode"); 1641 } 1642 clrbit(inosused, ino); 1643 if (ino < cgp->cg_irotor) 1644 cgp->cg_irotor = ino; 1645 cgp->cg_cs.cs_nifree++; 1646 fs->fs_cstotal.cs_nifree++; 1647 fs->fs_cs(fs, cg).cs_nifree++; 1648 if ((mode & IFMT) == IFDIR) { 1649 cgp->cg_cs.cs_ndir--; 1650 fs->fs_cstotal.cs_ndir--; 1651 fs->fs_cs(fs, cg).cs_ndir--; 1652 } 1653 fs->fs_fmod = 1; 1654 bdwrite(bp); 1655 return (0); 1656} 1657 1658/* 1659 * Find a block of the specified size in the specified cylinder group. 1660 * 1661 * It is a panic if a request is made to find a block if none are 1662 * available. 1663 */ 1664static ufs_daddr_t 1665ffs_mapsearch(fs, cgp, bpref, allocsiz) 1666 register struct fs *fs; 1667 register struct cg *cgp; 1668 ufs_daddr_t bpref; 1669 int allocsiz; 1670{ 1671 ufs_daddr_t bno; 1672 int start, len, loc, i; 1673 int blk, field, subfield, pos; 1674 u_int8_t *blksfree; 1675 1676 /* 1677 * find the fragment by searching through the free block 1678 * map for an appropriate bit pattern 1679 */ 1680 if (bpref) 1681 start = dtogd(fs, bpref) / NBBY; 1682 else 1683 start = cgp->cg_frotor / NBBY; 1684 blksfree = cg_blksfree(cgp); 1685 len = howmany(fs->fs_fpg, NBBY) - start; 1686 loc = scanc((u_int)len, (u_char *)&blksfree[start], 1687 (u_char *)fragtbl[fs->fs_frag], 1688 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 1689 if (loc == 0) { 1690 len = start + 1; 1691 start = 0; 1692 loc = scanc((u_int)len, (u_char *)&blksfree[0], 1693 (u_char *)fragtbl[fs->fs_frag], 1694 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 1695 if (loc == 0) { 1696 printf("start = %d, len = %d, fs = %s\n", 1697 start, len, fs->fs_fsmnt); 1698 panic("ffs_alloccg: map corrupted"); 1699 /* NOTREACHED */ 1700 } 1701 } 1702 bno = (start + len - loc) * NBBY; 1703 cgp->cg_frotor = bno; 1704 /* 1705 * found the byte in the map 1706 * sift through the bits to find the selected frag 1707 */ 1708 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 1709 blk = blkmap(fs, blksfree, bno); 1710 blk <<= 1; 1711 field = around[allocsiz]; 1712 subfield = inside[allocsiz]; 1713 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 1714 if ((blk & field) == subfield) 1715 return (bno + pos); 1716 field <<= 1; 1717 subfield <<= 1; 1718 } 1719 } 1720 printf("bno = %lu, fs = %s\n", (u_long)bno, fs->fs_fsmnt); 1721 panic("ffs_alloccg: block not in map"); 1722 return (-1); 1723} 1724 1725/* 1726 * Update the cluster map because of an allocation or free. 1727 * 1728 * Cnt == 1 means free; cnt == -1 means allocating. 1729 */ 1730void 1731ffs_clusteracct(fs, cgp, blkno, cnt) 1732 struct fs *fs; 1733 struct cg *cgp; 1734 ufs_daddr_t blkno; 1735 int cnt; 1736{ 1737 int32_t *sump; 1738 int32_t *lp; 1739 u_char *freemapp, *mapp; 1740 int i, start, end, forw, back, map, bit; 1741 1742 if (fs->fs_contigsumsize <= 0) 1743 return; 1744 freemapp = cg_clustersfree(cgp); 1745 sump = cg_clustersum(cgp); 1746 /* 1747 * Allocate or clear the actual block. 1748 */ 1749 if (cnt > 0) 1750 setbit(freemapp, blkno); 1751 else 1752 clrbit(freemapp, blkno); 1753 /* 1754 * Find the size of the cluster going forward. 1755 */ 1756 start = blkno + 1; 1757 end = start + fs->fs_contigsumsize; 1758 if (end >= cgp->cg_nclusterblks) 1759 end = cgp->cg_nclusterblks; 1760 mapp = &freemapp[start / NBBY]; 1761 map = *mapp++; 1762 bit = 1 << (start % NBBY); 1763 for (i = start; i < end; i++) { 1764 if ((map & bit) == 0) 1765 break; 1766 if ((i & (NBBY - 1)) != (NBBY - 1)) { 1767 bit <<= 1; 1768 } else { 1769 map = *mapp++; 1770 bit = 1; 1771 } 1772 } 1773 forw = i - start; 1774 /* 1775 * Find the size of the cluster going backward. 1776 */ 1777 start = blkno - 1; 1778 end = start - fs->fs_contigsumsize; 1779 if (end < 0) 1780 end = -1; 1781 mapp = &freemapp[start / NBBY]; 1782 map = *mapp--; 1783 bit = 1 << (start % NBBY); 1784 for (i = start; i > end; i--) { 1785 if ((map & bit) == 0) 1786 break; 1787 if ((i & (NBBY - 1)) != 0) { 1788 bit >>= 1; 1789 } else { 1790 map = *mapp--; 1791 bit = 1 << (NBBY - 1); 1792 } 1793 } 1794 back = start - i; 1795 /* 1796 * Account for old cluster and the possibly new forward and 1797 * back clusters. 1798 */ 1799 i = back + forw + 1; 1800 if (i > fs->fs_contigsumsize) 1801 i = fs->fs_contigsumsize; 1802 sump[i] += cnt; 1803 if (back > 0) 1804 sump[back] -= cnt; 1805 if (forw > 0) 1806 sump[forw] -= cnt; 1807 /* 1808 * Update cluster summary information. 1809 */ 1810 lp = &sump[fs->fs_contigsumsize]; 1811 for (i = fs->fs_contigsumsize; i > 0; i--) 1812 if (*lp-- > 0) 1813 break; 1814 fs->fs_maxcluster[cgp->cg_cgx] = i; 1815} 1816 1817/* 1818 * Fserr prints the name of a file system with an error diagnostic. 1819 * 1820 * The form of the error message is: 1821 * fs: error message 1822 */ 1823static void 1824ffs_fserr(fs, uid, cp) 1825 struct fs *fs; 1826 u_int uid; 1827 char *cp; 1828{ 1829 struct proc *p = curproc; /* XXX */ 1830 1831 log(LOG_ERR, "pid %d (%s), uid %d on %s: %s\n", p ? p->p_pid : -1, 1832 p ? p->p_comm : "-", uid, fs->fs_fsmnt, cp); 1833} 1834 1835/* 1836 * This function provides the capability for the fsck program to 1837 * update an active filesystem. Six operations are provided: 1838 * 1839 * adjrefcnt(inode, amt) - adjusts the reference count on the 1840 * specified inode by the specified amount. Under normal 1841 * operation the count should always go down. Decrementing 1842 * the count to zero will cause the inode to be freed. 1843 * adjblkcnt(inode, amt) - adjust the number of blocks used to 1844 * by the specifed amount. 1845 * freedirs(inode, count) - directory inodes [inode..inode + count - 1] 1846 * are marked as free. Inodes should never have to be marked 1847 * as in use. 1848 * freefiles(inode, count) - file inodes [inode..inode + count - 1] 1849 * are marked as free. Inodes should never have to be marked 1850 * as in use. 1851 * freeblks(blockno, size) - blocks [blockno..blockno + size - 1] 1852 * are marked as free. Blocks should never have to be marked 1853 * as in use. 1854 * setflags(flags, set/clear) - the fs_flags field has the specified 1855 * flags set (second parameter +1) or cleared (second parameter -1). 1856 */ 1857 1858static int sysctl_ffs_fsck __P((SYSCTL_HANDLER_ARGS)); 1859 1860SYSCTL_PROC(_vfs_ffs, FFS_ADJ_REFCNT, adjrefcnt, CTLFLAG_WR|CTLTYPE_STRUCT, 1861 0, 0, sysctl_ffs_fsck, "S,fsck", "Adjust Inode Reference Count"); 1862 1863SYSCTL_NODE(_vfs_ffs, FFS_ADJ_BLKCNT, adjblkcnt, CTLFLAG_WR, 1864 sysctl_ffs_fsck, "Adjust Inode Used Blocks Count"); 1865 1866SYSCTL_NODE(_vfs_ffs, FFS_DIR_FREE, freedirs, CTLFLAG_WR, 1867 sysctl_ffs_fsck, "Free Range of Directory Inodes"); 1868 1869SYSCTL_NODE(_vfs_ffs, FFS_FILE_FREE, freefiles, CTLFLAG_WR, 1870 sysctl_ffs_fsck, "Free Range of File Inodes"); 1871 1872SYSCTL_NODE(_vfs_ffs, FFS_BLK_FREE, freeblks, CTLFLAG_WR, 1873 sysctl_ffs_fsck, "Free Range of Blocks"); 1874 1875SYSCTL_NODE(_vfs_ffs, FFS_SET_FLAGS, setflags, CTLFLAG_WR, 1876 sysctl_ffs_fsck, "Change Filesystem Flags"); 1877 1878#ifdef DEBUG 1879static int fsckcmds = 0; 1880SYSCTL_INT(_debug, OID_AUTO, fsckcmds, CTLFLAG_RW, &fsckcmds, 0, ""); 1881#endif /* DEBUG */ 1882 1883static int 1884sysctl_ffs_fsck(SYSCTL_HANDLER_ARGS) 1885{ 1886 struct fsck_cmd cmd; 1887 struct inode tip; 1888 struct ufsmount *ump; 1889 struct vnode *vp; 1890 struct inode *ip; 1891 struct mount *mp; 1892 struct fs *fs; 1893 ufs_daddr_t blkno; 1894 long blkcnt, blksize; 1895 struct file *fp; 1896 int filetype, error; 1897 1898 if (req->newlen > sizeof cmd) 1899 return (EBADRPC); 1900 if ((error = SYSCTL_IN(req, &cmd, sizeof cmd)) != 0) 1901 return (error); 1902 if (cmd.version != FFS_CMD_VERSION) 1903 return (ERPCMISMATCH); 1904 if ((error = getvnode(curproc->p_fd, cmd.handle, &fp)) != 0) 1905 return (error); 1906 vn_start_write((struct vnode *)fp->f_data, &mp, V_WAIT); 1907 if (mp == 0 || strncmp(mp->mnt_stat.f_fstypename, "ufs", MFSNAMELEN)) { 1908 vn_finished_write(mp); 1909 return (EINVAL); 1910 } 1911 if (mp->mnt_flag & MNT_RDONLY) { 1912 vn_finished_write(mp); 1913 return (EROFS); 1914 } 1915 ump = VFSTOUFS(mp); 1916 fs = ump->um_fs; 1917 filetype = IFREG; 1918 1919 switch (oidp->oid_number) { 1920 1921 case FFS_SET_FLAGS: 1922#ifdef DEBUG 1923 if (fsckcmds) 1924 printf("%s: %s flags\n", mp->mnt_stat.f_mntonname, 1925 cmd.size > 0 ? "set" : "clear"); 1926#endif /* DEBUG */ 1927 if (cmd.size > 0) 1928 fs->fs_flags |= (long)cmd.value; 1929 else 1930 fs->fs_flags &= ~(long)cmd.value; 1931 break; 1932 1933 case FFS_ADJ_REFCNT: 1934#ifdef DEBUG 1935 if (fsckcmds) { 1936 printf("%s: adjust inode %d count by %ld\n", 1937 mp->mnt_stat.f_mntonname, (ino_t)cmd.value, 1938 cmd.size); 1939 } 1940#endif /* DEBUG */ 1941 if ((error = VFS_VGET(mp, (ino_t)cmd.value, &vp)) != 0) 1942 break; 1943 ip = VTOI(vp); 1944 ip->i_nlink += cmd.size; 1945 ip->i_effnlink += cmd.size; 1946 ip->i_flag |= IN_CHANGE; 1947 if (DOINGSOFTDEP(vp)) 1948 softdep_change_linkcnt(ip); 1949 vput(vp); 1950 break; 1951 1952 case FFS_ADJ_BLKCNT: 1953#ifdef DEBUG 1954 if (fsckcmds) { 1955 printf("%s: adjust inode %d block count by %ld\n", 1956 mp->mnt_stat.f_mntonname, (ino_t)cmd.value, 1957 cmd.size); 1958 } 1959#endif /* DEBUG */ 1960 if ((error = VFS_VGET(mp, (ino_t)cmd.value, &vp)) != 0) 1961 break; 1962 ip = VTOI(vp); 1963 ip->i_blocks += cmd.size; 1964 ip->i_flag |= IN_CHANGE; 1965 vput(vp); 1966 break; 1967 1968 case FFS_DIR_FREE: 1969 filetype = IFDIR; 1970 /* fall through */ 1971 1972 case FFS_FILE_FREE: 1973#ifdef DEBUG 1974 if (fsckcmds) { 1975 if (cmd.size == 1) 1976 printf("%s: free %s inode %d\n", 1977 mp->mnt_stat.f_mntonname, 1978 filetype == IFDIR ? "directory" : "file", 1979 (ino_t)cmd.value); 1980 else 1981 printf("%s: free %s inodes %d-%d\n", 1982 mp->mnt_stat.f_mntonname, 1983 filetype == IFDIR ? "directory" : "file", 1984 (ino_t)cmd.value, 1985 (ino_t)(cmd.value + cmd.size - 1)); 1986 } 1987#endif /* DEBUG */ 1988 tip.i_devvp = ump->um_devvp; 1989 tip.i_dev = ump->um_dev; 1990 tip.i_fs = fs; 1991 while (cmd.size > 0) { 1992 if ((error = ffs_freefile(&tip, cmd.value, filetype))) 1993 break; 1994 cmd.size -= 1; 1995 cmd.value += 1; 1996 } 1997 break; 1998 1999 case FFS_BLK_FREE: 2000#ifdef DEBUG 2001 if (fsckcmds) { 2002 if (cmd.size == 1) 2003 printf("%s: free block %d\n", 2004 mp->mnt_stat.f_mntonname, 2005 (ufs_daddr_t)cmd.value); 2006 else 2007 printf("%s: free blocks %d-%ld\n", 2008 mp->mnt_stat.f_mntonname, 2009 (ufs_daddr_t)cmd.value, 2010 (ufs_daddr_t)cmd.value + cmd.size - 1); 2011 } 2012#endif /* DEBUG */ 2013 tip.i_number = ROOTINO; 2014 tip.i_devvp = ump->um_devvp; 2015 tip.i_dev = ump->um_dev; 2016 tip.i_fs = fs; 2017 tip.i_size = cmd.size * fs->fs_fsize; 2018 tip.i_uid = 0; 2019 tip.i_vnode = NULL; 2020 blkno = (ufs_daddr_t)cmd.value; 2021 blkcnt = cmd.size; 2022 blksize = fs->fs_frag - (blkno % fs->fs_frag); 2023 while (blkcnt > 0) { 2024 if (blksize > blkcnt) 2025 blksize = blkcnt; 2026 ffs_blkfree(&tip, blkno, blksize * fs->fs_fsize); 2027 blkno += blksize; 2028 blkcnt -= blksize; 2029 blksize = fs->fs_frag; 2030 } 2031 break; 2032 2033 default: 2034#ifdef DEBUG 2035 if (fsckcmds) { 2036 printf("Invalid request %d from fsck\n", 2037 oidp->oid_number); 2038 } 2039#endif /* DEBUG */ 2040 error = EINVAL; 2041 break; 2042 2043 } 2044 vn_finished_write(mp); 2045 return (error); 2046} 2047