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