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