~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/btrfs/lzo.c

Version: ~ [ linux-5.19-rc3 ] ~ [ linux-5.18.5 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.48 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.123 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.199 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.248 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.284 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.319 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.302 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp