1 /* $NetBSD: lfs_alloc.c,v 1.155 2026/08/27 14:33:13 perseant Exp $ */ 2 3 /*- 4 * Copyright (c) 1999, 2000, 2001, 2002, 2003, 2007 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Konrad E. Schroder <perseant (at) hhhh.org>. 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 * Copyright (c) 1991, 1993 33 * The Regents of the University of California. All rights reserved. 34 * 35 * Redistribution and use in source and binary forms, with or without 36 * modification, are permitted provided that the following conditions 37 * are met: 38 * 1. Redistributions of source code must retain the above copyright 39 * notice, this list of conditions and the following disclaimer. 40 * 2. Redistributions in binary form must reproduce the above copyright 41 * notice, this list of conditions and the following disclaimer in the 42 * documentation and/or other materials provided with the distribution. 43 * 3. Neither the name of the University nor the names of its contributors 44 * may be used to endorse or promote products derived from this software 45 * without specific prior written permission. 46 * 47 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 48 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 49 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 50 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 51 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 52 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 53 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 54 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 55 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 56 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 57 * SUCH DAMAGE. 58 * 59 * @(#)lfs_alloc.c 8.4 (Berkeley) 1/4/94 60 */ 61 62 #include <sys/cdefs.h> 63 __KERNEL_RCSID(0, "$NetBSD: lfs_alloc.c,v 1.155 2026/08/27 14:33:13 perseant Exp $"); 64 65 #if defined(_KERNEL_OPT) 66 #include "opt_quota.h" 67 #endif 68 69 #include <sys/param.h> 70 #include <sys/systm.h> 71 #include <sys/kernel.h> 72 #include <sys/buf.h> 73 #include <sys/lock.h> 74 #include <sys/vnode.h> 75 #include <sys/syslog.h> 76 #include <sys/mount.h> 77 #include <sys/malloc.h> 78 #include <sys/pool.h> 79 #include <sys/proc.h> 80 #include <sys/kauth.h> 81 82 #include <ufs/lfs/ulfs_quotacommon.h> 83 #include <ufs/lfs/ulfs_inode.h> 84 #include <ufs/lfs/ulfsmount.h> 85 #include <ufs/lfs/ulfs_extern.h> 86 87 #include <ufs/lfs/lfs.h> 88 #include <ufs/lfs/lfs_accessors.h> 89 #include <ufs/lfs/lfs_extern.h> 90 #include <ufs/lfs/lfs_kernel.h> 91 92 int lfs_do_check_freelist = 0; 93 94 /* 95 * Add a new block to the Ifile, to accommodate future file creations. 96 * Called with the segment lock held. 97 */ 98 int 99 lfs_extend_ifile(struct lfs *fs, kauth_cred_t cred) 100 { 101 struct vnode *vp; 102 struct inode *ip; 103 IFILE64 *ifp64; 104 IFILE32 *ifp32; 105 IFILE_V1 *ifp_v1; 106 struct buf *bp, *cbp; 107 int error; 108 daddr_t i, blkno, xmax; 109 ino_t oldhead, tail; 110 CLEANERINFO *cip; 111 112 ASSERT_SEGLOCK(fs); 113 114 /* XXX should check or assert that we aren't readonly. */ 115 116 /* 117 * Get a block and extend the ifile inode. Leave the buffer for 118 * the block in bp. 119 */ 120 121 vp = fs->lfs_ivnode; 122 ip = VTOI(vp); 123 blkno = lfs_lblkno(fs, ip->i_size); 124 if ((error = lfs_balloc(vp, ip->i_size, lfs_sb_getbsize(fs), cred, 0, 125 &bp)) != 0) { 126 return (error); 127 } 128 ip->i_size += lfs_sb_getbsize(fs); 129 lfs_dino_setsize(fs, ip->i_din, ip->i_size); 130 uvm_vnp_setsize(vp, ip->i_size); 131 132 /* 133 * Compute the new number of inodes, and reallocate the in-memory 134 * inode freemap. 135 */ 136 137 /* first new inode number */ 138 i = (blkno - lfs_sb_getsegtabsz(fs) - lfs_sb_getcleansz(fs)) * 139 lfs_sb_getifpb(fs); 140 141 /* inode number to stop at (XXX: why *x*max?) */ 142 xmax = i + lfs_sb_getifpb(fs); 143 144 /* 145 * We insert the new inodes at the head of the free list. 146 * Under normal circumstances, the free list is empty here, 147 * so we are also incidentally placing them at the end (which 148 * we must do if we are to keep them in order). 149 */ 150 LFS_GET_HEADFREE(fs, cip, cbp, &oldhead); 151 LFS_PUT_HEADFREE(fs, cip, cbp, i); 152 LFS_GET_TAILFREE(fs, cip, cbp, &tail); 153 DLOG((DLOG_ALLOC, "oldhead=%jd, i=%jd, xmax=%jd, oldtail=%jd\n", 154 (intmax_t)oldhead, (intmax_t)i, (intmax_t)xmax, 155 (intmax_t)tail)); 156 if (tail == LFS_UNUSED_INUM) { 157 tail = xmax - 1; 158 LFS_PUT_TAILFREE(fs, cip, cbp, tail); 159 } 160 KASSERTMSG((lfs_sb_getfreehd(fs) != LFS_UNUSED_INUM), 161 "inode 0 allocated [2]"); 162 163 164 /* 165 * Initialize the ifile block. 166 * 167 * XXX: these loops should be restructured to use the accessor 168 * functions instead of using cutpaste polymorphism. 169 */ 170 171 if (fs->lfs_is64) { 172 for (ifp64 = (IFILE64 *)bp->b_data; i < xmax; ++ifp64) { 173 ifp64->if_version = 1; 174 ifp64->if_daddr = LFS_UNUSED_DADDR; 175 ifp64->if_nextfree = ++i; 176 } 177 ifp64--; 178 ifp64->if_nextfree = oldhead; 179 } else if (lfs_sb_getversion(fs) > 1) { 180 for (ifp32 = (IFILE32 *)bp->b_data; i < xmax; ++ifp32) { 181 ifp32->if_version = 1; 182 ifp32->if_daddr = LFS_UNUSED_DADDR; 183 ifp32->if_nextfree = ++i; 184 } 185 ifp32--; 186 ifp32->if_nextfree = oldhead; 187 } else { 188 for (ifp_v1 = (IFILE_V1 *)bp->b_data; i < xmax; ++ifp_v1) { 189 ifp_v1->if_version = 1; 190 ifp_v1->if_daddr = LFS_UNUSED_DADDR; 191 ifp_v1->if_nextfree = ++i; 192 } 193 ifp_v1--; 194 ifp_v1->if_nextfree = oldhead; 195 } 196 DLOG((DLOG_ALLOC, " now head=%jd tail=%jd\n", 197 (intmax_t)xmax - lfs_sb_getifpb(fs), (intmax_t)tail)); 198 199 /* 200 * Write out the new block. 201 */ 202 203 (void) LFS_BWRITE_LOG(bp); /* Ifile */ 204 205 return 0; 206 } 207 208 /* 209 * Allocate an inode for a new file. 210 * 211 * Takes the segment lock. Also (while holding it) takes lfs_lock 212 * to frob fs->lfs_fmod. 213 * 214 * XXX: the mode argument is unused; should just get rid of it. 215 */ 216 /* ARGSUSED */ 217 /* VOP_BWRITE 2i times */ 218 int 219 lfs_valloc(struct vnode *pvp, int mode, kauth_cred_t cred, 220 ino_t *ino, int *gen) 221 { 222 struct lfs *fs; 223 struct buf *bp, *cbp; 224 IFILE *ifp; 225 int error; 226 CLEANERINFO *cip; 227 228 fs = VTOI(pvp)->i_lfs; 229 if (fs->lfs_ronly) 230 return EROFS; 231 232 if (!(fs->lfs_flags & LFS_NOTYET)) 233 ASSERT_NO_SEGLOCK(fs); 234 235 DEBUG_CHECK_FREELIST(fs); 236 237 lfs_prelock(fs, 0); 238 239 /* Get the head of the freelist. */ 240 LFS_GET_HEADFREE(fs, cip, cbp, ino); 241 242 /* paranoia */ 243 KASSERT(*ino != LFS_UNUSED_INUM && *ino != LFS_IFILE_INUM); 244 DLOG((DLOG_ALLOC, "lfs_valloc: allocate inode %" PRId64 "\n", 245 *ino)); 246 247 /* 248 * Fetch the ifile entry and make sure the inode is really 249 * free. 250 */ 251 LFS_IENTRY(ifp, fs, *ino, bp); 252 if (lfs_if_getdaddr(fs, ifp) != LFS_UNUSED_DADDR) 253 panic("lfs_valloc: inuse inode %" PRId64 " on the free list", 254 *ino); 255 256 /* Update the inode freelist head in the superblock. */ 257 LFS_PUT_HEADFREE(fs, cip, cbp, lfs_if_getnextfree(fs, ifp)); 258 DLOG((DLOG_ALLOC, "lfs_valloc: headfree %" PRId64 " -> %ju\n", 259 *ino, (uintmax_t)lfs_if_getnextfree(fs, ifp))); 260 261 /* 262 * Retrieve the version number from the ifile entry. It was 263 * bumped by vfree, so don't bump it again. 264 */ 265 *gen = lfs_if_getversion(fs, ifp); 266 267 /* Done with ifile entry */ 268 269 /* 270 * Note LFS_ILLEGAL_DADDR == LFS_UNUSED_DADDR 271 * unless DEBUG is set. In that case we 272 * use that address to track inodes that have been 273 * allocated (and so not on the free list) but do not 274 * have proper disk addresses yet. 275 */ 276 lfs_if_setdaddr(fs, ifp, LFS_ILLEGAL_DADDR); 277 lfs_if_setnextfree(fs, ifp, LFS_UNUSED_INUM); 278 LFS_WRITEIENTRY(ifp, fs, *ino, bp); 279 280 if (lfs_sb_getfreehd(fs) == LFS_UNUSED_INUM) { 281 /* 282 * No more inodes; extend the ifile so that the next 283 * lfs_valloc will succeed. 284 */ 285 if ((error = lfs_extend_ifile(fs, cred)) != 0) { 286 /* restore the freelist */ 287 LFS_PUT_HEADFREE(fs, cip, cbp, *ino); 288 289 /* unlock and return */ 290 lfs_preunlock(fs); 291 return error; 292 } 293 } 294 KASSERTMSG((lfs_sb_getfreehd(fs) != LFS_UNUSED_INUM), 295 "inode 0 allocated [3]"); 296 297 /* Set superblock modified bit */ 298 mutex_enter(&lfs_lock); 299 fs->lfs_fmod = 1; 300 mutex_exit(&lfs_lock); 301 302 /* increment file count */ 303 lfs_sb_addnfiles(fs, 1); 304 305 /* done */ 306 lfs_preunlock(fs); 307 308 DEBUG_CHECK_FREELIST(fs); 309 return 0; 310 } 311 312 /* 313 * Allocate an inode for a new file, with given inode number and 314 * version. 315 * 316 * Called in the same context as lfs_valloc and therefore shares the 317 * same locking assumptions. 318 */ 319 int 320 lfs_valloc_fixed(struct lfs *fs, ino_t ino, int vers) 321 { 322 IFILE *ifp; 323 struct buf *bp, *cbp; 324 ino_t headino, thisino, oldnext, tailino; 325 CLEANERINFO *cip; 326 int extended = 0; 327 328 if (fs->lfs_ronly) 329 return EROFS; 330 331 if (!(fs->lfs_flags & LFS_NOTYET)) 332 ASSERT_NO_SEGLOCK(fs); 333 334 DEBUG_CHECK_FREELIST(fs); 335 336 lfs_prelock(fs, 0); 337 338 /* 339 * If the ifile is too short to contain this inum, extend it. 340 * 341 * XXX: lfs_extend_ifile should take a size instead of always 342 * doing just one block at time. 343 */ 344 while (VTOI(fs->lfs_ivnode)->i_size <= (ino / 345 lfs_sb_getifpb(fs) + lfs_sb_getcleansz(fs) + lfs_sb_getsegtabsz(fs)) 346 << lfs_sb_getbshift(fs)) { 347 DLOG((DLOG_ALLOC, "extend ifile to accommodate ino %jd\n", 348 (intmax_t)ino)); 349 lfs_extend_ifile(fs, NOCRED); 350 extended = 1; 351 } 352 353 /* 354 * Get the inode freelist next pointer. 355 */ 356 LFS_IENTRY(ifp, fs, ino, bp); 357 oldnext = lfs_if_getnextfree(fs, ifp); 358 brelse(bp, 0); 359 360 /* Get fail of inode freelist */ 361 LFS_GET_TAILFREE(fs, cip, cbp, &tailino); 362 363 /* Get head of inode freelist */ 364 LFS_GET_HEADFREE(fs, cip, cbp, &headino); 365 if (headino == ino) { 366 /* Easy case: the inode we wanted was at the head */ 367 LFS_PUT_HEADFREE(fs, cip, cbp, oldnext); 368 } else { 369 ino_t nextfree = 0, maxino, count; /* XXX: gcc */ 370 371 /* Have to find the desired inode in the freelist... */ 372 maxino = ((VTOI(fs->lfs_ivnode)->i_size >> lfs_sb_getbshift(fs)) 373 - lfs_sb_getcleansz(fs) - lfs_sb_getsegtabsz(fs)) 374 * lfs_sb_getifpb(fs); 375 count = 0; 376 377 thisino = headino; 378 while (thisino != LFS_UNUSED_INUM) { 379 /* read this ifile entry */ 380 LFS_IENTRY(ifp, fs, thisino, bp); 381 nextfree = lfs_if_getnextfree(fs, ifp); 382 /* stop if we find it or we hit the end */ 383 if (nextfree == ino || 384 nextfree == LFS_UNUSED_INUM) 385 break; 386 /* nope, keep going... */ 387 thisino = nextfree; 388 brelse(bp, 0); 389 if (++count > maxino) 390 break; 391 } 392 if (count > maxino) { 393 panic("loop in free list"); 394 lfs_preunlock(fs); 395 return ENOENT; 396 } 397 if (nextfree == LFS_UNUSED_INUM) { 398 /* hit the end -- this inode is not available */ 399 brelse(bp, 0); 400 lfs_preunlock(fs); 401 if (extended) 402 panic("extended ifile to accommodate but inode not found"); 403 return ENOENT; 404 } 405 /* found it; update the next pointer */ 406 lfs_if_setnextfree(fs, ifp, oldnext); 407 /* write the ifile block */ 408 LFS_BWRITE_LOG(bp); 409 410 /* If our inode was the tail, thisino is now the tail */ 411 if (tailino == ino) 412 LFS_PUT_TAILFREE(fs, cip, cbp, thisino); 413 } 414 415 /* Clear nextfree, note daddr, and set generation number */ 416 LFS_IENTRY(ifp, fs, ino, bp); 417 lfs_if_setversion(fs, ifp, vers); 418 lfs_if_setnextfree(fs, ifp, LFS_UNUSED_INUM); 419 /* See comment in lfs_valloc */ 420 lfs_if_setdaddr(fs, ifp, LFS_ILLEGAL_DADDR); 421 LFS_WRITEIENTRY(ifp, fs, ino, bp); 422 423 if (lfs_sb_getfreehd(fs) == LFS_UNUSED_INUM) { 424 int error; 425 /* 426 * No more inodes; extend the ifile so that the next 427 * lfs_valloc will succeed. 428 */ 429 if ((error = lfs_extend_ifile(fs, NOCRED)) != 0) { 430 /* restore the freelist */ 431 LFS_PUT_HEADFREE(fs, cip, cbp, ino); 432 433 /* unlock and return */ 434 lfs_preunlock(fs); 435 return error; 436 } 437 } 438 KASSERTMSG((lfs_sb_getfreehd(fs) != LFS_UNUSED_INUM), 439 "inode 0 allocated [4]"); 440 441 /* done */ 442 lfs_preunlock(fs); 443 444 DEBUG_CHECK_FREELIST(fs); 445 446 return 0; 447 } 448 449 /* 450 * Free an inode. 451 * 452 * Takes lfs_prelock. Also (independently) takes vp->v_interlock. 453 */ 454 /* ARGUSED */ 455 /* VOP_BWRITE 2i times */ 456 int 457 lfs_vfree(struct vnode *vp, ino_t ino, int mode) 458 { 459 CLEANERINFO *cip; 460 struct buf *cbp, *bp; 461 IFILE *ifp; 462 struct inode *ip; 463 struct lfs *fs; 464 struct segdelta *isd, *fsd, *tmp; 465 466 /* Get the inode number and file system. */ 467 ip = VTOI(vp); 468 fs = ip->i_lfs; 469 ino = ip->i_number; 470 471 ASSERT_NO_SEGLOCK(fs); 472 KASSERTMSG((ino != LFS_UNUSED_INUM), "inode 0 freed"); 473 KASSERT(!fs->lfs_ronly); 474 475 DLOG((DLOG_ALLOC, "lfs_vfree: free ino %lld\n", (long long)ino)); 476 477 /* Drain of pending writes */ 478 mutex_enter(vp->v_interlock); 479 while (lfs_sb_getversion(fs) > 1 && WRITEINPROG(vp)) { 480 cv_wait(&vp->v_cv, vp->v_interlock); 481 } 482 mutex_exit(vp->v_interlock); 483 484 lfs_prelock(fs, 0); 485 486 DEBUG_CHECK_FREELIST(fs); 487 488 /* 489 * If the inode was in a dirop, it isn't now. 490 * 491 * XXX: why are (v_uflag & VU_DIROP) and (ip->i_state & IN_ADIROP) 492 * not updated together in one function? (and why do both exist, 493 * anyway?) 494 */ 495 UNMARK_VNODE(vp); 496 497 mutex_enter(&lfs_lock); 498 if (vp->v_uflag & VU_DIROP) { 499 vp->v_uflag &= ~VU_DIROP; 500 --lfs_dirvcount; 501 --fs->lfs_dirvcount; 502 TAILQ_REMOVE(&fs->lfs_dchainhd, ip, i_lfs_dchain); 503 wakeup(&fs->lfs_dirvcount); 504 wakeup(&lfs_dirvcount); 505 mutex_exit(&lfs_lock); 506 vrele(vp); 507 508 /* 509 * If this inode is not going to be written any more, any 510 * segment accounting left over from its truncation needs 511 * to occur at the end of the next dirops flush. Move 512 * it to the fs-wide list for that purpose. 513 */ 514 RB_TREE_FOREACH_SAFE(isd, &ip->i_lfs_segdhd, tmp) { 515 rb_tree_remove_node(&ip->i_lfs_segdhd, isd); 516 /* Insert unless node exists */ 517 fsd = rb_tree_insert_node(&fs->lfs_segdhd, isd); 518 if (fsd != isd) { 519 /* Merge into existing */ 520 fsd->num += isd->num; 521 free(isd, M_SEGMENT); 522 } 523 } 524 } else { 525 /* 526 * If it's not a dirop, we can finalize right away. 527 */ 528 mutex_exit(&lfs_lock); 529 lfs_finalize_ino_seguse(fs, ip); 530 } 531 532 /* it is no longer an unwritten inode, so update the counts */ 533 KASSERT(!(ip->i_state & IN_CLEANING)); 534 mutex_enter(&lfs_lock); 535 LFS_CLR_UINO(ip, IN_ACCESSED|IN_MODIFIED); 536 mutex_exit(&lfs_lock); 537 538 /* Turn off all inode modification flags */ 539 ip->i_state &= ~IN_ALLMOD; 540 541 /* Mark it deleted */ 542 ip->i_lfs_iflags |= LFSI_DELETED; 543 544 /* 545 * Set the ifile's inode entry to unused, increment its version number 546 * and link it onto the free chain. 547 */ 548 549 /* update the on-disk address (to "nowhere") */ 550 lfs_update_iaddr(fs, ip, LFS_UNUSED_DADDR); 551 552 /* fetch the ifile entry */ 553 LFS_IENTRY(ifp, fs, ino, bp); 554 555 /* bump the version */ 556 lfs_if_setversion(fs, ifp, lfs_if_getversion(fs, ifp) + 1); 557 558 #if 0 559 if (lfs_sb_getversion(fs) == 1) { 560 #endif 561 ino_t nextfree; 562 563 /* insert on freelist */ 564 LFS_GET_HEADFREE(fs, cip, cbp, &nextfree); 565 lfs_if_setnextfree(fs, ifp, nextfree); 566 LFS_PUT_HEADFREE(fs, cip, cbp, ino); 567 568 /* write the ifile block */ 569 LFS_WRITEIENTRY(ifp, fs, ino, bp); 570 #if 0 571 } else { 572 ino_t tino, onf, otail; 573 574 /* 575 * Clear the freelist next pointer and write the ifile 576 * block. XXX: why? I'm sure there must be a reason but 577 * it seems both silly and dangerous. 578 */ 579 lfs_if_setnextfree(fs, ifp, LFS_UNUSED_INUM); 580 LFS_WRITEIENTRY(ifp, fs, ino, bp); 581 582 /* 583 * Insert on freelist in order. 584 */ 585 586 /* Find the next lower (by number) free inode */ 587 tino = lfs_freelist_prev(fs, ino); 588 589 if (tino == LFS_UNUSED_INUM) { 590 ino_t nextfree; 591 592 /* 593 * There isn't one; put us on the freelist head. 594 */ 595 596 /* reload the ifile block */ 597 LFS_IENTRY(ifp, fs, ino, bp); 598 /* update the list */ 599 LFS_GET_HEADFREE(fs, cip, cbp, &nextfree); 600 lfs_if_setnextfree(fs, ifp, nextfree); 601 LFS_PUT_HEADFREE(fs, cip, cbp, ino); 602 DLOG((DLOG_ALLOC, "lfs_vfree: headfree %lld -> %lld\n", 603 (long long)nextfree, (long long)ino)); 604 /* write the ifile block */ 605 LFS_WRITEIENTRY(ifp, fs, ino, bp); 606 607 /* If the list was empty, set tail too */ 608 LFS_GET_TAILFREE(fs, cip, cbp, &otail); 609 if (otail == LFS_UNUSED_INUM) { 610 LFS_PUT_TAILFREE(fs, cip, cbp, ino); 611 DLOG((DLOG_ALLOC, "lfs_vfree: tailfree %lld " 612 "-> %lld\n", (long long)otail, 613 (long long)ino)); 614 } 615 } else { 616 /* 617 * Insert this inode into the list after tino. 618 * We hold the segment lock so we don't have to 619 * worry about blocks being written out of order. 620 */ 621 622 DLOG((DLOG_ALLOC, "lfs_vfree: insert ino %lld " 623 " after %lld\n", ino, tino)); 624 625 /* load the previous inode's ifile block */ 626 LFS_IENTRY(ifp, fs, tino, bp); 627 /* update the list pointer */ 628 onf = lfs_if_getnextfree(fs, ifp); 629 lfs_if_setnextfree(fs, ifp, ino); 630 /* write the block */ 631 LFS_WRITEIENTRY(ifp, fs, tino, bp); 632 633 /* load this inode's ifile block */ 634 LFS_IENTRY(ifp, fs, ino, bp); 635 /* update the list pointer */ 636 lfs_if_setnextfree(fs, ifp, onf); 637 /* write the block */ 638 LFS_WRITEIENTRY(ifp, fs, tino, bp); 639 640 /* If we're last, put us on the tail */ 641 if (onf == LFS_UNUSED_INUM) { 642 LFS_GET_TAILFREE(fs, cip, cbp, &otail); 643 LFS_PUT_TAILFREE(fs, cip, cbp, ino); 644 DLOG((DLOG_ALLOC, "lfs_vfree: tailfree %lld " 645 "-> %lld\n", (long long)otail, 646 (long long)ino)); 647 } 648 } 649 } 650 #endif 651 652 /* Set superblock modified bit. */ 653 mutex_enter(&lfs_lock); 654 fs->lfs_fmod = 1; 655 mutex_exit(&lfs_lock); 656 657 /* Decrement file count. */ 658 lfs_sb_subnfiles(fs, 1); 659 660 lfs_preunlock(fs); 661 662 DEBUG_CHECK_FREELIST(fs); 663 664 return (0); 665 } 666 667 /* 668 * Free orphans. To be called by lfs_mountfs(). 669 * 670 * Takes the segment lock. 671 */ 672 void 673 lfs_free_orphans(struct lfs *fs) 674 { 675 IFILE *ifp = NULL; 676 struct vnode *vp; 677 struct buf *bp; 678 ino_t ino, maxino; 679 ino_t *orphan = NULL; 680 size_t norphan = 0; 681 size_t norphan_alloc = 0; 682 int i, error; 683 684 ASSERT_NO_SEGLOCK(fs); 685 lfs_prelock(fs, 0); 686 687 DEBUG_CHECK_FREELIST(fs); 688 689 /* largest inode on fs */ 690 maxino = ((fs->lfs_ivnode->v_size >> lfs_sb_getbshift(fs)) - 691 lfs_sb_getcleansz(fs) - lfs_sb_getsegtabsz(fs)) * lfs_sb_getifpb(fs); 692 693 /* 694 * Scan the ifile. 695 */ 696 697 for (ino = 0; ino < maxino; ino++) { 698 /* Load this inode's ifile entry. */ 699 if (ino % lfs_sb_getifpb(fs) == 0) 700 LFS_IENTRY(ifp, fs, ino, bp); 701 else 702 LFS_IENTRY_NEXT(ifp, fs); 703 704 /* Don't put zero or ifile on the free list */ 705 if (ino == LFS_UNUSED_INUM || ino == LFS_IFILE_INUM) 706 continue; 707 708 /* Recognize orphans by their magic nextfree value */ 709 if (lfs_if_getnextfree(fs, ifp) == LFS_ORPHAN_NEXTFREE(fs)) { 710 if (orphan == NULL) { 711 norphan_alloc = 32; /* XXX pulled from arse */ 712 orphan = kmem_zalloc(sizeof(orphan[0]) * 713 norphan_alloc, KM_SLEEP); 714 } else if (norphan == norphan_alloc) { 715 ino_t *orphan_new; 716 if (norphan_alloc >= 4096) 717 norphan_alloc += 4096; 718 else 719 norphan_alloc *= 2; 720 orphan_new = kmem_zalloc(sizeof(orphan[0]) * 721 norphan_alloc, KM_SLEEP); 722 memcpy(orphan_new, orphan, sizeof(orphan[0]) * 723 norphan); 724 kmem_free(orphan, sizeof(orphan[0]) * norphan); 725 orphan = orphan_new; 726 } 727 orphan[norphan++] = ino; 728 } 729 730 /* If moving to the next ifile block, release the buffer. */ 731 if ((ino + 1) % lfs_sb_getifpb(fs) == 0) 732 brelse(bp, 0); 733 } 734 735 /* done */ 736 lfs_preunlock(fs); 737 738 DEBUG_CHECK_FREELIST(fs); 739 740 /* Now free any orphans we found */ 741 if (orphan) { 742 for (i = 0; i < norphan; i++) { 743 error = VFS_VGET(fs->lfs_ivnode->v_mount, orphan[i], 744 LK_EXCLUSIVE, &vp); 745 if (error) { 746 printf("lfs_free_orphan vget ino %jd error %d\n", 747 (intmax_t)orphan[i], error); 748 continue; 749 } 750 vput(vp); 751 } 752 kmem_free(orphan, sizeof(orphan[0]) * norphan); 753 } 754 755 DEBUG_CHECK_FREELIST(fs); 756 } 757 758 /* 759 * Handle files deleted from the file system namespace. 760 * 761 * When inodes are reclaimed, they are added back to the free list as 762 * usual; but if the system crashes before they can be reclaimed, they 763 * will need to be reclaimed at next mount. We therefore set their 764 * nextfree field to the magic value LFS_ORPHAN_NEXTFREE so we can 765 * identify them. 766 * 767 * 768 * The caller holds a reference to vp, and the buffer cache provides 769 * exclusive access to the "nextfree" entry. 770 */ 771 void 772 lfs_orphan(struct lfs *fs, struct vnode *vp) 773 { 774 IFILE *ifp; 775 struct buf *bp; 776 struct inode *ip; 777 ino_t nextfree; 778 int mincount; 779 780 ip = VTOI(vp); 781 782 ASSERT_NO_SEGLOCK(fs); 783 KASSERT(ip->i_nlink == 0); 784 785 /* 786 * Check reference count. 787 * 788 * Even if the file is not still referenced, it holds a 789 * reference associated with VU_DIROP. This creates an 790 * opportunity for fhopen() to re-open the file, which is 791 * illegal. Therefore we count the number of references that 792 * would come from VDIROP and IN_CLEANING, and compare that 793 * against the vnode ref count. If the usecount can be 794 * accounted for by VDIROP and IN_CLEANING, mark the node 795 * IN_DEAD. 796 */ 797 mincount = 1; /* The caller holds one */ 798 mutex_enter(&lfs_lock); 799 if (ip->i_state & IN_CLEANING) 800 ++mincount; 801 if (vp->v_uflag & VU_DIROP) 802 ++mincount; 803 mutex_exit(&lfs_lock); 804 mutex_enter(vp->v_interlock); 805 if (vp->v_usecount <= mincount) 806 ip->i_state |= IN_DEAD; 807 mutex_exit(vp->v_interlock); 808 809 /* If not already done, mark this inode orphaned. */ 810 lfs_fraglock_enter(fs, RW_READER); 811 LFS_IENTRY(ifp, fs, ip->i_number, bp); 812 nextfree = lfs_if_getnextfree(fs, ifp); 813 if (nextfree == LFS_ORPHAN_NEXTFREE(fs)) { 814 brelse(bp, 0); 815 lfs_fraglock_exit(fs); 816 return; 817 } 818 KASSERT(nextfree == LFS_UNUSED_INUM); 819 lfs_if_setnextfree(fs, ifp, LFS_ORPHAN_NEXTFREE(fs)); 820 LFS_WRITEIENTRY(ifp, fs, ip->i_number, bp); 821 lfs_fraglock_exit(fs); 822 } 823 824 #ifdef DEBUG 825 static void dump_freelist(struct lfs *); 826 827 void 828 lfs_check_freelist(struct lfs *fs, const char *func, int line) 829 { 830 ino_t i, headino, maxino, thisino, tailino, nextfree; 831 int nfree, count; 832 struct inode *ip; 833 IFILE *ifp; 834 CLEANERINFO *cip; 835 struct buf *bp; 836 837 if (!lfs_do_check_freelist) 838 return; 839 840 lfs_prelock(fs, 0); 841 842 ip = VTOI(fs->lfs_ivnode); 843 maxino = ((ip->i_size >> lfs_sb_getbshift(fs)) - lfs_sb_getcleansz(fs) - 844 lfs_sb_getsegtabsz(fs)) * lfs_sb_getifpb(fs); 845 846 /* 847 * First, check every node. Every inode that doesn't have a disk 848 * address must have a nextfree pointer, the only exception 849 * being the tail of the free list. 850 */ 851 LFS_GET_TAILFREE(fs, cip, bp, &tailino); 852 nfree = 0; 853 for (i = LFS_IFILE_INUM + 1; i < maxino; ++i) { 854 LFS_IENTRY(ifp, fs, i, bp); 855 if (lfs_if_getdaddr(fs, ifp) == LFS_UNUSED_DADDR) { 856 ++nfree; 857 if (lfs_if_getnextfree(fs, ifp) == LFS_UNUSED_INUM 858 && i != tailino) { 859 brelse(bp, 0); 860 dump_freelist(fs); 861 printf("At %s:%d:\n", func, line); 862 printf("tailino=%jd, but ino=%jd" 863 " neither daddr nor nextfree\n", 864 (intmax_t)tailino, (intmax_t)i); 865 panic("Free list leak\n"); 866 } 867 } 868 if (i == tailino 869 || (!INUM_IS_BAD(fs, lfs_if_getnextfree(fs, ifp)))) { 870 if (lfs_if_getdaddr(fs, ifp) != LFS_UNUSED_DADDR) { 871 brelse(bp, 0); 872 dump_freelist(fs); 873 printf("At %s:%d:\n", func, line); 874 printf("with tailino=%jd, ino=%jd" 875 " daddr=0x%jx, nextfree=0x%jx\n", 876 (intmax_t)tailino, 877 (intmax_t)i, 878 (intmax_t)lfs_if_getdaddr(fs, ifp), 879 (intmax_t)lfs_if_getnextfree(fs, ifp)); 880 panic("In use inode on free list\n"); 881 } 882 } 883 brelse(bp, 0); 884 } 885 886 /* 887 * Walk the free list from head to tail. We should end up with 888 * the same number of free inodes as we counted above. 889 */ 890 891 /* Get head of inode freelist */ 892 LFS_GET_HEADFREE(fs, cip, bp, &headino); 893 count = 0; 894 thisino = headino; 895 while (thisino != LFS_UNUSED_INUM) { 896 if (++count > maxino) 897 break; 898 /* read this ifile entry */ 899 LFS_IENTRY(ifp, fs, thisino, bp); 900 nextfree = lfs_if_getnextfree(fs, ifp); 901 brelse(bp, 0); 902 if (nextfree == LFS_UNUSED_INUM) 903 break; 904 thisino = nextfree; 905 } 906 if (count > maxino) { 907 dump_freelist(fs); 908 printf("At %s:%d:\n", func, line); 909 printf("count=%jd, maxino=%jd:\n", 910 (intmax_t)count, (intmax_t)maxino); 911 panic("loop in free list"); 912 } 913 if (count != nfree) { 914 dump_freelist(fs); 915 printf("At %s:%d:\n", func, line); 916 printf("%d inodes without addresses, %d on free list\n", 917 nfree, count); 918 panic("Bad free list count"); 919 } 920 if (thisino != tailino) { 921 dump_freelist(fs); 922 printf("At %s:%d:\n", func, line); 923 printf("Last ino %jd but tail %jd\n", 924 (intmax_t)thisino, (intmax_t)tailino); 925 panic("Bad tail"); 926 } 927 lfs_preunlock(fs); 928 } 929 930 static void 931 dump_freelist(struct lfs *fs) 932 { 933 ino_t i, ni, maxino, headino, tailino; 934 struct inode *ip; 935 IFILE *ifp; 936 CLEANERINFO *cip; 937 struct buf *bp; 938 int count; 939 940 ip = VTOI(fs->lfs_ivnode); 941 maxino = ((ip->i_size >> lfs_sb_getbshift(fs)) - lfs_sb_getcleansz(fs) - 942 lfs_sb_getsegtabsz(fs)) * lfs_sb_getifpb(fs); 943 944 LFS_GET_HEADFREE(fs, cip, bp, &headino); 945 printf(" head: %jd\n", (intmax_t)headino); 946 LFS_GET_TAILFREE(fs, cip, bp, &tailino); 947 printf(" tail: %jd\n", (intmax_t)tailino); 948 count = 0; 949 for (i = LFS_IFILE_INUM + 1; i < maxino; ++i) { 950 LFS_IENTRY(ifp, fs, i, bp); 951 ni = lfs_if_getnextfree(fs, ifp); 952 if (ni != LFS_UNUSED_DADDR) { 953 printf("%jd -> %jd\n", 954 (intmax_t)i, (intmax_t)ni); 955 if (++count > 30) { 956 printf("...\n"); 957 i = maxino; /* terminate loop */ 958 } 959 } 960 brelse(bp, 0); 961 } 962 } 963 #endif /* DEBUG */ 964
Indexes created Sun Sep 20 00:26:38 UTC 2026