Commit | Line | Data |
---|---|---|
9eb425c0 PL |
1 | SQUASHFS 4.0 FILESYSTEM |
2 | ======================= | |
3 | ||
4 | Squashfs is a compressed read-only filesystem for Linux. | |
4b676d2d | 5 | It uses zlib/lzo compression to compress files, inodes and directories. |
9eb425c0 PL |
6 | Inodes in the system are very small and all blocks are packed to minimise |
7 | data overhead. Block sizes greater than 4K are supported up to a maximum | |
8 | of 1Mbytes (default block size 128K). | |
9 | ||
10 | Squashfs is intended for general read-only filesystem use, for archival | |
11 | use (i.e. in cases where a .tar.gz file may be used), and in constrained | |
12 | block device/memory systems (e.g. embedded systems) where low overhead is | |
13 | needed. | |
14 | ||
15 | Mailing list: squashfs-devel@lists.sourceforge.net | |
16 | Web site: www.squashfs.org | |
17 | ||
18 | 1. FILESYSTEM FEATURES | |
19 | ---------------------- | |
20 | ||
21 | Squashfs filesystem features versus Cramfs: | |
22 | ||
23 | Squashfs Cramfs | |
24 | ||
edf2e281 | 25 | Max filesystem size: 2^64 256 MiB |
9eb425c0 PL |
26 | Max file size: ~ 2 TiB 16 MiB |
27 | Max files: unlimited unlimited | |
28 | Max directories: unlimited unlimited | |
29 | Max entries per directory: unlimited unlimited | |
30 | Max block size: 1 MiB 4 KiB | |
31 | Metadata compression: yes no | |
32 | Directory indexes: yes no | |
33 | Sparse file support: yes no | |
34 | Tail-end packing (fragments): yes no | |
35 | Exportable (NFS etc.): yes no | |
36 | Hard link support: yes no | |
37 | "." and ".." in readdir: yes no | |
38 | Real inode numbers: yes no | |
39 | 32-bit uids/gids: yes no | |
40 | File creation time: yes no | |
899f4530 PL |
41 | Xattr support: yes no |
42 | ACL support: no no | |
9eb425c0 PL |
43 | |
44 | Squashfs compresses data, inodes and directories. In addition, inode and | |
45 | directory data are highly compacted, and packed on byte boundaries. Each | |
46 | compressed inode is on average 8 bytes in length (the exact length varies on | |
47 | file type, i.e. regular file, directory, symbolic link, and block/char device | |
48 | inodes have different sizes). | |
49 | ||
50 | 2. USING SQUASHFS | |
51 | ----------------- | |
52 | ||
53 | As squashfs is a read-only filesystem, the mksquashfs program must be used to | |
54 | create populated squashfs filesystems. This and other squashfs utilities | |
55 | can be obtained from http://www.squashfs.org. Usage instructions can be | |
56 | obtained from this site also. | |
57 | ||
58 | ||
59 | 3. SQUASHFS FILESYSTEM DESIGN | |
60 | ----------------------------- | |
61 | ||
899f4530 | 62 | A squashfs filesystem consists of a maximum of eight parts, packed together on a byte |
9eb425c0 PL |
63 | alignment: |
64 | ||
65 | --------------- | |
66 | | superblock | | |
67 | |---------------| | |
68 | | datablocks | | |
69 | | & fragments | | |
70 | |---------------| | |
71 | | inode table | | |
72 | |---------------| | |
73 | | directory | | |
74 | | table | | |
75 | |---------------| | |
76 | | fragment | | |
77 | | table | | |
78 | |---------------| | |
79 | | export | | |
80 | | table | | |
81 | |---------------| | |
82 | | uid/gid | | |
83 | | lookup table | | |
899f4530 PL |
84 | |---------------| |
85 | | xattr | | |
86 | | table | | |
9eb425c0 PL |
87 | --------------- |
88 | ||
89 | Compressed data blocks are written to the filesystem as files are read from | |
90 | the source directory, and checked for duplicates. Once all file data has been | |
91 | written the completed inode, directory, fragment, export and uid/gid lookup | |
92 | tables are written. | |
93 | ||
94 | 3.1 Inodes | |
95 | ---------- | |
96 | ||
97 | Metadata (inodes and directories) are compressed in 8Kbyte blocks. Each | |
98 | compressed block is prefixed by a two byte length, the top bit is set if the | |
99 | block is uncompressed. A block will be uncompressed if the -noI option is set, | |
100 | or if the compressed block was larger than the uncompressed block. | |
101 | ||
102 | Inodes are packed into the metadata blocks, and are not aligned to block | |
103 | boundaries, therefore inodes overlap compressed blocks. Inodes are identified | |
104 | by a 48-bit number which encodes the location of the compressed metadata block | |
105 | containing the inode, and the byte offset into that block where the inode is | |
106 | placed (<block, offset>). | |
107 | ||
108 | To maximise compression there are different inodes for each file type | |
109 | (regular file, directory, device, etc.), the inode contents and length | |
110 | varying with the type. | |
111 | ||
112 | To further maximise compression, two types of regular file inode and | |
113 | directory inode are defined: inodes optimised for frequently occurring | |
114 | regular files and directories, and extended types where extra | |
115 | information has to be stored. | |
116 | ||
117 | 3.2 Directories | |
118 | --------------- | |
119 | ||
120 | Like inodes, directories are packed into compressed metadata blocks, stored | |
121 | in a directory table. Directories are accessed using the start address of | |
122 | the metablock containing the directory and the offset into the | |
123 | decompressed block (<block, offset>). | |
124 | ||
125 | Directories are organised in a slightly complex way, and are not simply | |
126 | a list of file names. The organisation takes advantage of the | |
127 | fact that (in most cases) the inodes of the files will be in the same | |
128 | compressed metadata block, and therefore, can share the start block. | |
129 | Directories are therefore organised in a two level list, a directory | |
130 | header containing the shared start block value, and a sequence of directory | |
131 | entries, each of which share the shared start block. A new directory header | |
132 | is written once/if the inode start block changes. The directory | |
133 | header/directory entry list is repeated as many times as necessary. | |
134 | ||
135 | Directories are sorted, and can contain a directory index to speed up | |
136 | file lookup. Directory indexes store one entry per metablock, each entry | |
137 | storing the index/filename mapping to the first directory header | |
138 | in each metadata block. Directories are sorted in alphabetical order, | |
139 | and at lookup the index is scanned linearly looking for the first filename | |
140 | alphabetically larger than the filename being looked up. At this point the | |
141 | location of the metadata block the filename is in has been found. | |
142 | The general idea of the index is ensure only one metadata block needs to be | |
143 | decompressed to do a lookup irrespective of the length of the directory. | |
144 | This scheme has the advantage that it doesn't require extra memory overhead | |
145 | and doesn't require much extra storage on disk. | |
146 | ||
147 | 3.3 File data | |
148 | ------------- | |
149 | ||
150 | Regular files consist of a sequence of contiguous compressed blocks, and/or a | |
151 | compressed fragment block (tail-end packed block). The compressed size | |
152 | of each datablock is stored in a block list contained within the | |
153 | file inode. | |
154 | ||
155 | To speed up access to datablocks when reading 'large' files (256 Mbytes or | |
156 | larger), the code implements an index cache that caches the mapping from | |
157 | block index to datablock location on disk. | |
158 | ||
159 | The index cache allows Squashfs to handle large files (up to 1.75 TiB) while | |
160 | retaining a simple and space-efficient block list on disk. The cache | |
161 | is split into slots, caching up to eight 224 GiB files (128 KiB blocks). | |
162 | Larger files use multiple slots, with 1.75 TiB files using all 8 slots. | |
163 | The index cache is designed to be memory efficient, and by default uses | |
164 | 16 KiB. | |
165 | ||
166 | 3.4 Fragment lookup table | |
167 | ------------------------- | |
168 | ||
169 | Regular files can contain a fragment index which is mapped to a fragment | |
170 | location on disk and compressed size using a fragment lookup table. This | |
171 | fragment lookup table is itself stored compressed into metadata blocks. | |
172 | A second index table is used to locate these. This second index table for | |
173 | speed of access (and because it is small) is read at mount time and cached | |
174 | in memory. | |
175 | ||
176 | 3.5 Uid/gid lookup table | |
177 | ------------------------ | |
178 | ||
179 | For space efficiency regular files store uid and gid indexes, which are | |
180 | converted to 32-bit uids/gids using an id look up table. This table is | |
181 | stored compressed into metadata blocks. A second index table is used to | |
182 | locate these. This second index table for speed of access (and because it | |
183 | is small) is read at mount time and cached in memory. | |
184 | ||
185 | 3.6 Export table | |
186 | ---------------- | |
187 | ||
188 | To enable Squashfs filesystems to be exportable (via NFS etc.) filesystems | |
189 | can optionally (disabled with the -no-exports Mksquashfs option) contain | |
190 | an inode number to inode disk location lookup table. This is required to | |
191 | enable Squashfs to map inode numbers passed in filehandles to the inode | |
192 | location on disk, which is necessary when the export code reinstantiates | |
193 | expired/flushed inodes. | |
194 | ||
195 | This table is stored compressed into metadata blocks. A second index table is | |
196 | used to locate these. This second index table for speed of access (and because | |
197 | it is small) is read at mount time and cached in memory. | |
198 | ||
899f4530 PL |
199 | 3.7 Xattr table |
200 | --------------- | |
201 | ||
202 | The xattr table contains extended attributes for each inode. The xattrs | |
203 | for each inode are stored in a list, each list entry containing a type, | |
204 | name and value field. The type field encodes the xattr prefix | |
205 | ("user.", "trusted." etc) and it also encodes how the name/value fields | |
206 | should be interpreted. Currently the type indicates whether the value | |
207 | is stored inline (in which case the value field contains the xattr value), | |
208 | or if it is stored out of line (in which case the value field stores a | |
209 | reference to where the actual value is stored). This allows large values | |
210 | to be stored out of line improving scanning and lookup performance and it | |
211 | also allows values to be de-duplicated, the value being stored once, and | |
212 | all other occurences holding an out of line reference to that value. | |
213 | ||
214 | The xattr lists are packed into compressed 8K metadata blocks. | |
215 | To reduce overhead in inodes, rather than storing the on-disk | |
216 | location of the xattr list inside each inode, a 32-bit xattr id | |
217 | is stored. This xattr id is mapped into the location of the xattr | |
218 | list using a second xattr id lookup table. | |
9eb425c0 PL |
219 | |
220 | 4. TODOS AND OUTSTANDING ISSUES | |
221 | ------------------------------- | |
222 | ||
223 | 4.1 Todo list | |
224 | ------------- | |
225 | ||
899f4530 | 226 | Implement ACL support. |
9eb425c0 PL |
227 | |
228 | 4.2 Squashfs internal cache | |
229 | --------------------------- | |
230 | ||
231 | Blocks in Squashfs are compressed. To avoid repeatedly decompressing | |
232 | recently accessed data Squashfs uses two small metadata and fragment caches. | |
233 | ||
234 | The cache is not used for file datablocks, these are decompressed and cached in | |
235 | the page-cache in the normal way. The cache is used to temporarily cache | |
236 | fragment and metadata blocks which have been read as a result of a metadata | |
237 | (i.e. inode or directory) or fragment access. Because metadata and fragments | |
238 | are packed together into blocks (to gain greater compression) the read of a | |
239 | particular piece of metadata or fragment will retrieve other metadata/fragments | |
240 | which have been packed with it, these because of locality-of-reference may be | |
241 | read in the near future. Temporarily caching them ensures they are available | |
242 | for near future access without requiring an additional read and decompress. | |
243 | ||
244 | In the future this internal cache may be replaced with an implementation which | |
245 | uses the kernel page cache. Because the page cache operates on page sized | |
246 | units this may introduce additional complexity in terms of locking and | |
247 | associated race conditions. |