sbin/newfs/mkfs.c

   1 /*
   2  * Copyright (c) 1980, 1989, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by the University of
  16  *      California, Berkeley and its contributors.
  17  * 4. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 #ifndef lint
  35 #if 0
  36 static char sccsid[] = "@(#)mkfs.c      8.11 (Berkeley) 5/3/95";
  37 #endif
  38 static const char rcsid[] =
  39   "$FreeBSD$";
  40 #endif /* not lint */
  41
  42 #include <err.h>
  43 #include <signal.h>
  44 #include <stdlib.h>
  45 #include <string.h>
  46 #include <stdio.h>
  47 #include <unistd.h>
  48 #include <sys/param.h>
  49 #include <sys/time.h>
  50 #include <sys/types.h>
  51 #include <sys/wait.h>
  52 #include <sys/resource.h>
  53 #include <sys/stat.h>
  54 #include <ufs/ufs/dinode.h>
  55 #include <ufs/ufs/dir.h>
  56 #include <ufs/ffs/fs.h>
  57 #include <sys/disklabel.h>
  58 #include <sys/file.h>
  59 #include <sys/mman.h>
  60 #include <sys/ioctl.h>
  61 #include "newfs.h"
  62
  63 /*
  64  * make filesystem for cylinder-group style filesystems
  65  */
  66
  67 /*
  68  * We limit the size of the inode map to be no more than a
  69  * third of the cylinder group space, since we must leave at
  70  * least an equal amount of space for the block map.
  71  *
  72  * N.B.: MAXIPG must be a multiple of INOPB(fs).
  73  */
  74 #define MAXIPG(fs)      roundup((fs)->fs_bsize * NBBY / 3, INOPB(fs))
  75
  76 #define UMASK           0755
  77 #define MAXINOPB        (MAXBSIZE / sizeof(struct dinode))
  78 #define POWEROF2(num)   (((num) & ((num) - 1)) == 0)
  79
  80 static union {
  81         struct fs fs;
  82         char pad[SBSIZE];
  83 } fsun;
  84 #define sblock  fsun.fs
  85 static struct   csum *fscs;
  86
  87 static union {
  88         struct cg cg;
  89         char pad[MAXBSIZE];
  90 } cgun;
  91 #define acg     cgun.cg
  92
  93 static struct dinode zino[MAXBSIZE / sizeof(struct dinode)];
  94
  95 static int randinit;
  96 static daddr_t alloc(int size, int mode);
  97 static long calcipg(long lcpg, long bpcg, off_t *usedbp);
  98 static int charsperline(void);
  99 static void clrblock(struct fs *, unsigned char *, int);
 100 static void fsinit(time_t);
 101 static int ilog2(int);
 102 static void initcg(int, time_t);
 103 static int isblock(struct fs *, unsigned char *, int);
 104 static void iput(struct dinode *, ino_t);
 105 static int makedir(struct direct *, int);
 106 static void rdfs(daddr_t, int, char *);
 107 static void setblock(struct fs *, unsigned char *, int);
 108 static void wtfs(daddr_t, int, char *);
 109 static void wtfsflush(void);
 110
 111 void
 112 mkfs(struct partition *pp, char *fsys)
 113 {
 114         long i, mincpc, mincpg, inospercg;
 115         long cylno, j, lwarn = 0;
 116         long used, mincpgcnt, bpcg;
 117         off_t usedb;
 118         long mapcramped, inodecramped;
 119         time_t utime;
 120         quad_t sizepb;
 121         int width;
 122         char tmpbuf[100];       /* XXX this will break in about 2,500 years */
 123
 124         if (Rflag)
 125                 utime = 1000000000;
 126         else
 127                 time(&utime);
 128         if (!Rflag && !randinit) {
 129                 randinit = 1;
 130                 srandomdev();
 131         }
 132         sblock.fs_inodefmt = FS_44INODEFMT;
 133         sblock.fs_maxsymlinklen = MAXSYMLINKLEN;
 134         if (Uflag)
 135                 sblock.fs_flags |= FS_DOSOFTDEP;
 136         /*
 137          * Validate the given filesystem size.
 138          * Verify that its last block can actually be accessed.
 139          */
 140         if (fssize <= 0)
 141                 printf("preposterous size %d\n", fssize), exit(13);
 142         wtfs(fssize - (realsectorsize / DEV_BSIZE), realsectorsize,
 143             (char *)&sblock);
 144         /*
 145          * collect and verify the sector and track info
 146          */
 147         sblock.fs_nsect = secpercyl;
 148         sblock.fs_ntrak = 1;
 149         if (sblock.fs_nsect <= 0)
 150                 printf("preposterous nsect %d\n", sblock.fs_nsect), exit(15);
 151         /*
 152          * collect and verify the filesystem density info
 153          */
 154         sblock.fs_avgfilesize = avgfilesize;
 155         sblock.fs_avgfpdir = avgfilesperdir;
 156         if (sblock.fs_avgfilesize <= 0)
 157                 printf("illegal expected average file size %d\n",
 158                     sblock.fs_avgfilesize), exit(14);
 159         if (sblock.fs_avgfpdir <= 0)
 160                 printf("illegal expected number of files per directory %d\n",
 161                     sblock.fs_avgfpdir), exit(15);
 162         /*
 163          * collect and verify the block and fragment sizes
 164          */
 165         sblock.fs_bsize = bsize;
 166         sblock.fs_fsize = fsize;
 167         if (!POWEROF2(sblock.fs_bsize)) {
 168                 printf("block size must be a power of 2, not %d\n",
 169                     sblock.fs_bsize);
 170                 exit(16);
 171         }
 172         if (!POWEROF2(sblock.fs_fsize)) {
 173                 printf("fragment size must be a power of 2, not %d\n",
 174                     sblock.fs_fsize);
 175                 exit(17);
 176         }
 177         if (sblock.fs_fsize < sectorsize) {
 178                 printf("increasing fragment size from %d to sector size (%d)\n",
 179                     sblock.fs_fsize, sectorsize);
 180                 sblock.fs_fsize = sectorsize;
 181         }
 182         if (sblock.fs_bsize < MINBSIZE) {
 183                 printf("increasing block size from %d to minimum (%d)\n",
 184                     sblock.fs_bsize, MINBSIZE);
 185                 sblock.fs_bsize = MINBSIZE;
 186         }
 187         if (sblock.fs_bsize < sblock.fs_fsize) {
 188                 printf("increasing block size from %d to fragment size (%d)\n",
 189                     sblock.fs_bsize, sblock.fs_fsize);
 190                 sblock.fs_bsize = sblock.fs_fsize;
 191         }
 192         if (sblock.fs_fsize * MAXFRAG < sblock.fs_bsize) {
 193                 printf(
 194                 "increasing fragment size from %d to block size / %d (%d)\n",
 195                     sblock.fs_fsize, MAXFRAG, sblock.fs_bsize / MAXFRAG);
 196                 sblock.fs_fsize = sblock.fs_bsize / MAXFRAG;
 197         }
 198         sblock.fs_bmask = ~(sblock.fs_bsize - 1);
 199         sblock.fs_fmask = ~(sblock.fs_fsize - 1);
 200         sblock.fs_qbmask = ~sblock.fs_bmask;
 201         sblock.fs_qfmask = ~sblock.fs_fmask;
 202         sblock.fs_bshift = ilog2(sblock.fs_bsize);
 203         sblock.fs_fshift = ilog2(sblock.fs_fsize);
 204         sblock.fs_frag = numfrags(&sblock, sblock.fs_bsize);
 205         sblock.fs_fragshift = ilog2(sblock.fs_frag);
 206         if (sblock.fs_frag > MAXFRAG) {
 207                 printf("fragment size %d is still too small (can't happen)\n",
 208                     sblock.fs_bsize / MAXFRAG);
 209                 exit(21);
 210         }
 211         sblock.fs_nrpos = 1;
 212         sblock.fs_nindir = sblock.fs_bsize / sizeof(daddr_t);
 213         sblock.fs_inopb = sblock.fs_bsize / sizeof(struct dinode);
 214         sblock.fs_nspf = sblock.fs_fsize / sectorsize;
 215         sblock.fs_fsbtodb = ilog2(NSPF(&sblock));
 216         sblock.fs_sblkno =
 217             roundup(howmany(BBSIZE + SBSIZE, sblock.fs_fsize), sblock.fs_frag);
 218         sblock.fs_cblkno = (daddr_t)(sblock.fs_sblkno +
 219             roundup(howmany(SBSIZE, sblock.fs_fsize), sblock.fs_frag));
 220         sblock.fs_iblkno = sblock.fs_cblkno + sblock.fs_frag;
 221         sblock.fs_cgoffset =
 222             roundup(howmany(sblock.fs_nsect, NSPF(&sblock)), sblock.fs_frag);
 223         sblock.fs_cgmask = 0xffffffff;
 224         sblock.fs_maxfilesize = sblock.fs_bsize * NDADDR - 1;
 225         for (sizepb = sblock.fs_bsize, i = 0; i < NIADDR; i++) {
 226                 sizepb *= NINDIR(&sblock);
 227                 sblock.fs_maxfilesize += sizepb;
 228         }
 229         /*
 230          * Validate specified/determined secpercyl
 231          * and calculate minimum cylinders per group.
 232          */
 233         sblock.fs_spc = secpercyl;
 234         for (sblock.fs_cpc = NSPB(&sblock), i = sblock.fs_spc;
 235              sblock.fs_cpc > 1 && (i & 1) == 0;
 236              sblock.fs_cpc >>= 1, i >>= 1)
 237                 /* void */;
 238         mincpc = sblock.fs_cpc;
 239         bpcg = sblock.fs_spc * sectorsize;
 240         inospercg = roundup(bpcg / sizeof(struct dinode), INOPB(&sblock));
 241         if (inospercg > MAXIPG(&sblock))
 242                 inospercg = MAXIPG(&sblock);
 243         used = (sblock.fs_iblkno + inospercg / INOPF(&sblock)) * NSPF(&sblock);
 244         mincpgcnt = howmany(sblock.fs_cgoffset * (~sblock.fs_cgmask) + used,
 245             sblock.fs_spc);
 246         mincpg = roundup(mincpgcnt, mincpc);
 247         /*
 248          * Ensure that cylinder group with mincpg has enough space
 249          * for block maps.
 250          */
 251         sblock.fs_cpg = mincpg;
 252         sblock.fs_ipg = inospercg;
 253         if (maxcontig > 1)
 254                 sblock.fs_contigsumsize = MIN(maxcontig, FS_MAXCONTIG);
 255         mapcramped = 0;
 256         while (CGSIZE(&sblock) > sblock.fs_bsize) {
 257                 mapcramped = 1;
 258                 if (sblock.fs_bsize < MAXBSIZE) {
 259                         sblock.fs_bsize <<= 1;
 260                         if ((i & 1) == 0)
 261                                 i >>= 1;
 262                         else {
 263                                 sblock.fs_cpc <<= 1;
 264                                 mincpc <<= 1;
 265                                 mincpg = roundup(mincpgcnt, mincpc);
 266                                 sblock.fs_cpg = mincpg;
 267                         }
 268                         sblock.fs_frag <<= 1;
 269                         sblock.fs_fragshift += 1;
 270                         if (sblock.fs_frag <= MAXFRAG)
 271                                 continue;
 272                 }
 273                 if (sblock.fs_fsize == sblock.fs_bsize) {
 274                         printf("There is no block size that");
 275                         printf(" can support this disk\n");
 276                         exit(22);
 277                 }
 278                 sblock.fs_frag >>= 1;
 279                 sblock.fs_fragshift -= 1;
 280                 sblock.fs_fsize <<= 1;
 281                 sblock.fs_nspf <<= 1;
 282         }
 283         /*
 284          * Ensure that cylinder group with mincpg has enough space for inodes.
 285          */
 286         inodecramped = 0;
 287         inospercg = calcipg(mincpg, bpcg, &usedb);
 288         sblock.fs_ipg = inospercg;
 289         while (inospercg > MAXIPG(&sblock)) {
 290                 inodecramped = 1;
 291                 if (mincpc == 1 || sblock.fs_frag == 1 ||
 292                     sblock.fs_bsize == MINBSIZE)
 293                         break;
 294                 printf("With a block size of %d %s %d\n", sblock.fs_bsize,
 295                     "minimum bytes per inode is",
 296                     (int)((mincpg * (off_t)bpcg - usedb) /
 297                     MAXIPG(&sblock) + 1));
 298                 sblock.fs_bsize >>= 1;
 299                 sblock.fs_frag >>= 1;
 300                 sblock.fs_fragshift -= 1;
 301                 mincpc >>= 1;
 302                 sblock.fs_cpg = roundup(mincpgcnt, mincpc);
 303                 if (CGSIZE(&sblock) > sblock.fs_bsize) {
 304                         sblock.fs_bsize <<= 1;
 305                         break;
 306                 }
 307                 mincpg = sblock.fs_cpg;
 308                 inospercg = calcipg(mincpg, bpcg, &usedb);
 309                 sblock.fs_ipg = inospercg;
 310         }
 311         if (inodecramped) {
 312                 if (inospercg > MAXIPG(&sblock)) {
 313                         printf("Minimum bytes per inode is %d\n",
 314                             (int)((mincpg * (off_t)bpcg - usedb) /
 315                             MAXIPG(&sblock) + 1));
 316                 } else if (!mapcramped) {
 317                         printf("With %d bytes per inode, ", density);
 318                         printf("minimum cylinders per group is %ld\n", mincpg);
 319                 }
 320         }
 321         if (mapcramped) {
 322                 printf("With %d sectors per cylinder, ", sblock.fs_spc);
 323                 printf("minimum cylinders per group is %ld\n", mincpg);
 324         }
 325         if (inodecramped || mapcramped) {
 326                 if (sblock.fs_bsize != bsize)
 327                         printf("%s to be changed from %d to %d\n",
 328                             "This requires the block size",
 329                             bsize, sblock.fs_bsize);
 330                 if (sblock.fs_fsize != fsize)
 331                         printf("\t%s to be changed from %d to %d\n",
 332                             "and the fragment size", fsize, sblock.fs_fsize);
 333                 exit(23);
 334         }
 335         /*
 336          * Calculate the number of cylinders per group
 337          */
 338         sblock.fs_cpg = cpg;
 339         if (sblock.fs_cpg % mincpc != 0) {
 340                 printf("%s groups must have a multiple of %ld cylinders\n",
 341                     cpgflg ? "Cylinder" : "Warning: cylinder", mincpc);
 342                 sblock.fs_cpg = roundup(sblock.fs_cpg, mincpc);
 343                 if (!cpgflg)
 344                         cpg = sblock.fs_cpg;
 345         }
 346         /*
 347          * Must ensure there is enough space for inodes.
 348          */
 349         sblock.fs_ipg = calcipg(sblock.fs_cpg, bpcg, &usedb);
 350         while (sblock.fs_ipg > MAXIPG(&sblock)) {
 351                 inodecramped = 1;
 352                 sblock.fs_cpg -= mincpc;
 353                 sblock.fs_ipg = calcipg(sblock.fs_cpg, bpcg, &usedb);
 354         }
 355         /*
 356          * Must ensure there is enough space to hold block map.
 357          */
 358         while (CGSIZE(&sblock) > sblock.fs_bsize) {
 359                 mapcramped = 1;
 360                 sblock.fs_cpg -= mincpc;
 361                 sblock.fs_ipg = calcipg(sblock.fs_cpg, bpcg, &usedb);
 362         }
 363         sblock.fs_fpg = (sblock.fs_cpg * sblock.fs_spc) / NSPF(&sblock);
 364         if ((sblock.fs_cpg * sblock.fs_spc) % NSPB(&sblock) != 0) {
 365                 printf("panic (fs_cpg * fs_spc) %% NSPF != 0");
 366                 exit(24);
 367         }
 368         if (sblock.fs_cpg < mincpg) {
 369                 printf("cylinder groups must have at least %ld cylinders\n",
 370                         mincpg);
 371                 exit(25);
 372         } else if (cpgflg && sblock.fs_cpg != cpg) {
 373                 if (!mapcramped && !inodecramped)
 374                         exit(26);
 375                 if (mapcramped && inodecramped)
 376                         printf("Block size and bytes per inode restrict");
 377                 else if (mapcramped)
 378                         printf("Block size restricts");
 379                 else
 380                         printf("Bytes per inode restrict");
 381                 printf(" cylinders per group to %d.\n", sblock.fs_cpg);
 382                 if (cpgflg)
 383                         exit(27);
 384         }
 385         sblock.fs_cgsize = fragroundup(&sblock, CGSIZE(&sblock));
 386         /*
 387          * Now have size for filesystem and nsect and ntrak.
 388          * Determine number of cylinders and blocks in the filesystem.
 389          */
 390         sblock.fs_size = fssize = dbtofsb(&sblock, fssize);
 391         sblock.fs_ncyl = fssize * NSPF(&sblock) / sblock.fs_spc;
 392         if (fssize * NSPF(&sblock) > sblock.fs_ncyl * sblock.fs_spc) {
 393                 sblock.fs_ncyl++;
 394                 lwarn = 1;
 395         }
 396         if (sblock.fs_ncyl < 1) {
 397                 printf("filesystems must have at least one cylinder\n");
 398                 exit(28);
 399         }
 400         /*
 401          * Determine feasability/values of rotational layout tables.
 402          *
 403          * The size of the rotational layout tables is limited by the
 404          * size of the superblock, SBSIZE. The amount of space available
 405          * for tables is calculated as (SBSIZE - sizeof (struct fs)).
 406          * The size of these tables is inversely proportional to the block
 407          * size of the filesystem. The size increases if sectors per track
 408          * are not powers of two, because more cylinders must be described
 409          * by the tables before the rotational pattern repeats (fs_cpc).
 410          */
 411         sblock.fs_interleave = 1;
 412         sblock.fs_trackskew = 0;
 413         sblock.fs_npsect = secpercyl;
 414         sblock.fs_postblformat = FS_DYNAMICPOSTBLFMT;
 415         sblock.fs_sbsize = fragroundup(&sblock, sizeof(struct fs));
 416         if (sblock.fs_sbsize > SBSIZE)
 417                 sblock.fs_sbsize = SBSIZE;
 418         sblock.fs_cpc = 0;
 419         /*
 420          * Compute/validate number of cylinder groups.
 421          */
 422         sblock.fs_ncg = sblock.fs_ncyl / sblock.fs_cpg;
 423         if (sblock.fs_ncyl % sblock.fs_cpg)
 424                 sblock.fs_ncg++;
 425         sblock.fs_dblkno = sblock.fs_iblkno + sblock.fs_ipg / INOPF(&sblock);
 426         i = MIN(~sblock.fs_cgmask, sblock.fs_ncg - 1);
 427         if (cgdmin(&sblock, i) - cgbase(&sblock, i) >= sblock.fs_fpg) {
 428                 printf("inode blocks/cyl group (%ld) >= data blocks (%ld)\n",
 429                     cgdmin(&sblock, i) - cgbase(&sblock, i) / sblock.fs_frag,
 430                     (long)(sblock.fs_fpg / sblock.fs_frag));
 431                 printf("number of cylinders per cylinder group (%d) %s.\n",
 432                     sblock.fs_cpg, "must be increased");
 433                 exit(29);
 434         }
 435         j = sblock.fs_ncg - 1;
 436         if ((i = fssize - j * sblock.fs_fpg) < sblock.fs_fpg &&
 437             cgdmin(&sblock, j) - cgbase(&sblock, j) > i) {
 438                 if (j == 0) {
 439                         printf("Filesystem must have at least %d sectors\n",
 440                             NSPF(&sblock) *
 441                             (cgdmin(&sblock, 0) + 3 * sblock.fs_frag));
 442                         exit(30);
 443                 }
 444                 printf(
 445 "Warning: inode blocks/cyl group (%ld) >= data blocks (%ld) in last\n",
 446                     (cgdmin(&sblock, j) - cgbase(&sblock, j)) / sblock.fs_frag,
 447                     i / sblock.fs_frag);
 448                 printf(
 449 "    cylinder group. This implies %ld sector(s) cannot be allocated.\n",
 450                     i * NSPF(&sblock));
 451                 sblock.fs_ncg--;
 452                 sblock.fs_ncyl -= sblock.fs_ncyl % sblock.fs_cpg;
 453                 sblock.fs_size = fssize = sblock.fs_ncyl * sblock.fs_spc /
 454                     NSPF(&sblock);
 455                 lwarn = 0;
 456         }
 457         if (lwarn) {
 458                 printf("Warning: %d sector(s) in last cylinder unallocated\n",
 459                     sblock.fs_spc -
 460                     (fssize * NSPF(&sblock) - (sblock.fs_ncyl - 1) *
 461                     sblock.fs_spc));
 462         }
 463         /*
 464          * fill in remaining fields of the super block
 465          */
 466         sblock.fs_csaddr = cgdmin(&sblock, 0);
 467         sblock.fs_cssize =
 468             fragroundup(&sblock, sblock.fs_ncg * sizeof(struct csum));
 469         /*
 470          * The superblock fields 'fs_csmask' and 'fs_csshift' are no
 471          * longer used. However, we still initialise them so that the
 472          * filesystem remains compatible with old kernels.
 473          */
 474         i = sblock.fs_bsize / sizeof(struct csum);
 475         sblock.fs_csmask = ~(i - 1);
 476         sblock.fs_csshift = ilog2(i);
 477         fscs = (struct csum *)calloc(1, sblock.fs_cssize);
 478         if (fscs == NULL)
 479                 errx(31, "calloc failed");
 480         sblock.fs_magic = FS_MAGIC;
 481         sblock.fs_rotdelay = 0;
 482         sblock.fs_minfree = minfree;
 483         sblock.fs_maxcontig = maxcontig;
 484         sblock.fs_maxbpg = maxbpg;
 485         sblock.fs_rps = 60;
 486         sblock.fs_optim = opt;
 487         sblock.fs_cgrotor = 0;
 488         sblock.fs_cstotal.cs_ndir = 0;
 489         sblock.fs_cstotal.cs_nbfree = 0;
 490         sblock.fs_cstotal.cs_nifree = 0;
 491         sblock.fs_cstotal.cs_nffree = 0;
 492         sblock.fs_fmod = 0;
 493         sblock.fs_ronly = 0;
 494         sblock.fs_clean = 1;
 495         sblock.fs_id[0] = (long)utime;
 496         sblock.fs_id[1] = random();
 497
 498         /*
 499          * Dump out summary information about filesystem.
 500          */
 501         printf("%s:\t%d sectors in %d %s of %d tracks, %d sectors\n",
 502             fsys, sblock.fs_size * NSPF(&sblock), sblock.fs_ncyl,
 503             "cylinders", sblock.fs_ntrak, sblock.fs_nsect);
 504 #define B2MBFACTOR (1 / (1024.0 * 1024.0))
 505         printf("\t%.1fMB in %d cyl groups (%d c/g, %.2fMB/g, %d i/g)%s\n",
 506             (float)sblock.fs_size * sblock.fs_fsize * B2MBFACTOR,
 507             sblock.fs_ncg, sblock.fs_cpg,
 508             (float)sblock.fs_fpg * sblock.fs_fsize * B2MBFACTOR,
 509             sblock.fs_ipg,
 510             sblock.fs_flags & FS_DOSOFTDEP ? " SOFTUPDATES" : "");
 511 #undef B2MBFACTOR
 512         /*
 513          * Now build the cylinders group blocks and
 514          * then print out indices of cylinder groups.
 515          */
 516         printf("super-block backups (for fsck -b #) at:\n");
 517         i = 0;
 518         width = charsperline();
 519         for (cylno = 0; cylno < sblock.fs_ncg; cylno++) {
 520                 initcg(cylno, utime);
 521                 j = snprintf(tmpbuf, sizeof(tmpbuf), " %ld%s",
 522                     fsbtodb(&sblock, cgsblock(&sblock, cylno)),
 523                     cylno < (sblock.fs_ncg-1) ? "," : "");
 524                 if (j < 0)
 525                         tmpbuf[j = 0] = '\0';
 526                 if (i + j >= width) {
 527                         printf("\n");
 528                         i = 0;
 529                 }
 530                 i += j;
 531                 printf("%s", tmpbuf);
 532                 fflush(stdout);
 533         }
 534         printf("\n");
 535         if (Nflag)
 536                 exit(0);
 537         /*
 538          * Now construct the initial filesystem,
 539          * then write out the super-block.
 540          */
 541         fsinit(utime);
 542         sblock.fs_time = utime;
 543         wtfs((int)SBOFF / sectorsize, SBSIZE, (char *)&sblock);
 544         for (i = 0; i < sblock.fs_cssize; i += sblock.fs_bsize)
 545                 wtfs(fsbtodb(&sblock, sblock.fs_csaddr + numfrags(&sblock, i)),
 546                         sblock.fs_cssize - i < sblock.fs_bsize ?
 547                         sblock.fs_cssize - i : sblock.fs_bsize,
 548                         ((char *)fscs) + i);
 549         /*
 550          * Write out the duplicate super blocks
 551          */
 552         for (cylno = 0; cylno < sblock.fs_ncg; cylno++)
 553                 wtfs(fsbtodb(&sblock, cgsblock(&sblock, cylno)),
 554                     SBSIZE, (char *)&sblock);
 555         wtfsflush();
 556         /*
 557          * Update information about this partion in pack
 558          * label, to that it may be updated on disk.
 559          */
 560         if (pp != NULL) {
 561                 pp->p_fstype = FS_BSDFFS;
 562                 pp->p_fsize = sblock.fs_fsize;
 563                 pp->p_frag = sblock.fs_frag;
 564                 pp->p_cpg = sblock.fs_cpg;
 565         }
 566 }
 567
 568 /*
 569  * Initialize a cylinder group.
 570  */
 571 void
 572 initcg(int cylno, time_t utime)
 573 {
 574         daddr_t cbase, d, dlower, dupper, dmax, blkno;
 575         struct csum *cs;
 576         long i, j;
 577
 578         /*
 579          * Determine block bounds for cylinder group.
 580          * Allow space for super block summary information in first
 581          * cylinder group.
 582          */
 583         cbase = cgbase(&sblock, cylno);
 584         dmax = cbase + sblock.fs_fpg;
 585         if (dmax > sblock.fs_size)
 586                 dmax = sblock.fs_size;
 587         dlower = cgsblock(&sblock, cylno) - cbase;
 588         dupper = cgdmin(&sblock, cylno) - cbase;
 589         if (cylno == 0)
 590                 dupper += howmany(sblock.fs_cssize, sblock.fs_fsize);
 591         cs = fscs + cylno;
 592         memset(&acg, 0, sblock.fs_cgsize);
 593         acg.cg_time = utime;
 594         acg.cg_magic = CG_MAGIC;
 595         acg.cg_cgx = cylno;
 596         if (cylno == sblock.fs_ncg - 1)
 597                 acg.cg_ncyl = sblock.fs_ncyl % sblock.fs_cpg;
 598         else
 599                 acg.cg_ncyl = sblock.fs_cpg;
 600         acg.cg_niblk = sblock.fs_ipg;
 601         acg.cg_ndblk = dmax - cbase;
 602         if (sblock.fs_contigsumsize > 0)
 603                 acg.cg_nclusterblks = acg.cg_ndblk / sblock.fs_frag;
 604         acg.cg_btotoff = &acg.cg_space[0] - (u_char *)(&acg.cg_firstfield);
 605         acg.cg_boff = acg.cg_btotoff + sblock.fs_cpg * sizeof(int32_t);
 606         acg.cg_iusedoff = acg.cg_boff +
 607                 sblock.fs_cpg * sizeof(u_int16_t);
 608         acg.cg_freeoff = acg.cg_iusedoff + howmany(sblock.fs_ipg, NBBY);
 609         if (sblock.fs_contigsumsize <= 0) {
 610                 acg.cg_nextfreeoff = acg.cg_freeoff +
 611                     howmany(sblock.fs_cpg * sblock.fs_spc / NSPF(&sblock),
 612                     NBBY);
 613         } else {
 614                 acg.cg_clustersumoff = acg.cg_freeoff + howmany
 615                     (sblock.fs_cpg * sblock.fs_spc / NSPF(&sblock), NBBY) -
 616                     sizeof(u_int32_t);
 617                 acg.cg_clustersumoff =
 618                     roundup(acg.cg_clustersumoff, sizeof(u_int32_t));
 619                 acg.cg_clusteroff = acg.cg_clustersumoff +
 620                     (sblock.fs_contigsumsize + 1) * sizeof(u_int32_t);
 621                 acg.cg_nextfreeoff = acg.cg_clusteroff + howmany
 622                     (sblock.fs_cpg * sblock.fs_spc / NSPB(&sblock), NBBY);
 623         }
 624         if (acg.cg_nextfreeoff - (long)(&acg.cg_firstfield) >
 625             sblock.fs_cgsize) {
 626                 printf("Panic: cylinder group too big\n");
 627                 exit(37);
 628         }
 629         acg.cg_cs.cs_nifree += sblock.fs_ipg;
 630         if (cylno == 0)
 631                 for (i = 0; i < ROOTINO; i++) {
 632                         setbit(cg_inosused(&acg), i);
 633                         acg.cg_cs.cs_nifree--;
 634                 }
 635         for (i = 0; i < sblock.fs_ipg / INOPF(&sblock); i += sblock.fs_frag) {
 636                 for (j = 0; j < sblock.fs_bsize / sizeof(struct dinode); j++)
 637                         zino[j].di_gen = random();
 638                 wtfs(fsbtodb(&sblock, cgimin(&sblock, cylno) + i),
 639                     sblock.fs_bsize, (char *)zino);
 640         }
 641         if (cylno > 0) {
 642                 /*
 643                  * In cylno 0, beginning space is reserved
 644                  * for boot and super blocks.
 645                  */
 646                 for (d = 0; d < dlower; d += sblock.fs_frag) {
 647                         blkno = d / sblock.fs_frag;
 648                         setblock(&sblock, cg_blksfree(&acg), blkno);
 649                         if (sblock.fs_contigsumsize > 0)
 650                                 setbit(cg_clustersfree(&acg), blkno);
 651                         acg.cg_cs.cs_nbfree++;
 652                         cg_blktot(&acg)[cbtocylno(&sblock, d)]++;
 653                         cg_blks(&sblock, &acg, cbtocylno(&sblock, d))
 654                             [cbtorpos(&sblock, d)]++;
 655                 }
 656                 sblock.fs_dsize += dlower;
 657         }
 658         sblock.fs_dsize += acg.cg_ndblk - dupper;
 659         if ((i = dupper % sblock.fs_frag)) {
 660                 acg.cg_frsum[sblock.fs_frag - i]++;
 661                 for (d = dupper + sblock.fs_frag - i; dupper < d; dupper++) {
 662                         setbit(cg_blksfree(&acg), dupper);
 663                         acg.cg_cs.cs_nffree++;
 664                 }
 665         }
 666         for (d = dupper; d + sblock.fs_frag <= dmax - cbase;) {
 667                 blkno = d / sblock.fs_frag;
 668                 setblock(&sblock, cg_blksfree(&acg), blkno);
 669                 if (sblock.fs_contigsumsize > 0)
 670                         setbit(cg_clustersfree(&acg), blkno);
 671                 acg.cg_cs.cs_nbfree++;
 672                 cg_blktot(&acg)[cbtocylno(&sblock, d)]++;
 673                 cg_blks(&sblock, &acg, cbtocylno(&sblock, d))
 674                     [cbtorpos(&sblock, d)]++;
 675                 d += sblock.fs_frag;
 676         }
 677         if (d < dmax - cbase) {
 678                 acg.cg_frsum[dmax - cbase - d]++;
 679                 for (; d < dmax - cbase; d++) {
 680                         setbit(cg_blksfree(&acg), d);
 681                         acg.cg_cs.cs_nffree++;
 682                 }
 683         }
 684         if (sblock.fs_contigsumsize > 0) {
 685                 int32_t *sump = cg_clustersum(&acg);
 686                 u_char *mapp = cg_clustersfree(&acg);
 687                 int map = *mapp++;
 688                 int bit = 1;
 689                 int run = 0;
 690
 691                 for (i = 0; i < acg.cg_nclusterblks; i++) {
 692                         if ((map & bit) != 0)
 693                                 run++;
 694                         else if (run != 0) {
 695                                 if (run > sblock.fs_contigsumsize)
 696                                         run = sblock.fs_contigsumsize;
 697                                 sump[run]++;
 698                                 run = 0;
 699                         }
 700                         if ((i & (NBBY - 1)) != NBBY - 1)
 701                                 bit <<= 1;
 702                         else {
 703                                 map = *mapp++;
 704                                 bit = 1;
 705                         }
 706                 }
 707                 if (run != 0) {
 708                         if (run > sblock.fs_contigsumsize)
 709                                 run = sblock.fs_contigsumsize;
 710                         sump[run]++;
 711                 }
 712         }
 713         sblock.fs_cstotal.cs_ndir += acg.cg_cs.cs_ndir;
 714         sblock.fs_cstotal.cs_nffree += acg.cg_cs.cs_nffree;
 715         sblock.fs_cstotal.cs_nbfree += acg.cg_cs.cs_nbfree;
 716         sblock.fs_cstotal.cs_nifree += acg.cg_cs.cs_nifree;
 717         *cs = acg.cg_cs;
 718         wtfs(fsbtodb(&sblock, cgtod(&sblock, cylno)),
 719                 sblock.fs_bsize, (char *)&acg);
 720 }
 721
 722 /*
 723  * initialize the filesystem
 724  */
 725 struct dinode node;
 726
 727 #define PREDEFDIR 2
 728
 729 struct direct root_dir[] = {
 730         { ROOTINO, sizeof(struct direct), DT_DIR, 1, "." },
 731         { ROOTINO, sizeof(struct direct), DT_DIR, 2, ".." },
 732 };
 733 struct odirect {
 734         u_long  d_ino;
 735         u_short d_reclen;
 736         u_short d_namlen;
 737         u_char  d_name[MAXNAMLEN + 1];
 738 } oroot_dir[] = {
 739         { ROOTINO, sizeof(struct direct), 1, "." },
 740         { ROOTINO, sizeof(struct direct), 2, ".." },
 741 };
 742 char buf[MAXBSIZE];
 743
 744 void
 745 fsinit(time_t utime)
 746 {
 747
 748         /*
 749          * initialize the node
 750          */
 751         node.di_atime = utime;
 752         node.di_mtime = utime;
 753         node.di_ctime = utime;
 754         /*
 755          * create the root directory
 756          */
 757         node.di_mode = IFDIR | UMASK;
 758         node.di_nlink = PREDEFDIR;
 759         node.di_size = makedir(root_dir, PREDEFDIR);
 760         node.di_db[0] = alloc(sblock.fs_fsize, node.di_mode);
 761         node.di_blocks = btodb(fragroundup(&sblock, node.di_size));
 762         wtfs(fsbtodb(&sblock, node.di_db[0]), sblock.fs_fsize, buf);
 763         iput(&node, ROOTINO);
 764 }
 765
 766 /*
 767  * construct a set of directory entries in "buf".
 768  * return size of directory.
 769  */
 770 int
 771 makedir(struct direct *protodir, int entries)
 772 {
 773         char *cp;
 774         int i, spcleft;
 775
 776         spcleft = DIRBLKSIZ;
 777         for (cp = buf, i = 0; i < entries - 1; i++) {
 778                 protodir[i].d_reclen = DIRSIZ(0, &protodir[i]);
 779                 memmove(cp, &protodir[i], protodir[i].d_reclen);
 780                 cp += protodir[i].d_reclen;
 781                 spcleft -= protodir[i].d_reclen;
 782         }
 783         protodir[i].d_reclen = spcleft;
 784         memmove(cp, &protodir[i], DIRSIZ(0, &protodir[i]));
 785         return (DIRBLKSIZ);
 786 }
 787
 788 /*
 789  * allocate a block or frag
 790  */
 791 daddr_t
 792 alloc(int size, int mode)
 793 {
 794         int i, frag;
 795         daddr_t d, blkno;
 796
 797         rdfs(fsbtodb(&sblock, cgtod(&sblock, 0)), sblock.fs_cgsize,
 798             (char *)&acg);
 799         if (acg.cg_magic != CG_MAGIC) {
 800                 printf("cg 0: bad magic number\n");
 801                 return (0);
 802         }
 803         if (acg.cg_cs.cs_nbfree == 0) {
 804                 printf("first cylinder group ran out of space\n");
 805                 return (0);
 806         }
 807         for (d = 0; d < acg.cg_ndblk; d += sblock.fs_frag)
 808                 if (isblock(&sblock, cg_blksfree(&acg), d / sblock.fs_frag))
 809                         goto goth;
 810         printf("internal error: can't find block in cyl 0\n");
 811         return (0);
 812 goth:
 813         blkno = fragstoblks(&sblock, d);
 814         clrblock(&sblock, cg_blksfree(&acg), blkno);
 815         if (sblock.fs_contigsumsize > 0)
 816                 clrbit(cg_clustersfree(&acg), blkno);
 817         acg.cg_cs.cs_nbfree--;
 818         sblock.fs_cstotal.cs_nbfree--;
 819         fscs[0].cs_nbfree--;
 820         if (mode & IFDIR) {
 821                 acg.cg_cs.cs_ndir++;
 822                 sblock.fs_cstotal.cs_ndir++;
 823                 fscs[0].cs_ndir++;
 824         }
 825         cg_blktot(&acg)[cbtocylno(&sblock, d)]--;
 826         cg_blks(&sblock, &acg, cbtocylno(&sblock, d))[cbtorpos(&sblock, d)]--;
 827         if (size != sblock.fs_bsize) {
 828                 frag = howmany(size, sblock.fs_fsize);
 829                 fscs[0].cs_nffree += sblock.fs_frag - frag;
 830                 sblock.fs_cstotal.cs_nffree += sblock.fs_frag - frag;
 831                 acg.cg_cs.cs_nffree += sblock.fs_frag - frag;
 832                 acg.cg_frsum[sblock.fs_frag - frag]++;
 833                 for (i = frag; i < sblock.fs_frag; i++)
 834                         setbit(cg_blksfree(&acg), d + i);
 835         }
 836         wtfs(fsbtodb(&sblock, cgtod(&sblock, 0)), sblock.fs_cgsize,
 837             (char *)&acg);
 838         return (d);
 839 }
 840
 841 /*
 842  * Calculate number of inodes per group.
 843  */
 844 long
 845 calcipg(long lcpg, long bpcg, off_t *usedbp)
 846 {
 847         int i;
 848         long ipg, new_ipg, ncg, ncyl;
 849         off_t usedb;
 850
 851         /*
 852          * Prepare to scale by fssize / (number of sectors in cylinder groups).
 853          * Note that fssize is still in sectors, not filesystem blocks.
 854          */
 855         ncyl = howmany(fssize, (u_int)secpercyl);
 856         ncg = howmany(ncyl, lcpg);
 857         /*
 858          * Iterate a few times to allow for ipg depending on itself.
 859          */
 860         ipg = 0;
 861         for (i = 0; i < 10; i++) {
 862                 usedb = (sblock.fs_iblkno + ipg / INOPF(&sblock)) *
 863                     NSPF(&sblock) * (off_t)sectorsize;
 864                 new_ipg = (lcpg * (quad_t)bpcg - usedb) / density *
 865                     fssize / ncg / secpercyl / lcpg;
 866                 new_ipg = roundup(new_ipg, INOPB(&sblock));
 867                 if (new_ipg == ipg)
 868                         break;
 869                 ipg = new_ipg;
 870         }
 871         *usedbp = usedb;
 872         return (ipg);
 873 }
 874
 875 /*
 876  * Allocate an inode on the disk
 877  */
 878 void
 879 iput(struct dinode *ip, ino_t ino)
 880 {
 881         struct dinode lbuf[MAXINOPB];
 882         daddr_t d;
 883         int c;
 884
 885         ip->di_gen = random();
 886         c = ino_to_cg(&sblock, ino);
 887         rdfs(fsbtodb(&sblock, cgtod(&sblock, 0)), sblock.fs_cgsize,
 888             (char *)&acg);
 889         if (acg.cg_magic != CG_MAGIC) {
 890                 printf("cg 0: bad magic number\n");
 891                 exit(31);
 892         }
 893         acg.cg_cs.cs_nifree--;
 894         setbit(cg_inosused(&acg), ino);
 895         wtfs(fsbtodb(&sblock, cgtod(&sblock, 0)), sblock.fs_cgsize,
 896             (char *)&acg);
 897         sblock.fs_cstotal.cs_nifree--;
 898         fscs[0].cs_nifree--;
 899         if (ino >= sblock.fs_ipg * sblock.fs_ncg) {
 900                 printf("fsinit: inode value out of range (%d).\n", ino);
 901                 exit(32);
 902         }
 903         d = fsbtodb(&sblock, ino_to_fsba(&sblock, ino));
 904         rdfs(d, sblock.fs_bsize, (char *)lbuf);
 905         lbuf[ino_to_fsbo(&sblock, ino)] = *ip;
 906         wtfs(d, sblock.fs_bsize, (char *)lbuf);
 907 }
 908
 909 /*
 910  * read a block from the filesystem
 911  */
 912 void
 913 rdfs(daddr_t bno, int size, char *bf)
 914 {
 915         int n;
 916
 917         wtfsflush();
 918         if (lseek(fso, (off_t)bno * sectorsize, 0) < 0) {
 919                 printf("seek error: %ld\n", (long)bno);
 920                 err(33, "rdfs");
 921         }
 922         n = read(fso, bf, size);
 923         if (n != size) {
 924                 printf("read error: %ld\n", (long)bno);
 925                 err(34, "rdfs");
 926         }
 927 }
 928
 929 #define WCSIZE (128 * 1024)
 930 daddr_t wc_sect;                /* units of sectorsize */
 931 int wc_end;                     /* bytes */
 932 static char wc[WCSIZE];         /* bytes */
 933
 934 /*
 935  * Flush dirty write behind buffer.
 936  */
 937 static void
 938 wtfsflush()
 939 {
 940         int n;
 941         if (wc_end) {
 942                 if (lseek(fso, (off_t)wc_sect * sectorsize, SEEK_SET) < 0) {
 943                         printf("seek error: %ld\n", (long)wc_sect);
 944                         err(35, "wtfs - writecombine");
 945                 }
 946                 n = write(fso, wc, wc_end);
 947                 if (n != wc_end) {
 948                         printf("write error: %ld\n", (long)wc_sect);
 949                         err(36, "wtfs - writecombine");
 950                 }
 951                 wc_end = 0;
 952         }
 953 }
 954
 955 /*
 956  * write a block to the filesystem
 957  */
 958 static void
 959 wtfs(daddr_t bno, int size, char *bf)
 960 {
 961         int done, n;
 962
 963         if (Nflag)
 964                 return;
 965         done = 0;
 966         if (wc_end == 0 && size <= WCSIZE) {
 967                 wc_sect = bno;
 968                 bcopy(bf, wc, size);
 969                 wc_end = size;
 970                 if (wc_end < WCSIZE)
 971                         return;
 972                 done = 1;
 973         }
 974         if ((off_t)wc_sect * sectorsize + wc_end == (off_t)bno * sectorsize &&
 975             wc_end + size <= WCSIZE) {
 976                 bcopy(bf, wc + wc_end, size);
 977                 wc_end += size;
 978                 if (wc_end < WCSIZE)
 979                         return;
 980                 done = 1;
 981         }
 982         wtfsflush();
 983         if (done)
 984                 return;
 985         if (lseek(fso, (off_t)bno * sectorsize, SEEK_SET) < 0) {
 986                 printf("seek error: %ld\n", (long)bno);
 987                 err(35, "wtfs");
 988         }
 989         n = write(fso, bf, size);
 990         if (n != size) {
 991                 printf("write error: %ld\n", (long)bno);
 992                 err(36, "wtfs");
 993         }
 994 }
 995
 996 /*
 997  * check if a block is available
 998  */
 999 static int
1000 isblock(struct fs *fs, unsigned char *cp, int h)
1001 {
1002         unsigned char mask;
1003
1004         switch (fs->fs_frag) {
1005         case 8:
1006                 return (cp[h] == 0xff);
1007         case 4:
1008                 mask = 0x0f << ((h & 0x1) << 2);
1009                 return ((cp[h >> 1] & mask) == mask);
1010         case 2:
1011                 mask = 0x03 << ((h & 0x3) << 1);
1012                 return ((cp[h >> 2] & mask) == mask);
1013         case 1:
1014                 mask = 0x01 << (h & 0x7);
1015                 return ((cp[h >> 3] & mask) == mask);
1016         default:
1017                 fprintf(stderr, "isblock bad fs_frag %d\n", fs->fs_frag);
1018                 return (0);
1019         }
1020 }
1021
1022 /*
1023  * take a block out of the map
1024  */
1025 static void
1026 clrblock(struct fs *fs, unsigned char *cp, int h)
1027 {
1028         switch ((fs)->fs_frag) {
1029         case 8:
1030                 cp[h] = 0;
1031                 return;
1032         case 4:
1033                 cp[h >> 1] &= ~(0x0f << ((h & 0x1) << 2));
1034                 return;
1035         case 2:
1036                 cp[h >> 2] &= ~(0x03 << ((h & 0x3) << 1));
1037                 return;
1038         case 1:
1039                 cp[h >> 3] &= ~(0x01 << (h & 0x7));
1040                 return;
1041         default:
1042                 fprintf(stderr, "clrblock bad fs_frag %d\n", fs->fs_frag);
1043                 return;
1044         }
1045 }
1046
1047 /*
1048  * put a block into the map
1049  */
1050 static void
1051 setblock(struct fs *fs, unsigned char *cp, int h)
1052 {
1053         switch (fs->fs_frag) {
1054         case 8:
1055                 cp[h] = 0xff;
1056                 return;
1057         case 4:
1058                 cp[h >> 1] |= (0x0f << ((h & 0x1) << 2));
1059                 return;
1060         case 2:
1061                 cp[h >> 2] |= (0x03 << ((h & 0x3) << 1));
1062                 return;
1063         case 1:
1064                 cp[h >> 3] |= (0x01 << (h & 0x7));
1065                 return;
1066         default:
1067                 fprintf(stderr, "setblock bad fs_frag %d\n", fs->fs_frag);
1068                 return;
1069         }
1070 }
1071
1072 /*
1073  * Determine the number of characters in a
1074  * single line.
1075  */
1076
1077 static int
1078 charsperline(void)
1079 {
1080         int columns;
1081         char *cp;
1082         struct winsize ws;
1083
1084         columns = 0;
1085         if (ioctl(0, TIOCGWINSZ, &ws) != -1)
1086                 columns = ws.ws_col;
1087         if (columns == 0 && (cp = getenv("COLUMNS")))
1088                 columns = atoi(cp);
1089         if (columns == 0)
1090                 columns = 80;   /* last resort */
1091         return (columns);
1092 }
1093
1094 static int
1095 ilog2(int val)
1096 {
1097         u_int n;
1098
1099         for (n = 0; n < sizeof(n) * NBBY; n++)
1100                 if (1 << n == val)
1101                         return (n);
1102         errx(1, "ilog2: %d is not a power of 2\n", val);
1103 }