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 (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_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 162 docopy: 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 192 static 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 260 static 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 271 static 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 298 static 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 353 dstmap_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 363 static 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 402 int 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