src/sbin/newfs_ext2fs/mke2fs.c

   1 /* $OpenBSD: mke2fs.c,v 1.2 2010/02/16 12:25:35 otto Exp $ */
   2 /*      $NetBSD: mke2fs.c,v 1.13 2009/10/19 18:41:08 bouyer Exp $       */
   3
   4 /*-
   5  * Copyright (c) 2007 Izumi Tsutsui.  All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 /*
  29  * Copyright (c) 1980, 1989, 1993
  30  *      The Regents of the University of California.  All rights reserved.
  31  *
  32  * Redistribution and use in source and binary forms, with or without
  33  * modification, are permitted provided that the following conditions
  34  * are met:
  35  * 1. Redistributions of source code must retain the above copyright
  36  *    notice, this list of conditions and the following disclaimer.
  37  * 2. Redistributions in binary form must reproduce the above copyright
  38  *    notice, this list of conditions and the following disclaimer in the
  39  *    documentation and/or other materials provided with the distribution.
  40  * 3. Neither the name of the University nor the names of its contributors
  41  *    may be used to endorse or promote products derived from this software
  42  *    without specific prior written permission.
  43  *
  44  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  45  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  46  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  47  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  48  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  49  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  50  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  51  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  52  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  53  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  54  * SUCH DAMAGE.
  55  */
  56
  57 /*
  58  * Copyright (c) 1997 Manuel Bouyer.
  59  *
  60  * Redistribution and use in source and binary forms, with or without
  61  * modification, are permitted provided that the following conditions
  62  * are met:
  63  * 1. Redistributions of source code must retain the above copyright
  64  *      notice, this list of conditions and the following disclaimer.
  65  * 2. Redistributions in binary form must reproduce the above copyright
  66  *      notice, this list of conditions and the following disclaimer in the
  67  *      documentation and/or other materials provided with the distribution.
  68  *
  69  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  70  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  71  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  72  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  73  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  74  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  75  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  76  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  77  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  78  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  79  */
  80
  81 /*
  82  * mke2fs.c: "re-invent (dumb but non-GPLed) wheel as a fun project"
  83  *
  84  *      In spite of this name, there is no piece of code
  85  *      derived from GPLed e2fsprogs written for Linux.
  86  *      I referred them only to see how each structure
  87  *      member should be initialized.
  88  *
  89  * Reference:
  90  *      - All NetBSD sources under src/sys/ufs/ext2fs and src/sbin/fsck_ext2fs
  91  *      - Ext2fs Home Page
  92  *              http://e2fsprogs.sourceforge.net/ext2.html
  93  *      - Design and Implementation of the Second Extended Filesystem
  94  *              http://e2fsprogs.sourceforge.net/ext2intro.html
  95  *      - Linux Documentation "The Second Extended Filesystem"
  96  *              src/linux/Documentation/filesystems/ext2.txt
  97  *                  in the Linux kernel distribution
  98  */
  99
 100 #include <sys/cdefs.h>
 101
 102 #include <sys/param.h>
 103 #include <sys/mman.h>
 104 #include <sys/time.h>
 105 #include <ufs/ext2fs/ext2fs_dinode.h>
 106 #include <ufs/ext2fs/ext2fs_dir.h>
 107 #include <ufs/ext2fs/ext2fs.h>
 108 #include <sys/ioctl.h>
 109
 110 #include <err.h>
 111 #include <errno.h>
 112 #include <inttypes.h>
 113 #include <string.h>
 114 #include <unistd.h>
 115 #include <stdint.h>
 116 #include <stdlib.h>
 117 #include <stddef.h>
 118 #include <stdio.h>
 119
 120 #include "extern.h"
 121
 122 static void initcg(uint);
 123 static void zap_old_sblock(daddr_t);
 124 static uint cgoverhead(uint);
 125 static int fsinit(const struct timeval *);
 126 static int makedir(struct ext2fs_direct *, int);
 127 static void copy_dir(struct ext2fs_direct *, struct ext2fs_direct *);
 128 static void init_resizeino(const struct timeval *);
 129 static uint32_t alloc(uint32_t, uint16_t);
 130 static void iput(struct ext2fs_dinode *, ino_t);
 131 static void rdfs(daddr_t, int, void *);
 132 static void wtfs(daddr_t, int, void *);
 133 static int ilog2(uint);
 134 static int skpc(int, size_t, uint8_t *);
 135 static void uuid_get(struct m_ext2fs *);
 136
 137 /* XXX: some of these macro should be into <ufs/ext2fs/ext2fs.h>? */
 138 #define EXT2_DEF_MAX_MNT_COUNT  20
 139 #define EXT2_DEF_FSCKINTV       (180 * 24 * 60 * 60)    /* 180 days */
 140 #define EXT2_RESERVED_INODES    (EXT2_FIRSTINO - 1)
 141 #define EXT2_UMASK              0755
 142
 143 #define EXT2_INO_INDEX(ino)     ((ino) - 1)             /* no inode zero */
 144
 145 #define EXT2_LOSTFOUNDSIZE      16384
 146 #define EXT2_LOSTFOUNDINO       EXT2_FIRSTINO           /* XXX: not quite */
 147 #define EXT2_LOSTFOUNDUMASK     0700
 148
 149 #define EXT2_RESIZEINOUMASK     0600
 150
 151 #define NBLOCK_SUPERBLOCK       1
 152 #define NBLOCK_BLOCK_BITMAP     1
 153 #define NBLOCK_INODE_BITMAP     1
 154
 155 #define cgbase(fs, c)   \
 156         ((fs)->e2fs.e2fs_first_dblock + (fs)->e2fs.e2fs_bpg * (c))
 157
 158 #define       rounddown(x,y)  (((x)/(y))*(y))
 159
 160 /*
 161  * ext2fs super block and group descriptor structures
 162  *
 163  *   We don't have to use or setup whole in-memory m_ext2fs structure,
 164  *   but prepare it to use several macro defined in kernel headers.
 165  */
 166 union {
 167         struct m_ext2fs m_ext2fs;
 168         char pad[SBSIZE];
 169 } ext2fsun;
 170 #define sblock  ext2fsun.m_ext2fs
 171 #define gd      ext2fsun.m_ext2fs.e2fs_gd
 172
 173 static uint8_t *iobuf;          /* for superblock and group descriptors */
 174 static int iobufsize;
 175
 176 static uint8_t buf[MAXBSIZE];   /* for initcg() and makedir() ops */
 177
 178 static int fsi, fso;
 179
 180 void
 181 mke2fs(const char *fsys, int fi, int fo)
 182 {
 183         struct timeval tv;
 184         int64_t minfssize;
 185         uint bcount, fbcount, ficount;
 186         uint blocks_gd, blocks_per_cg, inodes_per_cg, iblocks_per_cg;
 187         uint minblocks_per_cg, blocks_lastcg;
 188         uint ncg, cylno, sboff;
 189         int i, len, col, delta, fld_width, max_cols;
 190         struct winsize winsize;
 191
 192         gettimeofday(&tv, NULL);
 193         fsi = fi;
 194         fso = fo;
 195
 196         /*
 197          * collect and verify the block and fragment sizes
 198          */
 199         if (!powerof2(bsize)) {
 200                 errx(EXIT_FAILURE,
 201                     "block size must be a power of 2, not %u\n",
 202                     bsize);
 203         }
 204         if (!powerof2(fsize)) {
 205                 errx(EXIT_FAILURE,
 206                     "fragment size must be a power of 2, not %u\n",
 207                     fsize);
 208         }
 209         if (fsize < sectorsize) {
 210                 errx(EXIT_FAILURE,
 211                     "fragment size %u is too small, minimum is %u\n",
 212                     fsize, sectorsize);
 213         }
 214         if (bsize < MINBSIZE) {
 215                 errx(EXIT_FAILURE,
 216                     "block size %u is too small, minimum is %u\n",
 217                     bsize, MINBSIZE);
 218         }
 219         if (bsize > EXT2_MAXBSIZE) {
 220                 errx(EXIT_FAILURE,
 221                     "block size %u is too large, maximum is %u\n",
 222                     bsize, MAXBSIZE);
 223         }
 224         if (bsize != fsize) {
 225                 /*
 226                  * There is no fragment support on current ext2fs (yet?),
 227                  * but some kernel code refers fsize or fpg as bsize or bpg
 228                  * and Linux seems to set the same values to them.
 229                  */
 230                 errx(EXIT_FAILURE,
 231                     "block size (%u) can't be different from "
 232                     "fragment size (%u)\n",
 233                     bsize, fsize);
 234         }
 235
 236         /* variable inodesize is REV1 feature */
 237         if (Oflag == 0 && inodesize != EXT2_REV0_DINODE_SIZE) {
 238                 errx(EXIT_FAILURE, "GOOD_OLD_REV file system format"
 239                     " doesn't support %d byte inode\n", inodesize);
 240         }
 241
 242         sblock.e2fs.e2fs_log_bsize = ilog2(bsize) - LOG_MINBSIZE;
 243         /* Umm, why not e2fs_log_fsize? */
 244         sblock.e2fs.e2fs_fsize = ilog2(fsize) - LOG_MINBSIZE;
 245
 246         sblock.e2fs_bsize = bsize;
 247         sblock.e2fs_bshift = sblock.e2fs.e2fs_log_bsize + LOG_MINBSIZE;
 248         sblock.e2fs_qbmask = sblock.e2fs_bsize - 1;
 249         sblock.e2fs_bmask = ~sblock.e2fs_qbmask;
 250         sblock.e2fs_fsbtodb = ilog2(sblock.e2fs_bsize) - ilog2(sectorsize);
 251         sblock.e2fs_ipb = sblock.e2fs_bsize / inodesize;
 252
 253         /*
 254          * Ext2fs preserves BBSIZE (1024 bytes) space at the top for
 255          * bootloader (though it is not enough at all for our bootloader).
 256          * If bsize == BBSIZE we have to preserve one block.
 257          * If bsize > BBSIZE, the first block already contains BBSIZE space
 258          * before superblock because superblock is allocated at SBOFF and
 259          * bsize is a power of two (i.e. 2048 bytes or more).
 260          */
 261         sblock.e2fs.e2fs_first_dblock = (sblock.e2fs_bsize > BBSIZE) ? 0 : 1;
 262         minfssize = fsbtodb(&sblock,
 263             sblock.e2fs.e2fs_first_dblock +
 264             NBLOCK_SUPERBLOCK +
 265             1 /* at least one group descriptor */ +
 266             NBLOCK_BLOCK_BITMAP +
 267             NBLOCK_INODE_BITMAP +
 268             1 /* at least one inode table block */ +
 269             1 /* at least one data block for rootdir */ +
 270             1 /* at least one data block for data */
 271             );                  /* XXX and more? */
 272
 273         if (fssize < minfssize)
 274                 errx(EXIT_FAILURE, "Filesystem size %" PRId64
 275                     " < minimum size of %" PRId64 "\n", fssize, minfssize);
 276
 277         bcount = dbtofsb(&sblock, fssize);
 278
 279         /*
 280          * While many people claim that ext2fs is a (bad) clone of ufs/ffs,
 281          * it isn't actual ffs so maybe we should call it "block group"
 282          * as their native name rather than ffs derived "cylinder group."
 283          * But we'll use the latter here since other kernel sources use it.
 284          * (I also agree "cylinder" based allocation is obsolete though)
 285          */
 286
 287         /* maybe "simple is the best" */
 288         blocks_per_cg = sblock.e2fs_bsize * NBBY;
 289
 290         ncg = howmany(bcount - sblock.e2fs.e2fs_first_dblock, blocks_per_cg);
 291         blocks_gd = howmany(sizeof(struct ext2_gd) * ncg, bsize);
 292
 293         /* check range of inode number */
 294         if (num_inodes < EXT2_FIRSTINO)
 295                 num_inodes = EXT2_FIRSTINO;     /* needs reserved inodes + 1 */
 296         if (num_inodes > UINT16_MAX * ncg)
 297                 num_inodes = UINT16_MAX * ncg;  /* ext2bgd_nifree is uint16_t */
 298
 299         inodes_per_cg = num_inodes / ncg;
 300         iblocks_per_cg = howmany(inodesize * inodes_per_cg, bsize);
 301
 302         /* Check that the last cylinder group has enough space for inodes */
 303         minblocks_per_cg =
 304             NBLOCK_BLOCK_BITMAP +
 305             NBLOCK_INODE_BITMAP +
 306             iblocks_per_cg +
 307             1;  /* at least one data block */
 308         if (Oflag == 0 || cg_has_sb(ncg - 1) != 0)
 309                 minblocks_per_cg += NBLOCK_SUPERBLOCK + blocks_gd;
 310
 311         blocks_lastcg = bcount - sblock.e2fs.e2fs_first_dblock -
 312             blocks_per_cg * (ncg - 1);
 313         if (blocks_lastcg < minblocks_per_cg) {
 314                 /*
 315                  * Since we make all the cylinder groups the same size, the
 316                  * last will only be small if there are more than one
 317                  * cylinder groups. If the last one is too small to store
 318                  * filesystem data, just kill it.
 319                  *
 320                  * XXX: Does fsck_ext2fs(8) properly handle this case?
 321                  */
 322                 bcount -= blocks_lastcg;
 323                 ncg--;
 324                 blocks_lastcg = blocks_per_cg;
 325                 blocks_gd = howmany(sizeof(struct ext2_gd) * ncg, bsize);
 326                 inodes_per_cg = num_inodes / ncg;
 327         }
 328         /* roundup inodes_per_cg to make it use whole inode table blocks */
 329         inodes_per_cg = roundup(inodes_per_cg, sblock.e2fs_ipb);
 330         num_inodes = inodes_per_cg * ncg;
 331         iblocks_per_cg = inodes_per_cg / sblock.e2fs_ipb;
 332
 333         /* XXX: probably we should check these adjusted values again */
 334
 335         sblock.e2fs.e2fs_bcount = bcount;
 336         sblock.e2fs.e2fs_icount = num_inodes;
 337
 338         sblock.e2fs_ncg = ncg;
 339         sblock.e2fs_ngdb = blocks_gd;
 340         sblock.e2fs_itpg = iblocks_per_cg;
 341
 342         sblock.e2fs.e2fs_rbcount = sblock.e2fs.e2fs_bcount * minfree / 100;
 343         /* e2fs_fbcount will be accounted later */
 344         /* e2fs_ficount will be accounted later */
 345
 346         sblock.e2fs.e2fs_bpg = blocks_per_cg;
 347         sblock.e2fs.e2fs_fpg = blocks_per_cg;
 348
 349         sblock.e2fs.e2fs_ipg = inodes_per_cg;
 350
 351         sblock.e2fs.e2fs_mtime = 0;
 352         sblock.e2fs.e2fs_wtime = tv.tv_sec;
 353         sblock.e2fs.e2fs_mnt_count = 0;
 354         /* XXX: should add some entropy to avoid checking all fs at once? */
 355         sblock.e2fs.e2fs_max_mnt_count = EXT2_DEF_MAX_MNT_COUNT;
 356
 357         sblock.e2fs.e2fs_magic = E2FS_MAGIC;
 358         sblock.e2fs.e2fs_state = E2FS_ISCLEAN;
 359         sblock.e2fs.e2fs_beh = E2FS_BEH_DEFAULT;
 360         sblock.e2fs.e2fs_minrev = 0;
 361         sblock.e2fs.e2fs_lastfsck = tv.tv_sec;
 362         sblock.e2fs.e2fs_fsckintv = EXT2_DEF_FSCKINTV;
 363
 364         /*
 365          * Maybe we can use E2FS_OS_FREEBSD here and it would be more proper,
 366          * but the purpose of this newfs_ext2fs(8) command is to provide
 367          * a filesystem which can be recognized by firmware on some
 368          * Linux based appliances that can load bootstrap files only from
 369          * (their native) ext2fs, and anyway we will (and should) try to
 370          * act like them as much as possible.
 371          *
 372          * Anyway, I hope that all newer such boxes will keep their support
 373          * for the "GOOD_OLD_REV" ext2fs.
 374          */
 375         sblock.e2fs.e2fs_creator = E2FS_OS_LINUX;
 376
 377         if (Oflag == 0) {
 378                 sblock.e2fs.e2fs_rev = E2FS_REV0;
 379                 sblock.e2fs.e2fs_features_compat   = 0;
 380                 sblock.e2fs.e2fs_features_incompat = 0;
 381                 sblock.e2fs.e2fs_features_rocompat = 0;
 382         } else {
 383                 sblock.e2fs.e2fs_rev = E2FS_REV1;
 384                 /*
 385                  * e2fsprogs say "REV1" is "dynamic" so
 386                  * it isn't quite a version and maybe it means
 387                  * "extended from REV0 so check compat features."
 388                  *
 389                  * XXX: We don't have any native tool to activate
 390                  *      the EXT2F_COMPAT_RESIZE feature and
 391                  *      fsck_ext2fs(8) might not fix structures for it.
 392                  */
 393                 sblock.e2fs.e2fs_features_compat   = EXT2F_COMPAT_RESIZE;
 394                 sblock.e2fs.e2fs_features_incompat = EXT2F_INCOMPAT_FTYPE;
 395                 sblock.e2fs.e2fs_features_rocompat =
 396                     EXT2F_ROCOMPAT_SPARSESUPER | EXT2F_ROCOMPAT_LARGEFILE;
 397         }
 398
 399         sblock.e2fs.e2fs_ruid = geteuid();
 400         sblock.e2fs.e2fs_rgid = getegid();
 401
 402         sblock.e2fs.e2fs_first_ino = EXT2_FIRSTINO;
 403         sblock.e2fs.e2fs_inode_size = inodesize;
 404
 405         /* e2fs_block_group_nr is set on writing superblock to each group */
 406
 407         uuid_get(&sblock);
 408         if (volname != NULL) {
 409                 if (strlen(volname) > sizeof(sblock.e2fs.e2fs_vname))
 410                         errx(EXIT_FAILURE, "Volume name is too long");
 411                 strlcpy(sblock.e2fs.e2fs_vname, volname,
 412                     sizeof(sblock.e2fs.e2fs_vname));
 413         }
 414
 415         sblock.e2fs.e2fs_fsmnt[0] = '\0';
 416         sblock.e2fs_fsmnt[0] = '\0';
 417
 418         sblock.e2fs.e2fs_algo = 0;              /* XXX unsupported? */
 419         sblock.e2fs.e2fs_prealloc = 0;          /* XXX unsupported? */
 420         sblock.e2fs.e2fs_dir_prealloc = 0;      /* XXX unsupported? */
 421
 422         /* calculate blocks for reserved group descriptors for resize */
 423         sblock.e2fs.e2fs_reserved_ngdb = 0;
 424         if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 425             (sblock.e2fs.e2fs_features_compat & EXT2F_COMPAT_RESIZE) != 0) {
 426                 uint64_t target_blocks;
 427                 uint target_ncg, target_ngdb, reserved_ngdb;
 428
 429                 /* reserve descriptors for size as 1024 times as current */
 430                 target_blocks =
 431                     (sblock.e2fs.e2fs_bcount - sblock.e2fs.e2fs_first_dblock)
 432                     * 1024ULL;
 433                 /* number of blocks must be in uint32_t */
 434                 if (target_blocks > UINT32_MAX)
 435                         target_blocks = UINT32_MAX;
 436                 target_ncg = howmany(target_blocks, sblock.e2fs.e2fs_bpg);
 437                 target_ngdb = howmany(sizeof(struct ext2_gd) * target_ncg,
 438                     sblock.e2fs_bsize);
 439                 /*
 440                  * Reserved group descriptor blocks are preserved as
 441                  * the second level double indirect reference blocks in
 442                  * the EXT2_RESIZEINO inode, so the maximum number of
 443                  * the blocks is NINDIR(fs).
 444                  * (see also descriptions in init_resizeino() function)
 445                  *
 446                  * We check a number including current e2fs_ngdb here
 447                  * because they will be moved into reserved gdb on
 448                  * possible future size shrink, though e2fsprogs don't
 449                  * seem to care about it.
 450                  */
 451                 if (target_ngdb > NINDIR(&sblock))
 452                         target_ngdb = NINDIR(&sblock);
 453
 454                 reserved_ngdb = target_ngdb - sblock.e2fs_ngdb;
 455
 456                 /* make sure reserved_ngdb fits in the last cg */
 457                 if (reserved_ngdb >= blocks_lastcg - cgoverhead(ncg - 1))
 458                         reserved_ngdb = blocks_lastcg - cgoverhead(ncg - 1);
 459                 if (reserved_ngdb == 0) {
 460                         /* if no space for reserved gdb, disable the feature */
 461                         sblock.e2fs.e2fs_features_compat &=
 462                             ~EXT2F_COMPAT_RESIZE;
 463                 }
 464                 sblock.e2fs.e2fs_reserved_ngdb = reserved_ngdb;
 465         }
 466
 467         /*
 468          * Initialize group descriptors
 469          */
 470         gd = malloc(sblock.e2fs_ngdb * bsize);
 471         if (gd == NULL)
 472                 errx(EXIT_FAILURE, "Can't allocate descriptors buffer");
 473         memset(gd, 0, sblock.e2fs_ngdb * bsize);
 474
 475         fbcount = 0;
 476         ficount = 0;
 477         for (cylno = 0; cylno < ncg; cylno++) {
 478                 uint boffset;
 479
 480                 boffset = cgbase(&sblock, cylno);
 481                 if (sblock.e2fs.e2fs_rev == E2FS_REV0 ||
 482                     (sblock.e2fs.e2fs_features_rocompat &
 483                      EXT2F_ROCOMPAT_SPARSESUPER) == 0 ||
 484                     cg_has_sb(cylno)) {
 485                         boffset += NBLOCK_SUPERBLOCK + sblock.e2fs_ngdb;
 486                         if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 487                             (sblock.e2fs.e2fs_features_compat &
 488                              EXT2F_COMPAT_RESIZE) != 0)
 489                                 boffset += sblock.e2fs.e2fs_reserved_ngdb;
 490                 }
 491                 gd[cylno].ext2bgd_b_bitmap = boffset;
 492                 boffset += NBLOCK_BLOCK_BITMAP;
 493                 gd[cylno].ext2bgd_i_bitmap = boffset;
 494                 boffset += NBLOCK_INODE_BITMAP;
 495                 gd[cylno].ext2bgd_i_tables = boffset;
 496                 if (cylno == (ncg - 1))
 497                         gd[cylno].ext2bgd_nbfree =
 498                             blocks_lastcg - cgoverhead(cylno);
 499                 else
 500                         gd[cylno].ext2bgd_nbfree =
 501                             sblock.e2fs.e2fs_bpg - cgoverhead(cylno);
 502                 fbcount += gd[cylno].ext2bgd_nbfree;
 503                 gd[cylno].ext2bgd_nifree = sblock.e2fs.e2fs_ipg;
 504                 if (cylno == 0) {
 505                         /* take reserved inodes off nifree */
 506                         gd[cylno].ext2bgd_nifree -= EXT2_RESERVED_INODES;
 507                 }
 508                 ficount += gd[cylno].ext2bgd_nifree;
 509                 gd[cylno].ext2bgd_ndirs = 0;
 510         }
 511         sblock.e2fs.e2fs_fbcount = fbcount;
 512         sblock.e2fs.e2fs_ficount = ficount;
 513
 514         /*
 515          * Dump out summary information about file system.
 516          */
 517         if (verbosity > 0) {
 518                 printf("%s: %u.%1uMB (%" PRId64 " sectors) "
 519                     "block size %u, fragment size %u\n",
 520                     fsys,
 521                     (uint)(((uint64_t)bcount * bsize) / (1024 * 1024)),
 522                     (uint)((uint64_t)bcount * bsize -
 523                     rounddown((uint64_t)bcount * bsize, 1024 * 1024))
 524                     / 1024 / 100,
 525                     fssize, bsize, fsize);
 526                 printf("\tusing %u block groups of %u.0MB, %u blks, "
 527                     "%u inodes.\n",
 528                     ncg, bsize * sblock.e2fs.e2fs_bpg / (1024 * 1024),
 529                     sblock.e2fs.e2fs_bpg, sblock.e2fs.e2fs_ipg);
 530         }
 531
 532         /*
 533          * allocate space for superblock and group descriptors
 534          */
 535         iobufsize = (NBLOCK_SUPERBLOCK + sblock.e2fs_ngdb) * sblock.e2fs_bsize;
 536         iobuf = mmap(0, iobufsize, PROT_READ|PROT_WRITE,
 537             MAP_ANON|MAP_PRIVATE, -1, 0);
 538         if (iobuf == NULL)
 539                 errx(EXIT_FAILURE, "Cannot allocate I/O buffer\n");
 540         memset(iobuf, 0, iobufsize);
 541
 542         /*
 543          * We now start writing to the filesystem
 544          */
 545
 546         if (!Nflag) {
 547                 static const uint pbsize[] = { 1024, 2048, 4096, 0 };
 548                 uint pblock, epblock;
 549                 /*
 550                  * Validate the given file system size.
 551                  * Verify that its last block can actually be accessed.
 552                  * Convert to file system fragment sized units.
 553                  */
 554                 if (fssize <= 0)
 555                         errx(EXIT_FAILURE, "Preposterous size %" PRId64 "\n",
 556                             fssize);
 557                 wtfs(fssize - 1, sectorsize, iobuf);
 558
 559                 /*
 560                  * Ensure there is nothing that looks like a filesystem
 561                  * superblock anywhere other than where ours will be.
 562                  * If fsck_ext2fs finds the wrong one all hell breaks loose!
 563                  *
 564                  * XXX: needs to check how fsck_ext2fs programs even
 565                  *      on other OSes determine alternate superblocks
 566                  */
 567                 for (i = 0; pbsize[i] != 0; i++) {
 568                         epblock = (uint64_t)bcount * bsize / pbsize[i];
 569                         for (pblock = ((pbsize[i] == SBSIZE) ? 1 : 0);
 570                             pblock < epblock;
 571                             pblock += pbsize[i] * NBBY /* bpg */)
 572                                 zap_old_sblock((daddr_t)pblock *
 573                                     pbsize[i] / sectorsize);
 574                 }
 575         }
 576
 577         if (verbosity >= 3)
 578                 printf("super-block backups (for fsck_ext2fs -b #) at:\n");
 579         /* If we are printing more than one line of numbers, line up columns */
 580         fld_width = verbosity < 4 ? 1 : snprintf(NULL, 0, "%" PRIu64,
 581             (uint64_t)cgbase(&sblock, ncg - 1));
 582         /* Get terminal width */
 583         if (ioctl(fileno(stdout), TIOCGWINSZ, &winsize) == 0)
 584                 max_cols = winsize.ws_col;
 585         else
 586                 max_cols = 80;
 587         if (Nflag && verbosity == 3)
 588                 /* Leave space to add " ..." after one row of numbers */
 589                 max_cols -= 4;
 590 #define BASE 0x10000    /* For some fixed-point maths */
 591         col = 0;
 592         delta = verbosity > 2 ? 0 : max_cols * BASE / ncg;
 593         for (cylno = 0; cylno < ncg; cylno++) {
 594                 fflush(stdout);
 595                 initcg(cylno);
 596                 if (verbosity < 2)
 597                         continue;
 598                 /* the first one is a master, not backup */
 599                 if (cylno == 0)
 600                         continue;
 601                 /* skip if this cylinder doesn't have a backup */
 602                 if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 603                     (sblock.e2fs.e2fs_features_rocompat &
 604                      EXT2F_ROCOMPAT_SPARSESUPER) != 0 &&
 605                     cg_has_sb(cylno) == 0)
 606                         continue;
 607
 608                 if (delta > 0) {
 609                         if (Nflag)
 610                                 /* No point doing dots for -N */
 611                                 break;
 612                         /* Print dots scaled to end near RH margin */
 613                         for (col += delta; col > BASE; col -= BASE)
 614                                 printf(".");
 615                         continue;
 616                 }
 617                 /* Print superblock numbers */
 618                 len = printf(" %*" PRIu64 "," + !col, fld_width,
 619                     (uint64_t)cgbase(&sblock, cylno));
 620                 col += len;
 621                 if (col + len < max_cols)
 622                         /* Next number fits */
 623                         continue;
 624                 /* Next number won't fit, need a newline */
 625                 if (verbosity <= 3) {
 626                         /* Print dots for subsequent cylinder groups */
 627                         delta = sblock.e2fs_ncg - cylno - 1;
 628                         if (delta != 0) {
 629                                 if (Nflag) {
 630                                         printf(" ...");
 631                                         break;
 632                                 }
 633                                 delta = max_cols * BASE / delta;
 634                         }
 635                 }
 636                 col = 0;
 637                 printf("\n");
 638         }
 639 #undef BASE
 640         if (col > 0)
 641                 printf("\n");
 642         if (Nflag)
 643                 return;
 644
 645         /*
 646          * Now construct the initial file system,
 647          */
 648         if (fsinit(&tv) == 0)
 649                 errx(EXIT_FAILURE, "Error making filesystem");
 650         /*
 651          * Write out the superblock and group descriptors
 652          */
 653         sblock.e2fs.e2fs_block_group_nr = 0;
 654         sboff = 0;
 655         if (cgbase(&sblock, 0) == 0) {
 656                 /*
 657                  * If the first block contains the boot block sectors,
 658                  * (i.e. in case of sblock.e2fs.e2fs_bsize > BBSIZE)
 659                  * we have to preserve data in it.
 660                  */
 661                 sboff = SBOFF;
 662         }
 663         e2fs_sbsave(&sblock.e2fs, (struct ext2fs *)(iobuf + sboff));
 664         e2fs_cgsave(gd, (struct ext2_gd *)(iobuf + sblock.e2fs_bsize),
 665            sizeof(struct ext2_gd) * sblock.e2fs_ncg);
 666         wtfs(fsbtodb(&sblock, cgbase(&sblock, 0)) + sboff / sectorsize,
 667             iobufsize - sboff, iobuf + sboff);
 668
 669         munmap(iobuf, iobufsize);
 670 }
 671
 672 /*
 673  * Initialize a cylinder (block) group.
 674  */
 675 void
 676 initcg(uint cylno)
 677 {
 678         uint nblcg, i, j, sboff;
 679         struct ext2fs_dinode *dp;
 680
 681         /*
 682          * Make a copy of the superblock and group descriptors.
 683          */
 684         if (sblock.e2fs.e2fs_rev == E2FS_REV0 ||
 685             (sblock.e2fs.e2fs_features_rocompat &
 686              EXT2F_ROCOMPAT_SPARSESUPER) == 0 ||
 687             cg_has_sb(cylno)) {
 688                 sblock.e2fs.e2fs_block_group_nr = cylno;
 689                 sboff = 0;
 690                 if (cgbase(&sblock, cylno) == 0) {
 691                         /* preserve data in bootblock in cg0 */
 692                         sboff = SBOFF;
 693                 }
 694                 e2fs_sbsave(&sblock.e2fs, (struct ext2fs *)(iobuf + sboff));
 695                 e2fs_cgsave(gd, (struct ext2_gd *)(iobuf +
 696                     sblock.e2fs_bsize * NBLOCK_SUPERBLOCK),
 697                     sizeof(struct ext2_gd) * sblock.e2fs_ncg);
 698                 /* write superblock and group descriptor backups */
 699                 wtfs(fsbtodb(&sblock, cgbase(&sblock, cylno)) +
 700                     sboff / sectorsize, iobufsize - sboff, iobuf + sboff);
 701         }
 702
 703         /*
 704          * Initialize block bitmap.
 705          */
 706         memset(buf, 0, sblock.e2fs_bsize);
 707         if (cylno == (sblock.e2fs_ncg - 1)) {
 708                 /* The last group could have less blocks than e2fs_bpg. */
 709                 nblcg = sblock.e2fs.e2fs_bcount -
 710                     cgbase(&sblock, sblock.e2fs_ncg - 1);
 711                 for (i = nblcg; i < roundup(nblcg, NBBY); i++)
 712                         setbit(buf, i);
 713                 memset(&buf[i / NBBY], ~0U, sblock.e2fs.e2fs_bpg - i);
 714         }
 715         /* set overhead (superblock, group descriptor etc.) blocks used */
 716         for (i = 0; i < cgoverhead(cylno) / NBBY; i++)
 717                 buf[i] = ~0;
 718         i = i * NBBY;
 719         for (; i < cgoverhead(cylno); i++)
 720                 setbit(buf, i);
 721         wtfs(fsbtodb(&sblock, gd[cylno].ext2bgd_b_bitmap), sblock.e2fs_bsize,
 722             buf);
 723
 724         /*
 725          * Initialize inode bitmap.
 726          *
 727          *  Assume e2fs_ipg is a multiple of NBBY since
 728          *  it's a multiple of e2fs_ipb (as we did above).
 729          *  Note even (possibly smaller) the last group has the same e2fs_ipg.
 730          */
 731         i = sblock.e2fs.e2fs_ipg / NBBY;
 732         memset(buf, 0, i);
 733         memset(buf + i, ~0U, sblock.e2fs_bsize - i);
 734         if (cylno == 0) {
 735                 /* mark reserved inodes */
 736                 for (i = 1; i < EXT2_FIRSTINO; i++)
 737                         setbit(buf, EXT2_INO_INDEX(i));
 738         }
 739         wtfs(fsbtodb(&sblock, gd[cylno].ext2bgd_i_bitmap), sblock.e2fs_bsize,
 740             buf);
 741
 742         /*
 743          * Initialize inode tables.
 744          *
 745          *  Just initialize generation numbers for NFS security.
 746          *  XXX: sys/ufs/ext2fs/ext2fs_alloc.c:ext2fs_valloc() seems
 747          *       to override these generated numbers.
 748          */
 749         memset(buf, 0, sblock.e2fs_bsize);
 750         for (i = 0; i < sblock.e2fs_itpg; i++) {
 751                 for (j = 0; j < sblock.e2fs_ipb; j++) {
 752                         dp = (struct ext2fs_dinode *)(buf + inodesize * j);
 753                         /* h2fs32() just for consistency */
 754                         dp->e2di_gen = h2fs32(arc4random());
 755                 }
 756                 wtfs(fsbtodb(&sblock, gd[cylno].ext2bgd_i_tables + i),
 757                     sblock.e2fs_bsize, buf);
 758         }
 759 }
 760
 761 /*
 762  * Zap possible lingering old superblock data
 763  */
 764 static void
 765 zap_old_sblock(daddr_t sec)
 766 {
 767         static daddr_t cg0_data;
 768         uint32_t oldfs[SBSIZE / sizeof(uint32_t)];
 769         static const struct fsm {
 770                 uint32_t offset;
 771                 uint32_t magic;
 772                 uint32_t mask;
 773         } fs_magics[] = {
 774                 {offsetof(struct ext2fs, e2fs_magic) / 4, E2FS_MAGIC, 0xffff},
 775                 {offsetof(struct ext2fs, e2fs_magic) / 4,
 776                     E2FS_MAGIC << 16, 0xffff0000},
 777                 {14, 0xef530000, 0xffff0000},   /* EXT2FS (big) */
 778                 {0x55c / 4, 0x00011954, ~0U},   /* FS_UFS1_MAGIC */
 779                 {0x55c / 4, 0x19540119, ~0U},   /* FS_UFS2_MAGIC */
 780                 {0, 0x70162, ~0U},              /* LFS_MAGIC */
 781                 {.offset = ~0U},
 782         };
 783         const struct fsm *fsm;
 784
 785         if (Nflag)
 786                 return;
 787
 788         /* don't override data before superblock */
 789         if (sec < SBOFF / sectorsize)
 790                 return;
 791
 792         if (cg0_data == 0) {
 793                 cg0_data =
 794                     ((daddr_t)sblock.e2fs.e2fs_first_dblock + cgoverhead(0)) *
 795                     sblock.e2fs_bsize / sectorsize;
 796         }
 797
 798         /* Ignore anything that is beyond our filesystem */
 799         if (sec >= fssize)
 800                 return;
 801         /* Zero anything inside our filesystem... */
 802         if (sec >= sblock.e2fs.e2fs_first_dblock * bsize / sectorsize) {
 803                 /* ...unless we will write that area anyway */
 804                 if (sec >= cg0_data)
 805                         /* assume iobuf is zero'ed here */
 806                         wtfs(sec, roundup(SBSIZE, sectorsize), iobuf);
 807                 return;
 808         }
 809
 810         /*
 811          * The sector might contain boot code, so we must validate it
 812          *
 813          * XXX: ext2fs won't preserve data after SBOFF,
 814          *      but first_dblock could have a different value.
 815          */
 816         rdfs(sec, sizeof(oldfs), &oldfs);
 817         for (fsm = fs_magics;; fsm++) {
 818                 uint32_t v;
 819                 if (fsm->mask == 0)
 820                         return;
 821                 v = oldfs[fsm->offset];
 822                 if ((v & fsm->mask) == fsm->magic ||
 823                     (swap32(v) & fsm->mask) == fsm->magic)
 824                         break;
 825         }
 826
 827         /* Just zap the magic number */
 828         oldfs[fsm->offset] = 0;
 829         wtfs(sec, sizeof(oldfs), &oldfs);
 830 }
 831
 832 /*
 833  * uint cgoverhead(uint c)
 834  *
 835  *      Return a number of reserved blocks on the specified group.
 836  *      XXX: should be shared with src/sbin/fsck_ext2fs/setup.c
 837  */
 838 uint
 839 cgoverhead(uint c)
 840 {
 841         uint overh;
 842
 843         overh = NBLOCK_BLOCK_BITMAP + NBLOCK_INODE_BITMAP + sblock.e2fs_itpg;
 844
 845         if (sblock.e2fs.e2fs_rev == E2FS_REV0 ||
 846             (sblock.e2fs.e2fs_features_rocompat &
 847              EXT2F_ROCOMPAT_SPARSESUPER) == 0 ||
 848             cg_has_sb(c) != 0) {
 849                 overh += NBLOCK_SUPERBLOCK + sblock.e2fs_ngdb;
 850
 851                 if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 852                     (sblock.e2fs.e2fs_features_compat &
 853                      EXT2F_COMPAT_RESIZE) != 0)
 854                         overh += sblock.e2fs.e2fs_reserved_ngdb;
 855         }
 856
 857         return overh;
 858 }
 859
 860 /*
 861  * Initialize the file system
 862  */
 863
 864 #define LOSTDIR         /* e2fsck complains if there is no lost+found */
 865
 866 #define PREDEFDIR       2
 867
 868 #ifdef LOSTDIR
 869 #define PREDEFROOTDIR   (PREDEFDIR + 1)
 870 #else
 871 #define PREDEFROOTDIR   PREDEFDIR
 872 #endif
 873
 874 struct ext2fs_direct root_dir[] = {
 875         { EXT2_ROOTINO, 0, 1, 0, "." },
 876         { EXT2_ROOTINO, 0, 2, 0, ".." },
 877 #ifdef LOSTDIR
 878         { EXT2_LOSTFOUNDINO, 0, 10, 0, "lost+found" },
 879 #endif
 880 };
 881
 882 #ifdef LOSTDIR
 883 struct ext2fs_direct lost_found_dir[] = {
 884         { EXT2_LOSTFOUNDINO, 0, 1, 0, "." },
 885         { EXT2_ROOTINO, 0, 2, 0, ".." },
 886 };
 887 struct ext2fs_direct pad_dir = { 0, sizeof(struct ext2fs_direct), 0, 0, "" };
 888 #endif
 889
 890 int
 891 fsinit(const struct timeval *tv)
 892 {
 893         struct ext2fs_dinode node;
 894 #ifdef LOSTDIR
 895         uint i, nblks_lostfound, blk;
 896 #endif
 897
 898         /*
 899          * Initialize the inode for the resizefs feature
 900          */
 901         if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 902             (sblock.e2fs.e2fs_features_compat & EXT2F_COMPAT_RESIZE) != 0)
 903                 init_resizeino(tv);
 904
 905         /*
 906          * Initialize the node
 907          */
 908
 909 #ifdef LOSTDIR
 910         /*
 911          * Create the lost+found directory
 912          */
 913         if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 914             sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE) {
 915                 lost_found_dir[0].e2d_type = EXT2_FT_DIR;
 916                 lost_found_dir[1].e2d_type = EXT2_FT_DIR;
 917         }
 918         (void)makedir(lost_found_dir, nitems(lost_found_dir));
 919
 920         /* prepare a bit large directory for preserved files */
 921         nblks_lostfound = EXT2_LOSTFOUNDSIZE / sblock.e2fs_bsize;
 922         /* ...but only with direct blocks */
 923         if (nblks_lostfound > NDADDR)
 924                 nblks_lostfound = NDADDR;
 925
 926         memset(&node, 0, sizeof(node));
 927         node.e2di_mode = EXT2_IFDIR | EXT2_LOSTFOUNDUMASK;
 928         node.e2di_uid_low = geteuid();
 929         node.e2di_size = sblock.e2fs_bsize * nblks_lostfound;
 930         node.e2di_atime = tv->tv_sec;
 931         node.e2di_ctime = tv->tv_sec;
 932         node.e2di_mtime = tv->tv_sec;
 933         node.e2di_gid_low = getegid();
 934         node.e2di_nlink = PREDEFDIR;
 935         /* e2di_nblock is a number of disk blocks, not ext2fs blocks */
 936         node.e2di_nblock = fsbtodb(&sblock, nblks_lostfound);
 937         node.e2di_blocks[0] = alloc(sblock.e2fs_bsize, node.e2di_mode);
 938         if (node.e2di_blocks[0] == 0) {
 939                 printf("%s: can't allocate block for lost+found\n", __func__);
 940                 return 0;
 941         }
 942         for (i = 1; i < nblks_lostfound; i++) {
 943                 blk = alloc(sblock.e2fs_bsize, 0);
 944                 if (blk == 0) {
 945                         printf("%s: can't allocate blocks for lost+found\n",
 946                             __func__);
 947                         return 0;
 948                 }
 949                 node.e2di_blocks[i] = blk;
 950         }
 951         wtfs(fsbtodb(&sblock, node.e2di_blocks[0]), sblock.e2fs_bsize, buf);
 952         pad_dir.e2d_reclen = sblock.e2fs_bsize;
 953         for (i = 1; i < nblks_lostfound; i++) {
 954                 memset(buf, 0, sblock.e2fs_bsize);
 955                 copy_dir(&pad_dir, (struct ext2fs_direct *)buf);
 956                 wtfs(fsbtodb(&sblock, node.e2di_blocks[i]), sblock.e2fs_bsize,
 957                     buf);
 958         }
 959         iput(&node, EXT2_LOSTFOUNDINO);
 960 #endif
 961         /*
 962          * create the root directory
 963          */
 964         memset(&node, 0, sizeof(node));
 965         if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 966             sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE) {
 967                 root_dir[0].e2d_type = EXT2_FT_DIR;
 968                 root_dir[1].e2d_type = EXT2_FT_DIR;
 969 #ifdef LOSTDIR
 970                 root_dir[2].e2d_type = EXT2_FT_DIR;
 971 #endif
 972         }
 973         node.e2di_mode = EXT2_IFDIR | EXT2_UMASK;
 974         node.e2di_uid_low = geteuid();
 975         node.e2di_size = makedir(root_dir, nitems(root_dir));
 976         node.e2di_atime = tv->tv_sec;
 977         node.e2di_ctime = tv->tv_sec;
 978         node.e2di_mtime = tv->tv_sec;
 979         node.e2di_gid_low = getegid();
 980         node.e2di_nlink = PREDEFROOTDIR;
 981         /* e2di_nblock is a number of disk block, not ext2fs block */
 982         node.e2di_nblock = fsbtodb(&sblock, 1);
 983         node.e2di_blocks[0] = alloc(node.e2di_size, node.e2di_mode);
 984         if (node.e2di_blocks[0] == 0) {
 985                 printf("%s: can't allocate block for root dir\n", __func__);
 986                 return 0;
 987         }
 988         wtfs(fsbtodb(&sblock, node.e2di_blocks[0]), sblock.e2fs_bsize, buf);
 989         iput(&node, EXT2_ROOTINO);
 990         return 1;
 991 }
 992
 993 /*
 994  * Construct a set of directory entries in "buf".
 995  * return size of directory.
 996  */
 997 int
 998 makedir(struct ext2fs_direct *protodir, int entries)
 999 {
1000         uint8_t *cp;
1001         uint i, spcleft;
1002         uint dirblksiz;
1003
1004         dirblksiz = sblock.e2fs_bsize;
1005         memset(buf, 0, dirblksiz);
1006         spcleft = dirblksiz;
1007         for (cp = buf, i = 0; i < entries - 1; i++) {
1008                 protodir[i].e2d_reclen = EXT2FS_DIRSIZ(protodir[i].e2d_namlen);
1009                 copy_dir(&protodir[i], (struct ext2fs_direct *)cp);
1010                 cp += protodir[i].e2d_reclen;
1011                 spcleft -= protodir[i].e2d_reclen;
1012         }
1013         protodir[i].e2d_reclen = spcleft;
1014         copy_dir(&protodir[i], (struct ext2fs_direct *)cp);
1015         return dirblksiz;
1016 }
1017
1018 /*
1019  * Copy a direntry to a buffer, in fs byte order
1020  */
1021 static void
1022 copy_dir(struct ext2fs_direct *dir, struct ext2fs_direct *dbuf)
1023 {
1024
1025         memcpy(dbuf, dir, EXT2FS_DIRSIZ(dir->e2d_namlen));
1026         dbuf->e2d_ino = h2fs32(dir->e2d_ino);
1027         dbuf->e2d_reclen = h2fs16(dir->e2d_reclen);
1028 }
1029
1030 /*
1031  * void init_resizeino(const struct timeval *tv);
1032  *
1033  *      Initialize the EXT2_RESEIZE_INO inode to preserve
1034  *      reserved group descriptor blocks for future growth of this ext2fs.
1035  */
1036 void
1037 init_resizeino(const struct timeval *tv)
1038 {
1039         struct ext2fs_dinode node;
1040         uint64_t isize;
1041         uint32_t *dindir_block, *reserved_gdb;
1042         uint nblock, i, cylno, n;
1043
1044         memset(&node, 0, sizeof(node));
1045
1046         /*
1047          * Note this function only prepares required structures for
1048          * future resize. It's a quite different work to implement
1049          * a utility like resize_ext2fs(8) which handles actual
1050          * resize ops even on offline.
1051          *
1052          * Anyway, I'm not sure if there is any documentation about
1053          * this resize ext2fs feature and related data structures,
1054          * and I've written this function based on things what I see
1055          * on some existing implementation and real file system data
1056          * created by existing tools. To be honest, they are not
1057          * so easy to read, so I will try to implement it here without
1058          * any dumb optimization for people who would eventually
1059          * work on "yet another wheel" like resize_ext2fs(8).
1060          */
1061
1062         /*
1063          * I'm not sure what type is appropriate for this inode.
1064          * The release notes of e2fsprogs says they changed e2fsck to allow
1065          * IFREG for RESIZEINO since a certain resize tool used it. Hmm.
1066          */
1067         node.e2di_mode = EXT2_IFREG | EXT2_RESIZEINOUMASK;
1068         node.e2di_uid_low = geteuid();
1069         node.e2di_atime = tv->tv_sec;
1070         node.e2di_ctime = tv->tv_sec;
1071         node.e2di_mtime = tv->tv_sec;
1072         node.e2di_gid_low = getegid();
1073         node.e2di_nlink = 1;
1074
1075         /*
1076          * To preserve the reserved group descriptor blocks,
1077          * EXT2_RESIZEINO uses only double indirect reference
1078          * blocks in its inode entries.
1079          *
1080          * All entries for direct, single indirect and triple
1081          * indirect references are left zero'ed. Maybe it's safe
1082          * because no write operation will happen with this inode.
1083          *
1084          * We have to allocate a block for the first level double
1085          * indirect reference block. Indexes of inode entries in
1086          * this first level dindirect block are corresponding to
1087          * indexes of group descriptors including both used (e2fs_ngdb)
1088          * and reserved (e2fs_reserved_ngdb) group descriptor blocks.
1089          *
1090          * Inode entries of indexes for used (e2fs_ngdb) descriptors are
1091          * left zero'ed. Entries for reserved (e2fs_reserved_ngdb) ones
1092          * have block numbers of actual reserved group descriptors
1093          * allocated at block group zero. This means e2fs_reserved_ngdb
1094          * blocks are reserved as the second level dindirect reference
1095          * blocks, and they actually contain block numbers of indirect
1096          * references. It may be safe since they don't have to keep any
1097          * data yet.
1098          *
1099          * Each these second dindirect blocks (i.e. reserved group
1100          * descriptor blocks in the first block group) should have
1101          * block numbers of its backups in all other block groups.
1102          * I.e. reserved_ngdb[0] block in block group 0 contains block
1103          * numbers of resreved_ngdb[0] from group 1 through (e2fs_ncg - 1).
1104          * The number of backups can be determined by the
1105          * EXT2_ROCOMPAT_SPARSESUPER feature and cg_has_sb() macro
1106          * as done in the above initcg() function.
1107          */
1108
1109         /* set e2di_size which occupies whole blocks through DINDIR blocks */
1110         isize = (uint64_t)sblock.e2fs_bsize * NDADDR +
1111             (uint64_t)sblock.e2fs_bsize * NINDIR(&sblock) +
1112             (uint64_t)sblock.e2fs_bsize * NINDIR(&sblock) * NINDIR(&sblock);
1113         if (isize > UINT32_MAX &&
1114             (sblock.e2fs.e2fs_features_rocompat &
1115              EXT2F_ROCOMPAT_LARGEFILE) == 0) {
1116                 /* XXX should enable it here and update all backups? */
1117                 errx(EXIT_FAILURE, "%s: large_file rocompat feature is "
1118                     "required to enable resize feature for this filesystem\n",
1119                     __func__);
1120         }
1121         /* upper 32bit is stored into e2di_dacl on REV1 feature */
1122         node.e2di_size = isize & UINT32_MAX;
1123         node.e2di_dacl = isize >> 32;
1124
1125 #define SINGLE  0       /* index of single indirect block */
1126 #define DOUBLE  1       /* index of double indirect block */
1127 #define TRIPLE  2       /* index of triple indirect block */
1128
1129         /* zero out entries for direct references */
1130         for (i = 0; i < NDADDR; i++)
1131                 node.e2di_blocks[i] = 0;
1132         /* also zero out entries for single and triple indirect references */
1133         node.e2di_blocks[NDADDR + SINGLE] = 0;
1134         node.e2di_blocks[NDADDR + TRIPLE] = 0;
1135
1136         /* allocate a block for the first level double indirect reference */
1137         node.e2di_blocks[NDADDR + DOUBLE] =
1138             alloc(sblock.e2fs_bsize, node.e2di_mode);
1139         if (node.e2di_blocks[NDADDR + DOUBLE] == 0)
1140                 errx(EXIT_FAILURE, "%s: Can't allocate a dindirect block",
1141                     __func__);
1142
1143         /* account this first block */
1144         nblock = fsbtodb(&sblock, 1);
1145
1146         /* allocate buffer to set data in the dindirect block */
1147         dindir_block = malloc(sblock.e2fs_bsize);
1148         if (dindir_block == NULL)
1149                 errx(EXIT_FAILURE,
1150                     "%s: Can't allocate buffer for a dindirect block",
1151                     __func__);
1152
1153         /* allocate buffer to set data in the group descriptor blocks */
1154         reserved_gdb = malloc(sblock.e2fs_bsize);
1155         if (reserved_gdb == NULL)
1156                 errx(EXIT_FAILURE,
1157                     "%s: Can't allocate buffer for group descriptor blocks",
1158                     __func__);
1159
1160         /*
1161          * Setup block entries in the first level dindirect blocks
1162          */
1163         for (i = 0; i < sblock.e2fs_ngdb; i++) {
1164                 /* no need to handle used group descriptor blocks */
1165                 dindir_block[i] = 0;
1166         }
1167         for (; i < sblock.e2fs_ngdb + sblock.e2fs.e2fs_reserved_ngdb; i++) {
1168                 /*
1169                  * point reserved group descriptor block in the first
1170                  * (i.e. master) block group
1171                  *
1172                  * XXX: e2fsprogs seem to use "(i % NINDIR(&sblock))" here
1173                  *      to store maximum NINDIR(&sblock) reserved gdbs.
1174                  *      I'm not sure what will be done on future filesystem
1175                  *      shrink in that case on their way.
1176                  */
1177                 if (i >= NINDIR(&sblock))
1178                         errx(EXIT_FAILURE, "%s: too many reserved "
1179                             "group descriptors (%u) for resize inode",
1180                             __func__, sblock.e2fs.e2fs_reserved_ngdb);
1181                 dindir_block[i] =
1182                     h2fs32(cgbase(&sblock, 0) + NBLOCK_SUPERBLOCK + i);
1183
1184                 /*
1185                  * Setup block entries in the second dindirect blocks
1186                  * (which are primary reserved group descriptor blocks)
1187                  * to point their backups.
1188                  */
1189                 for (n = 0, cylno = 1; cylno < sblock.e2fs_ncg; cylno++) {
1190                         /* skip block groups without backup */
1191                         if ((sblock.e2fs.e2fs_features_rocompat &
1192                              EXT2F_ROCOMPAT_SPARSESUPER) != 0 &&
1193                             cg_has_sb(cylno) == 0)
1194                                 continue;
1195
1196                         if (n >= NINDIR(&sblock))
1197                                 errx(EXIT_FAILURE, "%s: too many block groups "
1198                                     "for the resize feature", __func__);
1199                         /*
1200                          * These blocks are already reserved in
1201                          * initcg() so no need to use alloc() here.
1202                          */
1203                         reserved_gdb[n++] = h2fs32(cgbase(&sblock, cylno) +
1204                             NBLOCK_SUPERBLOCK + i);
1205                         nblock += fsbtodb(&sblock, 1);
1206                 }
1207                 for (; n < NINDIR(&sblock); n++)
1208                         reserved_gdb[n] = 0;
1209
1210                 /* write group descriptor block as the second dindirect refs */
1211                 wtfs(fsbtodb(&sblock, fs2h32(dindir_block[i])),
1212                     sblock.e2fs_bsize, reserved_gdb);
1213                 nblock += fsbtodb(&sblock, 1);
1214         }
1215         for (; i < NINDIR(&sblock); i++) {
1216                 /* leave trailing entries unallocated */
1217                 dindir_block[i] = 0;
1218         }
1219         free(reserved_gdb);
1220
1221         /* finally write the first level dindirect block */
1222         wtfs(fsbtodb(&sblock, node.e2di_blocks[NDADDR + DOUBLE]),
1223             sblock.e2fs_bsize, dindir_block);
1224         free(dindir_block);
1225
1226         node.e2di_nblock = nblock;
1227         iput(&node, EXT2_RESIZEINO);
1228 }
1229
1230 /*
1231  * uint32_t alloc(uint32_t size, uint16_t mode)
1232  *
1233  *      Allocate a block (from cylinder group 0)
1234  *      Reference: src/sys/ufs/ext2fs/ext2fs_alloc.c:ext2fs_alloccg()
1235  */
1236 uint32_t
1237 alloc(uint32_t size, uint16_t mode)
1238 {
1239         uint32_t loc, bno;
1240         uint8_t *bbp;
1241         uint len, map, i;
1242
1243         if (gd[0].ext2bgd_nbfree == 0)
1244                 return 0;
1245
1246         if (size > sblock.e2fs_bsize)
1247                 return 0;
1248
1249         bbp = malloc(sblock.e2fs_bsize);
1250         if (bbp == NULL)
1251                 return 0;
1252         rdfs(fsbtodb(&sblock, gd[0].ext2bgd_b_bitmap), sblock.e2fs_bsize, bbp);
1253
1254         /* XXX: kernel uses e2fs_fpg here */
1255         len = sblock.e2fs.e2fs_bpg / NBBY;
1256
1257 #if 0   /* no need block allocation for root or lost+found dir */
1258         for (loc = 0; loc < len; loc++) {
1259                 if (bbp[loc] == 0) {
1260                         bno = loc * NBBY;
1261                         goto gotit;
1262                 }
1263         }
1264 #endif
1265
1266         loc = skpc(~0U, len, bbp);
1267         if (loc == 0)
1268                 return 0;
1269         loc = len - loc;
1270         map = bbp[loc];
1271         bno = loc * NBBY;
1272         for (i = 0; i < NBBY; i++, bno++) {
1273                 if ((map & (1 << i)) == 0)
1274                         goto gotit;
1275         }
1276         return 0;
1277
1278  gotit:
1279         if (isset(bbp, bno))
1280                 errx(EXIT_FAILURE, "%s: inconsistent bitmap\n", __func__);
1281
1282         setbit(bbp, bno);
1283         wtfs(fsbtodb(&sblock, gd[0].ext2bgd_b_bitmap), sblock.e2fs_bsize, bbp);
1284         free(bbp);
1285         /* XXX: modified group descriptors won't be written into backups */
1286         gd[0].ext2bgd_nbfree--;
1287         if ((mode & EXT2_IFDIR) != 0)
1288                 gd[0].ext2bgd_ndirs++;
1289         sblock.e2fs.e2fs_fbcount--;
1290
1291         return sblock.e2fs.e2fs_first_dblock + bno;
1292 }
1293
1294 /*
1295  * void iput(struct ext2fs_dinode *ip, ino_t ino)
1296  *
1297  *      Put an inode entry into the corresponding table.
1298  */
1299 static void
1300 iput(struct ext2fs_dinode *ip, ino_t ino)
1301 {
1302         daddr_t d;
1303         uint c, i;
1304         struct ext2fs_dinode *dp;
1305         uint8_t *bp;
1306
1307         bp = malloc(sblock.e2fs_bsize);
1308         if (bp == NULL)
1309                 errx(EXIT_FAILURE, "%s: can't allocate buffer for inode\n",
1310                     __func__);
1311
1312         /*
1313          * Reserved inodes are allocated and accounted in initcg()
1314          * so skip checks of the bitmap and allocation for them.
1315          */
1316         if (ino >= EXT2_FIRSTINO) {
1317                 c = ino_to_cg(&sblock, ino);
1318
1319                 /* sanity check */
1320                 if (gd[c].ext2bgd_nifree == 0)
1321                         errx(EXIT_FAILURE,
1322                             "%s: no free inode %" PRIu64 " in block group %u\n",
1323                             __func__, (uint64_t)ino, c);
1324
1325                 /* update inode bitmap */
1326                 rdfs(fsbtodb(&sblock, gd[0].ext2bgd_i_bitmap),
1327                     sblock.e2fs_bsize, bp);
1328
1329                 /* more sanity */
1330                 if (isset(bp, EXT2_INO_INDEX(ino)))
1331                         errx(EXIT_FAILURE, "%s: inode %" PRIu64
1332                             " already in use\n", __func__, (uint64_t)ino);
1333                 setbit(bp, EXT2_INO_INDEX(ino));
1334                 wtfs(fsbtodb(&sblock, gd[0].ext2bgd_i_bitmap),
1335                     sblock.e2fs_bsize, bp);
1336                 gd[c].ext2bgd_nifree--;
1337                 sblock.e2fs.e2fs_ficount--;
1338         }
1339
1340         if (ino >= sblock.e2fs.e2fs_ipg * sblock.e2fs_ncg)
1341                 errx(EXIT_FAILURE, "%s: inode value out of range (%" PRIu64
1342                     ").\n", __func__, (uint64_t)ino);
1343
1344         /* update an inode entry in the table */
1345         d = fsbtodb(&sblock, ino_to_fsba(&sblock, ino));
1346         rdfs(d, sblock.e2fs_bsize, bp);
1347
1348         dp = (struct ext2fs_dinode *)(bp +
1349             inodesize * ino_to_fsbo(&sblock, ino));
1350         e2fs_isave(ip, dp);
1351         /* e2fs_i_bswap() doesn't swap e2di_blocks addrs */
1352         if ((ip->e2di_mode & EXT2_IFMT) != EXT2_IFLNK) {
1353                 for (i = 0; i < NDADDR + NIADDR; i++)
1354                         dp->e2di_blocks[i] = h2fs32(ip->e2di_blocks[i]);
1355         }
1356         /* h2fs32() just for consistency */
1357         dp->e2di_gen = h2fs32(arc4random());
1358
1359         wtfs(d, sblock.e2fs_bsize, bp);
1360         free(bp);
1361 }
1362
1363 /*
1364  * Read a block from the file system
1365  */
1366 void
1367 rdfs(daddr_t bno, int size, void *bf)
1368 {
1369         int n;
1370         off_t offset;
1371
1372         offset = bno;
1373         n = pread(fsi, bf, size, offset * sectorsize);
1374         if (n != size)
1375                 err(EXIT_FAILURE, "%s: read error for sector %" PRId64,
1376                     __func__, (int64_t)bno);
1377 }
1378
1379 /*
1380  * Write a block to the file system
1381  */
1382 void
1383 wtfs(daddr_t bno, int size, void *bf)
1384 {
1385         int n;
1386         off_t offset;
1387
1388         if (Nflag)
1389                 return;
1390         offset = bno;
1391         n = pwrite(fso, bf, size, offset * sectorsize);
1392         if (n != size)
1393                 err(EXIT_FAILURE, "%s: write error for sector %" PRId64,
1394                     __func__, (int64_t)bno);
1395 }
1396
1397 int
1398 ilog2(uint val)
1399 {
1400
1401         if (val == 0 || !powerof2(val))
1402                 errx(EXIT_FAILURE, "%s: %u is not a power of 2\n",
1403                     __func__, val);
1404
1405         return ffs(val) - 1;
1406 }
1407
1408 /*
1409  * int skpc(int mask, size_t size, uint8_t *cp)
1410  *
1411  *      Locate an unsigned character of value mask inside cp[].
1412  *      (from src/sys/lib/libkern/skpc.c)
1413  */
1414 int
1415 skpc(int mask, size_t size, uint8_t *cp)
1416 {
1417         uint8_t *end;
1418
1419         end = &cp[size];
1420         while (cp < end && *cp == (uint8_t)mask)
1421                 cp++;
1422
1423         return end - cp;
1424 }
1425
1426 static void
1427 uuid_get(struct m_ext2fs *sb)
1428 {
1429         unsigned char buf[sizeof(sb->e2fs.e2fs_uuid)];
1430
1431         arc4random_buf(buf, sizeof(buf));
1432         /* UUID version 4: random */
1433         buf[6] &= 0x0f;
1434         buf[6] |= 0x40;
1435         /* RFC4122 variant */
1436         buf[8] &= 0x3f;
1437         buf[8] |= 0x80;
1438         memcpy(sb->e2fs.e2fs_uuid, buf, sizeof(sb->e2fs.e2fs_uuid));
1439 }