| blob | b324c033035ad097fda59b86897ae0720df9f09b |
1 SQUASHFS 4.0 FILESYSTEM
2 =======================
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).
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.
15 Mailing list: squashfs-devel@lists.sourceforge.net
16 Web site: www.squashfs.org
18 1. FILESYSTEM FEATURES
19 ----------------------
21 Squashfs filesystem features versus Cramfs:
23 Squashfs Cramfs
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 and ACL support: no no
43 Squashfs compresses data, inodes and directories. In addition, inode and
44 directory data are highly compacted, and packed on byte boundaries. Each
45 compressed inode is on average 8 bytes in length (the exact length varies on
46 file type, i.e. regular file, directory, symbolic link, and block/char device
47 inodes have different sizes).
49 2. USING SQUASHFS
50 -----------------
52 As squashfs is a read-only filesystem, the mksquashfs program must be used to
53 create populated squashfs filesystems. This and other squashfs utilities
54 can be obtained from http://www.squashfs.org. Usage instructions can be
55 obtained from this site also.
58 3. SQUASHFS FILESYSTEM DESIGN
59 -----------------------------
61 A squashfs filesystem consists of seven parts, packed together on a byte
62 alignment:
64 ---------------
65 | superblock |
66 |---------------|
67 | datablocks |
68 | & fragments |
69 |---------------|
70 | inode table |
71 |---------------|
72 | directory |
73 | table |
74 |---------------|
75 | fragment |
76 | table |
77 |---------------|
78 | export |
79 | table |
80 |---------------|
81 | uid/gid |
82 | lookup table |
83 ---------------
85 Compressed data blocks are written to the filesystem as files are read from
86 the source directory, and checked for duplicates. Once all file data has been
87 written the completed inode, directory, fragment, export and uid/gid lookup
88 tables are written.
90 3.1 Inodes
91 ----------
93 Metadata (inodes and directories) are compressed in 8Kbyte blocks. Each
94 compressed block is prefixed by a two byte length, the top bit is set if the
95 block is uncompressed. A block will be uncompressed if the -noI option is set,
96 or if the compressed block was larger than the uncompressed block.
98 Inodes are packed into the metadata blocks, and are not aligned to block
99 boundaries, therefore inodes overlap compressed blocks. Inodes are identified
100 by a 48-bit number which encodes the location of the compressed metadata block
101 containing the inode, and the byte offset into that block where the inode is
102 placed (<block, offset>).
104 To maximise compression there are different inodes for each file type
105 (regular file, directory, device, etc.), the inode contents and length
106 varying with the type.
108 To further maximise compression, two types of regular file inode and
109 directory inode are defined: inodes optimised for frequently occurring
110 regular files and directories, and extended types where extra
111 information has to be stored.
113 3.2 Directories
114 ---------------
116 Like inodes, directories are packed into compressed metadata blocks, stored
117 in a directory table. Directories are accessed using the start address of
118 the metablock containing the directory and the offset into the
119 decompressed block (<block, offset>).
121 Directories are organised in a slightly complex way, and are not simply
122 a list of file names. The organisation takes advantage of the
123 fact that (in most cases) the inodes of the files will be in the same
124 compressed metadata block, and therefore, can share the start block.
125 Directories are therefore organised in a two level list, a directory
126 header containing the shared start block value, and a sequence of directory
127 entries, each of which share the shared start block. A new directory header
128 is written once/if the inode start block changes. The directory
129 header/directory entry list is repeated as many times as necessary.
131 Directories are sorted, and can contain a directory index to speed up
132 file lookup. Directory indexes store one entry per metablock, each entry
133 storing the index/filename mapping to the first directory header
134 in each metadata block. Directories are sorted in alphabetical order,
135 and at lookup the index is scanned linearly looking for the first filename
136 alphabetically larger than the filename being looked up. At this point the
137 location of the metadata block the filename is in has been found.
138 The general idea of the index is ensure only one metadata block needs to be
139 decompressed to do a lookup irrespective of the length of the directory.
140 This scheme has the advantage that it doesn't require extra memory overhead
141 and doesn't require much extra storage on disk.
143 3.3 File data
144 -------------
146 Regular files consist of a sequence of contiguous compressed blocks, and/or a
147 compressed fragment block (tail-end packed block). The compressed size
148 of each datablock is stored in a block list contained within the
149 file inode.
151 To speed up access to datablocks when reading 'large' files (256 Mbytes or
152 larger), the code implements an index cache that caches the mapping from
153 block index to datablock location on disk.
155 The index cache allows Squashfs to handle large files (up to 1.75 TiB) while
156 retaining a simple and space-efficient block list on disk. The cache
157 is split into slots, caching up to eight 224 GiB files (128 KiB blocks).
158 Larger files use multiple slots, with 1.75 TiB files using all 8 slots.
159 The index cache is designed to be memory efficient, and by default uses
160 16 KiB.
162 3.4 Fragment lookup table
163 -------------------------
165 Regular files can contain a fragment index which is mapped to a fragment
166 location on disk and compressed size using a fragment lookup table. This
167 fragment lookup table is itself stored compressed into metadata blocks.
168 A second index table is used to locate these. This second index table for
169 speed of access (and because it is small) is read at mount time and cached
170 in memory.
172 3.5 Uid/gid lookup table
173 ------------------------
175 For space efficiency regular files store uid and gid indexes, which are
176 converted to 32-bit uids/gids using an id look up table. This table is
177 stored compressed into metadata blocks. A second index table is used to
178 locate these. This second index table for speed of access (and because it
179 is small) is read at mount time and cached in memory.
181 3.6 Export table
182 ----------------
184 To enable Squashfs filesystems to be exportable (via NFS etc.) filesystems
185 can optionally (disabled with the -no-exports Mksquashfs option) contain
186 an inode number to inode disk location lookup table. This is required to
187 enable Squashfs to map inode numbers passed in filehandles to the inode
188 location on disk, which is necessary when the export code reinstantiates
189 expired/flushed inodes.
191 This table is stored compressed into metadata blocks. A second index table is
192 used to locate these. This second index table for speed of access (and because
193 it is small) is read at mount time and cached in memory.
196 4. TODOS AND OUTSTANDING ISSUES
197 -------------------------------
199 4.1 Todo list
200 -------------
202 Implement Xattr and ACL support. The Squashfs 4.0 filesystem layout has hooks
203 for these but the code has not been written. Once the code has been written
204 the existing layout should not require modification.
206 4.2 Squashfs internal cache
207 ---------------------------
209 Blocks in Squashfs are compressed. To avoid repeatedly decompressing
210 recently accessed data Squashfs uses two small metadata and fragment caches.
212 The cache is not used for file datablocks, these are decompressed and cached in
213 the page-cache in the normal way. The cache is used to temporarily cache
214 fragment and metadata blocks which have been read as a result of a metadata
215 (i.e. inode or directory) or fragment access. Because metadata and fragments
216 are packed together into blocks (to gain greater compression) the read of a
217 particular piece of metadata or fragment will retrieve other metadata/fragments
218 which have been packed with it, these because of locality-of-reference may be
219 read in the near future. Temporarily caching them ensures they are available
220 for near future access without requiring an additional read and decompress.
222 In the future this internal cache may be replaced with an implementation which
223 uses the kernel page cache. Because the page cache operates on page sized
224 units this may introduce additional complexity in terms of locking and
225 associated race conditions.