fs/btrfs/zstd.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2016-present, Facebook, Inc.
   4  * All rights reserved.
   5  *
   6  */
   7
   8 #include <linux/bio.h>
   9 #include <linux/err.h>
  10 #include <linux/init.h>
  11 #include <linux/kernel.h>
  12 #include <linux/mm.h>
  13 #include <linux/pagemap.h>
  14 #include <linux/refcount.h>
  15 #include <linux/sched.h>
  16 #include <linux/slab.h>
  17 #include <linux/zstd.h>
  18 #include "compression.h"
  19
  20 #define ZSTD_BTRFS_MAX_WINDOWLOG 17
  21 #define ZSTD_BTRFS_MAX_INPUT (1 << ZSTD_BTRFS_MAX_WINDOWLOG)
  22 #define ZSTD_BTRFS_DEFAULT_LEVEL 3
  23 #define ZSTD_BTRFS_MAX_LEVEL 15
  24
  25 static ZSTD_parameters zstd_get_btrfs_parameters(unsigned int level,
  26                                                  size_t src_len)
  27 {
  28         ZSTD_parameters params = ZSTD_getParams(level, src_len, 0);
  29
  30         if (params.cParams.windowLog > ZSTD_BTRFS_MAX_WINDOWLOG)
  31                 params.cParams.windowLog = ZSTD_BTRFS_MAX_WINDOWLOG;
  32         WARN_ON(src_len > ZSTD_BTRFS_MAX_INPUT);
  33         return params;
  34 }
  35
  36 struct workspace {
  37         void *mem;
  38         size_t size;
  39         char *buf;
  40         unsigned int req_level;
  41         struct list_head list;
  42         ZSTD_inBuffer in_buf;
  43         ZSTD_outBuffer out_buf;
  44 };
  45
  46 static struct workspace_manager wsm;
  47
  48 static size_t zstd_ws_mem_sizes[ZSTD_BTRFS_MAX_LEVEL];
  49
  50 /*
  51  * zstd_calc_ws_mem_sizes - calculate monotonic memory bounds
  52  *
  53  * It is possible based on the level configurations that a higher level
  54  * workspace uses less memory than a lower level workspace.  In order to reuse
  55  * workspaces, this must be made a monotonic relationship.  This precomputes
  56  * the required memory for each level and enforces the monotonicity between
  57  * level and memory required.
  58  */
  59 static void zstd_calc_ws_mem_sizes(void)
  60 {
  61         size_t max_size = 0;
  62         unsigned int level;
  63
  64         for (level = 1; level <= ZSTD_BTRFS_MAX_LEVEL; level++) {
  65                 ZSTD_parameters params =
  66                         zstd_get_btrfs_parameters(level, ZSTD_BTRFS_MAX_INPUT);
  67                 size_t level_size =
  68                         max_t(size_t,
  69                               ZSTD_CStreamWorkspaceBound(params.cParams),
  70                               ZSTD_DStreamWorkspaceBound(ZSTD_BTRFS_MAX_INPUT));
  71
  72                 max_size = max_t(size_t, max_size, level_size);
  73                 zstd_ws_mem_sizes[level - 1] = max_size;
  74         }
  75 }
  76
  77 static void zstd_init_workspace_manager(void)
  78 {
  79         zstd_calc_ws_mem_sizes();
  80
  81         btrfs_init_workspace_manager(&wsm, &btrfs_zstd_compress);
  82 }
  83
  84 static void zstd_cleanup_workspace_manager(void)
  85 {
  86         btrfs_cleanup_workspace_manager(&wsm);
  87 }
  88
  89 static struct list_head *zstd_get_workspace(unsigned int level)
  90 {
  91         struct list_head *ws = btrfs_get_workspace(&wsm, level);
  92         struct workspace *workspace = list_entry(ws, struct workspace, list);
  93
  94         workspace->req_level = level;
  95
  96         return ws;
  97 }
  98
  99 static void zstd_put_workspace(struct list_head *ws)
 100 {
 101         btrfs_put_workspace(&wsm, ws);
 102 }
 103
 104 static void zstd_free_workspace(struct list_head *ws)
 105 {
 106         struct workspace *workspace = list_entry(ws, struct workspace, list);
 107
 108         kvfree(workspace->mem);
 109         kfree(workspace->buf);
 110         kfree(workspace);
 111 }
 112
 113 static struct list_head *zstd_alloc_workspace(unsigned int level)
 114 {
 115         struct workspace *workspace;
 116
 117         workspace = kzalloc(sizeof(*workspace), GFP_KERNEL);
 118         if (!workspace)
 119                 return ERR_PTR(-ENOMEM);
 120
 121         workspace->size = zstd_ws_mem_sizes[level - 1];
 122         workspace->mem = kvmalloc(workspace->size, GFP_KERNEL);
 123         workspace->buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
 124         if (!workspace->mem || !workspace->buf)
 125                 goto fail;
 126
 127         INIT_LIST_HEAD(&workspace->list);
 128
 129         return &workspace->list;
 130 fail:
 131         zstd_free_workspace(&workspace->list);
 132         return ERR_PTR(-ENOMEM);
 133 }
 134
 135 static int zstd_compress_pages(struct list_head *ws,
 136                 struct address_space *mapping,
 137                 u64 start,
 138                 struct page **pages,
 139                 unsigned long *out_pages,
 140                 unsigned long *total_in,
 141                 unsigned long *total_out)
 142 {
 143         struct workspace *workspace = list_entry(ws, struct workspace, list);
 144         ZSTD_CStream *stream;
 145         int ret = 0;
 146         int nr_pages = 0;
 147         struct page *in_page = NULL;  /* The current page to read */
 148         struct page *out_page = NULL; /* The current page to write to */
 149         unsigned long tot_in = 0;
 150         unsigned long tot_out = 0;
 151         unsigned long len = *total_out;
 152         const unsigned long nr_dest_pages = *out_pages;
 153         unsigned long max_out = nr_dest_pages * PAGE_SIZE;
 154         ZSTD_parameters params = zstd_get_btrfs_parameters(workspace->req_level,
 155                                                            len);
 156
 157         *out_pages = 0;
 158         *total_out = 0;
 159         *total_in = 0;
 160
 161         /* Initialize the stream */
 162         stream = ZSTD_initCStream(params, len, workspace->mem,
 163                         workspace->size);
 164         if (!stream) {
 165                 pr_warn("BTRFS: ZSTD_initCStream failed\n");
 166                 ret = -EIO;
 167                 goto out;
 168         }
 169
 170         /* map in the first page of input data */
 171         in_page = find_get_page(mapping, start >> PAGE_SHIFT);
 172         workspace->in_buf.src = kmap(in_page);
 173         workspace->in_buf.pos = 0;
 174         workspace->in_buf.size = min_t(size_t, len, PAGE_SIZE);
 175
 176
 177         /* Allocate and map in the output buffer */
 178         out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
 179         if (out_page == NULL) {
 180                 ret = -ENOMEM;
 181                 goto out;
 182         }
 183         pages[nr_pages++] = out_page;
 184         workspace->out_buf.dst = kmap(out_page);
 185         workspace->out_buf.pos = 0;
 186         workspace->out_buf.size = min_t(size_t, max_out, PAGE_SIZE);
 187
 188         while (1) {
 189                 size_t ret2;
 190
 191                 ret2 = ZSTD_compressStream(stream, &workspace->out_buf,
 192                                 &workspace->in_buf);
 193                 if (ZSTD_isError(ret2)) {
 194                         pr_debug("BTRFS: ZSTD_compressStream returned %d\n",
 195                                         ZSTD_getErrorCode(ret2));
 196                         ret = -EIO;
 197                         goto out;
 198                 }
 199
 200                 /* Check to see if we are making it bigger */
 201                 if (tot_in + workspace->in_buf.pos > 8192 &&
 202                                 tot_in + workspace->in_buf.pos <
 203                                 tot_out + workspace->out_buf.pos) {
 204                         ret = -E2BIG;
 205                         goto out;
 206                 }
 207
 208                 /* We've reached the end of our output range */
 209                 if (workspace->out_buf.pos >= max_out) {
 210                         tot_out += workspace->out_buf.pos;
 211                         ret = -E2BIG;
 212                         goto out;
 213                 }
 214
 215                 /* Check if we need more output space */
 216                 if (workspace->out_buf.pos == workspace->out_buf.size) {
 217                         tot_out += PAGE_SIZE;
 218                         max_out -= PAGE_SIZE;
 219                         kunmap(out_page);
 220                         if (nr_pages == nr_dest_pages) {
 221                                 out_page = NULL;
 222                                 ret = -E2BIG;
 223                                 goto out;
 224                         }
 225                         out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
 226                         if (out_page == NULL) {
 227                                 ret = -ENOMEM;
 228                                 goto out;
 229                         }
 230                         pages[nr_pages++] = out_page;
 231                         workspace->out_buf.dst = kmap(out_page);
 232                         workspace->out_buf.pos = 0;
 233                         workspace->out_buf.size = min_t(size_t, max_out,
 234                                                         PAGE_SIZE);
 235                 }
 236
 237                 /* We've reached the end of the input */
 238                 if (workspace->in_buf.pos >= len) {
 239                         tot_in += workspace->in_buf.pos;
 240                         break;
 241                 }
 242
 243                 /* Check if we need more input */
 244                 if (workspace->in_buf.pos == workspace->in_buf.size) {
 245                         tot_in += PAGE_SIZE;
 246                         kunmap(in_page);
 247                         put_page(in_page);
 248
 249                         start += PAGE_SIZE;
 250                         len -= PAGE_SIZE;
 251                         in_page = find_get_page(mapping, start >> PAGE_SHIFT);
 252                         workspace->in_buf.src = kmap(in_page);
 253                         workspace->in_buf.pos = 0;
 254                         workspace->in_buf.size = min_t(size_t, len, PAGE_SIZE);
 255                 }
 256         }
 257         while (1) {
 258                 size_t ret2;
 259
 260                 ret2 = ZSTD_endStream(stream, &workspace->out_buf);
 261                 if (ZSTD_isError(ret2)) {
 262                         pr_debug("BTRFS: ZSTD_endStream returned %d\n",
 263                                         ZSTD_getErrorCode(ret2));
 264                         ret = -EIO;
 265                         goto out;
 266                 }
 267                 if (ret2 == 0) {
 268                         tot_out += workspace->out_buf.pos;
 269                         break;
 270                 }
 271                 if (workspace->out_buf.pos >= max_out) {
 272                         tot_out += workspace->out_buf.pos;
 273                         ret = -E2BIG;
 274                         goto out;
 275                 }
 276
 277                 tot_out += PAGE_SIZE;
 278                 max_out -= PAGE_SIZE;
 279                 kunmap(out_page);
 280                 if (nr_pages == nr_dest_pages) {
 281                         out_page = NULL;
 282                         ret = -E2BIG;
 283                         goto out;
 284                 }
 285                 out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
 286                 if (out_page == NULL) {
 287                         ret = -ENOMEM;
 288                         goto out;
 289                 }
 290                 pages[nr_pages++] = out_page;
 291                 workspace->out_buf.dst = kmap(out_page);
 292                 workspace->out_buf.pos = 0;
 293                 workspace->out_buf.size = min_t(size_t, max_out, PAGE_SIZE);
 294         }
 295
 296         if (tot_out >= tot_in) {
 297                 ret = -E2BIG;
 298                 goto out;
 299         }
 300
 301         ret = 0;
 302         *total_in = tot_in;
 303         *total_out = tot_out;
 304 out:
 305         *out_pages = nr_pages;
 306         /* Cleanup */
 307         if (in_page) {
 308                 kunmap(in_page);
 309                 put_page(in_page);
 310         }
 311         if (out_page)
 312                 kunmap(out_page);
 313         return ret;
 314 }
 315
 316 static int zstd_decompress_bio(struct list_head *ws, struct compressed_bio *cb)
 317 {
 318         struct workspace *workspace = list_entry(ws, struct workspace, list);
 319         struct page **pages_in = cb->compressed_pages;
 320         u64 disk_start = cb->start;
 321         struct bio *orig_bio = cb->orig_bio;
 322         size_t srclen = cb->compressed_len;
 323         ZSTD_DStream *stream;
 324         int ret = 0;
 325         unsigned long page_in_index = 0;
 326         unsigned long total_pages_in = DIV_ROUND_UP(srclen, PAGE_SIZE);
 327         unsigned long buf_start;
 328         unsigned long total_out = 0;
 329
 330         stream = ZSTD_initDStream(
 331                         ZSTD_BTRFS_MAX_INPUT, workspace->mem, workspace->size);
 332         if (!stream) {
 333                 pr_debug("BTRFS: ZSTD_initDStream failed\n");
 334                 ret = -EIO;
 335                 goto done;
 336         }
 337
 338         workspace->in_buf.src = kmap(pages_in[page_in_index]);
 339         workspace->in_buf.pos = 0;
 340         workspace->in_buf.size = min_t(size_t, srclen, PAGE_SIZE);
 341
 342         workspace->out_buf.dst = workspace->buf;
 343         workspace->out_buf.pos = 0;
 344         workspace->out_buf.size = PAGE_SIZE;
 345
 346         while (1) {
 347                 size_t ret2;
 348
 349                 ret2 = ZSTD_decompressStream(stream, &workspace->out_buf,
 350                                 &workspace->in_buf);
 351                 if (ZSTD_isError(ret2)) {
 352                         pr_debug("BTRFS: ZSTD_decompressStream returned %d\n",
 353                                         ZSTD_getErrorCode(ret2));
 354                         ret = -EIO;
 355                         goto done;
 356                 }
 357                 buf_start = total_out;
 358                 total_out += workspace->out_buf.pos;
 359                 workspace->out_buf.pos = 0;
 360
 361                 ret = btrfs_decompress_buf2page(workspace->out_buf.dst,
 362                                 buf_start, total_out, disk_start, orig_bio);
 363                 if (ret == 0)
 364                         break;
 365
 366                 if (workspace->in_buf.pos >= srclen)
 367                         break;
 368
 369                 /* Check if we've hit the end of a frame */
 370                 if (ret2 == 0)
 371                         break;
 372
 373                 if (workspace->in_buf.pos == workspace->in_buf.size) {
 374                         kunmap(pages_in[page_in_index++]);
 375                         if (page_in_index >= total_pages_in) {
 376                                 workspace->in_buf.src = NULL;
 377                                 ret = -EIO;
 378                                 goto done;
 379                         }
 380                         srclen -= PAGE_SIZE;
 381                         workspace->in_buf.src = kmap(pages_in[page_in_index]);
 382                         workspace->in_buf.pos = 0;
 383                         workspace->in_buf.size = min_t(size_t, srclen, PAGE_SIZE);
 384                 }
 385         }
 386         ret = 0;
 387         zero_fill_bio(orig_bio);
 388 done:
 389         if (workspace->in_buf.src)
 390                 kunmap(pages_in[page_in_index]);
 391         return ret;
 392 }
 393
 394 static int zstd_decompress(struct list_head *ws, unsigned char *data_in,
 395                 struct page *dest_page,
 396                 unsigned long start_byte,
 397                 size_t srclen, size_t destlen)
 398 {
 399         struct workspace *workspace = list_entry(ws, struct workspace, list);
 400         ZSTD_DStream *stream;
 401         int ret = 0;
 402         size_t ret2;
 403         unsigned long total_out = 0;
 404         unsigned long pg_offset = 0;
 405         char *kaddr;
 406
 407         stream = ZSTD_initDStream(
 408                         ZSTD_BTRFS_MAX_INPUT, workspace->mem, workspace->size);
 409         if (!stream) {
 410                 pr_warn("BTRFS: ZSTD_initDStream failed\n");
 411                 ret = -EIO;
 412                 goto finish;
 413         }
 414
 415         destlen = min_t(size_t, destlen, PAGE_SIZE);
 416
 417         workspace->in_buf.src = data_in;
 418         workspace->in_buf.pos = 0;
 419         workspace->in_buf.size = srclen;
 420
 421         workspace->out_buf.dst = workspace->buf;
 422         workspace->out_buf.pos = 0;
 423         workspace->out_buf.size = PAGE_SIZE;
 424
 425         ret2 = 1;
 426         while (pg_offset < destlen
 427                && workspace->in_buf.pos < workspace->in_buf.size) {
 428                 unsigned long buf_start;
 429                 unsigned long buf_offset;
 430                 unsigned long bytes;
 431
 432                 /* Check if the frame is over and we still need more input */
 433                 if (ret2 == 0) {
 434                         pr_debug("BTRFS: ZSTD_decompressStream ended early\n");
 435                         ret = -EIO;
 436                         goto finish;
 437                 }
 438                 ret2 = ZSTD_decompressStream(stream, &workspace->out_buf,
 439                                 &workspace->in_buf);
 440                 if (ZSTD_isError(ret2)) {
 441                         pr_debug("BTRFS: ZSTD_decompressStream returned %d\n",
 442                                         ZSTD_getErrorCode(ret2));
 443                         ret = -EIO;
 444                         goto finish;
 445                 }
 446
 447                 buf_start = total_out;
 448                 total_out += workspace->out_buf.pos;
 449                 workspace->out_buf.pos = 0;
 450
 451                 if (total_out <= start_byte)
 452                         continue;
 453
 454                 if (total_out > start_byte && buf_start < start_byte)
 455                         buf_offset = start_byte - buf_start;
 456                 else
 457                         buf_offset = 0;
 458
 459                 bytes = min_t(unsigned long, destlen - pg_offset,
 460                                 workspace->out_buf.size - buf_offset);
 461
 462                 kaddr = kmap_atomic(dest_page);
 463                 memcpy(kaddr + pg_offset, workspace->out_buf.dst + buf_offset,
 464                                 bytes);
 465                 kunmap_atomic(kaddr);
 466
 467                 pg_offset += bytes;
 468         }
 469         ret = 0;
 470 finish:
 471         if (pg_offset < destlen) {
 472                 kaddr = kmap_atomic(dest_page);
 473                 memset(kaddr + pg_offset, 0, destlen - pg_offset);
 474                 kunmap_atomic(kaddr);
 475         }
 476         return ret;
 477 }
 478
 479 static unsigned int zstd_set_level(unsigned int level)
 480 {
 481         return ZSTD_BTRFS_DEFAULT_LEVEL;
 482 }
 483
 484 const struct btrfs_compress_op btrfs_zstd_compress = {
 485         .init_workspace_manager = zstd_init_workspace_manager,
 486         .cleanup_workspace_manager = zstd_cleanup_workspace_manager,
 487         .get_workspace = zstd_get_workspace,
 488         .put_workspace = zstd_put_workspace,
 489         .alloc_workspace = zstd_alloc_workspace,
 490         .free_workspace = zstd_free_workspace,
 491         .compress_pages = zstd_compress_pages,
 492         .decompress_bio = zstd_decompress_bio,
 493         .decompress = zstd_decompress,
 494         .set_level = zstd_set_level,
 495 };