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