aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRob Landley <rob@landley.net>2007-02-18 16:24:55 -0500
committerRob Landley <rob@landley.net>2007-02-18 16:24:55 -0500
commitcff28b7bcda93a5ac1a3203a6ac8cbef55f23856 (patch)
tree23f6a4eb9f20a15e17f46ebe94f95f295f0da627
parent5f1d7e250f7d91e38d13dcdffb768df55599dfea (diff)
downloadtoybox-cff28b7bcda93a5ac1a3203a6ac8cbef55f23856.tar.gz
Precalculate block and inode usage given a starting file tree. This compiles,
probably doesn't actually work yet.
-rw-r--r--toys/mke2fs.c186
-rw-r--r--toys/toylist.h2
2 files changed, 111 insertions, 77 deletions
diff --git a/toys/mke2fs.c b/toys/mke2fs.c
index 64d65eba..931dec7f 100644
--- a/toys/mke2fs.c
+++ b/toys/mke2fs.c
@@ -55,7 +55,7 @@ static uint32_t count_blocks_used(uint64_t size)
// assigns bytes used to *size. Writes total block count to TT.treeblocks
// and inode count to TT.treeinodes.
-long check_treesize(struct dirtree *this, off_t *size)
+static long check_treesize(struct dirtree *this, off_t *size)
{
long blocks;
@@ -94,11 +94,15 @@ static void check_treelinks(void)
struct dirtree *this, *that;
for (this = TT.dt; this; this = treenext(this)) {
- 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++;
+ // 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 {
+ 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++;
+ }
}
}
@@ -127,6 +131,16 @@ static void create_uuid(char *uuid)
uuid[11] = uuid[11] | 128;
}
+// Figure out inodes per group, rounded up to fill complete inode blocks.
+static uint32_t get_inodespg(uint32_t inodes)
+{
+ uint32_t temp;
+
+ 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
static void init_superblock(struct ext2_superblock *sb)
@@ -142,8 +156,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);
- if (!TT.reserved_percent) TT.reserved_percent = 5;
- temp = (TT.blocks * (uint64_t)TT.reserved_percent) /100;
+ temp = (TT.blocks * (uint64_t)TT.reserved_percent) / 100;
sb->r_blocks_count = SWAP_LE32(temp);
sb->first_data_block = SWAP_LE32(TT.blocksize == 1024 ? 1 : 0);
@@ -151,31 +164,16 @@ static void init_superblock(struct ext2_superblock *sb)
// Set blocks_per_group and frags_per_group, which is the size of an
// allocation bitmap that fits in one block (I.E. how many bits per block)?
- temp = TT.blocksize*8;
- sb->blocks_per_group = sb->frags_per_group = SWAP_LE32(temp);
+ 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)/temp;
- if (TT.blocks & (temp-1)) TT.groups++;
-
- // 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;
- }
+ TT.groups = (TT.blocks)/TT.blockbits;
+ if (TT.blocks & (TT.blockbits-1)) TT.groups++;
// Figure out inodes per group, rounded up to block size.
- // How many blocks of inodes total, rounded up
- temp = TT.inodespg / (TT.blocksize/sizeof(struct ext2_inode));
- if (temp * (TT.blocksize/sizeof(struct ext2_inode)) != TT.inodespg) temp++;
- // How many blocks of inodes per group, again rounded up
- TT.inodespg = temp / TT.groups;
- if (temp & (TT.groups-1)) TT.inodespg++;
- // How many inodes per group is that?
- TT.inodespg *= (TT.blocksize/sizeof(struct ext2_inode));
+ TT.inodespg = get_inodespg(TT.inodespg);
// Set inodes_per_group and total inodes_count
sb->inodes_per_group = SWAP_LE32(TT.inodespg);
@@ -201,34 +199,53 @@ static void init_superblock(struct ext2_superblock *sb)
// sb->feature_compat |= SWAP_LE32(EXT3_FEATURE_COMPAT_HAS_JOURNAL);
}
-// Number of blocks used in this group by superblock/group list backup.
-// Returns 0 if this group doesn't have a superblock backup.
-static int group_superblock_used(uint32_t group)
+// Does this group contain a superblock backup (and group descriptor table)?
+static int is_sb_group(uint32_t group)
{
- int used = 0, i;
+ int i;
// Superblock backups are on groups 0, 1, and powers of 3, 5, and 7.
- if(!group || group==1) used++;
+ if(!group || group==1) return 1;
for (i=3; i<9; i+=2) {
int j = i;
while (j<group) j*=i;
- if (j==group) used++;
+ if (j==group) return 1;
}
+ return 0;
+}
- if (used) {
- // How blocks does the group table take up?
- used = TT.groups * sizeof(struct ext2_group);
- used += TT.blocksize - 1;
- used /= TT.blocksize;
- // Plus the superblock itself.
- used++;
- // And a corner case.
- if (!group && TT.blocksize == 1024) used++;
- }
+
+// Number of blocks used in this group by superblock/group list backup.
+static int group_superblock_used(uint32_t group)
+{
+ int used;
+
+ if (!is_sb_group(group)) return 0;
+
+ // How blocks does the group table take up?
+ used = TT.groups * sizeof(struct ext2_group);
+ used += TT.blocksize - 1;
+ used /= TT.blocksize;
+ // Plus the superblock itself.
+ used++;
+ // And a corner case.
+ if (!group && TT.blocksize == 1024) used++;
return used;
}
+static uint32_t get_all_group_blocks(void)
+{
+ 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;
+}
+
static void bits_set(char *array, int start, int len)
{
while(len) {
@@ -283,7 +300,7 @@ static void fill_inode(struct ext2_inode *in, struct dirtree *this)
int mke2fs_main(void)
{
- int i, temp, blockbits;
+ int i, temp;
off_t length;
// Handle command line arguments.
@@ -292,6 +309,27 @@ int mke2fs_main(void)
sscanf(toys.optargs[1], "%u", &TT.blocks);
temp = O_RDWR|O_CREAT;
} else temp = O_RDWR;
+ if (!TT.reserved_percent) TT.reserved_percent = 5;
+
+ // TODO: Check if filesystem is mounted here
+
+ // For mke?fs, open file. For gene?fs, create file.
+ TT.fsfd = xcreate(*toys.optargs, temp, 0777);
+
+ // Determine appropriate block size and block count from file length.
+ // (If no length, default to 4k. They can override it on the cmdline.)
+
+ length = fdlength(TT.fsfd);
+ if (!TT.blocksize) TT.blocksize = (length && length < 1<<29) ? 1024 : 4096;
+ 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.
@@ -305,50 +343,46 @@ int mke2fs_main(void)
TT.dt->st.st_ctime = TT.dt->st.st_mtime = time(NULL);
}
- // TODO: Check if filesystem is mounted here
-
- // For mke?fs, open file. For gene?fs, create file.
- TT.fsfd = xcreate(*toys.optargs, temp, 0777);
-
- // Determine appropriate block size and block count from file length.
-
- length = fdlength(TT.fsfd);
- if (!TT.blocksize) TT.blocksize = (length && length < 1<<29) ? 1024 : 4096;
- if (!TT.blocks) TT.blocks = length/TT.blocksize;
- if (!TT.blocks) error_exit("gene2fs is a TODO item");
+ // 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++;
+ }
+ }
- // Skip the first 1k to avoid the boot sector (if any), then
- // initialize superblock structure
+ // TT.blocks is now big enough to initialize superblock structure
- put_zeroes(1024);
init_superblock(&TT.sb);
- blockbits = 8*TT.blocksize;
+ temp = get_all_group_blocks();
+ if (TT.blocks < TT.treeblocks + temp) error_exit("Not enough space.\n");
- // Figure out how much space is used
- length = 0;
- length = check_treesize(TT.dt, &length);
- for (temp=i=0; i<TT.groups; i++) {
- temp += group_superblock_used(i) + 2;
- temp += TT.inodespg/(TT.blocksize/sizeof(struct ext2_inode));
- }
TT.sb.free_blocks_count = SWAP_LE32(TT.blocks - TT.treeblocks - temp);
TT.sb.free_inodes_count = SWAP_LE32(TT.inodespg*TT.groups - INODES_RESERVED
- TT.treeinodes);
- // Calculate st_nlink for each node in tree.
-
- check_treelinks();
-
- // Loop through block groups.
+ // Skip the first 1k to avoid the boot sector (if any)
+ put_zeroes(1024);
+ // Loop through block groups, write out each one.
for (i=0; i<TT.groups; i++) {
struct ext2_inode *in = (struct ext2_inode *)toybuf;
uint32_t start, itable, used, end;
int j, slot;
// Where does this group end?
- end = blockbits;
- if ((i+1)*blockbits > TT.blocks) end = TT.blocks & (blockbits-1);
+ end = TT.blockbits;
+ if ((i+1)*TT.blockbits > TT.blocks) end = TT.blocks & (TT.blockbits-1);
// Blocks used by inode table
itable = (TT.inodespg*sizeof(struct ext2_inode))/TT.blocksize;
@@ -391,7 +425,7 @@ int mke2fs_main(void)
bg[slot].free_blocks_count = SWAP_LE32(temp);
// Fill out rest of group structure (TODO: gene2fs allocation)
- used += j*blockbits;
+ used += j*TT.blockbits;
bg[slot].block_bitmap = SWAP_LE32(used++);
bg[slot].inode_bitmap = SWAP_LE32(used++);
bg[slot].inode_table = SWAP_LE32(used);
@@ -406,13 +440,13 @@ int mke2fs_main(void)
memset(toybuf, 0, TT.blocksize);
bits_set(toybuf, 0, start+itable);
- if (end!=blockbits) bits_set(toybuf, end, blockbits-end);
+ if (end!=TT.blockbits) bits_set(toybuf, end, TT.blockbits-end);
xwrite(TT.fsfd, toybuf, TT.blocksize);
// Write inode bitmap (TODO)
memset(toybuf, 0, TT.blocksize);
if (!i) bits_set(toybuf, 0, INODES_RESERVED);
- bits_set(toybuf, TT.inodespg, blockbits-TT.inodespg);
+ bits_set(toybuf, TT.inodespg, TT.blockbits-TT.inodespg);
xwrite(TT.fsfd, toybuf, TT.blocksize);
start += 3;
diff --git a/toys/toylist.h b/toys/toylist.h
index c2fff141..173e870a 100644
--- a/toys/toylist.h
+++ b/toys/toylist.h
@@ -25,7 +25,7 @@ struct mke2fs_data {
long reserved_percent;
char *gendir;
- unsigned blocks, groups, treeblocks, treeinodes;
+ unsigned blocks, groups, blockbits, treeblocks, treeinodes;
int fsfd, noseek;
struct ext2_superblock sb;
struct dirtree *dt;