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