squashfs.rst 11 KB

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