xref: /netbsd-src/sbin/resize_ffs/resize_ffs.c (revision e89934bbf778a6d6d6894877c4da59d0c7835b0f)
1 /*	$NetBSD: resize_ffs.c,v 1.47 2016/08/24 07:44:05 dholland Exp $	*/
2 /* From sources sent on February 17, 2003 */
3 /*-
4  * As its sole author, I explicitly place this code in the public
5  *  domain.  Anyone may use it for any purpose (though I would
6  *  appreciate credit where it is due).
7  *
8  *					der Mouse
9  *
10  *			       mouse@rodents.montreal.qc.ca
11  *		     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B
12  */
13 /*
14  * resize_ffs:
15  *
16  * Resize a file system.  Is capable of both growing and shrinking.
17  *
18  * Usage: resize_ffs [-s newsize] [-y] file_system
19  *
20  * Example: resize_ffs -s 29574 /dev/rsd1e
21  *
22  * newsize is in DEV_BSIZE units (ie, disk sectors, usually 512 bytes
23  *  each).
24  *
25  * Note: this currently requires gcc to build, since it is written
26  *  depending on gcc-specific features, notably nested function
27  *  definitions (which in at least a few cases depend on the lexical
28  *  scoping gcc provides, so they can't be trivially moved outside).
29  *
30  * Many thanks go to John Kohl <jtk@NetBSD.org> for finding bugs: the
31  *  one responsible for the "realloccgblk: can't find blk in cyl"
32  *  problem and a more minor one which left fs_dsize wrong when
33  *  shrinking.  (These actually indicate bugs in fsck too - it should
34  *  have caught and fixed them.)
35  *
36  */
37 
38 #include <sys/cdefs.h>
39 __RCSID("$NetBSD: resize_ffs.c,v 1.47 2016/08/24 07:44:05 dholland Exp $");
40 
41 #include <sys/disk.h>
42 #include <sys/disklabel.h>
43 #include <sys/dkio.h>
44 #include <sys/ioctl.h>
45 #include <sys/stat.h>
46 #include <sys/mman.h>
47 #include <sys/param.h>		/* MAXFRAG */
48 #include <ufs/ffs/fs.h>
49 #include <ufs/ffs/ffs_extern.h>
50 #include <ufs/ufs/dir.h>
51 #include <ufs/ufs/dinode.h>
52 #include <ufs/ufs/ufs_bswap.h>	/* ufs_rw32 */
53 
54 #include <err.h>
55 #include <errno.h>
56 #include <fcntl.h>
57 #include <stdio.h>
58 #include <stdlib.h>
59 #include <strings.h>
60 #include <unistd.h>
61 
62 #include "progress.h"
63 
64 /* new size of file system, in sectors */
65 static int64_t newsize;
66 
67 /* fd open onto disk device or file */
68 static int fd;
69 
70 /* disk device or file path */
71 char *special;
72 
73 /* must we break up big I/O operations - see checksmallio() */
74 static int smallio;
75 
76 /* size of a cg, in bytes, rounded up to a frag boundary */
77 static int cgblksz;
78 
79 /* possible superblock localtions */
80 static int search[] = SBLOCKSEARCH;
81 /* location of the superblock */
82 static off_t where;
83 
84 /* Superblocks. */
85 static struct fs *oldsb;	/* before we started */
86 static struct fs *newsb;	/* copy to work with */
87 /* Buffer to hold the above.  Make sure it's aligned correctly. */
88 static char sbbuf[2 * SBLOCKSIZE]
89 	__attribute__((__aligned__(__alignof__(struct fs))));
90 
91 union dinode {
92 	struct ufs1_dinode dp1;
93 	struct ufs2_dinode dp2;
94 };
95 #define DIP(dp, field)							      \
96 	((is_ufs2) ?							      \
97 	    (dp)->dp2.field : (dp)->dp1.field)
98 
99 #define DIP_ASSIGN(dp, field, value)					      \
100 	do {								      \
101 		if (is_ufs2)						      \
102 			(dp)->dp2.field = (value);			      \
103 		else							      \
104 			(dp)->dp1.field = (value);			      \
105 	} while (0)
106 
107 /* a cg's worth of brand new squeaky-clean inodes */
108 static struct ufs1_dinode *zinodes1;
109 static struct ufs2_dinode *zinodes2;
110 
111 /* pointers to the in-core cgs, read off disk and possibly modified */
112 static struct cg **cgs;
113 
114 /* pointer to csum array - the stuff pointed to on-disk by fs_csaddr */
115 static struct csum *csums;
116 
117 /* per-cg flags, indexed by cg number */
118 static unsigned char *cgflags;
119 #define CGF_DIRTY   0x01	/* needs to be written to disk */
120 #define CGF_BLKMAPS 0x02	/* block bitmaps need rebuilding */
121 #define CGF_INOMAPS 0x04	/* inode bitmaps need rebuilding */
122 
123 /* when shrinking, these two arrays record how we want blocks to move.	 */
124 /*  if blkmove[i] is j, the frag that started out as frag #i should end	 */
125 /*  up as frag #j.  inomove[i]=j means, similarly, that the inode that	 */
126 /*  started out as inode i should end up as inode j.			 */
127 static unsigned int *blkmove;
128 static unsigned int *inomove;
129 
130 /* in-core copies of all inodes in the fs, indexed by inumber */
131 union dinode *inodes;
132 
133 void *ibuf;	/* ptr to fs block-sized buffer for reading/writing inodes */
134 
135 /* byteswapped inodes */
136 union dinode *sinodes;
137 
138 /* per-inode flags, indexed by inumber */
139 static unsigned char *iflags;
140 #define IF_DIRTY  0x01		/* needs to be written to disk */
141 #define IF_BDIRTY 0x02		/* like DIRTY, but is set on first inode in a
142 				 * block of inodes, and applies to the whole
143 				 * block. */
144 
145 /* resize_ffs works directly on dinodes, adapt blksize() */
146 #define dblksize(fs, dip, lbn, filesize) \
147 	(((lbn) >= UFS_NDADDR || (uint64_t)(filesize) >= ffs_lblktosize(fs, (lbn) + 1)) \
148 	    ? (fs)->fs_bsize						       \
149 	    : (ffs_fragroundup(fs, ffs_blkoff(fs, (filesize)))))
150 
151 
152 /*
153  * Number of disk sectors per block/fragment
154  */
155 #define NSPB(fs)	(FFS_FSBTODB((fs),1) << (fs)->fs_fragshift)
156 #define NSPF(fs)	(FFS_FSBTODB((fs),1))
157 
158 /* global flags */
159 int is_ufs2 = 0;
160 int needswap = 0;
161 int verbose = 0;
162 int progress = 0;
163 
164 static void usage(void) __dead;
165 
166 /*
167  * See if we need to break up large I/O operations.  This should never
168  *  be needed, but under at least one <version,platform> combination,
169  *  large enough disk transfers to the raw device hang.  So if we're
170  *  talking to a character special device, play it safe; in this case,
171  *  readat() and writeat() break everything up into pieces no larger
172  *  than 8K, doing multiple syscalls for larger operations.
173  */
174 static void
175 checksmallio(void)
176 {
177 	struct stat stb;
178 
179 	fstat(fd, &stb);
180 	smallio = ((stb.st_mode & S_IFMT) == S_IFCHR);
181 }
182 
183 static int
184 isplainfile(void)
185 {
186 	struct stat stb;
187 
188 	fstat(fd, &stb);
189 	return S_ISREG(stb.st_mode);
190 }
191 /*
192  * Read size bytes starting at blkno into buf.  blkno is in DEV_BSIZE
193  *  units, ie, after FFS_FSBTODB(); size is in bytes.
194  */
195 static void
196 readat(off_t blkno, void *buf, int size)
197 {
198 	/* Seek to the correct place. */
199 	if (lseek(fd, blkno * DEV_BSIZE, L_SET) < 0)
200 		err(EXIT_FAILURE, "lseek failed");
201 
202 	/* See if we have to break up the transfer... */
203 	if (smallio) {
204 		char *bp;	/* pointer into buf */
205 		int left;	/* bytes left to go */
206 		int n;		/* number to do this time around */
207 		int rv;		/* syscall return value */
208 		bp = buf;
209 		left = size;
210 		while (left > 0) {
211 			n = (left > 8192) ? 8192 : left;
212 			rv = read(fd, bp, n);
213 			if (rv < 0)
214 				err(EXIT_FAILURE, "read failed");
215 			if (rv != n)
216 				errx(EXIT_FAILURE,
217 				    "read: wanted %d, got %d", n, rv);
218 			bp += n;
219 			left -= n;
220 		}
221 	} else {
222 		int rv;
223 		rv = read(fd, buf, size);
224 		if (rv < 0)
225 			err(EXIT_FAILURE, "read failed");
226 		if (rv != size)
227 			errx(EXIT_FAILURE, "read: wanted %d, got %d",
228 			    size, rv);
229 	}
230 }
231 /*
232  * Write size bytes from buf starting at blkno.  blkno is in DEV_BSIZE
233  *  units, ie, after FFS_FSBTODB(); size is in bytes.
234  */
235 static void
236 writeat(off_t blkno, const void *buf, int size)
237 {
238 	/* Seek to the correct place. */
239 	if (lseek(fd, blkno * DEV_BSIZE, L_SET) < 0)
240 		err(EXIT_FAILURE, "lseek failed");
241 	/* See if we have to break up the transfer... */
242 	if (smallio) {
243 		const char *bp;	/* pointer into buf */
244 		int left;	/* bytes left to go */
245 		int n;		/* number to do this time around */
246 		int rv;		/* syscall return value */
247 		bp = buf;
248 		left = size;
249 		while (left > 0) {
250 			n = (left > 8192) ? 8192 : left;
251 			rv = write(fd, bp, n);
252 			if (rv < 0)
253 				err(EXIT_FAILURE, "write failed");
254 			if (rv != n)
255 				errx(EXIT_FAILURE,
256 				    "write: wanted %d, got %d", n, rv);
257 			bp += n;
258 			left -= n;
259 		}
260 	} else {
261 		int rv;
262 		rv = write(fd, buf, size);
263 		if (rv < 0)
264 			err(EXIT_FAILURE, "write failed");
265 		if (rv != size)
266 			errx(EXIT_FAILURE,
267 			    "write: wanted %d, got %d", size, rv);
268 	}
269 }
270 /*
271  * Never-fail versions of malloc() and realloc(), and an allocation
272  *  routine (which also never fails) for allocating memory that will
273  *  never be freed until exit.
274  */
275 
276 /*
277  * Never-fail malloc.
278  */
279 static void *
280 nfmalloc(size_t nb, const char *tag)
281 {
282 	void *rv;
283 
284 	rv = malloc(nb);
285 	if (rv)
286 		return (rv);
287 	err(EXIT_FAILURE, "Can't allocate %lu bytes for %s",
288 	    (unsigned long int) nb, tag);
289 }
290 /*
291  * Never-fail realloc.
292  */
293 static void *
294 nfrealloc(void *blk, size_t nb, const char *tag)
295 {
296 	void *rv;
297 
298 	rv = realloc(blk, nb);
299 	if (rv)
300 		return (rv);
301 	err(EXIT_FAILURE, "Can't re-allocate %lu bytes for %s",
302 	    (unsigned long int) nb, tag);
303 }
304 /*
305  * Allocate memory that will never be freed or reallocated.  Arguably
306  *  this routine should handle small allocations by chopping up pages,
307  *  but that's not worth the bother; it's not called more than a
308  *  handful of times per run, and if the allocations are that small the
309  *  waste in giving each one its own page is ignorable.
310  */
311 static void *
312 alloconce(size_t nb, const char *tag)
313 {
314 	void *rv;
315 
316 	rv = mmap(0, nb, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0);
317 	if (rv != MAP_FAILED)
318 		return (rv);
319 	err(EXIT_FAILURE, "Can't map %lu bytes for %s",
320 	    (unsigned long int) nb, tag);
321 }
322 /*
323  * Load the cgs and csums off disk.  Also allocates the space to load
324  *  them into and initializes the per-cg flags.
325  */
326 static void
327 loadcgs(void)
328 {
329 	int cg;
330 	char *cgp;
331 
332 	cgblksz = roundup(oldsb->fs_cgsize, oldsb->fs_fsize);
333 	cgs = nfmalloc(oldsb->fs_ncg * sizeof(*cgs), "cg pointers");
334 	cgp = alloconce(oldsb->fs_ncg * cgblksz, "cgs");
335 	cgflags = nfmalloc(oldsb->fs_ncg, "cg flags");
336 	csums = nfmalloc(oldsb->fs_cssize, "cg summary");
337 	for (cg = 0; cg < oldsb->fs_ncg; cg++) {
338 		cgs[cg] = (struct cg *) cgp;
339 		readat(FFS_FSBTODB(oldsb, cgtod(oldsb, cg)), cgp, cgblksz);
340 		if (needswap)
341 			ffs_cg_swap(cgs[cg],cgs[cg],oldsb);
342 		cgflags[cg] = 0;
343 		cgp += cgblksz;
344 	}
345 	readat(FFS_FSBTODB(oldsb, oldsb->fs_csaddr), csums, oldsb->fs_cssize);
346 	if (needswap)
347 		ffs_csum_swap(csums,csums,oldsb->fs_cssize);
348 }
349 /*
350  * Set n bits, starting with bit #base, in the bitmap pointed to by
351  *  bitvec (which is assumed to be large enough to include bits base
352  *  through base+n-1).
353  */
354 static void
355 set_bits(unsigned char *bitvec, unsigned int base, unsigned int n)
356 {
357 	if (n < 1)
358 		return;		/* nothing to do */
359 	if (base & 7) {		/* partial byte at beginning */
360 		if (n <= 8 - (base & 7)) {	/* entirely within one byte */
361 			bitvec[base >> 3] |= (~((~0U) << n)) << (base & 7);
362 			return;
363 		}
364 		bitvec[base >> 3] |= (~0U) << (base & 7);
365 		n -= 8 - (base & 7);
366 		base = (base & ~7) + 8;
367 	}
368 	if (n >= 8) {		/* do full bytes */
369 		memset(bitvec + (base >> 3), 0xff, n >> 3);
370 		base += n & ~7;
371 		n &= 7;
372 	}
373 	if (n) {		/* partial byte at end */
374 		bitvec[base >> 3] |= ~((~0U) << n);
375 	}
376 }
377 /*
378  * Clear n bits, starting with bit #base, in the bitmap pointed to by
379  *  bitvec (which is assumed to be large enough to include bits base
380  *  through base+n-1).  Code parallels set_bits().
381  */
382 static void
383 clr_bits(unsigned char *bitvec, int base, int n)
384 {
385 	if (n < 1)
386 		return;
387 	if (base & 7) {
388 		if (n <= 8 - (base & 7)) {
389 			bitvec[base >> 3] &= ~((~((~0U) << n)) << (base & 7));
390 			return;
391 		}
392 		bitvec[base >> 3] &= ~((~0U) << (base & 7));
393 		n -= 8 - (base & 7);
394 		base = (base & ~7) + 8;
395 	}
396 	if (n >= 8) {
397 		memset(bitvec + (base >> 3), 0, n >> 3);
398 		base += n & ~7;
399 		n &= 7;
400 	}
401 	if (n) {
402 		bitvec[base >> 3] &= (~0U) << n;
403 	}
404 }
405 /*
406  * Test whether bit #bit is set in the bitmap pointed to by bitvec.
407  */
408 static int
409 bit_is_set(unsigned char *bitvec, int bit)
410 {
411 	return (bitvec[bit >> 3] & (1 << (bit & 7)));
412 }
413 /*
414  * Test whether bit #bit is clear in the bitmap pointed to by bitvec.
415  */
416 static int
417 bit_is_clr(unsigned char *bitvec, int bit)
418 {
419 	return (!bit_is_set(bitvec, bit));
420 }
421 /*
422  * Test whether a whole block of bits is set in a bitmap.  This is
423  *  designed for testing (aligned) disk blocks in a bit-per-frag
424  *  bitmap; it has assumptions wired into it based on that, essentially
425  *  that the entire block fits into a single byte.  This returns true
426  *  iff _all_ the bits are set; it is not just the complement of
427  *  blk_is_clr on the same arguments (unless blkfrags==1).
428  */
429 static int
430 blk_is_set(unsigned char *bitvec, int blkbase, int blkfrags)
431 {
432 	unsigned int mask;
433 
434 	mask = (~((~0U) << blkfrags)) << (blkbase & 7);
435 	return ((bitvec[blkbase >> 3] & mask) == mask);
436 }
437 /*
438  * Test whether a whole block of bits is clear in a bitmap.  See
439  *  blk_is_set (above) for assumptions.  This returns true iff _all_
440  *  the bits are clear; it is not just the complement of blk_is_set on
441  *  the same arguments (unless blkfrags==1).
442  */
443 static int
444 blk_is_clr(unsigned char *bitvec, int blkbase, int blkfrags)
445 {
446 	unsigned int mask;
447 
448 	mask = (~((~0U) << blkfrags)) << (blkbase & 7);
449 	return ((bitvec[blkbase >> 3] & mask) == 0);
450 }
451 /*
452  * Initialize a new cg.  Called when growing.  Assumes memory has been
453  *  allocated but not otherwise set up.  This code sets the fields of
454  *  the cg, initializes the bitmaps (and cluster summaries, if
455  *  applicable), updates both per-cylinder summary info and the global
456  *  summary info in newsb; it also writes out new inodes for the cg.
457  *
458  * This code knows it can never be called for cg 0, which makes it a
459  *  bit simpler than it would otherwise be.
460  */
461 static void
462 initcg(int cgn)
463 {
464 	struct cg *cg;		/* The in-core cg, of course */
465 	int base;		/* Disk address of cg base */
466 	int dlow;		/* Size of pre-cg data area */
467 	int dhigh;		/* Offset of post-inode data area, from base */
468 	int dmax;		/* Offset of end of post-inode data area */
469 	int i;			/* Generic loop index */
470 	int n;			/* Generic count */
471 	int start;		/* start of cg maps */
472 
473 	cg = cgs[cgn];
474 	/* Place the data areas */
475 	base = cgbase(newsb, cgn);
476 	dlow = cgsblock(newsb, cgn) - base;
477 	dhigh = cgdmin(newsb, cgn) - base;
478 	dmax = newsb->fs_size - base;
479 	if (dmax > newsb->fs_fpg)
480 		dmax = newsb->fs_fpg;
481 	start = &cg->cg_space[0] - (unsigned char *) cg;
482 	/*
483          * Clear out the cg - assumes all-0-bytes is the correct way
484          * to initialize fields we don't otherwise touch, which is
485          * perhaps not the right thing to do, but it's what fsck and
486          * mkfs do.
487          */
488 	memset(cg, 0, newsb->fs_cgsize);
489 	if (newsb->fs_old_flags & FS_FLAGS_UPDATED)
490 		cg->cg_time = newsb->fs_time;
491 	cg->cg_magic = CG_MAGIC;
492 	cg->cg_cgx = cgn;
493 	cg->cg_niblk = newsb->fs_ipg;
494 	cg->cg_ndblk = dmax;
495 
496 	if (is_ufs2) {
497 		cg->cg_time = newsb->fs_time;
498 		cg->cg_initediblk = newsb->fs_ipg < 2 * FFS_INOPB(newsb) ?
499 		    newsb->fs_ipg : 2 * FFS_INOPB(newsb);
500 		cg->cg_iusedoff = start;
501 	} else {
502 		cg->cg_old_time = newsb->fs_time;
503 		cg->cg_old_niblk = cg->cg_niblk;
504 		cg->cg_niblk = 0;
505 		cg->cg_initediblk = 0;
506 
507 
508 		cg->cg_old_ncyl = newsb->fs_old_cpg;
509 		/* Update the cg_old_ncyl value for the last cylinder. */
510 		if (cgn == newsb->fs_ncg - 1) {
511 			if ((newsb->fs_old_flags & FS_FLAGS_UPDATED) == 0)
512 				cg->cg_old_ncyl = newsb->fs_old_ncyl %
513 				    newsb->fs_old_cpg;
514 		}
515 
516 		/* Set up the bitmap pointers.  We have to be careful
517 		 * to lay out the cg _exactly_ the way mkfs and fsck
518 		 * do it, since fsck compares the _entire_ cg against
519 		 * a recomputed cg, and whines if there is any
520 		 * mismatch, including the bitmap offsets. */
521 		/* XXX update this comment when fsck is fixed */
522 		cg->cg_old_btotoff = start;
523 		cg->cg_old_boff = cg->cg_old_btotoff
524 		    + (newsb->fs_old_cpg * sizeof(int32_t));
525 		cg->cg_iusedoff = cg->cg_old_boff +
526 		    (newsb->fs_old_cpg * newsb->fs_old_nrpos * sizeof(int16_t));
527 	}
528 	cg->cg_freeoff = cg->cg_iusedoff + howmany(newsb->fs_ipg, NBBY);
529 	if (newsb->fs_contigsumsize > 0) {
530 		cg->cg_nclusterblks = cg->cg_ndblk / newsb->fs_frag;
531 		cg->cg_clustersumoff = cg->cg_freeoff +
532 		    howmany(newsb->fs_fpg, NBBY) - sizeof(int32_t);
533 		cg->cg_clustersumoff =
534 		    roundup(cg->cg_clustersumoff, sizeof(int32_t));
535 		cg->cg_clusteroff = cg->cg_clustersumoff +
536 		    ((newsb->fs_contigsumsize + 1) * sizeof(int32_t));
537 		cg->cg_nextfreeoff = cg->cg_clusteroff +
538 		    howmany(ffs_fragstoblks(newsb,newsb->fs_fpg), NBBY);
539 		n = dlow / newsb->fs_frag;
540 		if (n > 0) {
541 			set_bits(cg_clustersfree(cg, 0), 0, n);
542 			cg_clustersum(cg, 0)[(n > newsb->fs_contigsumsize) ?
543 			    newsb->fs_contigsumsize : n]++;
544 		}
545 	} else {
546 		cg->cg_nextfreeoff = cg->cg_freeoff +
547 		    howmany(newsb->fs_fpg, NBBY);
548 	}
549 	/* Mark the data areas as free; everything else is marked busy by the
550 	 * memset() up at the top. */
551 	set_bits(cg_blksfree(cg, 0), 0, dlow);
552 	set_bits(cg_blksfree(cg, 0), dhigh, dmax - dhigh);
553 	/* Initialize summary info */
554 	cg->cg_cs.cs_ndir = 0;
555 	cg->cg_cs.cs_nifree = newsb->fs_ipg;
556 	cg->cg_cs.cs_nbfree = dlow / newsb->fs_frag;
557 	cg->cg_cs.cs_nffree = 0;
558 
559 	/* This is the simplest way of doing this; we perhaps could
560 	 * compute the correct cg_blktot()[] and cg_blks()[] values
561 	 * other ways, but it would be complicated and hardly seems
562 	 * worth the effort.  (The reason there isn't
563 	 * frag-at-beginning and frag-at-end code here, like the code
564 	 * below for the post-inode data area, is that the pre-sb data
565 	 * area always starts at 0, and thus is block-aligned, and
566 	 * always ends at the sb, which is block-aligned.) */
567 	if ((newsb->fs_old_flags & FS_FLAGS_UPDATED) == 0)
568 		for (i = 0; i < dlow; i += newsb->fs_frag) {
569 			old_cg_blktot(cg, 0)[old_cbtocylno(newsb, i)]++;
570 			old_cg_blks(newsb, cg,
571 			    old_cbtocylno(newsb, i),
572 			    0)[old_cbtorpos(newsb, i)]++;
573 		}
574 
575 	/* Deal with a partial block at the beginning of the post-inode area.
576 	 * I'm not convinced this can happen - I think the inodes are always
577 	 * block-aligned and always an integral number of blocks - but it's
578 	 * cheap to do the right thing just in case. */
579 	if (dhigh % newsb->fs_frag) {
580 		n = newsb->fs_frag - (dhigh % newsb->fs_frag);
581 		cg->cg_frsum[n]++;
582 		cg->cg_cs.cs_nffree += n;
583 		dhigh += n;
584 	}
585 	n = (dmax - dhigh) / newsb->fs_frag;
586 	/* We have n full-size blocks in the post-inode data area. */
587 	if (n > 0) {
588 		cg->cg_cs.cs_nbfree += n;
589 		if (newsb->fs_contigsumsize > 0) {
590 			i = dhigh / newsb->fs_frag;
591 			set_bits(cg_clustersfree(cg, 0), i, n);
592 			cg_clustersum(cg, 0)[(n > newsb->fs_contigsumsize) ?
593 			    newsb->fs_contigsumsize : n]++;
594 		}
595 		if (is_ufs2 == 0)
596 			for (i = n; i > 0; i--) {
597 				old_cg_blktot(cg, 0)[old_cbtocylno(newsb,
598 					    dhigh)]++;
599 				old_cg_blks(newsb, cg,
600 				    old_cbtocylno(newsb, dhigh),
601 				    0)[old_cbtorpos(newsb,
602 					    dhigh)]++;
603 				dhigh += newsb->fs_frag;
604 			}
605 	}
606 	if (is_ufs2 == 0) {
607 		/* Deal with any leftover frag at the end of the cg. */
608 		i = dmax - dhigh;
609 		if (i) {
610 			cg->cg_frsum[i]++;
611 			cg->cg_cs.cs_nffree += i;
612 		}
613 	}
614 	/* Update the csum info. */
615 	csums[cgn] = cg->cg_cs;
616 	newsb->fs_cstotal.cs_nffree += cg->cg_cs.cs_nffree;
617 	newsb->fs_cstotal.cs_nbfree += cg->cg_cs.cs_nbfree;
618 	newsb->fs_cstotal.cs_nifree += cg->cg_cs.cs_nifree;
619 	if (is_ufs2) {
620 		/* Write out the cleared inodes. */
621 		writeat(FFS_FSBTODB(newsb, cgimin(newsb, cgn)), zinodes2,
622 		    cg->cg_initediblk * sizeof(*zinodes2));
623 	} else {
624 		/* Write out the cleared inodes. */
625 		writeat(FFS_FSBTODB(newsb, cgimin(newsb, cgn)), zinodes1,
626 		    newsb->fs_ipg * sizeof(*zinodes1));
627 	}
628 	/* Dirty the cg. */
629 	cgflags[cgn] |= CGF_DIRTY;
630 }
631 /*
632  * Find free space, at least nfrags consecutive frags of it.  Pays no
633  *  attention to block boundaries, but refuses to straddle cg
634  *  boundaries, even if the disk blocks involved are in fact
635  *  consecutive.  Return value is the frag number of the first frag of
636  *  the block, or -1 if no space was found.  Uses newsb for sb values,
637  *  and assumes the cgs[] structures correctly describe the area to be
638  *  searched.
639  *
640  * XXX is there a bug lurking in the ignoring of block boundaries by
641  *  the routine used by fragmove() in evict_data()?  Can an end-of-file
642  *  frag legally straddle a block boundary?  If not, this should be
643  *  cloned and fixed to stop at block boundaries for that use.  The
644  *  current one may still be needed for csum info motion, in case that
645  *  takes up more than a whole block (is the csum info allowed to begin
646  *  partway through a block and continue into the following block?).
647  *
648  * If we wrap off the end of the file system back to the beginning, we
649  *  can end up searching the end of the file system twice.  I ignore
650  *  this inefficiency, since if that happens we're going to croak with
651  *  a no-space error anyway, so it happens at most once.
652  */
653 static int
654 find_freespace(unsigned int nfrags)
655 {
656 	static int hand = 0;	/* hand rotates through all frags in the fs */
657 	int cgsize;		/* size of the cg hand currently points into */
658 	int cgn;		/* number of cg hand currently points into */
659 	int fwc;		/* frag-within-cg number of frag hand points
660 				 * to */
661 	unsigned int run;	/* length of run of free frags seen so far */
662 	int secondpass;		/* have we wrapped from end of fs to
663 				 * beginning? */
664 	unsigned char *bits;	/* cg_blksfree()[] for cg hand points into */
665 
666 	cgn = dtog(newsb, hand);
667 	fwc = dtogd(newsb, hand);
668 	secondpass = (hand == 0);
669 	run = 0;
670 	bits = cg_blksfree(cgs[cgn], 0);
671 	cgsize = cgs[cgn]->cg_ndblk;
672 	while (1) {
673 		if (bit_is_set(bits, fwc)) {
674 			run++;
675 			if (run >= nfrags)
676 				return (hand + 1 - run);
677 		} else {
678 			run = 0;
679 		}
680 		hand++;
681 		fwc++;
682 		if (fwc >= cgsize) {
683 			fwc = 0;
684 			cgn++;
685 			if (cgn >= newsb->fs_ncg) {
686 				hand = 0;
687 				if (secondpass)
688 					return (-1);
689 				secondpass = 1;
690 				cgn = 0;
691 			}
692 			bits = cg_blksfree(cgs[cgn], 0);
693 			cgsize = cgs[cgn]->cg_ndblk;
694 			run = 0;
695 		}
696 	}
697 }
698 /*
699  * Find a free block of disk space.  Finds an entire block of frags,
700  *  all of which are free.  Return value is the frag number of the
701  *  first frag of the block, or -1 if no space was found.  Uses newsb
702  *  for sb values, and assumes the cgs[] structures correctly describe
703  *  the area to be searched.
704  *
705  * See find_freespace(), above, for remarks about hand wrapping around.
706  */
707 static int
708 find_freeblock(void)
709 {
710 	static int hand = 0;	/* hand rotates through all frags in fs */
711 	int cgn;		/* cg number of cg hand points into */
712 	int fwc;		/* frag-within-cg number of frag hand points
713 				 * to */
714 	int cgsize;		/* size of cg hand points into */
715 	int secondpass;		/* have we wrapped from end to beginning? */
716 	unsigned char *bits;	/* cg_blksfree()[] for cg hand points into */
717 
718 	cgn = dtog(newsb, hand);
719 	fwc = dtogd(newsb, hand);
720 	secondpass = (hand == 0);
721 	bits = cg_blksfree(cgs[cgn], 0);
722 	cgsize = ffs_blknum(newsb, cgs[cgn]->cg_ndblk);
723 	while (1) {
724 		if (blk_is_set(bits, fwc, newsb->fs_frag))
725 			return (hand);
726 		fwc += newsb->fs_frag;
727 		hand += newsb->fs_frag;
728 		if (fwc >= cgsize) {
729 			fwc = 0;
730 			cgn++;
731 			if (cgn >= newsb->fs_ncg) {
732 				hand = 0;
733 				if (secondpass)
734 					return (-1);
735 				secondpass = 1;
736 				cgn = 0;
737 			}
738 			bits = cg_blksfree(cgs[cgn], 0);
739 			cgsize = ffs_blknum(newsb, cgs[cgn]->cg_ndblk);
740 		}
741 	}
742 }
743 /*
744  * Find a free inode, returning its inumber or -1 if none was found.
745  *  Uses newsb for sb values, and assumes the cgs[] structures
746  *  correctly describe the area to be searched.
747  *
748  * See find_freespace(), above, for remarks about hand wrapping around.
749  */
750 static int
751 find_freeinode(void)
752 {
753 	static int hand = 0;	/* hand rotates through all inodes in fs */
754 	int cgn;		/* cg number of cg hand points into */
755 	int iwc;		/* inode-within-cg number of inode hand points
756 				 * to */
757 	int secondpass;		/* have we wrapped from end to beginning? */
758 	unsigned char *bits;	/* cg_inosused()[] for cg hand points into */
759 
760 	cgn = hand / newsb->fs_ipg;
761 	iwc = hand % newsb->fs_ipg;
762 	secondpass = (hand == 0);
763 	bits = cg_inosused(cgs[cgn], 0);
764 	while (1) {
765 		if (bit_is_clr(bits, iwc))
766 			return (hand);
767 		hand++;
768 		iwc++;
769 		if (iwc >= newsb->fs_ipg) {
770 			iwc = 0;
771 			cgn++;
772 			if (cgn >= newsb->fs_ncg) {
773 				hand = 0;
774 				if (secondpass)
775 					return (-1);
776 				secondpass = 1;
777 				cgn = 0;
778 			}
779 			bits = cg_inosused(cgs[cgn], 0);
780 		}
781 	}
782 }
783 /*
784  * Mark a frag as free.  Sets the frag's bit in the cg_blksfree bitmap
785  *  for the appropriate cg, and marks the cg as dirty.
786  */
787 static void
788 free_frag(int fno)
789 {
790 	int cgn;
791 
792 	cgn = dtog(newsb, fno);
793 	set_bits(cg_blksfree(cgs[cgn], 0), dtogd(newsb, fno), 1);
794 	cgflags[cgn] |= CGF_DIRTY | CGF_BLKMAPS;
795 }
796 /*
797  * Allocate a frag.  Clears the frag's bit in the cg_blksfree bitmap
798  *  for the appropriate cg, and marks the cg as dirty.
799  */
800 static void
801 alloc_frag(int fno)
802 {
803 	int cgn;
804 
805 	cgn = dtog(newsb, fno);
806 	clr_bits(cg_blksfree(cgs[cgn], 0), dtogd(newsb, fno), 1);
807 	cgflags[cgn] |= CGF_DIRTY | CGF_BLKMAPS;
808 }
809 /*
810  * Fix up the csum array.  If shrinking, this involves freeing zero or
811  *  more frags; if growing, it involves allocating them, or if the
812  *  frags being grown into aren't free, finding space elsewhere for the
813  *  csum info.  (If the number of occupied frags doesn't change,
814  *  nothing happens here.)
815  */
816 static void
817 csum_fixup(void)
818 {
819 	int nold;		/* # frags in old csum info */
820 	int ntot;		/* # frags in new csum info */
821 	int nnew;		/* ntot-nold */
822 	int newloc;		/* new location for csum info, if necessary */
823 	int i;			/* generic loop index */
824 	int j;			/* generic loop index */
825 	int f;			/* "from" frag number, if moving */
826 	int t;			/* "to" frag number, if moving */
827 	int cgn;		/* cg number, used when shrinking */
828 
829 	ntot = howmany(newsb->fs_cssize, newsb->fs_fsize);
830 	nold = howmany(oldsb->fs_cssize, newsb->fs_fsize);
831 	nnew = ntot - nold;
832 	/* First, if there's no change in frag counts, it's easy. */
833 	if (nnew == 0)
834 		return;
835 	/* Next, if we're shrinking, it's almost as easy.  Just free up any
836 	 * frags in the old area we no longer need. */
837 	if (nnew < 0) {
838 		for ((i = newsb->fs_csaddr + ntot - 1), (j = nnew);
839 		    j < 0;
840 		    i--, j++) {
841 			free_frag(i);
842 		}
843 		return;
844 	}
845 	/* We must be growing.  Check to see that the new csum area fits
846 	 * within the file system.  I think this can never happen, since for
847 	 * the csum area to grow, we must be adding at least one cg, so the
848 	 * old csum area can't be this close to the end of the new file system.
849 	 * But it's a cheap check. */
850 	/* XXX what if csum info is at end of cg and grows into next cg, what
851 	 * if it spills over onto the next cg's backup superblock?  Can this
852 	 * happen? */
853 	if (newsb->fs_csaddr + ntot <= newsb->fs_size) {
854 		/* Okay, it fits - now,  see if the space we want is free. */
855 		for ((i = newsb->fs_csaddr + nold), (j = nnew);
856 		    j > 0;
857 		    i++, j--) {
858 			cgn = dtog(newsb, i);
859 			if (bit_is_clr(cg_blksfree(cgs[cgn], 0),
860 				dtogd(newsb, i)))
861 				break;
862 		}
863 		if (j <= 0) {
864 			/* Win win - all the frags we want are free. Allocate
865 			 * 'em and we're all done.  */
866 			for ((i = newsb->fs_csaddr + ntot - nnew),
867 				 (j = nnew); j > 0; i++, j--) {
868 				alloc_frag(i);
869 			}
870 			return;
871 		}
872 	}
873 	/* We have to move the csum info, sigh.  Look for new space, free old
874 	 * space, and allocate new.  Update fs_csaddr.  We don't copy anything
875 	 * on disk at this point; the csum info will be written to the
876 	 * then-current fs_csaddr as part of the final flush. */
877 	newloc = find_freespace(ntot);
878 	if (newloc < 0)
879 		errx(EXIT_FAILURE, "Sorry, no space available for new csums");
880 	for (i = 0, f = newsb->fs_csaddr, t = newloc; i < ntot; i++, f++, t++) {
881 		if (i < nold) {
882 			free_frag(f);
883 		}
884 		alloc_frag(t);
885 	}
886 	newsb->fs_csaddr = newloc;
887 }
888 /*
889  * Recompute newsb->fs_dsize.  Just scans all cgs, adding the number of
890  *  data blocks in that cg to the total.
891  */
892 static void
893 recompute_fs_dsize(void)
894 {
895 	int i;
896 
897 	newsb->fs_dsize = 0;
898 	for (i = 0; i < newsb->fs_ncg; i++) {
899 		int dlow;	/* size of before-sb data area */
900 		int dhigh;	/* offset of post-inode data area */
901 		int dmax;	/* total size of cg */
902 		int base;	/* base of cg, since cgsblock() etc add it in */
903 		base = cgbase(newsb, i);
904 		dlow = cgsblock(newsb, i) - base;
905 		dhigh = cgdmin(newsb, i) - base;
906 		dmax = newsb->fs_size - base;
907 		if (dmax > newsb->fs_fpg)
908 			dmax = newsb->fs_fpg;
909 		newsb->fs_dsize += dlow + dmax - dhigh;
910 	}
911 	/* Space in cg 0 before cgsblock is boot area, not free space! */
912 	newsb->fs_dsize -= cgsblock(newsb, 0) - cgbase(newsb, 0);
913 	/* And of course the csum info takes up space. */
914 	newsb->fs_dsize -= howmany(newsb->fs_cssize, newsb->fs_fsize);
915 }
916 /*
917  * Return the current time.  We call this and assign, rather than
918  *  calling time() directly, as insulation against OSes where fs_time
919  *  is not a time_t.
920  */
921 static time_t
922 timestamp(void)
923 {
924 	time_t t;
925 
926 	time(&t);
927 	return (t);
928 }
929 
930 /*
931  * Calculate new filesystem geometry
932  *  return 0 if geometry actually changed
933  */
934 static int
935 makegeometry(int chatter)
936 {
937 
938 	/* Update the size. */
939 	newsb->fs_size = FFS_DBTOFSB(newsb, newsize);
940 	if (is_ufs2)
941 		newsb->fs_ncg = howmany(newsb->fs_size, newsb->fs_fpg);
942 	else {
943 		/* Update fs_old_ncyl and fs_ncg. */
944 		newsb->fs_old_ncyl = howmany(newsb->fs_size * NSPF(newsb),
945 		    newsb->fs_old_spc);
946 		newsb->fs_ncg = howmany(newsb->fs_old_ncyl, newsb->fs_old_cpg);
947 	}
948 
949 	/* Does the last cg end before the end of its inode area? There is no
950 	 * reason why this couldn't be handled, but it would complicate a lot
951 	 * of code (in all file system code - fsck, kernel, etc) because of the
952 	 * potential partial inode area, and the gain in space would be
953 	 * minimal, at most the pre-sb data area. */
954 	if (cgdmin(newsb, newsb->fs_ncg - 1) > newsb->fs_size) {
955 		newsb->fs_ncg--;
956 		if (is_ufs2)
957 			newsb->fs_size = newsb->fs_ncg * newsb->fs_fpg;
958 		else {
959 			newsb->fs_old_ncyl = newsb->fs_ncg * newsb->fs_old_cpg;
960 			newsb->fs_size = (newsb->fs_old_ncyl *
961 				newsb->fs_old_spc) / NSPF(newsb);
962 		}
963 		if (chatter || verbose) {
964 			printf("Warning: last cylinder group is too small;\n");
965 			printf("    dropping it.  New size = %lu.\n",
966 			(unsigned long int) FFS_FSBTODB(newsb, newsb->fs_size));
967 		}
968 	}
969 
970 	/* Did we actually not grow?  (This can happen if newsize is less than
971 	 * a frag larger than the old size - unlikely, but no excuse to
972 	 * misbehave if it happens.) */
973 	if (newsb->fs_size == oldsb->fs_size)
974 		return 1;
975 
976 	return 0;
977 }
978 
979 
980 /*
981  * Grow the file system.
982  */
983 static void
984 grow(void)
985 {
986 	int i;
987 
988 	if (makegeometry(1)) {
989 		printf("New fs size %"PRIu64" = old fs size %"PRIu64
990 		    ", not growing.\n", newsb->fs_size, oldsb->fs_size);
991 		return;
992 	}
993 
994 	if (verbose) {
995 		printf("Growing fs from %"PRIu64" blocks to %"PRIu64
996 		    " blocks.\n", oldsb->fs_size, newsb->fs_size);
997 	}
998 
999 	/* Update the timestamp. */
1000 	newsb->fs_time = timestamp();
1001 	/* Allocate and clear the new-inode area, in case we add any cgs. */
1002 	if (is_ufs2) {
1003 		zinodes2 = alloconce(newsb->fs_ipg * sizeof(*zinodes2),
1004 			"zeroed inodes");
1005 		memset(zinodes2, 0, newsb->fs_ipg * sizeof(*zinodes2));
1006 	} else {
1007 		zinodes1 = alloconce(newsb->fs_ipg * sizeof(*zinodes1),
1008 			"zeroed inodes");
1009 		memset(zinodes1, 0, newsb->fs_ipg * sizeof(*zinodes1));
1010 	}
1011 
1012 	/* Check that the new last sector (frag, actually) is writable.  Since
1013 	 * it's at least one frag larger than it used to be, we know we aren't
1014 	 * overwriting anything important by this.  (The choice of sbbuf as
1015 	 * what to write is irrelevant; it's just something handy that's known
1016 	 * to be at least one frag in size.) */
1017 	writeat(FFS_FSBTODB(newsb,newsb->fs_size - 1), &sbbuf, newsb->fs_fsize);
1018 
1019 	/* Find out how big the csum area is, and realloc csums if bigger. */
1020 	newsb->fs_cssize = ffs_fragroundup(newsb,
1021 	    newsb->fs_ncg * sizeof(struct csum));
1022 	if (newsb->fs_cssize > oldsb->fs_cssize)
1023 		csums = nfrealloc(csums, newsb->fs_cssize, "new cg summary");
1024 	/* If we're adding any cgs, realloc structures and set up the new
1025 	   cgs. */
1026 	if (newsb->fs_ncg > oldsb->fs_ncg) {
1027 		char *cgp;
1028 		cgs = nfrealloc(cgs, newsb->fs_ncg * sizeof(*cgs),
1029                                 "cg pointers");
1030 		cgflags = nfrealloc(cgflags, newsb->fs_ncg, "cg flags");
1031 		memset(cgflags + oldsb->fs_ncg, 0,
1032 		    newsb->fs_ncg - oldsb->fs_ncg);
1033 		cgp = alloconce((newsb->fs_ncg - oldsb->fs_ncg) * cgblksz,
1034                                 "cgs");
1035 		for (i = oldsb->fs_ncg; i < newsb->fs_ncg; i++) {
1036 			cgs[i] = (struct cg *) cgp;
1037 			progress_bar(special, "grow cg",
1038 			    i - oldsb->fs_ncg, newsb->fs_ncg - oldsb->fs_ncg);
1039 			initcg(i);
1040 			cgp += cgblksz;
1041 		}
1042 		cgs[oldsb->fs_ncg - 1]->cg_old_ncyl = oldsb->fs_old_cpg;
1043 		cgflags[oldsb->fs_ncg - 1] |= CGF_DIRTY;
1044 	}
1045 	/* If the old fs ended partway through a cg, we have to update the old
1046 	 * last cg (though possibly not to a full cg!). */
1047 	if (oldsb->fs_size % oldsb->fs_fpg) {
1048 		struct cg *cg;
1049 		int newcgsize;
1050 		int prevcgtop;
1051 		int oldcgsize;
1052 		cg = cgs[oldsb->fs_ncg - 1];
1053 		cgflags[oldsb->fs_ncg - 1] |= CGF_DIRTY | CGF_BLKMAPS;
1054 		prevcgtop = oldsb->fs_fpg * (oldsb->fs_ncg - 1);
1055 		newcgsize = newsb->fs_size - prevcgtop;
1056 		if (newcgsize > newsb->fs_fpg)
1057 			newcgsize = newsb->fs_fpg;
1058 		oldcgsize = oldsb->fs_size % oldsb->fs_fpg;
1059 		set_bits(cg_blksfree(cg, 0), oldcgsize, newcgsize - oldcgsize);
1060 		cg->cg_old_ncyl = oldsb->fs_old_cpg;
1061 		cg->cg_ndblk = newcgsize;
1062 	}
1063 	/* Fix up the csum info, if necessary. */
1064 	csum_fixup();
1065 	/* Make fs_dsize match the new reality. */
1066 	recompute_fs_dsize();
1067 
1068 	progress_done();
1069 }
1070 /*
1071  * Call (*fn)() for each inode, passing the inode and its inumber.  The
1072  *  number of cylinder groups is pased in, so this can be used to map
1073  *  over either the old or the new file system's set of inodes.
1074  */
1075 static void
1076 map_inodes(void (*fn) (union dinode * di, unsigned int, void *arg),
1077 	   int ncg, void *cbarg) {
1078 	int i;
1079 	int ni;
1080 
1081 	ni = oldsb->fs_ipg * ncg;
1082 	for (i = 0; i < ni; i++)
1083 		(*fn) (inodes + i, i, cbarg);
1084 }
1085 /* Values for the third argument to the map function for
1086  * map_inode_data_blocks.  MDB_DATA indicates the block is contains
1087  * file data; MDB_INDIR_PRE and MDB_INDIR_POST indicate that it's an
1088  * indirect block.  The MDB_INDIR_PRE call is made before the indirect
1089  * block pointers are followed and the pointed-to blocks scanned,
1090  * MDB_INDIR_POST after.
1091  */
1092 #define MDB_DATA       1
1093 #define MDB_INDIR_PRE  2
1094 #define MDB_INDIR_POST 3
1095 
1096 typedef void (*mark_callback_t) (off_t blocknum, unsigned int nfrags,
1097 				 unsigned int blksize, int opcode);
1098 
1099 /* Helper function - handles a data block.  Calls the callback
1100  * function and returns number of bytes occupied in file (actually,
1101  * rounded up to a frag boundary).  The name is historical.  */
1102 static int
1103 markblk(mark_callback_t fn, union dinode * di, off_t bn, off_t o)
1104 {
1105 	int sz;
1106 	int nb;
1107 	off_t filesize;
1108 
1109 	filesize = DIP(di,di_size);
1110 	if (o >= filesize)
1111 		return (0);
1112 	sz = dblksize(newsb, di, ffs_lblkno(newsb, o), filesize);
1113 	nb = (sz > filesize - o) ? filesize - o : sz;
1114 	if (bn)
1115 		(*fn) (bn, ffs_numfrags(newsb, sz), nb, MDB_DATA);
1116 	return (sz);
1117 }
1118 /* Helper function - handles an indirect block.  Makes the
1119  * MDB_INDIR_PRE callback for the indirect block, loops over the
1120  * pointers and recurses, and makes the MDB_INDIR_POST callback.
1121  * Returns the number of bytes occupied in file, as does markblk().
1122  * For the sake of update_for_data_move(), we read the indirect block
1123  * _after_ making the _PRE callback.  The name is historical.  */
1124 static int
1125 markiblk(mark_callback_t fn, union dinode * di, off_t bn, off_t o, int lev)
1126 {
1127 	int i;
1128 	int j;
1129 	unsigned k;
1130 	int tot;
1131 	static int32_t indirblk1[howmany(MAXBSIZE, sizeof(int32_t))];
1132 	static int32_t indirblk2[howmany(MAXBSIZE, sizeof(int32_t))];
1133 	static int32_t indirblk3[howmany(MAXBSIZE, sizeof(int32_t))];
1134 	static int32_t *indirblks[3] = {
1135 		&indirblk1[0], &indirblk2[0], &indirblk3[0]
1136 	};
1137 
1138 	if (lev < 0)
1139 		return (markblk(fn, di, bn, o));
1140 	if (bn == 0) {
1141 		for (i = newsb->fs_bsize;
1142 		    lev >= 0;
1143 		    i *= FFS_NINDIR(newsb), lev--);
1144 		return (i);
1145 	}
1146 	(*fn) (bn, newsb->fs_frag, newsb->fs_bsize, MDB_INDIR_PRE);
1147 	readat(FFS_FSBTODB(newsb, bn), indirblks[lev], newsb->fs_bsize);
1148 	if (needswap)
1149 		for (k = 0; k < howmany(MAXBSIZE, sizeof(int32_t)); k++)
1150 			indirblks[lev][k] = bswap32(indirblks[lev][k]);
1151 	tot = 0;
1152 	for (i = 0; i < FFS_NINDIR(newsb); i++) {
1153 		j = markiblk(fn, di, indirblks[lev][i], o, lev - 1);
1154 		if (j == 0)
1155 			break;
1156 		o += j;
1157 		tot += j;
1158 	}
1159 	(*fn) (bn, newsb->fs_frag, newsb->fs_bsize, MDB_INDIR_POST);
1160 	return (tot);
1161 }
1162 
1163 
1164 /*
1165  * Call (*fn)() for each data block for an inode.  This routine assumes
1166  *  the inode is known to be of a type that has data blocks (file,
1167  *  directory, or non-fast symlink).  The called function is:
1168  *
1169  * (*fn)(unsigned int blkno, unsigned int nf, unsigned int nb, int op)
1170  *
1171  *  where blkno is the frag number, nf is the number of frags starting
1172  *  at blkno (always <= fs_frag), nb is the number of bytes that belong
1173  *  to the file (usually nf*fs_frag, often less for the last block/frag
1174  *  of a file).
1175  */
1176 static void
1177 map_inode_data_blocks(union dinode * di, mark_callback_t fn)
1178 {
1179 	off_t o;		/* offset within  inode */
1180 	int inc;		/* increment for o - maybe should be off_t? */
1181 	int b;			/* index within di_db[] and di_ib[] arrays */
1182 
1183 	/* Scan the direct blocks... */
1184 	o = 0;
1185 	for (b = 0; b < UFS_NDADDR; b++) {
1186 		inc = markblk(fn, di, DIP(di,di_db[b]), o);
1187 		if (inc == 0)
1188 			break;
1189 		o += inc;
1190 	}
1191 	/* ...and the indirect blocks. */
1192 	if (inc) {
1193 		for (b = 0; b < UFS_NIADDR; b++) {
1194 			inc = markiblk(fn, di, DIP(di,di_ib[b]), o, b);
1195 			if (inc == 0)
1196 				return;
1197 			o += inc;
1198 		}
1199 	}
1200 }
1201 
1202 static void
1203 dblk_callback(union dinode * di, unsigned int inum, void *arg)
1204 {
1205 	mark_callback_t fn;
1206 	off_t filesize;
1207 
1208 	filesize = DIP(di,di_size);
1209 	fn = (mark_callback_t) arg;
1210 	switch (DIP(di,di_mode) & IFMT) {
1211 	case IFLNK:
1212 		if (filesize <= newsb->fs_maxsymlinklen) {
1213 			break;
1214 		}
1215 		/* FALLTHROUGH */
1216 	case IFDIR:
1217 	case IFREG:
1218 		map_inode_data_blocks(di, fn);
1219 		break;
1220 	}
1221 }
1222 /*
1223  * Make a callback call, a la map_inode_data_blocks, for all data
1224  *  blocks in the entire fs.  This is used only once, in
1225  *  update_for_data_move, but it's out at top level because the complex
1226  *  downward-funarg nesting that would otherwise result seems to give
1227  *  gcc gastric distress.
1228  */
1229 static void
1230 map_data_blocks(mark_callback_t fn, int ncg)
1231 {
1232 	map_inodes(&dblk_callback, ncg, (void *) fn);
1233 }
1234 /*
1235  * Initialize the blkmove array.
1236  */
1237 static void
1238 blkmove_init(void)
1239 {
1240 	int i;
1241 
1242 	blkmove = alloconce(oldsb->fs_size * sizeof(*blkmove), "blkmove");
1243 	for (i = 0; i < oldsb->fs_size; i++)
1244 		blkmove[i] = i;
1245 }
1246 /*
1247  * Load the inodes off disk.  Allocates the structures and initializes
1248  *  them - the inodes from disk, the flags to zero.
1249  */
1250 static void
1251 loadinodes(void)
1252 {
1253 	int imax, ino, i, j;
1254 	struct ufs1_dinode *dp1 = NULL;
1255 	struct ufs2_dinode *dp2 = NULL;
1256 
1257 	/* read inodes one fs block at a time and copy them */
1258 
1259 	inodes = alloconce(oldsb->fs_ncg * oldsb->fs_ipg *
1260 	    sizeof(union dinode), "inodes");
1261 	iflags = alloconce(oldsb->fs_ncg * oldsb->fs_ipg, "inode flags");
1262 	memset(iflags, 0, oldsb->fs_ncg * oldsb->fs_ipg);
1263 
1264 	ibuf = nfmalloc(oldsb->fs_bsize,"inode block buf");
1265 	if (is_ufs2)
1266 		dp2 = (struct ufs2_dinode *)ibuf;
1267 	else
1268 		dp1 = (struct ufs1_dinode *)ibuf;
1269 
1270 	for (ino = 0,imax = oldsb->fs_ipg * oldsb->fs_ncg; ino < imax; ) {
1271 		readat(FFS_FSBTODB(oldsb, ino_to_fsba(oldsb, ino)), ibuf,
1272 		    oldsb->fs_bsize);
1273 
1274 		for (i = 0; i < oldsb->fs_inopb; i++) {
1275 			if (is_ufs2) {
1276 				if (needswap) {
1277 					ffs_dinode2_swap(&(dp2[i]), &(dp2[i]));
1278 					for (j = 0; j < UFS_NDADDR; j++)
1279 						dp2[i].di_db[j] =
1280 						    bswap32(dp2[i].di_db[j]);
1281 					for (j = 0; j < UFS_NIADDR; j++)
1282 						dp2[i].di_ib[j] =
1283 						    bswap32(dp2[i].di_ib[j]);
1284 				}
1285 				memcpy(&inodes[ino].dp2, &dp2[i],
1286 				    sizeof(inodes[ino].dp2));
1287 			} else {
1288 				if (needswap) {
1289 					ffs_dinode1_swap(&(dp1[i]), &(dp1[i]));
1290 					for (j = 0; j < UFS_NDADDR; j++)
1291 						dp1[i].di_db[j] =
1292 						    bswap32(dp1[i].di_db[j]);
1293 					for (j = 0; j < UFS_NIADDR; j++)
1294 						dp1[i].di_ib[j] =
1295 						    bswap32(dp1[i].di_ib[j]);
1296 				}
1297 				memcpy(&inodes[ino].dp1, &dp1[i],
1298 				    sizeof(inodes[ino].dp1));
1299 			}
1300 			    if (++ino > imax)
1301 				    errx(EXIT_FAILURE,
1302 					"Exceeded number of inodes");
1303 		}
1304 
1305 	}
1306 }
1307 /*
1308  * Report a file-system-too-full problem.
1309  */
1310 __dead static void
1311 toofull(void)
1312 {
1313 	errx(EXIT_FAILURE, "Sorry, would run out of data blocks");
1314 }
1315 /*
1316  * Record a desire to move "n" frags from "from" to "to".
1317  */
1318 static void
1319 mark_move(unsigned int from, unsigned int to, unsigned int n)
1320 {
1321 	for (; n > 0; n--)
1322 		blkmove[from++] = to++;
1323 }
1324 /* Helper function - evict n frags, starting with start (cg-relative).
1325  * The free bitmap is scanned, unallocated frags are ignored, and
1326  * each block of consecutive allocated frags is moved as a unit.
1327  */
1328 static void
1329 fragmove(struct cg * cg, int base, unsigned int start, unsigned int n)
1330 {
1331 	unsigned int i;
1332 	int run;
1333 
1334 	run = 0;
1335 	for (i = 0; i <= n; i++) {
1336 		if ((i < n) && bit_is_clr(cg_blksfree(cg, 0), start + i)) {
1337 			run++;
1338 		} else {
1339 			if (run > 0) {
1340 				int off;
1341 				off = find_freespace(run);
1342 				if (off < 0)
1343 					toofull();
1344 				mark_move(base + start + i - run, off, run);
1345 				set_bits(cg_blksfree(cg, 0), start + i - run,
1346 				    run);
1347 				clr_bits(cg_blksfree(cgs[dtog(oldsb, off)], 0),
1348 				    dtogd(oldsb, off), run);
1349 			}
1350 			run = 0;
1351 		}
1352 	}
1353 }
1354 /*
1355  * Evict all data blocks from the given cg, starting at minfrag (based
1356  *  at the beginning of the cg), for length nfrag.  The eviction is
1357  *  assumed to be entirely data-area; this should not be called with a
1358  *  range overlapping the metadata structures in the cg.  It also
1359  *  assumes minfrag points into the given cg; it will misbehave if this
1360  *  is not true.
1361  *
1362  * See the comment header on find_freespace() for one possible bug
1363  *  lurking here.
1364  */
1365 static void
1366 evict_data(struct cg * cg, unsigned int minfrag, int nfrag)
1367 {
1368 	int base;	/* base of cg (in frags from beginning of fs) */
1369 
1370 	base = cgbase(oldsb, cg->cg_cgx);
1371 	/* Does the boundary fall in the middle of a block?  To avoid
1372 	 * breaking between frags allocated as consecutive, we always
1373 	 * evict the whole block in this case, though one could argue
1374 	 * we should check to see if the frag before or after the
1375 	 * break is unallocated. */
1376 	if (minfrag % oldsb->fs_frag) {
1377 		int n;
1378 		n = minfrag % oldsb->fs_frag;
1379 		minfrag -= n;
1380 		nfrag += n;
1381 	}
1382 	/* Do whole blocks.  If a block is wholly free, skip it; if
1383 	 * wholly allocated, move it in toto.  If neither, call
1384 	 * fragmove() to move the frags to new locations. */
1385 	while (nfrag >= oldsb->fs_frag) {
1386 		if (!blk_is_set(cg_blksfree(cg, 0), minfrag, oldsb->fs_frag)) {
1387 			if (blk_is_clr(cg_blksfree(cg, 0), minfrag,
1388 				oldsb->fs_frag)) {
1389 				int off;
1390 				off = find_freeblock();
1391 				if (off < 0)
1392 					toofull();
1393 				mark_move(base + minfrag, off, oldsb->fs_frag);
1394 				set_bits(cg_blksfree(cg, 0), minfrag,
1395 				    oldsb->fs_frag);
1396 				clr_bits(cg_blksfree(cgs[dtog(oldsb, off)], 0),
1397 				    dtogd(oldsb, off), oldsb->fs_frag);
1398 			} else {
1399 				fragmove(cg, base, minfrag, oldsb->fs_frag);
1400 			}
1401 		}
1402 		minfrag += oldsb->fs_frag;
1403 		nfrag -= oldsb->fs_frag;
1404 	}
1405 	/* Clean up any sub-block amount left over. */
1406 	if (nfrag) {
1407 		fragmove(cg, base, minfrag, nfrag);
1408 	}
1409 }
1410 /*
1411  * Move all data blocks according to blkmove.  We have to be careful,
1412  *  because we may be updating indirect blocks that will themselves be
1413  *  getting moved, or inode int32_t arrays that point to indirect
1414  *  blocks that will be moved.  We call this before
1415  *  update_for_data_move, and update_for_data_move does inodes first,
1416  *  then indirect blocks in preorder, so as to make sure that the
1417  *  file system is self-consistent at all points, for better crash
1418  *  tolerance.  (We can get away with this only because all the writes
1419  *  done by perform_data_move() are writing into space that's not used
1420  *  by the old file system.)  If we crash, some things may point to the
1421  *  old data and some to the new, but both copies are the same.  The
1422  *  only wrong things should be csum info and free bitmaps, which fsck
1423  *  is entirely capable of cleaning up.
1424  *
1425  * Since blkmove_init() initializes all blocks to move to their current
1426  *  locations, we can have two blocks marked as wanting to move to the
1427  *  same location, but only two and only when one of them is the one
1428  *  that was already there.  So if blkmove[i]==i, we ignore that entry
1429  *  entirely - for unallocated blocks, we don't want it (and may be
1430  *  putting something else there), and for allocated blocks, we don't
1431  *  want to copy it anywhere.
1432  */
1433 static void
1434 perform_data_move(void)
1435 {
1436 	int i;
1437 	int run;
1438 	int maxrun;
1439 	char buf[65536];
1440 
1441 	maxrun = sizeof(buf) / newsb->fs_fsize;
1442 	run = 0;
1443 	for (i = 0; i < oldsb->fs_size; i++) {
1444 		if ((blkmove[i] == (unsigned)i /*XXX cast*/) ||
1445 		    (run >= maxrun) ||
1446 		    ((run > 0) &&
1447 			(blkmove[i] != blkmove[i - 1] + 1))) {
1448 			if (run > 0) {
1449 				readat(FFS_FSBTODB(oldsb, i - run), &buf[0],
1450 				    run << oldsb->fs_fshift);
1451 				writeat(FFS_FSBTODB(oldsb, blkmove[i - run]),
1452 				    &buf[0], run << oldsb->fs_fshift);
1453 			}
1454 			run = 0;
1455 		}
1456 		if (blkmove[i] != (unsigned)i /*XXX cast*/)
1457 			run++;
1458 	}
1459 	if (run > 0) {
1460 		readat(FFS_FSBTODB(oldsb, i - run), &buf[0],
1461 		    run << oldsb->fs_fshift);
1462 		writeat(FFS_FSBTODB(oldsb, blkmove[i - run]), &buf[0],
1463 		    run << oldsb->fs_fshift);
1464 	}
1465 }
1466 /*
1467  * This modifies an array of int32_t, according to blkmove.  This is
1468  *  used to update inode block arrays and indirect blocks to point to
1469  *  the new locations of data blocks.
1470  *
1471  * Return value is the number of int32_ts that needed updating; in
1472  *  particular, the return value is zero iff nothing was modified.
1473  */
1474 static int
1475 movemap_blocks(int32_t * vec, int n)
1476 {
1477 	int rv;
1478 
1479 	rv = 0;
1480 	for (; n > 0; n--, vec++) {
1481 		if (blkmove[*vec] != (unsigned)*vec /*XXX cast*/) {
1482 			*vec = blkmove[*vec];
1483 			rv++;
1484 		}
1485 	}
1486 	return (rv);
1487 }
1488 static void
1489 moveblocks_callback(union dinode * di, unsigned int inum, void *arg)
1490 {
1491 	int32_t *dblkptr, *iblkptr;
1492 
1493 	switch (DIP(di,di_mode) & IFMT) {
1494 	case IFLNK:
1495 		if ((off_t)DIP(di,di_size) <= oldsb->fs_maxsymlinklen) {
1496 			break;
1497 		}
1498 		/* FALLTHROUGH */
1499 	case IFDIR:
1500 	case IFREG:
1501 		if (is_ufs2) {
1502 			/* XXX these are not int32_t and this is WRONG! */
1503 			dblkptr = (void *) &(di->dp2.di_db[0]);
1504 			iblkptr = (void *) &(di->dp2.di_ib[0]);
1505 		} else {
1506 			dblkptr = &(di->dp1.di_db[0]);
1507 			iblkptr = &(di->dp1.di_ib[0]);
1508 		}
1509 		/*
1510 		 * Don't || these two calls; we need their
1511 		 * side-effects.
1512 		 */
1513 		if (movemap_blocks(dblkptr, UFS_NDADDR)) {
1514 			iflags[inum] |= IF_DIRTY;
1515 		}
1516 		if (movemap_blocks(iblkptr, UFS_NIADDR)) {
1517 			iflags[inum] |= IF_DIRTY;
1518 		}
1519 		break;
1520 	}
1521 }
1522 
1523 static void
1524 moveindir_callback(off_t off, unsigned int nfrag, unsigned int nbytes,
1525 		   int kind)
1526 {
1527 	unsigned int i;
1528 
1529 	if (kind == MDB_INDIR_PRE) {
1530 		int32_t blk[howmany(MAXBSIZE, sizeof(int32_t))];
1531 		readat(FFS_FSBTODB(oldsb, off), &blk[0], oldsb->fs_bsize);
1532 		if (needswap)
1533 			for (i = 0; i < howmany(MAXBSIZE, sizeof(int32_t)); i++)
1534 				blk[i] = bswap32(blk[i]);
1535 		if (movemap_blocks(&blk[0], FFS_NINDIR(oldsb))) {
1536 			if (needswap)
1537 				for (i = 0; i < howmany(MAXBSIZE,
1538 					sizeof(int32_t)); i++)
1539 					blk[i] = bswap32(blk[i]);
1540 			writeat(FFS_FSBTODB(oldsb, off), &blk[0], oldsb->fs_bsize);
1541 		}
1542 	}
1543 }
1544 /*
1545  * Update all inode data arrays and indirect blocks to point to the new
1546  *  locations of data blocks.  See the comment header on
1547  *  perform_data_move for some ordering considerations.
1548  */
1549 static void
1550 update_for_data_move(void)
1551 {
1552 	map_inodes(&moveblocks_callback, oldsb->fs_ncg, NULL);
1553 	map_data_blocks(&moveindir_callback, oldsb->fs_ncg);
1554 }
1555 /*
1556  * Initialize the inomove array.
1557  */
1558 static void
1559 inomove_init(void)
1560 {
1561 	int i;
1562 
1563 	inomove = alloconce(oldsb->fs_ipg * oldsb->fs_ncg * sizeof(*inomove),
1564                             "inomove");
1565 	for (i = (oldsb->fs_ipg * oldsb->fs_ncg) - 1; i >= 0; i--)
1566 		inomove[i] = i;
1567 }
1568 /*
1569  * Flush all dirtied inodes to disk.  Scans the inode flags array; for
1570  *  each dirty inode, it sets the BDIRTY bit on the first inode in the
1571  *  block containing the dirty inode.  Then it scans by blocks, and for
1572  *  each marked block, writes it.
1573  */
1574 static void
1575 flush_inodes(void)
1576 {
1577 	int i, j, k, ni, m;
1578 	struct ufs1_dinode *dp1 = NULL;
1579 	struct ufs2_dinode *dp2 = NULL;
1580 
1581 	ni = newsb->fs_ipg * newsb->fs_ncg;
1582 	m = FFS_INOPB(newsb) - 1;
1583 	for (i = 0; i < ni; i++) {
1584 		if (iflags[i] & IF_DIRTY) {
1585 			iflags[i & ~m] |= IF_BDIRTY;
1586 		}
1587 	}
1588 	m++;
1589 
1590 	if (is_ufs2)
1591 		dp2 = (struct ufs2_dinode *)ibuf;
1592 	else
1593 		dp1 = (struct ufs1_dinode *)ibuf;
1594 
1595 	for (i = 0; i < ni; i += m) {
1596 		if ((iflags[i] & IF_BDIRTY) == 0)
1597 			continue;
1598 		if (is_ufs2)
1599 			for (j = 0; j < m; j++) {
1600 				dp2[j] = inodes[i + j].dp2;
1601 				if (needswap) {
1602 					for (k = 0; k < UFS_NDADDR; k++)
1603 						dp2[j].di_db[k] =
1604 						    bswap32(dp2[j].di_db[k]);
1605 					for (k = 0; k < UFS_NIADDR; k++)
1606 						dp2[j].di_ib[k] =
1607 						    bswap32(dp2[j].di_ib[k]);
1608 					ffs_dinode2_swap(&dp2[j],
1609 					    &dp2[j]);
1610 				}
1611 			}
1612 		else
1613 			for (j = 0; j < m; j++) {
1614 				dp1[j] = inodes[i + j].dp1;
1615 				if (needswap) {
1616 					for (k = 0; k < UFS_NDADDR; k++)
1617 						dp1[j].di_db[k]=
1618 						    bswap32(dp1[j].di_db[k]);
1619 					for (k = 0; k < UFS_NIADDR; k++)
1620 						dp1[j].di_ib[k]=
1621 						    bswap32(dp1[j].di_ib[k]);
1622 					ffs_dinode1_swap(&dp1[j],
1623 					    &dp1[j]);
1624 				}
1625 			}
1626 
1627 		writeat(FFS_FSBTODB(newsb, ino_to_fsba(newsb, i)),
1628 		    ibuf, newsb->fs_bsize);
1629 	}
1630 }
1631 /*
1632  * Evict all inodes from the specified cg.  shrink() already checked
1633  *  that there were enough free inodes, so the no-free-inodes check is
1634  *  a can't-happen.  If it does trip, the file system should be in good
1635  *  enough shape for fsck to fix; see the comment on perform_data_move
1636  *  for the considerations in question.
1637  */
1638 static void
1639 evict_inodes(struct cg * cg)
1640 {
1641 	int inum;
1642 	int i;
1643 	int fi;
1644 
1645 	inum = newsb->fs_ipg * cg->cg_cgx;
1646 	for (i = 0; i < newsb->fs_ipg; i++, inum++) {
1647 		if (DIP(inodes + inum,di_mode) != 0) {
1648 			fi = find_freeinode();
1649 			if (fi < 0)
1650 				errx(EXIT_FAILURE, "Sorry, inodes evaporated - "
1651 				    "file system probably needs fsck");
1652 			inomove[inum] = fi;
1653 			clr_bits(cg_inosused(cg, 0), i, 1);
1654 			set_bits(cg_inosused(cgs[ino_to_cg(newsb, fi)], 0),
1655 			    fi % newsb->fs_ipg, 1);
1656 		}
1657 	}
1658 }
1659 /*
1660  * Move inodes from old locations to new.  Does not actually write
1661  *  anything to disk; just copies in-core and sets dirty bits.
1662  *
1663  * We have to be careful here for reasons similar to those mentioned in
1664  *  the comment header on perform_data_move, above: for the sake of
1665  *  crash tolerance, we want to make sure everything is present at both
1666  *  old and new locations before we update pointers.  So we call this
1667  *  first, then flush_inodes() to get them out on disk, then update
1668  *  directories to match.
1669  */
1670 static void
1671 perform_inode_move(void)
1672 {
1673 	unsigned int i;
1674 	unsigned int ni;
1675 
1676 	ni = oldsb->fs_ipg * oldsb->fs_ncg;
1677 	for (i = 0; i < ni; i++) {
1678 		if (inomove[i] != i) {
1679 			inodes[inomove[i]] = inodes[i];
1680 			iflags[inomove[i]] = iflags[i] | IF_DIRTY;
1681 		}
1682 	}
1683 }
1684 /*
1685  * Update the directory contained in the nb bytes at buf, to point to
1686  *  inodes' new locations.
1687  */
1688 static int
1689 update_dirents(char *buf, int nb)
1690 {
1691 	int rv;
1692 #define d ((struct direct *)buf)
1693 #define s32(x) (needswap?bswap32((x)):(x))
1694 #define s16(x) (needswap?bswap16((x)):(x))
1695 
1696 	rv = 0;
1697 	while (nb > 0) {
1698 		if (inomove[s32(d->d_ino)] != s32(d->d_ino)) {
1699 			rv++;
1700 			d->d_ino = s32(inomove[s32(d->d_ino)]);
1701 		}
1702 		nb -= s16(d->d_reclen);
1703 		buf += s16(d->d_reclen);
1704 	}
1705 	return (rv);
1706 #undef d
1707 #undef s32
1708 #undef s16
1709 }
1710 /*
1711  * Callback function for map_inode_data_blocks, for updating a
1712  *  directory to point to new inode locations.
1713  */
1714 static void
1715 update_dir_data(off_t bn, unsigned int size, unsigned int nb, int kind)
1716 {
1717 	if (kind == MDB_DATA) {
1718 		union {
1719 			struct direct d;
1720 			char ch[MAXBSIZE];
1721 		}     buf;
1722 		readat(FFS_FSBTODB(oldsb, bn), &buf, size << oldsb->fs_fshift);
1723 		if (update_dirents((char *) &buf, nb)) {
1724 			writeat(FFS_FSBTODB(oldsb, bn), &buf,
1725 			    size << oldsb->fs_fshift);
1726 		}
1727 	}
1728 }
1729 static void
1730 dirmove_callback(union dinode * di, unsigned int inum, void *arg)
1731 {
1732 	switch (DIP(di,di_mode) & IFMT) {
1733 	case IFDIR:
1734 		map_inode_data_blocks(di, &update_dir_data);
1735 		break;
1736 	}
1737 }
1738 /*
1739  * Update directory entries to point to new inode locations.
1740  */
1741 static void
1742 update_for_inode_move(void)
1743 {
1744 	map_inodes(&dirmove_callback, newsb->fs_ncg, NULL);
1745 }
1746 /*
1747  * Shrink the file system.
1748  */
1749 static void
1750 shrink(void)
1751 {
1752 	int i;
1753 
1754 	if (makegeometry(1)) {
1755 		printf("New fs size %"PRIu64" = old fs size %"PRIu64
1756 		    ", not shrinking.\n", newsb->fs_size, oldsb->fs_size);
1757 		return;
1758 	}
1759 
1760 	/* Let's make sure we're not being shrunk into oblivion. */
1761 	if (newsb->fs_ncg < 1)
1762 		errx(EXIT_FAILURE, "Size too small - file system would "
1763 		    "have no cylinders");
1764 
1765 	if (verbose) {
1766 		printf("Shrinking fs from %"PRIu64" blocks to %"PRIu64
1767 		    " blocks.\n", oldsb->fs_size, newsb->fs_size);
1768 	}
1769 
1770 	/* Load the inodes off disk - we'll need 'em. */
1771 	loadinodes();
1772 
1773 	/* Update the timestamp. */
1774 	newsb->fs_time = timestamp();
1775 
1776 	/* Initialize for block motion. */
1777 	blkmove_init();
1778 	/* Update csum size, then fix up for the new size */
1779 	newsb->fs_cssize = ffs_fragroundup(newsb,
1780 	    newsb->fs_ncg * sizeof(struct csum));
1781 	csum_fixup();
1782 	/* Evict data from any cgs being wholly eliminated */
1783 	for (i = newsb->fs_ncg; i < oldsb->fs_ncg; i++) {
1784 		int base;
1785 		int dlow;
1786 		int dhigh;
1787 		int dmax;
1788 		base = cgbase(oldsb, i);
1789 		dlow = cgsblock(oldsb, i) - base;
1790 		dhigh = cgdmin(oldsb, i) - base;
1791 		dmax = oldsb->fs_size - base;
1792 		if (dmax > cgs[i]->cg_ndblk)
1793 			dmax = cgs[i]->cg_ndblk;
1794 		evict_data(cgs[i], 0, dlow);
1795 		evict_data(cgs[i], dhigh, dmax - dhigh);
1796 		newsb->fs_cstotal.cs_ndir -= cgs[i]->cg_cs.cs_ndir;
1797 		newsb->fs_cstotal.cs_nifree -= cgs[i]->cg_cs.cs_nifree;
1798 		newsb->fs_cstotal.cs_nffree -= cgs[i]->cg_cs.cs_nffree;
1799 		newsb->fs_cstotal.cs_nbfree -= cgs[i]->cg_cs.cs_nbfree;
1800 	}
1801 	/* Update the new last cg. */
1802 	cgs[newsb->fs_ncg - 1]->cg_ndblk = newsb->fs_size -
1803 	    ((newsb->fs_ncg - 1) * newsb->fs_fpg);
1804 	/* Is the new last cg partial?  If so, evict any data from the part
1805 	 * being shrunken away. */
1806 	if (newsb->fs_size % newsb->fs_fpg) {
1807 		struct cg *cg;
1808 		int oldcgsize;
1809 		int newcgsize;
1810 		cg = cgs[newsb->fs_ncg - 1];
1811 		newcgsize = newsb->fs_size % newsb->fs_fpg;
1812 		oldcgsize = oldsb->fs_size - ((newsb->fs_ncg - 1) &
1813 		    oldsb->fs_fpg);
1814 		if (oldcgsize > oldsb->fs_fpg)
1815 			oldcgsize = oldsb->fs_fpg;
1816 		evict_data(cg, newcgsize, oldcgsize - newcgsize);
1817 		clr_bits(cg_blksfree(cg, 0), newcgsize, oldcgsize - newcgsize);
1818 	}
1819 	/* Find out whether we would run out of inodes.  (Note we
1820 	 * haven't actually done anything to the file system yet; all
1821 	 * those evict_data calls just update blkmove.) */
1822 	{
1823 		int slop;
1824 		slop = 0;
1825 		for (i = 0; i < newsb->fs_ncg; i++)
1826 			slop += cgs[i]->cg_cs.cs_nifree;
1827 		for (; i < oldsb->fs_ncg; i++)
1828 			slop -= oldsb->fs_ipg - cgs[i]->cg_cs.cs_nifree;
1829 		if (slop < 0)
1830 			errx(EXIT_FAILURE, "Sorry, would run out of inodes");
1831 	}
1832 	/* Copy data, then update pointers to data.  See the comment
1833 	 * header on perform_data_move for ordering considerations. */
1834 	perform_data_move();
1835 	update_for_data_move();
1836 	/* Now do inodes.  Initialize, evict, move, update - see the
1837 	 * comment header on perform_inode_move. */
1838 	inomove_init();
1839 	for (i = newsb->fs_ncg; i < oldsb->fs_ncg; i++)
1840 		evict_inodes(cgs[i]);
1841 	perform_inode_move();
1842 	flush_inodes();
1843 	update_for_inode_move();
1844 	/* Recompute all the bitmaps; most of them probably need it anyway,
1845 	 * the rest are just paranoia and not wanting to have to bother
1846 	 * keeping track of exactly which ones require it. */
1847 	for (i = 0; i < newsb->fs_ncg; i++)
1848 		cgflags[i] |= CGF_DIRTY | CGF_BLKMAPS | CGF_INOMAPS;
1849 	/* Update the cg_old_ncyl value for the last cylinder. */
1850 	if ((newsb->fs_old_flags & FS_FLAGS_UPDATED) == 0)
1851 		cgs[newsb->fs_ncg - 1]->cg_old_ncyl =
1852 		    newsb->fs_old_ncyl % newsb->fs_old_cpg;
1853 	/* Make fs_dsize match the new reality. */
1854 	recompute_fs_dsize();
1855 }
1856 /*
1857  * Recompute the block totals, block cluster summaries, and rotational
1858  *  position summaries, for a given cg (specified by number), based on
1859  *  its free-frag bitmap (cg_blksfree()[]).
1860  */
1861 static void
1862 rescan_blkmaps(int cgn)
1863 {
1864 	struct cg *cg;
1865 	int f;
1866 	int b;
1867 	int blkfree;
1868 	int blkrun;
1869 	int fragrun;
1870 	int fwb;
1871 
1872 	cg = cgs[cgn];
1873 	/* Subtract off the current totals from the sb's summary info */
1874 	newsb->fs_cstotal.cs_nffree -= cg->cg_cs.cs_nffree;
1875 	newsb->fs_cstotal.cs_nbfree -= cg->cg_cs.cs_nbfree;
1876 	/* Clear counters and bitmaps. */
1877 	cg->cg_cs.cs_nffree = 0;
1878 	cg->cg_cs.cs_nbfree = 0;
1879 	memset(&cg->cg_frsum[0], 0, MAXFRAG * sizeof(cg->cg_frsum[0]));
1880 	memset(&old_cg_blktot(cg, 0)[0], 0,
1881 	    newsb->fs_old_cpg * sizeof(old_cg_blktot(cg, 0)[0]));
1882 	memset(&old_cg_blks(newsb, cg, 0, 0)[0], 0,
1883 	    newsb->fs_old_cpg * newsb->fs_old_nrpos *
1884 	    sizeof(old_cg_blks(newsb, cg, 0, 0)[0]));
1885 	if (newsb->fs_contigsumsize > 0) {
1886 		cg->cg_nclusterblks = cg->cg_ndblk / newsb->fs_frag;
1887 		memset(&cg_clustersum(cg, 0)[1], 0,
1888 		    newsb->fs_contigsumsize *
1889 		    sizeof(cg_clustersum(cg, 0)[1]));
1890 		if (is_ufs2)
1891 			memset(&cg_clustersfree(cg, 0)[0], 0,
1892 			    howmany(newsb->fs_fpg / NSPB(newsb), NBBY));
1893 		else
1894 			memset(&cg_clustersfree(cg, 0)[0], 0,
1895 			    howmany((newsb->fs_old_cpg * newsb->fs_old_spc) /
1896 				NSPB(newsb), NBBY));
1897 	}
1898 	/* Scan the free-frag bitmap.  Runs of free frags are kept
1899 	 * track of with fragrun, and recorded into cg_frsum[] and
1900 	 * cg_cs.cs_nffree; on each block boundary, entire free blocks
1901 	 * are recorded as well. */
1902 	blkfree = 1;
1903 	blkrun = 0;
1904 	fragrun = 0;
1905 	f = 0;
1906 	b = 0;
1907 	fwb = 0;
1908 	while (f < cg->cg_ndblk) {
1909 		if (bit_is_set(cg_blksfree(cg, 0), f)) {
1910 			fragrun++;
1911 		} else {
1912 			blkfree = 0;
1913 			if (fragrun > 0) {
1914 				cg->cg_frsum[fragrun]++;
1915 				cg->cg_cs.cs_nffree += fragrun;
1916 			}
1917 			fragrun = 0;
1918 		}
1919 		f++;
1920 		fwb++;
1921 		if (fwb >= newsb->fs_frag) {
1922 			if (blkfree) {
1923 				cg->cg_cs.cs_nbfree++;
1924 				if (newsb->fs_contigsumsize > 0)
1925 					set_bits(cg_clustersfree(cg, 0), b, 1);
1926 				if (is_ufs2 == 0) {
1927 					old_cg_blktot(cg, 0)[
1928 						old_cbtocylno(newsb,
1929 						    f - newsb->fs_frag)]++;
1930 					old_cg_blks(newsb, cg,
1931 					    old_cbtocylno(newsb,
1932 						f - newsb->fs_frag),
1933 					    0)[old_cbtorpos(newsb,
1934 						    f - newsb->fs_frag)]++;
1935 				}
1936 				blkrun++;
1937 			} else {
1938 				if (fragrun > 0) {
1939 					cg->cg_frsum[fragrun]++;
1940 					cg->cg_cs.cs_nffree += fragrun;
1941 				}
1942 				if (newsb->fs_contigsumsize > 0) {
1943 					if (blkrun > 0) {
1944 						cg_clustersum(cg, 0)[(blkrun
1945 						    > newsb->fs_contigsumsize)
1946 						    ? newsb->fs_contigsumsize
1947 						    : blkrun]++;
1948 					}
1949 				}
1950 				blkrun = 0;
1951 			}
1952 			fwb = 0;
1953 			b++;
1954 			blkfree = 1;
1955 			fragrun = 0;
1956 		}
1957 	}
1958 	if (fragrun > 0) {
1959 		cg->cg_frsum[fragrun]++;
1960 		cg->cg_cs.cs_nffree += fragrun;
1961 	}
1962 	if ((blkrun > 0) && (newsb->fs_contigsumsize > 0)) {
1963 		cg_clustersum(cg, 0)[(blkrun > newsb->fs_contigsumsize) ?
1964 		    newsb->fs_contigsumsize : blkrun]++;
1965 	}
1966 	/*
1967          * Put the updated summary info back into csums, and add it
1968          * back into the sb's summary info.  Then mark the cg dirty.
1969          */
1970 	csums[cgn] = cg->cg_cs;
1971 	newsb->fs_cstotal.cs_nffree += cg->cg_cs.cs_nffree;
1972 	newsb->fs_cstotal.cs_nbfree += cg->cg_cs.cs_nbfree;
1973 	cgflags[cgn] |= CGF_DIRTY;
1974 }
1975 /*
1976  * Recompute the cg_inosused()[] bitmap, and the cs_nifree and cs_ndir
1977  *  values, for a cg, based on the in-core inodes for that cg.
1978  */
1979 static void
1980 rescan_inomaps(int cgn)
1981 {
1982 	struct cg *cg;
1983 	int inum;
1984 	int iwc;
1985 
1986 	cg = cgs[cgn];
1987 	newsb->fs_cstotal.cs_ndir -= cg->cg_cs.cs_ndir;
1988 	newsb->fs_cstotal.cs_nifree -= cg->cg_cs.cs_nifree;
1989 	cg->cg_cs.cs_ndir = 0;
1990 	cg->cg_cs.cs_nifree = 0;
1991 	memset(&cg_inosused(cg, 0)[0], 0, howmany(newsb->fs_ipg, NBBY));
1992 	inum = cgn * newsb->fs_ipg;
1993 	if (cgn == 0) {
1994 		set_bits(cg_inosused(cg, 0), 0, 2);
1995 		iwc = 2;
1996 		inum += 2;
1997 	} else {
1998 		iwc = 0;
1999 	}
2000 	for (; iwc < newsb->fs_ipg; iwc++, inum++) {
2001 		switch (DIP(inodes + inum, di_mode) & IFMT) {
2002 		case 0:
2003 			cg->cg_cs.cs_nifree++;
2004 			break;
2005 		case IFDIR:
2006 			cg->cg_cs.cs_ndir++;
2007 			/* FALLTHROUGH */
2008 		default:
2009 			set_bits(cg_inosused(cg, 0), iwc, 1);
2010 			break;
2011 		}
2012 	}
2013 	csums[cgn] = cg->cg_cs;
2014 	newsb->fs_cstotal.cs_ndir += cg->cg_cs.cs_ndir;
2015 	newsb->fs_cstotal.cs_nifree += cg->cg_cs.cs_nifree;
2016 	cgflags[cgn] |= CGF_DIRTY;
2017 }
2018 /*
2019  * Flush cgs to disk, recomputing anything they're marked as needing.
2020  */
2021 static void
2022 flush_cgs(void)
2023 {
2024 	int i;
2025 
2026 	for (i = 0; i < newsb->fs_ncg; i++) {
2027 		progress_bar(special, "flush cg",
2028 		    i, newsb->fs_ncg - 1);
2029 		if (cgflags[i] & CGF_BLKMAPS) {
2030 			rescan_blkmaps(i);
2031 		}
2032 		if (cgflags[i] & CGF_INOMAPS) {
2033 			rescan_inomaps(i);
2034 		}
2035 		if (cgflags[i] & CGF_DIRTY) {
2036 			cgs[i]->cg_rotor = 0;
2037 			cgs[i]->cg_frotor = 0;
2038 			cgs[i]->cg_irotor = 0;
2039 			if (needswap)
2040 				ffs_cg_swap(cgs[i],cgs[i],newsb);
2041 			writeat(FFS_FSBTODB(newsb, cgtod(newsb, i)), cgs[i],
2042 			    cgblksz);
2043 		}
2044 	}
2045 	if (needswap)
2046 		ffs_csum_swap(csums,csums,newsb->fs_cssize);
2047 	writeat(FFS_FSBTODB(newsb, newsb->fs_csaddr), csums, newsb->fs_cssize);
2048 
2049 	progress_done();
2050 }
2051 /*
2052  * Write the superblock, both to the main superblock and to each cg's
2053  *  alternative superblock.
2054  */
2055 static void
2056 write_sbs(void)
2057 {
2058 	int i;
2059 
2060 	if (newsb->fs_magic == FS_UFS1_MAGIC &&
2061 	    (newsb->fs_old_flags & FS_FLAGS_UPDATED) == 0) {
2062 		newsb->fs_old_time = newsb->fs_time;
2063 	    	newsb->fs_old_size = newsb->fs_size;
2064 	    	/* we don't update fs_csaddr */
2065 	    	newsb->fs_old_dsize = newsb->fs_dsize;
2066 		newsb->fs_old_cstotal.cs_ndir = newsb->fs_cstotal.cs_ndir;
2067 		newsb->fs_old_cstotal.cs_nbfree = newsb->fs_cstotal.cs_nbfree;
2068 		newsb->fs_old_cstotal.cs_nifree = newsb->fs_cstotal.cs_nifree;
2069 		newsb->fs_old_cstotal.cs_nffree = newsb->fs_cstotal.cs_nffree;
2070 		/* fill fs_old_postbl_start with 256 bytes of 0xff? */
2071 	}
2072 	/* copy newsb back to oldsb, so we can use it for offsets if
2073 	   newsb has been swapped for writing to disk */
2074 	memcpy(oldsb, newsb, SBLOCKSIZE);
2075 	if (needswap)
2076 		ffs_sb_swap(newsb,newsb);
2077 	writeat(where /  DEV_BSIZE, newsb, SBLOCKSIZE);
2078 	for (i = 0; i < oldsb->fs_ncg; i++) {
2079 		progress_bar(special, "write sb",
2080 		    i, oldsb->fs_ncg - 1);
2081 		writeat(FFS_FSBTODB(oldsb, cgsblock(oldsb, i)), newsb, SBLOCKSIZE);
2082 	}
2083 
2084 	progress_done();
2085 }
2086 
2087 /*
2088  * Check to see wether new size changes the filesystem
2089  *  return exit code
2090  */
2091 static int
2092 checkonly(void)
2093 {
2094 	if (makegeometry(0)) {
2095 		if (verbose) {
2096 			printf("Wouldn't change: already %" PRId64
2097 			    " blocks\n", (int64_t)oldsb->fs_size);
2098 		}
2099 		return 1;
2100 	}
2101 
2102 	if (verbose) {
2103 		printf("Would change: newsize: %" PRId64 " oldsize: %"
2104 		    PRId64 " fsdb: %" PRId64 "\n", FFS_DBTOFSB(oldsb, newsize),
2105 		    (int64_t)oldsb->fs_size,
2106 		    (int64_t)oldsb->fs_fsbtodb);
2107 	}
2108 	return 0;
2109 }
2110 
2111 static off_t
2112 get_dev_size(char *dev_name)
2113 {
2114 	struct dkwedge_info dkw;
2115 	struct partition *pp;
2116 	struct disklabel lp;
2117 	struct stat st;
2118 	size_t ptn;
2119 
2120 	/* Get info about partition/wedge */
2121 	if (ioctl(fd, DIOCGWEDGEINFO, &dkw) != -1)
2122 		return dkw.dkw_size;
2123 	if (ioctl(fd, DIOCGDINFO, &lp) != -1) {
2124 		ptn = strchr(dev_name, '\0')[-1] - 'a';
2125 		if (ptn >= lp.d_npartitions)
2126 			return 0;
2127 		pp = &lp.d_partitions[ptn];
2128 		return pp->p_size;
2129 	}
2130 	if (fstat(fd, &st) != -1 && S_ISREG(st.st_mode))
2131 		return st.st_size / DEV_BSIZE;
2132 
2133 	return 0;
2134 }
2135 
2136 /*
2137  * main().
2138  */
2139 int
2140 main(int argc, char **argv)
2141 {
2142 	int ch;
2143 	int CheckOnlyFlag;
2144 	int ExpertFlag;
2145 	int SFlag;
2146 	size_t i;
2147 
2148 	char reply[5];
2149 
2150 	newsize = 0;
2151 	ExpertFlag = 0;
2152 	SFlag = 0;
2153         CheckOnlyFlag = 0;
2154 
2155 	while ((ch = getopt(argc, argv, "cps:vy")) != -1) {
2156 		switch (ch) {
2157                 case 'c':
2158 			CheckOnlyFlag = 1;
2159 			break;
2160 		case 'p':
2161 			progress = 1;
2162 			break;
2163 		case 's':
2164 			SFlag = 1;
2165 			newsize = strtoll(optarg, NULL, 10);
2166 			if(newsize < 1) {
2167 				usage();
2168 			}
2169 			break;
2170 		case 'v':
2171 			verbose = 1;
2172 			break;
2173 		case 'y':
2174 			ExpertFlag = 1;
2175 			break;
2176 		case '?':
2177 			/* FALLTHROUGH */
2178 		default:
2179 			usage();
2180 		}
2181 	}
2182 	argc -= optind;
2183 	argv += optind;
2184 
2185 	if (argc != 1) {
2186 		usage();
2187 	}
2188 
2189 	special = *argv;
2190 
2191 	if (ExpertFlag == 0 && CheckOnlyFlag == 0) {
2192 		printf("It's required to manually run fsck on file system "
2193 		    "before you can resize it\n\n"
2194 		    " Did you run fsck on your disk (Yes/No) ? ");
2195 		fgets(reply, (int)sizeof(reply), stdin);
2196 		if (strcasecmp(reply, "Yes\n")) {
2197 			printf("\n Nothing done \n");
2198 			exit(EXIT_SUCCESS);
2199 		}
2200 	}
2201 
2202 	fd = open(special, O_RDWR, 0);
2203 	if (fd < 0)
2204 		err(EXIT_FAILURE, "Can't open `%s'", special);
2205 	checksmallio();
2206 
2207 	if (SFlag == 0) {
2208 		newsize = get_dev_size(special);
2209 		if (newsize == 0)
2210 			err(EXIT_FAILURE,
2211 			    "Can't resize file system, newsize not known.");
2212 	}
2213 
2214 	oldsb = (struct fs *) & sbbuf;
2215 	newsb = (struct fs *) (SBLOCKSIZE + (char *) &sbbuf);
2216 	for (where = search[i = 0]; search[i] != -1; where = search[++i]) {
2217 		readat(where / DEV_BSIZE, oldsb, SBLOCKSIZE);
2218 		switch (oldsb->fs_magic) {
2219 		case FS_UFS2_MAGIC:
2220 			is_ufs2 = 1;
2221 			/* FALLTHROUGH */
2222 		case FS_UFS1_MAGIC:
2223 			needswap = 0;
2224 			break;
2225 		case FS_UFS2_MAGIC_SWAPPED:
2226  			is_ufs2 = 1;
2227 			/* FALLTHROUGH */
2228 		case FS_UFS1_MAGIC_SWAPPED:
2229 			needswap = 1;
2230 			break;
2231 		default:
2232 			continue;
2233 		}
2234 		if (!is_ufs2 && where == SBLOCK_UFS2)
2235 			continue;
2236 		break;
2237 	}
2238 	if (where == (off_t)-1)
2239 		errx(EXIT_FAILURE, "Bad magic number");
2240 	if (needswap)
2241 		ffs_sb_swap(oldsb,oldsb);
2242 	if (oldsb->fs_magic == FS_UFS1_MAGIC &&
2243 	    (oldsb->fs_old_flags & FS_FLAGS_UPDATED) == 0) {
2244 		oldsb->fs_csaddr = oldsb->fs_old_csaddr;
2245 		oldsb->fs_size = oldsb->fs_old_size;
2246 		oldsb->fs_dsize = oldsb->fs_old_dsize;
2247 		oldsb->fs_cstotal.cs_ndir = oldsb->fs_old_cstotal.cs_ndir;
2248 		oldsb->fs_cstotal.cs_nbfree = oldsb->fs_old_cstotal.cs_nbfree;
2249 		oldsb->fs_cstotal.cs_nifree = oldsb->fs_old_cstotal.cs_nifree;
2250 		oldsb->fs_cstotal.cs_nffree = oldsb->fs_old_cstotal.cs_nffree;
2251 		/* any others? */
2252 		printf("Resizing with ffsv1 superblock\n");
2253 	}
2254 
2255 	oldsb->fs_qbmask = ~(int64_t) oldsb->fs_bmask;
2256 	oldsb->fs_qfmask = ~(int64_t) oldsb->fs_fmask;
2257 	if (oldsb->fs_ipg % FFS_INOPB(oldsb))
2258 		errx(EXIT_FAILURE, "ipg[%d] %% FFS_INOPB[%d] != 0",
2259 		    (int) oldsb->fs_ipg, (int) FFS_INOPB(oldsb));
2260 	/* The superblock is bigger than struct fs (there are trailing
2261 	 * tables, of non-fixed size); make sure we copy the whole
2262 	 * thing.  SBLOCKSIZE may be an over-estimate, but we do this
2263 	 * just once, so being generous is cheap. */
2264 	memcpy(newsb, oldsb, SBLOCKSIZE);
2265 
2266 	if (progress) {
2267 		progress_ttywidth(0);
2268 		signal(SIGWINCH, progress_ttywidth);
2269 	}
2270 
2271 	loadcgs();
2272 
2273 	if (progress && !CheckOnlyFlag) {
2274 		progress_switch(progress);
2275 		progress_init();
2276 	}
2277 
2278 	if (newsize > FFS_FSBTODB(oldsb, oldsb->fs_size)) {
2279 		if (CheckOnlyFlag)
2280 			exit(checkonly());
2281 		grow();
2282 	} else if (newsize < FFS_FSBTODB(oldsb, oldsb->fs_size)) {
2283 		if (is_ufs2)
2284 			errx(EXIT_FAILURE,"shrinking not supported for ufs2");
2285 		if (CheckOnlyFlag)
2286 			exit(checkonly());
2287 		shrink();
2288 	} else {
2289 		if (CheckOnlyFlag)
2290 			exit(checkonly());
2291 		if (verbose)
2292 			printf("No change requested: already %" PRId64
2293 			    " blocks\n", (int64_t)oldsb->fs_size);
2294 	}
2295 
2296 	flush_cgs();
2297 	write_sbs();
2298 	if (isplainfile())
2299 		ftruncate(fd,newsize * DEV_BSIZE);
2300 	return 0;
2301 }
2302 
2303 static void
2304 usage(void)
2305 {
2306 
2307 	(void)fprintf(stderr, "usage: %s [-cvy] [-s size] special\n",
2308 	    getprogname());
2309 	exit(EXIT_FAILURE);
2310 }
2311