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