Loading...
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/bio.h>
8#include <linux/file.h>
9#include <linux/fs.h>
10#include <linux/pagemap.h>
11#include <linux/highmem.h>
12#include <linux/time.h>
13#include <linux/init.h>
14#include <linux/string.h>
15#include <linux/backing-dev.h>
16#include <linux/writeback.h>
17#include <linux/slab.h>
18#include <linux/sched/mm.h>
19#include <linux/log2.h>
20#include <crypto/hash.h>
21#include "misc.h"
22#include "ctree.h"
23#include "disk-io.h"
24#include "transaction.h"
25#include "btrfs_inode.h"
26#include "volumes.h"
27#include "ordered-data.h"
28#include "compression.h"
29#include "extent_io.h"
30#include "extent_map.h"
31
32int zlib_compress_pages(struct list_head *ws, struct address_space *mapping,
33 u64 start, struct page **pages, unsigned long *out_pages,
34 unsigned long *total_in, unsigned long *total_out);
35int zlib_decompress_bio(struct list_head *ws, struct compressed_bio *cb);
36int zlib_decompress(struct list_head *ws, unsigned char *data_in,
37 struct page *dest_page, unsigned long start_byte, size_t srclen,
38 size_t destlen);
39struct list_head *zlib_alloc_workspace(unsigned int level);
40void zlib_free_workspace(struct list_head *ws);
41struct list_head *zlib_get_workspace(unsigned int level);
42
43int lzo_compress_pages(struct list_head *ws, struct address_space *mapping,
44 u64 start, struct page **pages, unsigned long *out_pages,
45 unsigned long *total_in, unsigned long *total_out);
46int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb);
47int lzo_decompress(struct list_head *ws, unsigned char *data_in,
48 struct page *dest_page, unsigned long start_byte, size_t srclen,
49 size_t destlen);
50struct list_head *lzo_alloc_workspace(unsigned int level);
51void lzo_free_workspace(struct list_head *ws);
52
53int zstd_compress_pages(struct list_head *ws, struct address_space *mapping,
54 u64 start, struct page **pages, unsigned long *out_pages,
55 unsigned long *total_in, unsigned long *total_out);
56int zstd_decompress_bio(struct list_head *ws, struct compressed_bio *cb);
57int zstd_decompress(struct list_head *ws, unsigned char *data_in,
58 struct page *dest_page, unsigned long start_byte, size_t srclen,
59 size_t destlen);
60void zstd_init_workspace_manager(void);
61void zstd_cleanup_workspace_manager(void);
62struct list_head *zstd_alloc_workspace(unsigned int level);
63void zstd_free_workspace(struct list_head *ws);
64struct list_head *zstd_get_workspace(unsigned int level);
65void zstd_put_workspace(struct list_head *ws);
66
67static const char* const btrfs_compress_types[] = { "", "zlib", "lzo", "zstd" };
68
69const char* btrfs_compress_type2str(enum btrfs_compression_type type)
70{
71 switch (type) {
72 case BTRFS_COMPRESS_ZLIB:
73 case BTRFS_COMPRESS_LZO:
74 case BTRFS_COMPRESS_ZSTD:
75 case BTRFS_COMPRESS_NONE:
76 return btrfs_compress_types[type];
77 default:
78 break;
79 }
80
81 return NULL;
82}
83
84bool btrfs_compress_is_valid_type(const char *str, size_t len)
85{
86 int i;
87
88 for (i = 1; i < ARRAY_SIZE(btrfs_compress_types); i++) {
89 size_t comp_len = strlen(btrfs_compress_types[i]);
90
91 if (len < comp_len)
92 continue;
93
94 if (!strncmp(btrfs_compress_types[i], str, comp_len))
95 return true;
96 }
97 return false;
98}
99
100static int compression_compress_pages(int type, struct list_head *ws,
101 struct address_space *mapping, u64 start, struct page **pages,
102 unsigned long *out_pages, unsigned long *total_in,
103 unsigned long *total_out)
104{
105 switch (type) {
106 case BTRFS_COMPRESS_ZLIB:
107 return zlib_compress_pages(ws, mapping, start, pages,
108 out_pages, total_in, total_out);
109 case BTRFS_COMPRESS_LZO:
110 return lzo_compress_pages(ws, mapping, start, pages,
111 out_pages, total_in, total_out);
112 case BTRFS_COMPRESS_ZSTD:
113 return zstd_compress_pages(ws, mapping, start, pages,
114 out_pages, total_in, total_out);
115 case BTRFS_COMPRESS_NONE:
116 default:
117 /*
118 * This can't happen, the type is validated several times
119 * before we get here. As a sane fallback, return what the
120 * callers will understand as 'no compression happened'.
121 */
122 return -E2BIG;
123 }
124}
125
126static int compression_decompress_bio(int type, struct list_head *ws,
127 struct compressed_bio *cb)
128{
129 switch (type) {
130 case BTRFS_COMPRESS_ZLIB: return zlib_decompress_bio(ws, cb);
131 case BTRFS_COMPRESS_LZO: return lzo_decompress_bio(ws, cb);
132 case BTRFS_COMPRESS_ZSTD: return zstd_decompress_bio(ws, cb);
133 case BTRFS_COMPRESS_NONE:
134 default:
135 /*
136 * This can't happen, the type is validated several times
137 * before we get here.
138 */
139 BUG();
140 }
141}
142
143static int compression_decompress(int type, struct list_head *ws,
144 unsigned char *data_in, struct page *dest_page,
145 unsigned long start_byte, size_t srclen, size_t destlen)
146{
147 switch (type) {
148 case BTRFS_COMPRESS_ZLIB: return zlib_decompress(ws, data_in, dest_page,
149 start_byte, srclen, destlen);
150 case BTRFS_COMPRESS_LZO: return lzo_decompress(ws, data_in, dest_page,
151 start_byte, srclen, destlen);
152 case BTRFS_COMPRESS_ZSTD: return zstd_decompress(ws, data_in, dest_page,
153 start_byte, srclen, destlen);
154 case BTRFS_COMPRESS_NONE:
155 default:
156 /*
157 * This can't happen, the type is validated several times
158 * before we get here.
159 */
160 BUG();
161 }
162}
163
164static int btrfs_decompress_bio(struct compressed_bio *cb);
165
166static inline int compressed_bio_size(struct btrfs_fs_info *fs_info,
167 unsigned long disk_size)
168{
169 u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
170
171 return sizeof(struct compressed_bio) +
172 (DIV_ROUND_UP(disk_size, fs_info->sectorsize)) * csum_size;
173}
174
175static int check_compressed_csum(struct btrfs_inode *inode, struct bio *bio,
176 u64 disk_start)
177{
178 struct btrfs_fs_info *fs_info = inode->root->fs_info;
179 SHASH_DESC_ON_STACK(shash, fs_info->csum_shash);
180 const u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
181 struct page *page;
182 unsigned long i;
183 char *kaddr;
184 u8 csum[BTRFS_CSUM_SIZE];
185 struct compressed_bio *cb = bio->bi_private;
186 u8 *cb_sum = cb->sums;
187
188 if (inode->flags & BTRFS_INODE_NODATASUM)
189 return 0;
190
191 shash->tfm = fs_info->csum_shash;
192
193 for (i = 0; i < cb->nr_pages; i++) {
194 page = cb->compressed_pages[i];
195
196 kaddr = kmap_atomic(page);
197 crypto_shash_digest(shash, kaddr, PAGE_SIZE, csum);
198 kunmap_atomic(kaddr);
199
200 if (memcmp(&csum, cb_sum, csum_size)) {
201 btrfs_print_data_csum_error(inode, disk_start,
202 csum, cb_sum, cb->mirror_num);
203 if (btrfs_io_bio(bio)->device)
204 btrfs_dev_stat_inc_and_print(
205 btrfs_io_bio(bio)->device,
206 BTRFS_DEV_STAT_CORRUPTION_ERRS);
207 return -EIO;
208 }
209 cb_sum += csum_size;
210 }
211 return 0;
212}
213
214/* when we finish reading compressed pages from the disk, we
215 * decompress them and then run the bio end_io routines on the
216 * decompressed pages (in the inode address space).
217 *
218 * This allows the checksumming and other IO error handling routines
219 * to work normally
220 *
221 * The compressed pages are freed here, and it must be run
222 * in process context
223 */
224static void end_compressed_bio_read(struct bio *bio)
225{
226 struct compressed_bio *cb = bio->bi_private;
227 struct inode *inode;
228 struct page *page;
229 unsigned long index;
230 unsigned int mirror = btrfs_io_bio(bio)->mirror_num;
231 int ret = 0;
232
233 if (bio->bi_status)
234 cb->errors = 1;
235
236 /* if there are more bios still pending for this compressed
237 * extent, just exit
238 */
239 if (!refcount_dec_and_test(&cb->pending_bios))
240 goto out;
241
242 /*
243 * Record the correct mirror_num in cb->orig_bio so that
244 * read-repair can work properly.
245 */
246 btrfs_io_bio(cb->orig_bio)->mirror_num = mirror;
247 cb->mirror_num = mirror;
248
249 /*
250 * Some IO in this cb have failed, just skip checksum as there
251 * is no way it could be correct.
252 */
253 if (cb->errors == 1)
254 goto csum_failed;
255
256 inode = cb->inode;
257 ret = check_compressed_csum(BTRFS_I(inode), bio,
258 (u64)bio->bi_iter.bi_sector << 9);
259 if (ret)
260 goto csum_failed;
261
262 /* ok, we're the last bio for this extent, lets start
263 * the decompression.
264 */
265 ret = btrfs_decompress_bio(cb);
266
267csum_failed:
268 if (ret)
269 cb->errors = 1;
270
271 /* release the compressed pages */
272 index = 0;
273 for (index = 0; index < cb->nr_pages; index++) {
274 page = cb->compressed_pages[index];
275 page->mapping = NULL;
276 put_page(page);
277 }
278
279 /* do io completion on the original bio */
280 if (cb->errors) {
281 bio_io_error(cb->orig_bio);
282 } else {
283 struct bio_vec *bvec;
284 struct bvec_iter_all iter_all;
285
286 /*
287 * we have verified the checksum already, set page
288 * checked so the end_io handlers know about it
289 */
290 ASSERT(!bio_flagged(bio, BIO_CLONED));
291 bio_for_each_segment_all(bvec, cb->orig_bio, iter_all)
292 SetPageChecked(bvec->bv_page);
293
294 bio_endio(cb->orig_bio);
295 }
296
297 /* finally free the cb struct */
298 kfree(cb->compressed_pages);
299 kfree(cb);
300out:
301 bio_put(bio);
302}
303
304/*
305 * Clear the writeback bits on all of the file
306 * pages for a compressed write
307 */
308static noinline void end_compressed_writeback(struct inode *inode,
309 const struct compressed_bio *cb)
310{
311 unsigned long index = cb->start >> PAGE_SHIFT;
312 unsigned long end_index = (cb->start + cb->len - 1) >> PAGE_SHIFT;
313 struct page *pages[16];
314 unsigned long nr_pages = end_index - index + 1;
315 int i;
316 int ret;
317
318 if (cb->errors)
319 mapping_set_error(inode->i_mapping, -EIO);
320
321 while (nr_pages > 0) {
322 ret = find_get_pages_contig(inode->i_mapping, index,
323 min_t(unsigned long,
324 nr_pages, ARRAY_SIZE(pages)), pages);
325 if (ret == 0) {
326 nr_pages -= 1;
327 index += 1;
328 continue;
329 }
330 for (i = 0; i < ret; i++) {
331 if (cb->errors)
332 SetPageError(pages[i]);
333 end_page_writeback(pages[i]);
334 put_page(pages[i]);
335 }
336 nr_pages -= ret;
337 index += ret;
338 }
339 /* the inode may be gone now */
340}
341
342/*
343 * do the cleanup once all the compressed pages hit the disk.
344 * This will clear writeback on the file pages and free the compressed
345 * pages.
346 *
347 * This also calls the writeback end hooks for the file pages so that
348 * metadata and checksums can be updated in the file.
349 */
350static void end_compressed_bio_write(struct bio *bio)
351{
352 struct compressed_bio *cb = bio->bi_private;
353 struct inode *inode;
354 struct page *page;
355 unsigned long index;
356
357 if (bio->bi_status)
358 cb->errors = 1;
359
360 /* if there are more bios still pending for this compressed
361 * extent, just exit
362 */
363 if (!refcount_dec_and_test(&cb->pending_bios))
364 goto out;
365
366 /* ok, we're the last bio for this extent, step one is to
367 * call back into the FS and do all the end_io operations
368 */
369 inode = cb->inode;
370 cb->compressed_pages[0]->mapping = cb->inode->i_mapping;
371 btrfs_writepage_endio_finish_ordered(cb->compressed_pages[0],
372 cb->start, cb->start + cb->len - 1,
373 bio->bi_status == BLK_STS_OK);
374 cb->compressed_pages[0]->mapping = NULL;
375
376 end_compressed_writeback(inode, cb);
377 /* note, our inode could be gone now */
378
379 /*
380 * release the compressed pages, these came from alloc_page and
381 * are not attached to the inode at all
382 */
383 index = 0;
384 for (index = 0; index < cb->nr_pages; index++) {
385 page = cb->compressed_pages[index];
386 page->mapping = NULL;
387 put_page(page);
388 }
389
390 /* finally free the cb struct */
391 kfree(cb->compressed_pages);
392 kfree(cb);
393out:
394 bio_put(bio);
395}
396
397/*
398 * worker function to build and submit bios for previously compressed pages.
399 * The corresponding pages in the inode should be marked for writeback
400 * and the compressed pages should have a reference on them for dropping
401 * when the IO is complete.
402 *
403 * This also checksums the file bytes and gets things ready for
404 * the end io hooks.
405 */
406blk_status_t btrfs_submit_compressed_write(struct btrfs_inode *inode, u64 start,
407 unsigned long len, u64 disk_start,
408 unsigned long compressed_len,
409 struct page **compressed_pages,
410 unsigned long nr_pages,
411 unsigned int write_flags,
412 struct cgroup_subsys_state *blkcg_css)
413{
414 struct btrfs_fs_info *fs_info = inode->root->fs_info;
415 struct bio *bio = NULL;
416 struct compressed_bio *cb;
417 unsigned long bytes_left;
418 int pg_index = 0;
419 struct page *page;
420 u64 first_byte = disk_start;
421 blk_status_t ret;
422 int skip_sum = inode->flags & BTRFS_INODE_NODATASUM;
423
424 WARN_ON(!PAGE_ALIGNED(start));
425 cb = kmalloc(compressed_bio_size(fs_info, compressed_len), GFP_NOFS);
426 if (!cb)
427 return BLK_STS_RESOURCE;
428 refcount_set(&cb->pending_bios, 0);
429 cb->errors = 0;
430 cb->inode = &inode->vfs_inode;
431 cb->start = start;
432 cb->len = len;
433 cb->mirror_num = 0;
434 cb->compressed_pages = compressed_pages;
435 cb->compressed_len = compressed_len;
436 cb->orig_bio = NULL;
437 cb->nr_pages = nr_pages;
438
439 bio = btrfs_bio_alloc(first_byte);
440 bio->bi_opf = REQ_OP_WRITE | write_flags;
441 bio->bi_private = cb;
442 bio->bi_end_io = end_compressed_bio_write;
443
444 if (blkcg_css) {
445 bio->bi_opf |= REQ_CGROUP_PUNT;
446 kthread_associate_blkcg(blkcg_css);
447 }
448 refcount_set(&cb->pending_bios, 1);
449
450 /* create and submit bios for the compressed pages */
451 bytes_left = compressed_len;
452 for (pg_index = 0; pg_index < cb->nr_pages; pg_index++) {
453 int submit = 0;
454
455 page = compressed_pages[pg_index];
456 page->mapping = inode->vfs_inode.i_mapping;
457 if (bio->bi_iter.bi_size)
458 submit = btrfs_bio_fits_in_stripe(page, PAGE_SIZE, bio,
459 0);
460
461 page->mapping = NULL;
462 if (submit || bio_add_page(bio, page, PAGE_SIZE, 0) <
463 PAGE_SIZE) {
464 /*
465 * inc the count before we submit the bio so
466 * we know the end IO handler won't happen before
467 * we inc the count. Otherwise, the cb might get
468 * freed before we're done setting it up
469 */
470 refcount_inc(&cb->pending_bios);
471 ret = btrfs_bio_wq_end_io(fs_info, bio,
472 BTRFS_WQ_ENDIO_DATA);
473 BUG_ON(ret); /* -ENOMEM */
474
475 if (!skip_sum) {
476 ret = btrfs_csum_one_bio(inode, bio, start, 1);
477 BUG_ON(ret); /* -ENOMEM */
478 }
479
480 ret = btrfs_map_bio(fs_info, bio, 0);
481 if (ret) {
482 bio->bi_status = ret;
483 bio_endio(bio);
484 }
485
486 bio = btrfs_bio_alloc(first_byte);
487 bio->bi_opf = REQ_OP_WRITE | write_flags;
488 bio->bi_private = cb;
489 bio->bi_end_io = end_compressed_bio_write;
490 if (blkcg_css)
491 bio->bi_opf |= REQ_CGROUP_PUNT;
492 bio_add_page(bio, page, PAGE_SIZE, 0);
493 }
494 if (bytes_left < PAGE_SIZE) {
495 btrfs_info(fs_info,
496 "bytes left %lu compress len %lu nr %lu",
497 bytes_left, cb->compressed_len, cb->nr_pages);
498 }
499 bytes_left -= PAGE_SIZE;
500 first_byte += PAGE_SIZE;
501 cond_resched();
502 }
503
504 ret = btrfs_bio_wq_end_io(fs_info, bio, BTRFS_WQ_ENDIO_DATA);
505 BUG_ON(ret); /* -ENOMEM */
506
507 if (!skip_sum) {
508 ret = btrfs_csum_one_bio(inode, bio, start, 1);
509 BUG_ON(ret); /* -ENOMEM */
510 }
511
512 ret = btrfs_map_bio(fs_info, bio, 0);
513 if (ret) {
514 bio->bi_status = ret;
515 bio_endio(bio);
516 }
517
518 if (blkcg_css)
519 kthread_associate_blkcg(NULL);
520
521 return 0;
522}
523
524static u64 bio_end_offset(struct bio *bio)
525{
526 struct bio_vec *last = bio_last_bvec_all(bio);
527
528 return page_offset(last->bv_page) + last->bv_len + last->bv_offset;
529}
530
531static noinline int add_ra_bio_pages(struct inode *inode,
532 u64 compressed_end,
533 struct compressed_bio *cb)
534{
535 unsigned long end_index;
536 unsigned long pg_index;
537 u64 last_offset;
538 u64 isize = i_size_read(inode);
539 int ret;
540 struct page *page;
541 unsigned long nr_pages = 0;
542 struct extent_map *em;
543 struct address_space *mapping = inode->i_mapping;
544 struct extent_map_tree *em_tree;
545 struct extent_io_tree *tree;
546 u64 end;
547 int misses = 0;
548
549 last_offset = bio_end_offset(cb->orig_bio);
550 em_tree = &BTRFS_I(inode)->extent_tree;
551 tree = &BTRFS_I(inode)->io_tree;
552
553 if (isize == 0)
554 return 0;
555
556 end_index = (i_size_read(inode) - 1) >> PAGE_SHIFT;
557
558 while (last_offset < compressed_end) {
559 pg_index = last_offset >> PAGE_SHIFT;
560
561 if (pg_index > end_index)
562 break;
563
564 page = xa_load(&mapping->i_pages, pg_index);
565 if (page && !xa_is_value(page)) {
566 misses++;
567 if (misses > 4)
568 break;
569 goto next;
570 }
571
572 page = __page_cache_alloc(mapping_gfp_constraint(mapping,
573 ~__GFP_FS));
574 if (!page)
575 break;
576
577 if (add_to_page_cache_lru(page, mapping, pg_index, GFP_NOFS)) {
578 put_page(page);
579 goto next;
580 }
581
582 end = last_offset + PAGE_SIZE - 1;
583 /*
584 * at this point, we have a locked page in the page cache
585 * for these bytes in the file. But, we have to make
586 * sure they map to this compressed extent on disk.
587 */
588 set_page_extent_mapped(page);
589 lock_extent(tree, last_offset, end);
590 read_lock(&em_tree->lock);
591 em = lookup_extent_mapping(em_tree, last_offset,
592 PAGE_SIZE);
593 read_unlock(&em_tree->lock);
594
595 if (!em || last_offset < em->start ||
596 (last_offset + PAGE_SIZE > extent_map_end(em)) ||
597 (em->block_start >> 9) != cb->orig_bio->bi_iter.bi_sector) {
598 free_extent_map(em);
599 unlock_extent(tree, last_offset, end);
600 unlock_page(page);
601 put_page(page);
602 break;
603 }
604 free_extent_map(em);
605
606 if (page->index == end_index) {
607 char *userpage;
608 size_t zero_offset = offset_in_page(isize);
609
610 if (zero_offset) {
611 int zeros;
612 zeros = PAGE_SIZE - zero_offset;
613 userpage = kmap_atomic(page);
614 memset(userpage + zero_offset, 0, zeros);
615 flush_dcache_page(page);
616 kunmap_atomic(userpage);
617 }
618 }
619
620 ret = bio_add_page(cb->orig_bio, page,
621 PAGE_SIZE, 0);
622
623 if (ret == PAGE_SIZE) {
624 nr_pages++;
625 put_page(page);
626 } else {
627 unlock_extent(tree, last_offset, end);
628 unlock_page(page);
629 put_page(page);
630 break;
631 }
632next:
633 last_offset += PAGE_SIZE;
634 }
635 return 0;
636}
637
638/*
639 * for a compressed read, the bio we get passed has all the inode pages
640 * in it. We don't actually do IO on those pages but allocate new ones
641 * to hold the compressed pages on disk.
642 *
643 * bio->bi_iter.bi_sector points to the compressed extent on disk
644 * bio->bi_io_vec points to all of the inode pages
645 *
646 * After the compressed pages are read, we copy the bytes into the
647 * bio we were passed and then call the bio end_io calls
648 */
649blk_status_t btrfs_submit_compressed_read(struct inode *inode, struct bio *bio,
650 int mirror_num, unsigned long bio_flags)
651{
652 struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
653 struct extent_map_tree *em_tree;
654 struct compressed_bio *cb;
655 unsigned long compressed_len;
656 unsigned long nr_pages;
657 unsigned long pg_index;
658 struct page *page;
659 struct bio *comp_bio;
660 u64 cur_disk_byte = (u64)bio->bi_iter.bi_sector << 9;
661 u64 em_len;
662 u64 em_start;
663 struct extent_map *em;
664 blk_status_t ret = BLK_STS_RESOURCE;
665 int faili = 0;
666 const u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
667 u8 *sums;
668
669 em_tree = &BTRFS_I(inode)->extent_tree;
670
671 /* we need the actual starting offset of this extent in the file */
672 read_lock(&em_tree->lock);
673 em = lookup_extent_mapping(em_tree,
674 page_offset(bio_first_page_all(bio)),
675 PAGE_SIZE);
676 read_unlock(&em_tree->lock);
677 if (!em)
678 return BLK_STS_IOERR;
679
680 compressed_len = em->block_len;
681 cb = kmalloc(compressed_bio_size(fs_info, compressed_len), GFP_NOFS);
682 if (!cb)
683 goto out;
684
685 refcount_set(&cb->pending_bios, 0);
686 cb->errors = 0;
687 cb->inode = inode;
688 cb->mirror_num = mirror_num;
689 sums = cb->sums;
690
691 cb->start = em->orig_start;
692 em_len = em->len;
693 em_start = em->start;
694
695 free_extent_map(em);
696 em = NULL;
697
698 cb->len = bio->bi_iter.bi_size;
699 cb->compressed_len = compressed_len;
700 cb->compress_type = extent_compress_type(bio_flags);
701 cb->orig_bio = bio;
702
703 nr_pages = DIV_ROUND_UP(compressed_len, PAGE_SIZE);
704 cb->compressed_pages = kcalloc(nr_pages, sizeof(struct page *),
705 GFP_NOFS);
706 if (!cb->compressed_pages)
707 goto fail1;
708
709 for (pg_index = 0; pg_index < nr_pages; pg_index++) {
710 cb->compressed_pages[pg_index] = alloc_page(GFP_NOFS |
711 __GFP_HIGHMEM);
712 if (!cb->compressed_pages[pg_index]) {
713 faili = pg_index - 1;
714 ret = BLK_STS_RESOURCE;
715 goto fail2;
716 }
717 }
718 faili = nr_pages - 1;
719 cb->nr_pages = nr_pages;
720
721 add_ra_bio_pages(inode, em_start + em_len, cb);
722
723 /* include any pages we added in add_ra-bio_pages */
724 cb->len = bio->bi_iter.bi_size;
725
726 comp_bio = btrfs_bio_alloc(cur_disk_byte);
727 comp_bio->bi_opf = REQ_OP_READ;
728 comp_bio->bi_private = cb;
729 comp_bio->bi_end_io = end_compressed_bio_read;
730 refcount_set(&cb->pending_bios, 1);
731
732 for (pg_index = 0; pg_index < nr_pages; pg_index++) {
733 int submit = 0;
734
735 page = cb->compressed_pages[pg_index];
736 page->mapping = inode->i_mapping;
737 page->index = em_start >> PAGE_SHIFT;
738
739 if (comp_bio->bi_iter.bi_size)
740 submit = btrfs_bio_fits_in_stripe(page, PAGE_SIZE,
741 comp_bio, 0);
742
743 page->mapping = NULL;
744 if (submit || bio_add_page(comp_bio, page, PAGE_SIZE, 0) <
745 PAGE_SIZE) {
746 unsigned int nr_sectors;
747
748 ret = btrfs_bio_wq_end_io(fs_info, comp_bio,
749 BTRFS_WQ_ENDIO_DATA);
750 BUG_ON(ret); /* -ENOMEM */
751
752 /*
753 * inc the count before we submit the bio so
754 * we know the end IO handler won't happen before
755 * we inc the count. Otherwise, the cb might get
756 * freed before we're done setting it up
757 */
758 refcount_inc(&cb->pending_bios);
759
760 if (!(BTRFS_I(inode)->flags & BTRFS_INODE_NODATASUM)) {
761 ret = btrfs_lookup_bio_sums(inode, comp_bio,
762 (u64)-1, sums);
763 BUG_ON(ret); /* -ENOMEM */
764 }
765
766 nr_sectors = DIV_ROUND_UP(comp_bio->bi_iter.bi_size,
767 fs_info->sectorsize);
768 sums += csum_size * nr_sectors;
769
770 ret = btrfs_map_bio(fs_info, comp_bio, mirror_num);
771 if (ret) {
772 comp_bio->bi_status = ret;
773 bio_endio(comp_bio);
774 }
775
776 comp_bio = btrfs_bio_alloc(cur_disk_byte);
777 comp_bio->bi_opf = REQ_OP_READ;
778 comp_bio->bi_private = cb;
779 comp_bio->bi_end_io = end_compressed_bio_read;
780
781 bio_add_page(comp_bio, page, PAGE_SIZE, 0);
782 }
783 cur_disk_byte += PAGE_SIZE;
784 }
785
786 ret = btrfs_bio_wq_end_io(fs_info, comp_bio, BTRFS_WQ_ENDIO_DATA);
787 BUG_ON(ret); /* -ENOMEM */
788
789 if (!(BTRFS_I(inode)->flags & BTRFS_INODE_NODATASUM)) {
790 ret = btrfs_lookup_bio_sums(inode, comp_bio, (u64)-1, sums);
791 BUG_ON(ret); /* -ENOMEM */
792 }
793
794 ret = btrfs_map_bio(fs_info, comp_bio, mirror_num);
795 if (ret) {
796 comp_bio->bi_status = ret;
797 bio_endio(comp_bio);
798 }
799
800 return 0;
801
802fail2:
803 while (faili >= 0) {
804 __free_page(cb->compressed_pages[faili]);
805 faili--;
806 }
807
808 kfree(cb->compressed_pages);
809fail1:
810 kfree(cb);
811out:
812 free_extent_map(em);
813 return ret;
814}
815
816/*
817 * Heuristic uses systematic sampling to collect data from the input data
818 * range, the logic can be tuned by the following constants:
819 *
820 * @SAMPLING_READ_SIZE - how many bytes will be copied from for each sample
821 * @SAMPLING_INTERVAL - range from which the sampled data can be collected
822 */
823#define SAMPLING_READ_SIZE (16)
824#define SAMPLING_INTERVAL (256)
825
826/*
827 * For statistical analysis of the input data we consider bytes that form a
828 * Galois Field of 256 objects. Each object has an attribute count, ie. how
829 * many times the object appeared in the sample.
830 */
831#define BUCKET_SIZE (256)
832
833/*
834 * The size of the sample is based on a statistical sampling rule of thumb.
835 * The common way is to perform sampling tests as long as the number of
836 * elements in each cell is at least 5.
837 *
838 * Instead of 5, we choose 32 to obtain more accurate results.
839 * If the data contain the maximum number of symbols, which is 256, we obtain a
840 * sample size bound by 8192.
841 *
842 * For a sample of at most 8KB of data per data range: 16 consecutive bytes
843 * from up to 512 locations.
844 */
845#define MAX_SAMPLE_SIZE (BTRFS_MAX_UNCOMPRESSED * \
846 SAMPLING_READ_SIZE / SAMPLING_INTERVAL)
847
848struct bucket_item {
849 u32 count;
850};
851
852struct heuristic_ws {
853 /* Partial copy of input data */
854 u8 *sample;
855 u32 sample_size;
856 /* Buckets store counters for each byte value */
857 struct bucket_item *bucket;
858 /* Sorting buffer */
859 struct bucket_item *bucket_b;
860 struct list_head list;
861};
862
863static struct workspace_manager heuristic_wsm;
864
865static void free_heuristic_ws(struct list_head *ws)
866{
867 struct heuristic_ws *workspace;
868
869 workspace = list_entry(ws, struct heuristic_ws, list);
870
871 kvfree(workspace->sample);
872 kfree(workspace->bucket);
873 kfree(workspace->bucket_b);
874 kfree(workspace);
875}
876
877static struct list_head *alloc_heuristic_ws(unsigned int level)
878{
879 struct heuristic_ws *ws;
880
881 ws = kzalloc(sizeof(*ws), GFP_KERNEL);
882 if (!ws)
883 return ERR_PTR(-ENOMEM);
884
885 ws->sample = kvmalloc(MAX_SAMPLE_SIZE, GFP_KERNEL);
886 if (!ws->sample)
887 goto fail;
888
889 ws->bucket = kcalloc(BUCKET_SIZE, sizeof(*ws->bucket), GFP_KERNEL);
890 if (!ws->bucket)
891 goto fail;
892
893 ws->bucket_b = kcalloc(BUCKET_SIZE, sizeof(*ws->bucket_b), GFP_KERNEL);
894 if (!ws->bucket_b)
895 goto fail;
896
897 INIT_LIST_HEAD(&ws->list);
898 return &ws->list;
899fail:
900 free_heuristic_ws(&ws->list);
901 return ERR_PTR(-ENOMEM);
902}
903
904const struct btrfs_compress_op btrfs_heuristic_compress = {
905 .workspace_manager = &heuristic_wsm,
906};
907
908static const struct btrfs_compress_op * const btrfs_compress_op[] = {
909 /* The heuristic is represented as compression type 0 */
910 &btrfs_heuristic_compress,
911 &btrfs_zlib_compress,
912 &btrfs_lzo_compress,
913 &btrfs_zstd_compress,
914};
915
916static struct list_head *alloc_workspace(int type, unsigned int level)
917{
918 switch (type) {
919 case BTRFS_COMPRESS_NONE: return alloc_heuristic_ws(level);
920 case BTRFS_COMPRESS_ZLIB: return zlib_alloc_workspace(level);
921 case BTRFS_COMPRESS_LZO: return lzo_alloc_workspace(level);
922 case BTRFS_COMPRESS_ZSTD: return zstd_alloc_workspace(level);
923 default:
924 /*
925 * This can't happen, the type is validated several times
926 * before we get here.
927 */
928 BUG();
929 }
930}
931
932static void free_workspace(int type, struct list_head *ws)
933{
934 switch (type) {
935 case BTRFS_COMPRESS_NONE: return free_heuristic_ws(ws);
936 case BTRFS_COMPRESS_ZLIB: return zlib_free_workspace(ws);
937 case BTRFS_COMPRESS_LZO: return lzo_free_workspace(ws);
938 case BTRFS_COMPRESS_ZSTD: return zstd_free_workspace(ws);
939 default:
940 /*
941 * This can't happen, the type is validated several times
942 * before we get here.
943 */
944 BUG();
945 }
946}
947
948static void btrfs_init_workspace_manager(int type)
949{
950 struct workspace_manager *wsm;
951 struct list_head *workspace;
952
953 wsm = btrfs_compress_op[type]->workspace_manager;
954 INIT_LIST_HEAD(&wsm->idle_ws);
955 spin_lock_init(&wsm->ws_lock);
956 atomic_set(&wsm->total_ws, 0);
957 init_waitqueue_head(&wsm->ws_wait);
958
959 /*
960 * Preallocate one workspace for each compression type so we can
961 * guarantee forward progress in the worst case
962 */
963 workspace = alloc_workspace(type, 0);
964 if (IS_ERR(workspace)) {
965 pr_warn(
966 "BTRFS: cannot preallocate compression workspace, will try later\n");
967 } else {
968 atomic_set(&wsm->total_ws, 1);
969 wsm->free_ws = 1;
970 list_add(workspace, &wsm->idle_ws);
971 }
972}
973
974static void btrfs_cleanup_workspace_manager(int type)
975{
976 struct workspace_manager *wsman;
977 struct list_head *ws;
978
979 wsman = btrfs_compress_op[type]->workspace_manager;
980 while (!list_empty(&wsman->idle_ws)) {
981 ws = wsman->idle_ws.next;
982 list_del(ws);
983 free_workspace(type, ws);
984 atomic_dec(&wsman->total_ws);
985 }
986}
987
988/*
989 * This finds an available workspace or allocates a new one.
990 * If it's not possible to allocate a new one, waits until there's one.
991 * Preallocation makes a forward progress guarantees and we do not return
992 * errors.
993 */
994struct list_head *btrfs_get_workspace(int type, unsigned int level)
995{
996 struct workspace_manager *wsm;
997 struct list_head *workspace;
998 int cpus = num_online_cpus();
999 unsigned nofs_flag;
1000 struct list_head *idle_ws;
1001 spinlock_t *ws_lock;
1002 atomic_t *total_ws;
1003 wait_queue_head_t *ws_wait;
1004 int *free_ws;
1005
1006 wsm = btrfs_compress_op[type]->workspace_manager;
1007 idle_ws = &wsm->idle_ws;
1008 ws_lock = &wsm->ws_lock;
1009 total_ws = &wsm->total_ws;
1010 ws_wait = &wsm->ws_wait;
1011 free_ws = &wsm->free_ws;
1012
1013again:
1014 spin_lock(ws_lock);
1015 if (!list_empty(idle_ws)) {
1016 workspace = idle_ws->next;
1017 list_del(workspace);
1018 (*free_ws)--;
1019 spin_unlock(ws_lock);
1020 return workspace;
1021
1022 }
1023 if (atomic_read(total_ws) > cpus) {
1024 DEFINE_WAIT(wait);
1025
1026 spin_unlock(ws_lock);
1027 prepare_to_wait(ws_wait, &wait, TASK_UNINTERRUPTIBLE);
1028 if (atomic_read(total_ws) > cpus && !*free_ws)
1029 schedule();
1030 finish_wait(ws_wait, &wait);
1031 goto again;
1032 }
1033 atomic_inc(total_ws);
1034 spin_unlock(ws_lock);
1035
1036 /*
1037 * Allocation helpers call vmalloc that can't use GFP_NOFS, so we have
1038 * to turn it off here because we might get called from the restricted
1039 * context of btrfs_compress_bio/btrfs_compress_pages
1040 */
1041 nofs_flag = memalloc_nofs_save();
1042 workspace = alloc_workspace(type, level);
1043 memalloc_nofs_restore(nofs_flag);
1044
1045 if (IS_ERR(workspace)) {
1046 atomic_dec(total_ws);
1047 wake_up(ws_wait);
1048
1049 /*
1050 * Do not return the error but go back to waiting. There's a
1051 * workspace preallocated for each type and the compression
1052 * time is bounded so we get to a workspace eventually. This
1053 * makes our caller's life easier.
1054 *
1055 * To prevent silent and low-probability deadlocks (when the
1056 * initial preallocation fails), check if there are any
1057 * workspaces at all.
1058 */
1059 if (atomic_read(total_ws) == 0) {
1060 static DEFINE_RATELIMIT_STATE(_rs,
1061 /* once per minute */ 60 * HZ,
1062 /* no burst */ 1);
1063
1064 if (__ratelimit(&_rs)) {
1065 pr_warn("BTRFS: no compression workspaces, low memory, retrying\n");
1066 }
1067 }
1068 goto again;
1069 }
1070 return workspace;
1071}
1072
1073static struct list_head *get_workspace(int type, int level)
1074{
1075 switch (type) {
1076 case BTRFS_COMPRESS_NONE: return btrfs_get_workspace(type, level);
1077 case BTRFS_COMPRESS_ZLIB: return zlib_get_workspace(level);
1078 case BTRFS_COMPRESS_LZO: return btrfs_get_workspace(type, level);
1079 case BTRFS_COMPRESS_ZSTD: return zstd_get_workspace(level);
1080 default:
1081 /*
1082 * This can't happen, the type is validated several times
1083 * before we get here.
1084 */
1085 BUG();
1086 }
1087}
1088
1089/*
1090 * put a workspace struct back on the list or free it if we have enough
1091 * idle ones sitting around
1092 */
1093void btrfs_put_workspace(int type, struct list_head *ws)
1094{
1095 struct workspace_manager *wsm;
1096 struct list_head *idle_ws;
1097 spinlock_t *ws_lock;
1098 atomic_t *total_ws;
1099 wait_queue_head_t *ws_wait;
1100 int *free_ws;
1101
1102 wsm = btrfs_compress_op[type]->workspace_manager;
1103 idle_ws = &wsm->idle_ws;
1104 ws_lock = &wsm->ws_lock;
1105 total_ws = &wsm->total_ws;
1106 ws_wait = &wsm->ws_wait;
1107 free_ws = &wsm->free_ws;
1108
1109 spin_lock(ws_lock);
1110 if (*free_ws <= num_online_cpus()) {
1111 list_add(ws, idle_ws);
1112 (*free_ws)++;
1113 spin_unlock(ws_lock);
1114 goto wake;
1115 }
1116 spin_unlock(ws_lock);
1117
1118 free_workspace(type, ws);
1119 atomic_dec(total_ws);
1120wake:
1121 cond_wake_up(ws_wait);
1122}
1123
1124static void put_workspace(int type, struct list_head *ws)
1125{
1126 switch (type) {
1127 case BTRFS_COMPRESS_NONE: return btrfs_put_workspace(type, ws);
1128 case BTRFS_COMPRESS_ZLIB: return btrfs_put_workspace(type, ws);
1129 case BTRFS_COMPRESS_LZO: return btrfs_put_workspace(type, ws);
1130 case BTRFS_COMPRESS_ZSTD: return zstd_put_workspace(ws);
1131 default:
1132 /*
1133 * This can't happen, the type is validated several times
1134 * before we get here.
1135 */
1136 BUG();
1137 }
1138}
1139
1140/*
1141 * Adjust @level according to the limits of the compression algorithm or
1142 * fallback to default
1143 */
1144static unsigned int btrfs_compress_set_level(int type, unsigned level)
1145{
1146 const struct btrfs_compress_op *ops = btrfs_compress_op[type];
1147
1148 if (level == 0)
1149 level = ops->default_level;
1150 else
1151 level = min(level, ops->max_level);
1152
1153 return level;
1154}
1155
1156/*
1157 * Given an address space and start and length, compress the bytes into @pages
1158 * that are allocated on demand.
1159 *
1160 * @type_level is encoded algorithm and level, where level 0 means whatever
1161 * default the algorithm chooses and is opaque here;
1162 * - compression algo are 0-3
1163 * - the level are bits 4-7
1164 *
1165 * @out_pages is an in/out parameter, holds maximum number of pages to allocate
1166 * and returns number of actually allocated pages
1167 *
1168 * @total_in is used to return the number of bytes actually read. It
1169 * may be smaller than the input length if we had to exit early because we
1170 * ran out of room in the pages array or because we cross the
1171 * max_out threshold.
1172 *
1173 * @total_out is an in/out parameter, must be set to the input length and will
1174 * be also used to return the total number of compressed bytes
1175 *
1176 * @max_out tells us the max number of bytes that we're allowed to
1177 * stuff into pages
1178 */
1179int btrfs_compress_pages(unsigned int type_level, struct address_space *mapping,
1180 u64 start, struct page **pages,
1181 unsigned long *out_pages,
1182 unsigned long *total_in,
1183 unsigned long *total_out)
1184{
1185 int type = btrfs_compress_type(type_level);
1186 int level = btrfs_compress_level(type_level);
1187 struct list_head *workspace;
1188 int ret;
1189
1190 level = btrfs_compress_set_level(type, level);
1191 workspace = get_workspace(type, level);
1192 ret = compression_compress_pages(type, workspace, mapping, start, pages,
1193 out_pages, total_in, total_out);
1194 put_workspace(type, workspace);
1195 return ret;
1196}
1197
1198/*
1199 * pages_in is an array of pages with compressed data.
1200 *
1201 * disk_start is the starting logical offset of this array in the file
1202 *
1203 * orig_bio contains the pages from the file that we want to decompress into
1204 *
1205 * srclen is the number of bytes in pages_in
1206 *
1207 * The basic idea is that we have a bio that was created by readpages.
1208 * The pages in the bio are for the uncompressed data, and they may not
1209 * be contiguous. They all correspond to the range of bytes covered by
1210 * the compressed extent.
1211 */
1212static int btrfs_decompress_bio(struct compressed_bio *cb)
1213{
1214 struct list_head *workspace;
1215 int ret;
1216 int type = cb->compress_type;
1217
1218 workspace = get_workspace(type, 0);
1219 ret = compression_decompress_bio(type, workspace, cb);
1220 put_workspace(type, workspace);
1221
1222 return ret;
1223}
1224
1225/*
1226 * a less complex decompression routine. Our compressed data fits in a
1227 * single page, and we want to read a single page out of it.
1228 * start_byte tells us the offset into the compressed data we're interested in
1229 */
1230int btrfs_decompress(int type, unsigned char *data_in, struct page *dest_page,
1231 unsigned long start_byte, size_t srclen, size_t destlen)
1232{
1233 struct list_head *workspace;
1234 int ret;
1235
1236 workspace = get_workspace(type, 0);
1237 ret = compression_decompress(type, workspace, data_in, dest_page,
1238 start_byte, srclen, destlen);
1239 put_workspace(type, workspace);
1240
1241 return ret;
1242}
1243
1244void __init btrfs_init_compress(void)
1245{
1246 btrfs_init_workspace_manager(BTRFS_COMPRESS_NONE);
1247 btrfs_init_workspace_manager(BTRFS_COMPRESS_ZLIB);
1248 btrfs_init_workspace_manager(BTRFS_COMPRESS_LZO);
1249 zstd_init_workspace_manager();
1250}
1251
1252void __cold btrfs_exit_compress(void)
1253{
1254 btrfs_cleanup_workspace_manager(BTRFS_COMPRESS_NONE);
1255 btrfs_cleanup_workspace_manager(BTRFS_COMPRESS_ZLIB);
1256 btrfs_cleanup_workspace_manager(BTRFS_COMPRESS_LZO);
1257 zstd_cleanup_workspace_manager();
1258}
1259
1260/*
1261 * Copy uncompressed data from working buffer to pages.
1262 *
1263 * buf_start is the byte offset we're of the start of our workspace buffer.
1264 *
1265 * total_out is the last byte of the buffer
1266 */
1267int btrfs_decompress_buf2page(const char *buf, unsigned long buf_start,
1268 unsigned long total_out, u64 disk_start,
1269 struct bio *bio)
1270{
1271 unsigned long buf_offset;
1272 unsigned long current_buf_start;
1273 unsigned long start_byte;
1274 unsigned long prev_start_byte;
1275 unsigned long working_bytes = total_out - buf_start;
1276 unsigned long bytes;
1277 char *kaddr;
1278 struct bio_vec bvec = bio_iter_iovec(bio, bio->bi_iter);
1279
1280 /*
1281 * start byte is the first byte of the page we're currently
1282 * copying into relative to the start of the compressed data.
1283 */
1284 start_byte = page_offset(bvec.bv_page) - disk_start;
1285
1286 /* we haven't yet hit data corresponding to this page */
1287 if (total_out <= start_byte)
1288 return 1;
1289
1290 /*
1291 * the start of the data we care about is offset into
1292 * the middle of our working buffer
1293 */
1294 if (total_out > start_byte && buf_start < start_byte) {
1295 buf_offset = start_byte - buf_start;
1296 working_bytes -= buf_offset;
1297 } else {
1298 buf_offset = 0;
1299 }
1300 current_buf_start = buf_start;
1301
1302 /* copy bytes from the working buffer into the pages */
1303 while (working_bytes > 0) {
1304 bytes = min_t(unsigned long, bvec.bv_len,
1305 PAGE_SIZE - (buf_offset % PAGE_SIZE));
1306 bytes = min(bytes, working_bytes);
1307
1308 kaddr = kmap_atomic(bvec.bv_page);
1309 memcpy(kaddr + bvec.bv_offset, buf + buf_offset, bytes);
1310 kunmap_atomic(kaddr);
1311 flush_dcache_page(bvec.bv_page);
1312
1313 buf_offset += bytes;
1314 working_bytes -= bytes;
1315 current_buf_start += bytes;
1316
1317 /* check if we need to pick another page */
1318 bio_advance(bio, bytes);
1319 if (!bio->bi_iter.bi_size)
1320 return 0;
1321 bvec = bio_iter_iovec(bio, bio->bi_iter);
1322 prev_start_byte = start_byte;
1323 start_byte = page_offset(bvec.bv_page) - disk_start;
1324
1325 /*
1326 * We need to make sure we're only adjusting
1327 * our offset into compression working buffer when
1328 * we're switching pages. Otherwise we can incorrectly
1329 * keep copying when we were actually done.
1330 */
1331 if (start_byte != prev_start_byte) {
1332 /*
1333 * make sure our new page is covered by this
1334 * working buffer
1335 */
1336 if (total_out <= start_byte)
1337 return 1;
1338
1339 /*
1340 * the next page in the biovec might not be adjacent
1341 * to the last page, but it might still be found
1342 * inside this working buffer. bump our offset pointer
1343 */
1344 if (total_out > start_byte &&
1345 current_buf_start < start_byte) {
1346 buf_offset = start_byte - buf_start;
1347 working_bytes = total_out - start_byte;
1348 current_buf_start = buf_start + buf_offset;
1349 }
1350 }
1351 }
1352
1353 return 1;
1354}
1355
1356/*
1357 * Shannon Entropy calculation
1358 *
1359 * Pure byte distribution analysis fails to determine compressibility of data.
1360 * Try calculating entropy to estimate the average minimum number of bits
1361 * needed to encode the sampled data.
1362 *
1363 * For convenience, return the percentage of needed bits, instead of amount of
1364 * bits directly.
1365 *
1366 * @ENTROPY_LVL_ACEPTABLE - below that threshold, sample has low byte entropy
1367 * and can be compressible with high probability
1368 *
1369 * @ENTROPY_LVL_HIGH - data are not compressible with high probability
1370 *
1371 * Use of ilog2() decreases precision, we lower the LVL to 5 to compensate.
1372 */
1373#define ENTROPY_LVL_ACEPTABLE (65)
1374#define ENTROPY_LVL_HIGH (80)
1375
1376/*
1377 * For increasead precision in shannon_entropy calculation,
1378 * let's do pow(n, M) to save more digits after comma:
1379 *
1380 * - maximum int bit length is 64
1381 * - ilog2(MAX_SAMPLE_SIZE) -> 13
1382 * - 13 * 4 = 52 < 64 -> M = 4
1383 *
1384 * So use pow(n, 4).
1385 */
1386static inline u32 ilog2_w(u64 n)
1387{
1388 return ilog2(n * n * n * n);
1389}
1390
1391static u32 shannon_entropy(struct heuristic_ws *ws)
1392{
1393 const u32 entropy_max = 8 * ilog2_w(2);
1394 u32 entropy_sum = 0;
1395 u32 p, p_base, sz_base;
1396 u32 i;
1397
1398 sz_base = ilog2_w(ws->sample_size);
1399 for (i = 0; i < BUCKET_SIZE && ws->bucket[i].count > 0; i++) {
1400 p = ws->bucket[i].count;
1401 p_base = ilog2_w(p);
1402 entropy_sum += p * (sz_base - p_base);
1403 }
1404
1405 entropy_sum /= ws->sample_size;
1406 return entropy_sum * 100 / entropy_max;
1407}
1408
1409#define RADIX_BASE 4U
1410#define COUNTERS_SIZE (1U << RADIX_BASE)
1411
1412static u8 get4bits(u64 num, int shift) {
1413 u8 low4bits;
1414
1415 num >>= shift;
1416 /* Reverse order */
1417 low4bits = (COUNTERS_SIZE - 1) - (num % COUNTERS_SIZE);
1418 return low4bits;
1419}
1420
1421/*
1422 * Use 4 bits as radix base
1423 * Use 16 u32 counters for calculating new position in buf array
1424 *
1425 * @array - array that will be sorted
1426 * @array_buf - buffer array to store sorting results
1427 * must be equal in size to @array
1428 * @num - array size
1429 */
1430static void radix_sort(struct bucket_item *array, struct bucket_item *array_buf,
1431 int num)
1432{
1433 u64 max_num;
1434 u64 buf_num;
1435 u32 counters[COUNTERS_SIZE];
1436 u32 new_addr;
1437 u32 addr;
1438 int bitlen;
1439 int shift;
1440 int i;
1441
1442 /*
1443 * Try avoid useless loop iterations for small numbers stored in big
1444 * counters. Example: 48 33 4 ... in 64bit array
1445 */
1446 max_num = array[0].count;
1447 for (i = 1; i < num; i++) {
1448 buf_num = array[i].count;
1449 if (buf_num > max_num)
1450 max_num = buf_num;
1451 }
1452
1453 buf_num = ilog2(max_num);
1454 bitlen = ALIGN(buf_num, RADIX_BASE * 2);
1455
1456 shift = 0;
1457 while (shift < bitlen) {
1458 memset(counters, 0, sizeof(counters));
1459
1460 for (i = 0; i < num; i++) {
1461 buf_num = array[i].count;
1462 addr = get4bits(buf_num, shift);
1463 counters[addr]++;
1464 }
1465
1466 for (i = 1; i < COUNTERS_SIZE; i++)
1467 counters[i] += counters[i - 1];
1468
1469 for (i = num - 1; i >= 0; i--) {
1470 buf_num = array[i].count;
1471 addr = get4bits(buf_num, shift);
1472 counters[addr]--;
1473 new_addr = counters[addr];
1474 array_buf[new_addr] = array[i];
1475 }
1476
1477 shift += RADIX_BASE;
1478
1479 /*
1480 * Normal radix expects to move data from a temporary array, to
1481 * the main one. But that requires some CPU time. Avoid that
1482 * by doing another sort iteration to original array instead of
1483 * memcpy()
1484 */
1485 memset(counters, 0, sizeof(counters));
1486
1487 for (i = 0; i < num; i ++) {
1488 buf_num = array_buf[i].count;
1489 addr = get4bits(buf_num, shift);
1490 counters[addr]++;
1491 }
1492
1493 for (i = 1; i < COUNTERS_SIZE; i++)
1494 counters[i] += counters[i - 1];
1495
1496 for (i = num - 1; i >= 0; i--) {
1497 buf_num = array_buf[i].count;
1498 addr = get4bits(buf_num, shift);
1499 counters[addr]--;
1500 new_addr = counters[addr];
1501 array[new_addr] = array_buf[i];
1502 }
1503
1504 shift += RADIX_BASE;
1505 }
1506}
1507
1508/*
1509 * Size of the core byte set - how many bytes cover 90% of the sample
1510 *
1511 * There are several types of structured binary data that use nearly all byte
1512 * values. The distribution can be uniform and counts in all buckets will be
1513 * nearly the same (eg. encrypted data). Unlikely to be compressible.
1514 *
1515 * Other possibility is normal (Gaussian) distribution, where the data could
1516 * be potentially compressible, but we have to take a few more steps to decide
1517 * how much.
1518 *
1519 * @BYTE_CORE_SET_LOW - main part of byte values repeated frequently,
1520 * compression algo can easy fix that
1521 * @BYTE_CORE_SET_HIGH - data have uniform distribution and with high
1522 * probability is not compressible
1523 */
1524#define BYTE_CORE_SET_LOW (64)
1525#define BYTE_CORE_SET_HIGH (200)
1526
1527static int byte_core_set_size(struct heuristic_ws *ws)
1528{
1529 u32 i;
1530 u32 coreset_sum = 0;
1531 const u32 core_set_threshold = ws->sample_size * 90 / 100;
1532 struct bucket_item *bucket = ws->bucket;
1533
1534 /* Sort in reverse order */
1535 radix_sort(ws->bucket, ws->bucket_b, BUCKET_SIZE);
1536
1537 for (i = 0; i < BYTE_CORE_SET_LOW; i++)
1538 coreset_sum += bucket[i].count;
1539
1540 if (coreset_sum > core_set_threshold)
1541 return i;
1542
1543 for (; i < BYTE_CORE_SET_HIGH && bucket[i].count > 0; i++) {
1544 coreset_sum += bucket[i].count;
1545 if (coreset_sum > core_set_threshold)
1546 break;
1547 }
1548
1549 return i;
1550}
1551
1552/*
1553 * Count byte values in buckets.
1554 * This heuristic can detect textual data (configs, xml, json, html, etc).
1555 * Because in most text-like data byte set is restricted to limited number of
1556 * possible characters, and that restriction in most cases makes data easy to
1557 * compress.
1558 *
1559 * @BYTE_SET_THRESHOLD - consider all data within this byte set size:
1560 * less - compressible
1561 * more - need additional analysis
1562 */
1563#define BYTE_SET_THRESHOLD (64)
1564
1565static u32 byte_set_size(const struct heuristic_ws *ws)
1566{
1567 u32 i;
1568 u32 byte_set_size = 0;
1569
1570 for (i = 0; i < BYTE_SET_THRESHOLD; i++) {
1571 if (ws->bucket[i].count > 0)
1572 byte_set_size++;
1573 }
1574
1575 /*
1576 * Continue collecting count of byte values in buckets. If the byte
1577 * set size is bigger then the threshold, it's pointless to continue,
1578 * the detection technique would fail for this type of data.
1579 */
1580 for (; i < BUCKET_SIZE; i++) {
1581 if (ws->bucket[i].count > 0) {
1582 byte_set_size++;
1583 if (byte_set_size > BYTE_SET_THRESHOLD)
1584 return byte_set_size;
1585 }
1586 }
1587
1588 return byte_set_size;
1589}
1590
1591static bool sample_repeated_patterns(struct heuristic_ws *ws)
1592{
1593 const u32 half_of_sample = ws->sample_size / 2;
1594 const u8 *data = ws->sample;
1595
1596 return memcmp(&data[0], &data[half_of_sample], half_of_sample) == 0;
1597}
1598
1599static void heuristic_collect_sample(struct inode *inode, u64 start, u64 end,
1600 struct heuristic_ws *ws)
1601{
1602 struct page *page;
1603 u64 index, index_end;
1604 u32 i, curr_sample_pos;
1605 u8 *in_data;
1606
1607 /*
1608 * Compression handles the input data by chunks of 128KiB
1609 * (defined by BTRFS_MAX_UNCOMPRESSED)
1610 *
1611 * We do the same for the heuristic and loop over the whole range.
1612 *
1613 * MAX_SAMPLE_SIZE - calculated under assumption that heuristic will
1614 * process no more than BTRFS_MAX_UNCOMPRESSED at a time.
1615 */
1616 if (end - start > BTRFS_MAX_UNCOMPRESSED)
1617 end = start + BTRFS_MAX_UNCOMPRESSED;
1618
1619 index = start >> PAGE_SHIFT;
1620 index_end = end >> PAGE_SHIFT;
1621
1622 /* Don't miss unaligned end */
1623 if (!IS_ALIGNED(end, PAGE_SIZE))
1624 index_end++;
1625
1626 curr_sample_pos = 0;
1627 while (index < index_end) {
1628 page = find_get_page(inode->i_mapping, index);
1629 in_data = kmap(page);
1630 /* Handle case where the start is not aligned to PAGE_SIZE */
1631 i = start % PAGE_SIZE;
1632 while (i < PAGE_SIZE - SAMPLING_READ_SIZE) {
1633 /* Don't sample any garbage from the last page */
1634 if (start > end - SAMPLING_READ_SIZE)
1635 break;
1636 memcpy(&ws->sample[curr_sample_pos], &in_data[i],
1637 SAMPLING_READ_SIZE);
1638 i += SAMPLING_INTERVAL;
1639 start += SAMPLING_INTERVAL;
1640 curr_sample_pos += SAMPLING_READ_SIZE;
1641 }
1642 kunmap(page);
1643 put_page(page);
1644
1645 index++;
1646 }
1647
1648 ws->sample_size = curr_sample_pos;
1649}
1650
1651/*
1652 * Compression heuristic.
1653 *
1654 * For now is's a naive and optimistic 'return true', we'll extend the logic to
1655 * quickly (compared to direct compression) detect data characteristics
1656 * (compressible/uncompressible) to avoid wasting CPU time on uncompressible
1657 * data.
1658 *
1659 * The following types of analysis can be performed:
1660 * - detect mostly zero data
1661 * - detect data with low "byte set" size (text, etc)
1662 * - detect data with low/high "core byte" set
1663 *
1664 * Return non-zero if the compression should be done, 0 otherwise.
1665 */
1666int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end)
1667{
1668 struct list_head *ws_list = get_workspace(0, 0);
1669 struct heuristic_ws *ws;
1670 u32 i;
1671 u8 byte;
1672 int ret = 0;
1673
1674 ws = list_entry(ws_list, struct heuristic_ws, list);
1675
1676 heuristic_collect_sample(inode, start, end, ws);
1677
1678 if (sample_repeated_patterns(ws)) {
1679 ret = 1;
1680 goto out;
1681 }
1682
1683 memset(ws->bucket, 0, sizeof(*ws->bucket)*BUCKET_SIZE);
1684
1685 for (i = 0; i < ws->sample_size; i++) {
1686 byte = ws->sample[i];
1687 ws->bucket[byte].count++;
1688 }
1689
1690 i = byte_set_size(ws);
1691 if (i < BYTE_SET_THRESHOLD) {
1692 ret = 2;
1693 goto out;
1694 }
1695
1696 i = byte_core_set_size(ws);
1697 if (i <= BYTE_CORE_SET_LOW) {
1698 ret = 3;
1699 goto out;
1700 }
1701
1702 if (i >= BYTE_CORE_SET_HIGH) {
1703 ret = 0;
1704 goto out;
1705 }
1706
1707 i = shannon_entropy(ws);
1708 if (i <= ENTROPY_LVL_ACEPTABLE) {
1709 ret = 4;
1710 goto out;
1711 }
1712
1713 /*
1714 * For the levels below ENTROPY_LVL_HIGH, additional analysis would be
1715 * needed to give green light to compression.
1716 *
1717 * For now just assume that compression at that level is not worth the
1718 * resources because:
1719 *
1720 * 1. it is possible to defrag the data later
1721 *
1722 * 2. the data would turn out to be hardly compressible, eg. 150 byte
1723 * values, every bucket has counter at level ~54. The heuristic would
1724 * be confused. This can happen when data have some internal repeated
1725 * patterns like "abbacbbc...". This can be detected by analyzing
1726 * pairs of bytes, which is too costly.
1727 */
1728 if (i < ENTROPY_LVL_HIGH) {
1729 ret = 5;
1730 goto out;
1731 } else {
1732 ret = 0;
1733 goto out;
1734 }
1735
1736out:
1737 put_workspace(0, ws_list);
1738 return ret;
1739}
1740
1741/*
1742 * Convert the compression suffix (eg. after "zlib" starting with ":") to
1743 * level, unrecognized string will set the default level
1744 */
1745unsigned int btrfs_compress_str2level(unsigned int type, const char *str)
1746{
1747 unsigned int level = 0;
1748 int ret;
1749
1750 if (!type)
1751 return 0;
1752
1753 if (str[0] == ':') {
1754 ret = kstrtouint(str + 1, 10, &level);
1755 if (ret)
1756 level = 0;
1757 }
1758
1759 level = btrfs_compress_set_level(type, level);
1760
1761 return level;
1762}
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/bio.h>
8#include <linux/file.h>
9#include <linux/fs.h>
10#include <linux/pagemap.h>
11#include <linux/pagevec.h>
12#include <linux/highmem.h>
13#include <linux/kthread.h>
14#include <linux/time.h>
15#include <linux/init.h>
16#include <linux/string.h>
17#include <linux/backing-dev.h>
18#include <linux/writeback.h>
19#include <linux/psi.h>
20#include <linux/slab.h>
21#include <linux/sched/mm.h>
22#include <linux/log2.h>
23#include <linux/shrinker.h>
24#include <crypto/hash.h>
25#include "misc.h"
26#include "ctree.h"
27#include "fs.h"
28#include "btrfs_inode.h"
29#include "bio.h"
30#include "ordered-data.h"
31#include "compression.h"
32#include "extent_io.h"
33#include "extent_map.h"
34#include "subpage.h"
35#include "messages.h"
36#include "super.h"
37
38static struct bio_set btrfs_compressed_bioset;
39
40static const char* const btrfs_compress_types[] = { "", "zlib", "lzo", "zstd" };
41
42const char* btrfs_compress_type2str(enum btrfs_compression_type type)
43{
44 switch (type) {
45 case BTRFS_COMPRESS_ZLIB:
46 case BTRFS_COMPRESS_LZO:
47 case BTRFS_COMPRESS_ZSTD:
48 case BTRFS_COMPRESS_NONE:
49 return btrfs_compress_types[type];
50 default:
51 break;
52 }
53
54 return NULL;
55}
56
57static inline struct compressed_bio *to_compressed_bio(struct btrfs_bio *bbio)
58{
59 return container_of(bbio, struct compressed_bio, bbio);
60}
61
62static struct compressed_bio *alloc_compressed_bio(struct btrfs_inode *inode,
63 u64 start, blk_opf_t op,
64 btrfs_bio_end_io_t end_io)
65{
66 struct btrfs_bio *bbio;
67
68 bbio = btrfs_bio(bio_alloc_bioset(NULL, BTRFS_MAX_COMPRESSED_PAGES, op,
69 GFP_NOFS, &btrfs_compressed_bioset));
70 btrfs_bio_init(bbio, inode->root->fs_info, end_io, NULL);
71 bbio->inode = inode;
72 bbio->file_offset = start;
73 return to_compressed_bio(bbio);
74}
75
76bool btrfs_compress_is_valid_type(const char *str, size_t len)
77{
78 int i;
79
80 for (i = 1; i < ARRAY_SIZE(btrfs_compress_types); i++) {
81 size_t comp_len = strlen(btrfs_compress_types[i]);
82
83 if (len < comp_len)
84 continue;
85
86 if (!strncmp(btrfs_compress_types[i], str, comp_len))
87 return true;
88 }
89 return false;
90}
91
92static int compression_compress_pages(int type, struct list_head *ws,
93 struct address_space *mapping, u64 start, struct page **pages,
94 unsigned long *out_pages, unsigned long *total_in,
95 unsigned long *total_out)
96{
97 switch (type) {
98 case BTRFS_COMPRESS_ZLIB:
99 return zlib_compress_pages(ws, mapping, start, pages,
100 out_pages, total_in, total_out);
101 case BTRFS_COMPRESS_LZO:
102 return lzo_compress_pages(ws, mapping, start, pages,
103 out_pages, total_in, total_out);
104 case BTRFS_COMPRESS_ZSTD:
105 return zstd_compress_pages(ws, mapping, start, pages,
106 out_pages, total_in, total_out);
107 case BTRFS_COMPRESS_NONE:
108 default:
109 /*
110 * This can happen when compression races with remount setting
111 * it to 'no compress', while caller doesn't call
112 * inode_need_compress() to check if we really need to
113 * compress.
114 *
115 * Not a big deal, just need to inform caller that we
116 * haven't allocated any pages yet.
117 */
118 *out_pages = 0;
119 return -E2BIG;
120 }
121}
122
123static int compression_decompress_bio(struct list_head *ws,
124 struct compressed_bio *cb)
125{
126 switch (cb->compress_type) {
127 case BTRFS_COMPRESS_ZLIB: return zlib_decompress_bio(ws, cb);
128 case BTRFS_COMPRESS_LZO: return lzo_decompress_bio(ws, cb);
129 case BTRFS_COMPRESS_ZSTD: return zstd_decompress_bio(ws, cb);
130 case BTRFS_COMPRESS_NONE:
131 default:
132 /*
133 * This can't happen, the type is validated several times
134 * before we get here.
135 */
136 BUG();
137 }
138}
139
140static int compression_decompress(int type, struct list_head *ws,
141 const u8 *data_in, struct page *dest_page,
142 unsigned long dest_pgoff, size_t srclen, size_t destlen)
143{
144 switch (type) {
145 case BTRFS_COMPRESS_ZLIB: return zlib_decompress(ws, data_in, dest_page,
146 dest_pgoff, srclen, destlen);
147 case BTRFS_COMPRESS_LZO: return lzo_decompress(ws, data_in, dest_page,
148 dest_pgoff, srclen, destlen);
149 case BTRFS_COMPRESS_ZSTD: return zstd_decompress(ws, data_in, dest_page,
150 dest_pgoff, srclen, destlen);
151 case BTRFS_COMPRESS_NONE:
152 default:
153 /*
154 * This can't happen, the type is validated several times
155 * before we get here.
156 */
157 BUG();
158 }
159}
160
161static void btrfs_free_compressed_pages(struct compressed_bio *cb)
162{
163 for (unsigned int i = 0; i < cb->nr_pages; i++)
164 btrfs_free_compr_page(cb->compressed_pages[i]);
165 kfree(cb->compressed_pages);
166}
167
168static int btrfs_decompress_bio(struct compressed_bio *cb);
169
170/*
171 * Global cache of last unused pages for compression/decompression.
172 */
173static struct btrfs_compr_pool {
174 struct shrinker *shrinker;
175 spinlock_t lock;
176 struct list_head list;
177 int count;
178 int thresh;
179} compr_pool;
180
181static unsigned long btrfs_compr_pool_count(struct shrinker *sh, struct shrink_control *sc)
182{
183 int ret;
184
185 /*
186 * We must not read the values more than once if 'ret' gets expanded in
187 * the return statement so we don't accidentally return a negative
188 * number, even if the first condition finds it positive.
189 */
190 ret = READ_ONCE(compr_pool.count) - READ_ONCE(compr_pool.thresh);
191
192 return ret > 0 ? ret : 0;
193}
194
195static unsigned long btrfs_compr_pool_scan(struct shrinker *sh, struct shrink_control *sc)
196{
197 struct list_head remove;
198 struct list_head *tmp, *next;
199 int freed;
200
201 if (compr_pool.count == 0)
202 return SHRINK_STOP;
203
204 INIT_LIST_HEAD(&remove);
205
206 /* For now, just simply drain the whole list. */
207 spin_lock(&compr_pool.lock);
208 list_splice_init(&compr_pool.list, &remove);
209 freed = compr_pool.count;
210 compr_pool.count = 0;
211 spin_unlock(&compr_pool.lock);
212
213 list_for_each_safe(tmp, next, &remove) {
214 struct page *page = list_entry(tmp, struct page, lru);
215
216 ASSERT(page_ref_count(page) == 1);
217 put_page(page);
218 }
219
220 return freed;
221}
222
223/*
224 * Common wrappers for page allocation from compression wrappers
225 */
226struct page *btrfs_alloc_compr_page(void)
227{
228 struct page *page = NULL;
229
230 spin_lock(&compr_pool.lock);
231 if (compr_pool.count > 0) {
232 page = list_first_entry(&compr_pool.list, struct page, lru);
233 list_del_init(&page->lru);
234 compr_pool.count--;
235 }
236 spin_unlock(&compr_pool.lock);
237
238 if (page)
239 return page;
240
241 return alloc_page(GFP_NOFS);
242}
243
244void btrfs_free_compr_page(struct page *page)
245{
246 bool do_free = false;
247
248 spin_lock(&compr_pool.lock);
249 if (compr_pool.count > compr_pool.thresh) {
250 do_free = true;
251 } else {
252 list_add(&page->lru, &compr_pool.list);
253 compr_pool.count++;
254 }
255 spin_unlock(&compr_pool.lock);
256
257 if (!do_free)
258 return;
259
260 ASSERT(page_ref_count(page) == 1);
261 put_page(page);
262}
263
264static void end_bbio_comprssed_read(struct btrfs_bio *bbio)
265{
266 struct compressed_bio *cb = to_compressed_bio(bbio);
267 blk_status_t status = bbio->bio.bi_status;
268
269 if (!status)
270 status = errno_to_blk_status(btrfs_decompress_bio(cb));
271
272 btrfs_free_compressed_pages(cb);
273 btrfs_bio_end_io(cb->orig_bbio, status);
274 bio_put(&bbio->bio);
275}
276
277/*
278 * Clear the writeback bits on all of the file
279 * pages for a compressed write
280 */
281static noinline void end_compressed_writeback(const struct compressed_bio *cb)
282{
283 struct inode *inode = &cb->bbio.inode->vfs_inode;
284 struct btrfs_fs_info *fs_info = inode_to_fs_info(inode);
285 unsigned long index = cb->start >> PAGE_SHIFT;
286 unsigned long end_index = (cb->start + cb->len - 1) >> PAGE_SHIFT;
287 struct folio_batch fbatch;
288 const int error = blk_status_to_errno(cb->bbio.bio.bi_status);
289 int i;
290 int ret;
291
292 if (error)
293 mapping_set_error(inode->i_mapping, error);
294
295 folio_batch_init(&fbatch);
296 while (index <= end_index) {
297 ret = filemap_get_folios(inode->i_mapping, &index, end_index,
298 &fbatch);
299
300 if (ret == 0)
301 return;
302
303 for (i = 0; i < ret; i++) {
304 struct folio *folio = fbatch.folios[i];
305
306 btrfs_folio_clamp_clear_writeback(fs_info, folio,
307 cb->start, cb->len);
308 }
309 folio_batch_release(&fbatch);
310 }
311 /* the inode may be gone now */
312}
313
314static void btrfs_finish_compressed_write_work(struct work_struct *work)
315{
316 struct compressed_bio *cb =
317 container_of(work, struct compressed_bio, write_end_work);
318
319 btrfs_finish_ordered_extent(cb->bbio.ordered, NULL, cb->start, cb->len,
320 cb->bbio.bio.bi_status == BLK_STS_OK);
321
322 if (cb->writeback)
323 end_compressed_writeback(cb);
324 /* Note, our inode could be gone now */
325
326 btrfs_free_compressed_pages(cb);
327 bio_put(&cb->bbio.bio);
328}
329
330/*
331 * Do the cleanup once all the compressed pages hit the disk. This will clear
332 * writeback on the file pages and free the compressed pages.
333 *
334 * This also calls the writeback end hooks for the file pages so that metadata
335 * and checksums can be updated in the file.
336 */
337static void end_bbio_comprssed_write(struct btrfs_bio *bbio)
338{
339 struct compressed_bio *cb = to_compressed_bio(bbio);
340 struct btrfs_fs_info *fs_info = bbio->inode->root->fs_info;
341
342 queue_work(fs_info->compressed_write_workers, &cb->write_end_work);
343}
344
345static void btrfs_add_compressed_bio_pages(struct compressed_bio *cb)
346{
347 struct bio *bio = &cb->bbio.bio;
348 u32 offset = 0;
349
350 while (offset < cb->compressed_len) {
351 u32 len = min_t(u32, cb->compressed_len - offset, PAGE_SIZE);
352
353 /* Maximum compressed extent is smaller than bio size limit. */
354 __bio_add_page(bio, cb->compressed_pages[offset >> PAGE_SHIFT],
355 len, 0);
356 offset += len;
357 }
358}
359
360/*
361 * worker function to build and submit bios for previously compressed pages.
362 * The corresponding pages in the inode should be marked for writeback
363 * and the compressed pages should have a reference on them for dropping
364 * when the IO is complete.
365 *
366 * This also checksums the file bytes and gets things ready for
367 * the end io hooks.
368 */
369void btrfs_submit_compressed_write(struct btrfs_ordered_extent *ordered,
370 struct page **compressed_pages,
371 unsigned int nr_pages,
372 blk_opf_t write_flags,
373 bool writeback)
374{
375 struct btrfs_inode *inode = BTRFS_I(ordered->inode);
376 struct btrfs_fs_info *fs_info = inode->root->fs_info;
377 struct compressed_bio *cb;
378
379 ASSERT(IS_ALIGNED(ordered->file_offset, fs_info->sectorsize));
380 ASSERT(IS_ALIGNED(ordered->num_bytes, fs_info->sectorsize));
381
382 cb = alloc_compressed_bio(inode, ordered->file_offset,
383 REQ_OP_WRITE | write_flags,
384 end_bbio_comprssed_write);
385 cb->start = ordered->file_offset;
386 cb->len = ordered->num_bytes;
387 cb->compressed_pages = compressed_pages;
388 cb->compressed_len = ordered->disk_num_bytes;
389 cb->writeback = writeback;
390 INIT_WORK(&cb->write_end_work, btrfs_finish_compressed_write_work);
391 cb->nr_pages = nr_pages;
392 cb->bbio.bio.bi_iter.bi_sector = ordered->disk_bytenr >> SECTOR_SHIFT;
393 cb->bbio.ordered = ordered;
394 btrfs_add_compressed_bio_pages(cb);
395
396 btrfs_submit_bio(&cb->bbio, 0);
397}
398
399/*
400 * Add extra pages in the same compressed file extent so that we don't need to
401 * re-read the same extent again and again.
402 *
403 * NOTE: this won't work well for subpage, as for subpage read, we lock the
404 * full page then submit bio for each compressed/regular extents.
405 *
406 * This means, if we have several sectors in the same page points to the same
407 * on-disk compressed data, we will re-read the same extent many times and
408 * this function can only help for the next page.
409 */
410static noinline int add_ra_bio_pages(struct inode *inode,
411 u64 compressed_end,
412 struct compressed_bio *cb,
413 int *memstall, unsigned long *pflags)
414{
415 struct btrfs_fs_info *fs_info = inode_to_fs_info(inode);
416 unsigned long end_index;
417 struct bio *orig_bio = &cb->orig_bbio->bio;
418 u64 cur = cb->orig_bbio->file_offset + orig_bio->bi_iter.bi_size;
419 u64 isize = i_size_read(inode);
420 int ret;
421 struct page *page;
422 struct extent_map *em;
423 struct address_space *mapping = inode->i_mapping;
424 struct extent_map_tree *em_tree;
425 struct extent_io_tree *tree;
426 int sectors_missed = 0;
427
428 em_tree = &BTRFS_I(inode)->extent_tree;
429 tree = &BTRFS_I(inode)->io_tree;
430
431 if (isize == 0)
432 return 0;
433
434 /*
435 * For current subpage support, we only support 64K page size,
436 * which means maximum compressed extent size (128K) is just 2x page
437 * size.
438 * This makes readahead less effective, so here disable readahead for
439 * subpage for now, until full compressed write is supported.
440 */
441 if (fs_info->sectorsize < PAGE_SIZE)
442 return 0;
443
444 end_index = (i_size_read(inode) - 1) >> PAGE_SHIFT;
445
446 while (cur < compressed_end) {
447 u64 page_end;
448 u64 pg_index = cur >> PAGE_SHIFT;
449 u32 add_size;
450
451 if (pg_index > end_index)
452 break;
453
454 page = xa_load(&mapping->i_pages, pg_index);
455 if (page && !xa_is_value(page)) {
456 sectors_missed += (PAGE_SIZE - offset_in_page(cur)) >>
457 fs_info->sectorsize_bits;
458
459 /* Beyond threshold, no need to continue */
460 if (sectors_missed > 4)
461 break;
462
463 /*
464 * Jump to next page start as we already have page for
465 * current offset.
466 */
467 cur = (pg_index << PAGE_SHIFT) + PAGE_SIZE;
468 continue;
469 }
470
471 page = __page_cache_alloc(mapping_gfp_constraint(mapping,
472 ~__GFP_FS));
473 if (!page)
474 break;
475
476 if (add_to_page_cache_lru(page, mapping, pg_index, GFP_NOFS)) {
477 put_page(page);
478 /* There is already a page, skip to page end */
479 cur = (pg_index << PAGE_SHIFT) + PAGE_SIZE;
480 continue;
481 }
482
483 if (!*memstall && PageWorkingset(page)) {
484 psi_memstall_enter(pflags);
485 *memstall = 1;
486 }
487
488 ret = set_page_extent_mapped(page);
489 if (ret < 0) {
490 unlock_page(page);
491 put_page(page);
492 break;
493 }
494
495 page_end = (pg_index << PAGE_SHIFT) + PAGE_SIZE - 1;
496 lock_extent(tree, cur, page_end, NULL);
497 read_lock(&em_tree->lock);
498 em = lookup_extent_mapping(em_tree, cur, page_end + 1 - cur);
499 read_unlock(&em_tree->lock);
500
501 /*
502 * At this point, we have a locked page in the page cache for
503 * these bytes in the file. But, we have to make sure they map
504 * to this compressed extent on disk.
505 */
506 if (!em || cur < em->start ||
507 (cur + fs_info->sectorsize > extent_map_end(em)) ||
508 (em->block_start >> SECTOR_SHIFT) != orig_bio->bi_iter.bi_sector) {
509 free_extent_map(em);
510 unlock_extent(tree, cur, page_end, NULL);
511 unlock_page(page);
512 put_page(page);
513 break;
514 }
515 free_extent_map(em);
516
517 if (page->index == end_index) {
518 size_t zero_offset = offset_in_page(isize);
519
520 if (zero_offset) {
521 int zeros;
522 zeros = PAGE_SIZE - zero_offset;
523 memzero_page(page, zero_offset, zeros);
524 }
525 }
526
527 add_size = min(em->start + em->len, page_end + 1) - cur;
528 ret = bio_add_page(orig_bio, page, add_size, offset_in_page(cur));
529 if (ret != add_size) {
530 unlock_extent(tree, cur, page_end, NULL);
531 unlock_page(page);
532 put_page(page);
533 break;
534 }
535 /*
536 * If it's subpage, we also need to increase its
537 * subpage::readers number, as at endio we will decrease
538 * subpage::readers and to unlock the page.
539 */
540 if (fs_info->sectorsize < PAGE_SIZE)
541 btrfs_subpage_start_reader(fs_info, page_folio(page),
542 cur, add_size);
543 put_page(page);
544 cur += add_size;
545 }
546 return 0;
547}
548
549/*
550 * for a compressed read, the bio we get passed has all the inode pages
551 * in it. We don't actually do IO on those pages but allocate new ones
552 * to hold the compressed pages on disk.
553 *
554 * bio->bi_iter.bi_sector points to the compressed extent on disk
555 * bio->bi_io_vec points to all of the inode pages
556 *
557 * After the compressed pages are read, we copy the bytes into the
558 * bio we were passed and then call the bio end_io calls
559 */
560void btrfs_submit_compressed_read(struct btrfs_bio *bbio)
561{
562 struct btrfs_inode *inode = bbio->inode;
563 struct btrfs_fs_info *fs_info = inode->root->fs_info;
564 struct extent_map_tree *em_tree = &inode->extent_tree;
565 struct compressed_bio *cb;
566 unsigned int compressed_len;
567 u64 file_offset = bbio->file_offset;
568 u64 em_len;
569 u64 em_start;
570 struct extent_map *em;
571 unsigned long pflags;
572 int memstall = 0;
573 blk_status_t ret;
574 int ret2;
575
576 /* we need the actual starting offset of this extent in the file */
577 read_lock(&em_tree->lock);
578 em = lookup_extent_mapping(em_tree, file_offset, fs_info->sectorsize);
579 read_unlock(&em_tree->lock);
580 if (!em) {
581 ret = BLK_STS_IOERR;
582 goto out;
583 }
584
585 ASSERT(extent_map_is_compressed(em));
586 compressed_len = em->block_len;
587
588 cb = alloc_compressed_bio(inode, file_offset, REQ_OP_READ,
589 end_bbio_comprssed_read);
590
591 cb->start = em->orig_start;
592 em_len = em->len;
593 em_start = em->start;
594
595 cb->len = bbio->bio.bi_iter.bi_size;
596 cb->compressed_len = compressed_len;
597 cb->compress_type = extent_map_compression(em);
598 cb->orig_bbio = bbio;
599
600 free_extent_map(em);
601
602 cb->nr_pages = DIV_ROUND_UP(compressed_len, PAGE_SIZE);
603 cb->compressed_pages = kcalloc(cb->nr_pages, sizeof(struct page *), GFP_NOFS);
604 if (!cb->compressed_pages) {
605 ret = BLK_STS_RESOURCE;
606 goto out_free_bio;
607 }
608
609 ret2 = btrfs_alloc_page_array(cb->nr_pages, cb->compressed_pages, 0);
610 if (ret2) {
611 ret = BLK_STS_RESOURCE;
612 goto out_free_compressed_pages;
613 }
614
615 add_ra_bio_pages(&inode->vfs_inode, em_start + em_len, cb, &memstall,
616 &pflags);
617
618 /* include any pages we added in add_ra-bio_pages */
619 cb->len = bbio->bio.bi_iter.bi_size;
620 cb->bbio.bio.bi_iter.bi_sector = bbio->bio.bi_iter.bi_sector;
621 btrfs_add_compressed_bio_pages(cb);
622
623 if (memstall)
624 psi_memstall_leave(&pflags);
625
626 btrfs_submit_bio(&cb->bbio, 0);
627 return;
628
629out_free_compressed_pages:
630 kfree(cb->compressed_pages);
631out_free_bio:
632 bio_put(&cb->bbio.bio);
633out:
634 btrfs_bio_end_io(bbio, ret);
635}
636
637/*
638 * Heuristic uses systematic sampling to collect data from the input data
639 * range, the logic can be tuned by the following constants:
640 *
641 * @SAMPLING_READ_SIZE - how many bytes will be copied from for each sample
642 * @SAMPLING_INTERVAL - range from which the sampled data can be collected
643 */
644#define SAMPLING_READ_SIZE (16)
645#define SAMPLING_INTERVAL (256)
646
647/*
648 * For statistical analysis of the input data we consider bytes that form a
649 * Galois Field of 256 objects. Each object has an attribute count, ie. how
650 * many times the object appeared in the sample.
651 */
652#define BUCKET_SIZE (256)
653
654/*
655 * The size of the sample is based on a statistical sampling rule of thumb.
656 * The common way is to perform sampling tests as long as the number of
657 * elements in each cell is at least 5.
658 *
659 * Instead of 5, we choose 32 to obtain more accurate results.
660 * If the data contain the maximum number of symbols, which is 256, we obtain a
661 * sample size bound by 8192.
662 *
663 * For a sample of at most 8KB of data per data range: 16 consecutive bytes
664 * from up to 512 locations.
665 */
666#define MAX_SAMPLE_SIZE (BTRFS_MAX_UNCOMPRESSED * \
667 SAMPLING_READ_SIZE / SAMPLING_INTERVAL)
668
669struct bucket_item {
670 u32 count;
671};
672
673struct heuristic_ws {
674 /* Partial copy of input data */
675 u8 *sample;
676 u32 sample_size;
677 /* Buckets store counters for each byte value */
678 struct bucket_item *bucket;
679 /* Sorting buffer */
680 struct bucket_item *bucket_b;
681 struct list_head list;
682};
683
684static struct workspace_manager heuristic_wsm;
685
686static void free_heuristic_ws(struct list_head *ws)
687{
688 struct heuristic_ws *workspace;
689
690 workspace = list_entry(ws, struct heuristic_ws, list);
691
692 kvfree(workspace->sample);
693 kfree(workspace->bucket);
694 kfree(workspace->bucket_b);
695 kfree(workspace);
696}
697
698static struct list_head *alloc_heuristic_ws(unsigned int level)
699{
700 struct heuristic_ws *ws;
701
702 ws = kzalloc(sizeof(*ws), GFP_KERNEL);
703 if (!ws)
704 return ERR_PTR(-ENOMEM);
705
706 ws->sample = kvmalloc(MAX_SAMPLE_SIZE, GFP_KERNEL);
707 if (!ws->sample)
708 goto fail;
709
710 ws->bucket = kcalloc(BUCKET_SIZE, sizeof(*ws->bucket), GFP_KERNEL);
711 if (!ws->bucket)
712 goto fail;
713
714 ws->bucket_b = kcalloc(BUCKET_SIZE, sizeof(*ws->bucket_b), GFP_KERNEL);
715 if (!ws->bucket_b)
716 goto fail;
717
718 INIT_LIST_HEAD(&ws->list);
719 return &ws->list;
720fail:
721 free_heuristic_ws(&ws->list);
722 return ERR_PTR(-ENOMEM);
723}
724
725const struct btrfs_compress_op btrfs_heuristic_compress = {
726 .workspace_manager = &heuristic_wsm,
727};
728
729static const struct btrfs_compress_op * const btrfs_compress_op[] = {
730 /* The heuristic is represented as compression type 0 */
731 &btrfs_heuristic_compress,
732 &btrfs_zlib_compress,
733 &btrfs_lzo_compress,
734 &btrfs_zstd_compress,
735};
736
737static struct list_head *alloc_workspace(int type, unsigned int level)
738{
739 switch (type) {
740 case BTRFS_COMPRESS_NONE: return alloc_heuristic_ws(level);
741 case BTRFS_COMPRESS_ZLIB: return zlib_alloc_workspace(level);
742 case BTRFS_COMPRESS_LZO: return lzo_alloc_workspace(level);
743 case BTRFS_COMPRESS_ZSTD: return zstd_alloc_workspace(level);
744 default:
745 /*
746 * This can't happen, the type is validated several times
747 * before we get here.
748 */
749 BUG();
750 }
751}
752
753static void free_workspace(int type, struct list_head *ws)
754{
755 switch (type) {
756 case BTRFS_COMPRESS_NONE: return free_heuristic_ws(ws);
757 case BTRFS_COMPRESS_ZLIB: return zlib_free_workspace(ws);
758 case BTRFS_COMPRESS_LZO: return lzo_free_workspace(ws);
759 case BTRFS_COMPRESS_ZSTD: return zstd_free_workspace(ws);
760 default:
761 /*
762 * This can't happen, the type is validated several times
763 * before we get here.
764 */
765 BUG();
766 }
767}
768
769static void btrfs_init_workspace_manager(int type)
770{
771 struct workspace_manager *wsm;
772 struct list_head *workspace;
773
774 wsm = btrfs_compress_op[type]->workspace_manager;
775 INIT_LIST_HEAD(&wsm->idle_ws);
776 spin_lock_init(&wsm->ws_lock);
777 atomic_set(&wsm->total_ws, 0);
778 init_waitqueue_head(&wsm->ws_wait);
779
780 /*
781 * Preallocate one workspace for each compression type so we can
782 * guarantee forward progress in the worst case
783 */
784 workspace = alloc_workspace(type, 0);
785 if (IS_ERR(workspace)) {
786 pr_warn(
787 "BTRFS: cannot preallocate compression workspace, will try later\n");
788 } else {
789 atomic_set(&wsm->total_ws, 1);
790 wsm->free_ws = 1;
791 list_add(workspace, &wsm->idle_ws);
792 }
793}
794
795static void btrfs_cleanup_workspace_manager(int type)
796{
797 struct workspace_manager *wsman;
798 struct list_head *ws;
799
800 wsman = btrfs_compress_op[type]->workspace_manager;
801 while (!list_empty(&wsman->idle_ws)) {
802 ws = wsman->idle_ws.next;
803 list_del(ws);
804 free_workspace(type, ws);
805 atomic_dec(&wsman->total_ws);
806 }
807}
808
809/*
810 * This finds an available workspace or allocates a new one.
811 * If it's not possible to allocate a new one, waits until there's one.
812 * Preallocation makes a forward progress guarantees and we do not return
813 * errors.
814 */
815struct list_head *btrfs_get_workspace(int type, unsigned int level)
816{
817 struct workspace_manager *wsm;
818 struct list_head *workspace;
819 int cpus = num_online_cpus();
820 unsigned nofs_flag;
821 struct list_head *idle_ws;
822 spinlock_t *ws_lock;
823 atomic_t *total_ws;
824 wait_queue_head_t *ws_wait;
825 int *free_ws;
826
827 wsm = btrfs_compress_op[type]->workspace_manager;
828 idle_ws = &wsm->idle_ws;
829 ws_lock = &wsm->ws_lock;
830 total_ws = &wsm->total_ws;
831 ws_wait = &wsm->ws_wait;
832 free_ws = &wsm->free_ws;
833
834again:
835 spin_lock(ws_lock);
836 if (!list_empty(idle_ws)) {
837 workspace = idle_ws->next;
838 list_del(workspace);
839 (*free_ws)--;
840 spin_unlock(ws_lock);
841 return workspace;
842
843 }
844 if (atomic_read(total_ws) > cpus) {
845 DEFINE_WAIT(wait);
846
847 spin_unlock(ws_lock);
848 prepare_to_wait(ws_wait, &wait, TASK_UNINTERRUPTIBLE);
849 if (atomic_read(total_ws) > cpus && !*free_ws)
850 schedule();
851 finish_wait(ws_wait, &wait);
852 goto again;
853 }
854 atomic_inc(total_ws);
855 spin_unlock(ws_lock);
856
857 /*
858 * Allocation helpers call vmalloc that can't use GFP_NOFS, so we have
859 * to turn it off here because we might get called from the restricted
860 * context of btrfs_compress_bio/btrfs_compress_pages
861 */
862 nofs_flag = memalloc_nofs_save();
863 workspace = alloc_workspace(type, level);
864 memalloc_nofs_restore(nofs_flag);
865
866 if (IS_ERR(workspace)) {
867 atomic_dec(total_ws);
868 wake_up(ws_wait);
869
870 /*
871 * Do not return the error but go back to waiting. There's a
872 * workspace preallocated for each type and the compression
873 * time is bounded so we get to a workspace eventually. This
874 * makes our caller's life easier.
875 *
876 * To prevent silent and low-probability deadlocks (when the
877 * initial preallocation fails), check if there are any
878 * workspaces at all.
879 */
880 if (atomic_read(total_ws) == 0) {
881 static DEFINE_RATELIMIT_STATE(_rs,
882 /* once per minute */ 60 * HZ,
883 /* no burst */ 1);
884
885 if (__ratelimit(&_rs)) {
886 pr_warn("BTRFS: no compression workspaces, low memory, retrying\n");
887 }
888 }
889 goto again;
890 }
891 return workspace;
892}
893
894static struct list_head *get_workspace(int type, int level)
895{
896 switch (type) {
897 case BTRFS_COMPRESS_NONE: return btrfs_get_workspace(type, level);
898 case BTRFS_COMPRESS_ZLIB: return zlib_get_workspace(level);
899 case BTRFS_COMPRESS_LZO: return btrfs_get_workspace(type, level);
900 case BTRFS_COMPRESS_ZSTD: return zstd_get_workspace(level);
901 default:
902 /*
903 * This can't happen, the type is validated several times
904 * before we get here.
905 */
906 BUG();
907 }
908}
909
910/*
911 * put a workspace struct back on the list or free it if we have enough
912 * idle ones sitting around
913 */
914void btrfs_put_workspace(int type, struct list_head *ws)
915{
916 struct workspace_manager *wsm;
917 struct list_head *idle_ws;
918 spinlock_t *ws_lock;
919 atomic_t *total_ws;
920 wait_queue_head_t *ws_wait;
921 int *free_ws;
922
923 wsm = btrfs_compress_op[type]->workspace_manager;
924 idle_ws = &wsm->idle_ws;
925 ws_lock = &wsm->ws_lock;
926 total_ws = &wsm->total_ws;
927 ws_wait = &wsm->ws_wait;
928 free_ws = &wsm->free_ws;
929
930 spin_lock(ws_lock);
931 if (*free_ws <= num_online_cpus()) {
932 list_add(ws, idle_ws);
933 (*free_ws)++;
934 spin_unlock(ws_lock);
935 goto wake;
936 }
937 spin_unlock(ws_lock);
938
939 free_workspace(type, ws);
940 atomic_dec(total_ws);
941wake:
942 cond_wake_up(ws_wait);
943}
944
945static void put_workspace(int type, struct list_head *ws)
946{
947 switch (type) {
948 case BTRFS_COMPRESS_NONE: return btrfs_put_workspace(type, ws);
949 case BTRFS_COMPRESS_ZLIB: return btrfs_put_workspace(type, ws);
950 case BTRFS_COMPRESS_LZO: return btrfs_put_workspace(type, ws);
951 case BTRFS_COMPRESS_ZSTD: return zstd_put_workspace(ws);
952 default:
953 /*
954 * This can't happen, the type is validated several times
955 * before we get here.
956 */
957 BUG();
958 }
959}
960
961/*
962 * Adjust @level according to the limits of the compression algorithm or
963 * fallback to default
964 */
965static unsigned int btrfs_compress_set_level(int type, unsigned level)
966{
967 const struct btrfs_compress_op *ops = btrfs_compress_op[type];
968
969 if (level == 0)
970 level = ops->default_level;
971 else
972 level = min(level, ops->max_level);
973
974 return level;
975}
976
977/*
978 * Given an address space and start and length, compress the bytes into @pages
979 * that are allocated on demand.
980 *
981 * @type_level is encoded algorithm and level, where level 0 means whatever
982 * default the algorithm chooses and is opaque here;
983 * - compression algo are 0-3
984 * - the level are bits 4-7
985 *
986 * @out_pages is an in/out parameter, holds maximum number of pages to allocate
987 * and returns number of actually allocated pages
988 *
989 * @total_in is used to return the number of bytes actually read. It
990 * may be smaller than the input length if we had to exit early because we
991 * ran out of room in the pages array or because we cross the
992 * max_out threshold.
993 *
994 * @total_out is an in/out parameter, must be set to the input length and will
995 * be also used to return the total number of compressed bytes
996 */
997int btrfs_compress_pages(unsigned int type_level, struct address_space *mapping,
998 u64 start, struct page **pages,
999 unsigned long *out_pages,
1000 unsigned long *total_in,
1001 unsigned long *total_out)
1002{
1003 int type = btrfs_compress_type(type_level);
1004 int level = btrfs_compress_level(type_level);
1005 struct list_head *workspace;
1006 int ret;
1007
1008 level = btrfs_compress_set_level(type, level);
1009 workspace = get_workspace(type, level);
1010 ret = compression_compress_pages(type, workspace, mapping, start, pages,
1011 out_pages, total_in, total_out);
1012 put_workspace(type, workspace);
1013 return ret;
1014}
1015
1016static int btrfs_decompress_bio(struct compressed_bio *cb)
1017{
1018 struct list_head *workspace;
1019 int ret;
1020 int type = cb->compress_type;
1021
1022 workspace = get_workspace(type, 0);
1023 ret = compression_decompress_bio(workspace, cb);
1024 put_workspace(type, workspace);
1025
1026 if (!ret)
1027 zero_fill_bio(&cb->orig_bbio->bio);
1028 return ret;
1029}
1030
1031/*
1032 * a less complex decompression routine. Our compressed data fits in a
1033 * single page, and we want to read a single page out of it.
1034 * start_byte tells us the offset into the compressed data we're interested in
1035 */
1036int btrfs_decompress(int type, const u8 *data_in, struct page *dest_page,
1037 unsigned long dest_pgoff, size_t srclen, size_t destlen)
1038{
1039 struct btrfs_fs_info *fs_info = page_to_fs_info(dest_page);
1040 struct list_head *workspace;
1041 const u32 sectorsize = fs_info->sectorsize;
1042 int ret;
1043
1044 /*
1045 * The full destination page range should not exceed the page size.
1046 * And the @destlen should not exceed sectorsize, as this is only called for
1047 * inline file extents, which should not exceed sectorsize.
1048 */
1049 ASSERT(dest_pgoff + destlen <= PAGE_SIZE && destlen <= sectorsize);
1050
1051 workspace = get_workspace(type, 0);
1052 ret = compression_decompress(type, workspace, data_in, dest_page,
1053 dest_pgoff, srclen, destlen);
1054 put_workspace(type, workspace);
1055
1056 return ret;
1057}
1058
1059int __init btrfs_init_compress(void)
1060{
1061 if (bioset_init(&btrfs_compressed_bioset, BIO_POOL_SIZE,
1062 offsetof(struct compressed_bio, bbio.bio),
1063 BIOSET_NEED_BVECS))
1064 return -ENOMEM;
1065
1066 compr_pool.shrinker = shrinker_alloc(SHRINKER_NONSLAB, "btrfs-compr-pages");
1067 if (!compr_pool.shrinker)
1068 return -ENOMEM;
1069
1070 btrfs_init_workspace_manager(BTRFS_COMPRESS_NONE);
1071 btrfs_init_workspace_manager(BTRFS_COMPRESS_ZLIB);
1072 btrfs_init_workspace_manager(BTRFS_COMPRESS_LZO);
1073 zstd_init_workspace_manager();
1074
1075 spin_lock_init(&compr_pool.lock);
1076 INIT_LIST_HEAD(&compr_pool.list);
1077 compr_pool.count = 0;
1078 /* 128K / 4K = 32, for 8 threads is 256 pages. */
1079 compr_pool.thresh = BTRFS_MAX_COMPRESSED / PAGE_SIZE * 8;
1080 compr_pool.shrinker->count_objects = btrfs_compr_pool_count;
1081 compr_pool.shrinker->scan_objects = btrfs_compr_pool_scan;
1082 compr_pool.shrinker->batch = 32;
1083 compr_pool.shrinker->seeks = DEFAULT_SEEKS;
1084 shrinker_register(compr_pool.shrinker);
1085
1086 return 0;
1087}
1088
1089void __cold btrfs_exit_compress(void)
1090{
1091 /* For now scan drains all pages and does not touch the parameters. */
1092 btrfs_compr_pool_scan(NULL, NULL);
1093 shrinker_free(compr_pool.shrinker);
1094
1095 btrfs_cleanup_workspace_manager(BTRFS_COMPRESS_NONE);
1096 btrfs_cleanup_workspace_manager(BTRFS_COMPRESS_ZLIB);
1097 btrfs_cleanup_workspace_manager(BTRFS_COMPRESS_LZO);
1098 zstd_cleanup_workspace_manager();
1099 bioset_exit(&btrfs_compressed_bioset);
1100}
1101
1102/*
1103 * Copy decompressed data from working buffer to pages.
1104 *
1105 * @buf: The decompressed data buffer
1106 * @buf_len: The decompressed data length
1107 * @decompressed: Number of bytes that are already decompressed inside the
1108 * compressed extent
1109 * @cb: The compressed extent descriptor
1110 * @orig_bio: The original bio that the caller wants to read for
1111 *
1112 * An easier to understand graph is like below:
1113 *
1114 * |<- orig_bio ->| |<- orig_bio->|
1115 * |<------- full decompressed extent ----->|
1116 * |<----------- @cb range ---->|
1117 * | |<-- @buf_len -->|
1118 * |<--- @decompressed --->|
1119 *
1120 * Note that, @cb can be a subpage of the full decompressed extent, but
1121 * @cb->start always has the same as the orig_file_offset value of the full
1122 * decompressed extent.
1123 *
1124 * When reading compressed extent, we have to read the full compressed extent,
1125 * while @orig_bio may only want part of the range.
1126 * Thus this function will ensure only data covered by @orig_bio will be copied
1127 * to.
1128 *
1129 * Return 0 if we have copied all needed contents for @orig_bio.
1130 * Return >0 if we need continue decompress.
1131 */
1132int btrfs_decompress_buf2page(const char *buf, u32 buf_len,
1133 struct compressed_bio *cb, u32 decompressed)
1134{
1135 struct bio *orig_bio = &cb->orig_bbio->bio;
1136 /* Offset inside the full decompressed extent */
1137 u32 cur_offset;
1138
1139 cur_offset = decompressed;
1140 /* The main loop to do the copy */
1141 while (cur_offset < decompressed + buf_len) {
1142 struct bio_vec bvec;
1143 size_t copy_len;
1144 u32 copy_start;
1145 /* Offset inside the full decompressed extent */
1146 u32 bvec_offset;
1147
1148 bvec = bio_iter_iovec(orig_bio, orig_bio->bi_iter);
1149 /*
1150 * cb->start may underflow, but subtracting that value can still
1151 * give us correct offset inside the full decompressed extent.
1152 */
1153 bvec_offset = page_offset(bvec.bv_page) + bvec.bv_offset - cb->start;
1154
1155 /* Haven't reached the bvec range, exit */
1156 if (decompressed + buf_len <= bvec_offset)
1157 return 1;
1158
1159 copy_start = max(cur_offset, bvec_offset);
1160 copy_len = min(bvec_offset + bvec.bv_len,
1161 decompressed + buf_len) - copy_start;
1162 ASSERT(copy_len);
1163
1164 /*
1165 * Extra range check to ensure we didn't go beyond
1166 * @buf + @buf_len.
1167 */
1168 ASSERT(copy_start - decompressed < buf_len);
1169 memcpy_to_page(bvec.bv_page, bvec.bv_offset,
1170 buf + copy_start - decompressed, copy_len);
1171 cur_offset += copy_len;
1172
1173 bio_advance(orig_bio, copy_len);
1174 /* Finished the bio */
1175 if (!orig_bio->bi_iter.bi_size)
1176 return 0;
1177 }
1178 return 1;
1179}
1180
1181/*
1182 * Shannon Entropy calculation
1183 *
1184 * Pure byte distribution analysis fails to determine compressibility of data.
1185 * Try calculating entropy to estimate the average minimum number of bits
1186 * needed to encode the sampled data.
1187 *
1188 * For convenience, return the percentage of needed bits, instead of amount of
1189 * bits directly.
1190 *
1191 * @ENTROPY_LVL_ACEPTABLE - below that threshold, sample has low byte entropy
1192 * and can be compressible with high probability
1193 *
1194 * @ENTROPY_LVL_HIGH - data are not compressible with high probability
1195 *
1196 * Use of ilog2() decreases precision, we lower the LVL to 5 to compensate.
1197 */
1198#define ENTROPY_LVL_ACEPTABLE (65)
1199#define ENTROPY_LVL_HIGH (80)
1200
1201/*
1202 * For increasead precision in shannon_entropy calculation,
1203 * let's do pow(n, M) to save more digits after comma:
1204 *
1205 * - maximum int bit length is 64
1206 * - ilog2(MAX_SAMPLE_SIZE) -> 13
1207 * - 13 * 4 = 52 < 64 -> M = 4
1208 *
1209 * So use pow(n, 4).
1210 */
1211static inline u32 ilog2_w(u64 n)
1212{
1213 return ilog2(n * n * n * n);
1214}
1215
1216static u32 shannon_entropy(struct heuristic_ws *ws)
1217{
1218 const u32 entropy_max = 8 * ilog2_w(2);
1219 u32 entropy_sum = 0;
1220 u32 p, p_base, sz_base;
1221 u32 i;
1222
1223 sz_base = ilog2_w(ws->sample_size);
1224 for (i = 0; i < BUCKET_SIZE && ws->bucket[i].count > 0; i++) {
1225 p = ws->bucket[i].count;
1226 p_base = ilog2_w(p);
1227 entropy_sum += p * (sz_base - p_base);
1228 }
1229
1230 entropy_sum /= ws->sample_size;
1231 return entropy_sum * 100 / entropy_max;
1232}
1233
1234#define RADIX_BASE 4U
1235#define COUNTERS_SIZE (1U << RADIX_BASE)
1236
1237static u8 get4bits(u64 num, int shift) {
1238 u8 low4bits;
1239
1240 num >>= shift;
1241 /* Reverse order */
1242 low4bits = (COUNTERS_SIZE - 1) - (num % COUNTERS_SIZE);
1243 return low4bits;
1244}
1245
1246/*
1247 * Use 4 bits as radix base
1248 * Use 16 u32 counters for calculating new position in buf array
1249 *
1250 * @array - array that will be sorted
1251 * @array_buf - buffer array to store sorting results
1252 * must be equal in size to @array
1253 * @num - array size
1254 */
1255static void radix_sort(struct bucket_item *array, struct bucket_item *array_buf,
1256 int num)
1257{
1258 u64 max_num;
1259 u64 buf_num;
1260 u32 counters[COUNTERS_SIZE];
1261 u32 new_addr;
1262 u32 addr;
1263 int bitlen;
1264 int shift;
1265 int i;
1266
1267 /*
1268 * Try avoid useless loop iterations for small numbers stored in big
1269 * counters. Example: 48 33 4 ... in 64bit array
1270 */
1271 max_num = array[0].count;
1272 for (i = 1; i < num; i++) {
1273 buf_num = array[i].count;
1274 if (buf_num > max_num)
1275 max_num = buf_num;
1276 }
1277
1278 buf_num = ilog2(max_num);
1279 bitlen = ALIGN(buf_num, RADIX_BASE * 2);
1280
1281 shift = 0;
1282 while (shift < bitlen) {
1283 memset(counters, 0, sizeof(counters));
1284
1285 for (i = 0; i < num; i++) {
1286 buf_num = array[i].count;
1287 addr = get4bits(buf_num, shift);
1288 counters[addr]++;
1289 }
1290
1291 for (i = 1; i < COUNTERS_SIZE; i++)
1292 counters[i] += counters[i - 1];
1293
1294 for (i = num - 1; i >= 0; i--) {
1295 buf_num = array[i].count;
1296 addr = get4bits(buf_num, shift);
1297 counters[addr]--;
1298 new_addr = counters[addr];
1299 array_buf[new_addr] = array[i];
1300 }
1301
1302 shift += RADIX_BASE;
1303
1304 /*
1305 * Normal radix expects to move data from a temporary array, to
1306 * the main one. But that requires some CPU time. Avoid that
1307 * by doing another sort iteration to original array instead of
1308 * memcpy()
1309 */
1310 memset(counters, 0, sizeof(counters));
1311
1312 for (i = 0; i < num; i ++) {
1313 buf_num = array_buf[i].count;
1314 addr = get4bits(buf_num, shift);
1315 counters[addr]++;
1316 }
1317
1318 for (i = 1; i < COUNTERS_SIZE; i++)
1319 counters[i] += counters[i - 1];
1320
1321 for (i = num - 1; i >= 0; i--) {
1322 buf_num = array_buf[i].count;
1323 addr = get4bits(buf_num, shift);
1324 counters[addr]--;
1325 new_addr = counters[addr];
1326 array[new_addr] = array_buf[i];
1327 }
1328
1329 shift += RADIX_BASE;
1330 }
1331}
1332
1333/*
1334 * Size of the core byte set - how many bytes cover 90% of the sample
1335 *
1336 * There are several types of structured binary data that use nearly all byte
1337 * values. The distribution can be uniform and counts in all buckets will be
1338 * nearly the same (eg. encrypted data). Unlikely to be compressible.
1339 *
1340 * Other possibility is normal (Gaussian) distribution, where the data could
1341 * be potentially compressible, but we have to take a few more steps to decide
1342 * how much.
1343 *
1344 * @BYTE_CORE_SET_LOW - main part of byte values repeated frequently,
1345 * compression algo can easy fix that
1346 * @BYTE_CORE_SET_HIGH - data have uniform distribution and with high
1347 * probability is not compressible
1348 */
1349#define BYTE_CORE_SET_LOW (64)
1350#define BYTE_CORE_SET_HIGH (200)
1351
1352static int byte_core_set_size(struct heuristic_ws *ws)
1353{
1354 u32 i;
1355 u32 coreset_sum = 0;
1356 const u32 core_set_threshold = ws->sample_size * 90 / 100;
1357 struct bucket_item *bucket = ws->bucket;
1358
1359 /* Sort in reverse order */
1360 radix_sort(ws->bucket, ws->bucket_b, BUCKET_SIZE);
1361
1362 for (i = 0; i < BYTE_CORE_SET_LOW; i++)
1363 coreset_sum += bucket[i].count;
1364
1365 if (coreset_sum > core_set_threshold)
1366 return i;
1367
1368 for (; i < BYTE_CORE_SET_HIGH && bucket[i].count > 0; i++) {
1369 coreset_sum += bucket[i].count;
1370 if (coreset_sum > core_set_threshold)
1371 break;
1372 }
1373
1374 return i;
1375}
1376
1377/*
1378 * Count byte values in buckets.
1379 * This heuristic can detect textual data (configs, xml, json, html, etc).
1380 * Because in most text-like data byte set is restricted to limited number of
1381 * possible characters, and that restriction in most cases makes data easy to
1382 * compress.
1383 *
1384 * @BYTE_SET_THRESHOLD - consider all data within this byte set size:
1385 * less - compressible
1386 * more - need additional analysis
1387 */
1388#define BYTE_SET_THRESHOLD (64)
1389
1390static u32 byte_set_size(const struct heuristic_ws *ws)
1391{
1392 u32 i;
1393 u32 byte_set_size = 0;
1394
1395 for (i = 0; i < BYTE_SET_THRESHOLD; i++) {
1396 if (ws->bucket[i].count > 0)
1397 byte_set_size++;
1398 }
1399
1400 /*
1401 * Continue collecting count of byte values in buckets. If the byte
1402 * set size is bigger then the threshold, it's pointless to continue,
1403 * the detection technique would fail for this type of data.
1404 */
1405 for (; i < BUCKET_SIZE; i++) {
1406 if (ws->bucket[i].count > 0) {
1407 byte_set_size++;
1408 if (byte_set_size > BYTE_SET_THRESHOLD)
1409 return byte_set_size;
1410 }
1411 }
1412
1413 return byte_set_size;
1414}
1415
1416static bool sample_repeated_patterns(struct heuristic_ws *ws)
1417{
1418 const u32 half_of_sample = ws->sample_size / 2;
1419 const u8 *data = ws->sample;
1420
1421 return memcmp(&data[0], &data[half_of_sample], half_of_sample) == 0;
1422}
1423
1424static void heuristic_collect_sample(struct inode *inode, u64 start, u64 end,
1425 struct heuristic_ws *ws)
1426{
1427 struct page *page;
1428 u64 index, index_end;
1429 u32 i, curr_sample_pos;
1430 u8 *in_data;
1431
1432 /*
1433 * Compression handles the input data by chunks of 128KiB
1434 * (defined by BTRFS_MAX_UNCOMPRESSED)
1435 *
1436 * We do the same for the heuristic and loop over the whole range.
1437 *
1438 * MAX_SAMPLE_SIZE - calculated under assumption that heuristic will
1439 * process no more than BTRFS_MAX_UNCOMPRESSED at a time.
1440 */
1441 if (end - start > BTRFS_MAX_UNCOMPRESSED)
1442 end = start + BTRFS_MAX_UNCOMPRESSED;
1443
1444 index = start >> PAGE_SHIFT;
1445 index_end = end >> PAGE_SHIFT;
1446
1447 /* Don't miss unaligned end */
1448 if (!PAGE_ALIGNED(end))
1449 index_end++;
1450
1451 curr_sample_pos = 0;
1452 while (index < index_end) {
1453 page = find_get_page(inode->i_mapping, index);
1454 in_data = kmap_local_page(page);
1455 /* Handle case where the start is not aligned to PAGE_SIZE */
1456 i = start % PAGE_SIZE;
1457 while (i < PAGE_SIZE - SAMPLING_READ_SIZE) {
1458 /* Don't sample any garbage from the last page */
1459 if (start > end - SAMPLING_READ_SIZE)
1460 break;
1461 memcpy(&ws->sample[curr_sample_pos], &in_data[i],
1462 SAMPLING_READ_SIZE);
1463 i += SAMPLING_INTERVAL;
1464 start += SAMPLING_INTERVAL;
1465 curr_sample_pos += SAMPLING_READ_SIZE;
1466 }
1467 kunmap_local(in_data);
1468 put_page(page);
1469
1470 index++;
1471 }
1472
1473 ws->sample_size = curr_sample_pos;
1474}
1475
1476/*
1477 * Compression heuristic.
1478 *
1479 * The following types of analysis can be performed:
1480 * - detect mostly zero data
1481 * - detect data with low "byte set" size (text, etc)
1482 * - detect data with low/high "core byte" set
1483 *
1484 * Return non-zero if the compression should be done, 0 otherwise.
1485 */
1486int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end)
1487{
1488 struct list_head *ws_list = get_workspace(0, 0);
1489 struct heuristic_ws *ws;
1490 u32 i;
1491 u8 byte;
1492 int ret = 0;
1493
1494 ws = list_entry(ws_list, struct heuristic_ws, list);
1495
1496 heuristic_collect_sample(inode, start, end, ws);
1497
1498 if (sample_repeated_patterns(ws)) {
1499 ret = 1;
1500 goto out;
1501 }
1502
1503 memset(ws->bucket, 0, sizeof(*ws->bucket)*BUCKET_SIZE);
1504
1505 for (i = 0; i < ws->sample_size; i++) {
1506 byte = ws->sample[i];
1507 ws->bucket[byte].count++;
1508 }
1509
1510 i = byte_set_size(ws);
1511 if (i < BYTE_SET_THRESHOLD) {
1512 ret = 2;
1513 goto out;
1514 }
1515
1516 i = byte_core_set_size(ws);
1517 if (i <= BYTE_CORE_SET_LOW) {
1518 ret = 3;
1519 goto out;
1520 }
1521
1522 if (i >= BYTE_CORE_SET_HIGH) {
1523 ret = 0;
1524 goto out;
1525 }
1526
1527 i = shannon_entropy(ws);
1528 if (i <= ENTROPY_LVL_ACEPTABLE) {
1529 ret = 4;
1530 goto out;
1531 }
1532
1533 /*
1534 * For the levels below ENTROPY_LVL_HIGH, additional analysis would be
1535 * needed to give green light to compression.
1536 *
1537 * For now just assume that compression at that level is not worth the
1538 * resources because:
1539 *
1540 * 1. it is possible to defrag the data later
1541 *
1542 * 2. the data would turn out to be hardly compressible, eg. 150 byte
1543 * values, every bucket has counter at level ~54. The heuristic would
1544 * be confused. This can happen when data have some internal repeated
1545 * patterns like "abbacbbc...". This can be detected by analyzing
1546 * pairs of bytes, which is too costly.
1547 */
1548 if (i < ENTROPY_LVL_HIGH) {
1549 ret = 5;
1550 goto out;
1551 } else {
1552 ret = 0;
1553 goto out;
1554 }
1555
1556out:
1557 put_workspace(0, ws_list);
1558 return ret;
1559}
1560
1561/*
1562 * Convert the compression suffix (eg. after "zlib" starting with ":") to
1563 * level, unrecognized string will set the default level
1564 */
1565unsigned int btrfs_compress_str2level(unsigned int type, const char *str)
1566{
1567 unsigned int level = 0;
1568 int ret;
1569
1570 if (!type)
1571 return 0;
1572
1573 if (str[0] == ':') {
1574 ret = kstrtouint(str + 1, 10, &level);
1575 if (ret)
1576 level = 0;
1577 }
1578
1579 level = btrfs_compress_set_level(type, level);
1580
1581 return level;
1582}