# HG changeset patch # User Rob Landley # Date 1176946786 14400 # Node ID aadd28817955ee4ca327b2d19677e48ecbfafd63 # Parent a3b8838c39083ab9c2ff9f20e671f2010deecd7c Next iteration of mke2fs development. diff -r a3b8838c3908 -r aadd28817955 toys/e2fs.h --- a/toys/e2fs.h Thu Mar 15 13:59:06 2007 -0400 +++ b/toys/e2fs.h Wed Apr 18 21:39:46 2007 -0400 @@ -100,7 +100,7 @@ uint32_t generation; // File version (for NFS) uint32_t file_acl; // File ACL uint32_t dir_acl; // Directory ACL (or top bits of file length) - uint32_t faddr; // Fragment address + uint32_t faddr; // Last block in file uint8_t frag; // Fragment number uint8_t fsize; // Fragment size uint16_t pad1; diff -r a3b8838c3908 -r aadd28817955 toys/mke2fs.c --- a/toys/mke2fs.c Thu Mar 15 13:59:06 2007 -0400 +++ b/toys/mke2fs.c Wed Apr 18 21:39:46 2007 -0400 @@ -9,34 +9,36 @@ #define TT toy.mke2fs - // b - block size (1024, 2048, 4096) - // F - force (run on mounted device or non-block device) - // i - bytes per inode - // N - number of inodes - // m - reserved blocks percentage - // n - Don't write - // q - quiet +#define INODES_RESERVED 10 - // L - volume label - // M - last mounted path - // o - creator os - - // j - create journal - // J - journal options (size=1024-102400 blocks,device=) - // device=/dev/blah or LABEL=label UUID=uuid +static uint32_t div_round_up(uint32_t a, uint32_t b) +{ + uint32_t c = a/b; - // E - extended options (stride=stripe-size blocks) - // O - none,dir_index,filetype,has_journal,journal_dev,sparse_super - -#define INODES_RESERVED 10 + if (a%b) c++; + return c; +} // Calculate data blocks plus index blocks needed to hold a file. -static uint32_t count_blocks_used(uint64_t size) +static uint32_t file_blocks_used(uint64_t size, uint32_t *blocklist) { uint32_t dblocks = (uint32_t)((size+(TT.blocksize-1))/TT.blocksize); uint32_t idx=TT.blocksize/4, iblocks=0, diblocks=0, tiblocks=0; + // Fill out index blocks. + + if (blocklist) { + int i; + + for (i=0; i<13 && i 13+idx) blocklist[13] = 13+idx; + idx = 13 + idx + (idx*idx); + if (dblocks > idx) blocklist[14] = idx; + + return 0; + } + // Account for direct, singly, doubly, and triply indirect index blocks if (dblocks > 12) { @@ -51,9 +53,18 @@ return dblocks + iblocks + diblocks + tiblocks; } -// Calculate the number of blocks used by each inode. Returns blocks used, -// assigns bytes used to *size. Writes total block count to TT.treeblocks -// and inode count to TT.treeinodes. +// Use the parent pointer to iterate through the tree non-recursively. +static struct dirtree *treenext(struct dirtree *this) +{ + while (this && !this->next) this = this->parent; + if (this) this = this->next; + + return this; +} + +// Recursively calculate the number of blocks used by each inode in the tree. +// Returns blocks used by this directory, assigns bytes used to *size. +// Writes total block count to TT.treeblocks and inode count to TT.treeinodes. static long check_treesize(struct dirtree *this, off_t *size) { @@ -65,44 +76,50 @@ if (this->child) this->st.st_blocks = check_treesize(this->child, &this->st.st_size); else if (S_ISREG(this->st.st_mode)) { - this->st.st_blocks = count_blocks_used(this->st.st_size); + this->st.st_blocks = file_blocks_used(this->st.st_size, 0); TT.treeblocks += this->st.st_blocks; } this = this->next; } - TT.treeblocks += blocks = count_blocks_used(*size); + TT.treeblocks += blocks = file_blocks_used(*size, 0); TT.treeinodes++; return blocks; } -// Use the parent pointer to iterate through the tree non-recursively. -static struct dirtree *treenext(struct dirtree *this) -{ - while (this && !this->next) this = this->parent; - if (this) this = this->next; - - return this; -} - +// Calculate inode numbers and link counts. +// // To do this right I need to copy the tree and sort it, but here's a really // ugly n^2 way of dealing with the problem that doesn't scale well to large -// numbers of files but can be done in very little code. +// numbers of files (> 100,000) but can be done in very little code. +// This rewrites inode numbers to their final values, allocating depth first. -static void check_treelinks(void) +static void check_treelinks(struct dirtree *tree) { - struct dirtree *this, *that; + struct dirtree *this=tree, *that; + long inode = INODES_RESERVED; - for (this = TT.dt; this; this = treenext(this)) { + while (this) { + ++inode; // Since we can't hardlink to directories, we know their link count. if (S_ISDIR(this->st.st_mode)) this->st.st_nlink = 2; else { + dev_t new = this->st.st_dev; + + if (!new) continue; + this->st.st_nlink = 0; - for (that = TT.dt; that; that = treenext(that)) - if (this->st.st_ino == that->st.st_ino) - if (this->st.st_dev == that->st.st_dev) - this->st.st_nlink++; + for (that = tree; that; that = treenext(that)) { + if (this->st.st_ino == that->st.st_ino && + this->st.st_dev == that->st.st_dev) + { + this->st.st_nlink++; + this->st.st_ino = inode; + } + } } + this->st.st_ino = inode; + this = treenext(this); } } @@ -114,7 +131,7 @@ // On the other hand, we have 128 bits to come up with a unique identifier, of // which 6 have a defined value. /dev/urandom it is. -static void create_uuid(char *uuid) +static void fake_uuid(char *uuid) { // Read 128 random bits int fd = xopen("/dev/urandom", O_RDONLY); @@ -131,17 +148,18 @@ uuid[11] = uuid[11] | 128; } -// Figure out inodes per group, rounded up to fill complete inode blocks. +// Calculate inodes per group from total inodes. static uint32_t get_inodespg(uint32_t inodes) { uint32_t temp; + // Round up to fill complete inode blocks. temp = (inodes + TT.groups - 1) / TT.groups; inodes = TT.blocksize/sizeof(struct ext2_inode); return ((temp + inodes - 1)/inodes)*inodes; } -// Fill out superblock and TT +// Fill out superblock and TT structures. static void init_superblock(struct ext2_superblock *sb) { @@ -156,6 +174,7 @@ // Fill out blocks_count, r_blocks_count, first_data_block sb->blocks_count = SWAP_LE32(TT.blocks); + sb->free_blocks_count = SWAP_LE32(TT.freeblocks); temp = (TT.blocks * (uint64_t)TT.reserved_percent) / 100; sb->r_blocks_count = SWAP_LE32(temp); @@ -166,19 +185,15 @@ sb->blocks_per_group = sb->frags_per_group = SWAP_LE32(TT.blockbits); - // How many block groups do we need? (Round up avoiding integer overflow.) - - TT.groups = (TT.blocks)/TT.blockbits; - if (TT.blocks & (TT.blockbits-1)) TT.groups++; - - // Figure out inodes per group, rounded up to block size. - - TT.inodespg = get_inodespg(TT.inodespg); - // Set inodes_per_group and total inodes_count sb->inodes_per_group = SWAP_LE32(TT.inodespg); sb->inodes_count = SWAP_LE32(TT.inodespg * TT.groups); + // Determine free inodes. + temp = TT.inodespg*TT.groups - INODES_RESERVED; + if (temp < TT.treeinodes) error_exit("Not enough inodes.\n"); + sb->free_inodes_count = SWAP_LE32(temp - TT.treeinodes); + // Fill out the rest of the superblock. sb->max_mnt_count=0xFFFF; sb->wtime = sb->lastcheck = sb->mkfs_time = SWAP_LE32(time(NULL)); @@ -191,8 +206,8 @@ sb->feature_incompat = SWAP_LE32(EXT2_FEATURE_INCOMPAT_FILETYPE); sb->feature_ro_compat = SWAP_LE32(EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER); - create_uuid(sb->uuid); - + fake_uuid(sb->uuid); + // TODO If we're called as mke3fs or mkfs.ext3, do a journal. //if (strchr(toys.which->name,'3')) @@ -215,14 +230,14 @@ } -// Number of blocks used in this group by superblock/group list backup. -static int group_superblock_used(uint32_t group) +// Number of blocks used in group by optional superblock/group list backup. +static int group_superblock_overhead(uint32_t group) { int used; if (!is_sb_group(group)) return 0; - // How blocks does the group table take up? + // How many blocks does the group descriptor table take up? used = TT.groups * sizeof(struct ext2_group); used += TT.blocksize - 1; used /= TT.blocksize; @@ -234,18 +249,16 @@ return used; } -static uint32_t get_all_group_blocks(void) +// Number of blocks used in group to store superblock/group/inode list +static int group_overhead(uint32_t group) { - uint32_t i, blocks, inodeblks; - - inodeblks = get_inodespg(TT.inodespg); - inodeblks /= TT.blocksize/sizeof(struct ext2_inode); - for (i = blocks = 0; i sizeof(toybuf) ? sizeof(toybuf) : len; @@ -277,33 +288,56 @@ } } +// Fill out an inode structure from struct stat info in dirtree. static void fill_inode(struct ext2_inode *in, struct dirtree *this) { - memset(in,0,sizeof(struct ext2_inode)); + uint32_t fbu[15]; + int temp; + + file_blocks_used(this->st.st_size, fbu); + + // If this inode needs data blocks allocated to it. + if (this->st.st_size) { + int i, group = TT.nextblock/TT.blockbits; - // This works on Linux. S_ISREG/DIR/CHR/BLK/FIFO/LNK/SOCK(m) - in->mode = this->st.st_mode; + // TODO: teach this about indirect blocks. + for (i=0; i<15; i++) { + // If we just jumped into a new group, skip group overhead blocks. + while (group >= TT.nextgroup) + TT.nextblock += group_overhead(TT.nextgroup++); + } + } + // TODO : S_ISREG/DIR/CHR/BLK/FIFO/LNK/SOCK(m) + in->mode = SWAP_LE32(this->st.st_mode); - in->uid = this->st.st_uid & 0xFFFF; - in->uid_high = this->st.st_uid >> 16; - in->gid = this->st.st_gid & 0xFFFF; - in->gid_high = this->st.st_gid >> 16; - in->size = this->st.st_size & 0xFFFFFFFF; + in->uid = SWAP_LE16(this->st.st_uid & 0xFFFF); + in->uid_high = SWAP_LE16(this->st.st_uid >> 16); + in->gid = SWAP_LE16(this->st.st_gid & 0xFFFF); + in->gid_high = SWAP_LE16(this->st.st_gid >> 16); + in->size = SWAP_LE32(this->st.st_size & 0xFFFFFFFF); - in->atime = this->st.st_atime; - in->ctime = this->st.st_ctime; - in->mtime = this->st.st_mtime; + // Contortions to make the compiler not generate a warning for x>>32 + // when x is 32 bits. The optimizer should clean this up. + if (sizeof(this->st.st_size) > 4) temp = 32; + else temp = 0; + if (temp) in->dir_acl = SWAP_LE32(this->st.st_size >> temp); + + in->atime = SWAP_LE32(this->st.st_atime); + in->ctime = SWAP_LE32(this->st.st_ctime); + in->mtime = SWAP_LE32(this->st.st_mtime); - in->links_count = this->st.st_nlink; - in->blocks = this->st.st_blocks; + in->links_count = SWAP_LE16(this->st.st_nlink); + in->blocks = SWAP_LE32(this->st.st_blocks); + // in->faddr } int mke2fs_main(void) { int i, temp; off_t length; - uint32_t usedblocks, usedinodes; - + uint32_t usedblocks, usedinodes, dtiblk, dtbblk; + struct dirtree *dti, *dtb; + // Handle command line arguments. if (toys.optargs[1]) { @@ -325,60 +359,70 @@ TT.blockbits = 8*TT.blocksize; if (!TT.blocks) TT.blocks = length/TT.blocksize; - // Figure out how many total inodes we need. - - if (!TT.inodespg) { - if (!TT.bytes_per_inode) TT.bytes_per_inode = 8192; - TT.inodespg = (TT.blocks * (uint64_t)TT.blocksize) / TT.bytes_per_inode; - } - // Collect gene2fs list or lost+found, calculate requirements. if (TT.gendir) { strncpy(toybuf, TT.gendir, sizeof(toybuf)); - TT.dt = read_dirtree(toybuf, NULL); + dti = read_dirtree(toybuf, NULL); } else { - TT.dt = xzalloc(sizeof(struct dirtree)+11); - strcpy(TT.dt->name, "lost+found"); - TT.dt->st.st_mode = S_IFDIR|0755; - TT.dt->st.st_ctime = TT.dt->st.st_mtime = time(NULL); + dti = xzalloc(sizeof(struct dirtree)+11); + strcpy(dti->name, "lost+found"); + dti->st.st_mode = S_IFDIR|0755; + dti->st.st_ctime = dti->st.st_mtime = time(NULL); + } + + // Add root directory inode. This is iterated through for when finding + // blocks, but not when finding inodes. The tree's parent pointers don't + // point back into this. + + dtb = xzalloc(sizeof(struct dirtree)+1); + dtb->st.st_mode = S_IFDIR|0755; + dtb->st.st_ctime = dtb->st.st_mtime = time(NULL); + dtb->child = dti; + + // Figure out how much space is used by preset files + length = check_treesize(dtb, &(dtb->st.st_size)); + check_treelinks(dtb); + + // Figure out how many total inodes we need. + + if (!TT.inodes) { + if (!TT.bytes_per_inode) TT.bytes_per_inode = 8192; + TT.inodes = (TT.blocks * (uint64_t)TT.blocksize) / TT.bytes_per_inode; } - // Figure out how much space is used by preset files - length = 0; - length = check_treesize(TT.dt, &length); - check_treelinks(); // Calculate st_nlink for each node in tree. + // If we're generating a filesystem and have no idea how many blocks it + // needs, start with a minimal guess, find the overhead of that many + // groups, and loop until this is enough groups to store this many blocks. + if (!TT.blocks) TT.groups = (TT.treeblocks/TT.blockbits)+1; + else TT.groups = div_round_up(TT.blocks, TT.blockbits); + + for (;;) { + temp = TT.treeblocks; + + for (i = 0; i