ffs_alloc.c revision 1.106.8.7
1 /* $NetBSD: ffs_alloc.c,v 1.106.8.7 2008/12/30 19:30:31 christos Exp $ */ 2 3 /*- 4 * Copyright (c) 2008 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Wasabi Systems, Inc. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * Copyright (c) 2002 Networks Associates Technology, Inc. 34 * All rights reserved. 35 * 36 * This software was developed for the FreeBSD Project by Marshall 37 * Kirk McKusick and Network Associates Laboratories, the Security 38 * Research Division of Network Associates, Inc. under DARPA/SPAWAR 39 * contract N66001-01-C-8035 ("CBOSS"), as part of the DARPA CHATS 40 * research program 41 * 42 * Copyright (c) 1982, 1986, 1989, 1993 43 * The Regents of the University of California. All rights reserved. 44 * 45 * Redistribution and use in source and binary forms, with or without 46 * modification, are permitted provided that the following conditions 47 * are met: 48 * 1. Redistributions of source code must retain the above copyright 49 * notice, this list of conditions and the following disclaimer. 50 * 2. Redistributions in binary form must reproduce the above copyright 51 * notice, this list of conditions and the following disclaimer in the 52 * documentation and/or other materials provided with the distribution. 53 * 3. Neither the name of the University nor the names of its contributors 54 * may be used to endorse or promote products derived from this software 55 * without specific prior written permission. 56 * 57 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 58 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 59 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 60 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 61 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 62 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 63 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 64 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 65 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 66 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 67 * SUCH DAMAGE. 68 * 69 * @(#)ffs_alloc.c 8.19 (Berkeley) 7/13/95 70 */ 71 72 #include <sys/cdefs.h> 73 __KERNEL_RCSID(0, "$NetBSD: ffs_alloc.c,v 1.106.8.7 2008/12/30 19:30:31 christos Exp $"); 74 75 #if defined(_KERNEL_OPT) 76 #include "opt_ffs.h" 77 #include "opt_quota.h" 78 #endif 79 80 #include <sys/param.h> 81 #include <sys/systm.h> 82 #include <sys/buf.h> 83 #include <sys/fstrans.h> 84 #include <sys/kauth.h> 85 #include <sys/kernel.h> 86 #include <sys/mount.h> 87 #include <sys/proc.h> 88 #include <sys/syslog.h> 89 #include <sys/vnode.h> 90 #include <sys/wapbl.h> 91 92 #include <miscfs/specfs/specdev.h> 93 #include <ufs/ufs/quota.h> 94 #include <ufs/ufs/ufsmount.h> 95 #include <ufs/ufs/inode.h> 96 #include <ufs/ufs/ufs_extern.h> 97 #include <ufs/ufs/ufs_bswap.h> 98 #include <ufs/ufs/ufs_wapbl.h> 99 100 #include <ufs/ffs/fs.h> 101 #include <ufs/ffs/ffs_extern.h> 102 103 static daddr_t ffs_alloccg(struct inode *, int, daddr_t, int, int); 104 static daddr_t ffs_alloccgblk(struct inode *, struct buf *, daddr_t, int); 105 static ino_t ffs_dirpref(struct inode *); 106 static daddr_t ffs_fragextend(struct inode *, int, daddr_t, int, int); 107 static void ffs_fserr(struct fs *, u_int, const char *); 108 static daddr_t ffs_hashalloc(struct inode *, int, daddr_t, int, int, 109 daddr_t (*)(struct inode *, int, daddr_t, int, int)); 110 static daddr_t ffs_nodealloccg(struct inode *, int, daddr_t, int, int); 111 static int32_t ffs_mapsearch(struct fs *, struct cg *, 112 daddr_t, int); 113 static void ffs_blkfree_common(struct ufsmount *, struct fs *, dev_t, struct buf *, 114 daddr_t, long, bool); 115 static void ffs_freefile_common(struct ufsmount *, struct fs *, dev_t, struct buf *, ino_t, 116 int, bool); 117 118 /* if 1, changes in optimalization strategy are logged */ 119 int ffs_log_changeopt = 0; 120 121 /* in ffs_tables.c */ 122 extern const int inside[], around[]; 123 extern const u_char * const fragtbl[]; 124 125 /* Basic consistency check for block allocations */ 126 static int 127 ffs_check_bad_allocation(const char *func, struct fs *fs, daddr_t bno, 128 long size, dev_t dev, ino_t inum) 129 { 130 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0 || 131 fragnum(fs, bno) + numfrags(fs, size) > fs->fs_frag) { 132 printf("dev = 0x%llx, bno = %" PRId64 " bsize = %d, " 133 "size = %ld, fs = %s\n", 134 (long long)dev, bno, fs->fs_bsize, size, fs->fs_fsmnt); 135 panic("%s: bad size", func); 136 } 137 138 if (bno >= fs->fs_size) { 139 printf("bad block %" PRId64 ", ino %llu\n", bno, 140 (unsigned long long)inum); 141 ffs_fserr(fs, inum, "bad block"); 142 return EINVAL; 143 } 144 return 0; 145 } 146 147 /* 148 * Allocate a block in the file system. 149 * 150 * The size of the requested block is given, which must be some 151 * multiple of fs_fsize and <= fs_bsize. 152 * A preference may be optionally specified. If a preference is given 153 * the following hierarchy is used to allocate a block: 154 * 1) allocate the requested block. 155 * 2) allocate a rotationally optimal block in the same cylinder. 156 * 3) allocate a block in the same cylinder group. 157 * 4) quadradically rehash into other cylinder groups, until an 158 * available block is located. 159 * If no block preference is given the following hierarchy is used 160 * to allocate a block: 161 * 1) allocate a block in the cylinder group that contains the 162 * inode for the file. 163 * 2) quadradically rehash into other cylinder groups, until an 164 * available block is located. 165 * 166 * => called with um_lock held 167 * => releases um_lock before returning 168 */ 169 int 170 ffs_alloc(struct inode *ip, daddr_t lbn, daddr_t bpref, int size, int flags, 171 kauth_cred_t cred, daddr_t *bnp) 172 { 173 struct ufsmount *ump; 174 struct fs *fs; 175 daddr_t bno; 176 int cg; 177 #ifdef QUOTA 178 int error; 179 #endif 180 181 fs = ip->i_fs; 182 ump = ip->i_ump; 183 184 KASSERT(mutex_owned(&ump->um_lock)); 185 186 #ifdef UVM_PAGE_TRKOWN 187 if (ITOV(ip)->v_type == VREG && 188 lblktosize(fs, (voff_t)lbn) < round_page(ITOV(ip)->v_size)) { 189 struct vm_page *pg; 190 struct uvm_object *uobj = &ITOV(ip)->v_uobj; 191 voff_t off = trunc_page(lblktosize(fs, lbn)); 192 voff_t endoff = round_page(lblktosize(fs, lbn) + size); 193 194 mutex_enter(&uobj->vmobjlock); 195 while (off < endoff) { 196 pg = uvm_pagelookup(uobj, off); 197 KASSERT(pg != NULL); 198 KASSERT(pg->owner == curproc->p_pid); 199 off += PAGE_SIZE; 200 } 201 mutex_exit(&uobj->vmobjlock); 202 } 203 #endif 204 205 *bnp = 0; 206 #ifdef DIAGNOSTIC 207 if ((u_int)size > fs->fs_bsize || fragoff(fs, size) != 0) { 208 printf("dev = 0x%llx, bsize = %d, size = %d, fs = %s\n", 209 ip->i_dev, fs->fs_bsize, size, fs->fs_fsmnt); 210 panic("ffs_alloc: bad size"); 211 } 212 if (cred == NOCRED) 213 panic("ffs_alloc: missing credential"); 214 #endif /* DIAGNOSTIC */ 215 if (size == fs->fs_bsize && fs->fs_cstotal.cs_nbfree == 0) 216 goto nospace; 217 if (freespace(fs, fs->fs_minfree) <= 0 && 218 kauth_authorize_generic(cred, KAUTH_GENERIC_ISSUSER, NULL) != 0) 219 goto nospace; 220 #ifdef QUOTA 221 mutex_exit(&ump->um_lock); 222 if ((error = chkdq(ip, btodb(size), cred, 0)) != 0) 223 return (error); 224 mutex_enter(&ump->um_lock); 225 #endif 226 227 if (bpref >= fs->fs_size) 228 bpref = 0; 229 if (bpref == 0) 230 cg = ino_to_cg(fs, ip->i_number); 231 else 232 cg = dtog(fs, bpref); 233 bno = ffs_hashalloc(ip, cg, bpref, size, flags, ffs_alloccg); 234 if (bno > 0) { 235 DIP_ADD(ip, blocks, btodb(size)); 236 ip->i_flag |= IN_CHANGE | IN_UPDATE; 237 *bnp = bno; 238 return (0); 239 } 240 #ifdef QUOTA 241 /* 242 * Restore user's disk quota because allocation failed. 243 */ 244 (void) chkdq(ip, -btodb(size), cred, FORCE); 245 #endif 246 if (flags & B_CONTIG) { 247 /* 248 * XXX ump->um_lock handling is "suspect" at best. 249 * For the case where ffs_hashalloc() fails early 250 * in the B_CONTIG case we reach here with um_lock 251 * already unlocked, so we can't release it again 252 * like in the normal error path. See kern/39206. 253 * 254 * 255 * Fail silently - it's up to our caller to report 256 * errors. 257 */ 258 return (ENOSPC); 259 } 260 nospace: 261 mutex_exit(&ump->um_lock); 262 ffs_fserr(fs, kauth_cred_geteuid(cred), "file system full"); 263 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 264 return (ENOSPC); 265 } 266 267 /* 268 * Reallocate a fragment to a bigger size 269 * 270 * The number and size of the old block is given, and a preference 271 * and new size is also specified. The allocator attempts to extend 272 * the original block. Failing that, the regular block allocator is 273 * invoked to get an appropriate block. 274 * 275 * => called with um_lock held 276 * => return with um_lock released 277 */ 278 int 279 ffs_realloccg(struct inode *ip, daddr_t lbprev, daddr_t bpref, int osize, 280 int nsize, kauth_cred_t cred, struct buf **bpp, daddr_t *blknop) 281 { 282 struct ufsmount *ump; 283 struct fs *fs; 284 struct buf *bp; 285 int cg, request, error; 286 daddr_t bprev, bno; 287 288 fs = ip->i_fs; 289 ump = ip->i_ump; 290 291 KASSERT(mutex_owned(&ump->um_lock)); 292 293 #ifdef UVM_PAGE_TRKOWN 294 if (ITOV(ip)->v_type == VREG) { 295 struct vm_page *pg; 296 struct uvm_object *uobj = &ITOV(ip)->v_uobj; 297 voff_t off = trunc_page(lblktosize(fs, lbprev)); 298 voff_t endoff = round_page(lblktosize(fs, lbprev) + osize); 299 300 mutex_enter(&uobj->vmobjlock); 301 while (off < endoff) { 302 pg = uvm_pagelookup(uobj, off); 303 KASSERT(pg != NULL); 304 KASSERT(pg->owner == curproc->p_pid); 305 KASSERT((pg->flags & PG_CLEAN) == 0); 306 off += PAGE_SIZE; 307 } 308 mutex_exit(&uobj->vmobjlock); 309 } 310 #endif 311 312 #ifdef DIAGNOSTIC 313 if ((u_int)osize > fs->fs_bsize || fragoff(fs, osize) != 0 || 314 (u_int)nsize > fs->fs_bsize || fragoff(fs, nsize) != 0) { 315 printf( 316 "dev = 0x%llx, bsize = %d, osize = %d, nsize = %d, fs = %s\n", 317 ip->i_dev, fs->fs_bsize, osize, nsize, fs->fs_fsmnt); 318 panic("ffs_realloccg: bad size"); 319 } 320 if (cred == NOCRED) 321 panic("ffs_realloccg: missing credential"); 322 #endif /* DIAGNOSTIC */ 323 if (freespace(fs, fs->fs_minfree) <= 0 && 324 kauth_authorize_generic(cred, KAUTH_GENERIC_ISSUSER, NULL) != 0) { 325 mutex_exit(&ump->um_lock); 326 goto nospace; 327 } 328 if (fs->fs_magic == FS_UFS2_MAGIC) 329 bprev = ufs_rw64(ip->i_ffs2_db[lbprev], UFS_FSNEEDSWAP(fs)); 330 else 331 bprev = ufs_rw32(ip->i_ffs1_db[lbprev], UFS_FSNEEDSWAP(fs)); 332 333 if (bprev == 0) { 334 printf("dev = 0x%llx, bsize = %d, bprev = %" PRId64 ", fs = %s\n", 335 (unsigned long long)ip->i_dev, fs->fs_bsize, bprev, 336 fs->fs_fsmnt); 337 panic("ffs_realloccg: bad bprev"); 338 } 339 mutex_exit(&ump->um_lock); 340 341 /* 342 * Allocate the extra space in the buffer. 343 */ 344 if (bpp != NULL && 345 (error = bread(ITOV(ip), lbprev, osize, NOCRED, 0, &bp)) != 0) { 346 brelse(bp, 0); 347 return (error); 348 } 349 #ifdef QUOTA 350 if ((error = chkdq(ip, btodb(nsize - osize), cred, 0)) != 0) { 351 if (bpp != NULL) { 352 brelse(bp, 0); 353 } 354 return (error); 355 } 356 #endif 357 /* 358 * Check for extension in the existing location. 359 */ 360 cg = dtog(fs, bprev); 361 mutex_enter(&ump->um_lock); 362 if ((bno = ffs_fragextend(ip, cg, bprev, osize, nsize)) != 0) { 363 DIP_ADD(ip, blocks, btodb(nsize - osize)); 364 ip->i_flag |= IN_CHANGE | IN_UPDATE; 365 366 if (bpp != NULL) { 367 if (bp->b_blkno != fsbtodb(fs, bno)) 368 panic("bad blockno"); 369 allocbuf(bp, nsize, 1); 370 memset((char *)bp->b_data + osize, 0, nsize - osize); 371 mutex_enter(bp->b_objlock); 372 KASSERT(!cv_has_waiters(&bp->b_done)); 373 bp->b_oflags |= BO_DONE; 374 mutex_exit(bp->b_objlock); 375 *bpp = bp; 376 } 377 if (blknop != NULL) { 378 *blknop = bno; 379 } 380 return (0); 381 } 382 /* 383 * Allocate a new disk location. 384 */ 385 if (bpref >= fs->fs_size) 386 bpref = 0; 387 switch ((int)fs->fs_optim) { 388 case FS_OPTSPACE: 389 /* 390 * Allocate an exact sized fragment. Although this makes 391 * best use of space, we will waste time relocating it if 392 * the file continues to grow. If the fragmentation is 393 * less than half of the minimum free reserve, we choose 394 * to begin optimizing for time. 395 */ 396 request = nsize; 397 if (fs->fs_minfree < 5 || 398 fs->fs_cstotal.cs_nffree > 399 fs->fs_dsize * fs->fs_minfree / (2 * 100)) 400 break; 401 402 if (ffs_log_changeopt) { 403 log(LOG_NOTICE, 404 "%s: optimization changed from SPACE to TIME\n", 405 fs->fs_fsmnt); 406 } 407 408 fs->fs_optim = FS_OPTTIME; 409 break; 410 case FS_OPTTIME: 411 /* 412 * At this point we have discovered a file that is trying to 413 * grow a small fragment to a larger fragment. To save time, 414 * we allocate a full sized block, then free the unused portion. 415 * If the file continues to grow, the `ffs_fragextend' call 416 * above will be able to grow it in place without further 417 * copying. If aberrant programs cause disk fragmentation to 418 * grow within 2% of the free reserve, we choose to begin 419 * optimizing for space. 420 */ 421 request = fs->fs_bsize; 422 if (fs->fs_cstotal.cs_nffree < 423 fs->fs_dsize * (fs->fs_minfree - 2) / 100) 424 break; 425 426 if (ffs_log_changeopt) { 427 log(LOG_NOTICE, 428 "%s: optimization changed from TIME to SPACE\n", 429 fs->fs_fsmnt); 430 } 431 432 fs->fs_optim = FS_OPTSPACE; 433 break; 434 default: 435 printf("dev = 0x%llx, optim = %d, fs = %s\n", 436 (unsigned long long)ip->i_dev, fs->fs_optim, fs->fs_fsmnt); 437 panic("ffs_realloccg: bad optim"); 438 /* NOTREACHED */ 439 } 440 bno = ffs_hashalloc(ip, cg, bpref, request, 0, ffs_alloccg); 441 if (bno > 0) { 442 if (!DOINGSOFTDEP(ITOV(ip))) { 443 if ((ip->i_ump->um_mountp->mnt_wapbl) && 444 (ITOV(ip)->v_type != VREG)) { 445 UFS_WAPBL_REGISTER_DEALLOCATION( 446 ip->i_ump->um_mountp, fsbtodb(fs, bprev), 447 osize); 448 } else 449 ffs_blkfree(fs, ip->i_devvp, bprev, (long)osize, 450 ip->i_number); 451 } 452 if (nsize < request) { 453 if ((ip->i_ump->um_mountp->mnt_wapbl) && 454 (ITOV(ip)->v_type != VREG)) { 455 UFS_WAPBL_REGISTER_DEALLOCATION( 456 ip->i_ump->um_mountp, 457 fsbtodb(fs, (bno + numfrags(fs, nsize))), 458 request - nsize); 459 } else 460 ffs_blkfree(fs, ip->i_devvp, 461 bno + numfrags(fs, nsize), 462 (long)(request - nsize), ip->i_number); 463 } 464 DIP_ADD(ip, blocks, btodb(nsize - osize)); 465 ip->i_flag |= IN_CHANGE | IN_UPDATE; 466 if (bpp != NULL) { 467 bp->b_blkno = fsbtodb(fs, bno); 468 allocbuf(bp, nsize, 1); 469 memset((char *)bp->b_data + osize, 0, (u_int)nsize - osize); 470 mutex_enter(bp->b_objlock); 471 KASSERT(!cv_has_waiters(&bp->b_done)); 472 bp->b_oflags |= BO_DONE; 473 mutex_exit(bp->b_objlock); 474 *bpp = bp; 475 } 476 if (blknop != NULL) { 477 *blknop = bno; 478 } 479 return (0); 480 } 481 mutex_exit(&ump->um_lock); 482 483 #ifdef QUOTA 484 /* 485 * Restore user's disk quota because allocation failed. 486 */ 487 (void) chkdq(ip, -btodb(nsize - osize), cred, FORCE); 488 #endif 489 if (bpp != NULL) { 490 brelse(bp, 0); 491 } 492 493 nospace: 494 /* 495 * no space available 496 */ 497 ffs_fserr(fs, kauth_cred_geteuid(cred), "file system full"); 498 uprintf("\n%s: write failed, file system is full\n", fs->fs_fsmnt); 499 return (ENOSPC); 500 } 501 502 /* 503 * Allocate an inode in the file system. 504 * 505 * If allocating a directory, use ffs_dirpref to select the inode. 506 * If allocating in a directory, the following hierarchy is followed: 507 * 1) allocate the preferred inode. 508 * 2) allocate an inode in the same cylinder group. 509 * 3) quadradically rehash into other cylinder groups, until an 510 * available inode is located. 511 * If no inode preference is given the following hierarchy is used 512 * to allocate an inode: 513 * 1) allocate an inode in cylinder group 0. 514 * 2) quadradically rehash into other cylinder groups, until an 515 * available inode is located. 516 * 517 * => um_lock not held upon entry or return 518 */ 519 int 520 ffs_valloc(struct vnode *pvp, int mode, kauth_cred_t cred, 521 struct vnode **vpp) 522 { 523 struct ufsmount *ump; 524 struct inode *pip; 525 struct fs *fs; 526 struct inode *ip; 527 struct timespec ts; 528 ino_t ino, ipref; 529 int cg, error; 530 531 UFS_WAPBL_JUNLOCK_ASSERT(pvp->v_mount); 532 533 *vpp = NULL; 534 pip = VTOI(pvp); 535 fs = pip->i_fs; 536 ump = pip->i_ump; 537 538 error = UFS_WAPBL_BEGIN(pvp->v_mount); 539 if (error) { 540 return error; 541 } 542 mutex_enter(&ump->um_lock); 543 if (fs->fs_cstotal.cs_nifree == 0) 544 goto noinodes; 545 546 if ((mode & IFMT) == IFDIR) 547 ipref = ffs_dirpref(pip); 548 else 549 ipref = pip->i_number; 550 if (ipref >= fs->fs_ncg * fs->fs_ipg) 551 ipref = 0; 552 cg = ino_to_cg(fs, ipref); 553 /* 554 * Track number of dirs created one after another 555 * in a same cg without intervening by files. 556 */ 557 if ((mode & IFMT) == IFDIR) { 558 if (fs->fs_contigdirs[cg] < 255) 559 fs->fs_contigdirs[cg]++; 560 } else { 561 if (fs->fs_contigdirs[cg] > 0) 562 fs->fs_contigdirs[cg]--; 563 } 564 ino = (ino_t)ffs_hashalloc(pip, cg, ipref, mode, 0, ffs_nodealloccg); 565 if (ino == 0) 566 goto noinodes; 567 UFS_WAPBL_END(pvp->v_mount); 568 error = VFS_VGET(pvp->v_mount, ino, vpp); 569 if (error) { 570 int err; 571 err = UFS_WAPBL_BEGIN(pvp->v_mount); 572 if (err == 0) 573 ffs_vfree(pvp, ino, mode); 574 if (err == 0) 575 UFS_WAPBL_END(pvp->v_mount); 576 return (error); 577 } 578 KASSERT((*vpp)->v_type == VNON); 579 ip = VTOI(*vpp); 580 if (ip->i_mode) { 581 #if 0 582 printf("mode = 0%o, inum = %d, fs = %s\n", 583 ip->i_mode, ip->i_number, fs->fs_fsmnt); 584 #else 585 printf("dmode %x mode %x dgen %x gen %x\n", 586 DIP(ip, mode), ip->i_mode, 587 DIP(ip, gen), ip->i_gen); 588 printf("size %llx blocks %llx\n", 589 (long long)DIP(ip, size), (long long)DIP(ip, blocks)); 590 printf("ino %llu ipref %llu\n", (unsigned long long)ino, 591 (unsigned long long)ipref); 592 #if 0 593 error = bread(ump->um_devvp, fsbtodb(fs, ino_to_fsba(fs, ino)), 594 (int)fs->fs_bsize, NOCRED, 0, &bp); 595 #endif 596 597 #endif 598 panic("ffs_valloc: dup alloc"); 599 } 600 if (DIP(ip, blocks)) { /* XXX */ 601 printf("free inode %s/%llu had %" PRId64 " blocks\n", 602 fs->fs_fsmnt, (unsigned long long)ino, DIP(ip, blocks)); 603 DIP_ASSIGN(ip, blocks, 0); 604 } 605 ip->i_flag &= ~IN_SPACECOUNTED; 606 ip->i_flags = 0; 607 DIP_ASSIGN(ip, flags, 0); 608 /* 609 * Set up a new generation number for this inode. 610 */ 611 ip->i_gen++; 612 DIP_ASSIGN(ip, gen, ip->i_gen); 613 if (fs->fs_magic == FS_UFS2_MAGIC) { 614 vfs_timestamp(&ts); 615 ip->i_ffs2_birthtime = ts.tv_sec; 616 ip->i_ffs2_birthnsec = ts.tv_nsec; 617 } 618 return (0); 619 noinodes: 620 mutex_exit(&ump->um_lock); 621 UFS_WAPBL_END(pvp->v_mount); 622 ffs_fserr(fs, kauth_cred_geteuid(cred), "out of inodes"); 623 uprintf("\n%s: create/symlink failed, no inodes free\n", fs->fs_fsmnt); 624 return (ENOSPC); 625 } 626 627 /* 628 * Find a cylinder group in which to place a directory. 629 * 630 * The policy implemented by this algorithm is to allocate a 631 * directory inode in the same cylinder group as its parent 632 * directory, but also to reserve space for its files inodes 633 * and data. Restrict the number of directories which may be 634 * allocated one after another in the same cylinder group 635 * without intervening allocation of files. 636 * 637 * If we allocate a first level directory then force allocation 638 * in another cylinder group. 639 */ 640 static ino_t 641 ffs_dirpref(struct inode *pip) 642 { 643 register struct fs *fs; 644 int cg, prefcg; 645 int64_t dirsize, cgsize, curdsz; 646 int avgifree, avgbfree, avgndir; 647 int minifree, minbfree, maxndir; 648 int mincg, minndir; 649 int maxcontigdirs; 650 651 KASSERT(mutex_owned(&pip->i_ump->um_lock)); 652 653 fs = pip->i_fs; 654 655 avgifree = fs->fs_cstotal.cs_nifree / fs->fs_ncg; 656 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 657 avgndir = fs->fs_cstotal.cs_ndir / fs->fs_ncg; 658 659 /* 660 * Force allocation in another cg if creating a first level dir. 661 */ 662 if (ITOV(pip)->v_vflag & VV_ROOT) { 663 prefcg = random() % fs->fs_ncg; 664 mincg = prefcg; 665 minndir = fs->fs_ipg; 666 for (cg = prefcg; cg < fs->fs_ncg; cg++) 667 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 668 fs->fs_cs(fs, cg).cs_nifree >= avgifree && 669 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 670 mincg = cg; 671 minndir = fs->fs_cs(fs, cg).cs_ndir; 672 } 673 for (cg = 0; cg < prefcg; cg++) 674 if (fs->fs_cs(fs, cg).cs_ndir < minndir && 675 fs->fs_cs(fs, cg).cs_nifree >= avgifree && 676 fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 677 mincg = cg; 678 minndir = fs->fs_cs(fs, cg).cs_ndir; 679 } 680 return ((ino_t)(fs->fs_ipg * mincg)); 681 } 682 683 /* 684 * Count various limits which used for 685 * optimal allocation of a directory inode. 686 */ 687 maxndir = min(avgndir + fs->fs_ipg / 16, fs->fs_ipg); 688 minifree = avgifree - fs->fs_ipg / 4; 689 if (minifree < 0) 690 minifree = 0; 691 minbfree = avgbfree - fragstoblks(fs, fs->fs_fpg) / 4; 692 if (minbfree < 0) 693 minbfree = 0; 694 cgsize = (int64_t)fs->fs_fsize * fs->fs_fpg; 695 dirsize = (int64_t)fs->fs_avgfilesize * fs->fs_avgfpdir; 696 if (avgndir != 0) { 697 curdsz = (cgsize - (int64_t)avgbfree * fs->fs_bsize) / avgndir; 698 if (dirsize < curdsz) 699 dirsize = curdsz; 700 } 701 if (cgsize < dirsize * 255) 702 maxcontigdirs = cgsize / dirsize; 703 else 704 maxcontigdirs = 255; 705 if (fs->fs_avgfpdir > 0) 706 maxcontigdirs = min(maxcontigdirs, 707 fs->fs_ipg / fs->fs_avgfpdir); 708 if (maxcontigdirs == 0) 709 maxcontigdirs = 1; 710 711 /* 712 * Limit number of dirs in one cg and reserve space for 713 * regular files, but only if we have no deficit in 714 * inodes or space. 715 */ 716 prefcg = ino_to_cg(fs, pip->i_number); 717 for (cg = prefcg; cg < fs->fs_ncg; cg++) 718 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 719 fs->fs_cs(fs, cg).cs_nifree >= minifree && 720 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 721 if (fs->fs_contigdirs[cg] < maxcontigdirs) 722 return ((ino_t)(fs->fs_ipg * cg)); 723 } 724 for (cg = 0; cg < prefcg; cg++) 725 if (fs->fs_cs(fs, cg).cs_ndir < maxndir && 726 fs->fs_cs(fs, cg).cs_nifree >= minifree && 727 fs->fs_cs(fs, cg).cs_nbfree >= minbfree) { 728 if (fs->fs_contigdirs[cg] < maxcontigdirs) 729 return ((ino_t)(fs->fs_ipg * cg)); 730 } 731 /* 732 * This is a backstop when we are deficient in space. 733 */ 734 for (cg = prefcg; cg < fs->fs_ncg; cg++) 735 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 736 return ((ino_t)(fs->fs_ipg * cg)); 737 for (cg = 0; cg < prefcg; cg++) 738 if (fs->fs_cs(fs, cg).cs_nifree >= avgifree) 739 break; 740 return ((ino_t)(fs->fs_ipg * cg)); 741 } 742 743 /* 744 * Select the desired position for the next block in a file. The file is 745 * logically divided into sections. The first section is composed of the 746 * direct blocks. Each additional section contains fs_maxbpg blocks. 747 * 748 * If no blocks have been allocated in the first section, the policy is to 749 * request a block in the same cylinder group as the inode that describes 750 * the file. If no blocks have been allocated in any other section, the 751 * policy is to place the section in a cylinder group with a greater than 752 * average number of free blocks. An appropriate cylinder group is found 753 * by using a rotor that sweeps the cylinder groups. When a new group of 754 * blocks is needed, the sweep begins in the cylinder group following the 755 * cylinder group from which the previous allocation was made. The sweep 756 * continues until a cylinder group with greater than the average number 757 * of free blocks is found. If the allocation is for the first block in an 758 * indirect block, the information on the previous allocation is unavailable; 759 * here a best guess is made based upon the logical block number being 760 * allocated. 761 * 762 * If a section is already partially allocated, the policy is to 763 * contiguously allocate fs_maxcontig blocks. The end of one of these 764 * contiguous blocks and the beginning of the next is laid out 765 * contigously if possible. 766 * 767 * => um_lock held on entry and exit 768 */ 769 daddr_t 770 ffs_blkpref_ufs1(struct inode *ip, daddr_t lbn, int indx, int flags, 771 int32_t *bap /* XXX ondisk32 */) 772 { 773 struct fs *fs; 774 int cg; 775 int avgbfree, startcg; 776 777 KASSERT(mutex_owned(&ip->i_ump->um_lock)); 778 779 fs = ip->i_fs; 780 781 /* 782 * If allocating a contiguous file with B_CONTIG, use the hints 783 * in the inode extentions to return the desired block. 784 * 785 * For metadata (indirect blocks) return the address of where 786 * the first indirect block resides - we'll scan for the next 787 * available slot if we need to allocate more than one indirect 788 * block. For data, return the address of the actual block 789 * relative to the address of the first data block. 790 */ 791 if (flags & B_CONTIG) { 792 KASSERT(ip->i_ffs_first_data_blk != 0); 793 KASSERT(ip->i_ffs_first_indir_blk != 0); 794 if (flags & B_METAONLY) 795 return ip->i_ffs_first_indir_blk; 796 else 797 return ip->i_ffs_first_data_blk + blkstofrags(fs, lbn); 798 } 799 800 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 801 if (lbn < NDADDR + NINDIR(fs)) { 802 cg = ino_to_cg(fs, ip->i_number); 803 return (cgbase(fs, cg) + fs->fs_frag); 804 } 805 /* 806 * Find a cylinder with greater than average number of 807 * unused data blocks. 808 */ 809 if (indx == 0 || bap[indx - 1] == 0) 810 startcg = 811 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 812 else 813 startcg = dtog(fs, 814 ufs_rw32(bap[indx - 1], UFS_FSNEEDSWAP(fs)) + 1); 815 startcg %= fs->fs_ncg; 816 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 817 for (cg = startcg; cg < fs->fs_ncg; cg++) 818 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 819 return (cgbase(fs, cg) + fs->fs_frag); 820 } 821 for (cg = 0; cg < startcg; cg++) 822 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 823 return (cgbase(fs, cg) + fs->fs_frag); 824 } 825 return (0); 826 } 827 /* 828 * We just always try to lay things out contiguously. 829 */ 830 return ufs_rw32(bap[indx - 1], UFS_FSNEEDSWAP(fs)) + fs->fs_frag; 831 } 832 833 daddr_t 834 ffs_blkpref_ufs2(struct inode *ip, daddr_t lbn, int indx, int flags, 835 int64_t *bap) 836 { 837 struct fs *fs; 838 int cg; 839 int avgbfree, startcg; 840 841 KASSERT(mutex_owned(&ip->i_ump->um_lock)); 842 843 fs = ip->i_fs; 844 845 /* 846 * If allocating a contiguous file with B_CONTIG, use the hints 847 * in the inode extentions to return the desired block. 848 * 849 * For metadata (indirect blocks) return the address of where 850 * the first indirect block resides - we'll scan for the next 851 * available slot if we need to allocate more than one indirect 852 * block. For data, return the address of the actual block 853 * relative to the address of the first data block. 854 */ 855 if (flags & B_CONTIG) { 856 KASSERT(ip->i_ffs_first_data_blk != 0); 857 KASSERT(ip->i_ffs_first_indir_blk != 0); 858 if (flags & B_METAONLY) 859 return ip->i_ffs_first_indir_blk; 860 else 861 return ip->i_ffs_first_data_blk + blkstofrags(fs, lbn); 862 } 863 864 if (indx % fs->fs_maxbpg == 0 || bap[indx - 1] == 0) { 865 if (lbn < NDADDR + NINDIR(fs)) { 866 cg = ino_to_cg(fs, ip->i_number); 867 return (cgbase(fs, cg) + fs->fs_frag); 868 } 869 /* 870 * Find a cylinder with greater than average number of 871 * unused data blocks. 872 */ 873 if (indx == 0 || bap[indx - 1] == 0) 874 startcg = 875 ino_to_cg(fs, ip->i_number) + lbn / fs->fs_maxbpg; 876 else 877 startcg = dtog(fs, 878 ufs_rw64(bap[indx - 1], UFS_FSNEEDSWAP(fs)) + 1); 879 startcg %= fs->fs_ncg; 880 avgbfree = fs->fs_cstotal.cs_nbfree / fs->fs_ncg; 881 for (cg = startcg; cg < fs->fs_ncg; cg++) 882 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 883 return (cgbase(fs, cg) + fs->fs_frag); 884 } 885 for (cg = 0; cg < startcg; cg++) 886 if (fs->fs_cs(fs, cg).cs_nbfree >= avgbfree) { 887 return (cgbase(fs, cg) + fs->fs_frag); 888 } 889 return (0); 890 } 891 /* 892 * We just always try to lay things out contiguously. 893 */ 894 return ufs_rw64(bap[indx - 1], UFS_FSNEEDSWAP(fs)) + fs->fs_frag; 895 } 896 897 898 /* 899 * Implement the cylinder overflow algorithm. 900 * 901 * The policy implemented by this algorithm is: 902 * 1) allocate the block in its requested cylinder group. 903 * 2) quadradically rehash on the cylinder group number. 904 * 3) brute force search for a free block. 905 * 906 * => called with um_lock held 907 * => returns with um_lock released on success, held on failure 908 * (*allocator releases lock on success, retains lock on failure) 909 */ 910 /*VARARGS5*/ 911 static daddr_t 912 ffs_hashalloc(struct inode *ip, int cg, daddr_t pref, 913 int size /* size for data blocks, mode for inodes */, 914 int flags, daddr_t (*allocator)(struct inode *, int, daddr_t, int, int)) 915 { 916 struct fs *fs; 917 daddr_t result; 918 int i, icg = cg; 919 920 fs = ip->i_fs; 921 /* 922 * 1: preferred cylinder group 923 */ 924 result = (*allocator)(ip, cg, pref, size, flags); 925 if (result) 926 return (result); 927 928 if (flags & B_CONTIG) 929 return (result); 930 /* 931 * 2: quadratic rehash 932 */ 933 for (i = 1; i < fs->fs_ncg; i *= 2) { 934 cg += i; 935 if (cg >= fs->fs_ncg) 936 cg -= fs->fs_ncg; 937 result = (*allocator)(ip, cg, 0, size, flags); 938 if (result) 939 return (result); 940 } 941 /* 942 * 3: brute force search 943 * Note that we start at i == 2, since 0 was checked initially, 944 * and 1 is always checked in the quadratic rehash. 945 */ 946 cg = (icg + 2) % fs->fs_ncg; 947 for (i = 2; i < fs->fs_ncg; i++) { 948 result = (*allocator)(ip, cg, 0, size, flags); 949 if (result) 950 return (result); 951 cg++; 952 if (cg == fs->fs_ncg) 953 cg = 0; 954 } 955 return (0); 956 } 957 958 /* 959 * Determine whether a fragment can be extended. 960 * 961 * Check to see if the necessary fragments are available, and 962 * if they are, allocate them. 963 * 964 * => called with um_lock held 965 * => returns with um_lock released on success, held on failure 966 */ 967 static daddr_t 968 ffs_fragextend(struct inode *ip, int cg, daddr_t bprev, int osize, int nsize) 969 { 970 struct ufsmount *ump; 971 struct fs *fs; 972 struct cg *cgp; 973 struct buf *bp; 974 daddr_t bno; 975 int frags, bbase; 976 int i, error; 977 u_int8_t *blksfree; 978 979 fs = ip->i_fs; 980 ump = ip->i_ump; 981 982 KASSERT(mutex_owned(&ump->um_lock)); 983 984 if (fs->fs_cs(fs, cg).cs_nffree < numfrags(fs, nsize - osize)) 985 return (0); 986 frags = numfrags(fs, nsize); 987 bbase = fragnum(fs, bprev); 988 if (bbase > fragnum(fs, (bprev + frags - 1))) { 989 /* cannot extend across a block boundary */ 990 return (0); 991 } 992 mutex_exit(&ump->um_lock); 993 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 994 (int)fs->fs_cgsize, NOCRED, B_MODIFY, &bp); 995 if (error) 996 goto fail; 997 cgp = (struct cg *)bp->b_data; 998 if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs))) 999 goto fail; 1000 cgp->cg_old_time = ufs_rw32(time_second, UFS_FSNEEDSWAP(fs)); 1001 if ((fs->fs_magic != FS_UFS1_MAGIC) || 1002 (fs->fs_old_flags & FS_FLAGS_UPDATED)) 1003 cgp->cg_time = ufs_rw64(time_second, UFS_FSNEEDSWAP(fs)); 1004 bno = dtogd(fs, bprev); 1005 blksfree = cg_blksfree(cgp, UFS_FSNEEDSWAP(fs)); 1006 for (i = numfrags(fs, osize); i < frags; i++) 1007 if (isclr(blksfree, bno + i)) 1008 goto fail; 1009 /* 1010 * the current fragment can be extended 1011 * deduct the count on fragment being extended into 1012 * increase the count on the remaining fragment (if any) 1013 * allocate the extended piece 1014 */ 1015 for (i = frags; i < fs->fs_frag - bbase; i++) 1016 if (isclr(blksfree, bno + i)) 1017 break; 1018 ufs_add32(cgp->cg_frsum[i - numfrags(fs, osize)], -1, UFS_FSNEEDSWAP(fs)); 1019 if (i != frags) 1020 ufs_add32(cgp->cg_frsum[i - frags], 1, UFS_FSNEEDSWAP(fs)); 1021 mutex_enter(&ump->um_lock); 1022 for (i = numfrags(fs, osize); i < frags; i++) { 1023 clrbit(blksfree, bno + i); 1024 ufs_add32(cgp->cg_cs.cs_nffree, -1, UFS_FSNEEDSWAP(fs)); 1025 fs->fs_cstotal.cs_nffree--; 1026 fs->fs_cs(fs, cg).cs_nffree--; 1027 } 1028 fs->fs_fmod = 1; 1029 ACTIVECG_CLR(fs, cg); 1030 mutex_exit(&ump->um_lock); 1031 if (DOINGSOFTDEP(ITOV(ip))) 1032 softdep_setup_blkmapdep(bp, fs, bprev); 1033 bdwrite(bp); 1034 return (bprev); 1035 1036 fail: 1037 brelse(bp, 0); 1038 mutex_enter(&ump->um_lock); 1039 return (0); 1040 } 1041 1042 /* 1043 * Determine whether a block can be allocated. 1044 * 1045 * Check to see if a block of the appropriate size is available, 1046 * and if it is, allocate it. 1047 */ 1048 static daddr_t 1049 ffs_alloccg(struct inode *ip, int cg, daddr_t bpref, int size, int flags) 1050 { 1051 struct ufsmount *ump; 1052 struct fs *fs = ip->i_fs; 1053 struct cg *cgp; 1054 struct buf *bp; 1055 int32_t bno; 1056 daddr_t blkno; 1057 int error, frags, allocsiz, i; 1058 u_int8_t *blksfree; 1059 #ifdef FFS_EI 1060 const int needswap = UFS_FSNEEDSWAP(fs); 1061 #endif 1062 1063 ump = ip->i_ump; 1064 1065 KASSERT(mutex_owned(&ump->um_lock)); 1066 1067 if (fs->fs_cs(fs, cg).cs_nbfree == 0 && size == fs->fs_bsize) 1068 return (0); 1069 mutex_exit(&ump->um_lock); 1070 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1071 (int)fs->fs_cgsize, NOCRED, B_MODIFY, &bp); 1072 if (error) 1073 goto fail; 1074 cgp = (struct cg *)bp->b_data; 1075 if (!cg_chkmagic(cgp, needswap) || 1076 (cgp->cg_cs.cs_nbfree == 0 && size == fs->fs_bsize)) 1077 goto fail; 1078 cgp->cg_old_time = ufs_rw32(time_second, needswap); 1079 if ((fs->fs_magic != FS_UFS1_MAGIC) || 1080 (fs->fs_old_flags & FS_FLAGS_UPDATED)) 1081 cgp->cg_time = ufs_rw64(time_second, needswap); 1082 if (size == fs->fs_bsize) { 1083 mutex_enter(&ump->um_lock); 1084 blkno = ffs_alloccgblk(ip, bp, bpref, flags); 1085 ACTIVECG_CLR(fs, cg); 1086 mutex_exit(&ump->um_lock); 1087 bdwrite(bp); 1088 return (blkno); 1089 } 1090 /* 1091 * check to see if any fragments are already available 1092 * allocsiz is the size which will be allocated, hacking 1093 * it down to a smaller size if necessary 1094 */ 1095 blksfree = cg_blksfree(cgp, needswap); 1096 frags = numfrags(fs, size); 1097 for (allocsiz = frags; allocsiz < fs->fs_frag; allocsiz++) 1098 if (cgp->cg_frsum[allocsiz] != 0) 1099 break; 1100 if (allocsiz == fs->fs_frag) { 1101 /* 1102 * no fragments were available, so a block will be 1103 * allocated, and hacked up 1104 */ 1105 if (cgp->cg_cs.cs_nbfree == 0) 1106 goto fail; 1107 mutex_enter(&ump->um_lock); 1108 blkno = ffs_alloccgblk(ip, bp, bpref, flags); 1109 bno = dtogd(fs, blkno); 1110 for (i = frags; i < fs->fs_frag; i++) 1111 setbit(blksfree, bno + i); 1112 i = fs->fs_frag - frags; 1113 ufs_add32(cgp->cg_cs.cs_nffree, i, needswap); 1114 fs->fs_cstotal.cs_nffree += i; 1115 fs->fs_cs(fs, cg).cs_nffree += i; 1116 fs->fs_fmod = 1; 1117 ufs_add32(cgp->cg_frsum[i], 1, needswap); 1118 ACTIVECG_CLR(fs, cg); 1119 mutex_exit(&ump->um_lock); 1120 bdwrite(bp); 1121 return (blkno); 1122 } 1123 bno = ffs_mapsearch(fs, cgp, bpref, allocsiz); 1124 #if 0 1125 /* 1126 * XXX fvdl mapsearch will panic, and never return -1 1127 * also: returning NULL as daddr_t ? 1128 */ 1129 if (bno < 0) 1130 goto fail; 1131 #endif 1132 for (i = 0; i < frags; i++) 1133 clrbit(blksfree, bno + i); 1134 mutex_enter(&ump->um_lock); 1135 ufs_add32(cgp->cg_cs.cs_nffree, -frags, needswap); 1136 fs->fs_cstotal.cs_nffree -= frags; 1137 fs->fs_cs(fs, cg).cs_nffree -= frags; 1138 fs->fs_fmod = 1; 1139 ufs_add32(cgp->cg_frsum[allocsiz], -1, needswap); 1140 if (frags != allocsiz) 1141 ufs_add32(cgp->cg_frsum[allocsiz - frags], 1, needswap); 1142 blkno = cg * fs->fs_fpg + bno; 1143 ACTIVECG_CLR(fs, cg); 1144 mutex_exit(&ump->um_lock); 1145 if (DOINGSOFTDEP(ITOV(ip))) 1146 softdep_setup_blkmapdep(bp, fs, blkno); 1147 bdwrite(bp); 1148 return blkno; 1149 1150 fail: 1151 brelse(bp, 0); 1152 mutex_enter(&ump->um_lock); 1153 return (0); 1154 } 1155 1156 /* 1157 * Allocate a block in a cylinder group. 1158 * 1159 * This algorithm implements the following policy: 1160 * 1) allocate the requested block. 1161 * 2) allocate a rotationally optimal block in the same cylinder. 1162 * 3) allocate the next available block on the block rotor for the 1163 * specified cylinder group. 1164 * Note that this routine only allocates fs_bsize blocks; these 1165 * blocks may be fragmented by the routine that allocates them. 1166 */ 1167 static daddr_t 1168 ffs_alloccgblk(struct inode *ip, struct buf *bp, daddr_t bpref, int flags) 1169 { 1170 struct ufsmount *ump; 1171 struct fs *fs = ip->i_fs; 1172 struct cg *cgp; 1173 daddr_t blkno; 1174 int32_t bno; 1175 u_int8_t *blksfree; 1176 #ifdef FFS_EI 1177 const int needswap = UFS_FSNEEDSWAP(fs); 1178 #endif 1179 1180 ump = ip->i_ump; 1181 1182 KASSERT(mutex_owned(&ump->um_lock)); 1183 1184 cgp = (struct cg *)bp->b_data; 1185 blksfree = cg_blksfree(cgp, needswap); 1186 if (bpref == 0 || dtog(fs, bpref) != ufs_rw32(cgp->cg_cgx, needswap)) { 1187 bpref = ufs_rw32(cgp->cg_rotor, needswap); 1188 } else { 1189 bpref = blknum(fs, bpref); 1190 bno = dtogd(fs, bpref); 1191 /* 1192 * if the requested block is available, use it 1193 */ 1194 if (ffs_isblock(fs, blksfree, fragstoblks(fs, bno))) 1195 goto gotit; 1196 /* 1197 * if the requested data block isn't available and we are 1198 * trying to allocate a contiguous file, return an error. 1199 */ 1200 if ((flags & (B_CONTIG | B_METAONLY)) == B_CONTIG) 1201 return (0); 1202 } 1203 1204 /* 1205 * Take the next available block in this cylinder group. 1206 */ 1207 bno = ffs_mapsearch(fs, cgp, bpref, (int)fs->fs_frag); 1208 if (bno < 0) 1209 return (0); 1210 cgp->cg_rotor = ufs_rw32(bno, needswap); 1211 gotit: 1212 blkno = fragstoblks(fs, bno); 1213 ffs_clrblock(fs, blksfree, blkno); 1214 ffs_clusteracct(fs, cgp, blkno, -1); 1215 ufs_add32(cgp->cg_cs.cs_nbfree, -1, needswap); 1216 fs->fs_cstotal.cs_nbfree--; 1217 fs->fs_cs(fs, ufs_rw32(cgp->cg_cgx, needswap)).cs_nbfree--; 1218 if ((fs->fs_magic == FS_UFS1_MAGIC) && 1219 ((fs->fs_old_flags & FS_FLAGS_UPDATED) == 0)) { 1220 int cylno; 1221 cylno = old_cbtocylno(fs, bno); 1222 KASSERT(cylno >= 0); 1223 KASSERT(cylno < fs->fs_old_ncyl); 1224 KASSERT(old_cbtorpos(fs, bno) >= 0); 1225 KASSERT(fs->fs_old_nrpos == 0 || old_cbtorpos(fs, bno) < fs->fs_old_nrpos); 1226 ufs_add16(old_cg_blks(fs, cgp, cylno, needswap)[old_cbtorpos(fs, bno)], -1, 1227 needswap); 1228 ufs_add32(old_cg_blktot(cgp, needswap)[cylno], -1, needswap); 1229 } 1230 fs->fs_fmod = 1; 1231 blkno = ufs_rw32(cgp->cg_cgx, needswap) * fs->fs_fpg + bno; 1232 if (DOINGSOFTDEP(ITOV(ip))) { 1233 mutex_exit(&ump->um_lock); 1234 softdep_setup_blkmapdep(bp, fs, blkno); 1235 mutex_enter(&ump->um_lock); 1236 } 1237 return (blkno); 1238 } 1239 1240 /* 1241 * Determine whether an inode can be allocated. 1242 * 1243 * Check to see if an inode is available, and if it is, 1244 * allocate it using the following policy: 1245 * 1) allocate the requested inode. 1246 * 2) allocate the next available inode after the requested 1247 * inode in the specified cylinder group. 1248 */ 1249 static daddr_t 1250 ffs_nodealloccg(struct inode *ip, int cg, daddr_t ipref, int mode, int flags) 1251 { 1252 struct ufsmount *ump = ip->i_ump; 1253 struct fs *fs = ip->i_fs; 1254 struct cg *cgp; 1255 struct buf *bp, *ibp; 1256 u_int8_t *inosused; 1257 int error, start, len, loc, map, i; 1258 int32_t initediblk; 1259 daddr_t nalloc; 1260 struct ufs2_dinode *dp2; 1261 #ifdef FFS_EI 1262 const int needswap = UFS_FSNEEDSWAP(fs); 1263 #endif 1264 1265 KASSERT(mutex_owned(&ump->um_lock)); 1266 UFS_WAPBL_JLOCK_ASSERT(ip->i_ump->um_mountp); 1267 1268 if (fs->fs_cs(fs, cg).cs_nifree == 0) 1269 return (0); 1270 mutex_exit(&ump->um_lock); 1271 ibp = NULL; 1272 initediblk = -1; 1273 retry: 1274 error = bread(ip->i_devvp, fsbtodb(fs, cgtod(fs, cg)), 1275 (int)fs->fs_cgsize, NOCRED, B_MODIFY, &bp); 1276 if (error) 1277 goto fail; 1278 cgp = (struct cg *)bp->b_data; 1279 if (!cg_chkmagic(cgp, needswap) || cgp->cg_cs.cs_nifree == 0) 1280 goto fail; 1281 1282 if (ibp != NULL && 1283 initediblk != ufs_rw32(cgp->cg_initediblk, needswap)) { 1284 /* Another thread allocated more inodes so we retry the test. */ 1285 brelse(ibp, BC_INVAL); 1286 ibp = NULL; 1287 } 1288 /* 1289 * Check to see if we need to initialize more inodes. 1290 */ 1291 if (fs->fs_magic == FS_UFS2_MAGIC && ibp == NULL) { 1292 initediblk = ufs_rw32(cgp->cg_initediblk, needswap); 1293 nalloc = fs->fs_ipg - ufs_rw32(cgp->cg_cs.cs_nifree, needswap); 1294 if (nalloc + INOPB(fs) > initediblk && 1295 initediblk < ufs_rw32(cgp->cg_niblk, needswap)) { 1296 /* 1297 * We have to release the cg buffer here to prevent 1298 * a deadlock when reading the inode block will 1299 * run a copy-on-write that might use this cg. 1300 */ 1301 brelse(bp, 0); 1302 bp = NULL; 1303 error = ffs_getblk(ip->i_devvp, fsbtodb(fs, 1304 ino_to_fsba(fs, cg * fs->fs_ipg + initediblk)), 1305 FFS_NOBLK, fs->fs_bsize, false, &ibp); 1306 if (error) 1307 goto fail; 1308 goto retry; 1309 } 1310 } 1311 1312 cgp->cg_old_time = ufs_rw32(time_second, needswap); 1313 if ((fs->fs_magic != FS_UFS1_MAGIC) || 1314 (fs->fs_old_flags & FS_FLAGS_UPDATED)) 1315 cgp->cg_time = ufs_rw64(time_second, needswap); 1316 inosused = cg_inosused(cgp, needswap); 1317 if (ipref) { 1318 ipref %= fs->fs_ipg; 1319 if (isclr(inosused, ipref)) 1320 goto gotit; 1321 } 1322 start = ufs_rw32(cgp->cg_irotor, needswap) / NBBY; 1323 len = howmany(fs->fs_ipg - ufs_rw32(cgp->cg_irotor, needswap), 1324 NBBY); 1325 loc = skpc(0xff, len, &inosused[start]); 1326 if (loc == 0) { 1327 len = start + 1; 1328 start = 0; 1329 loc = skpc(0xff, len, &inosused[0]); 1330 if (loc == 0) { 1331 printf("cg = %d, irotor = %d, fs = %s\n", 1332 cg, ufs_rw32(cgp->cg_irotor, needswap), 1333 fs->fs_fsmnt); 1334 panic("ffs_nodealloccg: map corrupted"); 1335 /* NOTREACHED */ 1336 } 1337 } 1338 i = start + len - loc; 1339 map = inosused[i]; 1340 ipref = i * NBBY; 1341 for (i = 1; i < (1 << NBBY); i <<= 1, ipref++) { 1342 if ((map & i) == 0) { 1343 cgp->cg_irotor = ufs_rw32(ipref, needswap); 1344 goto gotit; 1345 } 1346 } 1347 printf("fs = %s\n", fs->fs_fsmnt); 1348 panic("ffs_nodealloccg: block not in map"); 1349 /* NOTREACHED */ 1350 gotit: 1351 UFS_WAPBL_REGISTER_INODE(ip->i_ump->um_mountp, cg * fs->fs_ipg + ipref, 1352 mode); 1353 /* 1354 * Check to see if we need to initialize more inodes. 1355 */ 1356 if (ibp != NULL) { 1357 KASSERT(initediblk == ufs_rw32(cgp->cg_initediblk, needswap)); 1358 memset(ibp->b_data, 0, fs->fs_bsize); 1359 dp2 = (struct ufs2_dinode *)(ibp->b_data); 1360 for (i = 0; i < INOPB(fs); i++) { 1361 /* 1362 * Don't bother to swap, it's supposed to be 1363 * random, after all. 1364 */ 1365 dp2->di_gen = (arc4random() & INT32_MAX) / 2 + 1; 1366 dp2++; 1367 } 1368 initediblk += INOPB(fs); 1369 cgp->cg_initediblk = ufs_rw32(initediblk, needswap); 1370 } 1371 1372 mutex_enter(&ump->um_lock); 1373 ACTIVECG_CLR(fs, cg); 1374 setbit(inosused, ipref); 1375 ufs_add32(cgp->cg_cs.cs_nifree, -1, needswap); 1376 fs->fs_cstotal.cs_nifree--; 1377 fs->fs_cs(fs, cg).cs_nifree--; 1378 fs->fs_fmod = 1; 1379 if ((mode & IFMT) == IFDIR) { 1380 ufs_add32(cgp->cg_cs.cs_ndir, 1, needswap); 1381 fs->fs_cstotal.cs_ndir++; 1382 fs->fs_cs(fs, cg).cs_ndir++; 1383 } 1384 mutex_exit(&ump->um_lock); 1385 if (DOINGSOFTDEP(ITOV(ip))) 1386 softdep_setup_inomapdep(bp, ip, cg * fs->fs_ipg + ipref); 1387 if (ibp != NULL) { 1388 bwrite(bp); 1389 bawrite(ibp); 1390 } else 1391 bdwrite(bp); 1392 return (cg * fs->fs_ipg + ipref); 1393 fail: 1394 if (bp != NULL) 1395 brelse(bp, 0); 1396 if (ibp != NULL) 1397 brelse(ibp, BC_INVAL); 1398 mutex_enter(&ump->um_lock); 1399 return (0); 1400 } 1401 1402 /* 1403 * Allocate a block or fragment. 1404 * 1405 * The specified block or fragment is removed from the 1406 * free map, possibly fragmenting a block in the process. 1407 * 1408 * This implementation should mirror fs_blkfree 1409 * 1410 * => um_lock not held on entry or exit 1411 */ 1412 int 1413 ffs_blkalloc(struct inode *ip, daddr_t bno, long size) 1414 { 1415 int error; 1416 1417 error = ffs_check_bad_allocation(__func__, ip->i_fs, bno, size, 1418 ip->i_dev, ip->i_uid); 1419 if (error) 1420 return error; 1421 1422 return ffs_blkalloc_ump(ip->i_ump, bno, size); 1423 } 1424 1425 int 1426 ffs_blkalloc_ump(struct ufsmount *ump, daddr_t bno, long size) 1427 { 1428 struct fs *fs = ump->um_fs; 1429 struct cg *cgp; 1430 struct buf *bp; 1431 int32_t fragno, cgbno; 1432 int i, error, cg, blk, frags, bbase; 1433 u_int8_t *blksfree; 1434 const int needswap = UFS_FSNEEDSWAP(fs); 1435 1436 KASSERT((u_int)size <= fs->fs_bsize && fragoff(fs, size) == 0 && 1437 fragnum(fs, bno) + numfrags(fs, size) <= fs->fs_frag); 1438 KASSERT(bno < fs->fs_size); 1439 1440 cg = dtog(fs, bno); 1441 error = bread(ump->um_devvp, fsbtodb(fs, cgtod(fs, cg)), 1442 (int)fs->fs_cgsize, NOCRED, B_MODIFY, &bp); 1443 if (error) { 1444 brelse(bp, 0); 1445 return error; 1446 } 1447 cgp = (struct cg *)bp->b_data; 1448 if (!cg_chkmagic(cgp, needswap)) { 1449 brelse(bp, 0); 1450 return EIO; 1451 } 1452 cgp->cg_old_time = ufs_rw32(time_second, needswap); 1453 cgp->cg_time = ufs_rw64(time_second, needswap); 1454 cgbno = dtogd(fs, bno); 1455 blksfree = cg_blksfree(cgp, needswap); 1456 1457 mutex_enter(&ump->um_lock); 1458 if (size == fs->fs_bsize) { 1459 fragno = fragstoblks(fs, cgbno); 1460 if (!ffs_isblock(fs, blksfree, fragno)) { 1461 mutex_exit(&ump->um_lock); 1462 brelse(bp, 0); 1463 return EBUSY; 1464 } 1465 ffs_clrblock(fs, blksfree, fragno); 1466 ffs_clusteracct(fs, cgp, fragno, -1); 1467 ufs_add32(cgp->cg_cs.cs_nbfree, -1, needswap); 1468 fs->fs_cstotal.cs_nbfree--; 1469 fs->fs_cs(fs, cg).cs_nbfree--; 1470 } else { 1471 bbase = cgbno - fragnum(fs, cgbno); 1472 1473 frags = numfrags(fs, size); 1474 for (i = 0; i < frags; i++) { 1475 if (isclr(blksfree, cgbno + i)) { 1476 mutex_exit(&ump->um_lock); 1477 brelse(bp, 0); 1478 return EBUSY; 1479 } 1480 } 1481 /* 1482 * if a complete block is being split, account for it 1483 */ 1484 fragno = fragstoblks(fs, bbase); 1485 if (ffs_isblock(fs, blksfree, fragno)) { 1486 ufs_add32(cgp->cg_cs.cs_nffree, fs->fs_frag, needswap); 1487 fs->fs_cstotal.cs_nffree += fs->fs_frag; 1488 fs->fs_cs(fs, cg).cs_nffree += fs->fs_frag; 1489 ffs_clusteracct(fs, cgp, fragno, -1); 1490 ufs_add32(cgp->cg_cs.cs_nbfree, -1, needswap); 1491 fs->fs_cstotal.cs_nbfree--; 1492 fs->fs_cs(fs, cg).cs_nbfree--; 1493 } 1494 /* 1495 * decrement the counts associated with the old frags 1496 */ 1497 blk = blkmap(fs, blksfree, bbase); 1498 ffs_fragacct(fs, blk, cgp->cg_frsum, -1, needswap); 1499 /* 1500 * allocate the fragment 1501 */ 1502 for (i = 0; i < frags; i++) { 1503 clrbit(blksfree, cgbno + i); 1504 } 1505 ufs_add32(cgp->cg_cs.cs_nffree, -i, needswap); 1506 fs->fs_cstotal.cs_nffree -= i; 1507 fs->fs_cs(fs, cg).cs_nffree -= i; 1508 /* 1509 * add back in counts associated with the new frags 1510 */ 1511 blk = blkmap(fs, blksfree, bbase); 1512 ffs_fragacct(fs, blk, cgp->cg_frsum, 1, needswap); 1513 } 1514 fs->fs_fmod = 1; 1515 ACTIVECG_CLR(fs, cg); 1516 mutex_exit(&ump->um_lock); 1517 bdwrite(bp); 1518 return 0; 1519 } 1520 1521 /* 1522 * Free a block or fragment. 1523 * 1524 * The specified block or fragment is placed back in the 1525 * free map. If a fragment is deallocated, a possible 1526 * block reassembly is checked. 1527 * 1528 * => um_lock not held on entry or exit 1529 */ 1530 void 1531 ffs_blkfree(struct fs *fs, struct vnode *devvp, daddr_t bno, long size, 1532 ino_t inum) 1533 { 1534 struct cg *cgp; 1535 struct buf *bp; 1536 struct ufsmount *ump; 1537 daddr_t cgblkno; 1538 int error, cg; 1539 dev_t dev; 1540 const bool devvp_is_snapshot = (devvp->v_type != VBLK); 1541 #ifdef FFS_EI 1542 const int needswap = UFS_FSNEEDSWAP(fs); 1543 #endif 1544 1545 KASSERT(!devvp_is_snapshot); 1546 1547 cg = dtog(fs, bno); 1548 dev = devvp->v_rdev; 1549 ump = VFSTOUFS(devvp->v_specmountpoint); 1550 KASSERT(fs == ump->um_fs); 1551 cgblkno = fsbtodb(fs, cgtod(fs, cg)); 1552 if (ffs_snapblkfree(fs, devvp, bno, size, inum)) 1553 return; 1554 1555 error = ffs_check_bad_allocation(__func__, fs, bno, size, dev, inum); 1556 if (error) 1557 return; 1558 1559 error = bread(devvp, cgblkno, (int)fs->fs_cgsize, 1560 NOCRED, B_MODIFY, &bp); 1561 if (error) { 1562 brelse(bp, 0); 1563 return; 1564 } 1565 cgp = (struct cg *)bp->b_data; 1566 if (!cg_chkmagic(cgp, needswap)) { 1567 brelse(bp, 0); 1568 return; 1569 } 1570 1571 ffs_blkfree_common(ump, fs, dev, bp, bno, size, devvp_is_snapshot); 1572 1573 bdwrite(bp); 1574 } 1575 1576 /* 1577 * Free a block or fragment from a snapshot cg copy. 1578 * 1579 * The specified block or fragment is placed back in the 1580 * free map. If a fragment is deallocated, a possible 1581 * block reassembly is checked. 1582 * 1583 * => um_lock not held on entry or exit 1584 */ 1585 void 1586 ffs_blkfree_snap(struct fs *fs, struct vnode *devvp, daddr_t bno, long size, 1587 ino_t inum) 1588 { 1589 struct cg *cgp; 1590 struct buf *bp; 1591 struct ufsmount *ump; 1592 daddr_t cgblkno; 1593 int error, cg; 1594 dev_t dev; 1595 const bool devvp_is_snapshot = (devvp->v_type != VBLK); 1596 #ifdef FFS_EI 1597 const int needswap = UFS_FSNEEDSWAP(fs); 1598 #endif 1599 1600 KASSERT(devvp_is_snapshot); 1601 1602 cg = dtog(fs, bno); 1603 dev = VTOI(devvp)->i_devvp->v_rdev; 1604 ump = VFSTOUFS(devvp->v_mount); 1605 cgblkno = fragstoblks(fs, cgtod(fs, cg)); 1606 1607 error = ffs_check_bad_allocation(__func__, fs, bno, size, dev, inum); 1608 if (error) 1609 return; 1610 1611 error = bread(devvp, cgblkno, (int)fs->fs_cgsize, 1612 NOCRED, B_MODIFY, &bp); 1613 if (error) { 1614 brelse(bp, 0); 1615 return; 1616 } 1617 cgp = (struct cg *)bp->b_data; 1618 if (!cg_chkmagic(cgp, needswap)) { 1619 brelse(bp, 0); 1620 return; 1621 } 1622 1623 ffs_blkfree_common(ump, fs, dev, bp, bno, size, devvp_is_snapshot); 1624 1625 bdwrite(bp); 1626 } 1627 1628 static void 1629 ffs_blkfree_common(struct ufsmount *ump, struct fs *fs, dev_t dev, 1630 struct buf *bp, daddr_t bno, long size, bool devvp_is_snapshot) 1631 { 1632 struct cg *cgp; 1633 int32_t fragno, cgbno; 1634 int i, cg, blk, frags, bbase; 1635 u_int8_t *blksfree; 1636 const int needswap = UFS_FSNEEDSWAP(fs); 1637 1638 cg = dtog(fs, bno); 1639 cgp = (struct cg *)bp->b_data; 1640 cgp->cg_old_time = ufs_rw32(time_second, needswap); 1641 if ((fs->fs_magic != FS_UFS1_MAGIC) || 1642 (fs->fs_old_flags & FS_FLAGS_UPDATED)) 1643 cgp->cg_time = ufs_rw64(time_second, needswap); 1644 cgbno = dtogd(fs, bno); 1645 blksfree = cg_blksfree(cgp, needswap); 1646 mutex_enter(&ump->um_lock); 1647 if (size == fs->fs_bsize) { 1648 fragno = fragstoblks(fs, cgbno); 1649 if (!ffs_isfreeblock(fs, blksfree, fragno)) { 1650 if (devvp_is_snapshot) { 1651 mutex_exit(&ump->um_lock); 1652 return; 1653 } 1654 printf("dev = 0x%llx, block = %" PRId64 ", fs = %s\n", 1655 (unsigned long long)dev, bno, fs->fs_fsmnt); 1656 panic("blkfree: freeing free block"); 1657 } 1658 ffs_setblock(fs, blksfree, fragno); 1659 ffs_clusteracct(fs, cgp, fragno, 1); 1660 ufs_add32(cgp->cg_cs.cs_nbfree, 1, needswap); 1661 fs->fs_cstotal.cs_nbfree++; 1662 fs->fs_cs(fs, cg).cs_nbfree++; 1663 if ((fs->fs_magic == FS_UFS1_MAGIC) && 1664 ((fs->fs_old_flags & FS_FLAGS_UPDATED) == 0)) { 1665 i = old_cbtocylno(fs, cgbno); 1666 KASSERT(i >= 0); 1667 KASSERT(i < fs->fs_old_ncyl); 1668 KASSERT(old_cbtorpos(fs, cgbno) >= 0); 1669 KASSERT(fs->fs_old_nrpos == 0 || old_cbtorpos(fs, cgbno) < fs->fs_old_nrpos); 1670 ufs_add16(old_cg_blks(fs, cgp, i, needswap)[old_cbtorpos(fs, cgbno)], 1, 1671 needswap); 1672 ufs_add32(old_cg_blktot(cgp, needswap)[i], 1, needswap); 1673 } 1674 } else { 1675 bbase = cgbno - fragnum(fs, cgbno); 1676 /* 1677 * decrement the counts associated with the old frags 1678 */ 1679 blk = blkmap(fs, blksfree, bbase); 1680 ffs_fragacct(fs, blk, cgp->cg_frsum, -1, needswap); 1681 /* 1682 * deallocate the fragment 1683 */ 1684 frags = numfrags(fs, size); 1685 for (i = 0; i < frags; i++) { 1686 if (isset(blksfree, cgbno + i)) { 1687 printf("dev = 0x%llx, block = %" PRId64 1688 ", fs = %s\n", 1689 (unsigned long long)dev, bno + i, 1690 fs->fs_fsmnt); 1691 panic("blkfree: freeing free frag"); 1692 } 1693 setbit(blksfree, cgbno + i); 1694 } 1695 ufs_add32(cgp->cg_cs.cs_nffree, i, needswap); 1696 fs->fs_cstotal.cs_nffree += i; 1697 fs->fs_cs(fs, cg).cs_nffree += i; 1698 /* 1699 * add back in counts associated with the new frags 1700 */ 1701 blk = blkmap(fs, blksfree, bbase); 1702 ffs_fragacct(fs, blk, cgp->cg_frsum, 1, needswap); 1703 /* 1704 * if a complete block has been reassembled, account for it 1705 */ 1706 fragno = fragstoblks(fs, bbase); 1707 if (ffs_isblock(fs, blksfree, fragno)) { 1708 ufs_add32(cgp->cg_cs.cs_nffree, -fs->fs_frag, needswap); 1709 fs->fs_cstotal.cs_nffree -= fs->fs_frag; 1710 fs->fs_cs(fs, cg).cs_nffree -= fs->fs_frag; 1711 ffs_clusteracct(fs, cgp, fragno, 1); 1712 ufs_add32(cgp->cg_cs.cs_nbfree, 1, needswap); 1713 fs->fs_cstotal.cs_nbfree++; 1714 fs->fs_cs(fs, cg).cs_nbfree++; 1715 if ((fs->fs_magic == FS_UFS1_MAGIC) && 1716 ((fs->fs_old_flags & FS_FLAGS_UPDATED) == 0)) { 1717 i = old_cbtocylno(fs, bbase); 1718 KASSERT(i >= 0); 1719 KASSERT(i < fs->fs_old_ncyl); 1720 KASSERT(old_cbtorpos(fs, bbase) >= 0); 1721 KASSERT(fs->fs_old_nrpos == 0 || old_cbtorpos(fs, bbase) < fs->fs_old_nrpos); 1722 ufs_add16(old_cg_blks(fs, cgp, i, needswap)[old_cbtorpos(fs, 1723 bbase)], 1, needswap); 1724 ufs_add32(old_cg_blktot(cgp, needswap)[i], 1, needswap); 1725 } 1726 } 1727 } 1728 fs->fs_fmod = 1; 1729 ACTIVECG_CLR(fs, cg); 1730 mutex_exit(&ump->um_lock); 1731 } 1732 1733 /* 1734 * Free an inode. 1735 */ 1736 int 1737 ffs_vfree(struct vnode *vp, ino_t ino, int mode) 1738 { 1739 1740 if (DOINGSOFTDEP(vp)) { 1741 softdep_freefile(vp, ino, mode); 1742 return (0); 1743 } 1744 return ffs_freefile(vp->v_mount, ino, mode); 1745 } 1746 1747 /* 1748 * Do the actual free operation. 1749 * The specified inode is placed back in the free map. 1750 * 1751 * => um_lock not held on entry or exit 1752 */ 1753 int 1754 ffs_freefile(struct mount *mp, ino_t ino, int mode) 1755 { 1756 struct ufsmount *ump = VFSTOUFS(mp); 1757 struct fs *fs = ump->um_fs; 1758 struct vnode *devvp; 1759 struct cg *cgp; 1760 struct buf *bp; 1761 int error, cg; 1762 daddr_t cgbno; 1763 dev_t dev; 1764 #ifdef FFS_EI 1765 const int needswap = UFS_FSNEEDSWAP(fs); 1766 #endif 1767 1768 cg = ino_to_cg(fs, ino); 1769 devvp = ump->um_devvp; 1770 dev = devvp->v_rdev; 1771 cgbno = fsbtodb(fs, cgtod(fs, cg)); 1772 1773 if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 1774 panic("ifree: range: dev = 0x%llx, ino = %llu, fs = %s", 1775 (long long)dev, (unsigned long long)ino, fs->fs_fsmnt); 1776 error = bread(devvp, cgbno, (int)fs->fs_cgsize, 1777 NOCRED, B_MODIFY, &bp); 1778 if (error) { 1779 brelse(bp, 0); 1780 return (error); 1781 } 1782 cgp = (struct cg *)bp->b_data; 1783 if (!cg_chkmagic(cgp, needswap)) { 1784 brelse(bp, 0); 1785 return (0); 1786 } 1787 1788 ffs_freefile_common(ump, fs, dev, bp, ino, mode, false); 1789 1790 bdwrite(bp); 1791 1792 return 0; 1793 } 1794 1795 int 1796 ffs_freefile_snap(struct fs *fs, struct vnode *devvp, ino_t ino, int mode) 1797 { 1798 struct ufsmount *ump; 1799 struct cg *cgp; 1800 struct buf *bp; 1801 int error, cg; 1802 daddr_t cgbno; 1803 dev_t dev; 1804 #ifdef FFS_EI 1805 const int needswap = UFS_FSNEEDSWAP(fs); 1806 #endif 1807 1808 KASSERT(devvp->v_type != VBLK); 1809 1810 cg = ino_to_cg(fs, ino); 1811 dev = VTOI(devvp)->i_devvp->v_rdev; 1812 ump = VFSTOUFS(devvp->v_mount); 1813 cgbno = fragstoblks(fs, cgtod(fs, cg)); 1814 if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 1815 panic("ifree: range: dev = 0x%llx, ino = %llu, fs = %s", 1816 (unsigned long long)dev, (unsigned long long)ino, 1817 fs->fs_fsmnt); 1818 error = bread(devvp, cgbno, (int)fs->fs_cgsize, 1819 NOCRED, B_MODIFY, &bp); 1820 if (error) { 1821 brelse(bp, 0); 1822 return (error); 1823 } 1824 cgp = (struct cg *)bp->b_data; 1825 if (!cg_chkmagic(cgp, needswap)) { 1826 brelse(bp, 0); 1827 return (0); 1828 } 1829 ffs_freefile_common(ump, fs, dev, bp, ino, mode, true); 1830 1831 bdwrite(bp); 1832 1833 return 0; 1834 } 1835 1836 static void 1837 ffs_freefile_common(struct ufsmount *ump, struct fs *fs, dev_t dev, 1838 struct buf *bp, ino_t ino, int mode, bool devvp_is_snapshot) 1839 { 1840 int cg; 1841 struct cg *cgp; 1842 u_int8_t *inosused; 1843 #ifdef FFS_EI 1844 const int needswap = UFS_FSNEEDSWAP(fs); 1845 #endif 1846 1847 cg = ino_to_cg(fs, ino); 1848 cgp = (struct cg *)bp->b_data; 1849 cgp->cg_old_time = ufs_rw32(time_second, needswap); 1850 if ((fs->fs_magic != FS_UFS1_MAGIC) || 1851 (fs->fs_old_flags & FS_FLAGS_UPDATED)) 1852 cgp->cg_time = ufs_rw64(time_second, needswap); 1853 inosused = cg_inosused(cgp, needswap); 1854 ino %= fs->fs_ipg; 1855 if (isclr(inosused, ino)) { 1856 printf("ifree: dev = 0x%llx, ino = %llu, fs = %s\n", 1857 (unsigned long long)dev, (unsigned long long)ino + 1858 cg * fs->fs_ipg, fs->fs_fsmnt); 1859 if (fs->fs_ronly == 0) 1860 panic("ifree: freeing free inode"); 1861 } 1862 clrbit(inosused, ino); 1863 if (!devvp_is_snapshot) 1864 UFS_WAPBL_UNREGISTER_INODE(ump->um_mountp, 1865 ino + cg * fs->fs_ipg, mode); 1866 if (ino < ufs_rw32(cgp->cg_irotor, needswap)) 1867 cgp->cg_irotor = ufs_rw32(ino, needswap); 1868 ufs_add32(cgp->cg_cs.cs_nifree, 1, needswap); 1869 mutex_enter(&ump->um_lock); 1870 fs->fs_cstotal.cs_nifree++; 1871 fs->fs_cs(fs, cg).cs_nifree++; 1872 if ((mode & IFMT) == IFDIR) { 1873 ufs_add32(cgp->cg_cs.cs_ndir, -1, needswap); 1874 fs->fs_cstotal.cs_ndir--; 1875 fs->fs_cs(fs, cg).cs_ndir--; 1876 } 1877 fs->fs_fmod = 1; 1878 ACTIVECG_CLR(fs, cg); 1879 mutex_exit(&ump->um_lock); 1880 } 1881 1882 /* 1883 * Check to see if a file is free. 1884 */ 1885 int 1886 ffs_checkfreefile(struct fs *fs, struct vnode *devvp, ino_t ino) 1887 { 1888 struct cg *cgp; 1889 struct buf *bp; 1890 daddr_t cgbno; 1891 int ret, cg; 1892 u_int8_t *inosused; 1893 const bool devvp_is_snapshot = (devvp->v_type != VBLK); 1894 1895 KASSERT(devvp_is_snapshot); 1896 1897 cg = ino_to_cg(fs, ino); 1898 if (devvp_is_snapshot) 1899 cgbno = fragstoblks(fs, cgtod(fs, cg)); 1900 else 1901 cgbno = fsbtodb(fs, cgtod(fs, cg)); 1902 if ((u_int)ino >= fs->fs_ipg * fs->fs_ncg) 1903 return 1; 1904 if (bread(devvp, cgbno, (int)fs->fs_cgsize, NOCRED, 0, &bp)) { 1905 brelse(bp, 0); 1906 return 1; 1907 } 1908 cgp = (struct cg *)bp->b_data; 1909 if (!cg_chkmagic(cgp, UFS_FSNEEDSWAP(fs))) { 1910 brelse(bp, 0); 1911 return 1; 1912 } 1913 inosused = cg_inosused(cgp, UFS_FSNEEDSWAP(fs)); 1914 ino %= fs->fs_ipg; 1915 ret = isclr(inosused, ino); 1916 brelse(bp, 0); 1917 return ret; 1918 } 1919 1920 /* 1921 * Find a block of the specified size in the specified cylinder group. 1922 * 1923 * It is a panic if a request is made to find a block if none are 1924 * available. 1925 */ 1926 static int32_t 1927 ffs_mapsearch(struct fs *fs, struct cg *cgp, daddr_t bpref, int allocsiz) 1928 { 1929 int32_t bno; 1930 int start, len, loc, i; 1931 int blk, field, subfield, pos; 1932 int ostart, olen; 1933 u_int8_t *blksfree; 1934 #ifdef FFS_EI 1935 const int needswap = UFS_FSNEEDSWAP(fs); 1936 #endif 1937 1938 /* KASSERT(mutex_owned(&ump->um_lock)); */ 1939 1940 /* 1941 * find the fragment by searching through the free block 1942 * map for an appropriate bit pattern 1943 */ 1944 if (bpref) 1945 start = dtogd(fs, bpref) / NBBY; 1946 else 1947 start = ufs_rw32(cgp->cg_frotor, needswap) / NBBY; 1948 blksfree = cg_blksfree(cgp, needswap); 1949 len = howmany(fs->fs_fpg, NBBY) - start; 1950 ostart = start; 1951 olen = len; 1952 loc = scanc((u_int)len, 1953 (const u_char *)&blksfree[start], 1954 (const u_char *)fragtbl[fs->fs_frag], 1955 (1 << (allocsiz - 1 + (fs->fs_frag & (NBBY - 1))))); 1956 if (loc == 0) { 1957 len = start + 1; 1958 start = 0; 1959 loc = scanc((u_int)len, 1960 (const u_char *)&blksfree[0], 1961 (const u_char *)fragtbl[fs->fs_frag], 1962 (1 << (allocsiz - 1 + (fs->fs_frag & (NBBY - 1))))); 1963 if (loc == 0) { 1964 printf("start = %d, len = %d, fs = %s\n", 1965 ostart, olen, fs->fs_fsmnt); 1966 printf("offset=%d %ld\n", 1967 ufs_rw32(cgp->cg_freeoff, needswap), 1968 (long)blksfree - (long)cgp); 1969 printf("cg %d\n", cgp->cg_cgx); 1970 panic("ffs_alloccg: map corrupted"); 1971 /* NOTREACHED */ 1972 } 1973 } 1974 bno = (start + len - loc) * NBBY; 1975 cgp->cg_frotor = ufs_rw32(bno, needswap); 1976 /* 1977 * found the byte in the map 1978 * sift through the bits to find the selected frag 1979 */ 1980 for (i = bno + NBBY; bno < i; bno += fs->fs_frag) { 1981 blk = blkmap(fs, blksfree, bno); 1982 blk <<= 1; 1983 field = around[allocsiz]; 1984 subfield = inside[allocsiz]; 1985 for (pos = 0; pos <= fs->fs_frag - allocsiz; pos++) { 1986 if ((blk & field) == subfield) 1987 return (bno + pos); 1988 field <<= 1; 1989 subfield <<= 1; 1990 } 1991 } 1992 printf("bno = %d, fs = %s\n", bno, fs->fs_fsmnt); 1993 panic("ffs_alloccg: block not in map"); 1994 /* return (-1); */ 1995 } 1996 1997 /* 1998 * Update the cluster map because of an allocation or free. 1999 * 2000 * Cnt == 1 means free; cnt == -1 means allocating. 2001 */ 2002 void 2003 ffs_clusteracct(struct fs *fs, struct cg *cgp, int32_t blkno, int cnt) 2004 { 2005 int32_t *sump; 2006 int32_t *lp; 2007 u_char *freemapp, *mapp; 2008 int i, start, end, forw, back, map, bit; 2009 #ifdef FFS_EI 2010 const int needswap = UFS_FSNEEDSWAP(fs); 2011 #endif 2012 2013 /* KASSERT(mutex_owned(&ump->um_lock)); */ 2014 2015 if (fs->fs_contigsumsize <= 0) 2016 return; 2017 freemapp = cg_clustersfree(cgp, needswap); 2018 sump = cg_clustersum(cgp, needswap); 2019 /* 2020 * Allocate or clear the actual block. 2021 */ 2022 if (cnt > 0) 2023 setbit(freemapp, blkno); 2024 else 2025 clrbit(freemapp, blkno); 2026 /* 2027 * Find the size of the cluster going forward. 2028 */ 2029 start = blkno + 1; 2030 end = start + fs->fs_contigsumsize; 2031 if (end >= ufs_rw32(cgp->cg_nclusterblks, needswap)) 2032 end = ufs_rw32(cgp->cg_nclusterblks, needswap); 2033 mapp = &freemapp[start / NBBY]; 2034 map = *mapp++; 2035 bit = 1 << (start % NBBY); 2036 for (i = start; i < end; i++) { 2037 if ((map & bit) == 0) 2038 break; 2039 if ((i & (NBBY - 1)) != (NBBY - 1)) { 2040 bit <<= 1; 2041 } else { 2042 map = *mapp++; 2043 bit = 1; 2044 } 2045 } 2046 forw = i - start; 2047 /* 2048 * Find the size of the cluster going backward. 2049 */ 2050 start = blkno - 1; 2051 end = start - fs->fs_contigsumsize; 2052 if (end < 0) 2053 end = -1; 2054 mapp = &freemapp[start / NBBY]; 2055 map = *mapp--; 2056 bit = 1 << (start % NBBY); 2057 for (i = start; i > end; i--) { 2058 if ((map & bit) == 0) 2059 break; 2060 if ((i & (NBBY - 1)) != 0) { 2061 bit >>= 1; 2062 } else { 2063 map = *mapp--; 2064 bit = 1 << (NBBY - 1); 2065 } 2066 } 2067 back = start - i; 2068 /* 2069 * Account for old cluster and the possibly new forward and 2070 * back clusters. 2071 */ 2072 i = back + forw + 1; 2073 if (i > fs->fs_contigsumsize) 2074 i = fs->fs_contigsumsize; 2075 ufs_add32(sump[i], cnt, needswap); 2076 if (back > 0) 2077 ufs_add32(sump[back], -cnt, needswap); 2078 if (forw > 0) 2079 ufs_add32(sump[forw], -cnt, needswap); 2080 2081 /* 2082 * Update cluster summary information. 2083 */ 2084 lp = &sump[fs->fs_contigsumsize]; 2085 for (i = fs->fs_contigsumsize; i > 0; i--) 2086 if (ufs_rw32(*lp--, needswap) > 0) 2087 break; 2088 fs->fs_maxcluster[ufs_rw32(cgp->cg_cgx, needswap)] = i; 2089 } 2090 2091 /* 2092 * Fserr prints the name of a file system with an error diagnostic. 2093 * 2094 * The form of the error message is: 2095 * fs: error message 2096 */ 2097 static void 2098 ffs_fserr(struct fs *fs, u_int uid, const char *cp) 2099 { 2100 2101 log(LOG_ERR, "uid %d, pid %d, command %s, on %s: %s\n", 2102 uid, curproc->p_pid, curproc->p_comm, fs->fs_fsmnt, cp); 2103 } 2104
Indexes created Tue Oct 14 00:09:49 GMT 2025