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/lzo 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 nine parts, packed together on a
  63 byte 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
  92 Compressed data blocks are written to the filesystem as files are read from
  93 the source directory, and checked for duplicates.  Once all file data has been
  94 written the completed inode, directory, fragment, export and uid/gid lookup
  95 tables are written.
  96
  97 3.1 Compression options
  98 -----------------------
  99
 100 Compressors can optionally support compression specific options (e.g.
 101 dictionary size).  If non-default compression options have been used, then
 102 these are stored here.
 103
 104 3.2 Inodes
 105 ----------
 106
 107 Metadata (inodes and directories) are compressed in 8Kbyte blocks.  Each
 108 compressed block is prefixed by a two byte length, the top bit is set if the
 109 block is uncompressed.  A block will be uncompressed if the -noI option is set,
 110 or if the compressed block was larger than the uncompressed block.
 111
 112 Inodes are packed into the metadata blocks, and are not aligned to block
 113 boundaries, therefore inodes overlap compressed blocks.  Inodes are identified
 114 by a 48-bit number which encodes the location of the compressed metadata block
 115 containing the inode, and the byte offset into that block where the inode is
 116 placed (<block, offset>).
 117
 118 To maximise compression there are different inodes for each file type
 119 (regular file, directory, device, etc.), the inode contents and length
 120 varying with the type.
 121
 122 To further maximise compression, two types of regular file inode and
 123 directory inode are defined: inodes optimised for frequently occurring
 124 regular files and directories, and extended types where extra
 125 information has to be stored.
 126
 127 3.3 Directories
 128 ---------------
 129
 130 Like inodes, directories are packed into compressed metadata blocks, stored
 131 in a directory table.  Directories are accessed using the start address of
 132 the metablock containing the directory and the offset into the
 133 decompressed block (<block, offset>).
 134
 135 Directories are organised in a slightly complex way, and are not simply
 136 a list of file names.  The organisation takes advantage of the
 137 fact that (in most cases) the inodes of the files will be in the same
 138 compressed metadata block, and therefore, can share the start block.
 139 Directories are therefore organised in a two level list, a directory
 140 header containing the shared start block value, and a sequence of directory
 141 entries, each of which share the shared start block.  A new directory header
 142 is written once/if the inode start block changes.  The directory
 143 header/directory entry list is repeated as many times as necessary.
 144
 145 Directories are sorted, and can contain a directory index to speed up
 146 file lookup.  Directory indexes store one entry per metablock, each entry
 147 storing the index/filename mapping to the first directory header
 148 in each metadata block.  Directories are sorted in alphabetical order,
 149 and at lookup the index is scanned linearly looking for the first filename
 150 alphabetically larger than the filename being looked up.  At this point the
 151 location of the metadata block the filename is in has been found.
 152 The general idea of the index is ensure only one metadata block needs to be
 153 decompressed to do a lookup irrespective of the length of the directory.
 154 This scheme has the advantage that it doesn't require extra memory overhead
 155 and doesn't require much extra storage on disk.
 156
 157 3.4 File data
 158 -------------
 159
 160 Regular files consist of a sequence of contiguous compressed blocks, and/or a
 161 compressed fragment block (tail-end packed block).   The compressed size
 162 of each datablock is stored in a block list contained within the
 163 file inode.
 164
 165 To speed up access to datablocks when reading 'large' files (256 Mbytes or
 166 larger), the code implements an index cache that caches the mapping from
 167 block index to datablock location on disk.
 168
 169 The index cache allows Squashfs to handle large files (up to 1.75 TiB) while
 170 retaining a simple and space-efficient block list on disk.  The cache
 171 is split into slots, caching up to eight 224 GiB files (128 KiB blocks).
 172 Larger files use multiple slots, with 1.75 TiB files using all 8 slots.
 173 The index cache is designed to be memory efficient, and by default uses
 174 16 KiB.
 175
 176 3.5 Fragment lookup table
 177 -------------------------
 178
 179 Regular files can contain a fragment index which is mapped to a fragment
 180 location on disk and compressed size using a fragment lookup table.  This
 181 fragment lookup table is itself stored compressed into metadata blocks.
 182 A second index table is used to locate these.  This second index table for
 183 speed of access (and because it is small) is read at mount time and cached
 184 in memory.
 185
 186 3.6 Uid/gid lookup table
 187 ------------------------
 188
 189 For space efficiency regular files store uid and gid indexes, which are
 190 converted to 32-bit uids/gids using an id look up table.  This table is
 191 stored compressed into metadata blocks.  A second index table is used to
 192 locate these.  This second index table for speed of access (and because it
 193 is small) is read at mount time and cached in memory.
 194
 195 3.7 Export table
 196 ----------------
 197
 198 To enable Squashfs filesystems to be exportable (via NFS etc.) filesystems
 199 can optionally (disabled with the -no-exports Mksquashfs option) contain
 200 an inode number to inode disk location lookup table.  This is required to
 201 enable Squashfs to map inode numbers passed in filehandles to the inode
 202 location on disk, which is necessary when the export code reinstantiates
 203 expired/flushed inodes.
 204
 205 This table is stored compressed into metadata blocks.  A second index table is
 206 used to locate these.  This second index table for speed of access (and because
 207 it is small) is read at mount time and cached in memory.
 208
 209 3.8 Xattr table
 210 ---------------
 211
 212 The xattr table contains extended attributes for each inode.  The xattrs
 213 for each inode are stored in a list, each list entry containing a type,
 214 name and value field.  The type field encodes the xattr prefix
 215 ("user.", "trusted." etc) and it also encodes how the name/value fields
 216 should be interpreted.  Currently the type indicates whether the value
 217 is stored inline (in which case the value field contains the xattr value),
 218 or if it is stored out of line (in which case the value field stores a
 219 reference to where the actual value is stored).  This allows large values
 220 to be stored out of line improving scanning and lookup performance and it
 221 also allows values to be de-duplicated, the value being stored once, and
 222 all other occurrences holding an out of line reference to that value.
 223
 224 The xattr lists are packed into compressed 8K metadata blocks.
 225 To reduce overhead in inodes, rather than storing the on-disk
 226 location of the xattr list inside each inode, a 32-bit xattr id
 227 is stored.  This xattr id is mapped into the location of the xattr
 228 list using a second xattr id lookup table.
 229
 230 4. TODOS AND OUTSTANDING ISSUES
 231 -------------------------------
 232
 233 4.1 Todo list
 234 -------------
 235
 236 Implement ACL support.
 237
 238 4.2 Squashfs internal cache
 239 ---------------------------
 240
 241 Blocks in Squashfs are compressed.  To avoid repeatedly decompressing
 242 recently accessed data Squashfs uses two small metadata and fragment caches.
 243
 244 The cache is not used for file datablocks, these are decompressed and cached in
 245 the page-cache in the normal way.  The cache is used to temporarily cache
 246 fragment 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
 248 are packed together into blocks (to gain greater compression) the read of a
 249 particular piece of metadata or fragment will retrieve other metadata/fragments
 250 which have been packed with it, these because of locality-of-reference may be
 251 read in the near future. Temporarily caching them ensures they are available
 252 for near future access without requiring an additional read and decompress.
 253
 254 In the future this internal cache may be replaced with an implementation which
 255 uses the kernel page cache.  Because the page cache operates on page sized
 256 units this may introduce additional complexity in terms of locking and
 257 associated race conditions.