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
|