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 19 struct z_erofs_lz4_decompress_ctx { 20 struct z_erofs_decompress_req *rq; 21 /* # of encoded, decoded pages */ 22 unsigned int inpages, outpages; 23 /* decoded block total length (used for in-place decompression) */ 24 unsigned int oend; 25 }; 26 27 int z_erofs_load_lz4_config(struct super_block *sb, 28 struct erofs_super_block *dsb, 29 struct z_erofs_lz4_cfgs *lz4, int size) 30 { 31 struct erofs_sb_info *sbi = EROFS_SB(sb); 32 u16 distance; 33 34 if (lz4) { 35 if (size < sizeof(struct z_erofs_lz4_cfgs)) { 36 erofs_err(sb, "invalid lz4 cfgs, size=%u", size); 37 return -EINVAL; 38 } 39 distance = le16_to_cpu(lz4->max_distance); 40 41 sbi->lz4.max_pclusterblks = le16_to_cpu(lz4->max_pclusterblks); 42 if (!sbi->lz4.max_pclusterblks) { 43 sbi->lz4.max_pclusterblks = 1; /* reserved case */ 44 } else if (sbi->lz4.max_pclusterblks > 45 Z_EROFS_PCLUSTER_MAX_SIZE / EROFS_BLKSIZ) { 46 erofs_err(sb, "too large lz4 pclusterblks %u", 47 sbi->lz4.max_pclusterblks); 48 return -EINVAL; 49 } else if (sbi->lz4.max_pclusterblks >= 2) { 50 erofs_info(sb, "EXPERIMENTAL big pcluster feature in use. Use at your own risk!"); 51 } 52 } else { 53 distance = le16_to_cpu(dsb->u1.lz4_max_distance); 54 sbi->lz4.max_pclusterblks = 1; 55 } 56 57 sbi->lz4.max_distance_pages = distance ? 58 DIV_ROUND_UP(distance, PAGE_SIZE) + 1 : 59 LZ4_MAX_DISTANCE_PAGES; 60 return erofs_pcpubuf_growsize(sbi->lz4.max_pclusterblks); 61 } 62 63 /* 64 * Fill all gaps with bounce pages if it's a sparse page list. Also check if 65 * all physical pages are consecutive, which can be seen for moderate CR. 66 */ 67 static int z_erofs_lz4_prepare_dstpages(struct z_erofs_lz4_decompress_ctx *ctx, 68 struct page **pagepool) 69 { 70 struct z_erofs_decompress_req *rq = ctx->rq; 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 < ctx->outpages; ++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 122 static void *z_erofs_lz4_handle_overlap(struct z_erofs_lz4_decompress_ctx *ctx, 123 void *inpage, unsigned int *inputmargin, int *maptype, 124 bool support_0padding) 125 { 126 struct z_erofs_decompress_req *rq = ctx->rq; 127 unsigned int omargin, total, i, j; 128 struct page **in; 129 void *src, *tmp; 130 131 if (rq->inplace_io) { 132 omargin = PAGE_ALIGN(ctx->oend) - ctx->oend; 133 if (rq->partial_decoding || !support_0padding || 134 omargin < LZ4_DECOMPRESS_INPLACE_MARGIN(rq->inputsize)) 135 goto docopy; 136 137 for (i = 0; i < ctx->inpages; ++i) { 138 DBG_BUGON(rq->in[i] == NULL); 139 for (j = 0; j < ctx->outpages - ctx->inpages + i; ++j) 140 if (rq->out[j] == rq->in[i]) 141 goto docopy; 142 } 143 } 144 145 if (ctx->inpages <= 1) { 146 *maptype = 0; 147 return inpage; 148 } 149 kunmap_atomic(inpage); 150 might_sleep(); 151 src = erofs_vm_map_ram(rq->in, ctx->inpages); 152 if (!src) 153 return ERR_PTR(-ENOMEM); 154 *maptype = 1; 155 return src; 156 157 docopy: 158 /* Or copy compressed data which can be overlapped to per-CPU buffer */ 159 in = rq->in; 160 src = erofs_get_pcpubuf(ctx->inpages); 161 if (!src) { 162 DBG_BUGON(1); 163 kunmap_atomic(inpage); 164 return ERR_PTR(-EFAULT); 165 } 166 167 tmp = src; 168 total = rq->inputsize; 169 while (total) { 170 unsigned int page_copycnt = 171 min_t(unsigned int, total, PAGE_SIZE - *inputmargin); 172 173 if (!inpage) 174 inpage = kmap_atomic(*in); 175 memcpy(tmp, inpage + *inputmargin, page_copycnt); 176 kunmap_atomic(inpage); 177 inpage = NULL; 178 tmp += page_copycnt; 179 total -= page_copycnt; 180 ++in; 181 *inputmargin = 0; 182 } 183 *maptype = 2; 184 return src; 185 } 186 187 static int z_erofs_lz4_decompress_mem(struct z_erofs_lz4_decompress_ctx *ctx, 188 u8 *out) 189 { 190 struct z_erofs_decompress_req *rq = ctx->rq; 191 unsigned int inputmargin; 192 u8 *headpage, *src; 193 bool support_0padding; 194 int ret, maptype; 195 196 DBG_BUGON(*rq->in == NULL); 197 headpage = kmap_atomic(*rq->in); 198 inputmargin = 0; 199 support_0padding = false; 200 201 /* decompression inplace is only safe when zero_padding is enabled */ 202 if (erofs_sb_has_zero_padding(EROFS_SB(rq->sb))) { 203 support_0padding = true; 204 205 while (!headpage[inputmargin & ~PAGE_MASK]) 206 if (!(++inputmargin & ~PAGE_MASK)) 207 break; 208 209 if (inputmargin >= rq->inputsize) { 210 kunmap_atomic(headpage); 211 return -EIO; 212 } 213 } 214 215 rq->inputsize -= inputmargin; 216 src = z_erofs_lz4_handle_overlap(ctx, headpage, &inputmargin, 217 &maptype, support_0padding); 218 if (IS_ERR(src)) 219 return PTR_ERR(src); 220 221 /* legacy format could compress extra data in a pcluster. */ 222 if (rq->partial_decoding || !support_0padding) 223 ret = LZ4_decompress_safe_partial(src + inputmargin, out, 224 rq->inputsize, rq->outputsize, rq->outputsize); 225 else 226 ret = LZ4_decompress_safe(src + inputmargin, out, 227 rq->inputsize, rq->outputsize); 228 229 if (ret != rq->outputsize) { 230 erofs_err(rq->sb, "failed to decompress %d in[%u, %u] out[%u]", 231 ret, rq->inputsize, inputmargin, rq->outputsize); 232 233 print_hex_dump(KERN_DEBUG, "[ in]: ", DUMP_PREFIX_OFFSET, 234 16, 1, src + inputmargin, rq->inputsize, true); 235 print_hex_dump(KERN_DEBUG, "[out]: ", DUMP_PREFIX_OFFSET, 236 16, 1, out, rq->outputsize, true); 237 238 if (ret >= 0) 239 memset(out + ret, 0, rq->outputsize - ret); 240 ret = -EIO; 241 } else { 242 ret = 0; 243 } 244 245 if (maptype == 0) { 246 kunmap_atomic(headpage); 247 } else if (maptype == 1) { 248 vm_unmap_ram(src, ctx->inpages); 249 } else if (maptype == 2) { 250 erofs_put_pcpubuf(src); 251 } else { 252 DBG_BUGON(1); 253 return -EFAULT; 254 } 255 return ret; 256 } 257 258 static int z_erofs_lz4_decompress(struct z_erofs_decompress_req *rq, 259 struct page **pagepool) 260 { 261 struct z_erofs_lz4_decompress_ctx ctx; 262 unsigned int dst_maptype; 263 void *dst; 264 int ret; 265 266 ctx.rq = rq; 267 ctx.oend = rq->pageofs_out + rq->outputsize; 268 ctx.outpages = PAGE_ALIGN(ctx.oend) >> PAGE_SHIFT; 269 ctx.inpages = PAGE_ALIGN(rq->inputsize) >> PAGE_SHIFT; 270 271 /* one optimized fast path only for non bigpcluster cases yet */ 272 if (ctx.inpages == 1 && ctx.outpages == 1 && !rq->inplace_io) { 273 DBG_BUGON(!*rq->out); 274 dst = kmap_atomic(*rq->out); 275 dst_maptype = 0; 276 goto dstmap_out; 277 } 278 279 /* general decoding path which can be used for all cases */ 280 ret = z_erofs_lz4_prepare_dstpages(&ctx, pagepool); 281 if (ret < 0) { 282 return ret; 283 } else if (ret > 0) { 284 dst = page_address(*rq->out); 285 dst_maptype = 1; 286 } else { 287 dst = erofs_vm_map_ram(rq->out, ctx.outpages); 288 if (!dst) 289 return -ENOMEM; 290 dst_maptype = 2; 291 } 292 293 dstmap_out: 294 ret = z_erofs_lz4_decompress_mem(&ctx, dst + rq->pageofs_out); 295 if (!dst_maptype) 296 kunmap_atomic(dst); 297 else if (dst_maptype == 2) 298 vm_unmap_ram(dst, ctx.outpages); 299 return ret; 300 } 301 302 static int z_erofs_shifted_transform(struct z_erofs_decompress_req *rq, 303 struct page **pagepool) 304 { 305 const unsigned int nrpages_out = 306 PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT; 307 const unsigned int righthalf = PAGE_SIZE - rq->pageofs_out; 308 unsigned char *src, *dst; 309 310 if (nrpages_out > 2) { 311 DBG_BUGON(1); 312 return -EIO; 313 } 314 315 if (rq->out[0] == *rq->in) { 316 DBG_BUGON(nrpages_out != 1); 317 return 0; 318 } 319 320 src = kmap_atomic(*rq->in); 321 if (rq->out[0]) { 322 dst = kmap_atomic(rq->out[0]); 323 memcpy(dst + rq->pageofs_out, src, righthalf); 324 kunmap_atomic(dst); 325 } 326 327 if (nrpages_out == 2) { 328 DBG_BUGON(!rq->out[1]); 329 if (rq->out[1] == *rq->in) { 330 memmove(src, src + righthalf, rq->pageofs_out); 331 } else { 332 dst = kmap_atomic(rq->out[1]); 333 memcpy(dst, src + righthalf, rq->pageofs_out); 334 kunmap_atomic(dst); 335 } 336 } 337 kunmap_atomic(src); 338 return 0; 339 } 340 341 static struct z_erofs_decompressor decompressors[] = { 342 [Z_EROFS_COMPRESSION_SHIFTED] = { 343 .decompress = z_erofs_shifted_transform, 344 .name = "shifted" 345 }, 346 [Z_EROFS_COMPRESSION_LZ4] = { 347 .decompress = z_erofs_lz4_decompress, 348 .name = "lz4" 349 }, 350 #ifdef CONFIG_EROFS_FS_ZIP_LZMA 351 [Z_EROFS_COMPRESSION_LZMA] = { 352 .decompress = z_erofs_lzma_decompress, 353 .name = "lzma" 354 }, 355 #endif 356 }; 357 358 int z_erofs_decompress(struct z_erofs_decompress_req *rq, 359 struct page **pagepool) 360 { 361 return decompressors[rq->alg].decompress(rq, pagepool); 362 } 363