From b90926aafa136c2545703a5f94e769b7e16b3a7e Mon Sep 17 00:00:00 2001 From: Rob Landley Date: Mon, 12 Mar 2007 11:02:04 -0400 Subject: Add web page background image and check in some half-finished ext2 documentation. --- www/ext2.html | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 108 insertions(+) create mode 100644 www/ext2.html (limited to 'www/ext2.html') diff --git a/www/ext2.html b/www/ext2.html new file mode 100644 index 00000000..28bd6cd5 --- /dev/null +++ b/www/ext2.html @@ -0,0 +1,108 @@ +Rob's ext2 documentation + +

This page focuses on the ext2 on-disk format. The Linux kernel's filesystem +implementation (the code to read and write it) is documented in the kernel +source, Documentation/filesystems/ext2.txt.

+ +

Note: for our purposes, ext3 and ext4 are just ext2 with some extra data +fields.

+ +

Overview

+ +

Blocks and Block Groups

+ +

Every ext2 filesystem consists of blocks, which are divided into block +groups. Blocks can be 1k, 2k, or 4k in length.[1] +All ext2 disk layout is done in terms of these logical blocks, never in +terms of 512-byte logical blocks.

+ +

Each block group contains as many blocks as one block can hold a +bitmap for, so at a 1k block size a block group contains 8192 blocks (1024 +bytes * 8 bits), and at 4k block size a block group contains 32768 blocks. +Groups are numbered starting at 0, and occur one after another on disk, +in order, with no gaps between them.

+ +

Block groups contain the following structures, in order:

+ + + +

Not all block groups contain all structures. Specifically, the first two +(superblock and group table) only occur in some groups, and other block +groups start with the block bitmap and go from there. This frees up more +data blocks to hold actual file and directory data, see the superblock +description for details.

+ +

Each structure in this list is stored in its' own block (or blocks in the +case of the group and inode tables), and doesn't share blocks with any other +structure. This can involve padding the end of the block with zeroes, or +extending tables with extra entries to fill up the rest of the block.

+ +

The linux/ext2_fs.h #include file defines struct ext2_super_block, +struct ext2_group_desc, struct ext2_inode, struct ext2_dir_entry_2, and a lot +of constants. Toybox doesn't use this file directly, instead it has an e2fs.h +include of its own containting cleaned-up versions of the data it needs.

+ +

Superblock

+ +

The superblock contains a 1024 byte structure, which toybox calls +"struct ext2_superblock". Where exactly this structure is to be found is +a bit complicated for historical reasons.

+ +

For copies of the superblock stored in block groups after the first, +the superblock structure starts at the beginning of the first block of the +group, with zero padding afterwards if necessary (I.E. if the block size is +larger than 1k). In modern "sparse superblock" filesystems (everything +anyone still cares about), the superblock occurs in group 0 and in later groups +that are powers of 3, 5, and 7. (So groups 0, 1, 3, 5, 7, 9, 25, 27, 49, 81, +125, 243, 343...) Any block group starting with a superblock will also +have a group descriptor table, and ones that don't won't.

+ +

The very first superblock is weird. This is because if you format an entire +block device (rather than a partition), you stomp the very start of the disk +which contains the boot sector and the partition table. Back when ext2 on +floppies was common, this was a big deal.

+ +

So the very first 1024 bytes of the very first block are always left alone. +When the block size is 1024 bytes, then that block is left alone and the +superblock is stored in the second block instead[2]. +When the block size is larger than 1024 bytes, the first superblock starts +1024 bytes into the block, with the original data preserved by mke2fs and +appropriate zero padding added to the end of the block (if necessary).

+ +

Group descriptor table

+

Block bitmap

+

Inode bitmap

+

Inode table

+

Data blocks

+ +

Directories

+ +

For performance reasons, directory entries are 4-byte aligned (rec_len is +a multiple of 4), so up to 3 bytes of padding (zeroes) can be added at the end +of each name. (This affects rec_len but not the name_len.)

+ +

The last directory entry in each block is padded up to block size. If there +isn't enough space for another struct ext2_dentry the last

+ +

Question: is the length stored in the inode also padded up to block size?

+ +
+

Footnote 1: On some systems blocks can be larger than 4k, but +for implementation reasons not larger than PAGE_SIZE. So the Alpha can have +8k blocks but most other systems couldn't mount them, thus you don't see this +out in the wild much anymore.

+ +

Footnote 2: In this case, the first_data_block field in the +superblock structure will be set to 1. Otherwise it's always 0. How this +could POSSIBLY be useful information is an open question, since A) you have to +read the superblock before you can get this information, so you know where +it came from, B) the first copy of the superblock always starts at offset 1024 +no matter what, and if your block size is 1024 you already know you skipped the +first block.

-- cgit v1.2.3