/* * Copyright (c) Meta Platforms, Inc. and affiliates. * All rights reserved. * * This source code is licensed under both the BSD-style license (found in the * LICENSE file in the root directory of this source tree) and the GPLv2 (found * in the COPYING file in the root directory of this source tree). * You may select, at your option, one of the above-listed licenses. */ #ifndef ZSTD_CWKSP_H #define ZSTD_CWKSP_H /*-************************************* * Dependencies ***************************************/ #include "../common/allocations.h" /* ZSTD_customMalloc, ZSTD_customFree */ #include "../common/zstd_internal.h" #include "../common/portability_macros.h" #if defined (__cplusplus) extern "C" { #endif /*-************************************* * Constants ***************************************/ /* Since the workspace is effectively its own little malloc implementation / * arena, when we run under ASAN, we should similarly insert redzones between * each internal element of the workspace, so ASAN will catch overruns that * reach outside an object but that stay inside the workspace. * * This defines the size of that redzone. */ #ifndef ZSTD_CWKSP_ASAN_REDZONE_SIZE #define ZSTD_CWKSP_ASAN_REDZONE_SIZE … #endif /* Set our tables and aligneds to align by 64 bytes */ #define ZSTD_CWKSP_ALIGNMENT_BYTES … /*-************************************* * Structures ***************************************/ ZSTD_cwksp_alloc_phase_e; /** * Used to describe whether the workspace is statically allocated (and will not * necessarily ever be freed), or if it's dynamically allocated and we can * expect a well-formed caller to free this. */ ZSTD_cwksp_static_alloc_e; /** * Zstd fits all its internal datastructures into a single continuous buffer, * so that it only needs to perform a single OS allocation (or so that a buffer * can be provided to it and it can perform no allocations at all). This buffer * is called the workspace. * * Several optimizations complicate that process of allocating memory ranges * from this workspace for each internal datastructure: * * - These different internal datastructures have different setup requirements: * * - The static objects need to be cleared once and can then be trivially * reused for each compression. * * - Various buffers don't need to be initialized at all--they are always * written into before they're read. * * - The matchstate tables have a unique requirement that they don't need * their memory to be totally cleared, but they do need the memory to have * some bound, i.e., a guarantee that all values in the memory they've been * allocated is less than some maximum value (which is the starting value * for the indices that they will then use for compression). When this * guarantee is provided to them, they can use the memory without any setup * work. When it can't, they have to clear the area. * * - These buffers also have different alignment requirements. * * - We would like to reuse the objects in the workspace for multiple * compressions without having to perform any expensive reallocation or * reinitialization work. * * - We would like to be able to efficiently reuse the workspace across * multiple compressions **even when the compression parameters change** and * we need to resize some of the objects (where possible). * * To attempt to manage this buffer, given these constraints, the ZSTD_cwksp * abstraction was created. It works as follows: * * Workspace Layout: * * [ ... workspace ... ] * [objects][tables ->] free space [<- buffers][<- aligned][<- init once] * * The various objects that live in the workspace are divided into the * following categories, and are allocated separately: * * - Static objects: this is optionally the enclosing ZSTD_CCtx or ZSTD_CDict, * so that literally everything fits in a single buffer. Note: if present, * this must be the first object in the workspace, since ZSTD_customFree{CCtx, * CDict}() rely on a pointer comparison to see whether one or two frees are * required. * * - Fixed size objects: these are fixed-size, fixed-count objects that are * nonetheless "dynamically" allocated in the workspace so that we can * control how they're initialized separately from the broader ZSTD_CCtx. * Examples: * - Entropy Workspace * - 2 x ZSTD_compressedBlockState_t * - CDict dictionary contents * * - Tables: these are any of several different datastructures (hash tables, * chain tables, binary trees) that all respect a common format: they are * uint32_t arrays, all of whose values are between 0 and (nextSrc - base). * Their sizes depend on the cparams. These tables are 64-byte aligned. * * - Init once: these buffers require to be initialized at least once before * use. They should be used when we want to skip memory initialization * while not triggering memory checkers (like Valgrind) when reading from * from this memory without writing to it first. * These buffers should be used carefully as they might contain data * from previous compressions. * Buffers are aligned to 64 bytes. * * - Aligned: these buffers don't require any initialization before they're * used. The user of the buffer should make sure they write into a buffer * location before reading from it. * Buffers are aligned to 64 bytes. * * - Buffers: these buffers are used for various purposes that don't require * any alignment or initialization before they're used. This means they can * be moved around at no cost for a new compression. * * Allocating Memory: * * The various types of objects must be allocated in order, so they can be * correctly packed into the workspace buffer. That order is: * * 1. Objects * 2. Init once / Tables * 3. Aligned / Tables * 4. Buffers / Tables * * Attempts to reserve objects of different types out of order will fail. */ ZSTD_cwksp; /*-************************************* * Functions ***************************************/ MEM_STATIC size_t ZSTD_cwksp_available_space(ZSTD_cwksp* ws); MEM_STATIC void* ZSTD_cwksp_initialAllocStart(ZSTD_cwksp* ws); MEM_STATIC void ZSTD_cwksp_assert_internal_consistency(ZSTD_cwksp* ws) { … } /** * Align must be a power of 2. */ MEM_STATIC size_t ZSTD_cwksp_align(size_t size, size_t const align) { … } /** * Use this to determine how much space in the workspace we will consume to * allocate this object. (Normally it should be exactly the size of the object, * but under special conditions, like ASAN, where we pad each object, it might * be larger.) * * Since tables aren't currently redzoned, you don't need to call through this * to figure out how much space you need for the matchState tables. Everything * else is though. * * Do not use for sizing aligned buffers. Instead, use ZSTD_cwksp_aligned_alloc_size(). */ MEM_STATIC size_t ZSTD_cwksp_alloc_size(size_t size) { … } /** * Returns an adjusted alloc size that is the nearest larger multiple of 64 bytes. * Used to determine the number of bytes required for a given "aligned". */ MEM_STATIC size_t ZSTD_cwksp_aligned_alloc_size(size_t size) { … } /** * Returns the amount of additional space the cwksp must allocate * for internal purposes (currently only alignment). */ MEM_STATIC size_t ZSTD_cwksp_slack_space_required(void) { … } /** * Return the number of additional bytes required to align a pointer to the given number of bytes. * alignBytes must be a power of two. */ MEM_STATIC size_t ZSTD_cwksp_bytes_to_align_ptr(void* ptr, const size_t alignBytes) { … } /** * Returns the initial value for allocStart which is used to determine the position from * which we can allocate from the end of the workspace. */ MEM_STATIC void* ZSTD_cwksp_initialAllocStart(ZSTD_cwksp* ws) { … } /** * Internal function. Do not use directly. * Reserves the given number of bytes within the aligned/buffer segment of the wksp, * which counts from the end of the wksp (as opposed to the object/table segment). * * Returns a pointer to the beginning of that space. */ MEM_STATIC void* ZSTD_cwksp_reserve_internal_buffer_space(ZSTD_cwksp* ws, size_t const bytes) { … } /** * Moves the cwksp to the next phase, and does any necessary allocations. * cwksp initialization must necessarily go through each phase in order. * Returns a 0 on success, or zstd error */ MEM_STATIC size_t ZSTD_cwksp_internal_advance_phase(ZSTD_cwksp* ws, ZSTD_cwksp_alloc_phase_e phase) { … } /** * Returns whether this object/buffer/etc was allocated in this workspace. */ MEM_STATIC int ZSTD_cwksp_owns_buffer(const ZSTD_cwksp* ws, const void* ptr) { … } /** * Internal function. Do not use directly. */ MEM_STATIC void* ZSTD_cwksp_reserve_internal(ZSTD_cwksp* ws, size_t bytes, ZSTD_cwksp_alloc_phase_e phase) { … } /** * Reserves and returns unaligned memory. */ MEM_STATIC BYTE* ZSTD_cwksp_reserve_buffer(ZSTD_cwksp* ws, size_t bytes) { … } /** * Reserves and returns memory sized on and aligned on ZSTD_CWKSP_ALIGNMENT_BYTES (64 bytes). * This memory has been initialized at least once in the past. * This doesn't mean it has been initialized this time, and it might contain data from previous * operations. * The main usage is for algorithms that might need read access into uninitialized memory. * The algorithm must maintain safety under these conditions and must make sure it doesn't * leak any of the past data (directly or in side channels). */ MEM_STATIC void* ZSTD_cwksp_reserve_aligned_init_once(ZSTD_cwksp* ws, size_t bytes) { … } /** * Reserves and returns memory sized on and aligned on ZSTD_CWKSP_ALIGNMENT_BYTES (64 bytes). */ MEM_STATIC void* ZSTD_cwksp_reserve_aligned(ZSTD_cwksp* ws, size_t bytes) { … } /** * Aligned on 64 bytes. These buffers have the special property that * their values remain constrained, allowing us to reuse them without * memset()-ing them. */ MEM_STATIC void* ZSTD_cwksp_reserve_table(ZSTD_cwksp* ws, size_t bytes) { … } /** * Aligned on sizeof(void*). * Note : should happen only once, at workspace first initialization */ MEM_STATIC void* ZSTD_cwksp_reserve_object(ZSTD_cwksp* ws, size_t bytes) { … } MEM_STATIC void ZSTD_cwksp_mark_tables_dirty(ZSTD_cwksp* ws) { … } MEM_STATIC void ZSTD_cwksp_mark_tables_clean(ZSTD_cwksp* ws) { … } /** * Zero the part of the allocated tables not already marked clean. */ MEM_STATIC void ZSTD_cwksp_clean_tables(ZSTD_cwksp* ws) { … } /** * Invalidates table allocations. * All other allocations remain valid. */ MEM_STATIC void ZSTD_cwksp_clear_tables(ZSTD_cwksp* ws) { … } /** * Invalidates all buffer, aligned, and table allocations. * Object allocations remain valid. */ MEM_STATIC void ZSTD_cwksp_clear(ZSTD_cwksp* ws) { … } MEM_STATIC size_t ZSTD_cwksp_sizeof(const ZSTD_cwksp* ws) { … } MEM_STATIC size_t ZSTD_cwksp_used(const ZSTD_cwksp* ws) { … } /** * The provided workspace takes ownership of the buffer [start, start+size). * Any existing values in the workspace are ignored (the previously managed * buffer, if present, must be separately freed). */ MEM_STATIC void ZSTD_cwksp_init(ZSTD_cwksp* ws, void* start, size_t size, ZSTD_cwksp_static_alloc_e isStatic) { … } MEM_STATIC size_t ZSTD_cwksp_create(ZSTD_cwksp* ws, size_t size, ZSTD_customMem customMem) { … } MEM_STATIC void ZSTD_cwksp_free(ZSTD_cwksp* ws, ZSTD_customMem customMem) { … } /** * Moves the management of a workspace from one cwksp to another. The src cwksp * is left in an invalid state (src must be re-init()'ed before it's used again). */ MEM_STATIC void ZSTD_cwksp_move(ZSTD_cwksp* dst, ZSTD_cwksp* src) { … } MEM_STATIC int ZSTD_cwksp_reserve_failed(const ZSTD_cwksp* ws) { … } /*-************************************* * Functions Checking Free Space ***************************************/ /* ZSTD_alignmentSpaceWithinBounds() : * Returns if the estimated space needed for a wksp is within an acceptable limit of the * actual amount of space used. */ MEM_STATIC int ZSTD_cwksp_estimated_space_within_bounds(const ZSTD_cwksp *const ws, size_t const estimatedSpace) { … } MEM_STATIC size_t ZSTD_cwksp_available_space(ZSTD_cwksp* ws) { … } MEM_STATIC int ZSTD_cwksp_check_available(ZSTD_cwksp* ws, size_t additionalNeededSpace) { … } MEM_STATIC int ZSTD_cwksp_check_too_large(ZSTD_cwksp* ws, size_t additionalNeededSpace) { … } MEM_STATIC int ZSTD_cwksp_check_wasteful(ZSTD_cwksp* ws, size_t additionalNeededSpace) { … } MEM_STATIC void ZSTD_cwksp_bump_oversized_duration( ZSTD_cwksp* ws, size_t additionalNeededSpace) { … } #if defined (__cplusplus) } #endif #endif /* ZSTD_CWKSP_H */