• Gao Xiang's avatar
    staging: erofs: introduce VLE decompression support · 3883a79a
    Gao Xiang authored
    This patch introduces the basic in-place VLE decompression
    implementation for the erofs file system.
    
    Compared with fixed-sized input compression, it implements
    what we call 'the variable-length extent compression' which
    specifies the same output size for each compression block
    to make the full use of IO bandwidth (which means almost
    all data from block device can be directly used for decomp-
    ression), improve the real (rather than just via data caching,
    which costs more memory) random read and keep the relatively
    lower compression ratios (it saves more storage space than
    fixed-sized input compression which is also configured with
    the same input block size), as illustrated below:
    
            |---  variable-length extent ---|------ VLE ------|---  VLE ---|
             /> clusterofs                  /> clusterofs     /> clusterofs /> clusterofs
       ++---|-------++-----------++---------|-++-----------++-|---------++-|
    ...||   |       ||           ||         | ||           || |         || | ... original data
       ++---|-------++-----------++---------|-++-----------++-|---------++-|
       ++->cluster<-++->cluster<-++->cluster<-++->cluster<-++->cluster<-++
            size         size         size         size         size
             \                             /                 /            /
              \                      /              /            /
               \               /            /            /
                ++-----------++-----------++-----------++
            ... ||           ||           ||           || ... compressed clusters
                ++-----------++-----------++-----------++
                ++->cluster<-++->cluster<-++->cluster<-++
                     size         size         size
    
    The main point of 'in-place' refers to the decompression mode:
    Instead of allocating independent compressed pages and data
    structures, it reuses the allocated file cache pages at most
    to store its compressed data and the corresponding pagevec in
    a time-sharing approach by default, which will be useful for
    low memory scenario.
    
    In the end, unlike the other filesystems with (de)compression
    support using a relatively large compression block size, which
    reads and decompresses >= 128KB at once, and gains a more
    good-looking random read (In fact it collects small random reads
    into large sequential reads and caches all decompressed data
    in memory, but it is unacceptable especially for embedded devices
    with limited memory, and it is not the real random read), we
    select a universal small-sized 4KB compressed cluster, which is
    the smallest page size for most architectures, and all compressed
    clusters can be read and decompressed independently, which ensures
    random read number for all use cases.
    Signed-off-by: default avatarGao Xiang <gaoxiang25@huawei.com>
    Signed-off-by: default avatarGreg Kroah-Hartman <gregkh@linuxfoundation.org>
    3883a79a
internal.h 13.5 KB