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