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