Mercurial > hg > toybox
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 |
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> |