squashfs: update documentation to include description of xattr layout
[linux-2.6.git] / Documentation / filesystems / squashfs.txt
1 SQUASHFS 4.0 FILESYSTEM
2 =======================
3
4 Squashfs is a compressed read-only filesystem for Linux.
5 It uses zlib compression to compress files, inodes and directories.
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
25 Max filesystem size:            2^64                    256 MiB
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
41 Xattr support:                  yes                     no
42 ACL support:                    no                      no
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
62 A squashfs filesystem consists of a maximum of eight parts, packed together on a byte
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 |
84         |---------------|
85         |     xattr     |
86         |     table     |
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
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.
219
220 4. TODOS AND OUTSTANDING ISSUES
221 -------------------------------
222
223 4.1 Todo list
224 -------------
225
226 Implement ACL support.
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.