Squashfs 4.0 Filesystem

Squashfs 4.0 개요와 기능

Squashfs는 Linux용 압축 read-only 파일 시스템이다. zlib, lz4, lzo, xz, zstd로 file data뿐 아니라 inode와 directory도 압축한다. inode는 매우 작고 모든 block을 촘촘히 pack해 overhead를 줄인다. 4KB보다 큰 block을 최대 1MB까지 지원하며 기본 block 크기는 128KB다.

일반 read-only 배포, `.tar.gz`를 쓸 법한 archive, 낮은 overhead가 중요한 embedded block device·memory 시스템을 목표로 한다. kernel code 문의는 `linux-fsdevel@vger.kernel.org`, 도구 source는 `github.com/plougher/squashfs-tools`에 있다.

inode와 directory data는 byte boundary에 맞춰 강하게 compact된다. 압축 inode 하나는 평균 약 8 byte지만 regular file, directory, symbolic link, block·character device 등 file type마다 구조와 길이가 다르다.

.. SPDX-License-Identifier: GPL-2.0

=======================
Squashfs 4.0 Filesystem
=======================

Squashfs is a compressed read-only filesystem for Linux.

It uses zlib, lz4, lzo, xz or zstd compression to compress files, inodes and
directories.  Inodes in the system are very small and all blocks are packed to
minimise data overhead. Block sizes greater than 4K are supported up to a
maximum of 1Mbytes (default block size 128K).

Squashfs is intended for general read-only filesystem use, for archival
use (i.e. in cases where a .tar.gz file may be used), and in constrained
block device/memory systems (e.g. embedded systems) where low overhead is
needed.

Mailing list (kernel code): linux-fsdevel@vger.kernel.org
Web site: github.com/plougher/squashfs-tools

1. Filesystem Features
----------------------

Squashfs filesystem features versus Cramfs:

==============================         =========                ==========
                                Squashfs                Cramfs
==============================         =========                ==========
Max filesystem size                2^64                        256 MiB
Max file size                        ~ 2 TiB                        16 MiB
Max files                        unlimited                unlimited
Max directories                        unlimited                unlimited
Max entries per directory        unlimited                unlimited
Max block size                        1 MiB                        4 KiB
Metadata compression                yes                        no
Directory indexes                yes                        no
Sparse file support                yes                        no
Tail-end packing (fragments)        yes                        no
Exportable (NFS etc.)                yes                        no
Hard link support                yes                        no
"." and ".." in readdir                yes                        no
Real inode numbers                yes                        no
32-bit uids/gids                yes                        no
File creation time                yes                        no
Xattr support                        yes                        no
ACL support                        no                        no
==============================         =========                ==========

Squashfs compresses data, inodes and directories.  In addition, inode and
directory data are highly compacted, and packed on byte boundaries.  Each
compressed inode is on average 8 bytes in length (the exact length varies on
file type, i.e. regular file, directory, symbolic link, and block/char device
inodes have different sizes).

생성 도구와 mount option

read-only 파일 시스템이므로 내용이 채워진 image는 `mksquashfs`로 만든다. 배포판은 대개 이 프로그램과 유틸리티를 `squashfs-tools` package로 제공하며 source와 사용법도 프로젝트 site에서 얻을 수 있다.

`errors=continue`는 오류가 발생해도 panic하지 않는 기본값이다. `errors=panic`은 corruption을 만났을 때 ext4·btrfs 등과 비슷하게 kernel panic을 일으켜 분석용 kernel dump를 저장할 수 있게 한다.

`threads=`는 decompression mode 또는 thread 수를 정한다. `SQUASHFS_CHOICE_DECOMP_BY_MOUNT`가 켜지면 `single`, `multi`, `percpu`, 숫자를 선택할 수 있다. single은 동시 block 하나라 CPU·memory가 최소지만 parallel I/O가 느리다. multi는 core당 최대 두 decompressor를 수요에 따라 동적 할당한다. percpu는 core당 최대 하나를 두고 percpu variable로 load balance한다. 숫자 지정 상한은 `num_online_cpus() * 2`다.

mount 선택 기능은 없지만 `SQUASHFS_DECOMP_MULTI`와 `SQUASHFS_MOUNT_DECOMP_THREADS`가 모두 켜진 구성에서는 `threads=2|3|...`로 수를 지정하며 같은 상한을 적용한다.

2. Using Squashfs
-----------------

As squashfs is a read-only filesystem, the mksquashfs program must be used to
create populated squashfs filesystems.  This and other squashfs utilities
are very likely packaged by your linux distribution (called squashfs-tools).
The source code can be obtained from github.com/plougher/squashfs-tools.
Usage instructions can also be obtained from this site.

2.1 Mount options
-----------------
===================    =========================================================
errors=%s              Specify whether squashfs errors trigger a kernel panic
                       or not

                       ==========  =============================================
                         continue  errors don't trigger a panic (default)
                            panic  trigger a panic when errors are encountered,
                                   similar to several other filesystems (e.g.
                                   btrfs, ext4, f2fs, GFS2, jfs, ntfs, ubifs)

                                   This allows a kernel dump to be saved,
                                   useful for analyzing and debugging the
                                   corruption.
                       ==========  =============================================
threads=%s             Select the decompression mode or the number of threads

                       If SQUASHFS_CHOICE_DECOMP_BY_MOUNT is set:

                       ==========  =============================================
                           single  use single-threaded decompression (default)

                                   Only one block (data or metadata) can be
                                   decompressed at any one time. This limits
                                   CPU and memory usage to a minimum, but it
                                   also gives poor performance on parallel I/O
                                   workloads when using multiple CPU machines
                                   due to waiting on decompressor availability.
                            multi  use up to two parallel decompressors per core

                                   If you have a parallel I/O workload and your
                                   system has enough memory, using this option
                                   may improve overall I/O performance. It
                                   dynamically allocates decompressors on a
                                   demand basis.
                           percpu  use a maximum of one decompressor per core

                                   It uses percpu variables to ensure
                                   decompression is load-balanced across the
                                   cores.
                        1|2|3|...  configure the number of threads used for
                                   decompression

                                   The upper limit is num_online_cpus() * 2.
                       ==========  =============================================

                       If SQUASHFS_CHOICE_DECOMP_BY_MOUNT is **not** set and
                       SQUASHFS_DECOMP_MULTI, SQUASHFS_MOUNT_DECOMP_THREADS are
                       both set:

                       ==========  =============================================
                          2|3|...  configure the number of threads used for
                                   decompression

                                   The upper limit is num_online_cpus() * 2.
                       ==========  =============================================

===================    =========================================================

파일 시스템의 최대 아홉 영역

Squashfs image는 byte alignment로 연속 배치되는 최대 아홉 부분으로 구성된다. compression option은 non-default compressor 설정이 있을 때만 존재하고, export·xattr 같은 optional table도 설정에 따라 생략될 수 있다.

source directory에서 file을 읽는 동안 압축 data block을 image에 쓰고 duplicate를 검사한다. 모든 file data가 끝난 다음 완성된 inode, directory, fragment, export, uid/gid lookup, xattr table을 기록한다.

3. Squashfs Filesystem Design
-----------------------------

A squashfs filesystem consists of a maximum of nine parts, packed together on a
byte alignment::

         ---------------
        |  superblock         |
        |---------------|
        |  compression  |
        |    options    |
        |---------------|
        |  datablocks   |
        |  & fragments  |
        |---------------|
        |  inode table        |
        |---------------|
        |   directory        |
        |     table     |
        |---------------|
        |   fragment        |
        |    table      |
        |---------------|
        |    export     |
        |    table      |
        |---------------|
        |    uid/gid        |
        |  lookup table        |
        |---------------|
        |     xattr     |
        |     table        |
         ---------------

Compressed data blocks are written to the filesystem as files are read from
the source directory, and checked for duplicates.  Once all file data has been
written the completed inode, directory, fragment, export, uid/gid lookup and
xattr tables are written.

압축 option과 inode 주소

compressor는 dictionary size 같은 고유 option을 선택적으로 지원한다. 기본값이 아닌 option을 썼을 때 image의 compression options 영역에 저장한다.

inode와 directory metadata는 8KB block으로 압축된다. 각 block 앞에는 2-byte 길이가 있고 최상위 bit는 block이 uncompressed임을 뜻한다. `-noI`를 사용했거나 압축 결과가 원본보다 커졌으면 uncompressed로 저장한다.

inode는 metadata block 안에 block boundary alignment 없이 이어 붙기 때문에 압축 block 경계를 가로지를 수 있다. inode의 48-bit 번호는 inode를 포함하는 압축 metadata block 위치와 decompressed block 내부 byte offset을 `<block, offset>`으로 encoding한다.

압축률을 높이기 위해 regular file, directory, device 등 file type별 inode 구조와 길이가 다르다. 자주 나타나는 regular file·directory용 compact type과 추가 정보가 필요한 extended type도 별도로 정의한다.

3.1 Compression options
-----------------------

Compressors can optionally support compression specific options (e.g.
dictionary size).  If non-default compression options have been used, then
these are stored here.

3.2 Inodes
----------

Metadata (inodes and directories) are compressed in 8Kbyte blocks.  Each
compressed block is prefixed by a two byte length, the top bit is set if the
block is uncompressed.  A block will be uncompressed if the -noI option is set,
or if the compressed block was larger than the uncompressed block.

Inodes are packed into the metadata blocks, and are not aligned to block
boundaries, therefore inodes overlap compressed blocks.  Inodes are identified
by a 48-bit number which encodes the location of the compressed metadata block
containing the inode, and the byte offset into that block where the inode is
placed (<block, offset>).

To maximise compression there are different inodes for each file type
(regular file, directory, device, etc.), the inode contents and length
varying with the type.

To further maximise compression, two types of regular file inode and
directory inode are defined: inodes optimised for frequently occurring
regular files and directories, and extended types where extra
information has to be stored.

Directory의 2단계 list와 index

directory도 압축 metadata block에 pack되어 directory table에 저장된다. 접근 주소는 directory를 포함한 metablock의 시작 주소와 decompressed block 내부 offset인 `<block, offset>`이다.

단순 filename list가 아니라 inode가 대개 같은 압축 metadata block에 있다는 점을 이용한 2단계 list다. directory header가 공유 inode start block을 한 번 저장하고, 뒤의 여러 directory entry가 그 값을 공유한다. inode start block이 바뀔 때 새 header를 쓰며 필요한 만큼 header·entry 묶음을 반복한다.

directory는 alphabetic order로 정렬되고 lookup을 빠르게 할 index를 가질 수 있다. index는 metablock마다 entry 하나를 두어 그 block의 첫 directory header에 해당하는 index·filename mapping을 저장한다. 찾는 이름보다 사전순으로 처음 큰 filename을 만날 때까지 선형 scan하면 대상 metadata block을 알 수 있다.

이 방식은 directory 길이와 상관없이 lookup마다 metadata block 하나만 decompress하게 하면서 추가 memory와 disk 공간을 거의 요구하지 않는다.

3.3 Directories
---------------

Like inodes, directories are packed into compressed metadata blocks, stored
in a directory table.  Directories are accessed using the start address of
the metablock containing the directory and the offset into the
decompressed block (<block, offset>).

Directories are organised in a slightly complex way, and are not simply
a list of file names.  The organisation takes advantage of the
fact that (in most cases) the inodes of the files will be in the same
compressed metadata block, and therefore, can share the start block.
Directories are therefore organised in a two level list, a directory
header containing the shared start block value, and a sequence of directory
entries, each of which share the shared start block.  A new directory header
is written once/if the inode start block changes.  The directory
header/directory entry list is repeated as many times as necessary.

Directories are sorted, and can contain a directory index to speed up
file lookup.  Directory indexes store one entry per metablock, each entry
storing the index/filename mapping to the first directory header
in each metadata block.  Directories are sorted in alphabetical order,
and at lookup the index is scanned linearly looking for the first filename
alphabetically larger than the filename being looked up.  At this point the
location of the metadata block the filename is in has been found.
The general idea of the index is to ensure only one metadata block needs to be
decompressed to do a lookup irrespective of the length of the directory.
This scheme has the advantage that it doesn't require extra memory overhead
and doesn't require much extra storage on disk.

File block list와 대형 파일 index cache

regular file은 연속된 압축 block sequence와 선택적 압축 fragment block(tail-end packed block)으로 구성된다. 각 data block의 압축 크기는 file inode 안의 block list에 저장된다.

256MB 이상 큰 file을 읽을 때 block index에서 on-disk data block 위치를 빨리 찾도록 index cache를 사용한다. 단순하고 공간 효율적인 on-disk block list를 유지하면서 최대 1.75TiB file을 처리한다.

cache는 slot으로 나뉘며 128KB block 기준 최대 224GiB file 여덟 개를 cache할 수 있다. 더 큰 file은 여러 slot을 쓰고 1.75TiB file 하나는 8 slot 전부를 사용한다. 기본 memory 사용량은 16KiB다.

3.4 File data
-------------

Regular files consist of a sequence of contiguous compressed blocks, and/or a
compressed fragment block (tail-end packed block).   The compressed size
of each datablock is stored in a block list contained within the
file inode.

To speed up access to datablocks when reading 'large' files (256 Mbytes or
larger), the code implements an index cache that caches the mapping from
block index to datablock location on disk.

The index cache allows Squashfs to handle large files (up to 1.75 TiB) while
retaining a simple and space-efficient block list on disk.  The cache
is split into slots, caching up to eight 224 GiB files (128 KiB blocks).
Larger files use multiple slots, with 1.75 TiB files using all 8 slots.
The index cache is designed to be memory efficient, and by default uses
16 KiB.

Fragment·uid/gid·export lookup

regular file의 fragment index는 fragment lookup table을 통해 on-disk 위치와 압축 크기로 변환된다. 이 table 자체가 metadata block으로 압축되고, 그 block들을 찾는 두 번째 index table이 있다. 작고 접근 빈도가 높으므로 두 번째 table은 mount 때 읽어 memory에 cache한다.

공간 절약을 위해 regular file은 uid·gid 실제 값 대신 index를 저장한다. id lookup table이 이를 32-bit uid/gid로 변환한다. 이 table도 압축 metadata block과 mount 때 cache되는 두 번째 index table 구조를 사용한다.

NFS 등으로 export하려면 filehandle의 inode number에서 on-disk inode 위치를 찾을 table이 선택적으로 필요하다. export code가 만료·flush된 inode를 재생성할 때 이 mapping을 사용한다. `mksquashfs -no-exports`로 비활성화할 수 있으며, 역시 압축 table과 memory-cached 2차 index로 구성된다.

3.5 Fragment lookup table
-------------------------

Regular files can contain a fragment index which is mapped to a fragment
location on disk and compressed size using a fragment lookup table.  This
fragment lookup table is itself stored compressed into metadata blocks.
A second index table is used to locate these.  This second index table for
speed of access (and because it is small) is read at mount time and cached
in memory.

3.6 Uid/gid lookup table
------------------------

For space efficiency regular files store uid and gid indexes, which are
converted to 32-bit uids/gids using an id look up table.  This table is
stored compressed into metadata blocks.  A second index table is used to
locate these.  This second index table for speed of access (and because it
is small) is read at mount time and cached in memory.

3.7 Export table
----------------

To enable Squashfs filesystems to be exportable (via NFS etc.) filesystems
can optionally (disabled with the -no-exports Mksquashfs option) contain
an inode number to inode disk location lookup table.  This is required to
enable Squashfs to map inode numbers passed in filehandles to the inode
location on disk, which is necessary when the export code reinstantiates
expired/flushed inodes.

This table is stored compressed into metadata blocks.  A second index table is
used to locate these.  This second index table for speed of access (and because
it is small) is read at mount time and cached in memory.

Xattr list와 out-of-line 값

xattr table은 inode별 extended attribute를 list로 저장한다. 각 entry는 type, name, value field를 가지며 type은 `user.`, `trusted.` 같은 prefix와 name·value 해석 방법을 encoding한다.

value는 inline이면 value field에 직접 들어가고, out-of-line이면 실제 값 위치의 reference가 들어간다. 큰 값을 별도로 두면 scan·lookup 성능이 좋아지고 동일 value를 한 번만 저장해 여러 occurrence가 같은 reference를 쓰는 de-duplication도 가능하다.

xattr list는 압축 8KB metadata block에 pack된다. inode마다 긴 on-disk 위치를 저장하는 대신 32-bit xattr id만 두고, 두 번째 xattr id lookup table이 list 위치로 mapping해 inode overhead를 줄인다.

3.8 Xattr table
---------------

The xattr table contains extended attributes for each inode.  The xattrs
for each inode are stored in a list, each list entry containing a type,
name and value field.  The type field encodes the xattr prefix
("user.", "trusted." etc) and it also encodes how the name/value fields
should be interpreted.  Currently the type indicates whether the value
is stored inline (in which case the value field contains the xattr value),
or if it is stored out of line (in which case the value field stores a
reference to where the actual value is stored).  This allows large values
to be stored out of line improving scanning and lookup performance and it
also allows values to be de-duplicated, the value being stored once, and
all other occurrences holding an out of line reference to that value.

The xattr lists are packed into compressed 8K metadata blocks.
To reduce overhead in inodes, rather than storing the on-disk
location of the xattr list inside each inode, a 32-bit xattr id
is stored.  This xattr id is mapped into the location of the xattr
list using a second xattr id lookup table.

ACL TODO와 내부 cache

남은 TODO는 ACL 지원 구현이다.

압축 block을 최근 접근 때마다 다시 decompress하지 않도록 Squashfs는 작은 metadata cache와 fragment cache 두 개를 사용한다. 일반 file data block은 이 내부 cache 대상이 아니며 평소처럼 decompress한 뒤 kernel page cache에 저장한다.

metadata와 fragment는 압축률을 위해 한 block에 여러 항목이 함께 pack된다. 특정 항목을 읽을 때 같이 나온 이웃 항목은 locality of reference로 곧 다시 쓰일 가능성이 있으므로 잠시 cache하면 추가 read와 decompress를 피할 수 있다.

향후 내부 cache를 kernel page cache 기반 구현으로 바꿀 수 있다. 다만 page cache는 page-size 단위라 locking과 관련 race condition이 더 복잡해질 수 있다.

4. TODOs and Outstanding Issues
-------------------------------

4.1 TODO list
-------------

Implement ACL support.

4.2 Squashfs Internal Cache
---------------------------

Blocks in Squashfs are compressed.  To avoid repeatedly decompressing
recently accessed data Squashfs uses two small metadata and fragment caches.

The cache is not used for file datablocks, these are decompressed and cached in
the page-cache in the normal way.  The cache is used to temporarily cache
fragment and metadata blocks which have been read as a result of a metadata
(i.e. inode or directory) or fragment access.  Because metadata and fragments
are packed together into blocks (to gain greater compression) the read of a
particular piece of metadata or fragment will retrieve other metadata/fragments
which have been packed with it, these because of locality-of-reference may be
read in the near future. Temporarily caching them ensures they are available
for near future access without requiring an additional read and decompress.

In the future this internal cache may be replaced with an implementation which
uses the kernel page cache.  Because the page cache operates on page sized
units this may introduce additional complexity in terms of locking and
associated race conditions.