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