annotate www/ext2.html @ 1396:e0c9c5424864 draft

Isaac Dunham spotted that dhcp was also reimplementing daemon().
author Rob Landley <rob@landley.net>
date Sun, 20 Jul 2014 21:34:49 -0500
parents 7a82432fa970
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
107
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
1 <title>Rob's ext2 documentation</title>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
2
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
3 <p>This page focuses on the ext2 on-disk format. The Linux kernel's filesystem
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
4 implementation (the code to read and write it) is documented in the kernel
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
5 source, Documentation/filesystems/ext2.txt.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
6
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
7 <p>Note: for our purposes, ext3 and ext4 are just ext2 with some extra data
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
8 fields.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
9
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
10 <h2>Overview</h2>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
11
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
12 <h2>Blocks and Block Groups</h2>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
13
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
14 <p>Every ext2 filesystem consists of blocks, which are divided into block
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
15 groups. Blocks can be 1k, 2k, or 4k in length.<super><a href="#1">[1]</a></super>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
16 All ext2 disk layout is done in terms of these logical blocks, never in
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
17 terms of 512-byte logical blocks.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
18
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
19 <p>Each block group contains as many blocks as one block can hold a
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
20 bitmap for, so at a 1k block size a block group contains 8192 blocks (1024
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
21 bytes * 8 bits), and at 4k block size a block group contains 32768 blocks.
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
22 Groups are numbered starting at 0, and occur one after another on disk,
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
23 in order, with no gaps between them.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
24
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
25 <p>Block groups contain the following structures, in order:</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
26
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
27 <ul>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
28 <li>Superblock (sometimes)</li>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
29 <li>Group table (sometimes)</li>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
30 <li>Block bitmap</li>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
31 <li>Inode bitmap</li>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
32 <li>Inode table</li>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
33 <li>Data blocks</li>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
34 </ul>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
35
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
36 <p>Not all block groups contain all structures. Specifically, the first two
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
37 (superblock and group table) only occur in some groups, and other block
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
38 groups start with the block bitmap and go from there. This frees up more
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
39 data blocks to hold actual file and directory data, see the superblock
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
40 description for details.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
41
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
42 <p>Each structure in this list is stored in its' own block (or blocks in the
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
43 case of the group and inode tables), and doesn't share blocks with any other
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
44 structure. This can involve padding the end of the block with zeroes, or
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
45 extending tables with extra entries to fill up the rest of the block.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
46
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
47 <p>The linux/ext2_fs.h #include file defines struct ext2_super_block,
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
48 struct ext2_group_desc, struct ext2_inode, struct ext2_dir_entry_2, and a lot
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
49 of constants. Toybox doesn't use this file directly, instead it has an e2fs.h
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
50 include of its own containting cleaned-up versions of the data it needs.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
51
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
52 <h2>Superblock</h2>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
53
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
54 <p>The superblock contains a 1024 byte structure, which toybox calls
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
55 "struct ext2_superblock". Where exactly this structure is to be found is
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
56 a bit complicated for historical reasons.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
57
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
58 <p>For copies of the superblock stored in block groups after the first,
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
59 the superblock structure starts at the beginning of the first block of the
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
60 group, with zero padding afterwards if necessary (I.E. if the block size is
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
61 larger than 1k). In modern "sparse superblock" filesystems (everything
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
62 anyone still cares about), the superblock occurs in group 0 and in later groups
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
63 that are powers of 3, 5, and 7. (So groups 0, 1, 3, 5, 7, 9, 25, 27, 49, 81,
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
64 125, 243, 343...) Any block group starting with a superblock will also
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
65 have a group descriptor table, and ones that don't won't.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
66
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
67 <p>The very first superblock is weird. This is because if you format an entire
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
68 block device (rather than a partition), you stomp the very start of the disk
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
69 which contains the boot sector and the partition table. Back when ext2 on
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
70 floppies was common, this was a big deal.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
71
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
72 <p>So the very first 1024 bytes of the very first block are always left alone.
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
73 When the block size is 1024 bytes, then that block is left alone and the
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
74 superblock is stored in the second block instead<super><a href="#2">[2]</a>.
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
75 When the block size is larger than 1024 bytes, the first superblock starts
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
76 1024 bytes into the block, with the original data preserved by mke2fs and
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
77 appropriate zero padding added to the end of the block (if necessary).</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
78
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
79 <h2>Group descriptor table</h2>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
80 <h2>Block bitmap</h2>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
81 <h2>Inode bitmap</h2>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
82 <h2>Inode table</h2>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
83 <h2>Data blocks</h2>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
84
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
85 <h2>Directories</h2>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
86
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
87 <p>For performance reasons, directory entries are 4-byte aligned (rec_len is
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
88 a multiple of 4), so up to 3 bytes of padding (zeroes) can be added at the end
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
89 of each name. (This affects rec_len but not the name_len.)</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
90
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
91 <p>The last directory entry in each block is padded up to block size. If there
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
92 isn't enough space for another struct ext2_dentry the last </p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
93
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
94 <p>Question: is the length stored in the inode also padded up to block size?</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
95
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
96 <hr />
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
97 <p><a name="1" />Footnote 1: On some systems blocks can be larger than 4k, but
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
98 for implementation reasons not larger than PAGE_SIZE. So the Alpha can have
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
99 8k blocks but most other systems couldn't mount them, thus you don't see this
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
100 out in the wild much anymore.</p>
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
101
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
102 <p><a name="2" />Footnote 2: In this case, the first_data_block field in the
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
103 superblock structure will be set to 1. Otherwise it's always 0. How this
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
104 could POSSIBLY be useful information is an open question, since A) you have to
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
105 read the superblock before you can get this information, so you know where
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
106 it came from, B) the first copy of the superblock always starts at offset 1024
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
107 no matter what, and if your block size is 1024 you already know you skipped the
7a82432fa970 Add web page background image and check in some half-finished ext2
Rob Landley <rob@landley.net>
parents:
diff changeset
108 first block.</p>