xref: /freebsd/usr.sbin/makefs/ffs/mkfs.c (revision a2aef24aa3c8458e4036735dd6928b4ef77294e5)
1 /*	$NetBSD: mkfs.c,v 1.22 2011/10/09 22:30:13 christos Exp $	*/
2 
3 /*
4  * Copyright (c) 2002 Networks Associates Technology, Inc.
5  * All rights reserved.
6  *
7  * This software was developed for the FreeBSD Project by Marshall
8  * Kirk McKusick and Network Associates Laboratories, the Security
9  * Research Division of Network Associates, Inc. under DARPA/SPAWAR
10  * contract N66001-01-C-8035 ("CBOSS"), as part of the DARPA CHATS
11  * research program
12  *
13  * Copyright (c) 1980, 1989, 1993
14  *	The Regents of the University of California.  All rights reserved.
15  *
16  * Redistribution and use in source and binary forms, with or without
17  * modification, are permitted provided that the following conditions
18  * are met:
19  * 1. Redistributions of source code must retain the above copyright
20  *    notice, this list of conditions and the following disclaimer.
21  * 2. Redistributions in binary form must reproduce the above copyright
22  *    notice, this list of conditions and the following disclaimer in the
23  *    documentation and/or other materials provided with the distribution.
24  * 3. Neither the name of the University nor the names of its contributors
25  *    may be used to endorse or promote products derived from this software
26  *    without specific prior written permission.
27  *
28  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
29  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
32  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38  * SUCH DAMAGE.
39  */
40 
41 #include <sys/cdefs.h>
42 __FBSDID("$FreeBSD$");
43 
44 #include <sys/param.h>
45 #include <sys/time.h>
46 #include <sys/resource.h>
47 
48 #include <stdio.h>
49 #include <stdlib.h>
50 #include <string.h>
51 #include <unistd.h>
52 #include <errno.h>
53 #include <util.h>
54 
55 #include "makefs.h"
56 #include "ffs.h"
57 
58 #include <ufs/ufs/dinode.h>
59 #include <ufs/ffs/fs.h>
60 
61 #include "ffs/ufs_bswap.h"
62 #include "ffs/ufs_inode.h"
63 #include "ffs/ffs_extern.h"
64 #include "ffs/newfs_extern.h"
65 
66 #ifndef BBSIZE
67 #define	BBSIZE	8192			/* size of boot area, with label */
68 #endif
69 
70 static void initcg(uint32_t, time_t, const fsinfo_t *);
71 static int ilog2(int);
72 
73 static int count_digits(int);
74 
75 /*
76  * make file system for cylinder-group style file systems
77  */
78 #define	UMASK		0755
79 #define	POWEROF2(num)	(((num) & ((num) - 1)) == 0)
80 
81 static union {
82 	struct fs fs;
83 	char pad[SBLOCKSIZE];
84 } fsun;
85 #define	sblock	fsun.fs
86 
87 static union {
88 	struct cg cg;
89 	char pad[FFS_MAXBSIZE];
90 } cgun;
91 #define	acg	cgun.cg
92 
93 static char *iobuf;
94 static int iobufsize;
95 
96 static char writebuf[FFS_MAXBSIZE];
97 
98 static int     Oflag;	   /* format as an 4.3BSD file system */
99 static int64_t fssize;	   /* file system size */
100 static int     sectorsize;	   /* bytes/sector */
101 static int     fsize;	   /* fragment size */
102 static int     bsize;	   /* block size */
103 static int     maxbsize;   /* maximum clustering */
104 static int     maxblkspercg;
105 static int     minfree;	   /* free space threshold */
106 static int     opt;		   /* optimization preference (space or time) */
107 static int     density;	   /* number of bytes per inode */
108 static int     maxcontig;	   /* max contiguous blocks to allocate */
109 static int     maxbpg;	   /* maximum blocks per file in a cyl group */
110 static int     bbsize;	   /* boot block size */
111 static int     sbsize;	   /* superblock size */
112 static int     avgfilesize;	   /* expected average file size */
113 static int     avgfpdir;	   /* expected number of files per directory */
114 
115 struct fs *
116 ffs_mkfs(const char *fsys, const fsinfo_t *fsopts, time_t tstamp)
117 {
118 	int fragsperinode, optimalfpg, origdensity, minfpg, lastminfpg;
119 	int32_t csfrags;
120 	uint32_t i, cylno;
121 	long long sizepb;
122 	void *space;
123 	int size;
124 	int nprintcols, printcolwidth;
125 	ffs_opt_t	*ffs_opts = fsopts->fs_specific;
126 
127 	Oflag =		ffs_opts->version;
128 	fssize =        fsopts->size / fsopts->sectorsize;
129 	sectorsize =    fsopts->sectorsize;
130 	fsize =         ffs_opts->fsize;
131 	bsize =         ffs_opts->bsize;
132 	maxbsize =      ffs_opts->maxbsize;
133 	maxblkspercg =  ffs_opts->maxblkspercg;
134 	minfree =       ffs_opts->minfree;
135 	opt =           ffs_opts->optimization;
136 	density =       ffs_opts->density;
137 	maxcontig =     ffs_opts->maxcontig;
138 	maxbpg =        ffs_opts->maxbpg;
139 	avgfilesize =   ffs_opts->avgfilesize;
140 	avgfpdir =      ffs_opts->avgfpdir;
141 	bbsize =        BBSIZE;
142 	sbsize =        SBLOCKSIZE;
143 
144 	strlcpy(sblock.fs_volname, ffs_opts->label, sizeof(sblock.fs_volname));
145 
146 	if (Oflag == 0) {
147 		sblock.fs_old_inodefmt = FS_42INODEFMT;
148 		sblock.fs_maxsymlinklen = 0;
149 		sblock.fs_old_flags = 0;
150 	} else {
151 		sblock.fs_old_inodefmt = FS_44INODEFMT;
152 		sblock.fs_maxsymlinklen = (Oflag == 1 ? UFS1_MAXSYMLINKLEN :
153 		    UFS2_MAXSYMLINKLEN);
154 		sblock.fs_old_flags = FS_FLAGS_UPDATED;
155 		sblock.fs_flags = 0;
156 	}
157 	/*
158 	 * Validate the given file system size.
159 	 * Verify that its last block can actually be accessed.
160 	 * Convert to file system fragment sized units.
161 	 */
162 	if (fssize <= 0) {
163 		printf("preposterous size %lld\n", (long long)fssize);
164 		exit(13);
165 	}
166 	ffs_wtfs(fssize - 1, sectorsize, (char *)&sblock, fsopts);
167 
168 	/*
169 	 * collect and verify the filesystem density info
170 	 */
171 	sblock.fs_avgfilesize = avgfilesize;
172 	sblock.fs_avgfpdir = avgfpdir;
173 	if (sblock.fs_avgfilesize <= 0)
174 		printf("illegal expected average file size %d\n",
175 		    sblock.fs_avgfilesize), exit(14);
176 	if (sblock.fs_avgfpdir <= 0)
177 		printf("illegal expected number of files per directory %d\n",
178 		    sblock.fs_avgfpdir), exit(15);
179 	/*
180 	 * collect and verify the block and fragment sizes
181 	 */
182 	sblock.fs_bsize = bsize;
183 	sblock.fs_fsize = fsize;
184 	if (!POWEROF2(sblock.fs_bsize)) {
185 		printf("block size must be a power of 2, not %d\n",
186 		    sblock.fs_bsize);
187 		exit(16);
188 	}
189 	if (!POWEROF2(sblock.fs_fsize)) {
190 		printf("fragment size must be a power of 2, not %d\n",
191 		    sblock.fs_fsize);
192 		exit(17);
193 	}
194 	if (sblock.fs_fsize < sectorsize) {
195 		printf("fragment size %d is too small, minimum is %d\n",
196 		    sblock.fs_fsize, sectorsize);
197 		exit(18);
198 	}
199 	if (sblock.fs_bsize < MINBSIZE) {
200 		printf("block size %d is too small, minimum is %d\n",
201 		    sblock.fs_bsize, MINBSIZE);
202 		exit(19);
203 	}
204 	if (sblock.fs_bsize > FFS_MAXBSIZE) {
205 		printf("block size %d is too large, maximum is %d\n",
206 		    sblock.fs_bsize, FFS_MAXBSIZE);
207 		exit(19);
208 	}
209 	if (sblock.fs_bsize < sblock.fs_fsize) {
210 		printf("block size (%d) cannot be smaller than fragment size (%d)\n",
211 		    sblock.fs_bsize, sblock.fs_fsize);
212 		exit(20);
213 	}
214 
215 	if (maxbsize < bsize || !POWEROF2(maxbsize)) {
216 		sblock.fs_maxbsize = sblock.fs_bsize;
217 		printf("Extent size set to %d\n", sblock.fs_maxbsize);
218 	} else if (sblock.fs_maxbsize > FS_MAXCONTIG * sblock.fs_bsize) {
219 		sblock.fs_maxbsize = FS_MAXCONTIG * sblock.fs_bsize;
220 		printf("Extent size reduced to %d\n", sblock.fs_maxbsize);
221 	} else {
222 		sblock.fs_maxbsize = maxbsize;
223 	}
224 	sblock.fs_maxcontig = maxcontig;
225 	if (sblock.fs_maxcontig < sblock.fs_maxbsize / sblock.fs_bsize) {
226 		sblock.fs_maxcontig = sblock.fs_maxbsize / sblock.fs_bsize;
227 		printf("Maxcontig raised to %d\n", sblock.fs_maxbsize);
228 	}
229 
230 	if (sblock.fs_maxcontig > 1)
231 		sblock.fs_contigsumsize = MIN(sblock.fs_maxcontig,FS_MAXCONTIG);
232 
233 	sblock.fs_bmask = ~(sblock.fs_bsize - 1);
234 	sblock.fs_fmask = ~(sblock.fs_fsize - 1);
235 	sblock.fs_qbmask = ~sblock.fs_bmask;
236 	sblock.fs_qfmask = ~sblock.fs_fmask;
237 	for (sblock.fs_bshift = 0, i = sblock.fs_bsize; i > 1; i >>= 1)
238 		sblock.fs_bshift++;
239 	for (sblock.fs_fshift = 0, i = sblock.fs_fsize; i > 1; i >>= 1)
240 		sblock.fs_fshift++;
241 	sblock.fs_frag = numfrags(&sblock, sblock.fs_bsize);
242 	for (sblock.fs_fragshift = 0, i = sblock.fs_frag; i > 1; i >>= 1)
243 		sblock.fs_fragshift++;
244 	if (sblock.fs_frag > MAXFRAG) {
245 		printf("fragment size %d is too small, "
246 			"minimum with block size %d is %d\n",
247 		    sblock.fs_fsize, sblock.fs_bsize,
248 		    sblock.fs_bsize / MAXFRAG);
249 		exit(21);
250 	}
251 	sblock.fs_fsbtodb = ilog2(sblock.fs_fsize / sectorsize);
252 	sblock.fs_size = sblock.fs_providersize = fssize =
253 	    dbtofsb(&sblock, fssize);
254 
255 	if (Oflag <= 1) {
256 		sblock.fs_magic = FS_UFS1_MAGIC;
257 		sblock.fs_sblockloc = SBLOCK_UFS1;
258 		sblock.fs_nindir = sblock.fs_bsize / sizeof(ufs1_daddr_t);
259 		sblock.fs_inopb = sblock.fs_bsize / sizeof(struct ufs1_dinode);
260 		sblock.fs_maxsymlinklen = ((UFS_NDADDR + UFS_NIADDR) *
261 		    sizeof (ufs1_daddr_t));
262 		sblock.fs_old_inodefmt = FS_44INODEFMT;
263 		sblock.fs_old_cgoffset = 0;
264 		sblock.fs_old_cgmask = 0xffffffff;
265 		sblock.fs_old_size = sblock.fs_size;
266 		sblock.fs_old_rotdelay = 0;
267 		sblock.fs_old_rps = 60;
268 		sblock.fs_old_nspf = sblock.fs_fsize / sectorsize;
269 		sblock.fs_old_cpg = 1;
270 		sblock.fs_old_interleave = 1;
271 		sblock.fs_old_trackskew = 0;
272 		sblock.fs_old_cpc = 0;
273 		sblock.fs_old_postblformat = 1;
274 		sblock.fs_old_nrpos = 1;
275 	} else {
276 		sblock.fs_magic = FS_UFS2_MAGIC;
277 		sblock.fs_sblockloc = SBLOCK_UFS2;
278 		sblock.fs_nindir = sblock.fs_bsize / sizeof(ufs2_daddr_t);
279 		sblock.fs_inopb = sblock.fs_bsize / sizeof(struct ufs2_dinode);
280 		sblock.fs_maxsymlinklen = ((UFS_NDADDR + UFS_NIADDR) *
281 		    sizeof (ufs2_daddr_t));
282 		if (ffs_opts->softupdates == 1)
283 			sblock.fs_flags |= FS_DOSOFTDEP;
284 	}
285 
286 	sblock.fs_sblkno =
287 	    roundup(howmany(sblock.fs_sblockloc + SBLOCKSIZE, sblock.fs_fsize),
288 		sblock.fs_frag);
289 	sblock.fs_cblkno = (daddr_t)(sblock.fs_sblkno +
290 	    roundup(howmany(SBLOCKSIZE, sblock.fs_fsize), sblock.fs_frag));
291 	sblock.fs_iblkno = sblock.fs_cblkno + sblock.fs_frag;
292 	sblock.fs_maxfilesize = sblock.fs_bsize * UFS_NDADDR - 1;
293 	for (sizepb = sblock.fs_bsize, i = 0; i < UFS_NIADDR; i++) {
294 		sizepb *= NINDIR(&sblock);
295 		sblock.fs_maxfilesize += sizepb;
296 	}
297 
298 	/*
299 	 * Calculate the number of blocks to put into each cylinder group.
300 	 *
301 	 * This algorithm selects the number of blocks per cylinder
302 	 * group. The first goal is to have at least enough data blocks
303 	 * in each cylinder group to meet the density requirement. Once
304 	 * this goal is achieved we try to expand to have at least
305 	 * 1 cylinder group. Once this goal is achieved, we pack as
306 	 * many blocks into each cylinder group map as will fit.
307 	 *
308 	 * We start by calculating the smallest number of blocks that we
309 	 * can put into each cylinder group. If this is too big, we reduce
310 	 * the density until it fits.
311 	 */
312 	origdensity = density;
313 	for (;;) {
314 		fragsperinode = MAX(numfrags(&sblock, density), 1);
315 		minfpg = fragsperinode * INOPB(&sblock);
316 		if (minfpg > sblock.fs_size)
317 			minfpg = sblock.fs_size;
318 		sblock.fs_ipg = INOPB(&sblock);
319 		sblock.fs_fpg = roundup(sblock.fs_iblkno +
320 		    sblock.fs_ipg / INOPF(&sblock), sblock.fs_frag);
321 		if (sblock.fs_fpg < minfpg)
322 			sblock.fs_fpg = minfpg;
323 		sblock.fs_ipg = roundup(howmany(sblock.fs_fpg, fragsperinode),
324 		    INOPB(&sblock));
325 		sblock.fs_fpg = roundup(sblock.fs_iblkno +
326 		    sblock.fs_ipg / INOPF(&sblock), sblock.fs_frag);
327 		if (sblock.fs_fpg < minfpg)
328 			sblock.fs_fpg = minfpg;
329 		sblock.fs_ipg = roundup(howmany(sblock.fs_fpg, fragsperinode),
330 		    INOPB(&sblock));
331 		if (CGSIZE(&sblock) < (unsigned long)sblock.fs_bsize)
332 			break;
333 		density -= sblock.fs_fsize;
334 	}
335 	if (density != origdensity)
336 		printf("density reduced from %d to %d\n", origdensity, density);
337 
338 	if (maxblkspercg <= 0 || maxblkspercg >= fssize)
339 		maxblkspercg = fssize - 1;
340 	/*
341 	 * Start packing more blocks into the cylinder group until
342 	 * it cannot grow any larger, the number of cylinder groups
343 	 * drops below 1, or we reach the size requested.
344 	 */
345 	for ( ; sblock.fs_fpg < maxblkspercg; sblock.fs_fpg += sblock.fs_frag) {
346 		sblock.fs_ipg = roundup(howmany(sblock.fs_fpg, fragsperinode),
347 		    INOPB(&sblock));
348 		if (sblock.fs_size / sblock.fs_fpg < 1)
349 			break;
350 		if (CGSIZE(&sblock) < (unsigned long)sblock.fs_bsize)
351 			continue;
352 		if (CGSIZE(&sblock) == (unsigned long)sblock.fs_bsize)
353 			break;
354 		sblock.fs_fpg -= sblock.fs_frag;
355 		sblock.fs_ipg = roundup(howmany(sblock.fs_fpg, fragsperinode),
356 		    INOPB(&sblock));
357 		break;
358 	}
359 	/*
360 	 * Check to be sure that the last cylinder group has enough blocks
361 	 * to be viable. If it is too small, reduce the number of blocks
362 	 * per cylinder group which will have the effect of moving more
363 	 * blocks into the last cylinder group.
364 	 */
365 	optimalfpg = sblock.fs_fpg;
366 	for (;;) {
367 		sblock.fs_ncg = howmany(sblock.fs_size, sblock.fs_fpg);
368 		lastminfpg = roundup(sblock.fs_iblkno +
369 		    sblock.fs_ipg / INOPF(&sblock), sblock.fs_frag);
370 		if (sblock.fs_size < lastminfpg) {
371 			printf("Filesystem size %lld < minimum size of %d\n",
372 			    (long long)sblock.fs_size, lastminfpg);
373 			exit(28);
374 		}
375 		if (sblock.fs_size % sblock.fs_fpg >= lastminfpg ||
376 		    sblock.fs_size % sblock.fs_fpg == 0)
377 			break;
378 		sblock.fs_fpg -= sblock.fs_frag;
379 		sblock.fs_ipg = roundup(howmany(sblock.fs_fpg, fragsperinode),
380 		    INOPB(&sblock));
381 	}
382 	if (optimalfpg != sblock.fs_fpg)
383 		printf("Reduced frags per cylinder group from %d to %d %s\n",
384 		   optimalfpg, sblock.fs_fpg, "to enlarge last cyl group");
385 	sblock.fs_cgsize = fragroundup(&sblock, CGSIZE(&sblock));
386 	sblock.fs_dblkno = sblock.fs_iblkno + sblock.fs_ipg / INOPF(&sblock);
387 	if (Oflag <= 1) {
388 		sblock.fs_old_spc = sblock.fs_fpg * sblock.fs_old_nspf;
389 		sblock.fs_old_nsect = sblock.fs_old_spc;
390 		sblock.fs_old_npsect = sblock.fs_old_spc;
391 		sblock.fs_old_ncyl = sblock.fs_ncg;
392 	}
393 
394 	/*
395 	 * fill in remaining fields of the super block
396 	 */
397 	sblock.fs_csaddr = cgdmin(&sblock, 0);
398 	sblock.fs_cssize =
399 	    fragroundup(&sblock, sblock.fs_ncg * sizeof(struct csum));
400 
401 	/*
402 	 * Setup memory for temporary in-core cylgroup summaries.
403 	 * Cribbed from ffs_mountfs().
404 	 */
405 	size = sblock.fs_cssize;
406 	if (sblock.fs_contigsumsize > 0)
407 		size += sblock.fs_ncg * sizeof(int32_t);
408 	space = ecalloc(1, size);
409 	sblock.fs_csp = space;
410 	space = (char *)space + sblock.fs_cssize;
411 	if (sblock.fs_contigsumsize > 0) {
412 		int32_t *lp;
413 
414 		sblock.fs_maxcluster = lp = space;
415 		for (i = 0; i < sblock.fs_ncg; i++)
416 		*lp++ = sblock.fs_contigsumsize;
417 	}
418 
419 	sblock.fs_sbsize = fragroundup(&sblock, sizeof(struct fs));
420 	if (sblock.fs_sbsize > SBLOCKSIZE)
421 		sblock.fs_sbsize = SBLOCKSIZE;
422 	sblock.fs_minfree = minfree;
423 	sblock.fs_maxcontig = maxcontig;
424 	sblock.fs_maxbpg = maxbpg;
425 	sblock.fs_optim = opt;
426 	sblock.fs_cgrotor = 0;
427 	sblock.fs_pendingblocks = 0;
428 	sblock.fs_pendinginodes = 0;
429 	sblock.fs_cstotal.cs_ndir = 0;
430 	sblock.fs_cstotal.cs_nbfree = 0;
431 	sblock.fs_cstotal.cs_nifree = 0;
432 	sblock.fs_cstotal.cs_nffree = 0;
433 	sblock.fs_fmod = 0;
434 	sblock.fs_ronly = 0;
435 	sblock.fs_state = 0;
436 	sblock.fs_clean = FS_ISCLEAN;
437 	sblock.fs_ronly = 0;
438 	sblock.fs_id[0] = tstamp;
439 	sblock.fs_id[1] = random();
440 	sblock.fs_fsmnt[0] = '\0';
441 	csfrags = howmany(sblock.fs_cssize, sblock.fs_fsize);
442 	sblock.fs_dsize = sblock.fs_size - sblock.fs_sblkno -
443 	    sblock.fs_ncg * (sblock.fs_dblkno - sblock.fs_sblkno);
444 	sblock.fs_cstotal.cs_nbfree =
445 	    fragstoblks(&sblock, sblock.fs_dsize) -
446 	    howmany(csfrags, sblock.fs_frag);
447 	sblock.fs_cstotal.cs_nffree =
448 	    fragnum(&sblock, sblock.fs_size) +
449 	    (fragnum(&sblock, csfrags) > 0 ?
450 	    sblock.fs_frag - fragnum(&sblock, csfrags) : 0);
451 	sblock.fs_cstotal.cs_nifree =
452 	    sblock.fs_ncg * sblock.fs_ipg - UFS_ROOTINO;
453 	sblock.fs_cstotal.cs_ndir = 0;
454 	sblock.fs_dsize -= csfrags;
455 	sblock.fs_time = tstamp;
456 	if (Oflag <= 1) {
457 		sblock.fs_old_time = tstamp;
458 		sblock.fs_old_dsize = sblock.fs_dsize;
459 		sblock.fs_old_csaddr = sblock.fs_csaddr;
460 		sblock.fs_old_cstotal.cs_ndir = sblock.fs_cstotal.cs_ndir;
461 		sblock.fs_old_cstotal.cs_nbfree = sblock.fs_cstotal.cs_nbfree;
462 		sblock.fs_old_cstotal.cs_nifree = sblock.fs_cstotal.cs_nifree;
463 		sblock.fs_old_cstotal.cs_nffree = sblock.fs_cstotal.cs_nffree;
464 	}
465 	/*
466 	 * Dump out summary information about file system.
467 	 */
468 #define	B2MBFACTOR (1 / (1024.0 * 1024.0))
469 	printf("%s: %.1fMB (%lld sectors) block size %d, "
470 	       "fragment size %d\n",
471 	    fsys, (float)sblock.fs_size * sblock.fs_fsize * B2MBFACTOR,
472 	    (long long)fsbtodb(&sblock, sblock.fs_size),
473 	    sblock.fs_bsize, sblock.fs_fsize);
474 	printf("\tusing %d cylinder groups of %.2fMB, %d blks, "
475 	       "%d inodes.\n",
476 	    sblock.fs_ncg,
477 	    (float)sblock.fs_fpg * sblock.fs_fsize * B2MBFACTOR,
478 	    sblock.fs_fpg / sblock.fs_frag, sblock.fs_ipg);
479 #undef B2MBFACTOR
480 	/*
481 	 * Now determine how wide each column will be, and calculate how
482 	 * many columns will fit in a 76 char line. 76 is the width of the
483 	 * subwindows in sysinst.
484 	 */
485 	printcolwidth = count_digits(
486 			fsbtodb(&sblock, cgsblock(&sblock, sblock.fs_ncg -1)));
487 	nprintcols = 76 / (printcolwidth + 2);
488 
489 	/*
490 	 * allocate space for superblock, cylinder group map, and
491 	 * two sets of inode blocks.
492 	 */
493 	if (sblock.fs_bsize < SBLOCKSIZE)
494 		iobufsize = SBLOCKSIZE + 3 * sblock.fs_bsize;
495 	else
496 		iobufsize = 4 * sblock.fs_bsize;
497 	iobuf = ecalloc(1, iobufsize);
498 	/*
499 	 * Make a copy of the superblock into the buffer that we will be
500 	 * writing out in each cylinder group.
501 	 */
502 	memcpy(writebuf, &sblock, sbsize);
503 	if (fsopts->needswap)
504 		ffs_sb_swap(&sblock, (struct fs*)writebuf);
505 	memcpy(iobuf, writebuf, SBLOCKSIZE);
506 
507 	printf("super-block backups (for fsck -b #) at:");
508 	for (cylno = 0; cylno < sblock.fs_ncg; cylno++) {
509 		initcg(cylno, tstamp, fsopts);
510 		if (cylno % nprintcols == 0)
511 			printf("\n");
512 		printf(" %*lld,", printcolwidth,
513 			(long long)fsbtodb(&sblock, cgsblock(&sblock, cylno)));
514 		fflush(stdout);
515 	}
516 	printf("\n");
517 
518 	/*
519 	 * Now construct the initial file system,
520 	 * then write out the super-block.
521 	 */
522 	sblock.fs_time = tstamp;
523 	if (Oflag <= 1) {
524 		sblock.fs_old_cstotal.cs_ndir = sblock.fs_cstotal.cs_ndir;
525 		sblock.fs_old_cstotal.cs_nbfree = sblock.fs_cstotal.cs_nbfree;
526 		sblock.fs_old_cstotal.cs_nifree = sblock.fs_cstotal.cs_nifree;
527 		sblock.fs_old_cstotal.cs_nffree = sblock.fs_cstotal.cs_nffree;
528 	}
529 	if (fsopts->needswap)
530 		sblock.fs_flags |= FS_SWAPPED;
531 	ffs_write_superblock(&sblock, fsopts);
532 	return (&sblock);
533 }
534 
535 /*
536  * Write out the superblock and its duplicates,
537  * and the cylinder group summaries
538  */
539 void
540 ffs_write_superblock(struct fs *fs, const fsinfo_t *fsopts)
541 {
542 	int size, blks, i, saveflag;
543 	uint32_t cylno;
544 	void *space;
545 	char *wrbuf;
546 
547 	saveflag = fs->fs_flags & FS_INTERNAL;
548 	fs->fs_flags &= ~FS_INTERNAL;
549 
550         memcpy(writebuf, &sblock, sbsize);
551 	if (fsopts->needswap)
552 		ffs_sb_swap(fs, (struct fs*)writebuf);
553 	ffs_wtfs(fs->fs_sblockloc / sectorsize, sbsize, writebuf, fsopts);
554 
555 	/* Write out the duplicate super blocks */
556 	for (cylno = 0; cylno < fs->fs_ncg; cylno++)
557 		ffs_wtfs(fsbtodb(fs, cgsblock(fs, cylno)),
558 		    sbsize, writebuf, fsopts);
559 
560 	/* Write out the cylinder group summaries */
561 	size = fs->fs_cssize;
562 	blks = howmany(size, fs->fs_fsize);
563 	space = (void *)fs->fs_csp;
564 	wrbuf = emalloc(size);
565 	for (i = 0; i < blks; i+= fs->fs_frag) {
566 		size = fs->fs_bsize;
567 		if (i + fs->fs_frag > blks)
568 			size = (blks - i) * fs->fs_fsize;
569 		if (fsopts->needswap)
570 			ffs_csum_swap((struct csum *)space,
571 			    (struct csum *)wrbuf, size);
572 		else
573 			memcpy(wrbuf, space, (u_int)size);
574 		ffs_wtfs(fsbtodb(fs, fs->fs_csaddr + i), size, wrbuf, fsopts);
575 		space = (char *)space + size;
576 	}
577 	free(wrbuf);
578 	fs->fs_flags |= saveflag;
579 }
580 
581 /*
582  * Initialize a cylinder group.
583  */
584 static void
585 initcg(uint32_t cylno, time_t utime, const fsinfo_t *fsopts)
586 {
587 	daddr_t cbase, dmax;
588 	int32_t blkno;
589 	uint32_t i, j, d, dlower, dupper;
590 	struct ufs1_dinode *dp1;
591 	struct ufs2_dinode *dp2;
592 	int start;
593 
594 	/*
595 	 * Determine block bounds for cylinder group.
596 	 * Allow space for super block summary information in first
597 	 * cylinder group.
598 	 */
599 	cbase = cgbase(&sblock, cylno);
600 	dmax = cbase + sblock.fs_fpg;
601 	if (dmax > sblock.fs_size)
602 		dmax = sblock.fs_size;
603 	dlower = cgsblock(&sblock, cylno) - cbase;
604 	dupper = cgdmin(&sblock, cylno) - cbase;
605 	if (cylno == 0)
606 		dupper += howmany(sblock.fs_cssize, sblock.fs_fsize);
607 	memset(&acg, 0, sblock.fs_cgsize);
608 	acg.cg_time = utime;
609 	acg.cg_magic = CG_MAGIC;
610 	acg.cg_cgx = cylno;
611 	acg.cg_niblk = sblock.fs_ipg;
612 	acg.cg_initediblk = MIN(sblock.fs_ipg, 2 * INOPB(&sblock));
613 	acg.cg_ndblk = dmax - cbase;
614 	if (sblock.fs_contigsumsize > 0)
615 		acg.cg_nclusterblks = acg.cg_ndblk >> sblock.fs_fragshift;
616 	start = &acg.cg_space[0] - (u_char *)(&acg.cg_firstfield);
617 	if (Oflag == 2) {
618 		acg.cg_iusedoff = start;
619 	} else {
620 		if (cylno == sblock.fs_ncg - 1)
621 			acg.cg_old_ncyl = howmany(acg.cg_ndblk,
622 			    sblock.fs_fpg / sblock.fs_old_cpg);
623 		else
624 			acg.cg_old_ncyl = sblock.fs_old_cpg;
625 		acg.cg_old_time = acg.cg_time;
626 		acg.cg_time = 0;
627 		acg.cg_old_niblk = acg.cg_niblk;
628 		acg.cg_niblk = 0;
629 		acg.cg_initediblk = 0;
630 		acg.cg_old_btotoff = start;
631 		acg.cg_old_boff = acg.cg_old_btotoff +
632 		    sblock.fs_old_cpg * sizeof(int32_t);
633 		acg.cg_iusedoff = acg.cg_old_boff +
634 		    sblock.fs_old_cpg * sizeof(u_int16_t);
635 	}
636 	acg.cg_freeoff = acg.cg_iusedoff + howmany(sblock.fs_ipg, CHAR_BIT);
637 	if (sblock.fs_contigsumsize <= 0) {
638 		acg.cg_nextfreeoff = acg.cg_freeoff +
639 		   howmany(sblock.fs_fpg, CHAR_BIT);
640 	} else {
641 		acg.cg_clustersumoff = acg.cg_freeoff +
642 		    howmany(sblock.fs_fpg, CHAR_BIT) - sizeof(int32_t);
643 		acg.cg_clustersumoff =
644 		    roundup(acg.cg_clustersumoff, sizeof(int32_t));
645 		acg.cg_clusteroff = acg.cg_clustersumoff +
646 		    (sblock.fs_contigsumsize + 1) * sizeof(int32_t);
647 		acg.cg_nextfreeoff = acg.cg_clusteroff +
648 		    howmany(fragstoblks(&sblock, sblock.fs_fpg), CHAR_BIT);
649 	}
650 	if (acg.cg_nextfreeoff > (uint32_t)sblock.fs_cgsize) {
651 		printf("Panic: cylinder group too big\n");
652 		exit(37);
653 	}
654 	acg.cg_cs.cs_nifree += sblock.fs_ipg;
655 	if (cylno == 0)
656 		for (i = 0; i < UFS_ROOTINO; i++) {
657 			setbit(cg_inosused_swap(&acg, 0), i);
658 			acg.cg_cs.cs_nifree--;
659 		}
660 	if (cylno > 0) {
661 		/*
662 		 * In cylno 0, beginning space is reserved
663 		 * for boot and super blocks.
664 		 */
665 		for (d = 0, blkno = 0; d < dlower;) {
666 			ffs_setblock(&sblock, cg_blksfree_swap(&acg, 0), blkno);
667 			if (sblock.fs_contigsumsize > 0)
668 				setbit(cg_clustersfree_swap(&acg, 0), blkno);
669 			acg.cg_cs.cs_nbfree++;
670 			d += sblock.fs_frag;
671 			blkno++;
672 		}
673 	}
674 	if ((i = (dupper & (sblock.fs_frag - 1))) != 0) {
675 		acg.cg_frsum[sblock.fs_frag - i]++;
676 		for (d = dupper + sblock.fs_frag - i; dupper < d; dupper++) {
677 			setbit(cg_blksfree_swap(&acg, 0), dupper);
678 			acg.cg_cs.cs_nffree++;
679 		}
680 	}
681 	for (d = dupper, blkno = dupper >> sblock.fs_fragshift;
682 	     d + sblock.fs_frag <= acg.cg_ndblk; ) {
683 		ffs_setblock(&sblock, cg_blksfree_swap(&acg, 0), blkno);
684 		if (sblock.fs_contigsumsize > 0)
685 			setbit(cg_clustersfree_swap(&acg, 0), blkno);
686 		acg.cg_cs.cs_nbfree++;
687 		d += sblock.fs_frag;
688 		blkno++;
689 	}
690 	if (d < acg.cg_ndblk) {
691 		acg.cg_frsum[acg.cg_ndblk - d]++;
692 		for (; d < acg.cg_ndblk; d++) {
693 			setbit(cg_blksfree_swap(&acg, 0), d);
694 			acg.cg_cs.cs_nffree++;
695 		}
696 	}
697 	if (sblock.fs_contigsumsize > 0) {
698 		int32_t *sump = cg_clustersum_swap(&acg, 0);
699 		u_char *mapp = cg_clustersfree_swap(&acg, 0);
700 		int map = *mapp++;
701 		int bit = 1;
702 		int run = 0;
703 
704 		for (i = 0; i < acg.cg_nclusterblks; i++) {
705 			if ((map & bit) != 0) {
706 				run++;
707 			} else if (run != 0) {
708 				if (run > sblock.fs_contigsumsize)
709 					run = sblock.fs_contigsumsize;
710 				sump[run]++;
711 				run = 0;
712 			}
713 			if ((i & (CHAR_BIT - 1)) != (CHAR_BIT - 1)) {
714 				bit <<= 1;
715 			} else {
716 				map = *mapp++;
717 				bit = 1;
718 			}
719 		}
720 		if (run != 0) {
721 			if (run > sblock.fs_contigsumsize)
722 				run = sblock.fs_contigsumsize;
723 			sump[run]++;
724 		}
725 	}
726 	sblock.fs_cs(&sblock, cylno) = acg.cg_cs;
727 	/*
728 	 * Write out the duplicate super block, the cylinder group map
729 	 * and two blocks worth of inodes in a single write.
730 	 */
731 	start = MAX(sblock.fs_bsize, SBLOCKSIZE);
732 	memcpy(&iobuf[start], &acg, sblock.fs_cgsize);
733 	if (fsopts->needswap)
734 		ffs_cg_swap(&acg, (struct cg*)&iobuf[start], &sblock);
735 	start += sblock.fs_bsize;
736 	dp1 = (struct ufs1_dinode *)(&iobuf[start]);
737 	dp2 = (struct ufs2_dinode *)(&iobuf[start]);
738 	for (i = 0; i < acg.cg_initediblk; i++) {
739 		if (sblock.fs_magic == FS_UFS1_MAGIC) {
740 			/* No need to swap, it'll stay random */
741 			dp1->di_gen = random();
742 			dp1++;
743 		} else {
744 			dp2->di_gen = random();
745 			dp2++;
746 		}
747 	}
748 	ffs_wtfs(fsbtodb(&sblock, cgsblock(&sblock, cylno)), iobufsize, iobuf,
749 	    fsopts);
750 	/*
751 	 * For the old file system, we have to initialize all the inodes.
752 	 */
753 	if (Oflag <= 1) {
754 		for (i = 2 * sblock.fs_frag;
755 		     i < sblock.fs_ipg / INOPF(&sblock);
756 		     i += sblock.fs_frag) {
757 			dp1 = (struct ufs1_dinode *)(&iobuf[start]);
758 			for (j = 0; j < INOPB(&sblock); j++) {
759 				dp1->di_gen = random();
760 				dp1++;
761 			}
762 			ffs_wtfs(fsbtodb(&sblock, cgimin(&sblock, cylno) + i),
763 			    sblock.fs_bsize, &iobuf[start], fsopts);
764 		}
765 	}
766 }
767 
768 /*
769  * read a block from the file system
770  */
771 void
772 ffs_rdfs(daddr_t bno, int size, void *bf, const fsinfo_t *fsopts)
773 {
774 	int n;
775 	off_t offset;
776 
777 	offset = bno * fsopts->sectorsize + fsopts->offset;
778 	if (lseek(fsopts->fd, offset, SEEK_SET) < 0)
779 		err(1, "%s: seek error for sector %lld", __func__,
780 		    (long long)bno);
781 	n = read(fsopts->fd, bf, size);
782 	if (n == -1) {
783 		abort();
784 		err(1, "%s: read error bno %lld size %d", __func__,
785 		    (long long)bno, size);
786 	}
787 	else if (n != size)
788 		errx(1, "%s: read error for sector %lld", __func__,
789 		    (long long)bno);
790 }
791 
792 /*
793  * write a block to the file system
794  */
795 void
796 ffs_wtfs(daddr_t bno, int size, void *bf, const fsinfo_t *fsopts)
797 {
798 	int n;
799 	off_t offset;
800 
801 	offset = bno * fsopts->sectorsize + fsopts->offset;
802 	if (lseek(fsopts->fd, offset, SEEK_SET) < 0)
803 		err(1, "%s: seek error for sector %lld", __func__,
804 		    (long long)bno);
805 	n = write(fsopts->fd, bf, size);
806 	if (n == -1)
807 		err(1, "%s: write error for sector %lld", __func__,
808 		    (long long)bno);
809 	else if (n != size)
810 		errx(1, "%s: write error for sector %lld", __func__,
811 		    (long long)bno);
812 }
813 
814 
815 /* Determine how many digits are needed to print a given integer */
816 static int
817 count_digits(int num)
818 {
819 	int ndig;
820 
821 	for(ndig = 1; num > 9; num /=10, ndig++);
822 
823 	return (ndig);
824 }
825 
826 static int
827 ilog2(int val)
828 {
829 	u_int n;
830 
831 	for (n = 0; n < sizeof(n) * CHAR_BIT; n++)
832 		if (1 << n == val)
833 			return (n);
834 	errx(1, "%s: %d is not a power of 2", __func__, val);
835 }
836