zstd_cwksp.h

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