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

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

Version: ~ [ linux-5.8-rc4 ] ~ [ linux-5.7.7 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.50 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.131 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.187 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.229 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.229 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ 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.5 ] ~ [ 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, followd 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 void lzo_free_workspace(struct list_head *ws)
 65 {
 66         struct workspace *workspace = list_entry(ws, struct workspace, list);
 67 
 68         kvfree(workspace->buf);
 69         kvfree(workspace->cbuf);
 70         kvfree(workspace->mem);
 71         kfree(workspace);
 72 }
 73 
 74 static struct list_head *lzo_alloc_workspace(void)
 75 {
 76         struct workspace *workspace;
 77 
 78         workspace = kzalloc(sizeof(*workspace), GFP_KERNEL);
 79         if (!workspace)
 80                 return ERR_PTR(-ENOMEM);
 81 
 82         workspace->mem = kvmalloc(LZO1X_MEM_COMPRESS, GFP_KERNEL);
 83         workspace->buf = kvmalloc(lzo1x_worst_compress(PAGE_SIZE), GFP_KERNEL);
 84         workspace->cbuf = kvmalloc(lzo1x_worst_compress(PAGE_SIZE), GFP_KERNEL);
 85         if (!workspace->mem || !workspace->buf || !workspace->cbuf)
 86                 goto fail;
 87 
 88         INIT_LIST_HEAD(&workspace->list);
 89 
 90         return &workspace->list;
 91 fail:
 92         lzo_free_workspace(&workspace->list);
 93         return ERR_PTR(-ENOMEM);
 94 }
 95 
 96 static inline void write_compress_length(char *buf, size_t len)
 97 {
 98         __le32 dlen;
 99 
100         dlen = cpu_to_le32(len);
101         memcpy(buf, &dlen, LZO_LEN);
102 }
103 
104 static inline size_t read_compress_length(const char *buf)
105 {
106         __le32 dlen;
107 
108         memcpy(&dlen, buf, LZO_LEN);
109         return le32_to_cpu(dlen);
110 }
111 
112 static int lzo_compress_pages(struct list_head *ws,
113                               struct address_space *mapping,
114                               u64 start,
115                               struct page **pages,
116                               unsigned long *out_pages,
117                               unsigned long *total_in,
118                               unsigned long *total_out)
119 {
120         struct workspace *workspace = list_entry(ws, struct workspace, list);
121         int ret = 0;
122         char *data_in;
123         char *cpage_out;
124         int nr_pages = 0;
125         struct page *in_page = NULL;
126         struct page *out_page = NULL;
127         unsigned long bytes_left;
128         unsigned long len = *total_out;
129         unsigned long nr_dest_pages = *out_pages;
130         const unsigned long max_out = nr_dest_pages * PAGE_SIZE;
131         size_t in_len;
132         size_t out_len;
133         char *buf;
134         unsigned long tot_in = 0;
135         unsigned long tot_out = 0;
136         unsigned long pg_bytes_left;
137         unsigned long out_offset;
138         unsigned long bytes;
139 
140         *out_pages = 0;
141         *total_out = 0;
142         *total_in = 0;
143 
144         in_page = find_get_page(mapping, start >> PAGE_SHIFT);
145         data_in = kmap(in_page);
146 
147         /*
148          * store the size of all chunks of compressed data in
149          * the first 4 bytes
150          */
151         out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
152         if (out_page == NULL) {
153                 ret = -ENOMEM;
154                 goto out;
155         }
156         cpage_out = kmap(out_page);
157         out_offset = LZO_LEN;
158         tot_out = LZO_LEN;
159         pages[0] = out_page;
160         nr_pages = 1;
161         pg_bytes_left = PAGE_SIZE - LZO_LEN;
162 
163         /* compress at most one page of data each time */
164         in_len = min(len, PAGE_SIZE);
165         while (tot_in < len) {
166                 ret = lzo1x_1_compress(data_in, in_len, workspace->cbuf,
167                                        &out_len, workspace->mem);
168                 if (ret != LZO_E_OK) {
169                         pr_debug("BTRFS: lzo in loop returned %d\n",
170                                ret);
171                         ret = -EIO;
172                         goto out;
173                 }
174 
175                 /* store the size of this chunk of compressed data */
176                 write_compress_length(cpage_out + out_offset, out_len);
177                 tot_out += LZO_LEN;
178                 out_offset += LZO_LEN;
179                 pg_bytes_left -= LZO_LEN;
180 
181                 tot_in += in_len;
182                 tot_out += out_len;
183 
184                 /* copy bytes from the working buffer into the pages */
185                 buf = workspace->cbuf;
186                 while (out_len) {
187                         bytes = min_t(unsigned long, pg_bytes_left, out_len);
188 
189                         memcpy(cpage_out + out_offset, buf, bytes);
190 
191                         out_len -= bytes;
192                         pg_bytes_left -= bytes;
193                         buf += bytes;
194                         out_offset += bytes;
195 
196                         /*
197                          * we need another page for writing out.
198                          *
199                          * Note if there's less than 4 bytes left, we just
200                          * skip to a new page.
201                          */
202                         if ((out_len == 0 && pg_bytes_left < LZO_LEN) ||
203                             pg_bytes_left == 0) {
204                                 if (pg_bytes_left) {
205                                         memset(cpage_out + out_offset, 0,
206                                                pg_bytes_left);
207                                         tot_out += pg_bytes_left;
208                                 }
209 
210                                 /* we're done, don't allocate new page */
211                                 if (out_len == 0 && tot_in >= len)
212                                         break;
213 
214                                 kunmap(out_page);
215                                 if (nr_pages == nr_dest_pages) {
216                                         out_page = NULL;
217                                         ret = -E2BIG;
218                                         goto out;
219                                 }
220 
221                                 out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
222                                 if (out_page == NULL) {
223                                         ret = -ENOMEM;
224                                         goto out;
225                                 }
226                                 cpage_out = kmap(out_page);
227                                 pages[nr_pages++] = out_page;
228 
229                                 pg_bytes_left = PAGE_SIZE;
230                                 out_offset = 0;
231                         }
232                 }
233 
234                 /* we're making it bigger, give up */
235                 if (tot_in > 8192 && tot_in < tot_out) {
236                         ret = -E2BIG;
237                         goto out;
238                 }
239 
240                 /* we're all done */
241                 if (tot_in >= len)
242                         break;
243 
244                 if (tot_out > max_out)
245                         break;
246 
247                 bytes_left = len - tot_in;
248                 kunmap(in_page);
249                 put_page(in_page);
250 
251                 start += PAGE_SIZE;
252                 in_page = find_get_page(mapping, start >> PAGE_SHIFT);
253                 data_in = kmap(in_page);
254                 in_len = min(bytes_left, PAGE_SIZE);
255         }
256 
257         if (tot_out >= tot_in) {
258                 ret = -E2BIG;
259                 goto out;
260         }
261 
262         /* store the size of all chunks of compressed data */
263         cpage_out = kmap(pages[0]);
264         write_compress_length(cpage_out, tot_out);
265 
266         kunmap(pages[0]);
267 
268         ret = 0;
269         *total_out = tot_out;
270         *total_in = tot_in;
271 out:
272         *out_pages = nr_pages;
273         if (out_page)
274                 kunmap(out_page);
275 
276         if (in_page) {
277                 kunmap(in_page);
278                 put_page(in_page);
279         }
280 
281         return ret;
282 }
283 
284 static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)
285 {
286         struct workspace *workspace = list_entry(ws, struct workspace, list);
287         int ret = 0, ret2;
288         char *data_in;
289         unsigned long page_in_index = 0;
290         size_t srclen = cb->compressed_len;
291         unsigned long total_pages_in = DIV_ROUND_UP(srclen, PAGE_SIZE);
292         unsigned long buf_start;
293         unsigned long buf_offset = 0;
294         unsigned long bytes;
295         unsigned long working_bytes;
296         size_t in_len;
297         size_t out_len;
298         const size_t max_segment_len = lzo1x_worst_compress(PAGE_SIZE);
299         unsigned long in_offset;
300         unsigned long in_page_bytes_left;
301         unsigned long tot_in;
302         unsigned long tot_out;
303         unsigned long tot_len;
304         char *buf;
305         bool may_late_unmap, need_unmap;
306         struct page **pages_in = cb->compressed_pages;
307         u64 disk_start = cb->start;
308         struct bio *orig_bio = cb->orig_bio;
309 
310         data_in = kmap(pages_in[0]);
311         tot_len = read_compress_length(data_in);
312         /*
313          * Compressed data header check.
314          *
315          * The real compressed size can't exceed the maximum extent length, and
316          * all pages should be used (whole unused page with just the segment
317          * header is not possible).  If this happens it means the compressed
318          * extent is corrupted.
319          */
320         if (tot_len > min_t(size_t, BTRFS_MAX_COMPRESSED, srclen) ||
321             tot_len < srclen - PAGE_SIZE) {
322                 ret = -EUCLEAN;
323                 goto done;
324         }
325 
326         tot_in = LZO_LEN;
327         in_offset = LZO_LEN;
328         in_page_bytes_left = PAGE_SIZE - LZO_LEN;
329 
330         tot_out = 0;
331 
332         while (tot_in < tot_len) {
333                 in_len = read_compress_length(data_in + in_offset);
334                 in_page_bytes_left -= LZO_LEN;
335                 in_offset += LZO_LEN;
336                 tot_in += LZO_LEN;
337 
338                 /*
339                  * Segment header check.
340                  *
341                  * The segment length must not exceed the maximum LZO
342                  * compression size, nor the total compressed size.
343                  */
344                 if (in_len > max_segment_len || tot_in + in_len > tot_len) {
345                         ret = -EUCLEAN;
346                         goto done;
347                 }
348 
349                 tot_in += in_len;
350                 working_bytes = in_len;
351                 may_late_unmap = need_unmap = false;
352 
353                 /* fast path: avoid using the working buffer */
354                 if (in_page_bytes_left >= in_len) {
355                         buf = data_in + in_offset;
356                         bytes = in_len;
357                         may_late_unmap = true;
358                         goto cont;
359                 }
360 
361                 /* copy bytes from the pages into the working buffer */
362                 buf = workspace->cbuf;
363                 buf_offset = 0;
364                 while (working_bytes) {
365                         bytes = min(working_bytes, in_page_bytes_left);
366 
367                         memcpy(buf + buf_offset, data_in + in_offset, bytes);
368                         buf_offset += bytes;
369 cont:
370                         working_bytes -= bytes;
371                         in_page_bytes_left -= bytes;
372                         in_offset += bytes;
373 
374                         /* check if we need to pick another page */
375                         if ((working_bytes == 0 && in_page_bytes_left < LZO_LEN)
376                             || in_page_bytes_left == 0) {
377                                 tot_in += in_page_bytes_left;
378 
379                                 if (working_bytes == 0 && tot_in >= tot_len)
380                                         break;
381 
382                                 if (page_in_index + 1 >= total_pages_in) {
383                                         ret = -EIO;
384                                         goto done;
385                                 }
386 
387                                 if (may_late_unmap)
388                                         need_unmap = true;
389                                 else
390                                         kunmap(pages_in[page_in_index]);
391 
392                                 data_in = kmap(pages_in[++page_in_index]);
393 
394                                 in_page_bytes_left = PAGE_SIZE;
395                                 in_offset = 0;
396                         }
397                 }
398 
399                 out_len = max_segment_len;
400                 ret = lzo1x_decompress_safe(buf, in_len, workspace->buf,
401                                             &out_len);
402                 if (need_unmap)
403                         kunmap(pages_in[page_in_index - 1]);
404                 if (ret != LZO_E_OK) {
405                         pr_warn("BTRFS: decompress failed\n");
406                         ret = -EIO;
407                         break;
408                 }
409 
410                 buf_start = tot_out;
411                 tot_out += out_len;
412 
413                 ret2 = btrfs_decompress_buf2page(workspace->buf, buf_start,
414                                                  tot_out, disk_start, orig_bio);
415                 if (ret2 == 0)
416                         break;
417         }
418 done:
419         kunmap(pages_in[page_in_index]);
420         if (!ret)
421                 zero_fill_bio(orig_bio);
422         return ret;
423 }
424 
425 static int lzo_decompress(struct list_head *ws, unsigned char *data_in,
426                           struct page *dest_page,
427                           unsigned long start_byte,
428                           size_t srclen, size_t destlen)
429 {
430         struct workspace *workspace = list_entry(ws, struct workspace, list);
431         size_t in_len;
432         size_t out_len;
433         size_t max_segment_len = lzo1x_worst_compress(PAGE_SIZE);
434         int ret = 0;
435         char *kaddr;
436         unsigned long bytes;
437 
438         if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2)
439                 return -EUCLEAN;
440 
441         in_len = read_compress_length(data_in);
442         if (in_len != srclen)
443                 return -EUCLEAN;
444         data_in += LZO_LEN;
445 
446         in_len = read_compress_length(data_in);
447         if (in_len != srclen - LZO_LEN * 2) {
448                 ret = -EUCLEAN;
449                 goto out;
450         }
451         data_in += LZO_LEN;
452 
453         out_len = PAGE_SIZE;
454         ret = lzo1x_decompress_safe(data_in, in_len, workspace->buf, &out_len);
455         if (ret != LZO_E_OK) {
456                 pr_warn("BTRFS: decompress failed!\n");
457                 ret = -EIO;
458                 goto out;
459         }
460 
461         if (out_len < start_byte) {
462                 ret = -EIO;
463                 goto out;
464         }
465 
466         /*
467          * the caller is already checking against PAGE_SIZE, but lets
468          * move this check closer to the memcpy/memset
469          */
470         destlen = min_t(unsigned long, destlen, PAGE_SIZE);
471         bytes = min_t(unsigned long, destlen, out_len - start_byte);
472 
473         kaddr = kmap_atomic(dest_page);
474         memcpy(kaddr, workspace->buf + start_byte, bytes);
475 
476         /*
477          * btrfs_getblock is doing a zero on the tail of the page too,
478          * but this will cover anything missing from the decompressed
479          * data.
480          */
481         if (bytes < destlen)
482                 memset(kaddr+bytes, 0, destlen-bytes);
483         kunmap_atomic(kaddr);
484 out:
485         return ret;
486 }
487 
488 static void lzo_set_level(struct list_head *ws, unsigned int type)
489 {
490 }
491 
492 const struct btrfs_compress_op btrfs_lzo_compress = {
493         .alloc_workspace        = lzo_alloc_workspace,
494         .free_workspace         = lzo_free_workspace,
495         .compress_pages         = lzo_compress_pages,
496         .decompress_bio         = lzo_decompress_bio,
497         .decompress             = lzo_decompress,
498         .set_level              = lzo_set_level,
499 };
500 

~ [ 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