147e4937aSGao Xiang // SPDX-License-Identifier: GPL-2.0-only 247e4937aSGao Xiang /* 347e4937aSGao Xiang * Copyright (C) 2019 HUAWEI, Inc. 4592e7cd0SAlexander A. Klimov * https://www.huawei.com/ 547e4937aSGao Xiang * Created by Gao Xiang <gaoxiang25@huawei.com> 647e4937aSGao Xiang */ 747e4937aSGao Xiang #include "compress.h" 847e4937aSGao Xiang #include <linux/module.h> 947e4937aSGao Xiang #include <linux/lz4.h> 1047e4937aSGao Xiang 1147e4937aSGao Xiang #ifndef LZ4_DISTANCE_MAX /* history window size */ 1247e4937aSGao Xiang #define LZ4_DISTANCE_MAX 65535 /* set to maximum value by default */ 1347e4937aSGao Xiang #endif 1447e4937aSGao Xiang 1547e4937aSGao Xiang #define LZ4_MAX_DISTANCE_PAGES (DIV_ROUND_UP(LZ4_DISTANCE_MAX, PAGE_SIZE) + 1) 1647e4937aSGao Xiang #ifndef LZ4_DECOMPRESS_INPLACE_MARGIN 1747e4937aSGao Xiang #define LZ4_DECOMPRESS_INPLACE_MARGIN(srcsize) (((srcsize) >> 8) + 32) 1847e4937aSGao Xiang #endif 1947e4937aSGao Xiang 2047e4937aSGao Xiang struct z_erofs_decompressor { 2147e4937aSGao Xiang /* 2247e4937aSGao Xiang * if destpages have sparsed pages, fill them with bounce pages. 2347e4937aSGao Xiang * it also check whether destpages indicate continuous physical memory. 2447e4937aSGao Xiang */ 2547e4937aSGao Xiang int (*prepare_destpages)(struct z_erofs_decompress_req *rq, 2647e4937aSGao Xiang struct list_head *pagepool); 2747e4937aSGao Xiang int (*decompress)(struct z_erofs_decompress_req *rq, u8 *out); 2847e4937aSGao Xiang char *name; 2947e4937aSGao Xiang }; 3047e4937aSGao Xiang 315d50538fSHuang Jianan int z_erofs_load_lz4_config(struct super_block *sb, 3246249cdeSGao Xiang struct erofs_super_block *dsb, 3346249cdeSGao Xiang struct z_erofs_lz4_cfgs *lz4, int size) 345d50538fSHuang Jianan { 35*4fea63f7SGao Xiang struct erofs_sb_info *sbi = EROFS_SB(sb); 3646249cdeSGao Xiang u16 distance; 3746249cdeSGao Xiang 3846249cdeSGao Xiang if (lz4) { 3946249cdeSGao Xiang if (size < sizeof(struct z_erofs_lz4_cfgs)) { 4046249cdeSGao Xiang erofs_err(sb, "invalid lz4 cfgs, size=%u", size); 4146249cdeSGao Xiang return -EINVAL; 4246249cdeSGao Xiang } 4346249cdeSGao Xiang distance = le16_to_cpu(lz4->max_distance); 44*4fea63f7SGao Xiang 45*4fea63f7SGao Xiang sbi->lz4.max_pclusterblks = le16_to_cpu(lz4->max_pclusterblks); 46*4fea63f7SGao Xiang if (!sbi->lz4.max_pclusterblks) { 47*4fea63f7SGao Xiang sbi->lz4.max_pclusterblks = 1; /* reserved case */ 48*4fea63f7SGao Xiang } else if (sbi->lz4.max_pclusterblks > 49*4fea63f7SGao Xiang Z_EROFS_PCLUSTER_MAX_SIZE / EROFS_BLKSIZ) { 50*4fea63f7SGao Xiang erofs_err(sb, "too large lz4 pclusterblks %u", 51*4fea63f7SGao Xiang sbi->lz4.max_pclusterblks); 52*4fea63f7SGao Xiang return -EINVAL; 53*4fea63f7SGao Xiang } else if (sbi->lz4.max_pclusterblks >= 2) { 54*4fea63f7SGao Xiang erofs_info(sb, "EXPERIMENTAL big pcluster feature in use. Use at your own risk!"); 55*4fea63f7SGao Xiang } 5646249cdeSGao Xiang } else { 5714373711SGao Xiang distance = le16_to_cpu(dsb->u1.lz4_max_distance); 58*4fea63f7SGao Xiang sbi->lz4.max_pclusterblks = 1; 5946249cdeSGao Xiang } 605d50538fSHuang Jianan 61*4fea63f7SGao Xiang sbi->lz4.max_distance_pages = distance ? 625d50538fSHuang Jianan DIV_ROUND_UP(distance, PAGE_SIZE) + 1 : 635d50538fSHuang Jianan LZ4_MAX_DISTANCE_PAGES; 64*4fea63f7SGao Xiang return erofs_pcpubuf_growsize(sbi->lz4.max_pclusterblks); 655d50538fSHuang Jianan } 665d50538fSHuang Jianan 6799634bf3SGao Xiang static int z_erofs_lz4_prepare_destpages(struct z_erofs_decompress_req *rq, 6847e4937aSGao Xiang struct list_head *pagepool) 6947e4937aSGao Xiang { 7047e4937aSGao Xiang const unsigned int nr = 7147e4937aSGao Xiang PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT; 7247e4937aSGao Xiang struct page *availables[LZ4_MAX_DISTANCE_PAGES] = { NULL }; 7347e4937aSGao Xiang unsigned long bounced[DIV_ROUND_UP(LZ4_MAX_DISTANCE_PAGES, 7447e4937aSGao Xiang BITS_PER_LONG)] = { 0 }; 755d50538fSHuang Jianan unsigned int lz4_max_distance_pages = 765d50538fSHuang Jianan EROFS_SB(rq->sb)->lz4.max_distance_pages; 7747e4937aSGao Xiang void *kaddr = NULL; 7847e4937aSGao Xiang unsigned int i, j, top; 7947e4937aSGao Xiang 8047e4937aSGao Xiang top = 0; 8147e4937aSGao Xiang for (i = j = 0; i < nr; ++i, ++j) { 8247e4937aSGao Xiang struct page *const page = rq->out[i]; 8347e4937aSGao Xiang struct page *victim; 8447e4937aSGao Xiang 855d50538fSHuang Jianan if (j >= lz4_max_distance_pages) 8647e4937aSGao Xiang j = 0; 8747e4937aSGao Xiang 8847e4937aSGao Xiang /* 'valid' bounced can only be tested after a complete round */ 8947e4937aSGao Xiang if (test_bit(j, bounced)) { 905d50538fSHuang Jianan DBG_BUGON(i < lz4_max_distance_pages); 915d50538fSHuang Jianan DBG_BUGON(top >= lz4_max_distance_pages); 925d50538fSHuang Jianan availables[top++] = rq->out[i - lz4_max_distance_pages]; 9347e4937aSGao Xiang } 9447e4937aSGao Xiang 9547e4937aSGao Xiang if (page) { 9647e4937aSGao Xiang __clear_bit(j, bounced); 9747e4937aSGao Xiang if (kaddr) { 9847e4937aSGao Xiang if (kaddr + PAGE_SIZE == page_address(page)) 9947e4937aSGao Xiang kaddr += PAGE_SIZE; 10047e4937aSGao Xiang else 10147e4937aSGao Xiang kaddr = NULL; 10247e4937aSGao Xiang } else if (!i) { 10347e4937aSGao Xiang kaddr = page_address(page); 10447e4937aSGao Xiang } 10547e4937aSGao Xiang continue; 10647e4937aSGao Xiang } 10747e4937aSGao Xiang kaddr = NULL; 10847e4937aSGao Xiang __set_bit(j, bounced); 10947e4937aSGao Xiang 11047e4937aSGao Xiang if (top) { 11147e4937aSGao Xiang victim = availables[--top]; 11247e4937aSGao Xiang get_page(victim); 11347e4937aSGao Xiang } else { 114b4892fa3SHuang Jianan victim = erofs_allocpage(pagepool, 115b4892fa3SHuang Jianan GFP_KERNEL | __GFP_NOFAIL); 1166aaa7b06SGao Xiang set_page_private(victim, Z_EROFS_SHORTLIVED_PAGE); 11747e4937aSGao Xiang } 11847e4937aSGao Xiang rq->out[i] = victim; 11947e4937aSGao Xiang } 12047e4937aSGao Xiang return kaddr ? 1 : 0; 12147e4937aSGao Xiang } 12247e4937aSGao Xiang 12347e4937aSGao Xiang static void *generic_copy_inplace_data(struct z_erofs_decompress_req *rq, 12447e4937aSGao Xiang u8 *src, unsigned int pageofs_in) 12547e4937aSGao Xiang { 12647e4937aSGao Xiang /* 12747e4937aSGao Xiang * if in-place decompression is ongoing, those decompressed 12847e4937aSGao Xiang * pages should be copied in order to avoid being overlapped. 12947e4937aSGao Xiang */ 13047e4937aSGao Xiang struct page **in = rq->in; 13152488734SGao Xiang u8 *const tmp = erofs_get_pcpubuf(1); 13247e4937aSGao Xiang u8 *tmpp = tmp; 13347e4937aSGao Xiang unsigned int inlen = rq->inputsize - pageofs_in; 13447e4937aSGao Xiang unsigned int count = min_t(uint, inlen, PAGE_SIZE - pageofs_in); 13547e4937aSGao Xiang 13647e4937aSGao Xiang while (tmpp < tmp + inlen) { 13747e4937aSGao Xiang if (!src) 13847e4937aSGao Xiang src = kmap_atomic(*in); 13947e4937aSGao Xiang memcpy(tmpp, src + pageofs_in, count); 14047e4937aSGao Xiang kunmap_atomic(src); 14147e4937aSGao Xiang src = NULL; 14247e4937aSGao Xiang tmpp += count; 14347e4937aSGao Xiang pageofs_in = 0; 14447e4937aSGao Xiang count = PAGE_SIZE; 14547e4937aSGao Xiang ++in; 14647e4937aSGao Xiang } 14747e4937aSGao Xiang return tmp; 14847e4937aSGao Xiang } 14947e4937aSGao Xiang 15099634bf3SGao Xiang static int z_erofs_lz4_decompress(struct z_erofs_decompress_req *rq, u8 *out) 15147e4937aSGao Xiang { 15247e4937aSGao Xiang unsigned int inputmargin, inlen; 15347e4937aSGao Xiang u8 *src; 15447e4937aSGao Xiang bool copied, support_0padding; 15547e4937aSGao Xiang int ret; 15647e4937aSGao Xiang 15747e4937aSGao Xiang if (rq->inputsize > PAGE_SIZE) 15847e4937aSGao Xiang return -EOPNOTSUPP; 15947e4937aSGao Xiang 16047e4937aSGao Xiang src = kmap_atomic(*rq->in); 16147e4937aSGao Xiang inputmargin = 0; 16247e4937aSGao Xiang support_0padding = false; 16347e4937aSGao Xiang 16447e4937aSGao Xiang /* decompression inplace is only safe when 0padding is enabled */ 165de06a6a3SGao Xiang if (erofs_sb_has_lz4_0padding(EROFS_SB(rq->sb))) { 16647e4937aSGao Xiang support_0padding = true; 16747e4937aSGao Xiang 16847e4937aSGao Xiang while (!src[inputmargin & ~PAGE_MASK]) 16947e4937aSGao Xiang if (!(++inputmargin & ~PAGE_MASK)) 17047e4937aSGao Xiang break; 17147e4937aSGao Xiang 17247e4937aSGao Xiang if (inputmargin >= rq->inputsize) { 17347e4937aSGao Xiang kunmap_atomic(src); 17447e4937aSGao Xiang return -EIO; 17547e4937aSGao Xiang } 17647e4937aSGao Xiang } 17747e4937aSGao Xiang 17847e4937aSGao Xiang copied = false; 17947e4937aSGao Xiang inlen = rq->inputsize - inputmargin; 18047e4937aSGao Xiang if (rq->inplace_io) { 18147e4937aSGao Xiang const uint oend = (rq->pageofs_out + 18247e4937aSGao Xiang rq->outputsize) & ~PAGE_MASK; 18347e4937aSGao Xiang const uint nr = PAGE_ALIGN(rq->pageofs_out + 18447e4937aSGao Xiang rq->outputsize) >> PAGE_SHIFT; 18547e4937aSGao Xiang 18647e4937aSGao Xiang if (rq->partial_decoding || !support_0padding || 18747e4937aSGao Xiang rq->out[nr - 1] != rq->in[0] || 18847e4937aSGao Xiang rq->inputsize - oend < 18947e4937aSGao Xiang LZ4_DECOMPRESS_INPLACE_MARGIN(inlen)) { 19047e4937aSGao Xiang src = generic_copy_inplace_data(rq, src, inputmargin); 19147e4937aSGao Xiang inputmargin = 0; 19247e4937aSGao Xiang copied = true; 19347e4937aSGao Xiang } 19447e4937aSGao Xiang } 19547e4937aSGao Xiang 196af1038abSGao Xiang /* legacy format could compress extra data in a pcluster. */ 197af1038abSGao Xiang if (rq->partial_decoding || !support_0padding) 19847e4937aSGao Xiang ret = LZ4_decompress_safe_partial(src + inputmargin, out, 19947e4937aSGao Xiang inlen, rq->outputsize, 20047e4937aSGao Xiang rq->outputsize); 201af1038abSGao Xiang else 202af1038abSGao Xiang ret = LZ4_decompress_safe(src + inputmargin, out, 203af1038abSGao Xiang inlen, rq->outputsize); 204af1038abSGao Xiang 205aa99a76bSGao Xiang if (ret != rq->outputsize) { 206aa99a76bSGao Xiang erofs_err(rq->sb, "failed to decompress %d in[%u, %u] out[%u]", 207aa99a76bSGao Xiang ret, inlen, inputmargin, rq->outputsize); 208aa99a76bSGao Xiang 20947e4937aSGao Xiang WARN_ON(1); 21047e4937aSGao Xiang print_hex_dump(KERN_DEBUG, "[ in]: ", DUMP_PREFIX_OFFSET, 21147e4937aSGao Xiang 16, 1, src + inputmargin, inlen, true); 21247e4937aSGao Xiang print_hex_dump(KERN_DEBUG, "[out]: ", DUMP_PREFIX_OFFSET, 21347e4937aSGao Xiang 16, 1, out, rq->outputsize, true); 214aa99a76bSGao Xiang 215aa99a76bSGao Xiang if (ret >= 0) 216aa99a76bSGao Xiang memset(out + ret, 0, rq->outputsize - ret); 21747e4937aSGao Xiang ret = -EIO; 21847e4937aSGao Xiang } 21947e4937aSGao Xiang 22047e4937aSGao Xiang if (copied) 22147e4937aSGao Xiang erofs_put_pcpubuf(src); 22247e4937aSGao Xiang else 22347e4937aSGao Xiang kunmap_atomic(src); 22447e4937aSGao Xiang return ret; 22547e4937aSGao Xiang } 22647e4937aSGao Xiang 22747e4937aSGao Xiang static struct z_erofs_decompressor decompressors[] = { 22847e4937aSGao Xiang [Z_EROFS_COMPRESSION_SHIFTED] = { 22947e4937aSGao Xiang .name = "shifted" 23047e4937aSGao Xiang }, 23147e4937aSGao Xiang [Z_EROFS_COMPRESSION_LZ4] = { 23299634bf3SGao Xiang .prepare_destpages = z_erofs_lz4_prepare_destpages, 23399634bf3SGao Xiang .decompress = z_erofs_lz4_decompress, 23447e4937aSGao Xiang .name = "lz4" 23547e4937aSGao Xiang }, 23647e4937aSGao Xiang }; 23747e4937aSGao Xiang 23847e4937aSGao Xiang static void copy_from_pcpubuf(struct page **out, const char *dst, 23947e4937aSGao Xiang unsigned short pageofs_out, 24047e4937aSGao Xiang unsigned int outputsize) 24147e4937aSGao Xiang { 24247e4937aSGao Xiang const char *end = dst + outputsize; 24347e4937aSGao Xiang const unsigned int righthalf = PAGE_SIZE - pageofs_out; 24447e4937aSGao Xiang const char *cur = dst - pageofs_out; 24547e4937aSGao Xiang 24647e4937aSGao Xiang while (cur < end) { 24747e4937aSGao Xiang struct page *const page = *out++; 24847e4937aSGao Xiang 24947e4937aSGao Xiang if (page) { 25047e4937aSGao Xiang char *buf = kmap_atomic(page); 25147e4937aSGao Xiang 25247e4937aSGao Xiang if (cur >= dst) { 25347e4937aSGao Xiang memcpy(buf, cur, min_t(uint, PAGE_SIZE, 25447e4937aSGao Xiang end - cur)); 25547e4937aSGao Xiang } else { 25647e4937aSGao Xiang memcpy(buf + pageofs_out, cur + pageofs_out, 25747e4937aSGao Xiang min_t(uint, righthalf, end - cur)); 25847e4937aSGao Xiang } 25947e4937aSGao Xiang kunmap_atomic(buf); 26047e4937aSGao Xiang } 26147e4937aSGao Xiang cur += PAGE_SIZE; 26247e4937aSGao Xiang } 26347e4937aSGao Xiang } 26447e4937aSGao Xiang 26599634bf3SGao Xiang static int z_erofs_decompress_generic(struct z_erofs_decompress_req *rq, 26647e4937aSGao Xiang struct list_head *pagepool) 26747e4937aSGao Xiang { 26847e4937aSGao Xiang const unsigned int nrpages_out = 26947e4937aSGao Xiang PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT; 27047e4937aSGao Xiang const struct z_erofs_decompressor *alg = decompressors + rq->alg; 27147e4937aSGao Xiang unsigned int dst_maptype; 27247e4937aSGao Xiang void *dst; 27373d03931SGao Xiang int ret, i; 27447e4937aSGao Xiang 27547e4937aSGao Xiang if (nrpages_out == 1 && !rq->inplace_io) { 27647e4937aSGao Xiang DBG_BUGON(!*rq->out); 27747e4937aSGao Xiang dst = kmap_atomic(*rq->out); 27847e4937aSGao Xiang dst_maptype = 0; 27947e4937aSGao Xiang goto dstmap_out; 28047e4937aSGao Xiang } 28147e4937aSGao Xiang 28247e4937aSGao Xiang /* 28347e4937aSGao Xiang * For the case of small output size (especially much less 28447e4937aSGao Xiang * than PAGE_SIZE), memcpy the decompressed data rather than 28547e4937aSGao Xiang * compressed data is preferred. 28647e4937aSGao Xiang */ 28747e4937aSGao Xiang if (rq->outputsize <= PAGE_SIZE * 7 / 8) { 28852488734SGao Xiang dst = erofs_get_pcpubuf(1); 28947e4937aSGao Xiang if (IS_ERR(dst)) 29047e4937aSGao Xiang return PTR_ERR(dst); 29147e4937aSGao Xiang 29247e4937aSGao Xiang rq->inplace_io = false; 29347e4937aSGao Xiang ret = alg->decompress(rq, dst); 29447e4937aSGao Xiang if (!ret) 29547e4937aSGao Xiang copy_from_pcpubuf(rq->out, dst, rq->pageofs_out, 29647e4937aSGao Xiang rq->outputsize); 29747e4937aSGao Xiang 29847e4937aSGao Xiang erofs_put_pcpubuf(dst); 29947e4937aSGao Xiang return ret; 30047e4937aSGao Xiang } 30147e4937aSGao Xiang 30247e4937aSGao Xiang ret = alg->prepare_destpages(rq, pagepool); 30347e4937aSGao Xiang if (ret < 0) { 30447e4937aSGao Xiang return ret; 30547e4937aSGao Xiang } else if (ret) { 30647e4937aSGao Xiang dst = page_address(*rq->out); 30747e4937aSGao Xiang dst_maptype = 1; 30847e4937aSGao Xiang goto dstmap_out; 30947e4937aSGao Xiang } 31047e4937aSGao Xiang 31173d03931SGao Xiang i = 0; 31273d03931SGao Xiang while (1) { 313d4efd79aSChristoph Hellwig dst = vm_map_ram(rq->out, nrpages_out, -1); 31473d03931SGao Xiang 31573d03931SGao Xiang /* retry two more times (totally 3 times) */ 31673d03931SGao Xiang if (dst || ++i >= 3) 31773d03931SGao Xiang break; 31873d03931SGao Xiang vm_unmap_aliases(); 31973d03931SGao Xiang } 32073d03931SGao Xiang 32147e4937aSGao Xiang if (!dst) 32247e4937aSGao Xiang return -ENOMEM; 32373d03931SGao Xiang 32447e4937aSGao Xiang dst_maptype = 2; 32547e4937aSGao Xiang 32647e4937aSGao Xiang dstmap_out: 32747e4937aSGao Xiang ret = alg->decompress(rq, dst + rq->pageofs_out); 32847e4937aSGao Xiang 32947e4937aSGao Xiang if (!dst_maptype) 33047e4937aSGao Xiang kunmap_atomic(dst); 33147e4937aSGao Xiang else if (dst_maptype == 2) 33273d03931SGao Xiang vm_unmap_ram(dst, nrpages_out); 33347e4937aSGao Xiang return ret; 33447e4937aSGao Xiang } 33547e4937aSGao Xiang 33699634bf3SGao Xiang static int z_erofs_shifted_transform(const struct z_erofs_decompress_req *rq, 33747e4937aSGao Xiang struct list_head *pagepool) 33847e4937aSGao Xiang { 33947e4937aSGao Xiang const unsigned int nrpages_out = 34047e4937aSGao Xiang PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT; 34147e4937aSGao Xiang const unsigned int righthalf = PAGE_SIZE - rq->pageofs_out; 34247e4937aSGao Xiang unsigned char *src, *dst; 34347e4937aSGao Xiang 34447e4937aSGao Xiang if (nrpages_out > 2) { 34547e4937aSGao Xiang DBG_BUGON(1); 34647e4937aSGao Xiang return -EIO; 34747e4937aSGao Xiang } 34847e4937aSGao Xiang 34947e4937aSGao Xiang if (rq->out[0] == *rq->in) { 35047e4937aSGao Xiang DBG_BUGON(nrpages_out != 1); 35147e4937aSGao Xiang return 0; 35247e4937aSGao Xiang } 35347e4937aSGao Xiang 35447e4937aSGao Xiang src = kmap_atomic(*rq->in); 3554d202437SGao Xiang if (rq->out[0]) { 35647e4937aSGao Xiang dst = kmap_atomic(rq->out[0]); 35747e4937aSGao Xiang memcpy(dst + rq->pageofs_out, src, righthalf); 3584d202437SGao Xiang kunmap_atomic(dst); 35947e4937aSGao Xiang } 36047e4937aSGao Xiang 3614d202437SGao Xiang if (nrpages_out == 2) { 3624d202437SGao Xiang DBG_BUGON(!rq->out[1]); 36347e4937aSGao Xiang if (rq->out[1] == *rq->in) { 36447e4937aSGao Xiang memmove(src, src + righthalf, rq->pageofs_out); 3654d202437SGao Xiang } else { 36647e4937aSGao Xiang dst = kmap_atomic(rq->out[1]); 36747e4937aSGao Xiang memcpy(dst, src + righthalf, rq->pageofs_out); 36847e4937aSGao Xiang kunmap_atomic(dst); 3694d202437SGao Xiang } 3704d202437SGao Xiang } 37147e4937aSGao Xiang kunmap_atomic(src); 37247e4937aSGao Xiang return 0; 37347e4937aSGao Xiang } 37447e4937aSGao Xiang 37547e4937aSGao Xiang int z_erofs_decompress(struct z_erofs_decompress_req *rq, 37647e4937aSGao Xiang struct list_head *pagepool) 37747e4937aSGao Xiang { 37847e4937aSGao Xiang if (rq->alg == Z_EROFS_COMPRESSION_SHIFTED) 37999634bf3SGao Xiang return z_erofs_shifted_transform(rq, pagepool); 38099634bf3SGao Xiang return z_erofs_decompress_generic(rq, pagepool); 38147e4937aSGao Xiang } 38247e4937aSGao Xiang 383