5  * This source code is licensed under both the BSD-style license (found in the
8  * You may select, at your option, one of the above-listed licenses.
14 /*-*************************************
20 /*-*************************************
35 /*-*************************************
47  * expect a well-formed caller to free this.
55  * Zstd fits all its internal datastructures into a single continuous buffer,
56  * so that it only needs to perform a single OS allocation (or so that a buffer
63  * - These different internal datastructures have different setup requirements:
65  *   - The static objects need to be cleared once and can then be trivially
68  *   - Various buffers don't need to be initialized at all--they are always
71  *   - The matchstate tables have a unique requirement that they don't need
79  * - These buffers also have different alignment requirements.
81  * - We would like to reuse the objects in the workspace for multiple
85  * - We would like to be able to efficiently reuse the workspace across
95  * [objects][tables ... ->] free space [<- ... aligned][<- ... buffers]
100  * - Static objects: this is optionally the enclosing ZSTD_CCtx or ZSTD_CDict,
101  *   so that literally everything fits in a single buffer. Note: if present,
106  * - Fixed size objects: these are fixed-size, fixed-count objects that are
110  *   - Entropy Workspace
111  *   - 2 x ZSTD_compressedBlockState_t
112  *   - CDict dictionary contents
114  * - Tables: these are any of several different datastructures (hash tables,
116  *   uint32_t arrays, all of whose values are between 0 and (nextSrc - base).
119  * - Aligned: these buffers are used for various purposes that require 4 byte
122  * - Buffers: these buffers are used for various purposes that don't require
149     ZSTD_cwksp_alloc_phase_e phase;  member
153 /*-*************************************
161     assert(ws->workspace <= ws->objectEnd);  in ZSTD_cwksp_assert_internal_consistency()
162     assert(ws->objectEnd <= ws->tableEnd);  in ZSTD_cwksp_assert_internal_consistency()
163     assert(ws->objectEnd <= ws->tableValidEnd);  in ZSTD_cwksp_assert_internal_consistency()
164     assert(ws->tableEnd <= ws->allocStart);  in ZSTD_cwksp_assert_internal_consistency()
165     assert(ws->tableValidEnd <= ws->allocStart);  in ZSTD_cwksp_assert_internal_consistency()
166     assert(ws->allocStart <= ws->workspaceEnd);  in ZSTD_cwksp_assert_internal_consistency()
173     size_t const mask = align - 1;  in ZSTD_cwksp_align()
195         ZSTD_cwksp* ws, ZSTD_cwksp_alloc_phase_e phase) {  in ZSTD_cwksp_internal_advance_phase()  argument
196     assert(phase >= ws->phase);  in ZSTD_cwksp_internal_advance_phase()
197     if (phase > ws->phase) {  in ZSTD_cwksp_internal_advance_phase()
198         if (ws->phase < ZSTD_cwksp_alloc_buffers &&  in ZSTD_cwksp_internal_advance_phase()
199                 phase >= ZSTD_cwksp_alloc_buffers) {  in ZSTD_cwksp_internal_advance_phase()
200             ws->tableValidEnd = ws->objectEnd;  in ZSTD_cwksp_internal_advance_phase()
202         if (ws->phase < ZSTD_cwksp_alloc_aligned &&  in ZSTD_cwksp_internal_advance_phase()
203                 phase >= ZSTD_cwksp_alloc_aligned) {  in ZSTD_cwksp_internal_advance_phase()
204             /* If unaligned allocations down from a too-large top have left us  in ZSTD_cwksp_internal_advance_phase()
211             ws->allocStart = (BYTE*)ws->allocStart - ((size_t)ws->allocStart & (sizeof(U32)-1));  in ZSTD_cwksp_internal_advance_phase()
212             if (ws->allocStart < ws->tableValidEnd) {  in ZSTD_cwksp_internal_advance_phase()
213                 ws->tableValidEnd = ws->allocStart;  in ZSTD_cwksp_internal_advance_phase()
216         ws->phase = phase;  in ZSTD_cwksp_internal_advance_phase()
224     return (ptr != NULL) && (ws->workspace <= ptr) && (ptr <= ws->workspaceEnd);  in ZSTD_cwksp_owns_buffer()
231         ZSTD_cwksp* ws, size_t bytes, ZSTD_cwksp_alloc_phase_e phase) {  in ZSTD_cwksp_reserve_internal()  argument
233     void* bottom = ws->tableEnd;  in ZSTD_cwksp_reserve_internal()
234     ZSTD_cwksp_internal_advance_phase(ws, phase);  in ZSTD_cwksp_reserve_internal()
235     alloc = (BYTE *)ws->allocStart - bytes;  in ZSTD_cwksp_reserve_internal()
242         alloc, bytes, ZSTD_cwksp_available_space(ws) - bytes);  in ZSTD_cwksp_reserve_internal()
247         ws->allocFailed = 1;  in ZSTD_cwksp_reserve_internal()
250     if (alloc < ws->tableValidEnd) {  in ZSTD_cwksp_reserve_internal()
251         ws->tableValidEnd = alloc;  in ZSTD_cwksp_reserve_internal()
253     ws->allocStart = alloc;  in ZSTD_cwksp_reserve_internal()
270     assert((bytes & (sizeof(U32)-1)) == 0);  in ZSTD_cwksp_reserve_aligned()
276  * their values remain constrained, allowing us to re-use them without
277  * memset()-ing them.
280     const ZSTD_cwksp_alloc_phase_e phase = ZSTD_cwksp_alloc_aligned;  in ZSTD_cwksp_reserve_table()  local
281     void* alloc = ws->tableEnd;  in ZSTD_cwksp_reserve_table()
283     void* top = ws->allocStart;  in ZSTD_cwksp_reserve_table()
286         alloc, bytes, ZSTD_cwksp_available_space(ws) - bytes);  in ZSTD_cwksp_reserve_table()
287     assert((bytes & (sizeof(U32)-1)) == 0);  in ZSTD_cwksp_reserve_table()
288     ZSTD_cwksp_internal_advance_phase(ws, phase);  in ZSTD_cwksp_reserve_table()
293         ws->allocFailed = 1;  in ZSTD_cwksp_reserve_table()
296     ws->tableEnd = end;  in ZSTD_cwksp_reserve_table()
307     void* alloc = ws->objectEnd;  in ZSTD_cwksp_reserve_object()
313         alloc, bytes, roundedBytes, ZSTD_cwksp_available_space(ws) - roundedBytes);  in ZSTD_cwksp_reserve_object()
314     assert(((size_t)alloc & (sizeof(void*)-1)) == 0);  in ZSTD_cwksp_reserve_object()
315     assert((bytes & (sizeof(void*)-1)) == 0);  in ZSTD_cwksp_reserve_object()
317     /* we must be in the first phase, no advance is possible */  in ZSTD_cwksp_reserve_object()
318     if (ws->phase != ZSTD_cwksp_alloc_objects || end > ws->workspaceEnd) {  in ZSTD_cwksp_reserve_object()
320         ws->allocFailed = 1;  in ZSTD_cwksp_reserve_object()
323     ws->objectEnd = end;  in ZSTD_cwksp_reserve_object()
324     ws->tableEnd = end;  in ZSTD_cwksp_reserve_object()
325     ws->tableValidEnd = end;  in ZSTD_cwksp_reserve_object()
335     assert(ws->tableValidEnd >= ws->objectEnd);  in ZSTD_cwksp_mark_tables_dirty()
336     assert(ws->tableValidEnd <= ws->allocStart);  in ZSTD_cwksp_mark_tables_dirty()
337     ws->tableValidEnd = ws->objectEnd;  in ZSTD_cwksp_mark_tables_dirty()
343     assert(ws->tableValidEnd >= ws->objectEnd);  in ZSTD_cwksp_mark_tables_clean()
344     assert(ws->tableValidEnd <= ws->allocStart);  in ZSTD_cwksp_mark_tables_clean()
345     if (ws->tableValidEnd < ws->tableEnd) {  in ZSTD_cwksp_mark_tables_clean()
346         ws->tableValidEnd = ws->tableEnd;  in ZSTD_cwksp_mark_tables_clean()
356     assert(ws->tableValidEnd >= ws->objectEnd);  in ZSTD_cwksp_clean_tables()
357     assert(ws->tableValidEnd <= ws->allocStart);  in ZSTD_cwksp_clean_tables()
358     if (ws->tableValidEnd < ws->tableEnd) {  in ZSTD_cwksp_clean_tables()
359         ZSTD_memset(ws->tableValidEnd, 0, (BYTE*)ws->tableEnd - (BYTE*)ws->tableValidEnd);  in ZSTD_cwksp_clean_tables()
372     ws->tableEnd = ws->objectEnd;  in ZSTD_cwksp_clear_tables()
385     ws->tableEnd = ws->objectEnd;  in ZSTD_cwksp_clear()
386     ws->allocStart = ws->workspaceEnd;  in ZSTD_cwksp_clear()
387     ws->allocFailed = 0;  in ZSTD_cwksp_clear()
388     if (ws->phase > ZSTD_cwksp_alloc_buffers) {  in ZSTD_cwksp_clear()
389         ws->phase = ZSTD_cwksp_alloc_buffers;  in ZSTD_cwksp_clear()
401     assert(((size_t)start & (sizeof(void*)-1)) == 0); /* ensure correct alignment */  in ZSTD_cwksp_init()
402     ws->workspace = start;  in ZSTD_cwksp_init()
403     ws->workspaceEnd = (BYTE*)start + size;  in ZSTD_cwksp_init()
404     ws->objectEnd = ws->workspace;  in ZSTD_cwksp_init()
405     ws->tableValidEnd = ws->objectEnd;  in ZSTD_cwksp_init()
406     ws->phase = ZSTD_cwksp_alloc_objects;  in ZSTD_cwksp_init()
407     ws->isStatic = isStatic;  in ZSTD_cwksp_init()
409     ws->workspaceOversizedDuration = 0;  in ZSTD_cwksp_init()
422     void *ptr = ws->workspace;  in ZSTD_cwksp_free()
430  * is left in an invalid state (src must be re-init()'ed before it's used again).
438     return (size_t)((BYTE*)ws->workspaceEnd - (BYTE*)ws->workspace);  in ZSTD_cwksp_sizeof()
442     return (size_t)((BYTE*)ws->tableEnd - (BYTE*)ws->workspace)  in ZSTD_cwksp_used()
443          + (size_t)((BYTE*)ws->workspaceEnd - (BYTE*)ws->allocStart);  in ZSTD_cwksp_used()
447     return ws->allocFailed;  in ZSTD_cwksp_reserve_failed()
450 /*-*************************************
455     return (size_t)((BYTE*)ws->allocStart - (BYTE*)ws->tableEnd);  in ZSTD_cwksp_available_space()
469         && ws->workspaceOversizedDuration > ZSTD_WORKSPACETOOLARGE_MAXDURATION;  in ZSTD_cwksp_check_wasteful()
475         ws->workspaceOversizedDuration++;  in ZSTD_cwksp_bump_oversized_duration()
477         ws->workspaceOversizedDuration = 0;  in ZSTD_cwksp_bump_oversized_duration()