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