diff options
Diffstat (limited to 'toys')
| -rw-r--r-- | toys/e2fs.h | 2 | ||||
| -rw-r--r-- | toys/mke2fs.c | 332 |
2 files changed, 208 insertions, 126 deletions
diff --git a/toys/e2fs.h b/toys/e2fs.h index 08d3a901..13474804 100644 --- a/toys/e2fs.h +++ b/toys/e2fs.h @@ -100,7 +100,7 @@ struct ext2_inode { 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 --git a/toys/mke2fs.c b/toys/mke2fs.c index c9f8d178..30612ee8 100644 --- a/toys/mke2fs.c +++ b/toys/mke2fs.c @@ -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 - - // 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 +#define INODES_RESERVED 10 - // E - extended options (stride=stripe-size blocks) - // O - none,dir_index,filetype,has_journal,journal_dev,sparse_super +static uint32_t div_round_up(uint32_t a, uint32_t b) +{ + uint32_t c = a/b; -#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<dblocks; i++) blocklist[i] = i; + if (dblocks > 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 @@ static uint32_t count_blocks_used(uint64_t size) 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 @@ static long check_treesize(struct dirtree *this, off_t *size) 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 @@ static void check_treelinks(void) // 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 @@ static void create_uuid(char *uuid) 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 @@ static void init_superblock(struct ext2_superblock *sb) // 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 @@ static void init_superblock(struct ext2_superblock *sb) 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 @@ static void init_superblock(struct ext2_superblock *sb) 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 @@ static int is_sb_group(uint32_t group) } -// 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 @@ static int group_superblock_used(uint32_t group) 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<TT.groups; i++) - blocks += group_superblock_used(i) + 2 + inodeblks; - - return blocks; + // Return superblock backup overhead (if any), plus block/inode + // allocation bitmaps, plus inode tables. + return group_superblock_overhead(group) + 2 + get_inodespg(TT.inodespg) + / (TT.blocksize/sizeof(struct ext2_inode)); } +// In bitmap "array" set "len" bits starting at position "start" (from 0). static void bits_set(char *array, int start, int len) { while(len) { @@ -265,9 +278,7 @@ static void bits_set(char *array, int start, int len) // not seekable static void put_zeroes(int len) { - if(TT.noseek || -1 == lseek(TT.fsfd, len, SEEK_SET)) { - - TT.noseek=1; + if(-1 == lseek(TT.fsfd, len, SEEK_SET)) { memset(toybuf, 0, sizeof(toybuf)); while (len) { int out = len > sizeof(toybuf) ? sizeof(toybuf) : len; @@ -277,33 +288,56 @@ static void put_zeroes(int len) } } +// 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; - // This works on Linux. S_ISREG/DIR/CHR/BLK/FIFO/LNK/SOCK(m) - in->mode = this->st.st_mode; + file_blocks_used(this->st.st_size, fbu); - 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; + // If this inode needs data blocks allocated to it. + if (this->st.st_size) { + int i, group = TT.nextblock/TT.blockbits; - in->atime = this->st.st_atime; - in->ctime = this->st.st_ctime; - in->mtime = this->st.st_mtime; + // 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 = 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); + + // 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 @@ int mke2fs_main(void) 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 = 0; - length = check_treesize(TT.dt, &length); - check_treelinks(); // Calculate st_nlink for each node in tree. - - if (TT.gendir && !TT.blocks) { - // Figure out how many blocks of overhead superblock backups and - // group descriptor tables impose. Start with a minimal guess, - // find the overhead for that many groups, and loop until this - // is enough groups to store this many blocks. - TT.groups = (TT.treeblocks/TT.blockbits)+1; - for (;;) { - TT.blocks = TT.treeblocks + get_all_group_blocks(); - if (TT.blocks <= TT.groups * TT.blockbits) break; - TT.groups++; + 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; + } + + // 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<TT.groups; i++) temp += group_overhead(i); + + if (TT.blocks) { + if (TT.blocks < temp) error_exit("Not enough space.\n"); + break; + } + if (temp <= TT.groups * TT.blockbits) { + TT.blocks = temp; + break; } + TT.groups++; } + TT.freeblocks = TT.blocks - temp; - // TT.blocks is now big enough to initialize superblock structure + // Now we know all the TT data, initialize superblock structure. init_superblock(&TT.sb); - temp = get_all_group_blocks(); - if (TT.blocks < TT.treeblocks + temp) error_exit("Not enough space.\n"); - TT.sb.free_blocks_count = SWAP_LE32(TT.blocks - TT.treeblocks - temp); - temp = TT.inodespg*TT.groups - INODES_RESERVED; - if (temp < TT.treeinodes) error_exit("Not enough inodes.\n"); - TT.sb.free_inodes_count = SWAP_LE32(temp - TT.treeinodes); - - // Skip the first 1k to avoid the boot sector (if any) + // Start writing. Skip the first 1k to avoid the boot sector (if any). put_zeroes(1024); // Loop through block groups, write out each one. - usedblocks = 0; - usedinodes = 0; + dtiblk = dtbblk = usedblocks = usedinodes = 0; for (i=0; i<TT.groups; i++) { struct ext2_inode *in = (struct ext2_inode *)toybuf; uint32_t start, itable, used, end; @@ -392,7 +436,7 @@ int mke2fs_main(void) itable = (TT.inodespg*sizeof(struct ext2_inode))/TT.blocksize; // If a superblock goes here, write it out. - start = group_superblock_used(i); + start = group_superblock_overhead(i); if (start) { struct ext2_group *bg = (struct ext2_group *)toybuf; int treeblocks = TT.treeblocks, treeinodes = TT.treeinodes; @@ -410,7 +454,7 @@ int mke2fs_main(void) for(j=0; j<TT.groups; j++) { // Figure out what sector this group starts in. - used = group_superblock_used(j); + used = group_superblock_overhead(j); // Find next array slot in this block (flush block if full). slot = j % (TT.blocksize/sizeof(struct ext2_group)); @@ -487,12 +531,50 @@ int mke2fs_main(void) if (j) xwrite(TT.fsfd, in, TT.blocksize); memset(in, 0, TT.blocksize); } + if (!i && j<INODES_RESERVED) { + // Write root inode + if (j == 2) fill_inode(in+slot, dtb); + } else if (dti) { + fill_inode(in+slot, dti); + dti = treenext(dti); + } } xwrite(TT.fsfd, in, TT.blocksize); - // Write empty data blocks + while (dtb) { + // TODO write index data block + // TODO write root directory data block + // TODO write directory data block + // TODO write file data block + put_zeroes(TT.blocksize); + start++; + if (start == end) break; + } + // Write data blocks (TODO) put_zeroes((end-start) * TT.blocksize); } return 0; } + +// Scratch pad: + // 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 + + // 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 + + // E - extended options (stride=stripe-size blocks) + // O - none,dir_index,filetype,has_journal,journal_dev,sparse_super + + |