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_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 30 int 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 66 static 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 (!PageHighMem(page)) { 97 if (!i) { 98 kaddr = page_address(page); 99 continue; 100 } 101 if (kaddr && 102 kaddr + PAGE_SIZE == page_address(page)) { 103 kaddr += PAGE_SIZE; 104 continue; 105 } 106 } 107 kaddr = NULL; 108 continue; 109 } 110 kaddr = NULL; 111 __set_bit(j, bounced); 112 113 if (top) { 114 victim = availables[--top]; 115 get_page(victim); 116 } else { 117 victim = erofs_allocpage(pagepool, 118 GFP_KERNEL | __GFP_NOFAIL); 119 set_page_private(victim, Z_EROFS_SHORTLIVED_PAGE); 120 } 121 rq->out[i] = victim; 122 } 123 return kaddr ? 1 : 0; 124 } 125 126 static void *z_erofs_handle_inplace_io(struct z_erofs_decompress_req *rq, 127 void *inpage, unsigned int *inputmargin, int *maptype, 128 bool support_0padding) 129 { 130 unsigned int nrpages_in, nrpages_out; 131 unsigned int ofull, oend, inputsize, total, i, j; 132 struct page **in; 133 void *src, *tmp; 134 135 inputsize = rq->inputsize; 136 nrpages_in = PAGE_ALIGN(inputsize) >> PAGE_SHIFT; 137 oend = rq->pageofs_out + rq->outputsize; 138 ofull = PAGE_ALIGN(oend); 139 nrpages_out = ofull >> PAGE_SHIFT; 140 141 if (rq->inplace_io) { 142 if (rq->partial_decoding || !support_0padding || 143 ofull - oend < LZ4_DECOMPRESS_INPLACE_MARGIN(inputsize)) 144 goto docopy; 145 146 for (i = 0; i < nrpages_in; ++i) { 147 DBG_BUGON(rq->in[i] == NULL); 148 for (j = 0; j < nrpages_out - nrpages_in + i; ++j) 149 if (rq->out[j] == rq->in[i]) 150 goto docopy; 151 } 152 } 153 154 if (nrpages_in <= 1) { 155 *maptype = 0; 156 return inpage; 157 } 158 kunmap_atomic(inpage); 159 might_sleep(); 160 src = erofs_vm_map_ram(rq->in, nrpages_in); 161 if (!src) 162 return ERR_PTR(-ENOMEM); 163 *maptype = 1; 164 return src; 165 166 docopy: 167 /* Or copy compressed data which can be overlapped to per-CPU buffer */ 168 in = rq->in; 169 src = erofs_get_pcpubuf(nrpages_in); 170 if (!src) { 171 DBG_BUGON(1); 172 kunmap_atomic(inpage); 173 return ERR_PTR(-EFAULT); 174 } 175 176 tmp = src; 177 total = rq->inputsize; 178 while (total) { 179 unsigned int page_copycnt = 180 min_t(unsigned int, total, PAGE_SIZE - *inputmargin); 181 182 if (!inpage) 183 inpage = kmap_atomic(*in); 184 memcpy(tmp, inpage + *inputmargin, page_copycnt); 185 kunmap_atomic(inpage); 186 inpage = NULL; 187 tmp += page_copycnt; 188 total -= page_copycnt; 189 ++in; 190 *inputmargin = 0; 191 } 192 *maptype = 2; 193 return src; 194 } 195 196 static int z_erofs_lz4_decompress(struct z_erofs_decompress_req *rq, u8 *out) 197 { 198 unsigned int inputmargin; 199 u8 *headpage, *src; 200 bool support_0padding; 201 int ret, maptype; 202 203 DBG_BUGON(*rq->in == NULL); 204 headpage = kmap_atomic(*rq->in); 205 inputmargin = 0; 206 support_0padding = false; 207 208 /* decompression inplace is only safe when 0padding is enabled */ 209 if (erofs_sb_has_lz4_0padding(EROFS_SB(rq->sb))) { 210 support_0padding = true; 211 212 while (!headpage[inputmargin & ~PAGE_MASK]) 213 if (!(++inputmargin & ~PAGE_MASK)) 214 break; 215 216 if (inputmargin >= rq->inputsize) { 217 kunmap_atomic(headpage); 218 return -EIO; 219 } 220 } 221 222 rq->inputsize -= inputmargin; 223 src = z_erofs_handle_inplace_io(rq, headpage, &inputmargin, &maptype, 224 support_0padding); 225 if (IS_ERR(src)) 226 return PTR_ERR(src); 227 228 /* legacy format could compress extra data in a pcluster. */ 229 if (rq->partial_decoding || !support_0padding) 230 ret = LZ4_decompress_safe_partial(src + inputmargin, out, 231 rq->inputsize, rq->outputsize, rq->outputsize); 232 else 233 ret = LZ4_decompress_safe(src + inputmargin, out, 234 rq->inputsize, rq->outputsize); 235 236 if (ret != rq->outputsize) { 237 erofs_err(rq->sb, "failed to decompress %d in[%u, %u] out[%u]", 238 ret, rq->inputsize, inputmargin, rq->outputsize); 239 240 print_hex_dump(KERN_DEBUG, "[ in]: ", DUMP_PREFIX_OFFSET, 241 16, 1, src + inputmargin, rq->inputsize, true); 242 print_hex_dump(KERN_DEBUG, "[out]: ", DUMP_PREFIX_OFFSET, 243 16, 1, out, rq->outputsize, true); 244 245 if (ret >= 0) 246 memset(out + ret, 0, rq->outputsize - ret); 247 ret = -EIO; 248 } 249 250 if (maptype == 0) { 251 kunmap_atomic(src); 252 } else if (maptype == 1) { 253 vm_unmap_ram(src, PAGE_ALIGN(rq->inputsize) >> PAGE_SHIFT); 254 } else if (maptype == 2) { 255 erofs_put_pcpubuf(src); 256 } else { 257 DBG_BUGON(1); 258 return -EFAULT; 259 } 260 return ret; 261 } 262 263 static struct z_erofs_decompressor decompressors[] = { 264 [Z_EROFS_COMPRESSION_SHIFTED] = { 265 .name = "shifted" 266 }, 267 [Z_EROFS_COMPRESSION_LZ4] = { 268 .prepare_destpages = z_erofs_lz4_prepare_destpages, 269 .decompress = z_erofs_lz4_decompress, 270 .name = "lz4" 271 }, 272 }; 273 274 static void copy_from_pcpubuf(struct page **out, const char *dst, 275 unsigned short pageofs_out, 276 unsigned int outputsize) 277 { 278 const char *end = dst + outputsize; 279 const unsigned int righthalf = PAGE_SIZE - pageofs_out; 280 const char *cur = dst - pageofs_out; 281 282 while (cur < end) { 283 struct page *const page = *out++; 284 285 if (page) { 286 char *buf = kmap_atomic(page); 287 288 if (cur >= dst) { 289 memcpy(buf, cur, min_t(uint, PAGE_SIZE, 290 end - cur)); 291 } else { 292 memcpy(buf + pageofs_out, cur + pageofs_out, 293 min_t(uint, righthalf, end - cur)); 294 } 295 kunmap_atomic(buf); 296 } 297 cur += PAGE_SIZE; 298 } 299 } 300 301 static int z_erofs_decompress_generic(struct z_erofs_decompress_req *rq, 302 struct list_head *pagepool) 303 { 304 const unsigned int nrpages_out = 305 PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT; 306 const struct z_erofs_decompressor *alg = decompressors + rq->alg; 307 unsigned int dst_maptype; 308 void *dst; 309 int ret; 310 311 /* two optimized fast paths only for non bigpcluster cases yet */ 312 if (rq->inputsize <= PAGE_SIZE) { 313 if (nrpages_out == 1 && !rq->inplace_io) { 314 DBG_BUGON(!*rq->out); 315 dst = kmap_atomic(*rq->out); 316 dst_maptype = 0; 317 goto dstmap_out; 318 } 319 320 /* 321 * For the case of small output size (especially much less 322 * than PAGE_SIZE), memcpy the decompressed data rather than 323 * compressed data is preferred. 324 */ 325 if (rq->outputsize <= PAGE_SIZE * 7 / 8) { 326 dst = erofs_get_pcpubuf(1); 327 if (IS_ERR(dst)) 328 return PTR_ERR(dst); 329 330 rq->inplace_io = false; 331 ret = alg->decompress(rq, dst); 332 if (!ret) 333 copy_from_pcpubuf(rq->out, dst, rq->pageofs_out, 334 rq->outputsize); 335 336 erofs_put_pcpubuf(dst); 337 return ret; 338 } 339 } 340 341 /* general decoding path which can be used for all cases */ 342 ret = alg->prepare_destpages(rq, pagepool); 343 if (ret < 0) 344 return ret; 345 if (ret) { 346 dst = page_address(*rq->out); 347 dst_maptype = 1; 348 goto dstmap_out; 349 } 350 351 dst = erofs_vm_map_ram(rq->out, nrpages_out); 352 if (!dst) 353 return -ENOMEM; 354 dst_maptype = 2; 355 356 dstmap_out: 357 ret = alg->decompress(rq, dst + rq->pageofs_out); 358 359 if (!dst_maptype) 360 kunmap_atomic(dst); 361 else if (dst_maptype == 2) 362 vm_unmap_ram(dst, nrpages_out); 363 return ret; 364 } 365 366 static int z_erofs_shifted_transform(const struct z_erofs_decompress_req *rq, 367 struct list_head *pagepool) 368 { 369 const unsigned int nrpages_out = 370 PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT; 371 const unsigned int righthalf = PAGE_SIZE - rq->pageofs_out; 372 unsigned char *src, *dst; 373 374 if (nrpages_out > 2) { 375 DBG_BUGON(1); 376 return -EIO; 377 } 378 379 if (rq->out[0] == *rq->in) { 380 DBG_BUGON(nrpages_out != 1); 381 return 0; 382 } 383 384 src = kmap_atomic(*rq->in); 385 if (rq->out[0]) { 386 dst = kmap_atomic(rq->out[0]); 387 memcpy(dst + rq->pageofs_out, src, righthalf); 388 kunmap_atomic(dst); 389 } 390 391 if (nrpages_out == 2) { 392 DBG_BUGON(!rq->out[1]); 393 if (rq->out[1] == *rq->in) { 394 memmove(src, src + righthalf, rq->pageofs_out); 395 } else { 396 dst = kmap_atomic(rq->out[1]); 397 memcpy(dst, src + righthalf, rq->pageofs_out); 398 kunmap_atomic(dst); 399 } 400 } 401 kunmap_atomic(src); 402 return 0; 403 } 404 405 int z_erofs_decompress(struct z_erofs_decompress_req *rq, 406 struct list_head *pagepool) 407 { 408 if (rq->alg == Z_EROFS_COMPRESSION_SHIFTED) 409 return z_erofs_shifted_transform(rq, pagepool); 410 return z_erofs_decompress_generic(rq, pagepool); 411 } 412