/* $OpenBSD: mke2fs.c,v 1.16 2016/03/14 20:30:34 natano Exp $ */

/*	$NetBSD: mke2fs.c,v 1.13 2009/10/19 18:41:08 bouyer Exp $	*/

/*-

 * Copyright (c) 2007 Izumi Tsutsui.  All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 *

 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR

 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.

 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,

 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

/*

 * Copyright (c) 1980, 1989, 1993

 *	The Regents of the University of California.  All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 * 3. Neither the name of the University nor the names of its contributors

 *    may be used to endorse or promote products derived from this software

 *    without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND

 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE

 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS

 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

 * SUCH DAMAGE.

 */

/*

 * Copyright (c) 1997 Manuel Bouyer.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *	notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *	notice, this list of conditions and the following disclaimer in the

 *	documentation and/or other materials provided with the distribution.

 *

 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR

 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.

 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,

 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

/*

 * mke2fs.c: "re-invent (dumb but non-GPLed) wheel as a fun project"

 *

 *	In spite of this name, there is no piece of code

 *	derived from GPLed e2fsprogs written for Linux.

 *	I referred them only to see how each structure

 *	member should be initialized.

 *

 * Reference:

 *	- All NetBSD sources under src/sys/ufs/ext2fs and src/sbin/fsck_ext2fs

 *	- Ext2fs Home Page

 *		http://e2fsprogs.sourceforge.net/ext2.html

 *	- Design and Implementation of the Second Extended Filesystem

 *		http://e2fsprogs.sourceforge.net/ext2intro.html

 *	- Linux Documentation "The Second Extended Filesystem"

 *		src/linux/Documentation/filesystems/ext2.txt

 *		    in the Linux kernel distribution

 */

#include <sys/param.h>	/* MAXBSIZE powerof2 roundup setbit isset MIN */

#include <sys/types.h>

#include <sys/mman.h>

#include <sys/time.h>

#include <ufs/ext2fs/ext2fs_dinode.h>

#include <ufs/ext2fs/ext2fs_dir.h>

#include <ufs/ext2fs/ext2fs.h>

#include <sys/ioctl.h>

#include <err.h>

#include <errno.h>

#include <inttypes.h>

#include <string.h>

#include <unistd.h>

#include <stdint.h>

#include <stdlib.h>

#include <stddef.h>

#include <stdio.h>

#include "extern.h"

static void initcg(uint);

static void zap_old_sblock(daddr32_t);

static uint cgoverhead(uint);

static int fsinit(const struct timeval *);

static int makedir(struct ext2fs_direct *, int);

static void copy_dir(struct ext2fs_direct *, struct ext2fs_direct *);

static void init_resizeino(const struct timeval *);

static uint32_t alloc(uint32_t, uint16_t);

static void iput(struct ext2fs_dinode *, ino_t);

static void rdfs(daddr32_t, int, void *);

static void wtfs(daddr32_t, int, void *);

static int ilog2(uint);

static int skpc(int, size_t, uint8_t *);

static void uuid_get(struct m_ext2fs *);

/* XXX: some of these macro should be into <ufs/ext2fs/ext2fs.h>? */

#define EXT2_DEF_MAX_MNT_COUNT	20

#define EXT2_DEF_FSCKINTV	(180 * 24 * 60 * 60)	/* 180 days */

#define EXT2_RESERVED_INODES	(EXT2_FIRSTINO - 1)

#define EXT2_UMASK		0755

#define EXT2_INO_INDEX(ino)	((ino) - 1)		/* no inode zero */

#define EXT2_LOSTFOUNDSIZE	16384

#define EXT2_LOSTFOUNDINO	EXT2_FIRSTINO		/* XXX: not quite */

#define EXT2_LOSTFOUNDUMASK	0700

#define EXT2_RESIZEINOUMASK	0600

#define NBLOCK_SUPERBLOCK	1

#define NBLOCK_BLOCK_BITMAP	1

#define NBLOCK_INODE_BITMAP	1

#define cgbase(fs, c)	\

	((fs)->e2fs.e2fs_first_dblock + (fs)->e2fs.e2fs_bpg * (c))

#define       rounddown(x,y)  (((x)/(y))*(y))

/*

 * ext2fs super block and group descriptor structures

 *

 *   We don't have to use or setup whole in-memory m_ext2fs structure,

 *   but prepare it to use several macro defined in kernel headers.

 */

union {

	struct m_ext2fs m_ext2fs;

	char pad[SBSIZE];

} ext2fsun;

#define sblock	ext2fsun.m_ext2fs

#define gd	ext2fsun.m_ext2fs.e2fs_gd

static uint8_t *iobuf;		/* for superblock and group descriptors */

static int iobufsize;

static uint8_t buf[MAXBSIZE];	/* for initcg() and makedir() ops */

static int fd;

extern int max_cols;

void

mke2fs(const char *fsys, int f)

{

	struct timeval tv;

	int64_t minfssize;

	uint bcount, fbcount, ficount;

	uint blocks_gd, blocks_per_cg, inodes_per_cg, iblocks_per_cg;

	uint minblocks_per_cg, blocks_lastcg;

	uint ncg, cylno, sboff;

	int i, len, col, delta, fld_width;

	/*

	 * collect and verify the block and fragment sizes

	 */

		    "block size must be a power of 2, not %u\n",

		    bsize);

	}

		    "fragment size must be a power of 2, not %u\n",

		    fsize);

	}

		    "fragment size %u is too small, minimum is %u\n",

		    fsize, sectorsize);

	}

		    "block size %u is too small, minimum is %u\n",

		    bsize, MINBSIZE);

	}

		    "block size %u is too large, maximum is %u\n",

		    bsize, MAXBSIZE);

	}

		/*

		 * There is no fragment support on current ext2fs (yet?),

		 * but some kernel code refers fsize or fpg as bsize or bpg

		 * and Linux seems to set the same values to them.

		 */

		    "block size (%u) can't be different from "

		    "fragment size (%u)\n",

		    bsize, fsize);

	}

	/* variable inodesize is REV1 feature */

		    " doesn't support %d byte inode\n", inodesize);

	}

	/*

	 * Ext2fs preserves BBSIZE (1024 bytes) space at the top for

	 * bootloader (though it is not enough at all for our bootloader).

	 * If bsize == BBSIZE we have to preserve one block.

	 * If bsize > BBSIZE, the first block already contains BBSIZE space

	 * before superblock because superblock is allocated at SBOFF and

	 * bsize is a power of two (i.e. 2048 bytes or more).

	 */

	    sblock.e2fs.e2fs_first_dblock +

	    NBLOCK_SUPERBLOCK +

	    1 /* at least one group descriptor */ +

	    NBLOCK_BLOCK_BITMAP	+

	    NBLOCK_INODE_BITMAP +

	    1 /* at least one inode table block */ +

	    1 /* at least one data block for rootdir */ +

	    1 /* at least one data block for data */

	    );			/* XXX and more? */

		    " < minimum size of %" PRId64 "\n", fssize, minfssize);

	/*

	 * While many people claim that ext2fs is a (bad) clone of ufs/ffs,

	 * it isn't actual ffs so maybe we should call it "block group"

	 * as their native name rather than ffs derived "cylinder group."

	 * But we'll use the latter here since other kernel sources use it.

	 * (I also agree "cylinder" based allocation is obsolete though)

	 */

	/* maybe "simple is the best" */

	/* check range of inode number */

	/* Check that the last cylinder group has enough space for inodes */

	    NBLOCK_BLOCK_BITMAP +

	    NBLOCK_INODE_BITMAP +

	    iblocks_per_cg +

	    1;	/* at least one data block */

	    blocks_per_cg * (ncg - 1);

		/*

		 * Since we make all the cylinder groups the same size, the

		 * last will only be small if there are more than one

		 * cylinder groups. If the last one is too small to store

		 * filesystem data, just kill it.

		 *

		 * XXX: Does fsck_ext2fs(8) properly handle this case?

		 */

	}

	/* roundup inodes_per_cg to make it use whole inode table blocks */

	/* XXX: probably we should check these adjusted values again */

	/* e2fs_fbcount will be accounted later */

	/* e2fs_ficount will be accounted later */

	/* XXX: should add some entropy to avoid checking all fs at once? */

	/*

	 * Maybe we can use E2FS_OS_FREEBSD here and it would be more proper,

	 * but the purpose of this newfs_ext2fs(8) command is to provide

	 * a filesystem which can be recognized by firmware on some

	 * Linux based appliances that can load bootstrap files only from

	 * (their native) ext2fs, and anyway we will (and should) try to

	 * act like them as much as possible.

	 *

	 * Anyway, I hope that all newer such boxes will keep their support

	 * for the "GOOD_OLD_REV" ext2fs.

	 */

	} else {

		/*

		 * e2fsprogs say "REV1" is "dynamic" so

		 * it isn't quite a version and maybe it means

		 * "extended from REV0 so check compat features."

		 *

		 * XXX: We don't have any native tool to activate

		 *      the EXT2F_COMPAT_RESIZE feature and

		 *      fsck_ext2fs(8) might not fix structures for it.

		 */

		    EXT2F_ROCOMPAT_SPARSESUPER | EXT2F_ROCOMPAT_LARGEFILE;

	}

	/* e2fs_block_group_nr is set on writing superblock to each group */

		    sizeof(sblock.e2fs.e2fs_vname));

	}

	/* calculate blocks for reserved group descriptors for resize */

	    (sblock.e2fs.e2fs_features_compat & EXT2F_COMPAT_RESIZE) != 0) {

		uint64_t target_blocks;

		uint target_ncg, target_ngdb, reserved_ngdb;

		/* reserve descriptors for size as 1024 times as current */

		    (sblock.e2fs.e2fs_bcount - sblock.e2fs.e2fs_first_dblock)

		    * 1024ULL;

		/* number of blocks must be in uint32_t */

		    sblock.e2fs_bsize);

		/*

		 * Reserved group descriptor blocks are preserved as

		 * the second level double indirect reference blocks in

		 * the EXT2_RESIZEINO inode, so the maximum number of

		 * the blocks is NINDIR(fs).

		 * (see also descriptions in init_resizeino() function)

		 *

		 * We check a number including current e2fs_ngdb here

		 * because they will be moved into reserved gdb on

		 * possible future size shrink, though e2fsprogs don't

		 * seem to care about it.

		 */

		/* make sure reserved_ngdb fits in the last cg */

			/* if no space for reserved gdb, disable the feature */

			    ~EXT2F_COMPAT_RESIZE;

		}

	}

	/*

	 * Initialize group descriptors

	 */

		uint boffset;

		    (sblock.e2fs.e2fs_features_rocompat &

		     EXT2F_ROCOMPAT_SPARSESUPER) == 0 ||

		    cg_has_sb(cylno)) {

			    (sblock.e2fs.e2fs_features_compat &

			     EXT2F_COMPAT_RESIZE) != 0)

		}

			    blocks_lastcg - cgoverhead(cylno);

		else

			    sblock.e2fs.e2fs_bpg - cgoverhead(cylno);

			/* take reserved inodes off nifree */

		}

	}

	/*

	 * Dump out summary information about file system.

	 */

		    "block size %u, fragment size %u\n",

		    fsys,

		    (uint)(((uint64_t)bcount * bsize) / (1024 * 1024)),

		    (uint)((uint64_t)bcount * bsize -

		    rounddown((uint64_t)bcount * bsize, 1024 * 1024))

		    / 1024 / 100,

		    fssize, bsize, fsize);

		    "%u inodes.\n",

		    ncg, bsize * sblock.e2fs.e2fs_bpg / (1024 * 1024),

		    sblock.e2fs.e2fs_bpg, sblock.e2fs.e2fs_ipg);

	}

	/*

	 * allocate space for superblock and group descriptors

	 */

	    MAP_ANON|MAP_PRIVATE, -1, 0);

	/*

	 * We now start writing to the filesystem

	 */

		static const uint pbsize[] = { 1024, 2048, 4096, 0 };

		uint pblock, epblock;

		/*

		 * Validate the given file system size.

		 * Verify that its last block can actually be accessed.

		 * Convert to file system fragment sized units.

		 */

			    fssize);

		/*

		 * Ensure there is nothing that looks like a filesystem

		 * superblock anywhere other than where ours will be.

		 * If fsck_ext2fs finds the wrong one all hell breaks loose!

		 *

		 * XXX: needs to check how fsck_ext2fs programs even

		 *      on other OSes determine alternate superblocks

		 */

				    pbsize[i] / sectorsize);

		}

	}

	/* If we are printing more than one line of numbers, line up columns */

	    (uint64_t)cgbase(&sblock, ncg - 1));

		/* Leave space to add " ..." after one row of numbers */

#define BASE 0x10000	/* For some fixed-point maths */

		/* the first one is a master, not backup */

		/* skip if this cylinder doesn't have a backup */

		    (sblock.e2fs.e2fs_features_rocompat &

		     EXT2F_ROCOMPAT_SPARSESUPER) != 0 &&

		    cg_has_sb(cylno) == 0)

				/* No point doing dots for -N */

			/* Print dots scaled to end near RH margin */

			continue;

		}

		/* Print superblock numbers */

		    (uint64_t)cgbase(&sblock, cylno));

			/* Next number fits */

		/* Next number won't fit, need a newline */

			/* Print dots for subsequent cylinder groups */

				}

			}

		}

	}

#undef BASE

	/*

	 * Now construct the initial file system,

	 */

	/*

	 * Write out the superblock and group descriptors

	 */

		/*

		 * If the first block contains the boot block sectors,

		 * (i.e. in case of sblock.e2fs.e2fs_bsize > BBSIZE)

		 * we have to preserve data in it.

		 */

	}

	   sizeof(struct ext2_gd) * sblock.e2fs_ncg);

	    iobufsize - sboff, iobuf + sboff);

}

/*

 * Initialize a cylinder (block) group.

 */

void

initcg(uint cylno)

{

	uint nblcg, i, j, sboff;

	struct ext2fs_dinode *dp;

	/*

	 * Make a copy of the superblock and group descriptors.

	 */

	    (sblock.e2fs.e2fs_features_rocompat &

	     EXT2F_ROCOMPAT_SPARSESUPER) == 0 ||

	    cg_has_sb(cylno)) {

			/* preserve data in bootblock in cg0 */

		}

		    sblock.e2fs_bsize * NBLOCK_SUPERBLOCK),

		    sizeof(struct ext2_gd) * sblock.e2fs_ncg);

		/* write superblock and group descriptor backups */

		    sboff / sectorsize, iobufsize - sboff, iobuf + sboff);

	}

	/*

	 * Initialize block bitmap.

	 */

		/* The last group could have less blocks than e2fs_bpg. */

		    cgbase(&sblock, sblock.e2fs_ncg - 1);

	}

	/* set overhead (superblock, group descriptor etc.) blocks used */

	    buf);

	/*

	 * Initialize inode bitmap.

	 *

	 *  Assume e2fs_ipg is a multiple of NBBY since

	 *  it's a multiple of e2fs_ipb (as we did above).

	 *  Note even (possibly smaller) the last group has the same e2fs_ipg.

	 */

		/* mark reserved inodes */

	}

	    buf);

	/*

	 * Initialize inode tables.

	 *

	 *  Just initialize generation numbers for NFS security.

	 *  XXX: sys/ufs/ext2fs/ext2fs_alloc.c:ext2fs_valloc() seems

	 *       to override these generated numbers.

	 */

			/* If there is some bias in arc4random(), keep it. */

		}

		    sblock.e2fs_bsize, buf);

	}

}

/*

 * Zap possible lingering old superblock data

 */

static void

zap_old_sblock(daddr32_t sec)

{

	static daddr32_t cg0_data;

	uint32_t oldfs[SBSIZE / sizeof(uint32_t)];

	static const struct fsm {

		uint32_t offset;

		uint32_t magic;

		uint32_t mask;

	} fs_magics[] = {

		{offsetof(struct ext2fs, e2fs_magic) / 4, E2FS_MAGIC, 0xffff},

		{offsetof(struct ext2fs, e2fs_magic) / 4,

		    E2FS_MAGIC << 16, 0xffff0000},

		{14, 0xef530000, 0xffff0000},	/* EXT2FS (big) */

		{0x55c / 4, 0x00011954, ~0U},	/* FS_UFS1_MAGIC */

		{0x55c / 4, 0x19540119, ~0U},	/* FS_UFS2_MAGIC */

		{0, 0x70162, ~0U},		/* LFS_MAGIC */

		{.offset = ~0U},

	};

	const struct fsm *fsm;

	/* don't override data before superblock */

		    ((daddr32_t)sblock.e2fs.e2fs_first_dblock + cgoverhead(0)) *

		    sblock.e2fs_bsize / sectorsize;

	}

	/* Ignore anything that is beyond our filesystem */

	/* Zero anything inside our filesystem... */

		/* ...unless we will write that area anyway */

			/* assume iobuf is zero'ed here */

		return;

	}

	/*

	 * The sector might contain boot code, so we must validate it

	 *

	 * XXX: ext2fs won't preserve data after SBOFF,

	 *      but first_dblock could have a different value.

	 */

		uint32_t v;

			break;

	}

	/* Just zap the magic number */

}

/*

 * uint cgoverhead(uint c)

 *

 * 	Return a number of reserved blocks on the specified group.

 * 	XXX: should be shared with src/sbin/fsck_ext2fs/setup.c

 */

uint

cgoverhead(uint c)

{

	uint overh;

	    (sblock.e2fs.e2fs_features_rocompat &

	     EXT2F_ROCOMPAT_SPARSESUPER) == 0 ||

	    cg_has_sb(c) != 0) {

		    (sblock.e2fs.e2fs_features_compat &

		     EXT2F_COMPAT_RESIZE) != 0)

	}

}

/*

 * Initialize the file system

 */

#define LOSTDIR		/* e2fsck complains if there is no lost+found */

#define	PREDEFDIR	2

#ifdef LOSTDIR

#define	PREDEFROOTDIR	(PREDEFDIR + 1)

#else

#define	PREDEFROOTDIR	PREDEFDIR

#endif

struct ext2fs_direct root_dir[] = {

	{ EXT2_ROOTINO, 0, 1, 0, "." },

	{ EXT2_ROOTINO, 0, 2, 0, ".." },

#ifdef LOSTDIR

	{ EXT2_LOSTFOUNDINO, 0, 10, 0, "lost+found" },

#endif

};

#ifdef LOSTDIR

struct ext2fs_direct lost_found_dir[] = {

	{ EXT2_LOSTFOUNDINO, 0, 1, 0, "." },

	{ EXT2_ROOTINO, 0, 2, 0, ".." },

};

struct ext2fs_direct pad_dir = { 0, sizeof(struct ext2fs_direct), 0, 0, "" };

#endif

int

fsinit(const struct timeval *tv)

{

	struct ext2fs_dinode node;

#ifdef LOSTDIR

	uint i, nblks_lostfound, blk;

#endif

	/*

	 * Initialize the inode for the resizefs feature

	 */

	    (sblock.e2fs.e2fs_features_compat & EXT2F_COMPAT_RESIZE) != 0)

	/*

	 * Initialize the node

	 */

#ifdef LOSTDIR

	/*

	 * Create the lost+found directory

	 */

	    sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE) {

	}

	/* prepare a bit large directory for preserved files */

	/* ...but only with direct blocks */

	/* e2di_nblock is a number of disk blocks, not ext2fs blocks */

	}

			    __func__);

		}

	}

		    buf);

	}

#endif

	/*

	 * create the root directory

	 */

	    sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE) {

#ifdef LOSTDIR

#endif

	}

	/* e2di_nblock is a number of disk block, not ext2fs block */

	}

}

/*

 * Construct a set of directory entries in "buf".

 * return size of directory.

 */

int

makedir(struct ext2fs_direct *protodir, int entries)

{

	uint8_t *cp;

	uint i, spcleft;

	uint dirblksiz;