Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/ufs/ffs/ffs_alloc.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
1 /* 2 * Copyright (c) 2002 Networks Associates Technology, Inc. 3 * All rights reserved. 4 * 5 * This software was developed for the FreeBSD Project by Marshall 6 * Kirk McKusick and Network Associates Laboratories, the Security 7 * Research Division of Network Associates, Inc. under DARPA/SPAWAR 8 * contract N66001-01-C-8035 ("CBOSS"), as part of the DARPA CHATS 9 * research program 10 * 11 * Copyright (c) 1982, 1986, 1989, 1993 12 * The Regents of the University of California. All rights reserved. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions 16 * are met: 17 * 1. Redistributions of source code must retain the above copyright 18 * notice, this list of conditions and the following disclaimer. 19 * 2. Redistributions in binary form must reproduce the above copyright 20 * notice, this list of conditions and the following disclaimer in the 21 * documentation and/or other materials provided with the distribution. 22 * 3. All advertising materials mentioning features or use of this software 23 * must display the following acknowledgement: 24 * This product includes software developed by the University of 25 * California, Berkeley and its contributors. 26 * 4. Neither the name of the University nor the names of its contributors 27 * may be used to endorse or promote products derived from this software 28 * without specific prior written permission. 29 * 30 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 31 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 32 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 33 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 34 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 35 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 36 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 38 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 39 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 40 * SUCH DAMAGE. 41 * 42 * @(#)ffs_alloc.c 8.18 (Berkeley) 5/26/95 43 */ 44 45 #include <sys/cdefs.h> 46 __FBSDID("$FreeBSD: releng/5.2/sys/ufs/ffs/ffs_alloc.c 121785 2003-10-31 07:25:06Z truckman $"); 47 48 #include "opt_quota.h" 49 50 #include <sys/param.h> 51 #include <sys/systm.h> 52 #include <sys/bio.h> 53 #include <sys/buf.h> 54 #include <sys/conf.h> 55 #include <sys/file.h> 56 #include <sys/filedesc.h> 57 #include <sys/proc.h> 58 #include <sys/vnode.h> 59 #include <sys/mount.h> 60 #include <sys/kernel.h> 61 #include <sys/sysctl.h> 62 #include <sys/syslog.h> 63 64 #include <ufs/ufs/extattr.h> 65 #include <ufs/ufs/quota.h> 66 #include <ufs/ufs/inode.h> 67 #include <ufs/ufs/ufs_extern.h> 68 #include <ufs/ufs/ufsmount.h> 69 70 #include <ufs/ffs/fs.h> 71 #include <ufs/ffs/ffs_extern.h> 72 73 typedef ufs2_daddr_t allocfcn_t(struct inode *ip, int cg, ufs2_daddr_t bpref, 74 int size); 75 76 static ufs2_daddr_t ffs_alloccg(struct inode *, int, ufs2_daddr_t, int); 77 static ufs2_daddr_t 78 ffs_alloccgblk(struct inode *, struct buf *, ufs2_daddr_t); 79 #ifdef DIAGNOSTIC 80 static int ffs_checkblk(struct inode *, ufs2_daddr_t, long); 81 #endif 82 static ufs2_daddr_t ffs_clusteralloc(struct inode *, int, ufs2_daddr_t, int); 83 static ino_t ffs_dirpref(struct inode *); 84 static ufs2_daddr_t ffs_fragextend(struct inode *, int, ufs2_daddr_t, int, int); 85 static void ffs_fserr(struct fs *, ino_t, char *); 86 static ufs2_daddr_t ffs_hashalloc 87 (struct inode *, int, ufs2_daddr_t, int, allocfcn_t *); 88 static ufs2_daddr_t ffs_nodealloccg(struct inode *, int, ufs2_daddr_t, int); 89 static ufs1_daddr_t ffs_mapsearch(struct fs *, struct cg *, ufs2_daddr_t, int); 90 static int ffs_reallocblks_ufs1(struct vop_reallocblks_args *); 91 static int ffs_reallocblks_ufs2(struct vop_reallocblks_args *); 92 93 /* 94 * Allocate a block in the filesystem. 95 * 96 * The size of the requested block is given, which must be some 97 * multiple of fs_fsize and <= fs_bsize. 98 * A preference may be optionally specified. If a preference is given 99 * the following hierarchy is used to allocate a block: 100 * 1) allocate the requested block. 101 * 2) allocate a rotationally optimal block in the same cylinder. 102 * 3) allocate a block in the same cylinder group. 103 * 4) quadradically rehash into other cylinder groups, until an 104 * available block is located. 105 * If no block preference is given the following heirarchy is used 106 * to allocate a block: 107 * 1) allocate a block in the cylinder group that contains the 108 * inode for the file. 109 * 2) quadradically rehash into other cylinder groups, until an 110 * available block is located. 111 */ 112 int 113 ffs_alloc(ip, lbn, bpref, size, cred, bnp) 114 struct inode *ip; 115 ufs2_daddr_t lbn, bpref; 116 int size; 117 struct ucred *cred; 118 ufs2_daddr_t *bnp; 119 { 120 struct fs *fs; 121 ufs2_daddr_t bno; 122 int cg, reclaimed; 123 #ifdef QUOTA 124 int error; 125 #endif 126 127 *bnp = 0; 128 fs = ip->i_fs; 129 #ifdef DIAGNOSTIC 130 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 131 printf("dev = %s, bsize = %ld, size = %d, fs = %s\n", 132 devtoname(ip->i_dev), (long)fs->fs_bsize, size, 133 fs->fs_fsmnt); 134 panic("ffs_alloc: bad size"); 135 } 136 if (cred == NOCRED) 137 panic("ffs_alloc: missing credential"); 138 #endif /* DIAGNOSTIC */ 139 reclaimed = 0; 140 retry: 141 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 142 goto nospace; 143 if (suser_cred(cred, PRISON_ROOT) && 144 freespace(fs, fs->fs_minfree) - numfrags(fs, size) < 0) 145 goto nospace; 146 #ifdef QUOTA 147 error = chkdq(ip, btodb(size), cred, 0); 148 if (error) 149 return (error); 150 #endif 151 if (bpref >= fs->fs_size) 152 bpref = 0; 153 if (bpref == 0) 154 cg = ino_to_cg(fs, ip->i_number); 155 else 156 cg = dtog(fs, bpref); 157 bno = ffs_hashalloc(ip, cg, bpref, size, ffs_alloccg); 158 if (bno > 0) { 159 DIP(ip, i_blocks) += btodb(size); 160 ip->i_flag |= IN_CHANGE | IN_UPDATE; 161 *bnp = bno; 162 return (0); 163 } 164 #ifdef QUOTA 165 /* 166 * Restore user's disk quota because allocation failed. 167 */ 168 (void) chkdq(ip, -btodb(size), cred, FORCE); 169 #endif 170 nospace: 171 if (fs->fs_pendingblocks > 0 && reclaimed == 0) { 172 reclaimed = 1; 173 softdep_request_cleanup(fs, ITOV(ip)); 174 goto retry; 175 } 176 ffs_fserr(fs, ip->i_number, "filesystem full"); 177 uprintf("\n%s: write failed, filesystem is full\n", fs->fs_fsmnt); 178 return (ENOSPC); 179 } 180 181 /* 182 * Reallocate a fragment to a bigger size 183 * 184 * The number and size of the old block is given, and a preference 185 * and new size is also specified. The allocator attempts to extend 186 * the original block. Failing that, the regular block allocator is 187 * invoked to get an appropriate block. 188 */ 189 int 190 ffs_realloccg(ip, lbprev, bprev, bpref, osize, nsize, cred, bpp) 191 struct inode *ip; 192 ufs2_daddr_t lbprev; 193 ufs2_daddr_t bprev; 194 ufs2_daddr_t bpref; 195 int osize, nsize; 196 struct ucred *cred; 197 struct buf **bpp; 198 { 199 struct vnode *vp; 200 struct fs *fs; 201 struct buf *bp; 202 int cg, request, error, reclaimed; 203 ufs2_daddr_t bno; 204 205 *bpp = 0; 206 vp = ITOV(ip); 207 fs = ip->i_fs; 208 #ifdef DIAGNOSTIC 209 if (vp->v_mount->mnt_kern_flag & MNTK_SUSPENDED) 210 panic("ffs_realloccg: allocation on suspended filesystem"); 211 if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 212 (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 213 printf( 214 "dev = %s, bsize = %ld, osize = %d, nsize = %d, fs = %s\n", 215 devtoname(ip->i_dev), (long)fs->fs_bsize, osize, 216 nsize, fs->fs_fsmnt); 217 panic("ffs_realloccg: bad size"); 218 } 219 if (cred == NOCRED) 220 panic("ffs_realloccg: missing credential"); 221 #endif /* DIAGNOSTIC */ 222 reclaimed = 0; 223 retry: 224 if (suser_cred(cred, PRISON_ROOT) && 225 freespace(fs, fs->fs_minfree) - numfrags(fs, nsize - osize) < 0) 226 goto nospace; 227 if (bprev == 0) { 228 printf("dev = %s, bsize = %ld, bprev = %jd, fs = %s\n", 229 devtoname(ip->i_dev), (long)fs->fs_bsize, (intmax_t)bprev, 230 fs->fs_fsmnt); 231 panic("ffs_realloccg: bad bprev"); 232 } 233 /* 234 * Allocate the extra space in the buffer. 235 */ 236 error = bread(vp, lbprev, osize, NOCRED, &bp); 237 if (error) { 238 brelse(bp); 239 return (error); 240 } 241 242 if (bp->b_blkno == bp->b_lblkno) { 243 if (lbprev >= NDADDR) 244 panic("ffs_realloccg: lbprev out of range"); 245 bp->b_blkno = fsbtodb(fs, bprev); 246 } 247 248 #ifdef QUOTA 249 error = chkdq(ip, btodb(nsize - osize), cred, 0); 250 if (error) { 251 brelse(bp); 252 return (error); 253 } 254 #endif 255 /* 256 * Check for extension in the existing location. 257 */ 258 cg = dtog(fs, bprev); 259 bno = ffs_fragextend(ip, cg, bprev, osize, nsize); 260 if (bno) { 261 if (bp->b_blkno != fsbtodb(fs, bno)) 262 panic("ffs_realloccg: bad blockno"); 263 DIP(ip, i_blocks) += btodb(nsize - osize); 264 ip->i_flag |= IN_CHANGE | IN_UPDATE; 265 allocbuf(bp, nsize); 266 bp->b_flags |= B_DONE; 267 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 268 *bpp = bp; 269 return (0); 270 } 271 /* 272 * Allocate a new disk location. 273 */ 274 if (bpref >= fs->fs_size) 275 bpref = 0; 276 switch ((int)fs->fs_optim) { 277 case FS_OPTSPACE: 278 /* 279 * Allocate an exact sized fragment. Although this makes 280 * best use of space, we will waste time relocating it if 281 * the file continues to grow. If the fragmentation is 282 * less than half of the minimum free reserve, we choose 283 * to begin optimizing for time. 284 */ 285 request = nsize; 286 if (fs->fs_minfree <= 5 || 287 fs->fs_cstotal.cs_nffree > 288 (off_t)fs->fs_dsize * fs->fs_minfree / (2 * 100)) 289 break; 290 log(LOG_NOTICE, "%s: optimization changed from SPACE to TIME\n", 291 fs->fs_fsmnt); 292 fs->fs_optim = FS_OPTTIME; 293 break; 294 case FS_OPTTIME: 295 /* 296 * At this point we have discovered a file that is trying to 297 * grow a small fragment to a larger fragment. To save time, 298 * we allocate a full sized block, then free the unused portion. 299 * If the file continues to grow, the `ffs_fragextend' call 300 * above will be able to grow it in place without further 301 * copying. If aberrant programs cause disk fragmentation to 302 * grow within 2% of the free reserve, we choose to begin 303 * optimizing for space. 304 */ 305 request = fs->fs_bsize; 306 if (fs->fs_cstotal.cs_nffree < 307 (off_t)fs->fs_dsize * (fs->fs_minfree - 2) / 100) 308 break; 309 log(LOG_NOTICE, "%s: optimization changed from TIME to SPACE\n", 310 fs->fs_fsmnt); 311 fs->fs_optim = FS_OPTSPACE; 312 break; 313 default: 314 printf("dev = %s, optim = %ld, fs = %s\n", 315 devtoname(ip->i_dev), (long)fs->fs_optim, fs->fs_fsmnt); 316 panic("ffs_realloccg: bad optim"); 317 /* NOTREACHED */ 318 } 319 bno = ffs_hashalloc(ip, cg, bpref, request, ffs_alloccg); 320 if (bno > 0) { 321 bp->b_blkno = fsbtodb(fs, bno); 322 if (!DOINGSOFTDEP(vp)) 323 ffs_blkfree(fs, ip->i_devvp, bprev, (long)osize, 324 ip->i_number); 325 if (nsize < request) 326 ffs_blkfree(fs, ip->i_devvp, bno + numfrags(fs, nsize), 327 (long)(request - nsize), ip->i_number); 328 DIP(ip, i_blocks) += btodb(nsize - osize); 329 ip->i_flag |= IN_CHANGE | IN_UPDATE; 330 allocbuf(bp, nsize); 331 bp->b_flags |= B_DONE; 332 bzero((char *)bp->b_data + osize, (u_int)nsize - osize); 333 *bpp = bp; 334 return (0); 335 } 336 #ifdef QUOTA 337 /* 338 * Restore user's disk quota because allocation failed. 339 */ 340 (void) chkdq(ip, -btodb(nsize - osize), cred, FORCE); 341 #endif 342 brelse(bp); 343 nospace: 344 /* 345 * no space available 346 */ 347 if (fs->fs_pendingblocks > 0 && reclaimed == 0) { 348 reclaimed = 1; 349 softdep_request_cleanup(fs, vp); 350 goto retry; 351 } 352 ffs_fserr(fs, ip->i_number, "filesystem full"); 353 uprintf("\n%s: write failed, filesystem is full\n", fs->fs_fsmnt); 354 return (ENOSPC); 355 } 356 357 /* 358 * Reallocate a sequence of blocks into a contiguous sequence of blocks. 359 * 360 * The vnode and an array of buffer pointers for a range of sequential 361 * logical blocks to be made contiguous is given. The allocator attempts 362 * to find a range of sequential blocks starting as close as possible 363 * from the end of the allocation for the logical block immediately 364 * preceding the current range. If successful, the physical block numbers 365 * in the buffer pointers and in the inode are changed to reflect the new 366 * allocation. If unsuccessful, the allocation is left unchanged. The 367 * success in doing the reallocation is returned. Note that the error 368 * return is not reflected back to the user. Rather the previous block 369 * allocation will be used. 370 */ 371 372 SYSCTL_NODE(_vfs, OID_AUTO, ffs, CTLFLAG_RW, 0, "FFS filesystem"); 373 374 static int doasyncfree = 1; 375 SYSCTL_INT(_vfs_ffs, OID_AUTO, doasyncfree, CTLFLAG_RW, &doasyncfree, 0, ""); 376 377 static int doreallocblks = 1; 378 SYSCTL_INT(_vfs_ffs, OID_AUTO, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, ""); 379 380 #ifdef DEBUG 381 static volatile int prtrealloc = 0; 382 #endif 383 384 int 385 ffs_reallocblks(ap) 386 struct vop_reallocblks_args /* { 387 struct vnode *a_vp; 388 struct cluster_save *a_buflist; 389 } */ *ap; 390 { 391 392 if (doreallocblks == 0) 393 return (ENOSPC); 394 if (VTOI(ap->a_vp)->i_ump->um_fstype == UFS1) 395 return (ffs_reallocblks_ufs1(ap)); 396 return (ffs_reallocblks_ufs2(ap)); 397 } 398 399 static int 400 ffs_reallocblks_ufs1(ap) 401 struct vop_reallocblks_args /* { 402 struct vnode *a_vp; 403 struct cluster_save *a_buflist; 404 } */ *ap; 405 { 406 struct fs *fs; 407 struct inode *ip; 408 struct vnode *vp; 409 struct buf *sbp, *ebp; 410 ufs1_daddr_t *bap, *sbap, *ebap = 0; 411 struct cluster_save *buflist; 412 ufs_lbn_t start_lbn, end_lbn; 413 ufs1_daddr_t soff, newblk, blkno; 414 ufs2_daddr_t pref; 415 struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 416 int i, len, start_lvl, end_lvl, ssize; 417 418 vp = ap->a_vp; 419 ip = VTOI(vp); 420 fs = ip->i_fs; 421 if (fs->fs_contigsumsize <= 0) 422 return (ENOSPC); 423 buflist = ap->a_buflist; 424 len = buflist->bs_nchildren; 425 start_lbn = buflist->bs_children[0]->b_lblkno; 426 end_lbn = start_lbn + len - 1; 427 #ifdef DIAGNOSTIC 428 for (i = 0; i < len; i++) 429 if (!ffs_checkblk(ip, 430 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 431 panic("ffs_reallocblks: unallocated block 1"); 432 for (i = 1; i < len; i++) 433 if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 434 panic("ffs_reallocblks: non-logical cluster"); 435 blkno = buflist->bs_children[0]->b_blkno; 436 ssize = fsbtodb(fs, fs->fs_frag); 437 for (i = 1; i < len - 1; i++) 438 if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize)) 439 panic("ffs_reallocblks: non-physical cluster %d", i); 440 #endif 441 /* 442 * If the latest allocation is in a new cylinder group, assume that 443 * the filesystem has decided to move and do not force it back to 444 * the previous cylinder group. 445 */ 446 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 447 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 448 return (ENOSPC); 449 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 450 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 451 return (ENOSPC); 452 /* 453 * Get the starting offset and block map for the first block. 454 */ 455 if (start_lvl == 0) { 456 sbap = &ip->i_din1->di_db[0]; 457 soff = start_lbn; 458 } else { 459 idp = &start_ap[start_lvl - 1]; 460 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 461 brelse(sbp); 462 return (ENOSPC); 463 } 464 sbap = (ufs1_daddr_t *)sbp->b_data; 465 soff = idp->in_off; 466 } 467 /* 468 * Find the preferred location for the cluster. 469 */ 470 pref = ffs_blkpref_ufs1(ip, start_lbn, soff, sbap); 471 /* 472 * If the block range spans two block maps, get the second map. 473 */ 474 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 475 ssize = len; 476 } else { 477 #ifdef DIAGNOSTIC 478 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 479 panic("ffs_reallocblk: start == end"); 480 #endif 481 ssize = len - (idp->in_off + 1); 482 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 483 goto fail; 484 ebap = (ufs1_daddr_t *)ebp->b_data; 485 } 486 /* 487 * Search the block map looking for an allocation of the desired size. 488 */ 489 if ((newblk = ffs_hashalloc(ip, dtog(fs, pref), pref, 490 len, ffs_clusteralloc)) == 0) 491 goto fail; 492 /* 493 * We have found a new contiguous block. 494 * 495 * First we have to replace the old block pointers with the new 496 * block pointers in the inode and indirect blocks associated 497 * with the file. 498 */ 499 #ifdef DEBUG 500 if (prtrealloc) 501 printf("realloc: ino %d, lbns %jd-%jd\n\told:", ip->i_number, 502 (intmax_t)start_lbn, (intmax_t)end_lbn); 503 #endif 504 blkno = newblk; 505 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 506 if (i == ssize) { 507 bap = ebap; 508 soff = -i; 509 } 510 #ifdef DIAGNOSTIC 511 if (!ffs_checkblk(ip, 512 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 513 panic("ffs_reallocblks: unallocated block 2"); 514 if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap) 515 panic("ffs_reallocblks: alloc mismatch"); 516 #endif 517 #ifdef DEBUG 518 if (prtrealloc) 519 printf(" %d,", *bap); 520 #endif 521 if (DOINGSOFTDEP(vp)) { 522 if (sbap == &ip->i_din1->di_db[0] && i < ssize) 523 softdep_setup_allocdirect(ip, start_lbn + i, 524 blkno, *bap, fs->fs_bsize, fs->fs_bsize, 525 buflist->bs_children[i]); 526 else 527 softdep_setup_allocindir_page(ip, start_lbn + i, 528 i < ssize ? sbp : ebp, soff + i, blkno, 529 *bap, buflist->bs_children[i]); 530 } 531 *bap++ = blkno; 532 } 533 /* 534 * Next we must write out the modified inode and indirect blocks. 535 * For strict correctness, the writes should be synchronous since 536 * the old block values may have been written to disk. In practise 537 * they are almost never written, but if we are concerned about 538 * strict correctness, the `doasyncfree' flag should be set to zero. 539 * 540 * The test on `doasyncfree' should be changed to test a flag 541 * that shows whether the associated buffers and inodes have 542 * been written. The flag should be set when the cluster is 543 * started and cleared whenever the buffer or inode is flushed. 544 * We can then check below to see if it is set, and do the 545 * synchronous write only when it has been cleared. 546 */ 547 if (sbap != &ip->i_din1->di_db[0]) { 548 if (doasyncfree) 549 bdwrite(sbp); 550 else 551 bwrite(sbp); 552 } else { 553 ip->i_flag |= IN_CHANGE | IN_UPDATE; 554 if (!doasyncfree) 555 UFS_UPDATE(vp, 1); 556 } 557 if (ssize < len) { 558 if (doasyncfree) 559 bdwrite(ebp); 560 else 561 bwrite(ebp); 562 } 563 /* 564 * Last, free the old blocks and assign the new blocks to the buffers. 565 */ 566 #ifdef DEBUG 567 if (prtrealloc) 568 printf("\n\tnew:"); 569 #endif 570 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 571 if (!DOINGSOFTDEP(vp)) 572 ffs_blkfree(fs, ip->i_devvp, 573 dbtofsb(fs, buflist->bs_children[i]->b_blkno), 574 fs->fs_bsize, ip->i_number); 575 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 576 #ifdef DIAGNOSTIC 577 if (!ffs_checkblk(ip, 578 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 579 panic("ffs_reallocblks: unallocated block 3"); 580 #endif 581 #ifdef DEBUG 582 if (prtrealloc) 583 printf(" %d,", blkno); 584 #endif 585 } 586 #ifdef DEBUG 587 if (prtrealloc) { 588 prtrealloc--; 589 printf("\n"); 590 } 591 #endif 592 return (0); 593 594 fail: 595 if (ssize < len) 596 brelse(ebp); 597 if (sbap != &ip->i_din1->di_db[0]) 598 brelse(sbp); 599 return (ENOSPC); 600 } 601 602 static int 603 ffs_reallocblks_ufs2(ap) 604 struct vop_reallocblks_args /* { 605 struct vnode *a_vp; 606 struct cluster_save *a_buflist; 607 } */ *ap; 608 { 609 struct fs *fs; 610 struct inode *ip; 611 struct vnode *vp; 612 struct buf *sbp, *ebp; 613 ufs2_daddr_t *bap, *sbap, *ebap = 0; 614 struct cluster_save *buflist; 615 ufs_lbn_t start_lbn, end_lbn; 616 ufs2_daddr_t soff, newblk, blkno, pref; 617 struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp; 618 int i, len, start_lvl, end_lvl, ssize; 619 620 vp = ap->a_vp; 621 ip = VTOI(vp); 622 fs = ip->i_fs; 623 if (fs->fs_contigsumsize <= 0) 624 return (ENOSPC); 625 buflist = ap->a_buflist; 626 len = buflist->bs_nchildren; 627 start_lbn = buflist->bs_children[0]->b_lblkno; 628 end_lbn = start_lbn + len - 1; 629 #ifdef DIAGNOSTIC 630 for (i = 0; i < len; i++) 631 if (!ffs_checkblk(ip, 632 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 633 panic("ffs_reallocblks: unallocated block 1"); 634 for (i = 1; i < len; i++) 635 if (buflist->bs_children[i]->b_lblkno != start_lbn + i) 636 panic("ffs_reallocblks: non-logical cluster"); 637 blkno = buflist->bs_children[0]->b_blkno; 638 ssize = fsbtodb(fs, fs->fs_frag); 639 for (i = 1; i < len - 1; i++) 640 if (buflist->bs_children[i]->b_blkno != blkno + (i * ssize)) 641 panic("ffs_reallocblks: non-physical cluster %d", i); 642 #endif 643 /* 644 * If the latest allocation is in a new cylinder group, assume that 645 * the filesystem has decided to move and do not force it back to 646 * the previous cylinder group. 647 */ 648 if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) != 649 dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno))) 650 return (ENOSPC); 651 if (ufs_getlbns(vp, start_lbn, start_ap, &start_lvl) || 652 ufs_getlbns(vp, end_lbn, end_ap, &end_lvl)) 653 return (ENOSPC); 654 /* 655 * Get the starting offset and block map for the first block. 656 */ 657 if (start_lvl == 0) { 658 sbap = &ip->i_din2->di_db[0]; 659 soff = start_lbn; 660 } else { 661 idp = &start_ap[start_lvl - 1]; 662 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &sbp)) { 663 brelse(sbp); 664 return (ENOSPC); 665 } 666 sbap = (ufs2_daddr_t *)sbp->b_data; 667 soff = idp->in_off; 668 } 669 /* 670 * Find the preferred location for the cluster. 671 */ 672 pref = ffs_blkpref_ufs2(ip, start_lbn, soff, sbap); 673 /* 674 * If the block range spans two block maps, get the second map. 675 */ 676 if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) { 677 ssize = len; 678 } else { 679 #ifdef DIAGNOSTIC 680 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn) 681 panic("ffs_reallocblk: start == end"); 682 #endif 683 ssize = len - (idp->in_off + 1); 684 if (bread(vp, idp->in_lbn, (int)fs->fs_bsize, NOCRED, &ebp)) 685 goto fail; 686 ebap = (ufs2_daddr_t *)ebp->b_data; 687 } 688 /* 689 * Search the block map looking for an allocation of the desired size. 690 */ 691 if ((newblk = ffs_hashalloc(ip, dtog(fs, pref), pref, 692 len, ffs_clusteralloc)) == 0) 693 goto fail; 694 /* 695 * We have found a new contiguous block. 696 * 697 * First we have to replace the old block pointers with the new 698 * block pointers in the inode and indirect blocks associated 699 * with the file. 700 */ 701 #ifdef DEBUG 702 if (prtrealloc) 703 printf("realloc: ino %d, lbns %jd-%jd\n\told:", ip->i_number, 704 (intmax_t)start_lbn, (intmax_t)end_lbn); 705 #endif 706 blkno = newblk; 707 for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->fs_frag) { 708 if (i == ssize) { 709 bap = ebap; 710 soff = -i; 711 } 712 #ifdef DIAGNOSTIC 713 if (!ffs_checkblk(ip, 714 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 715 panic("ffs_reallocblks: unallocated block 2"); 716 if (dbtofsb(fs, buflist->bs_children[i]->b_blkno) != *bap) 717 panic("ffs_reallocblks: alloc mismatch"); 718 #endif 719 #ifdef DEBUG 720 if (prtrealloc) 721 printf(" %jd,", (intmax_t)*bap); 722 #endif 723 if (DOINGSOFTDEP(vp)) { 724 if (sbap == &ip->i_din2->di_db[0] && i < ssize) 725 softdep_setup_allocdirect(ip, start_lbn + i, 726 blkno, *bap, fs->fs_bsize, fs->fs_bsize, 727 buflist->bs_children[i]); 728 else 729 softdep_setup_allocindir_page(ip, start_lbn + i, 730 i < ssize ? sbp : ebp, soff + i, blkno, 731 *bap, buflist->bs_children[i]); 732 } 733 *bap++ = blkno; 734 } 735 /* 736 * Next we must write out the modified inode and indirect blocks. 737 * For strict correctness, the writes should be synchronous since 738 * the old block values may have been written to disk. In practise 739 * they are almost never written, but if we are concerned about 740 * strict correctness, the `doasyncfree' flag should be set to zero. 741 * 742 * The test on `doasyncfree' should be changed to test a flag 743 * that shows whether the associated buffers and inodes have 744 * been written. The flag should be set when the cluster is 745 * started and cleared whenever the buffer or inode is flushed. 746 * We can then check below to see if it is set, and do the 747 * synchronous write only when it has been cleared. 748 */ 749 if (sbap != &ip->i_din2->di_db[0]) { 750 if (doasyncfree) 751 bdwrite(sbp); 752 else 753 bwrite(sbp); 754 } else { 755 ip->i_flag |= IN_CHANGE | IN_UPDATE; 756 if (!doasyncfree) 757 UFS_UPDATE(vp, 1); 758 } 759 if (ssize < len) { 760 if (doasyncfree) 761 bdwrite(ebp); 762 else 763 bwrite(ebp); 764 } 765 /* 766 * Last, free the old blocks and assign the new blocks to the buffers. 767 */ 768 #ifdef DEBUG 769 if (prtrealloc) 770 printf("\n\tnew:"); 771 #endif 772 for (blkno = newblk, i = 0; i < len; i++, blkno += fs->fs_frag) { 773 if (!DOINGSOFTDEP(vp)) 774 ffs_blkfree(fs, ip->i_devvp, 775 dbtofsb(fs, buflist->bs_children[i]->b_blkno), 776 fs->fs_bsize, ip->i_number); 777 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno); 778 #ifdef DIAGNOSTIC 779 if (!ffs_checkblk(ip, 780 dbtofsb(fs, buflist->bs_children[i]->b_blkno), fs->fs_bsize)) 781 panic("ffs_reallocblks: unallocated block 3"); 782 #endif 783 #ifdef DEBUG 784 if (prtrealloc) 785 printf(" %jd,", (intmax_t)blkno); 786 #endif 787 } 788 #ifdef DEBUG 789 if (prtrealloc) { 790 prtrealloc--; 791 printf("\n"); 792 } 793 #endif 794 return (0); 795 796 fail: 797 if (ssize < len) 798 brelse(ebp); 799 if (sbap != &ip->i_din2->di_db[0]) 800 brelse(sbp); 801 return (ENOSPC); 802 } 803 804 /* 805 * Allocate an inode in the filesystem. 806 * 807 * If allocating a directory, use ffs_dirpref to select the inode. 808 * If allocating in a directory, the following hierarchy is followed: 809 * 1) allocate the preferred inode. 810 * 2) allocate an inode in the same cylinder group. 811 * 3) quadradically rehash into other cylinder groups, until an 812 * available inode is located. 813 * If no inode preference is given the following heirarchy is used 814 * to allocate an inode: 815 * 1) allocate an inode in cylinder group 0. 816 * 2) quadradically rehash into other cylinder groups, until an 817 * available inode is located. 818 */ 819 int 820 ffs_valloc(pvp, mode, cred, vpp) 821 struct vnode *pvp; 822 int mode; 823 struct ucred *cred; 824 struct vnode **vpp; 825 { 826 struct inode *pip; 827 struct fs *fs; 828 struct inode *ip; 829 struct timespec ts; 830 ino_t ino, ipref; 831 int cg, error; 832 833 *vpp = NULL; 834 pip = VTOI(pvp); 835 fs = pip->i_fs; 836 if (fs->fs_cstotal.cs_nifree == 0) 837 goto noinodes; 838 839 if ((mode & IFMT) == IFDIR) 840 ipref = ffs_dirpref(pip); 841 else 842 ipref = pip->i_number; 843 if (ipref >= fs->fs_ncg * fs->fs_ipg) 844 ipref = 0; 845 cg = ino_to_cg(fs, ipref); 846 /* 847 * Track number of dirs created one after another 848 * in a same cg without intervening by files. 849 */ 850 if ((mode & IFMT) == IFDIR) { 851 if (fs->fs_contigdirs[cg] < 255) 852 fs->fs_contigdirs[cg]++; 853 } else { 854 if (fs->fs_contigdirs[cg] > 0) 855 fs->fs_contigdirs[cg]--; 856 } 857 ino = (ino_t)ffs_hashalloc(pip, cg, ipref, mode, 858 (allocfcn_t *)ffs_nodealloccg); 859 if (ino == 0) 860 goto noinodes; 861 error = VFS_VGET(pvp->v_mount, ino, LK_EXCLUSIVE, vpp); 862 if (error) { 863 UFS_VFREE(pvp, ino, mode); 864 return (error); 865 } 866 ip = VTOI(*vpp); 867 if (ip->i_mode) { 868 printf("mode = 0%o, inum = %lu, fs = %s\n", 869 ip->i_mode, (u_long)ip->i_number, fs->fs_fsmnt); 870 panic("ffs_valloc: dup alloc"); 871 } 872 if (DIP(ip, i_blocks) && (fs->fs_flags & FS_UNCLEAN) == 0) { /* XXX */ 873 printf("free inode %s/%lu had %ld blocks\n", 874 fs->fs_fsmnt, (u_long)ino, (long)DIP(ip, i_blocks)); 875 DIP(ip, i_blocks) = 0; 876 } 877 ip->i_flags = 0; 878 DIP(ip, i_flags) = 0; 879 /* 880 * Set up a new generation number for this inode. 881 */ 882 if (ip->i_gen == 0 || ++ip->i_gen == 0) 883 ip->i_gen = arc4random() / 2 + 1; 884 DIP(ip, i_gen) = ip->i_gen; 885 if (fs->fs_magic == FS_UFS2_MAGIC) { 886 vfs_timestamp(&ts); 887 ip->i_din2->di_birthtime = ts.tv_sec; 888 ip->i_din2->di_birthnsec = ts.tv_nsec; 889 } 890 return (0); 891 noinodes: 892 ffs_fserr(fs, pip->i_number, "out of inodes"); 893 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 894 return (ENOSPC); 895 } 896 897 /* 898 * Find a cylinder group to place a directory. 899 * 900 * The policy implemented by this algorithm is to allocate a 901 * directory inode in the same cylinder group as its parent 902 * directory, but also to reserve space for its files inodes 903 * and data. Restrict the number of directories which may be 904 * allocated one after another in the same cylinder group 905 * without intervening allocation of files. 906 * 907 * If we allocate a first level directory then force allocation 908 * in another cylinder group. 909 */ 910 static ino_t 911 ffs_dirpref(pip) 912 struct inode *pip; 913 { 914 struct fs *fs; 915 int cg, prefcg, dirsize, cgsize; 916 int avgifree, avgbfree, avgndir, curdirsize; 917 int minifree, minbfree, maxndir; 918 int mincg, minndir; 919 int maxcontigdirs; 920 921 fs = pip->i_fs; 922 923 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 924 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 925 avgndir = fs->fs_cstotal.cs_ndir / fs->fs_ncg; 926 927 /* 928 * Force allocation in another cg if creating a first level dir. 929 */ 930 ASSERT_VOP_LOCKED(ITOV(pip), "ffs_dirpref"); 931 if (ITOV(pip)->v_vflag & VV_ROOT) { 932 prefcg = arc4random() % fs->fs_ncg; 933 mincg = prefcg; 934 minndir = fs->fs_ipg; 935 for (cg = prefcg; cg < fs->fs_ncg; cg++) 936 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 937 fs->fs_cs(fs, cg).cs_nifree >= avgifree && 938 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 939 mincg = cg; 940 minndir = fs->fs_cs(fs, cg).cs_ndir; 941 } 942 for (cg = 0; cg < prefcg; cg++) 943 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 944 fs->fs_cs(fs, cg).cs_nifree >= avgifree && 945 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 946 mincg = cg; 947 minndir = fs->fs_cs(fs, cg).cs_ndir; 948 } 949 return ((ino_t)(fs->fs_ipg * mincg)); 950 } 951 952 /* 953 * Count various limits which used for 954 * optimal allocation of a directory inode. 955 */ 956 maxndir = min(avgndir + fs->fs_ipg / 16, fs->fs_ipg); 957 minifree = avgifree - avgifree / 4; 958 if (minifree < 1) 959 minifree = 1; 960 minbfree = avgbfree - avgbfree / 4; 961 if (minbfree < 1) 962 minbfree = 1; 963 cgsize = fs->fs_fsize * fs->fs_fpg; 964 dirsize = fs->fs_avgfilesize * fs->fs_avgfpdir; 965 curdirsize = avgndir ? (cgsize - avgbfree * fs->fs_bsize) / avgndir : 0; 966 if (dirsize < curdirsize) 967 dirsize = curdirsize; 968 maxcontigdirs = min((avgbfree * fs->fs_bsize) / dirsize, 255); 969 if (fs->fs_avgfpdir > 0) 970 maxcontigdirs = min(maxcontigdirs, 971 fs->fs_ipg / fs->fs_avgfpdir); 972 if (maxcontigdirs == 0) 973 maxcontigdirs = 1; 974 975 /* 976 * Limit number of dirs in one cg and reserve space for 977 * regular files, but only if we have no deficit in 978 * inodes or space. 979 */ 980 prefcg = ino_to_cg(fs, pip->i_number); 981 for (cg = prefcg; cg < fs->fs_ncg; cg++) 982 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 983 fs->fs_cs(fs, cg).cs_nifree >= minifree && 984 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 985 if (fs->fs_contigdirs[cg] < maxcontigdirs) 986 return ((ino_t)(fs->fs_ipg * cg)); 987 } 988 for (cg = 0; cg < prefcg; cg++) 989 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 990 fs->fs_cs(fs, cg).cs_nifree >= minifree && 991 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 992 if (fs->fs_contigdirs[cg] < maxcontigdirs) 993 return ((ino_t)(fs->fs_ipg * cg)); 994 } 995 /* 996 * This is a backstop when we have deficit in space. 997 */ 998 for (cg = prefcg; cg < fs->fs_ncg; cg++) 999 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 1000 return ((ino_t)(fs->fs_ipg * cg)); 1001 for (cg = 0; cg < prefcg; cg++) 1002 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 1003 break; 1004 return ((ino_t)(fs->fs_ipg * cg)); 1005 } 1006 1007 /* 1008 * Select the desired position for the next block in a file. The file is 1009 * logically divided into sections. The first section is composed of the 1010 * direct blocks. Each additional section contains fs_maxbpg blocks. 1011 * 1012 * If no blocks have been allocated in the first section, the policy is to 1013 * request a block in the same cylinder group as the inode that describes 1014 * the file. If no blocks have been allocated in any other section, the 1015 * policy is to place the section in a cylinder group with a greater than 1016 * average number of free blocks. An appropriate cylinder group is found 1017 * by using a rotor that sweeps the cylinder groups. When a new group of 1018 * blocks is needed, the sweep begins in the cylinder group following the 1019 * cylinder group from which the previous allocation was made. The sweep 1020 * continues until a cylinder group with greater than the average number 1021 * of free blocks is found. If the allocation is for the first block in an 1022 * indirect block, the information on the previous allocation is unavailable; 1023 * here a best guess is made based upon the logical block number being 1024 * allocated. 1025 * 1026 * If a section is already partially allocated, the policy is to 1027 * contiguously allocate fs_maxcontig blocks. The end of one of these 1028 * contiguous blocks and the beginning of the next is laid out 1029 * contiguously if possible. 1030 */ 1031 ufs2_daddr_t 1032 ffs_blkpref_ufs1(ip, lbn, indx, bap) 1033 struct inode *ip; 1034 ufs_lbn_t lbn; 1035 int indx; 1036 ufs1_daddr_t *bap; 1037 { 1038 struct fs *fs; 1039 int cg; 1040 int avgbfree, startcg; 1041 1042 fs = ip->i_fs; 1043 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 1044 if (lbn < NDADDR + NINDIR(fs)) { 1045 cg = ino_to_cg(fs, ip->i_number); 1046 return (fs->fs_fpg * cg + fs->fs_frag); 1047 } 1048 /* 1049 * Find a cylinder with greater than average number of 1050 * unused data blocks. 1051 */ 1052 if (indx == 0 || bap[indx - 1] == 0) 1053 startcg = 1054 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 1055 else 1056 startcg = dtog(fs, bap[indx - 1]) + 1; 1057 startcg %= fs->fs_ncg; 1058 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 1059 for (cg = startcg; cg < fs->fs_ncg; cg++) 1060 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 1061 fs->fs_cgrotor = cg; 1062 return (fs->fs_fpg * cg + fs->fs_frag); 1063 } 1064 for (cg = 0; cg <= startcg; cg++) 1065 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 1066 fs->fs_cgrotor = cg; 1067 return (fs->fs_fpg * cg + fs->fs_frag); 1068 } 1069 return (0); 1070 } 1071 /* 1072 * We just always try to lay things out contiguously. 1073 */ 1074 return (bap[indx - 1] + fs->fs_frag); 1075 } 1076 1077 /* 1078 * Same as above, but for UFS2 1079 */ 1080 ufs2_daddr_t 1081 ffs_blkpref_ufs2(ip, lbn, indx, bap) 1082 struct inode *ip; 1083 ufs_lbn_t lbn; 1084 int indx; 1085 ufs2_daddr_t *bap; 1086 { 1087 struct fs *fs; 1088 int cg; 1089 int avgbfree, startcg; 1090 1091 fs = ip->i_fs; 1092 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 1093 if (lbn < NDADDR + NINDIR(fs)) { 1094 cg = ino_to_cg(fs, ip->i_number); 1095 return (fs->fs_fpg * cg + fs->fs_frag); 1096 } 1097 /* 1098 * Find a cylinder with greater than average number of 1099 * unused data blocks. 1100 */ 1101 if (indx == 0 || bap[indx - 1] == 0) 1102 startcg = 1103 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 1104 else 1105 startcg = dtog(fs, bap[indx - 1]) + 1; 1106 startcg %= fs->fs_ncg; 1107 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 1108 for (cg = startcg; cg < fs->fs_ncg; cg++) 1109 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 1110 fs->fs_cgrotor = cg; 1111 return (fs->fs_fpg * cg + fs->fs_frag); 1112 } 1113 for (cg = 0; cg <= startcg; cg++) 1114 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 1115 fs->fs_cgrotor = cg; 1116 return (fs->fs_fpg * cg + fs->fs_frag); 1117 } 1118 return (0); 1119 } 1120 /* 1121 * We just always try to lay things out contiguously. 1122 */ 1123 return (bap[indx - 1] + fs->fs_frag); 1124 } 1125 1126 /* 1127 * Implement the cylinder overflow algorithm. 1128 * 1129 * The policy implemented by this algorithm is: 1130 * 1) allocate the block in its requested cylinder group. 1131 * 2) quadradically rehash on the cylinder group number. 1132 * 3) brute force search for a free block. 1133 */ 1134 /*VARARGS5*/ 1135 static ufs2_daddr_t 1136 ffs_hashalloc(ip, cg, pref, size, allocator) 1137 struct inode *ip; 1138 int cg; 1139 ufs2_daddr_t pref; 1140 int size; /* size for data blocks, mode for inodes */ 1141 allocfcn_t *allocator; 1142 { 1143 struct fs *fs; 1144 ufs2_daddr_t result; 1145 int i, icg = cg; 1146 1147 #ifdef DIAGNOSTIC 1148 if (ITOV(ip)->v_mount->mnt_kern_flag & MNTK_SUSPENDED) 1149 panic("ffs_hashalloc: allocation on suspended filesystem"); 1150 #endif 1151 fs = ip->i_fs; 1152 /* 1153 * 1: preferred cylinder group 1154 */ 1155 result = (*allocator)(ip, cg, pref, size); 1156 if (result) 1157 return (result); 1158 /* 1159 * 2: quadratic rehash 1160 */ 1161 for (i = 1; i < fs->fs_ncg; i *= 2) { 1162 cg += i; 1163 if (cg >= fs->fs_ncg) 1164 cg -= fs->fs_ncg; 1165 result = (*allocator)(ip, cg, 0, size); 1166 if (result) 1167 return (result); 1168 } 1169 /* 1170 * 3: brute force search 1171 * Note that we start at i == 2, since 0 was checked initially, 1172 * and 1 is always checked in the quadratic rehash. 1173 */ 1174 cg = (icg + 2) % fs->fs_ncg; 1175 for (i = 2; i < fs->fs_ncg; i++) { 1176 result = (*allocator)(ip, cg, 0, size); 1177 if (result) 1178 return (result); 1179 cg++; 1180 if (cg == fs->fs_ncg) 1181 cg = 0; 1182 } 1183 return (0); 1184 } 1185 1186 /* 1187 * Determine whether a fragment can be extended. 1188 * 1189 * Check to see if the necessary fragments are available, and 1190 * if they are, allocate them. 1191 */ 1192 static ufs2_daddr_t 1193 ffs_fragextend(ip, cg, bprev, osize, nsize) 1194 struct inode *ip; 1195 int cg; 1196 ufs2_daddr_t bprev; 1197 int osize, nsize; 1198 { 1199 struct fs *fs; 1200 struct cg *cgp; 1201 struct buf *bp; 1202 long bno; 1203 int frags, bbase; 1204 int i, error; 1205 u_int8_t *blksfree; 1206 1207 fs = ip->i_fs; 1208 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 1209 return (0); 1210 frags = numfrags(fs, nsize); 1211 bbase = fragnum(fs, bprev); 1212 if (bbase > fragnum(fs, (bprev + frags - 1))) { 1213 /* cannot extend across a block boundary */ 1214 return (0); 1215 } 1216 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1217 (int)fs->fs_cgsize, NOCRED, &bp); 1218 if (error) { 1219 brelse(bp); 1220 return (0); 1221 } 1222 cgp = (struct cg *)bp->b_data; 1223 if (!cg_chkmagic(cgp)) { 1224 brelse(bp); 1225 return (0); 1226 } 1227 bp->b_xflags |= BX_BKGRDWRITE; 1228 cgp->cg_old_time = cgp->cg_time = time_second; 1229 bno = dtogd(fs, bprev); 1230 blksfree = cg_blksfree(cgp); 1231 for (i = numfrags(fs, osize); i < frags; i++) 1232 if (isclr(blksfree, bno + i)) { 1233 brelse(bp); 1234 return (0); 1235 } 1236 /* 1237 * the current fragment can be extended 1238 * deduct the count on fragment being extended into 1239 * increase the count on the remaining fragment (if any) 1240 * allocate the extended piece 1241 */ 1242 for (i = frags; i < fs->fs_frag - bbase; i++) 1243 if (isclr(blksfree, bno + i)) 1244 break; 1245 cgp->cg_frsum[i - numfrags(fs, osize)]--; 1246 if (i != frags) 1247 cgp->cg_frsum[i - frags]++; 1248 for (i = numfrags(fs, osize); i < frags; i++) { 1249 clrbit(blksfree, bno + i); 1250 cgp->cg_cs.cs_nffree--; 1251 fs->fs_cstotal.cs_nffree--; 1252 fs->fs_cs(fs, cg).cs_nffree--; 1253 } 1254 fs->fs_fmod = 1; 1255 if (DOINGSOFTDEP(ITOV(ip))) 1256 softdep_setup_blkmapdep(bp, fs, bprev); 1257 if (fs->fs_active != 0) 1258 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1259 bdwrite(bp); 1260 return (bprev); 1261 } 1262 1263 /* 1264 * Determine whether a block can be allocated. 1265 * 1266 * Check to see if a block of the appropriate size is available, 1267 * and if it is, allocate it. 1268 */ 1269 static ufs2_daddr_t 1270 ffs_alloccg(ip, cg, bpref, size) 1271 struct inode *ip; 1272 int cg; 1273 ufs2_daddr_t bpref; 1274 int size; 1275 { 1276 struct fs *fs; 1277 struct cg *cgp; 1278 struct buf *bp; 1279 ufs1_daddr_t bno; 1280 ufs2_daddr_t blkno; 1281 int i, allocsiz, error, frags; 1282 u_int8_t *blksfree; 1283 1284 fs = ip->i_fs; 1285 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 1286 return (0); 1287 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1288 (int)fs->fs_cgsize, NOCRED, &bp); 1289 if (error) { 1290 brelse(bp); 1291 return (0); 1292 } 1293 cgp = (struct cg *)bp->b_data; 1294 if (!cg_chkmagic(cgp) || 1295 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) { 1296 brelse(bp); 1297 return (0); 1298 } 1299 bp->b_xflags |= BX_BKGRDWRITE; 1300 cgp->cg_old_time = cgp->cg_time = time_second; 1301 if (size == fs->fs_bsize) { 1302 blkno = ffs_alloccgblk(ip, bp, bpref); 1303 if (fs->fs_active != 0) 1304 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1305 bdwrite(bp); 1306 return (blkno); 1307 } 1308 /* 1309 * check to see if any fragments are already available 1310 * allocsiz is the size which will be allocated, hacking 1311 * it down to a smaller size if necessary 1312 */ 1313 blksfree = cg_blksfree(cgp); 1314 frags = numfrags(fs, size); 1315 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 1316 if (cgp->cg_frsum[allocsiz] != 0) 1317 break; 1318 if (allocsiz == fs->fs_frag) { 1319 /* 1320 * no fragments were available, so a block will be 1321 * allocated, and hacked up 1322 */ 1323 if (cgp->cg_cs.cs_nbfree == 0) { 1324 brelse(bp); 1325 return (0); 1326 } 1327 blkno = ffs_alloccgblk(ip, bp, bpref); 1328 bno = dtogd(fs, blkno); 1329 for (i = frags; i < fs->fs_frag; i++) 1330 setbit(blksfree, bno + i); 1331 i = fs->fs_frag - frags; 1332 cgp->cg_cs.cs_nffree += i; 1333 fs->fs_cstotal.cs_nffree += i; 1334 fs->fs_cs(fs, cg).cs_nffree += i; 1335 fs->fs_fmod = 1; 1336 cgp->cg_frsum[i]++; 1337 if (fs->fs_active != 0) 1338 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1339 bdwrite(bp); 1340 return (blkno); 1341 } 1342 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 1343 if (bno < 0) { 1344 brelse(bp); 1345 return (0); 1346 } 1347 for (i = 0; i < frags; i++) 1348 clrbit(blksfree, bno + i); 1349 cgp->cg_cs.cs_nffree -= frags; 1350 fs->fs_cstotal.cs_nffree -= frags; 1351 fs->fs_cs(fs, cg).cs_nffree -= frags; 1352 fs->fs_fmod = 1; 1353 cgp->cg_frsum[allocsiz]--; 1354 if (frags != allocsiz) 1355 cgp->cg_frsum[allocsiz - frags]++; 1356 blkno = cg * fs->fs_fpg + bno; 1357 if (DOINGSOFTDEP(ITOV(ip))) 1358 softdep_setup_blkmapdep(bp, fs, blkno); 1359 if (fs->fs_active != 0) 1360 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1361 bdwrite(bp); 1362 return (blkno); 1363 } 1364 1365 /* 1366 * Allocate a block in a cylinder group. 1367 * 1368 * This algorithm implements the following policy: 1369 * 1) allocate the requested block. 1370 * 2) allocate a rotationally optimal block in the same cylinder. 1371 * 3) allocate the next available block on the block rotor for the 1372 * specified cylinder group. 1373 * Note that this routine only allocates fs_bsize blocks; these 1374 * blocks may be fragmented by the routine that allocates them. 1375 */ 1376 static ufs2_daddr_t 1377 ffs_alloccgblk(ip, bp, bpref) 1378 struct inode *ip; 1379 struct buf *bp; 1380 ufs2_daddr_t bpref; 1381 { 1382 struct fs *fs; 1383 struct cg *cgp; 1384 ufs1_daddr_t bno; 1385 ufs2_daddr_t blkno; 1386 u_int8_t *blksfree; 1387 1388 fs = ip->i_fs; 1389 cgp = (struct cg *)bp->b_data; 1390 blksfree = cg_blksfree(cgp); 1391 if (bpref == 0 || dtog(fs, bpref) != cgp->cg_cgx) { 1392 bpref = cgp->cg_rotor; 1393 } else { 1394 bpref = blknum(fs, bpref); 1395 bno = dtogd(fs, bpref); 1396 /* 1397 * if the requested block is available, use it 1398 */ 1399 if (ffs_isblock(fs, blksfree, fragstoblks(fs, bno))) 1400 goto gotit; 1401 } 1402 /* 1403 * Take the next available block in this cylinder group. 1404 */ 1405 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 1406 if (bno < 0) 1407 return (0); 1408 cgp->cg_rotor = bno; 1409 gotit: 1410 blkno = fragstoblks(fs, bno); 1411 ffs_clrblock(fs, blksfree, (long)blkno); 1412 ffs_clusteracct(fs, cgp, blkno, -1); 1413 cgp->cg_cs.cs_nbfree--; 1414 fs->fs_cstotal.cs_nbfree--; 1415 fs->fs_cs(fs, cgp->cg_cgx).cs_nbfree--; 1416 fs->fs_fmod = 1; 1417 blkno = cgp->cg_cgx * fs->fs_fpg + bno; 1418 if (DOINGSOFTDEP(ITOV(ip))) 1419 softdep_setup_blkmapdep(bp, fs, blkno); 1420 return (blkno); 1421 } 1422 1423 /* 1424 * Determine whether a cluster can be allocated. 1425 * 1426 * We do not currently check for optimal rotational layout if there 1427 * are multiple choices in the same cylinder group. Instead we just 1428 * take the first one that we find following bpref. 1429 */ 1430 static ufs2_daddr_t 1431 ffs_clusteralloc(ip, cg, bpref, len) 1432 struct inode *ip; 1433 int cg; 1434 ufs2_daddr_t bpref; 1435 int len; 1436 { 1437 struct fs *fs; 1438 struct cg *cgp; 1439 struct buf *bp; 1440 int i, run, bit, map, got; 1441 ufs2_daddr_t bno; 1442 u_char *mapp; 1443 int32_t *lp; 1444 u_int8_t *blksfree; 1445 1446 fs = ip->i_fs; 1447 if (fs->fs_maxcluster[cg] < len) 1448 return (0); 1449 if (bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), (int)fs->fs_cgsize, 1450 NOCRED, &bp)) 1451 goto fail; 1452 cgp = (struct cg *)bp->b_data; 1453 if (!cg_chkmagic(cgp)) 1454 goto fail; 1455 bp->b_xflags |= BX_BKGRDWRITE; 1456 /* 1457 * Check to see if a cluster of the needed size (or bigger) is 1458 * available in this cylinder group. 1459 */ 1460 lp = &cg_clustersum(cgp)[len]; 1461 for (i = len; i <= fs->fs_contigsumsize; i++) 1462 if (*lp++ > 0) 1463 break; 1464 if (i > fs->fs_contigsumsize) { 1465 /* 1466 * This is the first time looking for a cluster in this 1467 * cylinder group. Update the cluster summary information 1468 * to reflect the true maximum sized cluster so that 1469 * future cluster allocation requests can avoid reading 1470 * the cylinder group map only to find no clusters. 1471 */ 1472 lp = &cg_clustersum(cgp)[len - 1]; 1473 for (i = len - 1; i > 0; i--) 1474 if (*lp-- > 0) 1475 break; 1476 fs->fs_maxcluster[cg] = i; 1477 goto fail; 1478 } 1479 /* 1480 * Search the cluster map to find a big enough cluster. 1481 * We take the first one that we find, even if it is larger 1482 * than we need as we prefer to get one close to the previous 1483 * block allocation. We do not search before the current 1484 * preference point as we do not want to allocate a block 1485 * that is allocated before the previous one (as we will 1486 * then have to wait for another pass of the elevator 1487 * algorithm before it will be read). We prefer to fail and 1488 * be recalled to try an allocation in the next cylinder group. 1489 */ 1490 if (dtog(fs, bpref) != cg) 1491 bpref = 0; 1492 else 1493 bpref = fragstoblks(fs, dtogd(fs, blknum(fs, bpref))); 1494 mapp = &cg_clustersfree(cgp)[bpref / NBBY]; 1495 map = *mapp++; 1496 bit = 1 << (bpref % NBBY); 1497 for (run = 0, got = bpref; got < cgp->cg_nclusterblks; got++) { 1498 if ((map & bit) == 0) { 1499 run = 0; 1500 } else { 1501 run++; 1502 if (run == len) 1503 break; 1504 } 1505 if ((got & (NBBY - 1)) != (NBBY - 1)) { 1506 bit <<= 1; 1507 } else { 1508 map = *mapp++; 1509 bit = 1; 1510 } 1511 } 1512 if (got >= cgp->cg_nclusterblks) 1513 goto fail; 1514 /* 1515 * Allocate the cluster that we have found. 1516 */ 1517 blksfree = cg_blksfree(cgp); 1518 for (i = 1; i <= len; i++) 1519 if (!ffs_isblock(fs, blksfree, got - run + i)) 1520 panic("ffs_clusteralloc: map mismatch"); 1521 bno = cg * fs->fs_fpg + blkstofrags(fs, got - run + 1); 1522 if (dtog(fs, bno) != cg) 1523 panic("ffs_clusteralloc: allocated out of group"); 1524 len = blkstofrags(fs, len); 1525 for (i = 0; i < len; i += fs->fs_frag) 1526 if (ffs_alloccgblk(ip, bp, bno + i) != bno + i) 1527 panic("ffs_clusteralloc: lost block"); 1528 if (fs->fs_active != 0) 1529 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1530 bdwrite(bp); 1531 return (bno); 1532 1533 fail: 1534 brelse(bp); 1535 return (0); 1536 } 1537 1538 /* 1539 * Determine whether an inode can be allocated. 1540 * 1541 * Check to see if an inode is available, and if it is, 1542 * allocate it using the following policy: 1543 * 1) allocate the requested inode. 1544 * 2) allocate the next available inode after the requested 1545 * inode in the specified cylinder group. 1546 */ 1547 static ufs2_daddr_t 1548 ffs_nodealloccg(ip, cg, ipref, mode) 1549 struct inode *ip; 1550 int cg; 1551 ufs2_daddr_t ipref; 1552 int mode; 1553 { 1554 struct fs *fs; 1555 struct cg *cgp; 1556 struct buf *bp, *ibp; 1557 u_int8_t *inosused; 1558 struct ufs2_dinode *dp2; 1559 int error, start, len, loc, map, i; 1560 1561 fs = ip->i_fs; 1562 if (fs->fs_cs(fs, cg).cs_nifree == 0) 1563 return (0); 1564 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1565 (int)fs->fs_cgsize, NOCRED, &bp); 1566 if (error) { 1567 brelse(bp); 1568 return (0); 1569 } 1570 cgp = (struct cg *)bp->b_data; 1571 if (!cg_chkmagic(cgp) || cgp->cg_cs.cs_nifree == 0) { 1572 brelse(bp); 1573 return (0); 1574 } 1575 bp->b_xflags |= BX_BKGRDWRITE; 1576 cgp->cg_old_time = cgp->cg_time = time_second; 1577 inosused = cg_inosused(cgp); 1578 if (ipref) { 1579 ipref %= fs->fs_ipg; 1580 if (isclr(inosused, ipref)) 1581 goto gotit; 1582 } 1583 start = cgp->cg_irotor / NBBY; 1584 len = howmany(fs->fs_ipg - cgp->cg_irotor, NBBY); 1585 loc = skpc(0xff, len, &inosused[start]); 1586 if (loc == 0) { 1587 len = start + 1; 1588 start = 0; 1589 loc = skpc(0xff, len, &inosused[0]); 1590 if (loc == 0) { 1591 printf("cg = %d, irotor = %ld, fs = %s\n", 1592 cg, (long)cgp->cg_irotor, fs->fs_fsmnt); 1593 panic("ffs_nodealloccg: map corrupted"); 1594 /* NOTREACHED */ 1595 } 1596 } 1597 i = start + len - loc; 1598 map = inosused[i]; 1599 ipref = i * NBBY; 1600 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 1601 if ((map & i) == 0) { 1602 cgp->cg_irotor = ipref; 1603 goto gotit; 1604 } 1605 } 1606 printf("fs = %s\n", fs->fs_fsmnt); 1607 panic("ffs_nodealloccg: block not in map"); 1608 /* NOTREACHED */ 1609 gotit: 1610 if (DOINGSOFTDEP(ITOV(ip))) 1611 softdep_setup_inomapdep(bp, ip, cg * fs->fs_ipg + ipref); 1612 setbit(inosused, ipref); 1613 cgp->cg_cs.cs_nifree--; 1614 fs->fs_cstotal.cs_nifree--; 1615 fs->fs_cs(fs, cg).cs_nifree--; 1616 fs->fs_fmod = 1; 1617 if ((mode & IFMT) == IFDIR) { 1618 cgp->cg_cs.cs_ndir++; 1619 fs->fs_cstotal.cs_ndir++; 1620 fs->fs_cs(fs, cg).cs_ndir++; 1621 } 1622 /* 1623 * Check to see if we need to initialize more inodes. 1624 */ 1625 if (fs->fs_magic == FS_UFS2_MAGIC && 1626 ipref + INOPB(fs) > cgp->cg_initediblk && 1627 cgp->cg_initediblk < cgp->cg_niblk) { 1628 ibp = getblk(ip->i_devvp, fsbtodb(fs, 1629 ino_to_fsba(fs, cg * fs->fs_ipg + cgp->cg_initediblk)), 1630 (int)fs->fs_bsize, 0, 0, 0); 1631 bzero(ibp->b_data, (int)fs->fs_bsize); 1632 dp2 = (struct ufs2_dinode *)(ibp->b_data); 1633 for (i = 0; i < INOPB(fs); i++) { 1634 dp2->di_gen = arc4random() / 2 + 1; 1635 dp2++; 1636 } 1637 bawrite(ibp); 1638 cgp->cg_initediblk += INOPB(fs); 1639 } 1640 if (fs->fs_active != 0) 1641 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1642 bdwrite(bp); 1643 return (cg * fs->fs_ipg + ipref); 1644 } 1645 1646 /* 1647 * check if a block is free 1648 */ 1649 static int 1650 ffs_isfreeblock(struct fs *fs, u_char *cp, ufs1_daddr_t h) 1651 { 1652 1653 switch ((int)fs->fs_frag) { 1654 case 8: 1655 return (cp[h] == 0); 1656 case 4: 1657 return ((cp[h >> 1] & (0x0f << ((h & 0x1) << 2))) == 0); 1658 case 2: 1659 return ((cp[h >> 2] & (0x03 << ((h & 0x3) << 1))) == 0); 1660 case 1: 1661 return ((cp[h >> 3] & (0x01 << (h & 0x7))) == 0); 1662 default: 1663 panic("ffs_isfreeblock"); 1664 } 1665 return (0); 1666 } 1667 1668 /* 1669 * Free a block or fragment. 1670 * 1671 * The specified block or fragment is placed back in the 1672 * free map. If a fragment is deallocated, a possible 1673 * block reassembly is checked. 1674 */ 1675 void 1676 ffs_blkfree(fs, devvp, bno, size, inum) 1677 struct fs *fs; 1678 struct vnode *devvp; 1679 ufs2_daddr_t bno; 1680 long size; 1681 ino_t inum; 1682 { 1683 struct cg *cgp; 1684 struct buf *bp; 1685 ufs1_daddr_t fragno, cgbno; 1686 ufs2_daddr_t cgblkno; 1687 int i, cg, blk, frags, bbase; 1688 u_int8_t *blksfree; 1689 dev_t dev; 1690 1691 cg = dtog(fs, bno); 1692 if (devvp->v_type != VCHR) { 1693 /* devvp is a snapshot */ 1694 dev = VTOI(devvp)->i_devvp->v_rdev; 1695 cgblkno = fragstoblks(fs, cgtod(fs, cg)); 1696 } else { 1697 /* devvp is a normal disk device */ 1698 dev = devvp->v_rdev; 1699 cgblkno = fsbtodb(fs, cgtod(fs, cg)); 1700 ASSERT_VOP_LOCKED(devvp, "ffs_blkfree"); 1701 if ((devvp->v_vflag & VV_COPYONWRITE) && 1702 ffs_snapblkfree(fs, devvp, bno, size, inum)) 1703 return; 1704 VOP_FREEBLKS(devvp, fsbtodb(fs, bno), size); 1705 } 1706 #ifdef DIAGNOSTIC 1707 if (dev->si_mountpoint && 1708 (dev->si_mountpoint->mnt_kern_flag & MNTK_SUSPENDED)) 1709 panic("ffs_blkfree: deallocation on suspended filesystem"); 1710 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0 || 1711 fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) { 1712 printf("dev=%s, bno = %jd, bsize = %ld, size = %ld, fs = %s\n", 1713 devtoname(dev), (intmax_t)bno, (long)fs->fs_bsize, 1714 size, fs->fs_fsmnt); 1715 panic("ffs_blkfree: bad size"); 1716 } 1717 #endif 1718 if ((u_int)bno >= fs->fs_size) { 1719 printf("bad block %jd, ino %lu\n", (intmax_t)bno, 1720 (u_long)inum); 1721 ffs_fserr(fs, inum, "bad block"); 1722 return; 1723 } 1724 if (bread(devvp, cgblkno, (int)fs->fs_cgsize, NOCRED, &bp)) { 1725 brelse(bp); 1726 return; 1727 } 1728 cgp = (struct cg *)bp->b_data; 1729 if (!cg_chkmagic(cgp)) { 1730 brelse(bp); 1731 return; 1732 } 1733 bp->b_xflags |= BX_BKGRDWRITE; 1734 cgp->cg_old_time = cgp->cg_time = time_second; 1735 cgbno = dtogd(fs, bno); 1736 blksfree = cg_blksfree(cgp); 1737 if (size == fs->fs_bsize) { 1738 fragno = fragstoblks(fs, cgbno); 1739 if (!ffs_isfreeblock(fs, blksfree, fragno)) { 1740 if (devvp->v_type != VCHR) { 1741 /* devvp is a snapshot */ 1742 brelse(bp); 1743 return; 1744 } 1745 printf("dev = %s, block = %jd, fs = %s\n", 1746 devtoname(dev), (intmax_t)bno, fs->fs_fsmnt); 1747 panic("ffs_blkfree: freeing free block"); 1748 } 1749 ffs_setblock(fs, blksfree, fragno); 1750 ffs_clusteracct(fs, cgp, fragno, 1); 1751 cgp->cg_cs.cs_nbfree++; 1752 fs->fs_cstotal.cs_nbfree++; 1753 fs->fs_cs(fs, cg).cs_nbfree++; 1754 } else { 1755 bbase = cgbno - fragnum(fs, cgbno); 1756 /* 1757 * decrement the counts associated with the old frags 1758 */ 1759 blk = blkmap(fs, blksfree, bbase); 1760 ffs_fragacct(fs, blk, cgp->cg_frsum, -1); 1761 /* 1762 * deallocate the fragment 1763 */ 1764 frags = numfrags(fs, size); 1765 for (i = 0; i < frags; i++) { 1766 if (isset(blksfree, cgbno + i)) { 1767 printf("dev = %s, block = %jd, fs = %s\n", 1768 devtoname(dev), (intmax_t)(bno + i), 1769 fs->fs_fsmnt); 1770 panic("ffs_blkfree: freeing free frag"); 1771 } 1772 setbit(blksfree, cgbno + i); 1773 } 1774 cgp->cg_cs.cs_nffree += i; 1775 fs->fs_cstotal.cs_nffree += i; 1776 fs->fs_cs(fs, cg).cs_nffree += i; 1777 /* 1778 * add back in counts associated with the new frags 1779 */ 1780 blk = blkmap(fs, blksfree, bbase); 1781 ffs_fragacct(fs, blk, cgp->cg_frsum, 1); 1782 /* 1783 * if a complete block has been reassembled, account for it 1784 */ 1785 fragno = fragstoblks(fs, bbase); 1786 if (ffs_isblock(fs, blksfree, fragno)) { 1787 cgp->cg_cs.cs_nffree -= fs->fs_frag; 1788 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 1789 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 1790 ffs_clusteracct(fs, cgp, fragno, 1); 1791 cgp->cg_cs.cs_nbfree++; 1792 fs->fs_cstotal.cs_nbfree++; 1793 fs->fs_cs(fs, cg).cs_nbfree++; 1794 } 1795 } 1796 fs->fs_fmod = 1; 1797 if (fs->fs_active != 0) 1798 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1799 bdwrite(bp); 1800 } 1801 1802 #ifdef DIAGNOSTIC 1803 /* 1804 * Verify allocation of a block or fragment. Returns true if block or 1805 * fragment is allocated, false if it is free. 1806 */ 1807 static int 1808 ffs_checkblk(ip, bno, size) 1809 struct inode *ip; 1810 ufs2_daddr_t bno; 1811 long size; 1812 { 1813 struct fs *fs; 1814 struct cg *cgp; 1815 struct buf *bp; 1816 ufs1_daddr_t cgbno; 1817 int i, error, frags, free; 1818 u_int8_t *blksfree; 1819 1820 fs = ip->i_fs; 1821 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 1822 printf("bsize = %ld, size = %ld, fs = %s\n", 1823 (long)fs->fs_bsize, size, fs->fs_fsmnt); 1824 panic("ffs_checkblk: bad size"); 1825 } 1826 if ((u_int)bno >= fs->fs_size) 1827 panic("ffs_checkblk: bad block %jd", (intmax_t)bno); 1828 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, dtog(fs, bno))), 1829 (int)fs->fs_cgsize, NOCRED, &bp); 1830 if (error) 1831 panic("ffs_checkblk: cg bread failed"); 1832 cgp = (struct cg *)bp->b_data; 1833 if (!cg_chkmagic(cgp)) 1834 panic("ffs_checkblk: cg magic mismatch"); 1835 bp->b_xflags |= BX_BKGRDWRITE; 1836 blksfree = cg_blksfree(cgp); 1837 cgbno = dtogd(fs, bno); 1838 if (size == fs->fs_bsize) { 1839 free = ffs_isblock(fs, blksfree, fragstoblks(fs, cgbno)); 1840 } else { 1841 frags = numfrags(fs, size); 1842 for (free = 0, i = 0; i < frags; i++) 1843 if (isset(blksfree, cgbno + i)) 1844 free++; 1845 if (free != 0 && free != frags) 1846 panic("ffs_checkblk: partially free fragment"); 1847 } 1848 brelse(bp); 1849 return (!free); 1850 } 1851 #endif /* DIAGNOSTIC */ 1852 1853 /* 1854 * Free an inode. 1855 */ 1856 int 1857 ffs_vfree(pvp, ino, mode) 1858 struct vnode *pvp; 1859 ino_t ino; 1860 int mode; 1861 { 1862 if (DOINGSOFTDEP(pvp)) { 1863 softdep_freefile(pvp, ino, mode); 1864 return (0); 1865 } 1866 return (ffs_freefile(VTOI(pvp)->i_fs, VTOI(pvp)->i_devvp, ino, mode)); 1867 } 1868 1869 /* 1870 * Do the actual free operation. 1871 * The specified inode is placed back in the free map. 1872 */ 1873 int 1874 ffs_freefile(fs, devvp, ino, mode) 1875 struct fs *fs; 1876 struct vnode *devvp; 1877 ino_t ino; 1878 int mode; 1879 { 1880 struct cg *cgp; 1881 struct buf *bp; 1882 ufs2_daddr_t cgbno; 1883 int error, cg; 1884 u_int8_t *inosused; 1885 dev_t dev; 1886 1887 cg = ino_to_cg(fs, ino); 1888 if (devvp->v_type != VCHR) { 1889 /* devvp is a snapshot */ 1890 dev = VTOI(devvp)->i_devvp->v_rdev; 1891 cgbno = fragstoblks(fs, cgtod(fs, cg)); 1892 } else { 1893 /* devvp is a normal disk device */ 1894 dev = devvp->v_rdev; 1895 cgbno = fsbtodb(fs, cgtod(fs, cg)); 1896 } 1897 if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 1898 panic("ffs_freefile: range: dev = %s, ino = %lu, fs = %s", 1899 devtoname(dev), (u_long)ino, fs->fs_fsmnt); 1900 if ((error = bread(devvp, cgbno, (int)fs->fs_cgsize, NOCRED, &bp))) { 1901 brelse(bp); 1902 return (error); 1903 } 1904 cgp = (struct cg *)bp->b_data; 1905 if (!cg_chkmagic(cgp)) { 1906 brelse(bp); 1907 return (0); 1908 } 1909 bp->b_xflags |= BX_BKGRDWRITE; 1910 cgp->cg_old_time = cgp->cg_time = time_second; 1911 inosused = cg_inosused(cgp); 1912 ino %= fs->fs_ipg; 1913 if (isclr(inosused, ino)) { 1914 printf("dev = %s, ino = %lu, fs = %s\n", devtoname(dev), 1915 (u_long)ino + cg * fs->fs_ipg, fs->fs_fsmnt); 1916 if (fs->fs_ronly == 0) 1917 panic("ffs_freefile: freeing free inode"); 1918 } 1919 clrbit(inosused, ino); 1920 if (ino < cgp->cg_irotor) 1921 cgp->cg_irotor = ino; 1922 cgp->cg_cs.cs_nifree++; 1923 fs->fs_cstotal.cs_nifree++; 1924 fs->fs_cs(fs, cg).cs_nifree++; 1925 if ((mode & IFMT) == IFDIR) { 1926 cgp->cg_cs.cs_ndir--; 1927 fs->fs_cstotal.cs_ndir--; 1928 fs->fs_cs(fs, cg).cs_ndir--; 1929 } 1930 fs->fs_fmod = 1; 1931 if (fs->fs_active != 0) 1932 atomic_clear_int(&ACTIVECGNUM(fs, cg), ACTIVECGOFF(cg)); 1933 bdwrite(bp); 1934 return (0); 1935 } 1936 1937 /* 1938 * Check to see if a file is free. 1939 */ 1940 int 1941 ffs_checkfreefile(fs, devvp, ino) 1942 struct fs *fs; 1943 struct vnode *devvp; 1944 ino_t ino; 1945 { 1946 struct cg *cgp; 1947 struct buf *bp; 1948 ufs2_daddr_t cgbno; 1949 int ret, cg; 1950 u_int8_t *inosused; 1951 1952 cg = ino_to_cg(fs, ino); 1953 if (devvp->v_type != VCHR) { 1954 /* devvp is a snapshot */ 1955 cgbno = fragstoblks(fs, cgtod(fs, cg)); 1956 } else { 1957 /* devvp is a normal disk device */ 1958 cgbno = fsbtodb(fs, cgtod(fs, cg)); 1959 } 1960 if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 1961 return (1); 1962 if (bread(devvp, cgbno, (int)fs->fs_cgsize, NOCRED, &bp)) { 1963 brelse(bp); 1964 return (1); 1965 } 1966 cgp = (struct cg *)bp->b_data; 1967 if (!cg_chkmagic(cgp)) { 1968 brelse(bp); 1969 return (1); 1970 } 1971 inosused = cg_inosused(cgp); 1972 ino %= fs->fs_ipg; 1973 ret = isclr(inosused, ino); 1974 brelse(bp); 1975 return (ret); 1976 } 1977 1978 /* 1979 * Find a block of the specified size in the specified cylinder group. 1980 * 1981 * It is a panic if a request is made to find a block if none are 1982 * available. 1983 */ 1984 static ufs1_daddr_t 1985 ffs_mapsearch(fs, cgp, bpref, allocsiz) 1986 struct fs *fs; 1987 struct cg *cgp; 1988 ufs2_daddr_t bpref; 1989 int allocsiz; 1990 { 1991 ufs1_daddr_t bno; 1992 int start, len, loc, i; 1993 int blk, field, subfield, pos; 1994 u_int8_t *blksfree; 1995 1996 /* 1997 * find the fragment by searching through the free block 1998 * map for an appropriate bit pattern 1999 */ 2000 if (bpref) 2001 start = dtogd(fs, bpref) / NBBY; 2002 else 2003 start = cgp->cg_frotor / NBBY; 2004 blksfree = cg_blksfree(cgp); 2005 len = howmany(fs->fs_fpg, NBBY) - start; 2006 loc = scanc((u_int)len, (u_char *)&blksfree[start], 2007 (u_char *)fragtbl[fs->fs_frag], 2008 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 2009 if (loc == 0) { 2010 len = start + 1; 2011 start = 0; 2012 loc = scanc((u_int)len, (u_char *)&blksfree[0], 2013 (u_char *)fragtbl[fs->fs_frag], 2014 (u_char)(1 << (allocsiz - 1 + (fs->fs_frag % NBBY)))); 2015 if (loc == 0) { 2016 printf("start = %d, len = %d, fs = %s\n", 2017 start, len, fs->fs_fsmnt); 2018 panic("ffs_alloccg: map corrupted"); 2019 /* NOTREACHED */ 2020 } 2021 } 2022 bno = (start + len - loc) * NBBY; 2023 cgp->cg_frotor = bno; 2024 /* 2025 * found the byte in the map 2026 * sift through the bits to find the selected frag 2027 */ 2028 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 2029 blk = blkmap(fs, blksfree, bno); 2030 blk <<= 1; 2031 field = around[allocsiz]; 2032 subfield = inside[allocsiz]; 2033 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 2034 if ((blk & field) == subfield) 2035 return (bno + pos); 2036 field <<= 1; 2037 subfield <<= 1; 2038 } 2039 } 2040 printf("bno = %lu, fs = %s\n", (u_long)bno, fs->fs_fsmnt); 2041 panic("ffs_alloccg: block not in map"); 2042 return (-1); 2043 } 2044 2045 /* 2046 * Update the cluster map because of an allocation or free. 2047 * 2048 * Cnt == 1 means free; cnt == -1 means allocating. 2049 */ 2050 void 2051 ffs_clusteracct(fs, cgp, blkno, cnt) 2052 struct fs *fs; 2053 struct cg *cgp; 2054 ufs1_daddr_t blkno; 2055 int cnt; 2056 { 2057 int32_t *sump; 2058 int32_t *lp; 2059 u_char *freemapp, *mapp; 2060 int i, start, end, forw, back, map, bit; 2061 2062 if (fs->fs_contigsumsize <= 0) 2063 return; 2064 freemapp = cg_clustersfree(cgp); 2065 sump = cg_clustersum(cgp); 2066 /* 2067 * Allocate or clear the actual block. 2068 */ 2069 if (cnt > 0) 2070 setbit(freemapp, blkno); 2071 else 2072 clrbit(freemapp, blkno); 2073 /* 2074 * Find the size of the cluster going forward. 2075 */ 2076 start = blkno + 1; 2077 end = start + fs->fs_contigsumsize; 2078 if (end >= cgp->cg_nclusterblks) 2079 end = cgp->cg_nclusterblks; 2080 mapp = &freemapp[start / NBBY]; 2081 map = *mapp++; 2082 bit = 1 << (start % NBBY); 2083 for (i = start; i < end; i++) { 2084 if ((map & bit) == 0) 2085 break; 2086 if ((i & (NBBY - 1)) != (NBBY - 1)) { 2087 bit <<= 1; 2088 } else { 2089 map = *mapp++; 2090 bit = 1; 2091 } 2092 } 2093 forw = i - start; 2094 /* 2095 * Find the size of the cluster going backward. 2096 */ 2097 start = blkno - 1; 2098 end = start - fs->fs_contigsumsize; 2099 if (end < 0) 2100 end = -1; 2101 mapp = &freemapp[start / NBBY]; 2102 map = *mapp--; 2103 bit = 1 << (start % NBBY); 2104 for (i = start; i > end; i--) { 2105 if ((map & bit) == 0) 2106 break; 2107 if ((i & (NBBY - 1)) != 0) { 2108 bit >>= 1; 2109 } else { 2110 map = *mapp--; 2111 bit = 1 << (NBBY - 1); 2112 } 2113 } 2114 back = start - i; 2115 /* 2116 * Account for old cluster and the possibly new forward and 2117 * back clusters. 2118 */ 2119 i = back + forw + 1; 2120 if (i > fs->fs_contigsumsize) 2121 i = fs->fs_contigsumsize; 2122 sump[i] += cnt; 2123 if (back > 0) 2124 sump[back] -= cnt; 2125 if (forw > 0) 2126 sump[forw] -= cnt; 2127 /* 2128 * Update cluster summary information. 2129 */ 2130 lp = &sump[fs->fs_contigsumsize]; 2131 for (i = fs->fs_contigsumsize; i > 0; i--) 2132 if (*lp-- > 0) 2133 break; 2134 fs->fs_maxcluster[cgp->cg_cgx] = i; 2135 } 2136 2137 /* 2138 * Fserr prints the name of a filesystem with an error diagnostic. 2139 * 2140 * The form of the error message is: 2141 * fs: error message 2142 */ 2143 static void 2144 ffs_fserr(fs, inum, cp) 2145 struct fs *fs; 2146 ino_t inum; 2147 char *cp; 2148 { 2149 struct thread *td = curthread; /* XXX */ 2150 struct proc *p = td->td_proc; 2151 2152 log(LOG_ERR, "pid %d (%s), uid %d inumber %d on %s: %s\n", 2153 p->p_pid, p->p_comm, td->td_ucred->cr_uid, inum, fs->fs_fsmnt, cp); 2154 } 2155 2156 /* 2157 * This function provides the capability for the fsck program to 2158 * update an active filesystem. Six operations are provided: 2159 * 2160 * adjrefcnt(inode, amt) - adjusts the reference count on the 2161 * specified inode by the specified amount. Under normal 2162 * operation the count should always go down. Decrementing 2163 * the count to zero will cause the inode to be freed. 2164 * adjblkcnt(inode, amt) - adjust the number of blocks used to 2165 * by the specifed amount. 2166 * freedirs(inode, count) - directory inodes [inode..inode + count - 1] 2167 * are marked as free. Inodes should never have to be marked 2168 * as in use. 2169 * freefiles(inode, count) - file inodes [inode..inode + count - 1] 2170 * are marked as free. Inodes should never have to be marked 2171 * as in use. 2172 * freeblks(blockno, size) - blocks [blockno..blockno + size - 1] 2173 * are marked as free. Blocks should never have to be marked 2174 * as in use. 2175 * setflags(flags, set/clear) - the fs_flags field has the specified 2176 * flags set (second parameter +1) or cleared (second parameter -1). 2177 */ 2178 2179 static int sysctl_ffs_fsck(SYSCTL_HANDLER_ARGS); 2180 2181 SYSCTL_PROC(_vfs_ffs, FFS_ADJ_REFCNT, adjrefcnt, CTLFLAG_WR|CTLTYPE_STRUCT, 2182 0, 0, sysctl_ffs_fsck, "S,fsck", "Adjust Inode Reference Count"); 2183 2184 SYSCTL_NODE(_vfs_ffs, FFS_ADJ_BLKCNT, adjblkcnt, CTLFLAG_WR, 2185 sysctl_ffs_fsck, "Adjust Inode Used Blocks Count"); 2186 2187 SYSCTL_NODE(_vfs_ffs, FFS_DIR_FREE, freedirs, CTLFLAG_WR, 2188 sysctl_ffs_fsck, "Free Range of Directory Inodes"); 2189 2190 SYSCTL_NODE(_vfs_ffs, FFS_FILE_FREE, freefiles, CTLFLAG_WR, 2191 sysctl_ffs_fsck, "Free Range of File Inodes"); 2192 2193 SYSCTL_NODE(_vfs_ffs, FFS_BLK_FREE, freeblks, CTLFLAG_WR, 2194 sysctl_ffs_fsck, "Free Range of Blocks"); 2195 2196 SYSCTL_NODE(_vfs_ffs, FFS_SET_FLAGS, setflags, CTLFLAG_WR, 2197 sysctl_ffs_fsck, "Change Filesystem Flags"); 2198 2199 #ifdef DEBUG 2200 static int fsckcmds = 0; 2201 SYSCTL_INT(_debug, OID_AUTO, fsckcmds, CTLFLAG_RW, &fsckcmds, 0, ""); 2202 #endif /* DEBUG */ 2203 2204 static int 2205 sysctl_ffs_fsck(SYSCTL_HANDLER_ARGS) 2206 { 2207 struct fsck_cmd cmd; 2208 struct ufsmount *ump; 2209 struct vnode *vp; 2210 struct inode *ip; 2211 struct mount *mp; 2212 struct fs *fs; 2213 ufs2_daddr_t blkno; 2214 long blkcnt, blksize; 2215 struct file *fp; 2216 int filetype, error; 2217 2218 if (req->newlen > sizeof cmd) 2219 return (EBADRPC); 2220 if ((error = SYSCTL_IN(req, &cmd, sizeof cmd)) != 0) 2221 return (error); 2222 if (cmd.version != FFS_CMD_VERSION) 2223 return (ERPCMISMATCH); 2224 if ((error = getvnode(curproc->p_fd, cmd.handle, &fp)) != 0) 2225 return (error); 2226 vn_start_write(fp->f_data, &mp, V_WAIT); 2227 if (mp == 0 || strncmp(mp->mnt_stat.f_fstypename, "ufs", MFSNAMELEN)) { 2228 vn_finished_write(mp); 2229 fdrop(fp, curthread); 2230 return (EINVAL); 2231 } 2232 if (mp->mnt_flag & MNT_RDONLY) { 2233 vn_finished_write(mp); 2234 fdrop(fp, curthread); 2235 return (EROFS); 2236 } 2237 ump = VFSTOUFS(mp); 2238 fs = ump->um_fs; 2239 filetype = IFREG; 2240 2241 switch (oidp->oid_number) { 2242 2243 case FFS_SET_FLAGS: 2244 #ifdef DEBUG 2245 if (fsckcmds) 2246 printf("%s: %s flags\n", mp->mnt_stat.f_mntonname, 2247 cmd.size > 0 ? "set" : "clear"); 2248 #endif /* DEBUG */ 2249 if (cmd.size > 0) 2250 fs->fs_flags |= (long)cmd.value; 2251 else 2252 fs->fs_flags &= ~(long)cmd.value; 2253 break; 2254 2255 case FFS_ADJ_REFCNT: 2256 #ifdef DEBUG 2257 if (fsckcmds) { 2258 printf("%s: adjust inode %jd count by %jd\n", 2259 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value, 2260 (intmax_t)cmd.size); 2261 } 2262 #endif /* DEBUG */ 2263 if ((error = VFS_VGET(mp, (ino_t)cmd.value, LK_EXCLUSIVE, &vp))) 2264 break; 2265 ip = VTOI(vp); 2266 ip->i_nlink += cmd.size; 2267 DIP(ip, i_nlink) = ip->i_nlink; 2268 ip->i_effnlink += cmd.size; 2269 ip->i_flag |= IN_CHANGE; 2270 if (DOINGSOFTDEP(vp)) 2271 softdep_change_linkcnt(ip); 2272 vput(vp); 2273 break; 2274 2275 case FFS_ADJ_BLKCNT: 2276 #ifdef DEBUG 2277 if (fsckcmds) { 2278 printf("%s: adjust inode %jd block count by %jd\n", 2279 mp->mnt_stat.f_mntonname, (intmax_t)cmd.value, 2280 (intmax_t)cmd.size); 2281 } 2282 #endif /* DEBUG */ 2283 if ((error = VFS_VGET(mp, (ino_t)cmd.value, LK_EXCLUSIVE, &vp))) 2284 break; 2285 ip = VTOI(vp); 2286 DIP(ip, i_blocks) += cmd.size; 2287 ip->i_flag |= IN_CHANGE; 2288 vput(vp); 2289 break; 2290 2291 case FFS_DIR_FREE: 2292 filetype = IFDIR; 2293 /* fall through */ 2294 2295 case FFS_FILE_FREE: 2296 #ifdef DEBUG 2297 if (fsckcmds) { 2298 if (cmd.size == 1) 2299 printf("%s: free %s inode %d\n", 2300 mp->mnt_stat.f_mntonname, 2301 filetype == IFDIR ? "directory" : "file", 2302 (ino_t)cmd.value); 2303 else 2304 printf("%s: free %s inodes %d-%d\n", 2305 mp->mnt_stat.f_mntonname, 2306 filetype == IFDIR ? "directory" : "file", 2307 (ino_t)cmd.value, 2308 (ino_t)(cmd.value + cmd.size - 1)); 2309 } 2310 #endif /* DEBUG */ 2311 while (cmd.size > 0) { 2312 if ((error = ffs_freefile(fs, ump->um_devvp, cmd.value, 2313 filetype))) 2314 break; 2315 cmd.size -= 1; 2316 cmd.value += 1; 2317 } 2318 break; 2319 2320 case FFS_BLK_FREE: 2321 #ifdef DEBUG 2322 if (fsckcmds) { 2323 if (cmd.size == 1) 2324 printf("%s: free block %jd\n", 2325 mp->mnt_stat.f_mntonname, 2326 (intmax_t)cmd.value); 2327 else 2328 printf("%s: free blocks %jd-%jd\n", 2329 mp->mnt_stat.f_mntonname, 2330 (intmax_t)cmd.value, 2331 (intmax_t)cmd.value + cmd.size - 1); 2332 } 2333 #endif /* DEBUG */ 2334 blkno = cmd.value; 2335 blkcnt = cmd.size; 2336 blksize = fs->fs_frag - (blkno % fs->fs_frag); 2337 while (blkcnt > 0) { 2338 if (blksize > blkcnt) 2339 blksize = blkcnt; 2340 ffs_blkfree(fs, ump->um_devvp, blkno, 2341 blksize * fs->fs_fsize, ROOTINO); 2342 blkno += blksize; 2343 blkcnt -= blksize; 2344 blksize = fs->fs_frag; 2345 } 2346 break; 2347 2348 default: 2349 #ifdef DEBUG 2350 if (fsckcmds) { 2351 printf("Invalid request %d from fsck\n", 2352 oidp->oid_number); 2353 } 2354 #endif /* DEBUG */ 2355 error = EINVAL; 2356 break; 2357 2358 } 2359 fdrop(fp, curthread); 2360 vn_finished_write(mp); 2361 return (error); 2362 }
Cache object: e79e08ee872cffbc8c92e54289f5ad5f
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]