linux/fs/erofs/decompressor.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0-only
   2/*
   3 * Copyright (C) 2019 HUAWEI, Inc.
   4 *             https://www.huawei.com/
   5 */
   6#include "compress.h"
   7#include <linux/module.h>
   8#include <linux/lz4.h>
   9
  10#ifndef LZ4_DISTANCE_MAX        /* history window size */
  11#define LZ4_DISTANCE_MAX 65535  /* set to maximum value by default */
  12#endif
  13
  14#define LZ4_MAX_DISTANCE_PAGES  (DIV_ROUND_UP(LZ4_DISTANCE_MAX, PAGE_SIZE) + 1)
  15#ifndef LZ4_DECOMPRESS_INPLACE_MARGIN
  16#define LZ4_DECOMPRESS_INPLACE_MARGIN(srcsize)  (((srcsize) >> 8) + 32)
  17#endif
  18
  19struct z_erofs_decompressor {
  20        /*
  21         * if destpages have sparsed pages, fill them with bounce pages.
  22         * it also check whether destpages indicate continuous physical memory.
  23         */
  24        int (*prepare_destpages)(struct z_erofs_decompress_req *rq,
  25                                 struct list_head *pagepool);
  26        int (*decompress)(struct z_erofs_decompress_req *rq, u8 *out);
  27        char *name;
  28};
  29
  30int z_erofs_load_lz4_config(struct super_block *sb,
  31                            struct erofs_super_block *dsb,
  32                            struct z_erofs_lz4_cfgs *lz4, int size)
  33{
  34        struct erofs_sb_info *sbi = EROFS_SB(sb);
  35        u16 distance;
  36
  37        if (lz4) {
  38                if (size < sizeof(struct z_erofs_lz4_cfgs)) {
  39                        erofs_err(sb, "invalid lz4 cfgs, size=%u", size);
  40                        return -EINVAL;
  41                }
  42                distance = le16_to_cpu(lz4->max_distance);
  43
  44                sbi->lz4.max_pclusterblks = le16_to_cpu(lz4->max_pclusterblks);
  45                if (!sbi->lz4.max_pclusterblks) {
  46                        sbi->lz4.max_pclusterblks = 1;  /* reserved case */
  47                } else if (sbi->lz4.max_pclusterblks >
  48                           Z_EROFS_PCLUSTER_MAX_SIZE / EROFS_BLKSIZ) {
  49                        erofs_err(sb, "too large lz4 pclusterblks %u",
  50                                  sbi->lz4.max_pclusterblks);
  51                        return -EINVAL;
  52                } else if (sbi->lz4.max_pclusterblks >= 2) {
  53                        erofs_info(sb, "EXPERIMENTAL big pcluster feature in use. Use at your own risk!");
  54                }
  55        } else {
  56                distance = le16_to_cpu(dsb->u1.lz4_max_distance);
  57                sbi->lz4.max_pclusterblks = 1;
  58        }
  59
  60        sbi->lz4.max_distance_pages = distance ?
  61                                        DIV_ROUND_UP(distance, PAGE_SIZE) + 1 :
  62                                        LZ4_MAX_DISTANCE_PAGES;
  63        return erofs_pcpubuf_growsize(sbi->lz4.max_pclusterblks);
  64}
  65
  66static int z_erofs_lz4_prepare_destpages(struct z_erofs_decompress_req *rq,
  67                                         struct list_head *pagepool)
  68{
  69        const unsigned int nr =
  70                PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT;
  71        struct page *availables[LZ4_MAX_DISTANCE_PAGES] = { NULL };
  72        unsigned long bounced[DIV_ROUND_UP(LZ4_MAX_DISTANCE_PAGES,
  73                                           BITS_PER_LONG)] = { 0 };
  74        unsigned int lz4_max_distance_pages =
  75                                EROFS_SB(rq->sb)->lz4.max_distance_pages;
  76        void *kaddr = NULL;
  77        unsigned int i, j, top;
  78
  79        top = 0;
  80        for (i = j = 0; i < nr; ++i, ++j) {
  81                struct page *const page = rq->out[i];
  82                struct page *victim;
  83
  84                if (j >= lz4_max_distance_pages)
  85                        j = 0;
  86
  87                /* 'valid' bounced can only be tested after a complete round */
  88                if (test_bit(j, bounced)) {
  89                        DBG_BUGON(i < lz4_max_distance_pages);
  90                        DBG_BUGON(top >= lz4_max_distance_pages);
  91                        availables[top++] = rq->out[i - lz4_max_distance_pages];
  92                }
  93
  94                if (page) {
  95                        __clear_bit(j, bounced);
  96                        if (kaddr) {
  97                                if (kaddr + PAGE_SIZE == page_address(page))
  98                                        kaddr += PAGE_SIZE;
  99                                else
 100                                        kaddr = NULL;
 101                        } else if (!i) {
 102                                kaddr = page_address(page);
 103                        }
 104                        continue;
 105                }
 106                kaddr = NULL;
 107                __set_bit(j, bounced);
 108
 109                if (top) {
 110                        victim = availables[--top];
 111                        get_page(victim);
 112                } else {
 113                        victim = erofs_allocpage(pagepool,
 114                                                 GFP_KERNEL | __GFP_NOFAIL);
 115                        set_page_private(victim, Z_EROFS_SHORTLIVED_PAGE);
 116                }
 117                rq->out[i] = victim;
 118        }
 119        return kaddr ? 1 : 0;
 120}
 121
 122static void *z_erofs_handle_inplace_io(struct z_erofs_decompress_req *rq,
 123                        void *inpage, unsigned int *inputmargin, int *maptype,
 124                        bool support_0padding)
 125{
 126        unsigned int nrpages_in, nrpages_out;
 127        unsigned int ofull, oend, inputsize, total, i, j;
 128        struct page **in;
 129        void *src, *tmp;
 130
 131        inputsize = rq->inputsize;
 132        nrpages_in = PAGE_ALIGN(inputsize) >> PAGE_SHIFT;
 133        oend = rq->pageofs_out + rq->outputsize;
 134        ofull = PAGE_ALIGN(oend);
 135        nrpages_out = ofull >> PAGE_SHIFT;
 136
 137        if (rq->inplace_io) {
 138                if (rq->partial_decoding || !support_0padding ||
 139                    ofull - oend < LZ4_DECOMPRESS_INPLACE_MARGIN(inputsize))
 140                        goto docopy;
 141
 142                for (i = 0; i < nrpages_in; ++i) {
 143                        DBG_BUGON(rq->in[i] == NULL);
 144                        for (j = 0; j < nrpages_out - nrpages_in + i; ++j)
 145                                if (rq->out[j] == rq->in[i])
 146                                        goto docopy;
 147                }
 148        }
 149
 150        if (nrpages_in <= 1) {
 151                *maptype = 0;
 152                return inpage;
 153        }
 154        kunmap_atomic(inpage);
 155        might_sleep();
 156        src = erofs_vm_map_ram(rq->in, nrpages_in);
 157        if (!src)
 158                return ERR_PTR(-ENOMEM);
 159        *maptype = 1;
 160        return src;
 161
 162docopy:
 163        /* Or copy compressed data which can be overlapped to per-CPU buffer */
 164        in = rq->in;
 165        src = erofs_get_pcpubuf(nrpages_in);
 166        if (!src) {
 167                DBG_BUGON(1);
 168                kunmap_atomic(inpage);
 169                return ERR_PTR(-EFAULT);
 170        }
 171
 172        tmp = src;
 173        total = rq->inputsize;
 174        while (total) {
 175                unsigned int page_copycnt =
 176                        min_t(unsigned int, total, PAGE_SIZE - *inputmargin);
 177
 178                if (!inpage)
 179                        inpage = kmap_atomic(*in);
 180                memcpy(tmp, inpage + *inputmargin, page_copycnt);
 181                kunmap_atomic(inpage);
 182                inpage = NULL;
 183                tmp += page_copycnt;
 184                total -= page_copycnt;
 185                ++in;
 186                *inputmargin = 0;
 187        }
 188        *maptype = 2;
 189        return src;
 190}
 191
 192static int z_erofs_lz4_decompress(struct z_erofs_decompress_req *rq, u8 *out)
 193{
 194        unsigned int inputmargin;
 195        u8 *headpage, *src;
 196        bool support_0padding;
 197        int ret, maptype;
 198
 199        DBG_BUGON(*rq->in == NULL);
 200        headpage = kmap_atomic(*rq->in);
 201        inputmargin = 0;
 202        support_0padding = false;
 203
 204        /* decompression inplace is only safe when 0padding is enabled */
 205        if (erofs_sb_has_lz4_0padding(EROFS_SB(rq->sb))) {
 206                support_0padding = true;
 207
 208                while (!headpage[inputmargin & ~PAGE_MASK])
 209                        if (!(++inputmargin & ~PAGE_MASK))
 210                                break;
 211
 212                if (inputmargin >= rq->inputsize) {
 213                        kunmap_atomic(headpage);
 214                        return -EIO;
 215                }
 216        }
 217
 218        rq->inputsize -= inputmargin;
 219        src = z_erofs_handle_inplace_io(rq, headpage, &inputmargin, &maptype,
 220                                        support_0padding);
 221        if (IS_ERR(src))
 222                return PTR_ERR(src);
 223
 224        /* legacy format could compress extra data in a pcluster. */
 225        if (rq->partial_decoding || !support_0padding)
 226                ret = LZ4_decompress_safe_partial(src + inputmargin, out,
 227                                rq->inputsize, rq->outputsize, rq->outputsize);
 228        else
 229                ret = LZ4_decompress_safe(src + inputmargin, out,
 230                                          rq->inputsize, rq->outputsize);
 231
 232        if (ret != rq->outputsize) {
 233                erofs_err(rq->sb, "failed to decompress %d in[%u, %u] out[%u]",
 234                          ret, rq->inputsize, inputmargin, rq->outputsize);
 235
 236                WARN_ON(1);
 237                print_hex_dump(KERN_DEBUG, "[ in]: ", DUMP_PREFIX_OFFSET,
 238                               16, 1, src + inputmargin, rq->inputsize, true);
 239                print_hex_dump(KERN_DEBUG, "[out]: ", DUMP_PREFIX_OFFSET,
 240                               16, 1, out, rq->outputsize, true);
 241
 242                if (ret >= 0)
 243                        memset(out + ret, 0, rq->outputsize - ret);
 244                ret = -EIO;
 245        }
 246
 247        if (maptype == 0) {
 248                kunmap_atomic(src);
 249        } else if (maptype == 1) {
 250                vm_unmap_ram(src, PAGE_ALIGN(rq->inputsize) >> PAGE_SHIFT);
 251        } else if (maptype == 2) {
 252                erofs_put_pcpubuf(src);
 253        } else {
 254                DBG_BUGON(1);
 255                return -EFAULT;
 256        }
 257        return ret;
 258}
 259
 260static struct z_erofs_decompressor decompressors[] = {
 261        [Z_EROFS_COMPRESSION_SHIFTED] = {
 262                .name = "shifted"
 263        },
 264        [Z_EROFS_COMPRESSION_LZ4] = {
 265                .prepare_destpages = z_erofs_lz4_prepare_destpages,
 266                .decompress = z_erofs_lz4_decompress,
 267                .name = "lz4"
 268        },
 269};
 270
 271static void copy_from_pcpubuf(struct page **out, const char *dst,
 272                              unsigned short pageofs_out,
 273                              unsigned int outputsize)
 274{
 275        const char *end = dst + outputsize;
 276        const unsigned int righthalf = PAGE_SIZE - pageofs_out;
 277        const char *cur = dst - pageofs_out;
 278
 279        while (cur < end) {
 280                struct page *const page = *out++;
 281
 282                if (page) {
 283                        char *buf = kmap_atomic(page);
 284
 285                        if (cur >= dst) {
 286                                memcpy(buf, cur, min_t(uint, PAGE_SIZE,
 287                                                       end - cur));
 288                        } else {
 289                                memcpy(buf + pageofs_out, cur + pageofs_out,
 290                                       min_t(uint, righthalf, end - cur));
 291                        }
 292                        kunmap_atomic(buf);
 293                }
 294                cur += PAGE_SIZE;
 295        }
 296}
 297
 298static int z_erofs_decompress_generic(struct z_erofs_decompress_req *rq,
 299                                      struct list_head *pagepool)
 300{
 301        const unsigned int nrpages_out =
 302                PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT;
 303        const struct z_erofs_decompressor *alg = decompressors + rq->alg;
 304        unsigned int dst_maptype;
 305        void *dst;
 306        int ret;
 307
 308        /* two optimized fast paths only for non bigpcluster cases yet */
 309        if (rq->inputsize <= PAGE_SIZE) {
 310                if (nrpages_out == 1 && !rq->inplace_io) {
 311                        DBG_BUGON(!*rq->out);
 312                        dst = kmap_atomic(*rq->out);
 313                        dst_maptype = 0;
 314                        goto dstmap_out;
 315                }
 316
 317                /*
 318                 * For the case of small output size (especially much less
 319                 * than PAGE_SIZE), memcpy the decompressed data rather than
 320                 * compressed data is preferred.
 321                 */
 322                if (rq->outputsize <= PAGE_SIZE * 7 / 8) {
 323                        dst = erofs_get_pcpubuf(1);
 324                        if (IS_ERR(dst))
 325                                return PTR_ERR(dst);
 326
 327                        rq->inplace_io = false;
 328                        ret = alg->decompress(rq, dst);
 329                        if (!ret)
 330                                copy_from_pcpubuf(rq->out, dst, rq->pageofs_out,
 331                                                  rq->outputsize);
 332
 333                        erofs_put_pcpubuf(dst);
 334                        return ret;
 335                }
 336        }
 337
 338        /* general decoding path which can be used for all cases */
 339        ret = alg->prepare_destpages(rq, pagepool);
 340        if (ret < 0)
 341                return ret;
 342        if (ret) {
 343                dst = page_address(*rq->out);
 344                dst_maptype = 1;
 345                goto dstmap_out;
 346        }
 347
 348        dst = erofs_vm_map_ram(rq->out, nrpages_out);
 349        if (!dst)
 350                return -ENOMEM;
 351        dst_maptype = 2;
 352
 353dstmap_out:
 354        ret = alg->decompress(rq, dst + rq->pageofs_out);
 355
 356        if (!dst_maptype)
 357                kunmap_atomic(dst);
 358        else if (dst_maptype == 2)
 359                vm_unmap_ram(dst, nrpages_out);
 360        return ret;
 361}
 362
 363static int z_erofs_shifted_transform(const struct z_erofs_decompress_req *rq,
 364                                     struct list_head *pagepool)
 365{
 366        const unsigned int nrpages_out =
 367                PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT;
 368        const unsigned int righthalf = PAGE_SIZE - rq->pageofs_out;
 369        unsigned char *src, *dst;
 370
 371        if (nrpages_out > 2) {
 372                DBG_BUGON(1);
 373                return -EIO;
 374        }
 375
 376        if (rq->out[0] == *rq->in) {
 377                DBG_BUGON(nrpages_out != 1);
 378                return 0;
 379        }
 380
 381        src = kmap_atomic(*rq->in);
 382        if (rq->out[0]) {
 383                dst = kmap_atomic(rq->out[0]);
 384                memcpy(dst + rq->pageofs_out, src, righthalf);
 385                kunmap_atomic(dst);
 386        }
 387
 388        if (nrpages_out == 2) {
 389                DBG_BUGON(!rq->out[1]);
 390                if (rq->out[1] == *rq->in) {
 391                        memmove(src, src + righthalf, rq->pageofs_out);
 392                } else {
 393                        dst = kmap_atomic(rq->out[1]);
 394                        memcpy(dst, src + righthalf, rq->pageofs_out);
 395                        kunmap_atomic(dst);
 396                }
 397        }
 398        kunmap_atomic(src);
 399        return 0;
 400}
 401
 402int z_erofs_decompress(struct z_erofs_decompress_req *rq,
 403                       struct list_head *pagepool)
 404{
 405        if (rq->alg == Z_EROFS_COMPRESSION_SHIFTED)
 406                return z_erofs_shifted_transform(rq, pagepool);
 407        return z_erofs_decompress_generic(rq, pagepool);
 408}
 409