parted-1.8.7/libparted/fs/ext2/ext2_mkfs.c - nest-learning-thermostat/5.0/parted - Git at Google

 /*
     ext2_mkfs.c -- ext2 fs creator
     Copyright (C) 1999, 2000, 2001, 2007 Free Software Foundation, Inc.

     This program is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by
     the Free Software Foundation; either version 2 of the License, or
     (at your option) any later version.

     This program is distributed in the hope that it will be useful,
     but WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     GNU General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with this program; if not, write to the Free Software
     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
 */

 #include <config.h>

 #ifndef DISCOVER_ONLY

 #define USE_EXT2_IS_DATA_BLOCK

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <sys/stat.h>
 #include <time.h>
 #include <unistd.h>
 #include <uuid/uuid.h>
 #include "ext2.h"

 /* formula grabbed from linux ext2 kernel source
  *
  * returns 1 iff:
  * 	x == y^N,       N is some natural number
  * OR	x == 0
  */
 static __inline__ int is_root(int x, int y)
 {
 	if (!x) return 1;

 	while (1)
 	{
 		if (x == 1) return 1;

 		if (x % y) return 0;

 		x /= y;
 	}
 }

 static __inline__ int is_group_sparse(int sparsesbfs, int group)
 {
 	if (!sparsesbfs)
 		return 1;

 	if (is_root(group, 3) || is_root(group, 5) || is_root(group, 7))
 		return 1;

 	return 0;
 }

 /* has implicit parameter 'sb' !! */
 #define is_sparse(group) is_group_sparse(EXT2_SUPER_FEATURE_RO_COMPAT(*sb) \
 	       			& EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER, (group))

 static int ext2_mkfs_write_main(struct ext2_dev_handle *handle,
 				struct ext2_super_block *sb,
 				struct ext2_group_desc *gd)
 {
 	int freeit;
 	int i;
 	int numgroups;
 	int gdblocks;
 	unsigned char *sbbuf;
 	struct ext2_super_block *sb_for_io;

 	freeit = 0;
 	sbbuf = (unsigned char *)sb;
 	sb_for_io = sb;
 	if (EXT2_SUPER_LOG_BLOCK_SIZE(*sb))
 	{
 		sbbuf = ped_malloc(1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));
 		if (!(handle->ops->read)(handle->cookie, sbbuf, 0, 1))
 			return 0;
 		memcpy (sbbuf+1024, sb, 1024);
 		freeit = 1;
 		sb_for_io = (struct ext2_super_block*) (sbbuf + 1024);
 	}

 	numgroups = ped_div_round_up (EXT2_SUPER_BLOCKS_COUNT(*sb)
 			        - EXT2_SUPER_FIRST_DATA_BLOCK(*sb),
 			    EXT2_SUPER_BLOCKS_PER_GROUP(*sb));
 	gdblocks = ped_div_round_up (numgroups * sizeof(struct ext2_group_desc),
 			   1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));

 	for (i=0;i<numgroups;i++)
 	{
 		if (is_sparse(i))
 		{
 			int offset;

 			offset = EXT2_SUPER_FIRST_DATA_BLOCK(*sb)
 				 + i * EXT2_SUPER_BLOCKS_PER_GROUP(*sb);

 			sb_for_io->s_block_group_nr = PED_CPU_TO_LE16 (i);

 			if (!handle->ops->write(handle->cookie, sbbuf,
 					        offset, 1))
 				return 0;
 			if (!handle->ops->write(handle->cookie, gd, offset+1,
 						gdblocks))
 				return 0;
 		}
 	}

 	sb_for_io->s_block_group_nr = 0;

 	if (freeit)
 		ped_free(sbbuf);
 	return 1;
 }

 static int ext2_mkfs_write_meta(struct ext2_dev_handle *handle,
 				struct ext2_super_block *sb,
 				struct ext2_group_desc *gd,
 				PedTimer* timer)
 {
 	int blocksize;
 	int gdtsize;
 	int i;
 	int itsize;
 	int numgroups;
 	unsigned char *bb;
 	unsigned char *ib;
 	unsigned char *zero;

 	blocksize = 1 << (EXT2_SUPER_LOG_BLOCK_SIZE(*sb) + 13);

 	numgroups = ped_div_round_up (EXT2_SUPER_BLOCKS_COUNT(*sb)
 				- EXT2_SUPER_FIRST_DATA_BLOCK(*sb),
 			    EXT2_SUPER_BLOCKS_PER_GROUP(*sb));
 	itsize = ped_div_round_up (sizeof(struct ext2_inode)
 				* EXT2_SUPER_INODES_PER_GROUP(*sb),
 			 (1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb)));
 	gdtsize = ped_div_round_up (sizeof(struct ext2_group_desc) * numgroups,
 			  (1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb)));

 	bb = ped_malloc(1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));
 	if (!bb) goto error;
 	ib = ped_malloc(1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));
 	if (!ib) goto error_free_bb;
 	zero = ped_malloc((1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb)) * itsize);
 	if (!zero) goto error_free_zero;

 	memset(zero, 0, (1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb)) * itsize);

 	ped_timer_reset (timer);
 	ped_timer_set_state_name (timer, _("writing per-group metadata"));

 	for (i=0;i<numgroups;i++)
 	{
 		int admin;
 		blk_t bbblock;
 		int groupsize;
 		int groupoffset;
 		blk_t ibblock;
 		int j;

 		ped_timer_update (timer, 1.0 * i / numgroups);

 		groupoffset = i*EXT2_SUPER_BLOCKS_PER_GROUP(*sb)
 			      + EXT2_SUPER_FIRST_DATA_BLOCK(*sb);
 		groupsize = PED_MIN(EXT2_SUPER_BLOCKS_COUNT(*sb) - groupoffset,
 				    EXT2_SUPER_BLOCKS_PER_GROUP(*sb));

 		admin = itsize + 2;
 		bbblock = groupoffset;
 		ibblock = groupoffset + 1;
 		if (is_sparse(i))
 		{
 			admin += gdtsize + 1;
 			bbblock = groupoffset + gdtsize + 1;
 			ibblock = groupoffset + gdtsize + 2;
 		}

 		{
 			memset(bb, 0, 1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));
 			if (is_sparse(i))
 				for (j=0;j<gdtsize+1;j++)
 					bb[j>>3] |= _bitmap[j&7];

 			j = bbblock - groupoffset;
 			bb[j>>3] |= _bitmap[j&7];

 			j = ibblock - groupoffset;
 			bb[j>>3] |= _bitmap[j&7];

 			for (j=0;j<itsize;j++)
 			{
 				int k = j + gdtsize + 3;

 				bb[k>>3] |= _bitmap[k&7];
 			}

 			for (j=groupsize;j<blocksize;j++)
 				bb[j>>3] |= _bitmap[j&7];

 			if (!handle->ops->write(handle->cookie, bb, bbblock, 1))
 				goto error_free_zero;
 		}

 		{
 			memset(ib, 0, 1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));

 			for (j=EXT2_SUPER_INODES_PER_GROUP(*sb);j<blocksize;j++)
 				bb[j>>3] |= _bitmap[j&7];

 			if (!handle->ops->write(handle->cookie, ib, ibblock, 1))
 				goto error_free_zero;
 		}

 		if (!handle->ops->write(handle->cookie, zero,
 					groupoffset + gdtsize + 3, itsize))
 			goto error_free_zero;

 		gd[i].bg_block_bitmap = PED_CPU_TO_LE32(bbblock);
 		gd[i].bg_inode_bitmap = PED_CPU_TO_LE32(ibblock);
 		gd[i].bg_inode_table = PED_CPU_TO_LE32(groupoffset + gdtsize
 						       + 3);
 		gd[i].bg_free_blocks_count = PED_CPU_TO_LE16(groupsize - admin);
 		gd[i].bg_free_inodes_count = PED_CPU_TO_LE16(
 			EXT2_SUPER_INODES_PER_GROUP(*sb));
 		gd[i].bg_used_dirs_count = 0;
 		gd[i].bg_used_dirs_count = 0;
 		gd[i].bg_pad = 0;
 		gd[i].bg_reserved[0] = 0;
 		gd[i].bg_reserved[1] = 0;
 		gd[i].bg_reserved[2] = 0;

 		sb->s_free_blocks_count = PED_CPU_TO_LE32 (
 			EXT2_SUPER_FREE_BLOCKS_COUNT(*sb)
 			+ EXT2_GROUP_FREE_BLOCKS_COUNT(gd[i]));
 	}

 	ped_timer_update (timer, 1.0);

 	ped_free(zero);
 	ped_free(ib);
 	ped_free(bb);
 	return 1;

 error_free_zero:
 	ped_free(zero);
 	ped_free(ib);
 error_free_bb:
 	ped_free(bb);
 error:
 	return 0;
 }

 /* returns the offset into the buffer of the start of the next dir entry */
 static int _set_dirent(void* buf, int offset, int block_size, int is_last,
 		       uint32_t inode, char* name, int file_type)
 {
 	struct ext2_dir_entry_2 *dirent = (void*) (((char*)buf) + offset);
 	int name_len = strlen(name);
 	int rec_len;

 	if (is_last)
 		rec_len = block_size - offset;
 	else
 		rec_len = ped_round_up_to(name_len + 1 + 8, 4);

 	memset (dirent, 0, rec_len);

 	dirent->inode = PED_CPU_TO_LE32(inode);
 	dirent->name_len = name_len;
 	dirent->rec_len = PED_CPU_TO_LE16(rec_len);
 	dirent->file_type = file_type;
 	strcpy(dirent->name, name);

 	return offset + rec_len;
 }

 static int ext2_mkfs_create_lost_and_found_inode(struct ext2_fs *fs)
 {
 	struct ext2_buffer_head *bh;
 	blk_t blocks[12];
 	uint32_t* data = ped_malloc ((fs->blocksize / 4) * sizeof(uint32_t));
 	int i;
 	struct ext2_inode inode;
 	int offset;

 	for (i=0;i<12;i++)
 	{
 		if (!(blocks[i] = ext2_find_free_block(fs)))
 			return 0;

 		if (!ext2_set_block_state(fs, blocks[i], 1, 1))
 			return 0;
 	}

 	/* create the directory entries, preallocating lots of blocks */
 	/* first block contains . and .. */
 	bh = ext2_bcreate(fs, blocks[0]);
 	if (!bh)
 		return 0;
 	memset(bh->data, 0, fs->blocksize);
 	offset = _set_dirent(bh->data, 0, fs->blocksize, 0,
 			     11, ".", EXT2_FT_DIR);
 	offset = _set_dirent(bh->data, offset, fs->blocksize, 1,
 			     EXT2_ROOT_INO, "..", EXT2_FT_DIR);
 	bh->dirty = 1;
 	ext2_brelse(bh, 1);

 	/* subsequent blocks are empty */
 	memset(data, 0, fs->blocksize);
 	data[0] = 0;
 	data[1] = PED_CPU_TO_LE32(fs->blocksize);
 	for (i=1;i<12;i++)
 	{
 		bh = ext2_bcreate(fs, blocks[i]);
 		memcpy(bh->data, data, fs->blocksize);
 		bh->dirty = 1;
 		ext2_brelse(bh, 1);
 	}

 	/* create inode */
 	memset(&inode, 0, sizeof(struct ext2_inode));
 	inode.i_mode = PED_CPU_TO_LE16(S_IFDIR | 0755);
 	inode.i_uid = 0;
 	inode.i_size = PED_CPU_TO_LE32(12 * fs->blocksize);
 	inode.i_atime = PED_CPU_TO_LE32(time(NULL));
 	inode.i_ctime = PED_CPU_TO_LE32(time(NULL));
 	inode.i_mtime = PED_CPU_TO_LE32(time(NULL));
 	inode.i_dtime = 0;
 	inode.i_gid = 0;
 	inode.i_links_count = PED_CPU_TO_LE16(2);
 	inode.i_blocks = PED_CPU_TO_LE32((12 * fs->blocksize) >> 9);
 	inode.i_flags = 0;
 	for (i=0;i<12;i++)
 		inode.i_block[i] = PED_CPU_TO_LE32(blocks[i]);

 	if (!ext2_write_inode(fs, 11, &inode))
 		return 0;
 	fs->gd[0].bg_used_dirs_count = PED_CPU_TO_LE16(
 		EXT2_GROUP_USED_DIRS_COUNT(fs->gd[0]) + 1);
 	fs->metadirty |= EXT2_META_GD;

 	return 1;
 }

 static int ext2_mkfs_create_root_inode(struct ext2_fs *fs)
 {
 	struct ext2_buffer_head *bh;
 	blk_t block;
 	struct ext2_inode inode;
 	int offset;

 	if (!(block = ext2_find_free_block(fs)))
 		return 0;
 	if (!ext2_set_block_state(fs, block, 1, 1))
 		return 0;

 	/* create directory entries */
 	bh = ext2_bcreate(fs, block);
 	memset(bh->data, 0, fs->blocksize);
 	offset = _set_dirent(bh->data, 0, fs->blocksize, 0,
 			     EXT2_ROOT_INO, ".", EXT2_FT_DIR);
 	offset = _set_dirent(bh->data, offset, fs->blocksize, 0,
 			     EXT2_ROOT_INO, "..", EXT2_FT_DIR);
 	offset = _set_dirent(bh->data, offset, fs->blocksize, 1,
 			     11, "lost+found", EXT2_FT_DIR);
 	bh->dirty = 1;
 	if (!ext2_brelse(bh, 1))
 		return 0;

 	/* create inode */
 	memset(&inode, 0, sizeof(struct ext2_inode));
 	inode.i_mode = PED_CPU_TO_LE16(S_IFDIR | 0755);
 	inode.i_uid = 0;
 	inode.i_size = PED_CPU_TO_LE32(fs->blocksize);
 	inode.i_atime = PED_CPU_TO_LE32(time(NULL));
 	inode.i_ctime = PED_CPU_TO_LE32(time(NULL));
 	inode.i_mtime = PED_CPU_TO_LE32(time(NULL));
 	inode.i_dtime = 0;
 	inode.i_gid = 0;
 	inode.i_links_count = PED_CPU_TO_LE16(3);
 	inode.i_blocks = PED_CPU_TO_LE32(fs->blocksize >> 9);
 	inode.i_flags = 0;
 	inode.i_block[0] = PED_CPU_TO_LE32(block);

 	if (!ext2_write_inode(fs, 2, &inode))
 		return 0;
 	fs->gd[0].bg_used_dirs_count = PED_CPU_TO_LE16 (
 		EXT2_GROUP_USED_DIRS_COUNT(fs->gd[0]) + 1);
 	fs->metadirty |= EXT2_META_GD;

 	return 1;
 }

 static int ext2_reserve_inodes(struct ext2_fs *fs)
 {
 	int i;

 	for (i=1;i<12;i++)
 		if (!ext2_set_inode_state(fs, i, 1, 1))
 			return 0;
 	return 1;
 }

 static int ext2_mkfs_init_sb (struct ext2_super_block *sb, blk_t numblocks,
 			      int numgroups, int first_block,
 			      int log_block_size, blk_t blocks_per_group,
 			      int inodes_per_group, int sparse_sb,
 			      int reserved_block_percentage)
 {
 	/* catch a bug in gcc 2.95.2 */
 	PED_ASSERT(numgroups != 0, return 0);

 	memset(sb, 0, 1024);

 	sb->s_inodes_count = PED_CPU_TO_LE32(numgroups * inodes_per_group);
 	sb->s_blocks_count = PED_CPU_TO_LE32(numblocks);
 	sb->s_r_blocks_count = PED_CPU_TO_LE32(((uint64_t)numblocks
 				* reserved_block_percentage) / 100);

 	/* hack: this get's inc'd as we go through each group in
 	 * ext2_mkfs_write_meta()
 	 */
 	sb->s_free_blocks_count = 0;
 	sb->s_free_inodes_count = PED_CPU_TO_LE32 (numgroups
 							* inodes_per_group);
 	sb->s_first_data_block = PED_CPU_TO_LE32(first_block);
 	sb->s_log_block_size = PED_CPU_TO_LE32(log_block_size - 10);
 	sb->s_log_frag_size = sb->s_log_block_size;
 	sb->s_blocks_per_group = PED_CPU_TO_LE32(blocks_per_group);
 	sb->s_frags_per_group = PED_CPU_TO_LE32(blocks_per_group);
 	sb->s_inodes_per_group = PED_CPU_TO_LE32(inodes_per_group);
 	sb->s_mtime = 0;
 	sb->s_wtime = 0;
 	sb->s_mnt_count = 0;
 	sb->s_max_mnt_count = PED_CPU_TO_LE16(30);
 	sb->s_magic = PED_CPU_TO_LE16(0xEF53);
 	sb->s_state = PED_CPU_TO_LE16(EXT2_VALID_FS);
 	sb->s_errors = PED_CPU_TO_LE16(EXT2_ERRORS_DEFAULT);
 	sb->s_minor_rev_level = 0;
 	sb->s_lastcheck = 0;
 	sb->s_checkinterval = 0;
 	sb->s_creator_os = 0;
 	sb->s_rev_level = PED_CPU_TO_LE32(1);
 	sb->s_def_resuid = 0;
 	sb->s_def_resgid = 0;
 	sb->s_first_ino = PED_CPU_TO_LE32(11);
 	sb->s_inode_size = PED_CPU_TO_LE16(128);
 	sb->s_block_group_nr = 0;
 	sb->s_feature_compat = 0;
 	sb->s_feature_incompat = 0;
 	sb->s_feature_ro_compat = 0;
 	if (sparse_sb)
 		sb->s_feature_ro_compat
 			|= PED_CPU_TO_LE32(EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER);

 /* FIXME: let the user decide? _set_dirent() assumes FILETYPE */
 	sb->s_feature_incompat
 		|= PED_CPU_TO_LE32(EXT2_FEATURE_INCOMPAT_FILETYPE);

 	uuid_generate(sb->s_uuid);
 	memset(sb->s_volume_name, 0, 16);
 	memset(sb->s_last_mounted, 0, 64);
 	sb->s_algorithm_usage_bitmap = 0;
 	sb->s_prealloc_blocks = 0;
 	sb->s_prealloc_dir_blocks = 0;
 	sb->s_padding1 = 0;

 	return 1;
 }

 struct ext2_fs *ext2_mkfs(struct ext2_dev_handle *handle,
 			  blk_t numblocks,
 			  int log_block_size,
 			  blk_t blocks_per_group,
 			  int inodes_per_group,
 			  int sparse_sb,
 			  int reserved_block_percentage,
 			  PedTimer* timer)
 {
 	struct ext2_fs *fs;
 	struct ext2_super_block sb;
 	struct ext2_group_desc *gd;
 	int numgroups;
 	int first_block;
 	int non_sparse_admin;
 	int sparse_admin;
 	int last_group_blocks;
 	int last_group_admin;

 	/* if the FS is > 512Mb, use 4k blocks, otherwise 1k blocks */
 	if (log_block_size == 0) {
 		handle->ops->set_blocksize(handle->cookie, 12);
 		if (handle->ops->get_size(handle->cookie) > (512 * 1024))
 			log_block_size = 12;
 		else
 			log_block_size = 10;
 	}

         /* FIXME: block size must be > MAX(logicalbs, physicalbs)
          * to avoid modify-on-write.
          *      -- Leslie
          */


 	handle->ops->set_blocksize(handle->cookie, log_block_size);

 	if (numblocks == 0)
 		numblocks = handle->ops->get_size(handle->cookie);

 	if (blocks_per_group == (unsigned int) 0)
 		blocks_per_group = 8 << log_block_size;

 	first_block = (log_block_size == 10) ? 1 : 0;

 	numgroups = ped_div_round_up (numblocks
                         - first_block, blocks_per_group);

 	if (inodes_per_group == 0)
 		inodes_per_group = ped_round_up_to (
 			numblocks / numgroups / 2,
 			(1 << log_block_size) / sizeof(struct ext2_inode));

 	if (sparse_sb == -1)
 		sparse_sb = 1;

         /* FIXME: 5% not appropriate for modern drive sizes */
 	if (reserved_block_percentage == -1)
 		reserved_block_percentage = 5;

 	last_group_blocks = (numblocks - first_block) % blocks_per_group;
 	if (!last_group_blocks) last_group_blocks = blocks_per_group;
 	non_sparse_admin = 2
 			   + inodes_per_group * sizeof(struct ext2_inode)
 			   	/ (1 << log_block_size);
 	sparse_admin = non_sparse_admin
 		       + ped_div_round_up (numgroups
                                        * sizeof(struct ext2_group_desc),
 				  1 << log_block_size);
 	last_group_admin = is_group_sparse(sparse_sb, numgroups - 1)
 			   ? sparse_admin : non_sparse_admin;
 	if (last_group_admin >= last_group_blocks) {
 		numgroups--;
 		numblocks -= last_group_blocks;
 	}
 	if (!numgroups
 	    || (numgroups == 1
 		    && (last_group_blocks - last_group_admin < 8
 	    		|| inodes_per_group < 16))) {
 		ped_exception_throw (
 			PED_EXCEPTION_ERROR,
 			PED_EXCEPTION_CANCEL,
 			_("File system too small for ext2."));
 		goto error;
 	}

 	gd = ped_malloc(numgroups * sizeof(struct ext2_group_desc)
 			+ (1 << log_block_size));
 	if (!gd)
 		goto error;

 	if (!ext2_mkfs_init_sb(&sb, numblocks, numgroups, first_block,
 			       log_block_size, blocks_per_group,
 			       inodes_per_group, sparse_sb,
 			       reserved_block_percentage))
        		goto error_free_gd;
 	if (!ext2_mkfs_write_meta(handle, &sb, gd, timer))
        		goto error_free_gd;
 	if (!ext2_mkfs_write_main(handle, &sb, gd))
        		goto error_free_gd;

 	fs = ext2_open(handle, 0);
 	if (!fs) goto error_close_fs;
 	if (!ext2_reserve_inodes(fs)) goto error_close_fs;
 	if (!ext2_mkfs_create_root_inode(fs)) goto error_close_fs;
 	if (!ext2_mkfs_create_lost_and_found_inode(fs))
 		goto error_close_fs;
 	if (!ext2_sync(fs)) goto error_close_fs;
 	ped_free(gd);
 	return fs;

 error_close_fs:
 	ext2_close(fs);
 error_free_gd:
 	ped_free (gd);
 error:
 	return NULL;
 }
 #endif /* !DISCOVER_ONLY */
	/*
	ext2_mkfs.c -- ext2 fs creator
	Copyright (C) 1999, 2000, 2001, 2007 Free Software Foundation, Inc.

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
	*/

	#include <config.h>

	#ifndef DISCOVER_ONLY

	#define USE_EXT2_IS_DATA_BLOCK

	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>
	#include <sys/stat.h>
	#include <time.h>
	#include <unistd.h>
	#include <uuid/uuid.h>
	#include "ext2.h"

	/* formula grabbed from linux ext2 kernel source
	*
	* returns 1 iff:
	* x == y^N, N is some natural number
	* OR x == 0
	*/
	static __inline__ int is_root(int x, int y)
	{
	if (!x) return 1;

	while (1)
	{
	if (x == 1) return 1;

	if (x % y) return 0;

	x /= y;
	}
	}

	static __inline__ int is_group_sparse(int sparsesbfs, int group)
	{
	if (!sparsesbfs)
	return 1;

	if (is_root(group, 3) \|\| is_root(group, 5) \|\| is_root(group, 7))
	return 1;

	return 0;
	}

	/* has implicit parameter 'sb' !! */
	#define is_sparse(group) is_group_sparse(EXT2_SUPER_FEATURE_RO_COMPAT(*sb) \
	& EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER, (group))

	static int ext2_mkfs_write_main(struct ext2_dev_handle *handle,
	struct ext2_super_block *sb,
	struct ext2_group_desc *gd)
	{
	int freeit;
	int i;
	int numgroups;
	int gdblocks;
	unsigned char *sbbuf;
	struct ext2_super_block *sb_for_io;

	freeit = 0;
	sbbuf = (unsigned char *)sb;
	sb_for_io = sb;
	if (EXT2_SUPER_LOG_BLOCK_SIZE(*sb))
	{
	sbbuf = ped_malloc(1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));
	if (!(handle->ops->read)(handle->cookie, sbbuf, 0, 1))
	return 0;
	memcpy (sbbuf+1024, sb, 1024);
	freeit = 1;
	sb_for_io = (struct ext2_super_block*) (sbbuf + 1024);
	}

	numgroups = ped_div_round_up (EXT2_SUPER_BLOCKS_COUNT(*sb)
	- EXT2_SUPER_FIRST_DATA_BLOCK(*sb),
	EXT2_SUPER_BLOCKS_PER_GROUP(*sb));
	gdblocks = ped_div_round_up (numgroups * sizeof(struct ext2_group_desc),
	1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));

	for (i=0;i<numgroups;i++)
	{
	if (is_sparse(i))
	{
	int offset;

	offset = EXT2_SUPER_FIRST_DATA_BLOCK(*sb)
	+ i * EXT2_SUPER_BLOCKS_PER_GROUP(*sb);

	sb_for_io->s_block_group_nr = PED_CPU_TO_LE16 (i);

	if (!handle->ops->write(handle->cookie, sbbuf,
	offset, 1))
	return 0;
	if (!handle->ops->write(handle->cookie, gd, offset+1,
	gdblocks))
	return 0;
	}
	}

	sb_for_io->s_block_group_nr = 0;

	if (freeit)
	ped_free(sbbuf);
	return 1;
	}

	static int ext2_mkfs_write_meta(struct ext2_dev_handle *handle,
	struct ext2_super_block *sb,
	struct ext2_group_desc *gd,
	PedTimer* timer)
	{
	int blocksize;
	int gdtsize;
	int i;
	int itsize;
	int numgroups;
	unsigned char *bb;
	unsigned char *ib;
	unsigned char *zero;

	blocksize = 1 << (EXT2_SUPER_LOG_BLOCK_SIZE(*sb) + 13);

	numgroups = ped_div_round_up (EXT2_SUPER_BLOCKS_COUNT(*sb)
	- EXT2_SUPER_FIRST_DATA_BLOCK(*sb),
	EXT2_SUPER_BLOCKS_PER_GROUP(*sb));
	itsize = ped_div_round_up (sizeof(struct ext2_inode)
	* EXT2_SUPER_INODES_PER_GROUP(*sb),
	(1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb)));
	gdtsize = ped_div_round_up (sizeof(struct ext2_group_desc) * numgroups,
	(1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb)));

	bb = ped_malloc(1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));
	if (!bb) goto error;
	ib = ped_malloc(1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));
	if (!ib) goto error_free_bb;
	zero = ped_malloc((1024 << EXT2_SUPER_LOG_BLOCK_SIZE(sb)) itsize);
	if (!zero) goto error_free_zero;

	memset(zero, 0, (1024 << EXT2_SUPER_LOG_BLOCK_SIZE(sb)) itsize);

	ped_timer_reset (timer);
	ped_timer_set_state_name (timer, _("writing per-group metadata"));

	for (i=0;i<numgroups;i++)
	{
	int admin;
	blk_t bbblock;
	int groupsize;
	int groupoffset;
	blk_t ibblock;
	int j;

	ped_timer_update (timer, 1.0 * i / numgroups);

	groupoffset = iEXT2_SUPER_BLOCKS_PER_GROUP(sb)
	+ EXT2_SUPER_FIRST_DATA_BLOCK(*sb);
	groupsize = PED_MIN(EXT2_SUPER_BLOCKS_COUNT(*sb) - groupoffset,
	EXT2_SUPER_BLOCKS_PER_GROUP(*sb));

	admin = itsize + 2;
	bbblock = groupoffset;
	ibblock = groupoffset + 1;
	if (is_sparse(i))
	{
	admin += gdtsize + 1;
	bbblock = groupoffset + gdtsize + 1;
	ibblock = groupoffset + gdtsize + 2;
	}

	{
	memset(bb, 0, 1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));
	if (is_sparse(i))
	for (j=0;j<gdtsize+1;j++)
	bb[j>>3] \|= _bitmap[j&7];

	j = bbblock - groupoffset;
	bb[j>>3] \|= _bitmap[j&7];

	j = ibblock - groupoffset;
	bb[j>>3] \|= _bitmap[j&7];

	for (j=0;j<itsize;j++)
	{
	int k = j + gdtsize + 3;

	bb[k>>3] \|= _bitmap[k&7];
	}

	for (j=groupsize;j<blocksize;j++)
	bb[j>>3] \|= _bitmap[j&7];

	if (!handle->ops->write(handle->cookie, bb, bbblock, 1))
	goto error_free_zero;
	}

	{
	memset(ib, 0, 1024 << EXT2_SUPER_LOG_BLOCK_SIZE(*sb));

	for (j=EXT2_SUPER_INODES_PER_GROUP(*sb);j<blocksize;j++)
	bb[j>>3] \|= _bitmap[j&7];

	if (!handle->ops->write(handle->cookie, ib, ibblock, 1))
	goto error_free_zero;
	}

	if (!handle->ops->write(handle->cookie, zero,
	groupoffset + gdtsize + 3, itsize))
	goto error_free_zero;

	gd[i].bg_block_bitmap = PED_CPU_TO_LE32(bbblock);
	gd[i].bg_inode_bitmap = PED_CPU_TO_LE32(ibblock);
	gd[i].bg_inode_table = PED_CPU_TO_LE32(groupoffset + gdtsize
	+ 3);
	gd[i].bg_free_blocks_count = PED_CPU_TO_LE16(groupsize - admin);
	gd[i].bg_free_inodes_count = PED_CPU_TO_LE16(
	EXT2_SUPER_INODES_PER_GROUP(*sb));
	gd[i].bg_used_dirs_count = 0;
	gd[i].bg_used_dirs_count = 0;
	gd[i].bg_pad = 0;
	gd[i].bg_reserved[0] = 0;
	gd[i].bg_reserved[1] = 0;
	gd[i].bg_reserved[2] = 0;

	sb->s_free_blocks_count = PED_CPU_TO_LE32 (
	EXT2_SUPER_FREE_BLOCKS_COUNT(*sb)
	+ EXT2_GROUP_FREE_BLOCKS_COUNT(gd[i]));
	}

	ped_timer_update (timer, 1.0);

	ped_free(zero);
	ped_free(ib);
	ped_free(bb);
	return 1;

	error_free_zero:
	ped_free(zero);
	ped_free(ib);
	error_free_bb:
	ped_free(bb);
	error:
	return 0;
	}

	/* returns the offset into the buffer of the start of the next dir entry */
	static int _set_dirent(void* buf, int offset, int block_size, int is_last,
	uint32_t inode, char* name, int file_type)
	{
	struct ext2_dir_entry_2 dirent = (void) (((char*)buf) + offset);
	int name_len = strlen(name);
	int rec_len;

	if (is_last)
	rec_len = block_size - offset;
	else
	rec_len = ped_round_up_to(name_len + 1 + 8, 4);

	memset (dirent, 0, rec_len);

	dirent->inode = PED_CPU_TO_LE32(inode);
	dirent->name_len = name_len;
	dirent->rec_len = PED_CPU_TO_LE16(rec_len);
	dirent->file_type = file_type;
	strcpy(dirent->name, name);

	return offset + rec_len;
	}

	static int ext2_mkfs_create_lost_and_found_inode(struct ext2_fs *fs)
	{
	struct ext2_buffer_head *bh;
	blk_t blocks[12];
	uint32_t* data = ped_malloc ((fs->blocksize / 4) * sizeof(uint32_t));
	int i;
	struct ext2_inode inode;
	int offset;

	for (i=0;i<12;i++)
	{
	if (!(blocks[i] = ext2_find_free_block(fs)))
	return 0;

	if (!ext2_set_block_state(fs, blocks[i], 1, 1))
	return 0;
	}

	/* create the directory entries, preallocating lots of blocks */
	/* first block contains . and .. */
	bh = ext2_bcreate(fs, blocks[0]);
	if (!bh)
	return 0;
	memset(bh->data, 0, fs->blocksize);
	offset = _set_dirent(bh->data, 0, fs->blocksize, 0,
	11, ".", EXT2_FT_DIR);
	offset = _set_dirent(bh->data, offset, fs->blocksize, 1,
	EXT2_ROOT_INO, "..", EXT2_FT_DIR);
	bh->dirty = 1;
	ext2_brelse(bh, 1);

	/* subsequent blocks are empty */
	memset(data, 0, fs->blocksize);
	data[0] = 0;
	data[1] = PED_CPU_TO_LE32(fs->blocksize);
	for (i=1;i<12;i++)
	{
	bh = ext2_bcreate(fs, blocks[i]);
	memcpy(bh->data, data, fs->blocksize);
	bh->dirty = 1;
	ext2_brelse(bh, 1);
	}

	/* create inode */
	memset(&inode, 0, sizeof(struct ext2_inode));
	inode.i_mode = PED_CPU_TO_LE16(S_IFDIR \| 0755);
	inode.i_uid = 0;
	inode.i_size = PED_CPU_TO_LE32(12 * fs->blocksize);
	inode.i_atime = PED_CPU_TO_LE32(time(NULL));
	inode.i_ctime = PED_CPU_TO_LE32(time(NULL));
	inode.i_mtime = PED_CPU_TO_LE32(time(NULL));
	inode.i_dtime = 0;
	inode.i_gid = 0;
	inode.i_links_count = PED_CPU_TO_LE16(2);
	inode.i_blocks = PED_CPU_TO_LE32((12 * fs->blocksize) >> 9);
	inode.i_flags = 0;
	for (i=0;i<12;i++)
	inode.i_block[i] = PED_CPU_TO_LE32(blocks[i]);

	if (!ext2_write_inode(fs, 11, &inode))
	return 0;
	fs->gd[0].bg_used_dirs_count = PED_CPU_TO_LE16(
	EXT2_GROUP_USED_DIRS_COUNT(fs->gd[0]) + 1);
	fs->metadirty \|= EXT2_META_GD;

	return 1;
	}

	static int ext2_mkfs_create_root_inode(struct ext2_fs *fs)
	{
	struct ext2_buffer_head *bh;
	blk_t block;
	struct ext2_inode inode;
	int offset;

	if (!(block = ext2_find_free_block(fs)))
	return 0;
	if (!ext2_set_block_state(fs, block, 1, 1))
	return 0;

	/* create directory entries */
	bh = ext2_bcreate(fs, block);
	memset(bh->data, 0, fs->blocksize);
	offset = _set_dirent(bh->data, 0, fs->blocksize, 0,
	EXT2_ROOT_INO, ".", EXT2_FT_DIR);
	offset = _set_dirent(bh->data, offset, fs->blocksize, 0,
	EXT2_ROOT_INO, "..", EXT2_FT_DIR);
	offset = _set_dirent(bh->data, offset, fs->blocksize, 1,
	11, "lost+found", EXT2_FT_DIR);
	bh->dirty = 1;
	if (!ext2_brelse(bh, 1))
	return 0;

	/* create inode */
	memset(&inode, 0, sizeof(struct ext2_inode));
	inode.i_mode = PED_CPU_TO_LE16(S_IFDIR \| 0755);
	inode.i_uid = 0;
	inode.i_size = PED_CPU_TO_LE32(fs->blocksize);
	inode.i_atime = PED_CPU_TO_LE32(time(NULL));
	inode.i_ctime = PED_CPU_TO_LE32(time(NULL));
	inode.i_mtime = PED_CPU_TO_LE32(time(NULL));
	inode.i_dtime = 0;
	inode.i_gid = 0;
	inode.i_links_count = PED_CPU_TO_LE16(3);
	inode.i_blocks = PED_CPU_TO_LE32(fs->blocksize >> 9);
	inode.i_flags = 0;
	inode.i_block[0] = PED_CPU_TO_LE32(block);

	if (!ext2_write_inode(fs, 2, &inode))
	return 0;
	fs->gd[0].bg_used_dirs_count = PED_CPU_TO_LE16 (
	EXT2_GROUP_USED_DIRS_COUNT(fs->gd[0]) + 1);
	fs->metadirty \|= EXT2_META_GD;

	return 1;
	}

	static int ext2_reserve_inodes(struct ext2_fs *fs)
	{
	int i;

	for (i=1;i<12;i++)
	if (!ext2_set_inode_state(fs, i, 1, 1))
	return 0;
	return 1;
	}

	static int ext2_mkfs_init_sb (struct ext2_super_block *sb, blk_t numblocks,
	int numgroups, int first_block,
	int log_block_size, blk_t blocks_per_group,
	int inodes_per_group, int sparse_sb,
	int reserved_block_percentage)
	{
	/* catch a bug in gcc 2.95.2 */
	PED_ASSERT(numgroups != 0, return 0);

	memset(sb, 0, 1024);

	sb->s_inodes_count = PED_CPU_TO_LE32(numgroups * inodes_per_group);
	sb->s_blocks_count = PED_CPU_TO_LE32(numblocks);
	sb->s_r_blocks_count = PED_CPU_TO_LE32(((uint64_t)numblocks
	* reserved_block_percentage) / 100);

	/* hack: this get's inc'd as we go through each group in
	* ext2_mkfs_write_meta()
	*/
	sb->s_free_blocks_count = 0;
	sb->s_free_inodes_count = PED_CPU_TO_LE32 (numgroups
	* inodes_per_group);
	sb->s_first_data_block = PED_CPU_TO_LE32(first_block);
	sb->s_log_block_size = PED_CPU_TO_LE32(log_block_size - 10);
	sb->s_log_frag_size = sb->s_log_block_size;
	sb->s_blocks_per_group = PED_CPU_TO_LE32(blocks_per_group);
	sb->s_frags_per_group = PED_CPU_TO_LE32(blocks_per_group);
	sb->s_inodes_per_group = PED_CPU_TO_LE32(inodes_per_group);
	sb->s_mtime = 0;
	sb->s_wtime = 0;
	sb->s_mnt_count = 0;
	sb->s_max_mnt_count = PED_CPU_TO_LE16(30);
	sb->s_magic = PED_CPU_TO_LE16(0xEF53);
	sb->s_state = PED_CPU_TO_LE16(EXT2_VALID_FS);
	sb->s_errors = PED_CPU_TO_LE16(EXT2_ERRORS_DEFAULT);
	sb->s_minor_rev_level = 0;
	sb->s_lastcheck = 0;
	sb->s_checkinterval = 0;
	sb->s_creator_os = 0;
	sb->s_rev_level = PED_CPU_TO_LE32(1);
	sb->s_def_resuid = 0;
	sb->s_def_resgid = 0;
	sb->s_first_ino = PED_CPU_TO_LE32(11);
	sb->s_inode_size = PED_CPU_TO_LE16(128);
	sb->s_block_group_nr = 0;
	sb->s_feature_compat = 0;
	sb->s_feature_incompat = 0;
	sb->s_feature_ro_compat = 0;
	if (sparse_sb)
	sb->s_feature_ro_compat
	\|= PED_CPU_TO_LE32(EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER);

	/* FIXME: let the user decide? _set_dirent() assumes FILETYPE */
	sb->s_feature_incompat
	\|= PED_CPU_TO_LE32(EXT2_FEATURE_INCOMPAT_FILETYPE);

	uuid_generate(sb->s_uuid);
	memset(sb->s_volume_name, 0, 16);
	memset(sb->s_last_mounted, 0, 64);
	sb->s_algorithm_usage_bitmap = 0;
	sb->s_prealloc_blocks = 0;
	sb->s_prealloc_dir_blocks = 0;
	sb->s_padding1 = 0;

	return 1;
	}

	struct ext2_fs ext2_mkfs(struct ext2_dev_handle handle,
	blk_t numblocks,
	int log_block_size,
	blk_t blocks_per_group,
	int inodes_per_group,
	int sparse_sb,
	int reserved_block_percentage,
	PedTimer* timer)
	{
	struct ext2_fs *fs;
	struct ext2_super_block sb;
	struct ext2_group_desc *gd;
	int numgroups;
	int first_block;
	int non_sparse_admin;
	int sparse_admin;
	int last_group_blocks;
	int last_group_admin;

	/* if the FS is > 512Mb, use 4k blocks, otherwise 1k blocks */
	if (log_block_size == 0) {
	handle->ops->set_blocksize(handle->cookie, 12);
	if (handle->ops->get_size(handle->cookie) > (512 * 1024))
	log_block_size = 12;
	else
	log_block_size = 10;
	}

	/* FIXME: block size must be > MAX(logicalbs, physicalbs)
	* to avoid modify-on-write.
	* -- Leslie
	*/


	handle->ops->set_blocksize(handle->cookie, log_block_size);

	if (numblocks == 0)
	numblocks = handle->ops->get_size(handle->cookie);

	if (blocks_per_group == (unsigned int) 0)
	blocks_per_group = 8 << log_block_size;

	first_block = (log_block_size == 10) ? 1 : 0;

	numgroups = ped_div_round_up (numblocks
	- first_block, blocks_per_group);

	if (inodes_per_group == 0)
	inodes_per_group = ped_round_up_to (
	numblocks / numgroups / 2,
	(1 << log_block_size) / sizeof(struct ext2_inode));

	if (sparse_sb == -1)
	sparse_sb = 1;

	/* FIXME: 5% not appropriate for modern drive sizes */
	if (reserved_block_percentage == -1)
	reserved_block_percentage = 5;

	last_group_blocks = (numblocks - first_block) % blocks_per_group;
	if (!last_group_blocks) last_group_blocks = blocks_per_group;
	non_sparse_admin = 2
	+ inodes_per_group * sizeof(struct ext2_inode)
	/ (1 << log_block_size);
	sparse_admin = non_sparse_admin
	+ ped_div_round_up (numgroups
	* sizeof(struct ext2_group_desc),
	1 << log_block_size);
	last_group_admin = is_group_sparse(sparse_sb, numgroups - 1)
	? sparse_admin : non_sparse_admin;
	if (last_group_admin >= last_group_blocks) {
	numgroups--;
	numblocks -= last_group_blocks;
	}
	if (!numgroups
	\|\| (numgroups == 1
	&& (last_group_blocks - last_group_admin < 8
	\|\| inodes_per_group < 16))) {
	ped_exception_throw (
	PED_EXCEPTION_ERROR,
	PED_EXCEPTION_CANCEL,
	_("File system too small for ext2."));
	goto error;
	}

	gd = ped_malloc(numgroups * sizeof(struct ext2_group_desc)
	+ (1 << log_block_size));
	if (!gd)
	goto error;

	if (!ext2_mkfs_init_sb(&sb, numblocks, numgroups, first_block,
	log_block_size, blocks_per_group,
	inodes_per_group, sparse_sb,
	reserved_block_percentage))
	goto error_free_gd;
	if (!ext2_mkfs_write_meta(handle, &sb, gd, timer))
	goto error_free_gd;
	if (!ext2_mkfs_write_main(handle, &sb, gd))
	goto error_free_gd;

	fs = ext2_open(handle, 0);
	if (!fs) goto error_close_fs;
	if (!ext2_reserve_inodes(fs)) goto error_close_fs;
	if (!ext2_mkfs_create_root_inode(fs)) goto error_close_fs;
	if (!ext2_mkfs_create_lost_and_found_inode(fs))
	goto error_close_fs;
	if (!ext2_sync(fs)) goto error_close_fs;
	ped_free(gd);
	return fs;

	error_close_fs:
	ext2_close(fs);
	error_free_gd:
	ped_free (gd);
	error:
	return NULL;
	}
	#endif /* !DISCOVER_ONLY */