lzo.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (C) 2008 Oracle. All rights reserved.
  4. */
  5. #include <linux/kernel.h>
  6. #include <linux/slab.h>
  7. #include <linux/mm.h>
  8. #include <linux/init.h>
  9. #include <linux/err.h>
  10. #include <linux/sched.h>
  11. #include <linux/pagemap.h>
  12. #include <linux/bio.h>
  13. #include <linux/lzo.h>
  14. #include <linux/refcount.h>
  15. #include "compression.h"
  16. #define LZO_LEN 4
  17. /*
  18. * Btrfs LZO compression format
  19. *
  20. * Regular and inlined LZO compressed data extents consist of:
  21. *
  22. * 1. Header
  23. * Fixed size. LZO_LEN (4) bytes long, LE32.
  24. * Records the total size (including the header) of compressed data.
  25. *
  26. * 2. Segment(s)
  27. * Variable size. Each segment includes one segment header, followed by data
  28. * payload.
  29. * One regular LZO compressed extent can have one or more segments.
  30. * For inlined LZO compressed extent, only one segment is allowed.
  31. * One segment represents at most one page of uncompressed data.
  32. *
  33. * 2.1 Segment header
  34. * Fixed size. LZO_LEN (4) bytes long, LE32.
  35. * Records the total size of the segment (not including the header).
  36. * Segment header never crosses page boundary, thus it's possible to
  37. * have at most 3 padding zeros at the end of the page.
  38. *
  39. * 2.2 Data Payload
  40. * Variable size. Size up limit should be lzo1x_worst_compress(PAGE_SIZE)
  41. * which is 4419 for a 4KiB page.
  42. *
  43. * Example:
  44. * Page 1:
  45. * 0 0x2 0x4 0x6 0x8 0xa 0xc 0xe 0x10
  46. * 0x0000 | Header | SegHdr 01 | Data payload 01 ... |
  47. * ...
  48. * 0x0ff0 | SegHdr N | Data payload N ... |00|
  49. * ^^ padding zeros
  50. * Page 2:
  51. * 0x1000 | SegHdr N+1| Data payload N+1 ... |
  52. */
  53. struct workspace {
  54. void *mem;
  55. void *buf; /* where decompressed data goes */
  56. void *cbuf; /* where compressed data goes */
  57. struct list_head list;
  58. };
  59. static struct workspace_manager wsm;
  60. void lzo_free_workspace(struct list_head *ws)
  61. {
  62. struct workspace *workspace = list_entry(ws, struct workspace, list);
  63. kvfree(workspace->buf);
  64. kvfree(workspace->cbuf);
  65. kvfree(workspace->mem);
  66. kfree(workspace);
  67. }
  68. struct list_head *lzo_alloc_workspace(unsigned int level)
  69. {
  70. struct workspace *workspace;
  71. workspace = kzalloc(sizeof(*workspace), GFP_KERNEL);
  72. if (!workspace)
  73. return ERR_PTR(-ENOMEM);
  74. workspace->mem = kvmalloc(LZO1X_MEM_COMPRESS, GFP_KERNEL);
  75. workspace->buf = kvmalloc(lzo1x_worst_compress(PAGE_SIZE), GFP_KERNEL);
  76. workspace->cbuf = kvmalloc(lzo1x_worst_compress(PAGE_SIZE), GFP_KERNEL);
  77. if (!workspace->mem || !workspace->buf || !workspace->cbuf)
  78. goto fail;
  79. INIT_LIST_HEAD(&workspace->list);
  80. return &workspace->list;
  81. fail:
  82. lzo_free_workspace(&workspace->list);
  83. return ERR_PTR(-ENOMEM);
  84. }
  85. static inline void write_compress_length(char *buf, size_t len)
  86. {
  87. __le32 dlen;
  88. dlen = cpu_to_le32(len);
  89. memcpy(buf, &dlen, LZO_LEN);
  90. }
  91. static inline size_t read_compress_length(const char *buf)
  92. {
  93. __le32 dlen;
  94. memcpy(&dlen, buf, LZO_LEN);
  95. return le32_to_cpu(dlen);
  96. }
  97. int lzo_compress_pages(struct list_head *ws, struct address_space *mapping,
  98. u64 start, struct page **pages, unsigned long *out_pages,
  99. unsigned long *total_in, unsigned long *total_out)
  100. {
  101. struct workspace *workspace = list_entry(ws, struct workspace, list);
  102. int ret = 0;
  103. char *data_in;
  104. char *cpage_out;
  105. int nr_pages = 0;
  106. struct page *in_page = NULL;
  107. struct page *out_page = NULL;
  108. unsigned long bytes_left;
  109. unsigned long len = *total_out;
  110. unsigned long nr_dest_pages = *out_pages;
  111. const unsigned long max_out = nr_dest_pages * PAGE_SIZE;
  112. size_t in_len;
  113. size_t out_len;
  114. char *buf;
  115. unsigned long tot_in = 0;
  116. unsigned long tot_out = 0;
  117. unsigned long pg_bytes_left;
  118. unsigned long out_offset;
  119. unsigned long bytes;
  120. *out_pages = 0;
  121. *total_out = 0;
  122. *total_in = 0;
  123. in_page = find_get_page(mapping, start >> PAGE_SHIFT);
  124. data_in = kmap(in_page);
  125. /*
  126. * store the size of all chunks of compressed data in
  127. * the first 4 bytes
  128. */
  129. out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
  130. if (out_page == NULL) {
  131. ret = -ENOMEM;
  132. goto out;
  133. }
  134. cpage_out = kmap(out_page);
  135. out_offset = LZO_LEN;
  136. tot_out = LZO_LEN;
  137. pages[0] = out_page;
  138. nr_pages = 1;
  139. pg_bytes_left = PAGE_SIZE - LZO_LEN;
  140. /* compress at most one page of data each time */
  141. in_len = min(len, PAGE_SIZE);
  142. while (tot_in < len) {
  143. ret = lzo1x_1_compress(data_in, in_len, workspace->cbuf,
  144. &out_len, workspace->mem);
  145. if (ret != LZO_E_OK) {
  146. pr_debug("BTRFS: lzo in loop returned %d\n",
  147. ret);
  148. ret = -EIO;
  149. goto out;
  150. }
  151. /* store the size of this chunk of compressed data */
  152. write_compress_length(cpage_out + out_offset, out_len);
  153. tot_out += LZO_LEN;
  154. out_offset += LZO_LEN;
  155. pg_bytes_left -= LZO_LEN;
  156. tot_in += in_len;
  157. tot_out += out_len;
  158. /* copy bytes from the working buffer into the pages */
  159. buf = workspace->cbuf;
  160. while (out_len) {
  161. bytes = min_t(unsigned long, pg_bytes_left, out_len);
  162. memcpy(cpage_out + out_offset, buf, bytes);
  163. out_len -= bytes;
  164. pg_bytes_left -= bytes;
  165. buf += bytes;
  166. out_offset += bytes;
  167. /*
  168. * we need another page for writing out.
  169. *
  170. * Note if there's less than 4 bytes left, we just
  171. * skip to a new page.
  172. */
  173. if ((out_len == 0 && pg_bytes_left < LZO_LEN) ||
  174. pg_bytes_left == 0) {
  175. if (pg_bytes_left) {
  176. memset(cpage_out + out_offset, 0,
  177. pg_bytes_left);
  178. tot_out += pg_bytes_left;
  179. }
  180. /* we're done, don't allocate new page */
  181. if (out_len == 0 && tot_in >= len)
  182. break;
  183. kunmap(out_page);
  184. if (nr_pages == nr_dest_pages) {
  185. out_page = NULL;
  186. ret = -E2BIG;
  187. goto out;
  188. }
  189. out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
  190. if (out_page == NULL) {
  191. ret = -ENOMEM;
  192. goto out;
  193. }
  194. cpage_out = kmap(out_page);
  195. pages[nr_pages++] = out_page;
  196. pg_bytes_left = PAGE_SIZE;
  197. out_offset = 0;
  198. }
  199. }
  200. /* we're making it bigger, give up */
  201. if (tot_in > 8192 && tot_in < tot_out) {
  202. ret = -E2BIG;
  203. goto out;
  204. }
  205. /* we're all done */
  206. if (tot_in >= len)
  207. break;
  208. if (tot_out > max_out)
  209. break;
  210. bytes_left = len - tot_in;
  211. kunmap(in_page);
  212. put_page(in_page);
  213. start += PAGE_SIZE;
  214. in_page = find_get_page(mapping, start >> PAGE_SHIFT);
  215. data_in = kmap(in_page);
  216. in_len = min(bytes_left, PAGE_SIZE);
  217. }
  218. if (tot_out >= tot_in) {
  219. ret = -E2BIG;
  220. goto out;
  221. }
  222. /* store the size of all chunks of compressed data */
  223. cpage_out = kmap(pages[0]);
  224. write_compress_length(cpage_out, tot_out);
  225. kunmap(pages[0]);
  226. ret = 0;
  227. *total_out = tot_out;
  228. *total_in = tot_in;
  229. out:
  230. *out_pages = nr_pages;
  231. if (out_page)
  232. kunmap(out_page);
  233. if (in_page) {
  234. kunmap(in_page);
  235. put_page(in_page);
  236. }
  237. return ret;
  238. }
  239. int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)
  240. {
  241. struct workspace *workspace = list_entry(ws, struct workspace, list);
  242. int ret = 0, ret2;
  243. char *data_in;
  244. unsigned long page_in_index = 0;
  245. size_t srclen = cb->compressed_len;
  246. unsigned long total_pages_in = DIV_ROUND_UP(srclen, PAGE_SIZE);
  247. unsigned long buf_start;
  248. unsigned long buf_offset = 0;
  249. unsigned long bytes;
  250. unsigned long working_bytes;
  251. size_t in_len;
  252. size_t out_len;
  253. const size_t max_segment_len = lzo1x_worst_compress(PAGE_SIZE);
  254. unsigned long in_offset;
  255. unsigned long in_page_bytes_left;
  256. unsigned long tot_in;
  257. unsigned long tot_out;
  258. unsigned long tot_len;
  259. char *buf;
  260. bool may_late_unmap, need_unmap;
  261. struct page **pages_in = cb->compressed_pages;
  262. u64 disk_start = cb->start;
  263. struct bio *orig_bio = cb->orig_bio;
  264. data_in = kmap(pages_in[0]);
  265. tot_len = read_compress_length(data_in);
  266. /*
  267. * Compressed data header check.
  268. *
  269. * The real compressed size can't exceed the maximum extent length, and
  270. * all pages should be used (whole unused page with just the segment
  271. * header is not possible). If this happens it means the compressed
  272. * extent is corrupted.
  273. */
  274. if (tot_len > min_t(size_t, BTRFS_MAX_COMPRESSED, srclen) ||
  275. tot_len < srclen - PAGE_SIZE) {
  276. ret = -EUCLEAN;
  277. goto done;
  278. }
  279. tot_in = LZO_LEN;
  280. in_offset = LZO_LEN;
  281. in_page_bytes_left = PAGE_SIZE - LZO_LEN;
  282. tot_out = 0;
  283. while (tot_in < tot_len) {
  284. in_len = read_compress_length(data_in + in_offset);
  285. in_page_bytes_left -= LZO_LEN;
  286. in_offset += LZO_LEN;
  287. tot_in += LZO_LEN;
  288. /*
  289. * Segment header check.
  290. *
  291. * The segment length must not exceed the maximum LZO
  292. * compression size, nor the total compressed size.
  293. */
  294. if (in_len > max_segment_len || tot_in + in_len > tot_len) {
  295. ret = -EUCLEAN;
  296. goto done;
  297. }
  298. tot_in += in_len;
  299. working_bytes = in_len;
  300. may_late_unmap = need_unmap = false;
  301. /* fast path: avoid using the working buffer */
  302. if (in_page_bytes_left >= in_len) {
  303. buf = data_in + in_offset;
  304. bytes = in_len;
  305. may_late_unmap = true;
  306. goto cont;
  307. }
  308. /* copy bytes from the pages into the working buffer */
  309. buf = workspace->cbuf;
  310. buf_offset = 0;
  311. while (working_bytes) {
  312. bytes = min(working_bytes, in_page_bytes_left);
  313. memcpy(buf + buf_offset, data_in + in_offset, bytes);
  314. buf_offset += bytes;
  315. cont:
  316. working_bytes -= bytes;
  317. in_page_bytes_left -= bytes;
  318. in_offset += bytes;
  319. /* check if we need to pick another page */
  320. if ((working_bytes == 0 && in_page_bytes_left < LZO_LEN)
  321. || in_page_bytes_left == 0) {
  322. tot_in += in_page_bytes_left;
  323. if (working_bytes == 0 && tot_in >= tot_len)
  324. break;
  325. if (page_in_index + 1 >= total_pages_in) {
  326. ret = -EIO;
  327. goto done;
  328. }
  329. if (may_late_unmap)
  330. need_unmap = true;
  331. else
  332. kunmap(pages_in[page_in_index]);
  333. data_in = kmap(pages_in[++page_in_index]);
  334. in_page_bytes_left = PAGE_SIZE;
  335. in_offset = 0;
  336. }
  337. }
  338. out_len = max_segment_len;
  339. ret = lzo1x_decompress_safe(buf, in_len, workspace->buf,
  340. &out_len);
  341. if (need_unmap)
  342. kunmap(pages_in[page_in_index - 1]);
  343. if (ret != LZO_E_OK) {
  344. pr_warn("BTRFS: decompress failed\n");
  345. ret = -EIO;
  346. break;
  347. }
  348. buf_start = tot_out;
  349. tot_out += out_len;
  350. ret2 = btrfs_decompress_buf2page(workspace->buf, buf_start,
  351. tot_out, disk_start, orig_bio);
  352. if (ret2 == 0)
  353. break;
  354. }
  355. done:
  356. kunmap(pages_in[page_in_index]);
  357. if (!ret)
  358. zero_fill_bio(orig_bio);
  359. return ret;
  360. }
  361. int lzo_decompress(struct list_head *ws, unsigned char *data_in,
  362. struct page *dest_page, unsigned long start_byte, size_t srclen,
  363. size_t destlen)
  364. {
  365. struct workspace *workspace = list_entry(ws, struct workspace, list);
  366. size_t in_len;
  367. size_t out_len;
  368. size_t max_segment_len = lzo1x_worst_compress(PAGE_SIZE);
  369. int ret = 0;
  370. char *kaddr;
  371. unsigned long bytes;
  372. if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2)
  373. return -EUCLEAN;
  374. in_len = read_compress_length(data_in);
  375. if (in_len != srclen)
  376. return -EUCLEAN;
  377. data_in += LZO_LEN;
  378. in_len = read_compress_length(data_in);
  379. if (in_len != srclen - LZO_LEN * 2) {
  380. ret = -EUCLEAN;
  381. goto out;
  382. }
  383. data_in += LZO_LEN;
  384. out_len = PAGE_SIZE;
  385. ret = lzo1x_decompress_safe(data_in, in_len, workspace->buf, &out_len);
  386. if (ret != LZO_E_OK) {
  387. pr_warn("BTRFS: decompress failed!\n");
  388. ret = -EIO;
  389. goto out;
  390. }
  391. if (out_len < start_byte) {
  392. ret = -EIO;
  393. goto out;
  394. }
  395. /*
  396. * the caller is already checking against PAGE_SIZE, but lets
  397. * move this check closer to the memcpy/memset
  398. */
  399. destlen = min_t(unsigned long, destlen, PAGE_SIZE);
  400. bytes = min_t(unsigned long, destlen, out_len - start_byte);
  401. kaddr = kmap_atomic(dest_page);
  402. memcpy(kaddr, workspace->buf + start_byte, bytes);
  403. /*
  404. * btrfs_getblock is doing a zero on the tail of the page too,
  405. * but this will cover anything missing from the decompressed
  406. * data.
  407. */
  408. if (bytes < destlen)
  409. memset(kaddr+bytes, 0, destlen-bytes);
  410. kunmap_atomic(kaddr);
  411. out:
  412. return ret;
  413. }
  414. const struct btrfs_compress_op btrfs_lzo_compress = {
  415. .workspace_manager = &wsm,
  416. .max_level = 1,
  417. .default_level = 1,
  418. };