1 Notes on Filesystem Layout 1 Notes on Filesystem Layout
2 -------------------------- 2 --------------------------
3 3
4 These notes describe what mkcramfs generates. 4 These notes describe what mkcramfs generates. Kernel requirements are
5 a bit looser, e.g. it doesn't care if the <fil 5 a bit looser, e.g. it doesn't care if the <file_data> items are
6 swapped around (though it does care that direc 6 swapped around (though it does care that directory entries (inodes) in
7 a given directory are contiguous, as this is u 7 a given directory are contiguous, as this is used by readdir).
8 8
9 All data is currently in host-endian format; n 9 All data is currently in host-endian format; neither mkcramfs nor the
10 kernel ever do swabbing. (See section `Block 10 kernel ever do swabbing. (See section `Block Size' below.)
11 11
12 <filesystem>: 12 <filesystem>:
13 <superblock> 13 <superblock>
14 <directory_structure> 14 <directory_structure>
15 <data> 15 <data>
16 16
17 <superblock>: struct cramfs_super (see cramfs_ 17 <superblock>: struct cramfs_super (see cramfs_fs.h).
18 18
19 <directory_structure>: 19 <directory_structure>:
20 For each file: 20 For each file:
21 struct cramfs_inode (see cramf 21 struct cramfs_inode (see cramfs_fs.h).
22 Filename. Not generally null- 22 Filename. Not generally null-terminated, but it is
23 null-padded to a multiple of 23 null-padded to a multiple of 4 bytes.
24 24
25 The order of inode traversal is described as " 25 The order of inode traversal is described as "width-first" (not to be
26 confused with breadth-first); i.e. like depth- 26 confused with breadth-first); i.e. like depth-first but listing all of
27 a directory's entries before recursing down it 27 a directory's entries before recursing down its subdirectories: the
28 same order as `ls -AUR' (but without the /^\.. 28 same order as `ls -AUR' (but without the /^\..*:$/ directory header
29 lines); put another way, the same order as `fi 29 lines); put another way, the same order as `find -type d -exec
30 ls -AU1 {} \;'. 30 ls -AU1 {} \;'.
31 31
32 Beginning in 2.4.7, directory entries are sort 32 Beginning in 2.4.7, directory entries are sorted. This optimization
33 allows cramfs_lookup to return more quickly wh 33 allows cramfs_lookup to return more quickly when a filename does not
34 exist, speeds up user-space directory sorts, e 34 exist, speeds up user-space directory sorts, etc.
35 35
36 <data>: 36 <data>:
37 One <file_data> for each file that's e 37 One <file_data> for each file that's either a symlink or a
38 regular file of non-zero st_size. 38 regular file of non-zero st_size.
39 39
40 <file_data>: 40 <file_data>:
41 nblocks * <block_pointer> 41 nblocks * <block_pointer>
42 (where nblocks = (st_size - 1) / blks 42 (where nblocks = (st_size - 1) / blksize + 1)
43 nblocks * <block> 43 nblocks * <block>
44 padding to multiple of 4 bytes 44 padding to multiple of 4 bytes
45 45
46 The i'th <block_pointer> for a file stores the 46 The i'th <block_pointer> for a file stores the byte offset of the
47 *end* of the i'th <block> (i.e. one past the l 47 *end* of the i'th <block> (i.e. one past the last byte, which is the
48 same as the start of the (i+1)'th <block> if t 48 same as the start of the (i+1)'th <block> if there is one). The first
49 <block> immediately follows the last <block_po 49 <block> immediately follows the last <block_pointer> for the file.
50 <block_pointer>s are each 32 bits long. 50 <block_pointer>s are each 32 bits long.
51 51
52 When the CRAMFS_FLAG_EXT_BLOCK_POINTERS capabi <<
53 <block_pointer>'s top bits may contain special <<
54 <<
55 CRAMFS_BLK_FLAG_UNCOMPRESSED (bit 31): <<
56 The block data is not compressed and s <<
57 <<
58 CRAMFS_BLK_FLAG_DIRECT_PTR (bit 30): <<
59 The <block_pointer> stores the actual <<
60 its end, shifted right by 2 bits. The <<
61 aligned to a 4-byte boundary. The bloc <<
62 if CRAMFS_BLK_FLAG_UNCOMPRESSED is als <<
63 the compressed data length is included <<
64 the block data. This is used to allow <<
65 and specific data block alignments e.g <<
66 <<
67 <<
68 The order of <file_data>'s is a depth-first de 52 The order of <file_data>'s is a depth-first descent of the directory
69 tree, i.e. the same order as `find -size +0 \( 53 tree, i.e. the same order as `find -size +0 \( -type f -o -type l \)
70 -print'. 54 -print'.
71 55
72 56
73 <block>: The i'th <block> is the output of zli 57 <block>: The i'th <block> is the output of zlib's compress function
74 applied to the i'th blksize-sized chunk of the !! 58 applied to the i'th blksize-sized chunk of the input data.
75 corresponding CRAMFS_BLK_FLAG_UNCOMPRESSED <bl <<
76 otherwise it is the input data directly. <<
77 (For the last <block> of the file, the input m 59 (For the last <block> of the file, the input may of course be smaller.)
78 Each <block> may be a different size. (See <b 60 Each <block> may be a different size. (See <block_pointer> above.)
79 <<
80 <block>s are merely byte-aligned, not generall 61 <block>s are merely byte-aligned, not generally u32-aligned.
81 62
82 When CRAMFS_BLK_FLAG_DIRECT_PTR is specified t <<
83 <block> may be located anywhere and not necess <<
84 the previous/next blocks. In that case it is m <<
85 If CRAMFS_BLK_FLAG_UNCOMPRESSED is also specif <<
86 blksize except for the last block which is lim <<
87 If CRAMFS_BLK_FLAG_DIRECT_PTR is set and CRAMF <<
88 is not set then the first 2 bytes of the block <<
89 remaining block data as this cannot be determi <<
90 logically adjacent blocks. <<
91 <<
92 63
93 Holes 64 Holes
94 ----- 65 -----
95 66
96 This kernel supports cramfs holes (i.e. [effic 67 This kernel supports cramfs holes (i.e. [efficient representation of]
97 blocks in uncompressed data consisting entirel 68 blocks in uncompressed data consisting entirely of NUL bytes), but by
98 default mkcramfs doesn't test for & create hol 69 default mkcramfs doesn't test for & create holes, since cramfs in
99 kernels up to at least 2.3.39 didn't support h 70 kernels up to at least 2.3.39 didn't support holes. Run mkcramfs
100 with -z if you want it to create files that ca 71 with -z if you want it to create files that can have holes in them.
101 72
102 73
103 Tools 74 Tools
104 ----- 75 -----
105 76
106 The cramfs user-space tools, including mkcramf 77 The cramfs user-space tools, including mkcramfs and cramfsck, are
107 located at <http://sourceforge.net/projects/cr 78 located at <http://sourceforge.net/projects/cramfs/>.
108 79
109 80
110 Future Development 81 Future Development
111 ================== 82 ==================
112 83
113 Block Size 84 Block Size
114 ---------- 85 ----------
115 86
116 (Block size in cramfs refers to the size of in 87 (Block size in cramfs refers to the size of input data that is
117 compressed at a time. It's intended to be som 88 compressed at a time. It's intended to be somewhere around
118 PAGE_SIZE for cramfs_read_folio's convenience. !! 89 PAGE_SIZE for cramfs_readpage's convenience.)
119 90
120 The superblock ought to indicate the block siz 91 The superblock ought to indicate the block size that the fs was
121 written for, since comments in <linux/pagemap. 92 written for, since comments in <linux/pagemap.h> indicate that
122 PAGE_SIZE may grow in future (if I interpret t 93 PAGE_SIZE may grow in future (if I interpret the comment
123 correctly). 94 correctly).
124 95
125 Currently, mkcramfs #define's PAGE_SIZE as 409 96 Currently, mkcramfs #define's PAGE_SIZE as 4096 and uses that
126 for blksize, whereas Linux-2.3.39 uses its PAG 97 for blksize, whereas Linux-2.3.39 uses its PAGE_SIZE, which in
127 turn is defined as PAGE_SIZE (which can be as 98 turn is defined as PAGE_SIZE (which can be as large as 32KB on arm).
128 This discrepancy is a bug, though it's not cle 99 This discrepancy is a bug, though it's not clear which should be
129 changed. 100 changed.
130 101
131 One option is to change mkcramfs to take its P 102 One option is to change mkcramfs to take its PAGE_SIZE from
132 <asm/page.h>. Personally I don't like this op 103 <asm/page.h>. Personally I don't like this option, but it does
133 require the least amount of change: just chang 104 require the least amount of change: just change `#define
134 PAGE_SIZE (4096)' to `#include <asm/page.h>'. 105 PAGE_SIZE (4096)' to `#include <asm/page.h>'. The disadvantage
135 is that the generated cramfs cannot always be 106 is that the generated cramfs cannot always be shared between different
136 kernels, not even necessarily kernels of the s 107 kernels, not even necessarily kernels of the same architecture if
137 PAGE_SIZE is subject to change between kernel 108 PAGE_SIZE is subject to change between kernel versions
138 (currently possible with arm and ia64). 109 (currently possible with arm and ia64).
139 110
140 The remaining options try to make cramfs more 111 The remaining options try to make cramfs more sharable.
141 112
142 One part of that is addressing endianness. Th 113 One part of that is addressing endianness. The two options here are
143 `always use little-endian' (like ext2fs) or `w 114 `always use little-endian' (like ext2fs) or `writer chooses
144 endianness; kernel adapts at runtime'. Little 115 endianness; kernel adapts at runtime'. Little-endian wins because of
145 code simplicity and little CPU overhead even o 116 code simplicity and little CPU overhead even on big-endian machines.
146 117
147 The cost of swabbing is changing the code to u 118 The cost of swabbing is changing the code to use the le32_to_cpu
148 etc. macros as used by ext2fs. We don't need 119 etc. macros as used by ext2fs. We don't need to swab the compressed
149 data, only the superblock, inodes and block po 120 data, only the superblock, inodes and block pointers.
150 121
151 122
152 The other part of making cramfs more sharable 123 The other part of making cramfs more sharable is choosing a block
153 size. The options are: 124 size. The options are:
154 125
155 1. Always 4096 bytes. 126 1. Always 4096 bytes.
156 127
157 2. Writer chooses blocksize; kernel adapts b 128 2. Writer chooses blocksize; kernel adapts but rejects blocksize >
158 PAGE_SIZE. 129 PAGE_SIZE.
159 130
160 3. Writer chooses blocksize; kernel adapts e 131 3. Writer chooses blocksize; kernel adapts even to blocksize >
161 PAGE_SIZE. 132 PAGE_SIZE.
162 133
163 It's easy enough to change the kernel to use a 134 It's easy enough to change the kernel to use a smaller value than
164 PAGE_SIZE: just make cramfs_read_folio read mu !! 135 PAGE_SIZE: just make cramfs_readpage read multiple blocks.
165 136
166 The cost of option 1 is that kernels with a la 137 The cost of option 1 is that kernels with a larger PAGE_SIZE
167 value don't get as good compression as they ca 138 value don't get as good compression as they can.
168 139
169 The cost of option 2 relative to option 1 is t 140 The cost of option 2 relative to option 1 is that the code uses
170 variables instead of #define'd constants. The 141 variables instead of #define'd constants. The gain is that people
171 with kernels having larger PAGE_SIZE can make 142 with kernels having larger PAGE_SIZE can make use of that if
172 they don't mind their cramfs being inaccessibl 143 they don't mind their cramfs being inaccessible to kernels with
173 smaller PAGE_SIZE values. 144 smaller PAGE_SIZE values.
174 145
175 Option 3 is easy to implement if we don't mind 146 Option 3 is easy to implement if we don't mind being CPU-inefficient:
176 e.g. get read_folio to decompress to a buffer !! 147 e.g. get readpage to decompress to a buffer of size MAX_BLKSIZE (which
177 must be no larger than 32KB) and discard what 148 must be no larger than 32KB) and discard what it doesn't need.
178 Getting read_folio to read into all the covere !! 149 Getting readpage to read into all the covered pages is harder.
179 150
180 The main advantage of option 3 over 1, 2, is b 151 The main advantage of option 3 over 1, 2, is better compression. The
181 cost is greater complexity. Probably not wort 152 cost is greater complexity. Probably not worth it, but I hope someone
182 will disagree. (If it is implemented, then I' 153 will disagree. (If it is implemented, then I'll re-use that code in
183 e2compr.) 154 e2compr.)
184 155
185 156
186 Another cost of 2 and 3 over 1 is making mkcra 157 Another cost of 2 and 3 over 1 is making mkcramfs use a different
187 block size, but that just means adding and par 158 block size, but that just means adding and parsing a -b option.
188 159
189 160
190 Inode Size 161 Inode Size
191 ---------- 162 ----------
192 163
193 Given that cramfs will probably be used for CD 164 Given that cramfs will probably be used for CDs etc. as well as just
194 silicon ROMs, it might make sense to expand th 165 silicon ROMs, it might make sense to expand the inode a little from
195 its current 12 bytes. Inodes other than the r 166 its current 12 bytes. Inodes other than the root inode are followed
196 by filename, so the expansion doesn't even hav 167 by filename, so the expansion doesn't even have to be a multiple of 4
197 bytes. 168 bytes.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.