1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3 * 4 * Copyright 2009, 2010 Jeffrey W. Roberson <jeff@FreeBSD.org> 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29 #include <sys/cdefs.h> 30 __FBSDID("$FreeBSD$"); 31 32 #include <sys/param.h> 33 #include <sys/disk.h> 34 #include <sys/disklabel.h> 35 #include <sys/mount.h> 36 #include <sys/stat.h> 37 38 #include <ufs/ufs/extattr.h> 39 #include <ufs/ufs/quota.h> 40 #include <ufs/ufs/ufsmount.h> 41 #include <ufs/ufs/dinode.h> 42 #include <ufs/ufs/dir.h> 43 #include <ufs/ffs/fs.h> 44 45 #include <assert.h> 46 #include <err.h> 47 #include <setjmp.h> 48 #include <stdarg.h> 49 #include <stdio.h> 50 #include <stdlib.h> 51 #include <stdint.h> 52 #include <libufs.h> 53 #include <string.h> 54 #include <strings.h> 55 #include <sysexits.h> 56 #include <time.h> 57 58 #include "fsck.h" 59 60 #define DOTDOT_OFFSET DIRECTSIZ(1) 61 62 struct suj_seg { 63 TAILQ_ENTRY(suj_seg) ss_next; 64 struct jsegrec ss_rec; 65 uint8_t *ss_blk; 66 }; 67 68 struct suj_rec { 69 TAILQ_ENTRY(suj_rec) sr_next; 70 union jrec *sr_rec; 71 }; 72 TAILQ_HEAD(srechd, suj_rec); 73 74 struct suj_ino { 75 LIST_ENTRY(suj_ino) si_next; 76 struct srechd si_recs; 77 struct srechd si_newrecs; 78 struct srechd si_movs; 79 struct jtrncrec *si_trunc; 80 ino_t si_ino; 81 char si_skipparent; 82 char si_hasrecs; 83 char si_blkadj; 84 char si_linkadj; 85 int si_mode; 86 nlink_t si_nlinkadj; 87 nlink_t si_nlink; 88 nlink_t si_dotlinks; 89 }; 90 LIST_HEAD(inohd, suj_ino); 91 92 struct suj_blk { 93 LIST_ENTRY(suj_blk) sb_next; 94 struct srechd sb_recs; 95 ufs2_daddr_t sb_blk; 96 }; 97 LIST_HEAD(blkhd, suj_blk); 98 99 struct suj_cg { 100 LIST_ENTRY(suj_cg) sc_next; 101 struct blkhd sc_blkhash[HASHSIZE]; 102 struct inohd sc_inohash[HASHSIZE]; 103 struct ino_blk *sc_lastiblk; 104 struct suj_ino *sc_lastino; 105 struct suj_blk *sc_lastblk; 106 struct bufarea *sc_cgbp; 107 struct cg *sc_cgp; 108 int sc_cgx; 109 }; 110 111 static LIST_HEAD(cghd, suj_cg) cghash[HASHSIZE]; 112 static struct suj_cg *lastcg; 113 114 static TAILQ_HEAD(seghd, suj_seg) allsegs; 115 static uint64_t oldseq; 116 static struct fs *fs = NULL; 117 static ino_t sujino; 118 119 /* 120 * Summary statistics. 121 */ 122 static uint64_t freefrags; 123 static uint64_t freeblocks; 124 static uint64_t freeinos; 125 static uint64_t freedir; 126 static uint64_t jbytes; 127 static uint64_t jrecs; 128 129 static jmp_buf jmpbuf; 130 131 typedef void (*ino_visitor)(ino_t, ufs_lbn_t, ufs2_daddr_t, int); 132 static void err_suj(const char *, ...) __dead2; 133 static void ino_trunc(ino_t, off_t); 134 static void ino_decr(ino_t); 135 static void ino_adjust(struct suj_ino *); 136 static void ino_build(struct suj_ino *); 137 static int blk_isfree(ufs2_daddr_t); 138 static void initsuj(void); 139 140 static void * 141 errmalloc(size_t n) 142 { 143 void *a; 144 145 a = Malloc(n); 146 if (a == NULL) 147 err(EX_OSERR, "malloc(%zu)", n); 148 return (a); 149 } 150 151 /* 152 * When hit a fatal error in journalling check, print out 153 * the error and then offer to fallback to normal fsck. 154 */ 155 static void 156 err_suj(const char * restrict fmt, ...) 157 { 158 va_list ap; 159 160 if (preen) 161 (void)fprintf(stdout, "%s: ", cdevname); 162 163 va_start(ap, fmt); 164 (void)vfprintf(stdout, fmt, ap); 165 va_end(ap); 166 167 longjmp(jmpbuf, -1); 168 } 169 170 /* 171 * Lookup a cg by number in the hash so we can keep track of which cgs 172 * need stats rebuilt. 173 */ 174 static struct suj_cg * 175 cg_lookup(int cgx) 176 { 177 struct cghd *hd; 178 struct suj_cg *sc; 179 struct bufarea *cgbp; 180 181 if (cgx < 0 || cgx >= fs->fs_ncg) 182 err_suj("Bad cg number %d\n", cgx); 183 if (lastcg && lastcg->sc_cgx == cgx) 184 return (lastcg); 185 cgbp = cglookup(cgx); 186 if (!check_cgmagic(cgx, cgbp, 0)) 187 err_suj("UNABLE TO REBUILD CYLINDER GROUP %d", cgx); 188 hd = &cghash[HASH(cgx)]; 189 LIST_FOREACH(sc, hd, sc_next) 190 if (sc->sc_cgx == cgx) { 191 sc->sc_cgbp = cgbp; 192 sc->sc_cgp = sc->sc_cgbp->b_un.b_cg; 193 lastcg = sc; 194 return (sc); 195 } 196 sc = errmalloc(sizeof(*sc)); 197 bzero(sc, sizeof(*sc)); 198 sc->sc_cgbp = cgbp; 199 sc->sc_cgp = sc->sc_cgbp->b_un.b_cg; 200 sc->sc_cgx = cgx; 201 LIST_INSERT_HEAD(hd, sc, sc_next); 202 return (sc); 203 } 204 205 /* 206 * Lookup an inode number in the hash and allocate a suj_ino if it does 207 * not exist. 208 */ 209 static struct suj_ino * 210 ino_lookup(ino_t ino, int creat) 211 { 212 struct suj_ino *sino; 213 struct inohd *hd; 214 struct suj_cg *sc; 215 216 sc = cg_lookup(ino_to_cg(fs, ino)); 217 if (sc->sc_lastino && sc->sc_lastino->si_ino == ino) 218 return (sc->sc_lastino); 219 hd = &sc->sc_inohash[HASH(ino)]; 220 LIST_FOREACH(sino, hd, si_next) 221 if (sino->si_ino == ino) 222 return (sino); 223 if (creat == 0) 224 return (NULL); 225 sino = errmalloc(sizeof(*sino)); 226 bzero(sino, sizeof(*sino)); 227 sino->si_ino = ino; 228 TAILQ_INIT(&sino->si_recs); 229 TAILQ_INIT(&sino->si_newrecs); 230 TAILQ_INIT(&sino->si_movs); 231 LIST_INSERT_HEAD(hd, sino, si_next); 232 233 return (sino); 234 } 235 236 /* 237 * Lookup a block number in the hash and allocate a suj_blk if it does 238 * not exist. 239 */ 240 static struct suj_blk * 241 blk_lookup(ufs2_daddr_t blk, int creat) 242 { 243 struct suj_blk *sblk; 244 struct suj_cg *sc; 245 struct blkhd *hd; 246 247 sc = cg_lookup(dtog(fs, blk)); 248 if (sc->sc_lastblk && sc->sc_lastblk->sb_blk == blk) 249 return (sc->sc_lastblk); 250 hd = &sc->sc_blkhash[HASH(fragstoblks(fs, blk))]; 251 LIST_FOREACH(sblk, hd, sb_next) 252 if (sblk->sb_blk == blk) 253 return (sblk); 254 if (creat == 0) 255 return (NULL); 256 sblk = errmalloc(sizeof(*sblk)); 257 bzero(sblk, sizeof(*sblk)); 258 sblk->sb_blk = blk; 259 TAILQ_INIT(&sblk->sb_recs); 260 LIST_INSERT_HEAD(hd, sblk, sb_next); 261 262 return (sblk); 263 } 264 265 static int 266 blk_overlaps(struct jblkrec *brec, ufs2_daddr_t start, int frags) 267 { 268 ufs2_daddr_t bstart; 269 ufs2_daddr_t bend; 270 ufs2_daddr_t end; 271 272 end = start + frags; 273 bstart = brec->jb_blkno + brec->jb_oldfrags; 274 bend = bstart + brec->jb_frags; 275 if (start < bend && end > bstart) 276 return (1); 277 return (0); 278 } 279 280 static int 281 blk_equals(struct jblkrec *brec, ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t start, 282 int frags) 283 { 284 285 if (brec->jb_ino != ino || brec->jb_lbn != lbn) 286 return (0); 287 if (brec->jb_blkno + brec->jb_oldfrags != start) 288 return (0); 289 if (brec->jb_frags < frags) 290 return (0); 291 return (1); 292 } 293 294 static void 295 blk_setmask(struct jblkrec *brec, int *mask) 296 { 297 int i; 298 299 for (i = brec->jb_oldfrags; i < brec->jb_oldfrags + brec->jb_frags; i++) 300 *mask |= 1 << i; 301 } 302 303 /* 304 * Determine whether a given block has been reallocated to a new location. 305 * Returns a mask of overlapping bits if any frags have been reused or 306 * zero if the block has not been re-used and the contents can be trusted. 307 * 308 * This is used to ensure that an orphaned pointer due to truncate is safe 309 * to be freed. The mask value can be used to free partial blocks. 310 */ 311 static int 312 blk_freemask(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn, int frags) 313 { 314 struct suj_blk *sblk; 315 struct suj_rec *srec; 316 struct jblkrec *brec; 317 int mask; 318 int off; 319 320 /* 321 * To be certain we're not freeing a reallocated block we lookup 322 * this block in the blk hash and see if there is an allocation 323 * journal record that overlaps with any fragments in the block 324 * we're concerned with. If any fragments have been reallocated 325 * the block has already been freed and re-used for another purpose. 326 */ 327 mask = 0; 328 sblk = blk_lookup(blknum(fs, blk), 0); 329 if (sblk == NULL) 330 return (0); 331 off = blk - sblk->sb_blk; 332 TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) { 333 brec = (struct jblkrec *)srec->sr_rec; 334 /* 335 * If the block overlaps but does not match 336 * exactly this record refers to the current 337 * location. 338 */ 339 if (blk_overlaps(brec, blk, frags) == 0) 340 continue; 341 if (blk_equals(brec, ino, lbn, blk, frags) == 1) 342 mask = 0; 343 else 344 blk_setmask(brec, &mask); 345 } 346 if (debug) 347 printf("blk_freemask: blk %jd sblk %jd off %d mask 0x%X\n", 348 blk, sblk->sb_blk, off, mask); 349 return (mask >> off); 350 } 351 352 /* 353 * Determine whether it is safe to follow an indirect. It is not safe 354 * if any part of the indirect has been reallocated or the last journal 355 * entry was an allocation. Just allocated indirects may not have valid 356 * pointers yet and all of their children will have their own records. 357 * It is also not safe to follow an indirect if the cg bitmap has been 358 * cleared as a new allocation may write to the block prior to the journal 359 * being written. 360 * 361 * Returns 1 if it's safe to follow the indirect and 0 otherwise. 362 */ 363 static int 364 blk_isindir(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn) 365 { 366 struct suj_blk *sblk; 367 struct jblkrec *brec; 368 369 sblk = blk_lookup(blk, 0); 370 if (sblk == NULL) 371 return (1); 372 if (TAILQ_EMPTY(&sblk->sb_recs)) 373 return (1); 374 brec = (struct jblkrec *)TAILQ_LAST(&sblk->sb_recs, srechd)->sr_rec; 375 if (blk_equals(brec, ino, lbn, blk, fs->fs_frag)) 376 if (brec->jb_op == JOP_FREEBLK) 377 return (!blk_isfree(blk)); 378 return (0); 379 } 380 381 /* 382 * Check to see if the requested block is available. 383 * We can just check in the cylinder-group maps as 384 * they will only have usable blocks in them. 385 */ 386 ufs2_daddr_t 387 suj_checkblkavail(ufs2_daddr_t blkno, long frags) 388 { 389 struct bufarea *cgbp; 390 struct cg *cgp; 391 ufs2_daddr_t j, k, baseblk; 392 long cg; 393 394 if ((u_int64_t)blkno > sblock.fs_size) 395 return (0); 396 cg = dtog(&sblock, blkno); 397 cgbp = cglookup(cg); 398 cgp = cgbp->b_un.b_cg; 399 if (!check_cgmagic(cg, cgbp, 0)) 400 return (-((cg + 1) * sblock.fs_fpg - sblock.fs_frag)); 401 baseblk = dtogd(&sblock, blkno); 402 for (j = 0; j <= sblock.fs_frag - frags; j++) { 403 if (!isset(cg_blksfree(cgp), baseblk + j)) 404 continue; 405 for (k = 1; k < frags; k++) 406 if (!isset(cg_blksfree(cgp), baseblk + j + k)) 407 break; 408 if (k < frags) { 409 j += k; 410 continue; 411 } 412 for (k = 0; k < frags; k++) 413 clrbit(cg_blksfree(cgp), baseblk + j + k); 414 n_blks += frags; 415 if (frags == sblock.fs_frag) 416 cgp->cg_cs.cs_nbfree--; 417 else 418 cgp->cg_cs.cs_nffree -= frags; 419 cgdirty(cgbp); 420 return ((cg * sblock.fs_fpg) + baseblk + j); 421 } 422 return (0); 423 } 424 425 /* 426 * Clear an inode from the cg bitmap. If the inode was already clear return 427 * 0 so the caller knows it does not have to check the inode contents. 428 */ 429 static int 430 ino_free(ino_t ino, int mode) 431 { 432 struct suj_cg *sc; 433 uint8_t *inosused; 434 struct cg *cgp; 435 int cg; 436 437 cg = ino_to_cg(fs, ino); 438 ino = ino % fs->fs_ipg; 439 sc = cg_lookup(cg); 440 cgp = sc->sc_cgp; 441 inosused = cg_inosused(cgp); 442 /* 443 * The bitmap may never have made it to the disk so we have to 444 * conditionally clear. We can avoid writing the cg in this case. 445 */ 446 if (isclr(inosused, ino)) 447 return (0); 448 freeinos++; 449 clrbit(inosused, ino); 450 if (ino < cgp->cg_irotor) 451 cgp->cg_irotor = ino; 452 cgp->cg_cs.cs_nifree++; 453 if ((mode & IFMT) == IFDIR) { 454 freedir++; 455 cgp->cg_cs.cs_ndir--; 456 } 457 cgdirty(sc->sc_cgbp); 458 459 return (1); 460 } 461 462 /* 463 * Free 'frags' frags starting at filesystem block 'bno' skipping any frags 464 * set in the mask. 465 */ 466 static void 467 blk_free(ino_t ino, ufs2_daddr_t bno, int mask, int frags) 468 { 469 ufs1_daddr_t fragno, cgbno; 470 struct suj_cg *sc; 471 struct cg *cgp; 472 int i, cg; 473 uint8_t *blksfree; 474 475 if (debug) 476 printf("Freeing %d frags at blk %jd mask 0x%x\n", 477 frags, bno, mask); 478 /* 479 * Check to see if the block needs to be claimed by a snapshot. 480 * If wanted, the snapshot references it. Otherwise we free it. 481 */ 482 if (snapblkfree(fs, bno, lfragtosize(fs, frags), ino, 483 suj_checkblkavail)) 484 return; 485 cg = dtog(fs, bno); 486 sc = cg_lookup(cg); 487 cgp = sc->sc_cgp; 488 cgbno = dtogd(fs, bno); 489 blksfree = cg_blksfree(cgp); 490 491 /* 492 * If it's not allocated we only wrote the journal entry 493 * and never the bitmaps. Here we unconditionally clear and 494 * resolve the cg summary later. 495 */ 496 if (frags == fs->fs_frag && mask == 0) { 497 fragno = fragstoblks(fs, cgbno); 498 ffs_setblock(fs, blksfree, fragno); 499 freeblocks++; 500 } else { 501 /* 502 * deallocate the fragment 503 */ 504 for (i = 0; i < frags; i++) 505 if ((mask & (1 << i)) == 0 && isclr(blksfree, cgbno +i)) { 506 freefrags++; 507 setbit(blksfree, cgbno + i); 508 } 509 } 510 cgdirty(sc->sc_cgbp); 511 } 512 513 /* 514 * Returns 1 if the whole block starting at 'bno' is marked free and 0 515 * otherwise. 516 */ 517 static int 518 blk_isfree(ufs2_daddr_t bno) 519 { 520 struct suj_cg *sc; 521 522 sc = cg_lookup(dtog(fs, bno)); 523 return ffs_isblock(fs, cg_blksfree(sc->sc_cgp), dtogd(fs, bno)); 524 } 525 526 /* 527 * Determine whether a block exists at a particular lbn in an inode. 528 * Returns 1 if found, 0 if not. lbn may be negative for indirects 529 * or ext blocks. 530 */ 531 static int 532 blk_isat(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int *frags) 533 { 534 struct inode ip; 535 union dinode *dp; 536 ufs2_daddr_t nblk; 537 538 ginode(ino, &ip); 539 dp = ip.i_dp; 540 if (DIP(dp, di_nlink) == 0 || DIP(dp, di_mode) == 0) { 541 irelse(&ip); 542 return (0); 543 } 544 nblk = ino_blkatoff(dp, ino, lbn, frags, NULL); 545 irelse(&ip); 546 return (nblk == blk); 547 } 548 549 /* 550 * Clear the directory entry at diroff that should point to child. Minimal 551 * checking is done and it is assumed that this path was verified with isat. 552 */ 553 static void 554 ino_clrat(ino_t parent, off_t diroff, ino_t child) 555 { 556 union dinode *dip; 557 struct direct *dp; 558 struct inode ip; 559 ufs2_daddr_t blk; 560 struct bufarea *bp; 561 ufs_lbn_t lbn; 562 int blksize; 563 int frags; 564 int doff; 565 566 if (debug) 567 printf("Clearing inode %ju from parent %ju at offset %jd\n", 568 (uintmax_t)child, (uintmax_t)parent, diroff); 569 570 lbn = lblkno(fs, diroff); 571 doff = blkoff(fs, diroff); 572 ginode(parent, &ip); 573 dip = ip.i_dp; 574 blk = ino_blkatoff(dip, parent, lbn, &frags, NULL); 575 blksize = sblksize(fs, DIP(dip, di_size), lbn); 576 irelse(&ip); 577 bp = getdatablk(blk, blksize, BT_DIRDATA); 578 if (bp->b_errs != 0) 579 err_suj("ino_clrat: UNRECOVERABLE I/O ERROR"); 580 dp = (struct direct *)&bp->b_un.b_buf[doff]; 581 if (dp->d_ino != child) 582 errx(1, "Inode %ju does not exist in %ju at %jd", 583 (uintmax_t)child, (uintmax_t)parent, diroff); 584 dp->d_ino = 0; 585 dirty(bp); 586 brelse(bp); 587 /* 588 * The actual .. reference count will already have been removed 589 * from the parent by the .. remref record. 590 */ 591 } 592 593 /* 594 * Determines whether a pointer to an inode exists within a directory 595 * at a specified offset. Returns the mode of the found entry. 596 */ 597 static int 598 ino_isat(ino_t parent, off_t diroff, ino_t child, int *mode, int *isdot) 599 { 600 struct inode ip; 601 union dinode *dip; 602 struct bufarea *bp; 603 struct direct *dp; 604 ufs2_daddr_t blk; 605 ufs_lbn_t lbn; 606 int blksize; 607 int frags; 608 int dpoff; 609 int doff; 610 611 *isdot = 0; 612 ginode(parent, &ip); 613 dip = ip.i_dp; 614 *mode = DIP(dip, di_mode); 615 if ((*mode & IFMT) != IFDIR) { 616 if (debug) { 617 /* 618 * This can happen if the parent inode 619 * was reallocated. 620 */ 621 if (*mode != 0) 622 printf("Directory %ju has bad mode %o\n", 623 (uintmax_t)parent, *mode); 624 else 625 printf("Directory %ju has zero mode\n", 626 (uintmax_t)parent); 627 } 628 irelse(&ip); 629 return (0); 630 } 631 lbn = lblkno(fs, diroff); 632 doff = blkoff(fs, diroff); 633 blksize = sblksize(fs, DIP(dip, di_size), lbn); 634 if (diroff + DIRECTSIZ(1) > DIP(dip, di_size) || doff >= blksize) { 635 if (debug) 636 printf("ino %ju absent from %ju due to offset %jd" 637 " exceeding size %jd\n", 638 (uintmax_t)child, (uintmax_t)parent, diroff, 639 DIP(dip, di_size)); 640 irelse(&ip); 641 return (0); 642 } 643 blk = ino_blkatoff(dip, parent, lbn, &frags, NULL); 644 irelse(&ip); 645 if (blk <= 0) { 646 if (debug) 647 printf("Sparse directory %ju", (uintmax_t)parent); 648 return (0); 649 } 650 bp = getdatablk(blk, blksize, BT_DIRDATA); 651 if (bp->b_errs != 0) 652 err_suj("ino_isat: UNRECOVERABLE I/O ERROR"); 653 /* 654 * Walk through the records from the start of the block to be 655 * certain we hit a valid record and not some junk in the middle 656 * of a file name. Stop when we reach or pass the expected offset. 657 */ 658 dpoff = rounddown(doff, DIRBLKSIZ); 659 do { 660 dp = (struct direct *)&bp->b_un.b_buf[dpoff]; 661 if (dpoff == doff) 662 break; 663 if (dp->d_reclen == 0) 664 break; 665 dpoff += dp->d_reclen; 666 } while (dpoff <= doff); 667 if (dpoff > fs->fs_bsize) 668 err_suj("Corrupt directory block in dir ino %ju\n", 669 (uintmax_t)parent); 670 /* Not found. */ 671 if (dpoff != doff) { 672 if (debug) 673 printf("ino %ju not found in %ju, lbn %jd, dpoff %d\n", 674 (uintmax_t)child, (uintmax_t)parent, lbn, dpoff); 675 brelse(bp); 676 return (0); 677 } 678 /* 679 * We found the item in question. Record the mode and whether it's 680 * a . or .. link for the caller. 681 */ 682 if (dp->d_ino == child) { 683 if (child == parent) 684 *isdot = 1; 685 else if (dp->d_namlen == 2 && 686 dp->d_name[0] == '.' && dp->d_name[1] == '.') 687 *isdot = 1; 688 *mode = DTTOIF(dp->d_type); 689 brelse(bp); 690 return (1); 691 } 692 if (debug) 693 printf("ino %ju doesn't match dirent ino %ju in parent %ju\n", 694 (uintmax_t)child, (uintmax_t)dp->d_ino, (uintmax_t)parent); 695 brelse(bp); 696 return (0); 697 } 698 699 #define VISIT_INDIR 0x0001 700 #define VISIT_EXT 0x0002 701 #define VISIT_ROOT 0x0004 /* Operation came via root & valid pointers. */ 702 703 /* 704 * Read an indirect level which may or may not be linked into an inode. 705 */ 706 static void 707 indir_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, uint64_t *frags, 708 ino_visitor visitor, int flags) 709 { 710 struct bufarea *bp; 711 ufs_lbn_t lbnadd; 712 ufs2_daddr_t nblk; 713 ufs_lbn_t nlbn; 714 int level; 715 int i; 716 717 /* 718 * Don't visit indirect blocks with contents we can't trust. This 719 * should only happen when indir_visit() is called to complete a 720 * truncate that never finished and not when a pointer is found via 721 * an inode. 722 */ 723 if (blk == 0) 724 return; 725 level = lbn_level(lbn); 726 if (level == -1) 727 err_suj("Invalid level for lbn %jd\n", lbn); 728 if ((flags & VISIT_ROOT) == 0 && blk_isindir(blk, ino, lbn) == 0) { 729 if (debug) 730 printf("blk %jd ino %ju lbn %jd(%d) is not indir.\n", 731 blk, (uintmax_t)ino, lbn, level); 732 goto out; 733 } 734 lbnadd = 1; 735 for (i = level; i > 0; i--) 736 lbnadd *= NINDIR(fs); 737 bp = getdatablk(blk, fs->fs_bsize, BT_LEVEL1 + level); 738 if (bp->b_errs != 0) 739 err_suj("indir_visit: UNRECOVERABLE I/O ERROR"); 740 for (i = 0; i < NINDIR(fs); i++) { 741 if ((nblk = IBLK(bp, i)) == 0) 742 continue; 743 if (level == 0) { 744 nlbn = -lbn + i * lbnadd; 745 (*frags) += fs->fs_frag; 746 visitor(ino, nlbn, nblk, fs->fs_frag); 747 } else { 748 nlbn = (lbn + 1) - (i * lbnadd); 749 indir_visit(ino, nlbn, nblk, frags, visitor, flags); 750 } 751 } 752 brelse(bp); 753 out: 754 if (flags & VISIT_INDIR) { 755 (*frags) += fs->fs_frag; 756 visitor(ino, lbn, blk, fs->fs_frag); 757 } 758 } 759 760 /* 761 * Visit each block in an inode as specified by 'flags' and call a 762 * callback function. The callback may inspect or free blocks. The 763 * count of frags found according to the size in the file is returned. 764 * This is not valid for sparse files but may be used to determine 765 * the correct di_blocks for a file. 766 */ 767 static uint64_t 768 ino_visit(union dinode *dp, ino_t ino, ino_visitor visitor, int flags) 769 { 770 ufs_lbn_t nextlbn; 771 ufs_lbn_t tmpval; 772 ufs_lbn_t lbn; 773 uint64_t size; 774 uint64_t fragcnt; 775 int mode; 776 int frags; 777 int i; 778 779 size = DIP(dp, di_size); 780 mode = DIP(dp, di_mode) & IFMT; 781 fragcnt = 0; 782 if ((flags & VISIT_EXT) && 783 fs->fs_magic == FS_UFS2_MAGIC && dp->dp2.di_extsize) { 784 for (i = 0; i < UFS_NXADDR; i++) { 785 if (dp->dp2.di_extb[i] == 0) 786 continue; 787 frags = sblksize(fs, dp->dp2.di_extsize, i); 788 frags = numfrags(fs, frags); 789 fragcnt += frags; 790 visitor(ino, -1 - i, dp->dp2.di_extb[i], frags); 791 } 792 } 793 /* Skip datablocks for short links and devices. */ 794 if (mode == IFBLK || mode == IFCHR || 795 (mode == IFLNK && size < fs->fs_maxsymlinklen)) 796 return (fragcnt); 797 for (i = 0; i < UFS_NDADDR; i++) { 798 if (DIP(dp, di_db[i]) == 0) 799 continue; 800 frags = sblksize(fs, size, i); 801 frags = numfrags(fs, frags); 802 fragcnt += frags; 803 visitor(ino, i, DIP(dp, di_db[i]), frags); 804 } 805 /* 806 * We know the following indirects are real as we're following 807 * real pointers to them. 808 */ 809 flags |= VISIT_ROOT; 810 for (i = 0, tmpval = NINDIR(fs), lbn = UFS_NDADDR; i < UFS_NIADDR; i++, 811 lbn = nextlbn) { 812 nextlbn = lbn + tmpval; 813 tmpval *= NINDIR(fs); 814 if (DIP(dp, di_ib[i]) == 0) 815 continue; 816 indir_visit(ino, -lbn - i, DIP(dp, di_ib[i]), &fragcnt, visitor, 817 flags); 818 } 819 return (fragcnt); 820 } 821 822 /* 823 * Null visitor function used when we just want to count blocks and 824 * record the lbn. 825 */ 826 ufs_lbn_t visitlbn; 827 static void 828 null_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags) 829 { 830 if (lbn > 0) 831 visitlbn = lbn; 832 } 833 834 /* 835 * Recalculate di_blocks when we discover that a block allocation or 836 * free was not successfully completed. The kernel does not roll this back 837 * because it would be too expensive to compute which indirects were 838 * reachable at the time the inode was written. 839 */ 840 static void 841 ino_adjblks(struct suj_ino *sino) 842 { 843 struct inode ip; 844 union dinode *dp; 845 uint64_t blocks; 846 uint64_t frags; 847 off_t isize; 848 off_t size; 849 ino_t ino; 850 851 ino = sino->si_ino; 852 ginode(ino, &ip); 853 dp = ip.i_dp; 854 /* No need to adjust zero'd inodes. */ 855 if (DIP(dp, di_mode) == 0) { 856 irelse(&ip); 857 return; 858 } 859 /* 860 * Visit all blocks and count them as well as recording the last 861 * valid lbn in the file. If the file size doesn't agree with the 862 * last lbn we need to truncate to fix it. Otherwise just adjust 863 * the blocks count. 864 */ 865 visitlbn = 0; 866 frags = ino_visit(dp, ino, null_visit, VISIT_INDIR | VISIT_EXT); 867 blocks = fsbtodb(fs, frags); 868 /* 869 * We assume the size and direct block list is kept coherent by 870 * softdep. For files that have extended into indirects we truncate 871 * to the size in the inode or the maximum size permitted by 872 * populated indirects. 873 */ 874 if (visitlbn >= UFS_NDADDR) { 875 isize = DIP(dp, di_size); 876 size = lblktosize(fs, visitlbn + 1); 877 if (isize > size) 878 isize = size; 879 /* Always truncate to free any unpopulated indirects. */ 880 ino_trunc(ino, isize); 881 irelse(&ip); 882 return; 883 } 884 if (blocks == DIP(dp, di_blocks)) { 885 irelse(&ip); 886 return; 887 } 888 if (debug) 889 printf("ino %ju adjusting block count from %jd to %jd\n", 890 (uintmax_t)ino, DIP(dp, di_blocks), blocks); 891 DIP_SET(dp, di_blocks, blocks); 892 inodirty(&ip); 893 irelse(&ip); 894 } 895 896 static void 897 blk_free_visit(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags) 898 { 899 900 blk_free(ino, blk, blk_freemask(blk, ino, lbn, frags), frags); 901 } 902 903 /* 904 * Free a block or tree of blocks that was previously rooted in ino at 905 * the given lbn. If the lbn is an indirect all children are freed 906 * recursively. 907 */ 908 static void 909 blk_free_lbn(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t lbn, int frags, int follow) 910 { 911 uint64_t resid; 912 int mask; 913 914 mask = blk_freemask(blk, ino, lbn, frags); 915 resid = 0; 916 if (lbn <= -UFS_NDADDR && follow && mask == 0) 917 indir_visit(ino, lbn, blk, &resid, blk_free_visit, VISIT_INDIR); 918 else 919 blk_free(ino, blk, mask, frags); 920 } 921 922 static void 923 ino_setskip(struct suj_ino *sino, ino_t parent) 924 { 925 int isdot; 926 int mode; 927 928 if (ino_isat(sino->si_ino, DOTDOT_OFFSET, parent, &mode, &isdot)) 929 sino->si_skipparent = 1; 930 } 931 932 static void 933 ino_remref(ino_t parent, ino_t child, uint64_t diroff, int isdotdot) 934 { 935 struct suj_ino *sino; 936 struct suj_rec *srec; 937 struct jrefrec *rrec; 938 939 /* 940 * Lookup this inode to see if we have a record for it. 941 */ 942 sino = ino_lookup(child, 0); 943 /* 944 * Tell any child directories we've already removed their 945 * parent link cnt. Don't try to adjust our link down again. 946 */ 947 if (sino != NULL && isdotdot == 0) 948 ino_setskip(sino, parent); 949 /* 950 * No valid record for this inode. Just drop the on-disk 951 * link by one. 952 */ 953 if (sino == NULL || sino->si_hasrecs == 0) { 954 ino_decr(child); 955 return; 956 } 957 /* 958 * Use ino_adjust() if ino_check() has already processed this 959 * child. If we lose the last non-dot reference to a 960 * directory it will be discarded. 961 */ 962 if (sino->si_linkadj) { 963 if (sino->si_nlink == 0) 964 err_suj("ino_remref: ino %ld mode 0%o about to go " 965 "negative\n", sino->si_ino, sino->si_mode); 966 sino->si_nlink--; 967 if (isdotdot) 968 sino->si_dotlinks--; 969 ino_adjust(sino); 970 return; 971 } 972 /* 973 * If we haven't yet processed this inode we need to make 974 * sure we will successfully discover the lost path. If not 975 * use nlinkadj to remember. 976 */ 977 TAILQ_FOREACH(srec, &sino->si_recs, sr_next) { 978 rrec = (struct jrefrec *)srec->sr_rec; 979 if (rrec->jr_parent == parent && 980 rrec->jr_diroff == diroff) 981 return; 982 } 983 sino->si_nlinkadj++; 984 } 985 986 /* 987 * Free the children of a directory when the directory is discarded. 988 */ 989 static void 990 ino_free_children(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags) 991 { 992 struct suj_ino *sino; 993 struct bufarea *bp; 994 struct direct *dp; 995 off_t diroff; 996 int skipparent; 997 int isdotdot; 998 int dpoff; 999 int size; 1000 1001 sino = ino_lookup(ino, 0); 1002 if (sino) 1003 skipparent = sino->si_skipparent; 1004 else 1005 skipparent = 0; 1006 size = lfragtosize(fs, frags); 1007 bp = getdatablk(blk, size, BT_DIRDATA); 1008 if (bp->b_errs != 0) 1009 err_suj("ino_free_children: UNRECOVERABLE I/O ERROR"); 1010 dp = (struct direct *)&bp->b_un.b_buf[0]; 1011 for (dpoff = 0; dpoff < size && dp->d_reclen; dpoff += dp->d_reclen) { 1012 dp = (struct direct *)&bp->b_un.b_buf[dpoff]; 1013 if (dp->d_ino == 0 || dp->d_ino == UFS_WINO) 1014 continue; 1015 if (dp->d_namlen == 1 && dp->d_name[0] == '.') 1016 continue; 1017 isdotdot = dp->d_namlen == 2 && dp->d_name[0] == '.' && 1018 dp->d_name[1] == '.'; 1019 if (isdotdot && skipparent == 1) 1020 continue; 1021 if (debug) 1022 printf("Directory %ju removing ino %ju name %s\n", 1023 (uintmax_t)ino, (uintmax_t)dp->d_ino, dp->d_name); 1024 diroff = lblktosize(fs, lbn) + dpoff; 1025 ino_remref(ino, dp->d_ino, diroff, isdotdot); 1026 } 1027 brelse(bp); 1028 } 1029 1030 /* 1031 * Reclaim an inode, freeing all blocks and decrementing all children's 1032 * link counts. Free the inode back to the cg. 1033 */ 1034 static void 1035 ino_reclaim(struct inode *ip, ino_t ino, int mode) 1036 { 1037 union dinode *dp; 1038 uint32_t gen; 1039 1040 dp = ip->i_dp; 1041 if (ino == UFS_ROOTINO) 1042 err_suj("Attempting to free UFS_ROOTINO\n"); 1043 if (debug) 1044 printf("Truncating and freeing ino %ju, nlink %d, mode %o\n", 1045 (uintmax_t)ino, DIP(dp, di_nlink), DIP(dp, di_mode)); 1046 1047 /* We are freeing an inode or directory. */ 1048 if ((DIP(dp, di_mode) & IFMT) == IFDIR) 1049 ino_visit(dp, ino, ino_free_children, 0); 1050 DIP_SET(dp, di_nlink, 0); 1051 if ((DIP(dp, di_flags) & SF_SNAPSHOT) != 0) 1052 snapremove(ino); 1053 ino_visit(dp, ino, blk_free_visit, VISIT_EXT | VISIT_INDIR); 1054 /* Here we have to clear the inode and release any blocks it holds. */ 1055 gen = DIP(dp, di_gen); 1056 if (fs->fs_magic == FS_UFS1_MAGIC) 1057 bzero(dp, sizeof(struct ufs1_dinode)); 1058 else 1059 bzero(dp, sizeof(struct ufs2_dinode)); 1060 DIP_SET(dp, di_gen, gen); 1061 inodirty(ip); 1062 ino_free(ino, mode); 1063 return; 1064 } 1065 1066 /* 1067 * Adjust an inode's link count down by one when a directory goes away. 1068 */ 1069 static void 1070 ino_decr(ino_t ino) 1071 { 1072 struct inode ip; 1073 union dinode *dp; 1074 int reqlink; 1075 int nlink; 1076 int mode; 1077 1078 ginode(ino, &ip); 1079 dp = ip.i_dp; 1080 nlink = DIP(dp, di_nlink); 1081 mode = DIP(dp, di_mode); 1082 if (nlink < 1) 1083 err_suj("Inode %d link count %d invalid\n", ino, nlink); 1084 if (mode == 0) 1085 err_suj("Inode %d has a link of %d with 0 mode\n", ino, nlink); 1086 nlink--; 1087 if ((mode & IFMT) == IFDIR) 1088 reqlink = 2; 1089 else 1090 reqlink = 1; 1091 if (nlink < reqlink) { 1092 if (debug) 1093 printf("ino %ju not enough links to live %d < %d\n", 1094 (uintmax_t)ino, nlink, reqlink); 1095 ino_reclaim(&ip, ino, mode); 1096 irelse(&ip); 1097 return; 1098 } 1099 DIP_SET(dp, di_nlink, nlink); 1100 inodirty(&ip); 1101 irelse(&ip); 1102 } 1103 1104 /* 1105 * Adjust the inode link count to 'nlink'. If the count reaches zero 1106 * free it. 1107 */ 1108 static void 1109 ino_adjust(struct suj_ino *sino) 1110 { 1111 struct jrefrec *rrec; 1112 struct suj_rec *srec; 1113 struct suj_ino *stmp; 1114 union dinode *dp; 1115 struct inode ip; 1116 nlink_t nlink; 1117 nlink_t reqlink; 1118 int recmode; 1119 int isdot; 1120 int mode; 1121 ino_t ino; 1122 1123 nlink = sino->si_nlink; 1124 ino = sino->si_ino; 1125 mode = sino->si_mode & IFMT; 1126 /* 1127 * If it's a directory with no dot links, it was truncated before 1128 * the name was cleared. We need to clear the dirent that 1129 * points at it. 1130 */ 1131 if (mode == IFDIR && nlink == 1 && sino->si_dotlinks == 0) { 1132 sino->si_nlink = nlink = 0; 1133 TAILQ_FOREACH(srec, &sino->si_recs, sr_next) { 1134 rrec = (struct jrefrec *)srec->sr_rec; 1135 if (ino_isat(rrec->jr_parent, rrec->jr_diroff, ino, 1136 &recmode, &isdot) == 0) 1137 continue; 1138 ino_clrat(rrec->jr_parent, rrec->jr_diroff, ino); 1139 break; 1140 } 1141 if (srec == NULL) 1142 errx(1, "Directory %ju name not found", (uintmax_t)ino); 1143 } 1144 /* 1145 * If it's a directory with no real names pointing to it go ahead 1146 * and truncate it. This will free any children. 1147 */ 1148 if (mode == IFDIR && nlink - sino->si_dotlinks == 0) { 1149 sino->si_nlink = nlink = 0; 1150 /* 1151 * Mark any .. links so they know not to free this inode 1152 * when they are removed. 1153 */ 1154 TAILQ_FOREACH(srec, &sino->si_recs, sr_next) { 1155 rrec = (struct jrefrec *)srec->sr_rec; 1156 if (rrec->jr_diroff == DOTDOT_OFFSET) { 1157 stmp = ino_lookup(rrec->jr_parent, 0); 1158 if (stmp) 1159 ino_setskip(stmp, ino); 1160 } 1161 } 1162 } 1163 ginode(ino, &ip); 1164 dp = ip.i_dp; 1165 mode = DIP(dp, di_mode) & IFMT; 1166 if (nlink > UFS_LINK_MAX) 1167 err_suj("ino %ju nlink manipulation error, new %ju, old %d\n", 1168 (uintmax_t)ino, (uintmax_t)nlink, DIP(dp, di_nlink)); 1169 if (debug) 1170 printf("Adjusting ino %ju, nlink %ju, old link %d lastmode %o\n", 1171 (uintmax_t)ino, (uintmax_t)nlink, DIP(dp, di_nlink), 1172 sino->si_mode); 1173 if (mode == 0) { 1174 if (debug) 1175 printf("ino %ju, zero inode freeing bitmap\n", 1176 (uintmax_t)ino); 1177 ino_free(ino, sino->si_mode); 1178 irelse(&ip); 1179 return; 1180 } 1181 /* XXX Should be an assert? */ 1182 if (mode != sino->si_mode && debug) 1183 printf("ino %ju, mode %o != %o\n", 1184 (uintmax_t)ino, mode, sino->si_mode); 1185 if ((mode & IFMT) == IFDIR) 1186 reqlink = 2; 1187 else 1188 reqlink = 1; 1189 /* If the inode doesn't have enough links to live, free it. */ 1190 if (nlink < reqlink) { 1191 if (debug) 1192 printf("ino %ju not enough links to live %ju < %ju\n", 1193 (uintmax_t)ino, (uintmax_t)nlink, 1194 (uintmax_t)reqlink); 1195 ino_reclaim(&ip, ino, mode); 1196 irelse(&ip); 1197 return; 1198 } 1199 /* If required write the updated link count. */ 1200 if (DIP(dp, di_nlink) == nlink) { 1201 if (debug) 1202 printf("ino %ju, link matches, skipping.\n", 1203 (uintmax_t)ino); 1204 irelse(&ip); 1205 return; 1206 } 1207 DIP_SET(dp, di_nlink, nlink); 1208 inodirty(&ip); 1209 irelse(&ip); 1210 } 1211 1212 /* 1213 * Truncate some or all blocks in an indirect, freeing any that are required 1214 * and zeroing the indirect. 1215 */ 1216 static void 1217 indir_trunc(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, ufs_lbn_t lastlbn, 1218 union dinode *dp) 1219 { 1220 struct bufarea *bp; 1221 ufs_lbn_t lbnadd; 1222 ufs2_daddr_t nblk; 1223 ufs_lbn_t next; 1224 ufs_lbn_t nlbn; 1225 int isdirty; 1226 int level; 1227 int i; 1228 1229 if (blk == 0) 1230 return; 1231 isdirty = 0; 1232 level = lbn_level(lbn); 1233 if (level == -1) 1234 err_suj("Invalid level for lbn %jd\n", lbn); 1235 lbnadd = 1; 1236 for (i = level; i > 0; i--) 1237 lbnadd *= NINDIR(fs); 1238 bp = getdatablk(blk, fs->fs_bsize, BT_LEVEL1 + level); 1239 if (bp->b_errs != 0) 1240 err_suj("indir_trunc: UNRECOVERABLE I/O ERROR"); 1241 for (i = 0; i < NINDIR(fs); i++) { 1242 if ((nblk = IBLK(bp, i)) == 0) 1243 continue; 1244 if (level != 0) { 1245 nlbn = (lbn + 1) - (i * lbnadd); 1246 /* 1247 * Calculate the lbn of the next indirect to 1248 * determine if any of this indirect must be 1249 * reclaimed. 1250 */ 1251 next = -(lbn + level) + ((i+1) * lbnadd); 1252 if (next <= lastlbn) 1253 continue; 1254 indir_trunc(ino, nlbn, nblk, lastlbn, dp); 1255 /* If all of this indirect was reclaimed, free it. */ 1256 nlbn = next - lbnadd; 1257 if (nlbn < lastlbn) 1258 continue; 1259 } else { 1260 nlbn = -lbn + i * lbnadd; 1261 if (nlbn < lastlbn) 1262 continue; 1263 } 1264 isdirty = 1; 1265 blk_free(ino, nblk, 0, fs->fs_frag); 1266 IBLK_SET(bp, i, 0); 1267 } 1268 if (isdirty) 1269 dirty(bp); 1270 brelse(bp); 1271 } 1272 1273 /* 1274 * Truncate an inode to the minimum of the given size or the last populated 1275 * block after any over size have been discarded. The kernel would allocate 1276 * the last block in the file but fsck does not and neither do we. This 1277 * code never extends files, only shrinks them. 1278 */ 1279 static void 1280 ino_trunc(ino_t ino, off_t size) 1281 { 1282 struct inode ip; 1283 union dinode *dp; 1284 struct bufarea *bp; 1285 ufs2_daddr_t bn; 1286 uint64_t totalfrags; 1287 ufs_lbn_t nextlbn; 1288 ufs_lbn_t lastlbn; 1289 ufs_lbn_t tmpval; 1290 ufs_lbn_t lbn; 1291 ufs_lbn_t i; 1292 int blksize, frags; 1293 off_t cursize; 1294 off_t off; 1295 int mode; 1296 1297 ginode(ino, &ip); 1298 dp = ip.i_dp; 1299 mode = DIP(dp, di_mode) & IFMT; 1300 cursize = DIP(dp, di_size); 1301 /* If no size change, nothing to do */ 1302 if (size == cursize) { 1303 irelse(&ip); 1304 return; 1305 } 1306 if (debug) 1307 printf("Truncating ino %ju, mode %o to size %jd from size %jd\n", 1308 (uintmax_t)ino, mode, size, cursize); 1309 1310 /* Skip datablocks for short links and devices. */ 1311 if (mode == 0 || mode == IFBLK || mode == IFCHR || 1312 (mode == IFLNK && cursize < fs->fs_maxsymlinklen)) { 1313 irelse(&ip); 1314 return; 1315 } 1316 /* Don't extend. */ 1317 if (size > cursize) { 1318 irelse(&ip); 1319 return; 1320 } 1321 if ((DIP(dp, di_flags) & SF_SNAPSHOT) != 0) { 1322 if (size > 0) 1323 err_suj("Partial truncation of ino %ju snapshot file\n", 1324 (uintmax_t)ino); 1325 snapremove(ino); 1326 } 1327 lastlbn = lblkno(fs, blkroundup(fs, size)); 1328 for (i = lastlbn; i < UFS_NDADDR; i++) { 1329 if ((bn = DIP(dp, di_db[i])) == 0) 1330 continue; 1331 blksize = sblksize(fs, cursize, i); 1332 blk_free(ino, bn, 0, numfrags(fs, blksize)); 1333 DIP_SET(dp, di_db[i], 0); 1334 } 1335 /* 1336 * Follow indirect blocks, freeing anything required. 1337 */ 1338 for (i = 0, tmpval = NINDIR(fs), lbn = UFS_NDADDR; i < UFS_NIADDR; i++, 1339 lbn = nextlbn) { 1340 nextlbn = lbn + tmpval; 1341 tmpval *= NINDIR(fs); 1342 /* If we're not freeing any in this indirect range skip it. */ 1343 if (lastlbn >= nextlbn) 1344 continue; 1345 if ((bn = DIP(dp, di_ib[i])) == 0) 1346 continue; 1347 indir_trunc(ino, -lbn - i, bn, lastlbn, dp); 1348 /* If we freed everything in this indirect free the indir. */ 1349 if (lastlbn > lbn) 1350 continue; 1351 blk_free(ino, bn, 0, fs->fs_frag); 1352 DIP_SET(dp, di_ib[i], 0); 1353 } 1354 /* 1355 * Now that we've freed any whole blocks that exceed the desired 1356 * truncation size, figure out how many blocks remain and what the 1357 * last populated lbn is. We will set the size to this last lbn 1358 * rather than worrying about allocating the final lbn as the kernel 1359 * would've done. This is consistent with normal fsck behavior. 1360 */ 1361 visitlbn = 0; 1362 totalfrags = ino_visit(dp, ino, null_visit, VISIT_INDIR | VISIT_EXT); 1363 if (size > lblktosize(fs, visitlbn + 1)) 1364 size = lblktosize(fs, visitlbn + 1); 1365 /* 1366 * If we're truncating direct blocks we have to adjust frags 1367 * accordingly. 1368 */ 1369 if (visitlbn < UFS_NDADDR && totalfrags) { 1370 long oldspace, newspace; 1371 1372 bn = DIP(dp, di_db[visitlbn]); 1373 if (bn == 0) 1374 err_suj("Bad blk at ino %ju lbn %jd\n", 1375 (uintmax_t)ino, visitlbn); 1376 oldspace = sblksize(fs, cursize, visitlbn); 1377 newspace = sblksize(fs, size, visitlbn); 1378 if (oldspace != newspace) { 1379 bn += numfrags(fs, newspace); 1380 frags = numfrags(fs, oldspace - newspace); 1381 blk_free(ino, bn, 0, frags); 1382 totalfrags -= frags; 1383 } 1384 } 1385 DIP_SET(dp, di_blocks, fsbtodb(fs, totalfrags)); 1386 DIP_SET(dp, di_size, size); 1387 inodirty(&ip); 1388 /* 1389 * If we've truncated into the middle of a block or frag we have 1390 * to zero it here. Otherwise the file could extend into 1391 * uninitialized space later. 1392 */ 1393 off = blkoff(fs, size); 1394 if (off && DIP(dp, di_mode) != IFDIR) { 1395 long clrsize; 1396 1397 bn = ino_blkatoff(dp, ino, visitlbn, &frags, NULL); 1398 if (bn == 0) 1399 err_suj("Block missing from ino %ju at lbn %jd\n", 1400 (uintmax_t)ino, visitlbn); 1401 clrsize = frags * fs->fs_fsize; 1402 bp = getdatablk(bn, clrsize, BT_DATA); 1403 if (bp->b_errs != 0) 1404 err_suj("ino_trunc: UNRECOVERABLE I/O ERROR"); 1405 clrsize -= off; 1406 bzero(&bp->b_un.b_buf[off], clrsize); 1407 dirty(bp); 1408 brelse(bp); 1409 } 1410 irelse(&ip); 1411 return; 1412 } 1413 1414 /* 1415 * Process records available for one inode and determine whether the 1416 * link count is correct or needs adjusting. 1417 */ 1418 static void 1419 ino_check(struct suj_ino *sino) 1420 { 1421 struct suj_rec *srec; 1422 struct jrefrec *rrec; 1423 nlink_t dotlinks; 1424 nlink_t newlinks; 1425 nlink_t removes; 1426 nlink_t nlink; 1427 ino_t ino; 1428 int isdot; 1429 int isat; 1430 int mode; 1431 1432 if (sino->si_hasrecs == 0) 1433 return; 1434 ino = sino->si_ino; 1435 rrec = (struct jrefrec *)TAILQ_FIRST(&sino->si_recs)->sr_rec; 1436 nlink = rrec->jr_nlink; 1437 newlinks = 0; 1438 dotlinks = 0; 1439 removes = sino->si_nlinkadj; 1440 TAILQ_FOREACH(srec, &sino->si_recs, sr_next) { 1441 rrec = (struct jrefrec *)srec->sr_rec; 1442 isat = ino_isat(rrec->jr_parent, rrec->jr_diroff, 1443 rrec->jr_ino, &mode, &isdot); 1444 if (isat && (mode & IFMT) != (rrec->jr_mode & IFMT)) 1445 err_suj("Inode mode/directory type mismatch %o != %o\n", 1446 mode, rrec->jr_mode); 1447 if (debug) 1448 printf("jrefrec: op %d ino %ju, nlink %ju, parent %ju, " 1449 "diroff %jd, mode %o, isat %d, isdot %d\n", 1450 rrec->jr_op, (uintmax_t)rrec->jr_ino, 1451 (uintmax_t)rrec->jr_nlink, 1452 (uintmax_t)rrec->jr_parent, 1453 (uintmax_t)rrec->jr_diroff, 1454 rrec->jr_mode, isat, isdot); 1455 mode = rrec->jr_mode & IFMT; 1456 if (rrec->jr_op == JOP_REMREF) 1457 removes++; 1458 newlinks += isat; 1459 if (isdot) 1460 dotlinks += isat; 1461 } 1462 /* 1463 * The number of links that remain are the starting link count 1464 * subtracted by the total number of removes with the total 1465 * links discovered back in. An incomplete remove thus 1466 * makes no change to the link count but an add increases 1467 * by one. 1468 */ 1469 if (debug) 1470 printf( 1471 "ino %ju nlink %ju newlinks %ju removes %ju dotlinks %ju\n", 1472 (uintmax_t)ino, (uintmax_t)nlink, (uintmax_t)newlinks, 1473 (uintmax_t)removes, (uintmax_t)dotlinks); 1474 nlink += newlinks; 1475 nlink -= removes; 1476 sino->si_linkadj = 1; 1477 sino->si_nlink = nlink; 1478 sino->si_dotlinks = dotlinks; 1479 sino->si_mode = mode; 1480 ino_adjust(sino); 1481 } 1482 1483 /* 1484 * Process records available for one block and determine whether it is 1485 * still allocated and whether the owning inode needs to be updated or 1486 * a free completed. 1487 */ 1488 static void 1489 blk_check(struct suj_blk *sblk) 1490 { 1491 struct suj_rec *srec; 1492 struct jblkrec *brec; 1493 struct suj_ino *sino; 1494 ufs2_daddr_t blk; 1495 int mask; 1496 int frags; 1497 int isat; 1498 1499 /* 1500 * Each suj_blk actually contains records for any fragments in that 1501 * block. As a result we must evaluate each record individually. 1502 */ 1503 sino = NULL; 1504 TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) { 1505 brec = (struct jblkrec *)srec->sr_rec; 1506 frags = brec->jb_frags; 1507 blk = brec->jb_blkno + brec->jb_oldfrags; 1508 isat = blk_isat(brec->jb_ino, brec->jb_lbn, blk, &frags); 1509 if (sino == NULL || sino->si_ino != brec->jb_ino) { 1510 sino = ino_lookup(brec->jb_ino, 1); 1511 sino->si_blkadj = 1; 1512 } 1513 if (debug) 1514 printf("op %d blk %jd ino %ju lbn %jd frags %d isat %d (%d)\n", 1515 brec->jb_op, blk, (uintmax_t)brec->jb_ino, 1516 brec->jb_lbn, brec->jb_frags, isat, frags); 1517 /* 1518 * If we found the block at this address we still have to 1519 * determine if we need to free the tail end that was 1520 * added by adding contiguous fragments from the same block. 1521 */ 1522 if (isat == 1) { 1523 if (frags == brec->jb_frags) 1524 continue; 1525 mask = blk_freemask(blk, brec->jb_ino, brec->jb_lbn, 1526 brec->jb_frags); 1527 mask >>= frags; 1528 blk += frags; 1529 frags = brec->jb_frags - frags; 1530 blk_free(brec->jb_ino, blk, mask, frags); 1531 continue; 1532 } 1533 /* 1534 * The block wasn't found, attempt to free it. It won't be 1535 * freed if it was actually reallocated. If this was an 1536 * allocation we don't want to follow indirects as they 1537 * may not be written yet. Any children of the indirect will 1538 * have their own records. If it's a free we need to 1539 * recursively free children. 1540 */ 1541 blk_free_lbn(blk, brec->jb_ino, brec->jb_lbn, brec->jb_frags, 1542 brec->jb_op == JOP_FREEBLK); 1543 } 1544 } 1545 1546 /* 1547 * Walk the list of inode records for this cg and resolve moved and duplicate 1548 * inode references now that we have a complete picture. 1549 */ 1550 static void 1551 cg_build(struct suj_cg *sc) 1552 { 1553 struct suj_ino *sino; 1554 int i; 1555 1556 for (i = 0; i < HASHSIZE; i++) 1557 LIST_FOREACH(sino, &sc->sc_inohash[i], si_next) 1558 ino_build(sino); 1559 } 1560 1561 /* 1562 * Handle inodes requiring truncation. This must be done prior to 1563 * looking up any inodes in directories. 1564 */ 1565 static void 1566 cg_trunc(struct suj_cg *sc) 1567 { 1568 struct suj_ino *sino; 1569 int i; 1570 1571 for (i = 0; i < HASHSIZE; i++) { 1572 LIST_FOREACH(sino, &sc->sc_inohash[i], si_next) { 1573 if (sino->si_trunc) { 1574 ino_trunc(sino->si_ino, 1575 sino->si_trunc->jt_size); 1576 sino->si_blkadj = 0; 1577 sino->si_trunc = NULL; 1578 } 1579 if (sino->si_blkadj) 1580 ino_adjblks(sino); 1581 } 1582 } 1583 } 1584 1585 static void 1586 cg_adj_blk(struct suj_cg *sc) 1587 { 1588 struct suj_ino *sino; 1589 int i; 1590 1591 for (i = 0; i < HASHSIZE; i++) { 1592 LIST_FOREACH(sino, &sc->sc_inohash[i], si_next) { 1593 if (sino->si_blkadj) 1594 ino_adjblks(sino); 1595 } 1596 } 1597 } 1598 1599 /* 1600 * Free any partially allocated blocks and then resolve inode block 1601 * counts. 1602 */ 1603 static void 1604 cg_check_blk(struct suj_cg *sc) 1605 { 1606 struct suj_blk *sblk; 1607 int i; 1608 1609 1610 for (i = 0; i < HASHSIZE; i++) 1611 LIST_FOREACH(sblk, &sc->sc_blkhash[i], sb_next) 1612 blk_check(sblk); 1613 } 1614 1615 /* 1616 * Walk the list of inode records for this cg, recovering any 1617 * changes which were not complete at the time of crash. 1618 */ 1619 static void 1620 cg_check_ino(struct suj_cg *sc) 1621 { 1622 struct suj_ino *sino; 1623 int i; 1624 1625 for (i = 0; i < HASHSIZE; i++) 1626 LIST_FOREACH(sino, &sc->sc_inohash[i], si_next) 1627 ino_check(sino); 1628 } 1629 1630 static void 1631 cg_apply(void (*apply)(struct suj_cg *)) 1632 { 1633 struct suj_cg *scg; 1634 int i; 1635 1636 for (i = 0; i < HASHSIZE; i++) 1637 LIST_FOREACH(scg, &cghash[i], sc_next) 1638 apply(scg); 1639 } 1640 1641 /* 1642 * Process the unlinked but referenced file list. Freeing all inodes. 1643 */ 1644 static void 1645 ino_unlinked(void) 1646 { 1647 struct inode ip; 1648 union dinode *dp; 1649 uint16_t mode; 1650 ino_t inon; 1651 ino_t ino; 1652 1653 ino = fs->fs_sujfree; 1654 fs->fs_sujfree = 0; 1655 while (ino != 0) { 1656 ginode(ino, &ip); 1657 dp = ip.i_dp; 1658 mode = DIP(dp, di_mode) & IFMT; 1659 inon = DIP(dp, di_freelink); 1660 DIP_SET(dp, di_freelink, 0); 1661 inodirty(&ip); 1662 /* 1663 * XXX Should this be an errx? 1664 */ 1665 if (DIP(dp, di_nlink) == 0) { 1666 if (debug) 1667 printf("Freeing unlinked ino %ju mode %o\n", 1668 (uintmax_t)ino, mode); 1669 ino_reclaim(&ip, ino, mode); 1670 } else if (debug) 1671 printf("Skipping ino %ju mode %o with link %d\n", 1672 (uintmax_t)ino, mode, DIP(dp, di_nlink)); 1673 ino = inon; 1674 irelse(&ip); 1675 } 1676 } 1677 1678 /* 1679 * Append a new record to the list of records requiring processing. 1680 */ 1681 static void 1682 ino_append(union jrec *rec) 1683 { 1684 struct jrefrec *refrec; 1685 struct jmvrec *mvrec; 1686 struct suj_ino *sino; 1687 struct suj_rec *srec; 1688 1689 mvrec = &rec->rec_jmvrec; 1690 refrec = &rec->rec_jrefrec; 1691 if (debug && mvrec->jm_op == JOP_MVREF) 1692 printf("ino move: ino %ju, parent %ju, " 1693 "diroff %jd, oldoff %jd\n", 1694 (uintmax_t)mvrec->jm_ino, (uintmax_t)mvrec->jm_parent, 1695 (uintmax_t)mvrec->jm_newoff, (uintmax_t)mvrec->jm_oldoff); 1696 else if (debug && 1697 (refrec->jr_op == JOP_ADDREF || refrec->jr_op == JOP_REMREF)) 1698 printf("ino ref: op %d, ino %ju, nlink %ju, " 1699 "parent %ju, diroff %jd\n", 1700 refrec->jr_op, (uintmax_t)refrec->jr_ino, 1701 (uintmax_t)refrec->jr_nlink, 1702 (uintmax_t)refrec->jr_parent, (uintmax_t)refrec->jr_diroff); 1703 sino = ino_lookup(((struct jrefrec *)rec)->jr_ino, 1); 1704 sino->si_hasrecs = 1; 1705 srec = errmalloc(sizeof(*srec)); 1706 srec->sr_rec = rec; 1707 TAILQ_INSERT_TAIL(&sino->si_newrecs, srec, sr_next); 1708 } 1709 1710 /* 1711 * Add a reference adjustment to the sino list and eliminate dups. The 1712 * primary loop in ino_build_ref() checks for dups but new ones may be 1713 * created as a result of offset adjustments. 1714 */ 1715 static void 1716 ino_add_ref(struct suj_ino *sino, struct suj_rec *srec) 1717 { 1718 struct jrefrec *refrec; 1719 struct suj_rec *srn; 1720 struct jrefrec *rrn; 1721 1722 refrec = (struct jrefrec *)srec->sr_rec; 1723 /* 1724 * We walk backwards so that the oldest link count is preserved. If 1725 * an add record conflicts with a remove keep the remove. Redundant 1726 * removes are eliminated in ino_build_ref. Otherwise we keep the 1727 * oldest record at a given location. 1728 */ 1729 for (srn = TAILQ_LAST(&sino->si_recs, srechd); srn; 1730 srn = TAILQ_PREV(srn, srechd, sr_next)) { 1731 rrn = (struct jrefrec *)srn->sr_rec; 1732 if (rrn->jr_parent != refrec->jr_parent || 1733 rrn->jr_diroff != refrec->jr_diroff) 1734 continue; 1735 if (rrn->jr_op == JOP_REMREF || refrec->jr_op == JOP_ADDREF) { 1736 rrn->jr_mode = refrec->jr_mode; 1737 return; 1738 } 1739 /* 1740 * Adding a remove. 1741 * 1742 * Replace the record in place with the old nlink in case 1743 * we replace the head of the list. Abandon srec as a dup. 1744 */ 1745 refrec->jr_nlink = rrn->jr_nlink; 1746 srn->sr_rec = srec->sr_rec; 1747 return; 1748 } 1749 TAILQ_INSERT_TAIL(&sino->si_recs, srec, sr_next); 1750 } 1751 1752 /* 1753 * Create a duplicate of a reference at a previous location. 1754 */ 1755 static void 1756 ino_dup_ref(struct suj_ino *sino, struct jrefrec *refrec, off_t diroff) 1757 { 1758 struct jrefrec *rrn; 1759 struct suj_rec *srn; 1760 1761 rrn = errmalloc(sizeof(*refrec)); 1762 *rrn = *refrec; 1763 rrn->jr_op = JOP_ADDREF; 1764 rrn->jr_diroff = diroff; 1765 srn = errmalloc(sizeof(*srn)); 1766 srn->sr_rec = (union jrec *)rrn; 1767 ino_add_ref(sino, srn); 1768 } 1769 1770 /* 1771 * Add a reference to the list at all known locations. We follow the offset 1772 * changes for a single instance and create duplicate add refs at each so 1773 * that we can tolerate any version of the directory block. Eliminate 1774 * removes which collide with adds that are seen in the journal. They should 1775 * not adjust the link count down. 1776 */ 1777 static void 1778 ino_build_ref(struct suj_ino *sino, struct suj_rec *srec) 1779 { 1780 struct jrefrec *refrec; 1781 struct jmvrec *mvrec; 1782 struct suj_rec *srp; 1783 struct suj_rec *srn; 1784 struct jrefrec *rrn; 1785 off_t diroff; 1786 1787 refrec = (struct jrefrec *)srec->sr_rec; 1788 /* 1789 * Search for a mvrec that matches this offset. Whether it's an add 1790 * or a remove we can delete the mvref after creating a dup record in 1791 * the old location. 1792 */ 1793 if (!TAILQ_EMPTY(&sino->si_movs)) { 1794 diroff = refrec->jr_diroff; 1795 for (srn = TAILQ_LAST(&sino->si_movs, srechd); srn; srn = srp) { 1796 srp = TAILQ_PREV(srn, srechd, sr_next); 1797 mvrec = (struct jmvrec *)srn->sr_rec; 1798 if (mvrec->jm_parent != refrec->jr_parent || 1799 mvrec->jm_newoff != diroff) 1800 continue; 1801 diroff = mvrec->jm_oldoff; 1802 TAILQ_REMOVE(&sino->si_movs, srn, sr_next); 1803 free(srn); 1804 ino_dup_ref(sino, refrec, diroff); 1805 } 1806 } 1807 /* 1808 * If a remove wasn't eliminated by an earlier add just append it to 1809 * the list. 1810 */ 1811 if (refrec->jr_op == JOP_REMREF) { 1812 ino_add_ref(sino, srec); 1813 return; 1814 } 1815 /* 1816 * Walk the list of records waiting to be added to the list. We 1817 * must check for moves that apply to our current offset and remove 1818 * them from the list. Remove any duplicates to eliminate removes 1819 * with corresponding adds. 1820 */ 1821 TAILQ_FOREACH_SAFE(srn, &sino->si_newrecs, sr_next, srp) { 1822 switch (srn->sr_rec->rec_jrefrec.jr_op) { 1823 case JOP_ADDREF: 1824 /* 1825 * This should actually be an error we should 1826 * have a remove for every add journaled. 1827 */ 1828 rrn = (struct jrefrec *)srn->sr_rec; 1829 if (rrn->jr_parent != refrec->jr_parent || 1830 rrn->jr_diroff != refrec->jr_diroff) 1831 break; 1832 TAILQ_REMOVE(&sino->si_newrecs, srn, sr_next); 1833 break; 1834 case JOP_REMREF: 1835 /* 1836 * Once we remove the current iteration of the 1837 * record at this address we're done. 1838 */ 1839 rrn = (struct jrefrec *)srn->sr_rec; 1840 if (rrn->jr_parent != refrec->jr_parent || 1841 rrn->jr_diroff != refrec->jr_diroff) 1842 break; 1843 TAILQ_REMOVE(&sino->si_newrecs, srn, sr_next); 1844 ino_add_ref(sino, srec); 1845 return; 1846 case JOP_MVREF: 1847 /* 1848 * Update our diroff based on any moves that match 1849 * and remove the move. 1850 */ 1851 mvrec = (struct jmvrec *)srn->sr_rec; 1852 if (mvrec->jm_parent != refrec->jr_parent || 1853 mvrec->jm_oldoff != refrec->jr_diroff) 1854 break; 1855 ino_dup_ref(sino, refrec, mvrec->jm_oldoff); 1856 refrec->jr_diroff = mvrec->jm_newoff; 1857 TAILQ_REMOVE(&sino->si_newrecs, srn, sr_next); 1858 break; 1859 default: 1860 err_suj("ino_build_ref: Unknown op %d\n", 1861 srn->sr_rec->rec_jrefrec.jr_op); 1862 } 1863 } 1864 ino_add_ref(sino, srec); 1865 } 1866 1867 /* 1868 * Walk the list of new records and add them in-order resolving any 1869 * dups and adjusted offsets. 1870 */ 1871 static void 1872 ino_build(struct suj_ino *sino) 1873 { 1874 struct suj_rec *srec; 1875 1876 while ((srec = TAILQ_FIRST(&sino->si_newrecs)) != NULL) { 1877 TAILQ_REMOVE(&sino->si_newrecs, srec, sr_next); 1878 switch (srec->sr_rec->rec_jrefrec.jr_op) { 1879 case JOP_ADDREF: 1880 case JOP_REMREF: 1881 ino_build_ref(sino, srec); 1882 break; 1883 case JOP_MVREF: 1884 /* 1885 * Add this mvrec to the queue of pending mvs. 1886 */ 1887 TAILQ_INSERT_TAIL(&sino->si_movs, srec, sr_next); 1888 break; 1889 default: 1890 err_suj("ino_build: Unknown op %d\n", 1891 srec->sr_rec->rec_jrefrec.jr_op); 1892 } 1893 } 1894 if (TAILQ_EMPTY(&sino->si_recs)) 1895 sino->si_hasrecs = 0; 1896 } 1897 1898 /* 1899 * Modify journal records so they refer to the base block number 1900 * and a start and end frag range. This is to facilitate the discovery 1901 * of overlapping fragment allocations. 1902 */ 1903 static void 1904 blk_build(struct jblkrec *blkrec) 1905 { 1906 struct suj_rec *srec; 1907 struct suj_blk *sblk; 1908 struct jblkrec *blkrn; 1909 ufs2_daddr_t blk; 1910 int frag; 1911 1912 if (debug) 1913 printf("blk_build: op %d blkno %jd frags %d oldfrags %d " 1914 "ino %ju lbn %jd\n", 1915 blkrec->jb_op, (uintmax_t)blkrec->jb_blkno, 1916 blkrec->jb_frags, blkrec->jb_oldfrags, 1917 (uintmax_t)blkrec->jb_ino, (uintmax_t)blkrec->jb_lbn); 1918 1919 blk = blknum(fs, blkrec->jb_blkno); 1920 frag = fragnum(fs, blkrec->jb_blkno); 1921 sblk = blk_lookup(blk, 1); 1922 /* 1923 * Rewrite the record using oldfrags to indicate the offset into 1924 * the block. Leave jb_frags as the actual allocated count. 1925 */ 1926 blkrec->jb_blkno -= frag; 1927 blkrec->jb_oldfrags = frag; 1928 if (blkrec->jb_oldfrags + blkrec->jb_frags > fs->fs_frag) 1929 err_suj("Invalid fragment count %d oldfrags %d\n", 1930 blkrec->jb_frags, frag); 1931 /* 1932 * Detect dups. If we detect a dup we always discard the oldest 1933 * record as it is superseded by the new record. This speeds up 1934 * later stages but also eliminates free records which are used 1935 * to indicate that the contents of indirects can be trusted. 1936 */ 1937 TAILQ_FOREACH(srec, &sblk->sb_recs, sr_next) { 1938 blkrn = (struct jblkrec *)srec->sr_rec; 1939 if (blkrn->jb_ino != blkrec->jb_ino || 1940 blkrn->jb_lbn != blkrec->jb_lbn || 1941 blkrn->jb_blkno != blkrec->jb_blkno || 1942 blkrn->jb_frags != blkrec->jb_frags || 1943 blkrn->jb_oldfrags != blkrec->jb_oldfrags) 1944 continue; 1945 if (debug) 1946 printf("Removed dup.\n"); 1947 /* Discard the free which is a dup with an alloc. */ 1948 if (blkrec->jb_op == JOP_FREEBLK) 1949 return; 1950 TAILQ_REMOVE(&sblk->sb_recs, srec, sr_next); 1951 free(srec); 1952 break; 1953 } 1954 srec = errmalloc(sizeof(*srec)); 1955 srec->sr_rec = (union jrec *)blkrec; 1956 TAILQ_INSERT_TAIL(&sblk->sb_recs, srec, sr_next); 1957 } 1958 1959 static void 1960 ino_build_trunc(struct jtrncrec *rec) 1961 { 1962 struct suj_ino *sino; 1963 1964 if (debug) 1965 printf("ino_build_trunc: op %d ino %ju, size %jd\n", 1966 rec->jt_op, (uintmax_t)rec->jt_ino, 1967 (uintmax_t)rec->jt_size); 1968 sino = ino_lookup(rec->jt_ino, 1); 1969 if (rec->jt_op == JOP_SYNC) { 1970 sino->si_trunc = NULL; 1971 return; 1972 } 1973 if (sino->si_trunc == NULL || sino->si_trunc->jt_size > rec->jt_size) 1974 sino->si_trunc = rec; 1975 } 1976 1977 /* 1978 * Build up tables of the operations we need to recover. 1979 */ 1980 static void 1981 suj_build(void) 1982 { 1983 struct suj_seg *seg; 1984 union jrec *rec; 1985 int off; 1986 int i; 1987 1988 TAILQ_FOREACH(seg, &allsegs, ss_next) { 1989 if (debug) 1990 printf("seg %jd has %d records, oldseq %jd.\n", 1991 seg->ss_rec.jsr_seq, seg->ss_rec.jsr_cnt, 1992 seg->ss_rec.jsr_oldest); 1993 off = 0; 1994 rec = (union jrec *)seg->ss_blk; 1995 for (i = 0; i < seg->ss_rec.jsr_cnt; off += JREC_SIZE, rec++) { 1996 /* skip the segrec. */ 1997 if ((off % real_dev_bsize) == 0) 1998 continue; 1999 switch (rec->rec_jrefrec.jr_op) { 2000 case JOP_ADDREF: 2001 case JOP_REMREF: 2002 case JOP_MVREF: 2003 ino_append(rec); 2004 break; 2005 case JOP_NEWBLK: 2006 case JOP_FREEBLK: 2007 blk_build((struct jblkrec *)rec); 2008 break; 2009 case JOP_TRUNC: 2010 case JOP_SYNC: 2011 ino_build_trunc((struct jtrncrec *)rec); 2012 break; 2013 default: 2014 err_suj("Unknown journal operation %d (%d)\n", 2015 rec->rec_jrefrec.jr_op, off); 2016 } 2017 i++; 2018 } 2019 } 2020 } 2021 2022 /* 2023 * Prune the journal segments to those we care about based on the 2024 * oldest sequence in the newest segment. Order the segment list 2025 * based on sequence number. 2026 */ 2027 static void 2028 suj_prune(void) 2029 { 2030 struct suj_seg *seg; 2031 struct suj_seg *segn; 2032 uint64_t newseq; 2033 int discard; 2034 2035 if (debug) 2036 printf("Pruning up to %jd\n", oldseq); 2037 /* First free the expired segments. */ 2038 TAILQ_FOREACH_SAFE(seg, &allsegs, ss_next, segn) { 2039 if (seg->ss_rec.jsr_seq >= oldseq) 2040 continue; 2041 TAILQ_REMOVE(&allsegs, seg, ss_next); 2042 free(seg->ss_blk); 2043 free(seg); 2044 } 2045 /* Next ensure that segments are ordered properly. */ 2046 seg = TAILQ_FIRST(&allsegs); 2047 if (seg == NULL) { 2048 if (debug) 2049 printf("Empty journal\n"); 2050 return; 2051 } 2052 newseq = seg->ss_rec.jsr_seq; 2053 for (;;) { 2054 seg = TAILQ_LAST(&allsegs, seghd); 2055 if (seg->ss_rec.jsr_seq >= newseq) 2056 break; 2057 TAILQ_REMOVE(&allsegs, seg, ss_next); 2058 TAILQ_INSERT_HEAD(&allsegs, seg, ss_next); 2059 newseq = seg->ss_rec.jsr_seq; 2060 2061 } 2062 if (newseq != oldseq) { 2063 TAILQ_FOREACH(seg, &allsegs, ss_next) { 2064 printf("%jd, ", seg->ss_rec.jsr_seq); 2065 } 2066 printf("\n"); 2067 err_suj("Journal file sequence mismatch %jd != %jd\n", 2068 newseq, oldseq); 2069 } 2070 /* 2071 * The kernel may asynchronously write segments which can create 2072 * gaps in the sequence space. Throw away any segments after the 2073 * gap as the kernel guarantees only those that are contiguously 2074 * reachable are marked as completed. 2075 */ 2076 discard = 0; 2077 TAILQ_FOREACH_SAFE(seg, &allsegs, ss_next, segn) { 2078 if (!discard && newseq++ == seg->ss_rec.jsr_seq) { 2079 jrecs += seg->ss_rec.jsr_cnt; 2080 jbytes += seg->ss_rec.jsr_blocks * real_dev_bsize; 2081 continue; 2082 } 2083 discard = 1; 2084 if (debug) 2085 printf("Journal order mismatch %jd != %jd pruning\n", 2086 newseq-1, seg->ss_rec.jsr_seq); 2087 TAILQ_REMOVE(&allsegs, seg, ss_next); 2088 free(seg->ss_blk); 2089 free(seg); 2090 } 2091 if (debug) 2092 printf("Processing journal segments from %jd to %jd\n", 2093 oldseq, newseq-1); 2094 } 2095 2096 /* 2097 * Verify the journal inode before attempting to read records. 2098 */ 2099 static int 2100 suj_verifyino(union dinode *dp) 2101 { 2102 2103 if (DIP(dp, di_nlink) != 1) { 2104 printf("Invalid link count %d for journal inode %ju\n", 2105 DIP(dp, di_nlink), (uintmax_t)sujino); 2106 return (-1); 2107 } 2108 2109 if ((DIP(dp, di_flags) & (SF_IMMUTABLE | SF_NOUNLINK)) != 2110 (SF_IMMUTABLE | SF_NOUNLINK)) { 2111 printf("Invalid flags 0x%X for journal inode %ju\n", 2112 DIP(dp, di_flags), (uintmax_t)sujino); 2113 return (-1); 2114 } 2115 2116 if (DIP(dp, di_mode) != (IFREG | IREAD)) { 2117 printf("Invalid mode %o for journal inode %ju\n", 2118 DIP(dp, di_mode), (uintmax_t)sujino); 2119 return (-1); 2120 } 2121 2122 if (DIP(dp, di_size) < SUJ_MIN) { 2123 printf("Invalid size %jd for journal inode %ju\n", 2124 DIP(dp, di_size), (uintmax_t)sujino); 2125 return (-1); 2126 } 2127 2128 if (DIP(dp, di_modrev) != fs->fs_mtime) { 2129 printf("Journal timestamp does not match fs mount time\n"); 2130 return (-1); 2131 } 2132 2133 return (0); 2134 } 2135 2136 struct jblocks { 2137 struct jextent *jb_extent; /* Extent array. */ 2138 int jb_avail; /* Available extents. */ 2139 int jb_used; /* Last used extent. */ 2140 int jb_head; /* Allocator head. */ 2141 int jb_off; /* Allocator extent offset. */ 2142 }; 2143 struct jextent { 2144 ufs2_daddr_t je_daddr; /* Disk block address. */ 2145 int je_blocks; /* Disk block count. */ 2146 }; 2147 2148 static struct jblocks *suj_jblocks; 2149 2150 static struct jblocks * 2151 jblocks_create(void) 2152 { 2153 struct jblocks *jblocks; 2154 int size; 2155 2156 jblocks = errmalloc(sizeof(*jblocks)); 2157 jblocks->jb_avail = 10; 2158 jblocks->jb_used = 0; 2159 jblocks->jb_head = 0; 2160 jblocks->jb_off = 0; 2161 size = sizeof(struct jextent) * jblocks->jb_avail; 2162 jblocks->jb_extent = errmalloc(size); 2163 bzero(jblocks->jb_extent, size); 2164 2165 return (jblocks); 2166 } 2167 2168 /* 2169 * Return the next available disk block and the amount of contiguous 2170 * free space it contains. 2171 */ 2172 static ufs2_daddr_t 2173 jblocks_next(struct jblocks *jblocks, int bytes, int *actual) 2174 { 2175 struct jextent *jext; 2176 ufs2_daddr_t daddr; 2177 int freecnt; 2178 int blocks; 2179 2180 blocks = btodb(bytes); 2181 jext = &jblocks->jb_extent[jblocks->jb_head]; 2182 freecnt = jext->je_blocks - jblocks->jb_off; 2183 if (freecnt == 0) { 2184 jblocks->jb_off = 0; 2185 if (++jblocks->jb_head > jblocks->jb_used) 2186 return (0); 2187 jext = &jblocks->jb_extent[jblocks->jb_head]; 2188 freecnt = jext->je_blocks; 2189 } 2190 if (freecnt > blocks) 2191 freecnt = blocks; 2192 *actual = dbtob(freecnt); 2193 daddr = jext->je_daddr + jblocks->jb_off; 2194 2195 return (daddr); 2196 } 2197 2198 /* 2199 * Advance the allocation head by a specified number of bytes, consuming 2200 * one journal segment. 2201 */ 2202 static void 2203 jblocks_advance(struct jblocks *jblocks, int bytes) 2204 { 2205 2206 jblocks->jb_off += btodb(bytes); 2207 } 2208 2209 static void 2210 jblocks_destroy(struct jblocks *jblocks) 2211 { 2212 2213 free(jblocks->jb_extent); 2214 free(jblocks); 2215 } 2216 2217 static void 2218 jblocks_add(struct jblocks *jblocks, ufs2_daddr_t daddr, int blocks) 2219 { 2220 struct jextent *jext; 2221 int size; 2222 2223 jext = &jblocks->jb_extent[jblocks->jb_used]; 2224 /* Adding the first block. */ 2225 if (jext->je_daddr == 0) { 2226 jext->je_daddr = daddr; 2227 jext->je_blocks = blocks; 2228 return; 2229 } 2230 /* Extending the last extent. */ 2231 if (jext->je_daddr + jext->je_blocks == daddr) { 2232 jext->je_blocks += blocks; 2233 return; 2234 } 2235 /* Adding a new extent. */ 2236 if (++jblocks->jb_used == jblocks->jb_avail) { 2237 jblocks->jb_avail *= 2; 2238 size = sizeof(struct jextent) * jblocks->jb_avail; 2239 jext = errmalloc(size); 2240 bzero(jext, size); 2241 bcopy(jblocks->jb_extent, jext, 2242 sizeof(struct jextent) * jblocks->jb_used); 2243 free(jblocks->jb_extent); 2244 jblocks->jb_extent = jext; 2245 } 2246 jext = &jblocks->jb_extent[jblocks->jb_used]; 2247 jext->je_daddr = daddr; 2248 jext->je_blocks = blocks; 2249 2250 return; 2251 } 2252 2253 /* 2254 * Add a file block from the journal to the extent map. We can't read 2255 * each file block individually because the kernel treats it as a circular 2256 * buffer and segments may span mutliple contiguous blocks. 2257 */ 2258 static void 2259 suj_add_block(ino_t ino, ufs_lbn_t lbn, ufs2_daddr_t blk, int frags) 2260 { 2261 2262 jblocks_add(suj_jblocks, fsbtodb(fs, blk), fsbtodb(fs, frags)); 2263 } 2264 2265 static void 2266 suj_read(void) 2267 { 2268 uint8_t block[1 * 1024 * 1024]; 2269 struct suj_seg *seg; 2270 struct jsegrec *recn; 2271 struct jsegrec *rec; 2272 ufs2_daddr_t blk; 2273 int readsize; 2274 int blocks; 2275 int recsize; 2276 int size; 2277 int i; 2278 2279 /* 2280 * Read records until we exhaust the journal space. If we find 2281 * an invalid record we start searching for a valid segment header 2282 * at the next block. This is because we don't have a head/tail 2283 * pointer and must recover the information indirectly. At the gap 2284 * between the head and tail we won't necessarily have a valid 2285 * segment. 2286 */ 2287 restart: 2288 for (;;) { 2289 size = sizeof(block); 2290 blk = jblocks_next(suj_jblocks, size, &readsize); 2291 if (blk == 0) 2292 return; 2293 size = readsize; 2294 /* 2295 * Read 1MB at a time and scan for records within this block. 2296 */ 2297 if (pread(fsreadfd, &block, size, dbtob(blk)) != size) { 2298 err_suj("Error reading journal block %jd\n", 2299 (intmax_t)blk); 2300 } 2301 for (rec = (void *)block; size; size -= recsize, 2302 rec = (struct jsegrec *)((uintptr_t)rec + recsize)) { 2303 recsize = real_dev_bsize; 2304 if (rec->jsr_time != fs->fs_mtime) { 2305 #ifdef notdef 2306 if (debug) 2307 printf("Rec time %jd != fs mtime %jd\n", 2308 rec->jsr_time, fs->fs_mtime); 2309 #endif 2310 jblocks_advance(suj_jblocks, recsize); 2311 continue; 2312 } 2313 if (rec->jsr_cnt == 0) { 2314 if (debug) 2315 printf("Found illegal count %d\n", 2316 rec->jsr_cnt); 2317 jblocks_advance(suj_jblocks, recsize); 2318 continue; 2319 } 2320 blocks = rec->jsr_blocks; 2321 recsize = blocks * real_dev_bsize; 2322 if (recsize > size) { 2323 /* 2324 * We may just have run out of buffer, restart 2325 * the loop to re-read from this spot. 2326 */ 2327 if (size < fs->fs_bsize && 2328 size != readsize && 2329 recsize <= fs->fs_bsize) 2330 goto restart; 2331 if (debug) 2332 printf("Found invalid segsize %d > %d\n", 2333 recsize, size); 2334 recsize = real_dev_bsize; 2335 jblocks_advance(suj_jblocks, recsize); 2336 continue; 2337 } 2338 /* 2339 * Verify that all blocks in the segment are present. 2340 */ 2341 for (i = 1; i < blocks; i++) { 2342 recn = (void *)((uintptr_t)rec) + i * 2343 real_dev_bsize; 2344 if (recn->jsr_seq == rec->jsr_seq && 2345 recn->jsr_time == rec->jsr_time) 2346 continue; 2347 if (debug) 2348 printf("Incomplete record %jd (%d)\n", 2349 rec->jsr_seq, i); 2350 recsize = i * real_dev_bsize; 2351 jblocks_advance(suj_jblocks, recsize); 2352 goto restart; 2353 } 2354 seg = errmalloc(sizeof(*seg)); 2355 seg->ss_blk = errmalloc(recsize); 2356 seg->ss_rec = *rec; 2357 bcopy((void *)rec, seg->ss_blk, recsize); 2358 if (rec->jsr_oldest > oldseq) 2359 oldseq = rec->jsr_oldest; 2360 TAILQ_INSERT_TAIL(&allsegs, seg, ss_next); 2361 jblocks_advance(suj_jblocks, recsize); 2362 } 2363 } 2364 } 2365 2366 /* 2367 * Orchestrate the verification of a filesystem via the softupdates journal. 2368 */ 2369 int 2370 suj_check(const char *filesys) 2371 { 2372 struct inodesc idesc; 2373 struct csum *cgsum; 2374 union dinode *jip; 2375 struct inode ip; 2376 uint64_t blocks; 2377 int i, retval; 2378 struct suj_seg *seg; 2379 struct suj_seg *segn; 2380 2381 initsuj(); 2382 fs = &sblock; 2383 if (real_dev_bsize == 0 && ioctl(fsreadfd, DIOCGSECTORSIZE, 2384 &real_dev_bsize) == -1) 2385 real_dev_bsize = secsize; 2386 if (debug) 2387 printf("dev_bsize %u\n", real_dev_bsize); 2388 2389 /* 2390 * Set an exit point when SUJ check failed 2391 */ 2392 retval = setjmp(jmpbuf); 2393 if (retval != 0) { 2394 pwarn("UNEXPECTED SU+J INCONSISTENCY\n"); 2395 TAILQ_FOREACH_SAFE(seg, &allsegs, ss_next, segn) { 2396 TAILQ_REMOVE(&allsegs, seg, ss_next); 2397 free(seg->ss_blk); 2398 free(seg); 2399 } 2400 if (reply("FALLBACK TO FULL FSCK") == 0) { 2401 ckfini(0); 2402 exit(EEXIT); 2403 } else 2404 return (-1); 2405 } 2406 2407 /* 2408 * Search the root directory for the SUJ_FILE. 2409 */ 2410 idesc.id_type = DATA; 2411 idesc.id_fix = IGNORE; 2412 idesc.id_number = UFS_ROOTINO; 2413 idesc.id_func = findino; 2414 idesc.id_name = SUJ_FILE; 2415 ginode(UFS_ROOTINO, &ip); 2416 if ((ckinode(ip.i_dp, &idesc) & FOUND) == FOUND) { 2417 sujino = idesc.id_parent; 2418 irelse(&ip); 2419 } else { 2420 printf("Journal inode removed. Use tunefs to re-create.\n"); 2421 sblock.fs_flags &= ~FS_SUJ; 2422 sblock.fs_sujfree = 0; 2423 irelse(&ip); 2424 return (-1); 2425 } 2426 /* 2427 * Fetch the journal inode and verify it. 2428 */ 2429 ginode(sujino, &ip); 2430 jip = ip.i_dp; 2431 printf("** SU+J Recovering %s\n", filesys); 2432 if (suj_verifyino(jip) != 0 || (!preen && !reply("USE JOURNAL"))) { 2433 irelse(&ip); 2434 return (-1); 2435 } 2436 /* 2437 * Build a list of journal blocks in jblocks before parsing the 2438 * available journal blocks in with suj_read(). 2439 */ 2440 printf("** Reading %jd byte journal from inode %ju.\n", 2441 DIP(jip, di_size), (uintmax_t)sujino); 2442 suj_jblocks = jblocks_create(); 2443 blocks = ino_visit(jip, sujino, suj_add_block, 0); 2444 if (blocks != numfrags(fs, DIP(jip, di_size))) { 2445 printf("Sparse journal inode %ju.\n", (uintmax_t)sujino); 2446 irelse(&ip); 2447 return (-1); 2448 } 2449 irelse(&ip); 2450 suj_read(); 2451 jblocks_destroy(suj_jblocks); 2452 suj_jblocks = NULL; 2453 if (preen || reply("RECOVER")) { 2454 printf("** Building recovery table.\n"); 2455 suj_prune(); 2456 suj_build(); 2457 cg_apply(cg_build); 2458 printf("** Resolving unreferenced inode list.\n"); 2459 ino_unlinked(); 2460 printf("** Processing journal entries.\n"); 2461 cg_apply(cg_trunc); 2462 cg_apply(cg_check_blk); 2463 cg_apply(cg_adj_blk); 2464 cg_apply(cg_check_ino); 2465 } 2466 if (preen == 0 && (jrecs > 0 || jbytes > 0) && reply("WRITE CHANGES") == 0) 2467 return (0); 2468 /* 2469 * Check block counts of snapshot inodes and 2470 * make copies of any needed snapshot blocks. 2471 */ 2472 for (i = 0; i < snapcnt; i++) 2473 check_blkcnt(&snaplist[i]); 2474 snapflush(suj_checkblkavail); 2475 /* 2476 * Recompute the fs summary info from correct cs summaries. 2477 */ 2478 bzero(&fs->fs_cstotal, sizeof(struct csum_total)); 2479 for (i = 0; i < fs->fs_ncg; i++) { 2480 cgsum = &fs->fs_cs(fs, i); 2481 fs->fs_cstotal.cs_nffree += cgsum->cs_nffree; 2482 fs->fs_cstotal.cs_nbfree += cgsum->cs_nbfree; 2483 fs->fs_cstotal.cs_nifree += cgsum->cs_nifree; 2484 fs->fs_cstotal.cs_ndir += cgsum->cs_ndir; 2485 } 2486 fs->fs_pendinginodes = 0; 2487 fs->fs_pendingblocks = 0; 2488 fs->fs_clean = 1; 2489 fs->fs_time = time(NULL); 2490 fs->fs_mtime = time(NULL); 2491 sbdirty(); 2492 ckfini(1); 2493 if (jrecs > 0 || jbytes > 0) { 2494 printf("** %jd journal records in %jd bytes for %.2f%% utilization\n", 2495 jrecs, jbytes, ((float)jrecs / (float)(jbytes / JREC_SIZE)) * 100); 2496 printf("** Freed %jd inodes (%jd dirs) %jd blocks, and %jd frags.\n", 2497 freeinos, freedir, freeblocks, freefrags); 2498 } 2499 2500 return (0); 2501 } 2502 2503 static void 2504 initsuj(void) 2505 { 2506 int i; 2507 2508 for (i = 0; i < HASHSIZE; i++) 2509 LIST_INIT(&cghash[i]); 2510 lastcg = NULL; 2511 TAILQ_INIT(&allsegs); 2512 oldseq = 0; 2513 fs = NULL; 2514 sujino = 0; 2515 freefrags = 0; 2516 freeblocks = 0; 2517 freeinos = 0; 2518 freedir = 0; 2519 jbytes = 0; 2520 jrecs = 0; 2521 suj_jblocks = NULL; 2522 } 2523