deps/libchdr/deps/zstd-1.5.6/lib/compress/zstd_cwksp.h

   1 /*
   2  * Copyright (c) Meta Platforms, Inc. and affiliates.
   3  * All rights reserved.
   4  *
   5  * This source code is licensed under both the BSD-style license (found in the
   6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
   7  * in the COPYING file in the root directory of this source tree).
   8  * You may select, at your option, one of the above-listed licenses.
   9  */
  10
  11 #ifndef ZSTD_CWKSP_H
  12 #define ZSTD_CWKSP_H
  13
  14 /*-*************************************
  15 *  Dependencies
  16 ***************************************/
  17 #include "../common/allocations.h"  /* ZSTD_customMalloc, ZSTD_customFree */
  18 #include "../common/zstd_internal.h"
  19 #include "../common/portability_macros.h"
  20
  21 #if defined (__cplusplus)
  22 extern "C" {
  23 #endif
  24
  25 /*-*************************************
  26 *  Constants
  27 ***************************************/
  28
  29 /* Since the workspace is effectively its own little malloc implementation /
  30  * arena, when we run under ASAN, we should similarly insert redzones between
  31  * each internal element of the workspace, so ASAN will catch overruns that
  32  * reach outside an object but that stay inside the workspace.
  33  *
  34  * This defines the size of that redzone.
  35  */
  36 #ifndef ZSTD_CWKSP_ASAN_REDZONE_SIZE
  37 #define ZSTD_CWKSP_ASAN_REDZONE_SIZE 128
  38 #endif
  39
  40
  41 /* Set our tables and aligneds to align by 64 bytes */
  42 #define ZSTD_CWKSP_ALIGNMENT_BYTES 64
  43
  44 /*-*************************************
  45 *  Structures
  46 ***************************************/
  47 typedef enum {
  48     ZSTD_cwksp_alloc_objects,
  49     ZSTD_cwksp_alloc_aligned_init_once,
  50     ZSTD_cwksp_alloc_aligned,
  51     ZSTD_cwksp_alloc_buffers
  52 } ZSTD_cwksp_alloc_phase_e;
  53
  54 /**
  55  * Used to describe whether the workspace is statically allocated (and will not
  56  * necessarily ever be freed), or if it's dynamically allocated and we can
  57  * expect a well-formed caller to free this.
  58  */
  59 typedef enum {
  60     ZSTD_cwksp_dynamic_alloc,
  61     ZSTD_cwksp_static_alloc
  62 } ZSTD_cwksp_static_alloc_e;
  63
  64 /**
  65  * Zstd fits all its internal datastructures into a single continuous buffer,
  66  * so that it only needs to perform a single OS allocation (or so that a buffer
  67  * can be provided to it and it can perform no allocations at all). This buffer
  68  * is called the workspace.
  69  *
  70  * Several optimizations complicate that process of allocating memory ranges
  71  * from this workspace for each internal datastructure:
  72  *
  73  * - These different internal datastructures have different setup requirements:
  74  *
  75  *   - The static objects need to be cleared once and can then be trivially
  76  *     reused for each compression.
  77  *
  78  *   - Various buffers don't need to be initialized at all--they are always
  79  *     written into before they're read.
  80  *
  81  *   - The matchstate tables have a unique requirement that they don't need
  82  *     their memory to be totally cleared, but they do need the memory to have
  83  *     some bound, i.e., a guarantee that all values in the memory they've been
  84  *     allocated is less than some maximum value (which is the starting value
  85  *     for the indices that they will then use for compression). When this
  86  *     guarantee is provided to them, they can use the memory without any setup
  87  *     work. When it can't, they have to clear the area.
  88  *
  89  * - These buffers also have different alignment requirements.
  90  *
  91  * - We would like to reuse the objects in the workspace for multiple
  92  *   compressions without having to perform any expensive reallocation or
  93  *   reinitialization work.
  94  *
  95  * - We would like to be able to efficiently reuse the workspace across
  96  *   multiple compressions **even when the compression parameters change** and
  97  *   we need to resize some of the objects (where possible).
  98  *
  99  * To attempt to manage this buffer, given these constraints, the ZSTD_cwksp
 100  * abstraction was created. It works as follows:
 101  *
 102  * Workspace Layout:
 103  *
 104  * [                        ... workspace ...                           ]
 105  * [objects][tables ->] free space [<- buffers][<- aligned][<- init once]
 106  *
 107  * The various objects that live in the workspace are divided into the
 108  * following categories, and are allocated separately:
 109  *
 110  * - Static objects: this is optionally the enclosing ZSTD_CCtx or ZSTD_CDict,
 111  *   so that literally everything fits in a single buffer. Note: if present,
 112  *   this must be the first object in the workspace, since ZSTD_customFree{CCtx,
 113  *   CDict}() rely on a pointer comparison to see whether one or two frees are
 114  *   required.
 115  *
 116  * - Fixed size objects: these are fixed-size, fixed-count objects that are
 117  *   nonetheless "dynamically" allocated in the workspace so that we can
 118  *   control how they're initialized separately from the broader ZSTD_CCtx.
 119  *   Examples:
 120  *   - Entropy Workspace
 121  *   - 2 x ZSTD_compressedBlockState_t
 122  *   - CDict dictionary contents
 123  *
 124  * - Tables: these are any of several different datastructures (hash tables,
 125  *   chain tables, binary trees) that all respect a common format: they are
 126  *   uint32_t arrays, all of whose values are between 0 and (nextSrc - base).
 127  *   Their sizes depend on the cparams. These tables are 64-byte aligned.
 128  *
 129  * - Init once: these buffers require to be initialized at least once before
 130  *   use. They should be used when we want to skip memory initialization
 131  *   while not triggering memory checkers (like Valgrind) when reading from
 132  *   from this memory without writing to it first.
 133  *   These buffers should be used carefully as they might contain data
 134  *   from previous compressions.
 135  *   Buffers are aligned to 64 bytes.
 136  *
 137  * - Aligned: these buffers don't require any initialization before they're
 138  *   used. The user of the buffer should make sure they write into a buffer
 139  *   location before reading from it.
 140  *   Buffers are aligned to 64 bytes.
 141  *
 142  * - Buffers: these buffers are used for various purposes that don't require
 143  *   any alignment or initialization before they're used. This means they can
 144  *   be moved around at no cost for a new compression.
 145  *
 146  * Allocating Memory:
 147  *
 148  * The various types of objects must be allocated in order, so they can be
 149  * correctly packed into the workspace buffer. That order is:
 150  *
 151  * 1. Objects
 152  * 2. Init once / Tables
 153  * 3. Aligned / Tables
 154  * 4. Buffers / Tables
 155  *
 156  * Attempts to reserve objects of different types out of order will fail.
 157  */
 158 typedef struct {
 159     void* workspace;
 160     void* workspaceEnd;
 161
 162     void* objectEnd;
 163     void* tableEnd;
 164     void* tableValidEnd;
 165     void* allocStart;
 166     void* initOnceStart;
 167
 168     BYTE allocFailed;
 169     int workspaceOversizedDuration;
 170     ZSTD_cwksp_alloc_phase_e phase;
 171     ZSTD_cwksp_static_alloc_e isStatic;
 172 } ZSTD_cwksp;
 173
 174 /*-*************************************
 175 *  Functions
 176 ***************************************/
 177
 178 MEM_STATIC size_t ZSTD_cwksp_available_space(ZSTD_cwksp* ws);
 179 MEM_STATIC void*  ZSTD_cwksp_initialAllocStart(ZSTD_cwksp* ws);
 180
 181 MEM_STATIC void ZSTD_cwksp_assert_internal_consistency(ZSTD_cwksp* ws) {
 182     (void)ws;
 183     assert(ws->workspace <= ws->objectEnd);
 184     assert(ws->objectEnd <= ws->tableEnd);
 185     assert(ws->objectEnd <= ws->tableValidEnd);
 186     assert(ws->tableEnd <= ws->allocStart);
 187     assert(ws->tableValidEnd <= ws->allocStart);
 188     assert(ws->allocStart <= ws->workspaceEnd);
 189     assert(ws->initOnceStart <= ZSTD_cwksp_initialAllocStart(ws));
 190     assert(ws->workspace <= ws->initOnceStart);
 191 #if ZSTD_MEMORY_SANITIZER
 192     {
 193         intptr_t const offset = __msan_test_shadow(ws->initOnceStart,
 194             (U8*)ZSTD_cwksp_initialAllocStart(ws) - (U8*)ws->initOnceStart);
 195         (void)offset;
 196 #if defined(ZSTD_MSAN_PRINT)
 197         if(offset!=-1) {
 198             __msan_print_shadow((U8*)ws->initOnceStart + offset - 8, 32);
 199         }
 200 #endif
 201         assert(offset==-1);
 202     };
 203 #endif
 204 }
 205
 206 /**
 207  * Align must be a power of 2.
 208  */
 209 MEM_STATIC size_t ZSTD_cwksp_align(size_t size, size_t const align) {
 210     size_t const mask = align - 1;
 211     assert((align & mask) == 0);
 212     return (size + mask) & ~mask;
 213 }
 214
 215 /**
 216  * Use this to determine how much space in the workspace we will consume to
 217  * allocate this object. (Normally it should be exactly the size of the object,
 218  * but under special conditions, like ASAN, where we pad each object, it might
 219  * be larger.)
 220  *
 221  * Since tables aren't currently redzoned, you don't need to call through this
 222  * to figure out how much space you need for the matchState tables. Everything
 223  * else is though.
 224  *
 225  * Do not use for sizing aligned buffers. Instead, use ZSTD_cwksp_aligned_alloc_size().
 226  */
 227 MEM_STATIC size_t ZSTD_cwksp_alloc_size(size_t size) {
 228     if (size == 0)
 229         return 0;
 230 #if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
 231     return size + 2 * ZSTD_CWKSP_ASAN_REDZONE_SIZE;
 232 #else
 233     return size;
 234 #endif
 235 }
 236
 237 /**
 238  * Returns an adjusted alloc size that is the nearest larger multiple of 64 bytes.
 239  * Used to determine the number of bytes required for a given "aligned".
 240  */
 241 MEM_STATIC size_t ZSTD_cwksp_aligned_alloc_size(size_t size) {
 242     return ZSTD_cwksp_alloc_size(ZSTD_cwksp_align(size, ZSTD_CWKSP_ALIGNMENT_BYTES));
 243 }
 244
 245 /**
 246  * Returns the amount of additional space the cwksp must allocate
 247  * for internal purposes (currently only alignment).
 248  */
 249 MEM_STATIC size_t ZSTD_cwksp_slack_space_required(void) {
 250     /* For alignment, the wksp will always allocate an additional 2*ZSTD_CWKSP_ALIGNMENT_BYTES
 251      * bytes to align the beginning of tables section and end of buffers;
 252      */
 253     size_t const slackSpace = ZSTD_CWKSP_ALIGNMENT_BYTES * 2;
 254     return slackSpace;
 255 }
 256
 257
 258 /**
 259  * Return the number of additional bytes required to align a pointer to the given number of bytes.
 260  * alignBytes must be a power of two.
 261  */
 262 MEM_STATIC size_t ZSTD_cwksp_bytes_to_align_ptr(void* ptr, const size_t alignBytes) {
 263     size_t const alignBytesMask = alignBytes - 1;
 264     size_t const bytes = (alignBytes - ((size_t)ptr & (alignBytesMask))) & alignBytesMask;
 265     assert((alignBytes & alignBytesMask) == 0);
 266     assert(bytes < alignBytes);
 267     return bytes;
 268 }
 269
 270 /**
 271  * Returns the initial value for allocStart which is used to determine the position from
 272  * which we can allocate from the end of the workspace.
 273  */
 274 MEM_STATIC void*  ZSTD_cwksp_initialAllocStart(ZSTD_cwksp* ws) {
 275     return (void*)((size_t)ws->workspaceEnd & ~(ZSTD_CWKSP_ALIGNMENT_BYTES-1));
 276 }
 277
 278 /**
 279  * Internal function. Do not use directly.
 280  * Reserves the given number of bytes within the aligned/buffer segment of the wksp,
 281  * which counts from the end of the wksp (as opposed to the object/table segment).
 282  *
 283  * Returns a pointer to the beginning of that space.
 284  */
 285 MEM_STATIC void*
 286 ZSTD_cwksp_reserve_internal_buffer_space(ZSTD_cwksp* ws, size_t const bytes)
 287 {
 288     void* const alloc = (BYTE*)ws->allocStart - bytes;
 289     void* const bottom = ws->tableEnd;
 290     DEBUGLOG(5, "cwksp: reserving %p %zd bytes, %zd bytes remaining",
 291         alloc, bytes, ZSTD_cwksp_available_space(ws) - bytes);
 292     ZSTD_cwksp_assert_internal_consistency(ws);
 293     assert(alloc >= bottom);
 294     if (alloc < bottom) {
 295         DEBUGLOG(4, "cwksp: alloc failed!");
 296         ws->allocFailed = 1;
 297         return NULL;
 298     }
 299     /* the area is reserved from the end of wksp.
 300      * If it overlaps with tableValidEnd, it voids guarantees on values' range */
 301     if (alloc < ws->tableValidEnd) {
 302         ws->tableValidEnd = alloc;
 303     }
 304     ws->allocStart = alloc;
 305     return alloc;
 306 }
 307
 308 /**
 309  * Moves the cwksp to the next phase, and does any necessary allocations.
 310  * cwksp initialization must necessarily go through each phase in order.
 311  * Returns a 0 on success, or zstd error
 312  */
 313 MEM_STATIC size_t
 314 ZSTD_cwksp_internal_advance_phase(ZSTD_cwksp* ws, ZSTD_cwksp_alloc_phase_e phase)
 315 {
 316     assert(phase >= ws->phase);
 317     if (phase > ws->phase) {
 318         /* Going from allocating objects to allocating initOnce / tables */
 319         if (ws->phase < ZSTD_cwksp_alloc_aligned_init_once &&
 320             phase >= ZSTD_cwksp_alloc_aligned_init_once) {
 321             ws->tableValidEnd = ws->objectEnd;
 322             ws->initOnceStart = ZSTD_cwksp_initialAllocStart(ws);
 323
 324             {   /* Align the start of the tables to 64 bytes. Use [0, 63] bytes */
 325                 void *const alloc = ws->objectEnd;
 326                 size_t const bytesToAlign = ZSTD_cwksp_bytes_to_align_ptr(alloc, ZSTD_CWKSP_ALIGNMENT_BYTES);
 327                 void *const objectEnd = (BYTE *) alloc + bytesToAlign;
 328                 DEBUGLOG(5, "reserving table alignment addtl space: %zu", bytesToAlign);
 329                 RETURN_ERROR_IF(objectEnd > ws->workspaceEnd, memory_allocation,
 330                                 "table phase - alignment initial allocation failed!");
 331                 ws->objectEnd = objectEnd;
 332                 ws->tableEnd = objectEnd;  /* table area starts being empty */
 333                 if (ws->tableValidEnd < ws->tableEnd) {
 334                     ws->tableValidEnd = ws->tableEnd;
 335                 }
 336             }
 337         }
 338         ws->phase = phase;
 339         ZSTD_cwksp_assert_internal_consistency(ws);
 340     }
 341     return 0;
 342 }
 343
 344 /**
 345  * Returns whether this object/buffer/etc was allocated in this workspace.
 346  */
 347 MEM_STATIC int ZSTD_cwksp_owns_buffer(const ZSTD_cwksp* ws, const void* ptr)
 348 {
 349     return (ptr != NULL) && (ws->workspace <= ptr) && (ptr < ws->workspaceEnd);
 350 }
 351
 352 /**
 353  * Internal function. Do not use directly.
 354  */
 355 MEM_STATIC void*
 356 ZSTD_cwksp_reserve_internal(ZSTD_cwksp* ws, size_t bytes, ZSTD_cwksp_alloc_phase_e phase)
 357 {
 358     void* alloc;
 359     if (ZSTD_isError(ZSTD_cwksp_internal_advance_phase(ws, phase)) || bytes == 0) {
 360         return NULL;
 361     }
 362
 363 #if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
 364     /* over-reserve space */
 365     bytes += 2 * ZSTD_CWKSP_ASAN_REDZONE_SIZE;
 366 #endif
 367
 368     alloc = ZSTD_cwksp_reserve_internal_buffer_space(ws, bytes);
 369
 370 #if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
 371     /* Move alloc so there's ZSTD_CWKSP_ASAN_REDZONE_SIZE unused space on
 372      * either size. */
 373     if (alloc) {
 374         alloc = (BYTE *)alloc + ZSTD_CWKSP_ASAN_REDZONE_SIZE;
 375         if (ws->isStatic == ZSTD_cwksp_dynamic_alloc) {
 376             /* We need to keep the redzone poisoned while unpoisoning the bytes that
 377              * are actually allocated. */
 378             __asan_unpoison_memory_region(alloc, bytes - 2 * ZSTD_CWKSP_ASAN_REDZONE_SIZE);
 379         }
 380     }
 381 #endif
 382
 383     return alloc;
 384 }
 385
 386 /**
 387  * Reserves and returns unaligned memory.
 388  */
 389 MEM_STATIC BYTE* ZSTD_cwksp_reserve_buffer(ZSTD_cwksp* ws, size_t bytes)
 390 {
 391     return (BYTE*)ZSTD_cwksp_reserve_internal(ws, bytes, ZSTD_cwksp_alloc_buffers);
 392 }
 393
 394 /**
 395  * Reserves and returns memory sized on and aligned on ZSTD_CWKSP_ALIGNMENT_BYTES (64 bytes).
 396  * This memory has been initialized at least once in the past.
 397  * This doesn't mean it has been initialized this time, and it might contain data from previous
 398  * operations.
 399  * The main usage is for algorithms that might need read access into uninitialized memory.
 400  * The algorithm must maintain safety under these conditions and must make sure it doesn't
 401  * leak any of the past data (directly or in side channels).
 402  */
 403 MEM_STATIC void* ZSTD_cwksp_reserve_aligned_init_once(ZSTD_cwksp* ws, size_t bytes)
 404 {
 405     size_t const alignedBytes = ZSTD_cwksp_align(bytes, ZSTD_CWKSP_ALIGNMENT_BYTES);
 406     void* ptr = ZSTD_cwksp_reserve_internal(ws, alignedBytes, ZSTD_cwksp_alloc_aligned_init_once);
 407     assert(((size_t)ptr & (ZSTD_CWKSP_ALIGNMENT_BYTES-1))== 0);
 408     if(ptr && ptr < ws->initOnceStart) {
 409         /* We assume the memory following the current allocation is either:
 410          * 1. Not usable as initOnce memory (end of workspace)
 411          * 2. Another initOnce buffer that has been allocated before (and so was previously memset)
 412          * 3. An ASAN redzone, in which case we don't want to write on it
 413          * For these reasons it should be fine to not explicitly zero every byte up to ws->initOnceStart.
 414          * Note that we assume here that MSAN and ASAN cannot run in the same time. */
 415         ZSTD_memset(ptr, 0, MIN((size_t)((U8*)ws->initOnceStart - (U8*)ptr), alignedBytes));
 416         ws->initOnceStart = ptr;
 417     }
 418 #if ZSTD_MEMORY_SANITIZER
 419     assert(__msan_test_shadow(ptr, bytes) == -1);
 420 #endif
 421     return ptr;
 422 }
 423
 424 /**
 425  * Reserves and returns memory sized on and aligned on ZSTD_CWKSP_ALIGNMENT_BYTES (64 bytes).
 426  */
 427 MEM_STATIC void* ZSTD_cwksp_reserve_aligned(ZSTD_cwksp* ws, size_t bytes)
 428 {
 429     void* ptr = ZSTD_cwksp_reserve_internal(ws, ZSTD_cwksp_align(bytes, ZSTD_CWKSP_ALIGNMENT_BYTES),
 430                                             ZSTD_cwksp_alloc_aligned);
 431     assert(((size_t)ptr & (ZSTD_CWKSP_ALIGNMENT_BYTES-1))== 0);
 432     return ptr;
 433 }
 434
 435 /**
 436  * Aligned on 64 bytes. These buffers have the special property that
 437  * their values remain constrained, allowing us to reuse them without
 438  * memset()-ing them.
 439  */
 440 MEM_STATIC void* ZSTD_cwksp_reserve_table(ZSTD_cwksp* ws, size_t bytes)
 441 {
 442     const ZSTD_cwksp_alloc_phase_e phase = ZSTD_cwksp_alloc_aligned_init_once;
 443     void* alloc;
 444     void* end;
 445     void* top;
 446
 447     /* We can only start allocating tables after we are done reserving space for objects at the
 448      * start of the workspace */
 449     if(ws->phase < phase) {
 450         if (ZSTD_isError(ZSTD_cwksp_internal_advance_phase(ws, phase))) {
 451             return NULL;
 452         }
 453     }
 454     alloc = ws->tableEnd;
 455     end = (BYTE *)alloc + bytes;
 456     top = ws->allocStart;
 457
 458     DEBUGLOG(5, "cwksp: reserving %p table %zd bytes, %zd bytes remaining",
 459         alloc, bytes, ZSTD_cwksp_available_space(ws) - bytes);
 460     assert((bytes & (sizeof(U32)-1)) == 0);
 461     ZSTD_cwksp_assert_internal_consistency(ws);
 462     assert(end <= top);
 463     if (end > top) {
 464         DEBUGLOG(4, "cwksp: table alloc failed!");
 465         ws->allocFailed = 1;
 466         return NULL;
 467     }
 468     ws->tableEnd = end;
 469
 470 #if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
 471     if (ws->isStatic == ZSTD_cwksp_dynamic_alloc) {
 472         __asan_unpoison_memory_region(alloc, bytes);
 473     }
 474 #endif
 475
 476     assert((bytes & (ZSTD_CWKSP_ALIGNMENT_BYTES-1)) == 0);
 477     assert(((size_t)alloc & (ZSTD_CWKSP_ALIGNMENT_BYTES-1))== 0);
 478     return alloc;
 479 }
 480
 481 /**
 482  * Aligned on sizeof(void*).
 483  * Note : should happen only once, at workspace first initialization
 484  */
 485 MEM_STATIC void* ZSTD_cwksp_reserve_object(ZSTD_cwksp* ws, size_t bytes)
 486 {
 487     size_t const roundedBytes = ZSTD_cwksp_align(bytes, sizeof(void*));
 488     void* alloc = ws->objectEnd;
 489     void* end = (BYTE*)alloc + roundedBytes;
 490
 491 #if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
 492     /* over-reserve space */
 493     end = (BYTE *)end + 2 * ZSTD_CWKSP_ASAN_REDZONE_SIZE;
 494 #endif
 495
 496     DEBUGLOG(4,
 497         "cwksp: reserving %p object %zd bytes (rounded to %zd), %zd bytes remaining",
 498         alloc, bytes, roundedBytes, ZSTD_cwksp_available_space(ws) - roundedBytes);
 499     assert((size_t)alloc % ZSTD_ALIGNOF(void*) == 0);
 500     assert(bytes % ZSTD_ALIGNOF(void*) == 0);
 501     ZSTD_cwksp_assert_internal_consistency(ws);
 502     /* we must be in the first phase, no advance is possible */
 503     if (ws->phase != ZSTD_cwksp_alloc_objects || end > ws->workspaceEnd) {
 504         DEBUGLOG(3, "cwksp: object alloc failed!");
 505         ws->allocFailed = 1;
 506         return NULL;
 507     }
 508     ws->objectEnd = end;
 509     ws->tableEnd = end;
 510     ws->tableValidEnd = end;
 511
 512 #if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
 513     /* Move alloc so there's ZSTD_CWKSP_ASAN_REDZONE_SIZE unused space on
 514      * either size. */
 515     alloc = (BYTE*)alloc + ZSTD_CWKSP_ASAN_REDZONE_SIZE;
 516     if (ws->isStatic == ZSTD_cwksp_dynamic_alloc) {
 517         __asan_unpoison_memory_region(alloc, bytes);
 518     }
 519 #endif
 520
 521     return alloc;
 522 }
 523
 524 MEM_STATIC void ZSTD_cwksp_mark_tables_dirty(ZSTD_cwksp* ws)
 525 {
 526     DEBUGLOG(4, "cwksp: ZSTD_cwksp_mark_tables_dirty");
 527
 528 #if ZSTD_MEMORY_SANITIZER && !defined (ZSTD_MSAN_DONT_POISON_WORKSPACE)
 529     /* To validate that the table reuse logic is sound, and that we don't
 530      * access table space that we haven't cleaned, we re-"poison" the table
 531      * space every time we mark it dirty.
 532      * Since tableValidEnd space and initOnce space may overlap we don't poison
 533      * the initOnce portion as it break its promise. This means that this poisoning
 534      * check isn't always applied fully. */
 535     {
 536         size_t size = (BYTE*)ws->tableValidEnd - (BYTE*)ws->objectEnd;
 537         assert(__msan_test_shadow(ws->objectEnd, size) == -1);
 538         if((BYTE*)ws->tableValidEnd < (BYTE*)ws->initOnceStart) {
 539             __msan_poison(ws->objectEnd, size);
 540         } else {
 541             assert(ws->initOnceStart >= ws->objectEnd);
 542             __msan_poison(ws->objectEnd, (BYTE*)ws->initOnceStart - (BYTE*)ws->objectEnd);
 543         }
 544     }
 545 #endif
 546
 547     assert(ws->tableValidEnd >= ws->objectEnd);
 548     assert(ws->tableValidEnd <= ws->allocStart);
 549     ws->tableValidEnd = ws->objectEnd;
 550     ZSTD_cwksp_assert_internal_consistency(ws);
 551 }
 552
 553 MEM_STATIC void ZSTD_cwksp_mark_tables_clean(ZSTD_cwksp* ws) {
 554     DEBUGLOG(4, "cwksp: ZSTD_cwksp_mark_tables_clean");
 555     assert(ws->tableValidEnd >= ws->objectEnd);
 556     assert(ws->tableValidEnd <= ws->allocStart);
 557     if (ws->tableValidEnd < ws->tableEnd) {
 558         ws->tableValidEnd = ws->tableEnd;
 559     }
 560     ZSTD_cwksp_assert_internal_consistency(ws);
 561 }
 562
 563 /**
 564  * Zero the part of the allocated tables not already marked clean.
 565  */
 566 MEM_STATIC void ZSTD_cwksp_clean_tables(ZSTD_cwksp* ws) {
 567     DEBUGLOG(4, "cwksp: ZSTD_cwksp_clean_tables");
 568     assert(ws->tableValidEnd >= ws->objectEnd);
 569     assert(ws->tableValidEnd <= ws->allocStart);
 570     if (ws->tableValidEnd < ws->tableEnd) {
 571         ZSTD_memset(ws->tableValidEnd, 0, (size_t)((BYTE*)ws->tableEnd - (BYTE*)ws->tableValidEnd));
 572     }
 573     ZSTD_cwksp_mark_tables_clean(ws);
 574 }
 575
 576 /**
 577  * Invalidates table allocations.
 578  * All other allocations remain valid.
 579  */
 580 MEM_STATIC void ZSTD_cwksp_clear_tables(ZSTD_cwksp* ws) {
 581     DEBUGLOG(4, "cwksp: clearing tables!");
 582
 583 #if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
 584     /* We don't do this when the workspace is statically allocated, because
 585      * when that is the case, we have no capability to hook into the end of the
 586      * workspace's lifecycle to unpoison the memory.
 587      */
 588     if (ws->isStatic == ZSTD_cwksp_dynamic_alloc) {
 589         size_t size = (BYTE*)ws->tableValidEnd - (BYTE*)ws->objectEnd;
 590         __asan_poison_memory_region(ws->objectEnd, size);
 591     }
 592 #endif
 593
 594     ws->tableEnd = ws->objectEnd;
 595     ZSTD_cwksp_assert_internal_consistency(ws);
 596 }
 597
 598 /**
 599  * Invalidates all buffer, aligned, and table allocations.
 600  * Object allocations remain valid.
 601  */
 602 MEM_STATIC void ZSTD_cwksp_clear(ZSTD_cwksp* ws) {
 603     DEBUGLOG(4, "cwksp: clearing!");
 604
 605 #if ZSTD_MEMORY_SANITIZER && !defined (ZSTD_MSAN_DONT_POISON_WORKSPACE)
 606     /* To validate that the context reuse logic is sound, and that we don't
 607      * access stuff that this compression hasn't initialized, we re-"poison"
 608      * the workspace except for the areas in which we expect memory reuse
 609      * without initialization (objects, valid tables area and init once
 610      * memory). */
 611     {
 612         if((BYTE*)ws->tableValidEnd < (BYTE*)ws->initOnceStart) {
 613             size_t size = (BYTE*)ws->initOnceStart - (BYTE*)ws->tableValidEnd;
 614             __msan_poison(ws->tableValidEnd, size);
 615         }
 616     }
 617 #endif
 618
 619 #if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
 620     /* We don't do this when the workspace is statically allocated, because
 621      * when that is the case, we have no capability to hook into the end of the
 622      * workspace's lifecycle to unpoison the memory.
 623      */
 624     if (ws->isStatic == ZSTD_cwksp_dynamic_alloc) {
 625         size_t size = (BYTE*)ws->workspaceEnd - (BYTE*)ws->objectEnd;
 626         __asan_poison_memory_region(ws->objectEnd, size);
 627     }
 628 #endif
 629
 630     ws->tableEnd = ws->objectEnd;
 631     ws->allocStart = ZSTD_cwksp_initialAllocStart(ws);
 632     ws->allocFailed = 0;
 633     if (ws->phase > ZSTD_cwksp_alloc_aligned_init_once) {
 634         ws->phase = ZSTD_cwksp_alloc_aligned_init_once;
 635     }
 636     ZSTD_cwksp_assert_internal_consistency(ws);
 637 }
 638
 639 MEM_STATIC size_t ZSTD_cwksp_sizeof(const ZSTD_cwksp* ws) {
 640     return (size_t)((BYTE*)ws->workspaceEnd - (BYTE*)ws->workspace);
 641 }
 642
 643 MEM_STATIC size_t ZSTD_cwksp_used(const ZSTD_cwksp* ws) {
 644     return (size_t)((BYTE*)ws->tableEnd - (BYTE*)ws->workspace)
 645          + (size_t)((BYTE*)ws->workspaceEnd - (BYTE*)ws->allocStart);
 646 }
 647
 648 /**
 649  * The provided workspace takes ownership of the buffer [start, start+size).
 650  * Any existing values in the workspace are ignored (the previously managed
 651  * buffer, if present, must be separately freed).
 652  */
 653 MEM_STATIC void ZSTD_cwksp_init(ZSTD_cwksp* ws, void* start, size_t size, ZSTD_cwksp_static_alloc_e isStatic) {
 654     DEBUGLOG(4, "cwksp: init'ing workspace with %zd bytes", size);
 655     assert(((size_t)start & (sizeof(void*)-1)) == 0); /* ensure correct alignment */
 656     ws->workspace = start;
 657     ws->workspaceEnd = (BYTE*)start + size;
 658     ws->objectEnd = ws->workspace;
 659     ws->tableValidEnd = ws->objectEnd;
 660     ws->initOnceStart = ZSTD_cwksp_initialAllocStart(ws);
 661     ws->phase = ZSTD_cwksp_alloc_objects;
 662     ws->isStatic = isStatic;
 663     ZSTD_cwksp_clear(ws);
 664     ws->workspaceOversizedDuration = 0;
 665     ZSTD_cwksp_assert_internal_consistency(ws);
 666 }
 667
 668 MEM_STATIC size_t ZSTD_cwksp_create(ZSTD_cwksp* ws, size_t size, ZSTD_customMem customMem) {
 669     void* workspace = ZSTD_customMalloc(size, customMem);
 670     DEBUGLOG(4, "cwksp: creating new workspace with %zd bytes", size);
 671     RETURN_ERROR_IF(workspace == NULL, memory_allocation, "NULL pointer!");
 672     ZSTD_cwksp_init(ws, workspace, size, ZSTD_cwksp_dynamic_alloc);
 673     return 0;
 674 }
 675
 676 MEM_STATIC void ZSTD_cwksp_free(ZSTD_cwksp* ws, ZSTD_customMem customMem) {
 677     void *ptr = ws->workspace;
 678     DEBUGLOG(4, "cwksp: freeing workspace");
 679 #if ZSTD_MEMORY_SANITIZER && !defined(ZSTD_MSAN_DONT_POISON_WORKSPACE)
 680     if (ptr != NULL && customMem.customFree != NULL) {
 681         __msan_unpoison(ptr, ZSTD_cwksp_sizeof(ws));
 682     }
 683 #endif
 684     ZSTD_memset(ws, 0, sizeof(ZSTD_cwksp));
 685     ZSTD_customFree(ptr, customMem);
 686 }
 687
 688 /**
 689  * Moves the management of a workspace from one cwksp to another. The src cwksp
 690  * is left in an invalid state (src must be re-init()'ed before it's used again).
 691  */
 692 MEM_STATIC void ZSTD_cwksp_move(ZSTD_cwksp* dst, ZSTD_cwksp* src) {
 693     *dst = *src;
 694     ZSTD_memset(src, 0, sizeof(ZSTD_cwksp));
 695 }
 696
 697 MEM_STATIC int ZSTD_cwksp_reserve_failed(const ZSTD_cwksp* ws) {
 698     return ws->allocFailed;
 699 }
 700
 701 /*-*************************************
 702 *  Functions Checking Free Space
 703 ***************************************/
 704
 705 /* ZSTD_alignmentSpaceWithinBounds() :
 706  * Returns if the estimated space needed for a wksp is within an acceptable limit of the
 707  * actual amount of space used.
 708  */
 709 MEM_STATIC int ZSTD_cwksp_estimated_space_within_bounds(const ZSTD_cwksp *const ws, size_t const estimatedSpace) {
 710     /* We have an alignment space between objects and tables between tables and buffers, so we can have up to twice
 711      * the alignment bytes difference between estimation and actual usage */
 712     return (estimatedSpace - ZSTD_cwksp_slack_space_required()) <= ZSTD_cwksp_used(ws) &&
 713            ZSTD_cwksp_used(ws) <= estimatedSpace;
 714 }
 715
 716
 717 MEM_STATIC size_t ZSTD_cwksp_available_space(ZSTD_cwksp* ws) {
 718     return (size_t)((BYTE*)ws->allocStart - (BYTE*)ws->tableEnd);
 719 }
 720
 721 MEM_STATIC int ZSTD_cwksp_check_available(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
 722     return ZSTD_cwksp_available_space(ws) >= additionalNeededSpace;
 723 }
 724
 725 MEM_STATIC int ZSTD_cwksp_check_too_large(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
 726     return ZSTD_cwksp_check_available(
 727         ws, additionalNeededSpace * ZSTD_WORKSPACETOOLARGE_FACTOR);
 728 }
 729
 730 MEM_STATIC int ZSTD_cwksp_check_wasteful(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
 731     return ZSTD_cwksp_check_too_large(ws, additionalNeededSpace)
 732         && ws->workspaceOversizedDuration > ZSTD_WORKSPACETOOLARGE_MAXDURATION;
 733 }
 734
 735 MEM_STATIC void ZSTD_cwksp_bump_oversized_duration(
 736         ZSTD_cwksp* ws, size_t additionalNeededSpace) {
 737     if (ZSTD_cwksp_check_too_large(ws, additionalNeededSpace)) {
 738         ws->workspaceOversizedDuration++;
 739     } else {
 740         ws->workspaceOversizedDuration = 0;
 741     }
 742 }
 743
 744 #if defined (__cplusplus)
 745 }
 746 #endif
 747
 748 #endif /* ZSTD_CWKSP_H */