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)
22extern "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***************************************/
47typedef 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 */
59typedef 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 */
158typedef 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
178MEM_STATIC size_t ZSTD_cwksp_available_space(ZSTD_cwksp* ws);
179MEM_STATIC void* ZSTD_cwksp_initialAllocStart(ZSTD_cwksp* ws);
180
181MEM_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#if defined(ZSTD_MSAN_PRINT)
196 if(offset!=-1) {
197 __msan_print_shadow((U8*)ws->initOnceStart + offset - 8, 32);
198 }
199#endif
200 assert(offset==-1);
201 };
202#endif
203}
204
205/**
206 * Align must be a power of 2.
207 */
208MEM_STATIC size_t ZSTD_cwksp_align(size_t size, size_t const align) {
209 size_t const mask = align - 1;
210 assert((align & mask) == 0);
211 return (size + mask) & ~mask;
212}
213
214/**
215 * Use this to determine how much space in the workspace we will consume to
216 * allocate this object. (Normally it should be exactly the size of the object,
217 * but under special conditions, like ASAN, where we pad each object, it might
218 * be larger.)
219 *
220 * Since tables aren't currently redzoned, you don't need to call through this
221 * to figure out how much space you need for the matchState tables. Everything
222 * else is though.
223 *
224 * Do not use for sizing aligned buffers. Instead, use ZSTD_cwksp_aligned_alloc_size().
225 */
226MEM_STATIC size_t ZSTD_cwksp_alloc_size(size_t size) {
227 if (size == 0)
228 return 0;
229#if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
230 return size + 2 * ZSTD_CWKSP_ASAN_REDZONE_SIZE;
231#else
232 return size;
233#endif
234}
235
236/**
237 * Returns an adjusted alloc size that is the nearest larger multiple of 64 bytes.
238 * Used to determine the number of bytes required for a given "aligned".
239 */
240MEM_STATIC size_t ZSTD_cwksp_aligned_alloc_size(size_t size) {
241 return ZSTD_cwksp_alloc_size(ZSTD_cwksp_align(size, ZSTD_CWKSP_ALIGNMENT_BYTES));
242}
243
244/**
245 * Returns the amount of additional space the cwksp must allocate
246 * for internal purposes (currently only alignment).
247 */
248MEM_STATIC size_t ZSTD_cwksp_slack_space_required(void) {
249 /* For alignment, the wksp will always allocate an additional 2*ZSTD_CWKSP_ALIGNMENT_BYTES
250 * bytes to align the beginning of tables section and end of buffers;
251 */
252 size_t const slackSpace = ZSTD_CWKSP_ALIGNMENT_BYTES * 2;
253 return slackSpace;
254}
255
256
257/**
258 * Return the number of additional bytes required to align a pointer to the given number of bytes.
259 * alignBytes must be a power of two.
260 */
261MEM_STATIC size_t ZSTD_cwksp_bytes_to_align_ptr(void* ptr, const size_t alignBytes) {
262 size_t const alignBytesMask = alignBytes - 1;
263 size_t const bytes = (alignBytes - ((size_t)ptr & (alignBytesMask))) & alignBytesMask;
264 assert((alignBytes & alignBytesMask) == 0);
265 assert(bytes < alignBytes);
266 return bytes;
267}
268
269/**
270 * Returns the initial value for allocStart which is used to determine the position from
271 * which we can allocate from the end of the workspace.
272 */
273MEM_STATIC void* ZSTD_cwksp_initialAllocStart(ZSTD_cwksp* ws) {
274 return (void*)((size_t)ws->workspaceEnd & ~(ZSTD_CWKSP_ALIGNMENT_BYTES-1));
275}
276
277/**
278 * Internal function. Do not use directly.
279 * Reserves the given number of bytes within the aligned/buffer segment of the wksp,
280 * which counts from the end of the wksp (as opposed to the object/table segment).
281 *
282 * Returns a pointer to the beginning of that space.
283 */
284MEM_STATIC void*
285ZSTD_cwksp_reserve_internal_buffer_space(ZSTD_cwksp* ws, size_t const bytes)
286{
287 void* const alloc = (BYTE*)ws->allocStart - bytes;
288 void* const bottom = ws->tableEnd;
289 DEBUGLOG(5, "cwksp: reserving %p %zd bytes, %zd bytes remaining",
290 alloc, bytes, ZSTD_cwksp_available_space(ws) - bytes);
291 ZSTD_cwksp_assert_internal_consistency(ws);
292 assert(alloc >= bottom);
293 if (alloc < bottom) {
294 DEBUGLOG(4, "cwksp: alloc failed!");
295 ws->allocFailed = 1;
296 return NULL;
297 }
298 /* the area is reserved from the end of wksp.
299 * If it overlaps with tableValidEnd, it voids guarantees on values' range */
300 if (alloc < ws->tableValidEnd) {
301 ws->tableValidEnd = alloc;
302 }
303 ws->allocStart = alloc;
304 return alloc;
305}
306
307/**
308 * Moves the cwksp to the next phase, and does any necessary allocations.
309 * cwksp initialization must necessarily go through each phase in order.
310 * Returns a 0 on success, or zstd error
311 */
312MEM_STATIC size_t
313ZSTD_cwksp_internal_advance_phase(ZSTD_cwksp* ws, ZSTD_cwksp_alloc_phase_e phase)
314{
315 assert(phase >= ws->phase);
316 if (phase > ws->phase) {
317 /* Going from allocating objects to allocating initOnce / tables */
318 if (ws->phase < ZSTD_cwksp_alloc_aligned_init_once &&
319 phase >= ZSTD_cwksp_alloc_aligned_init_once) {
320 ws->tableValidEnd = ws->objectEnd;
321 ws->initOnceStart = ZSTD_cwksp_initialAllocStart(ws);
322
323 { /* Align the start of the tables to 64 bytes. Use [0, 63] bytes */
324 void *const alloc = ws->objectEnd;
325 size_t const bytesToAlign = ZSTD_cwksp_bytes_to_align_ptr(alloc, ZSTD_CWKSP_ALIGNMENT_BYTES);
326 void *const objectEnd = (BYTE *) alloc + bytesToAlign;
327 DEBUGLOG(5, "reserving table alignment addtl space: %zu", bytesToAlign);
328 RETURN_ERROR_IF(objectEnd > ws->workspaceEnd, memory_allocation,
329 "table phase - alignment initial allocation failed!");
330 ws->objectEnd = objectEnd;
331 ws->tableEnd = objectEnd; /* table area starts being empty */
332 if (ws->tableValidEnd < ws->tableEnd) {
333 ws->tableValidEnd = ws->tableEnd;
334 }
335 }
336 }
337 ws->phase = phase;
338 ZSTD_cwksp_assert_internal_consistency(ws);
339 }
340 return 0;
341}
342
343/**
344 * Returns whether this object/buffer/etc was allocated in this workspace.
345 */
346MEM_STATIC int ZSTD_cwksp_owns_buffer(const ZSTD_cwksp* ws, const void* ptr)
347{
348 return (ptr != NULL) && (ws->workspace <= ptr) && (ptr < ws->workspaceEnd);
349}
350
351/**
352 * Internal function. Do not use directly.
353 */
354MEM_STATIC void*
355ZSTD_cwksp_reserve_internal(ZSTD_cwksp* ws, size_t bytes, ZSTD_cwksp_alloc_phase_e phase)
356{
357 void* alloc;
358 if (ZSTD_isError(ZSTD_cwksp_internal_advance_phase(ws, phase)) || bytes == 0) {
359 return NULL;
360 }
361
362#if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
363 /* over-reserve space */
364 bytes += 2 * ZSTD_CWKSP_ASAN_REDZONE_SIZE;
365#endif
366
367 alloc = ZSTD_cwksp_reserve_internal_buffer_space(ws, bytes);
368
369#if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
370 /* Move alloc so there's ZSTD_CWKSP_ASAN_REDZONE_SIZE unused space on
371 * either size. */
372 if (alloc) {
373 alloc = (BYTE *)alloc + ZSTD_CWKSP_ASAN_REDZONE_SIZE;
374 if (ws->isStatic == ZSTD_cwksp_dynamic_alloc) {
375 /* We need to keep the redzone poisoned while unpoisoning the bytes that
376 * are actually allocated. */
377 __asan_unpoison_memory_region(alloc, bytes - 2 * ZSTD_CWKSP_ASAN_REDZONE_SIZE);
378 }
379 }
380#endif
381
382 return alloc;
383}
384
385/**
386 * Reserves and returns unaligned memory.
387 */
388MEM_STATIC BYTE* ZSTD_cwksp_reserve_buffer(ZSTD_cwksp* ws, size_t bytes)
389{
390 return (BYTE*)ZSTD_cwksp_reserve_internal(ws, bytes, ZSTD_cwksp_alloc_buffers);
391}
392
393/**
394 * Reserves and returns memory sized on and aligned on ZSTD_CWKSP_ALIGNMENT_BYTES (64 bytes).
395 * This memory has been initialized at least once in the past.
396 * This doesn't mean it has been initialized this time, and it might contain data from previous
397 * operations.
398 * The main usage is for algorithms that might need read access into uninitialized memory.
399 * The algorithm must maintain safety under these conditions and must make sure it doesn't
400 * leak any of the past data (directly or in side channels).
401 */
402MEM_STATIC void* ZSTD_cwksp_reserve_aligned_init_once(ZSTD_cwksp* ws, size_t bytes)
403{
404 size_t const alignedBytes = ZSTD_cwksp_align(bytes, ZSTD_CWKSP_ALIGNMENT_BYTES);
405 void* ptr = ZSTD_cwksp_reserve_internal(ws, alignedBytes, ZSTD_cwksp_alloc_aligned_init_once);
406 assert(((size_t)ptr & (ZSTD_CWKSP_ALIGNMENT_BYTES-1))== 0);
407 if(ptr && ptr < ws->initOnceStart) {
408 /* We assume the memory following the current allocation is either:
409 * 1. Not usable as initOnce memory (end of workspace)
410 * 2. Another initOnce buffer that has been allocated before (and so was previously memset)
411 * 3. An ASAN redzone, in which case we don't want to write on it
412 * For these reasons it should be fine to not explicitly zero every byte up to ws->initOnceStart.
413 * Note that we assume here that MSAN and ASAN cannot run in the same time. */
414 ZSTD_memset(ptr, 0, MIN((size_t)((U8*)ws->initOnceStart - (U8*)ptr), alignedBytes));
415 ws->initOnceStart = ptr;
416 }
417#if ZSTD_MEMORY_SANITIZER
418 assert(__msan_test_shadow(ptr, bytes) == -1);
419#endif
420 return ptr;
421}
422
423/**
424 * Reserves and returns memory sized on and aligned on ZSTD_CWKSP_ALIGNMENT_BYTES (64 bytes).
425 */
426MEM_STATIC void* ZSTD_cwksp_reserve_aligned(ZSTD_cwksp* ws, size_t bytes)
427{
428 void* ptr = ZSTD_cwksp_reserve_internal(ws, ZSTD_cwksp_align(bytes, ZSTD_CWKSP_ALIGNMENT_BYTES),
429 ZSTD_cwksp_alloc_aligned);
430 assert(((size_t)ptr & (ZSTD_CWKSP_ALIGNMENT_BYTES-1))== 0);
431 return ptr;
432}
433
434/**
435 * Aligned on 64 bytes. These buffers have the special property that
436 * their values remain constrained, allowing us to re-use them without
437 * memset()-ing them.
438 */
439MEM_STATIC void* ZSTD_cwksp_reserve_table(ZSTD_cwksp* ws, size_t bytes)
440{
441 const ZSTD_cwksp_alloc_phase_e phase = ZSTD_cwksp_alloc_aligned_init_once;
442 void* alloc;
443 void* end;
444 void* top;
445
446 /* We can only start allocating tables after we are done reserving space for objects at the
447 * start of the workspace */
448 if(ws->phase < phase) {
449 if (ZSTD_isError(ZSTD_cwksp_internal_advance_phase(ws, phase))) {
450 return NULL;
451 }
452 }
453 alloc = ws->tableEnd;
454 end = (BYTE *)alloc + bytes;
455 top = ws->allocStart;
456
457 DEBUGLOG(5, "cwksp: reserving %p table %zd bytes, %zd bytes remaining",
458 alloc, bytes, ZSTD_cwksp_available_space(ws) - bytes);
459 assert((bytes & (sizeof(U32)-1)) == 0);
460 ZSTD_cwksp_assert_internal_consistency(ws);
461 assert(end <= top);
462 if (end > top) {
463 DEBUGLOG(4, "cwksp: table alloc failed!");
464 ws->allocFailed = 1;
465 return NULL;
466 }
467 ws->tableEnd = end;
468
469#if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
470 if (ws->isStatic == ZSTD_cwksp_dynamic_alloc) {
471 __asan_unpoison_memory_region(alloc, bytes);
472 }
473#endif
474
475 assert((bytes & (ZSTD_CWKSP_ALIGNMENT_BYTES-1)) == 0);
476 assert(((size_t)alloc & (ZSTD_CWKSP_ALIGNMENT_BYTES-1))== 0);
477 return alloc;
478}
479
480/**
481 * Aligned on sizeof(void*).
482 * Note : should happen only once, at workspace first initialization
483 */
484MEM_STATIC void* ZSTD_cwksp_reserve_object(ZSTD_cwksp* ws, size_t bytes)
485{
486 size_t const roundedBytes = ZSTD_cwksp_align(bytes, sizeof(void*));
487 void* alloc = ws->objectEnd;
488 void* end = (BYTE*)alloc + roundedBytes;
489
490#if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
491 /* over-reserve space */
492 end = (BYTE *)end + 2 * ZSTD_CWKSP_ASAN_REDZONE_SIZE;
493#endif
494
495 DEBUGLOG(4,
496 "cwksp: reserving %p object %zd bytes (rounded to %zd), %zd bytes remaining",
497 alloc, bytes, roundedBytes, ZSTD_cwksp_available_space(ws) - roundedBytes);
498 assert((size_t)alloc % ZSTD_ALIGNOF(void*) == 0);
499 assert(bytes % ZSTD_ALIGNOF(void*) == 0);
500 ZSTD_cwksp_assert_internal_consistency(ws);
501 /* we must be in the first phase, no advance is possible */
502 if (ws->phase != ZSTD_cwksp_alloc_objects || end > ws->workspaceEnd) {
503 DEBUGLOG(3, "cwksp: object alloc failed!");
504 ws->allocFailed = 1;
505 return NULL;
506 }
507 ws->objectEnd = end;
508 ws->tableEnd = end;
509 ws->tableValidEnd = end;
510
511#if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
512 /* Move alloc so there's ZSTD_CWKSP_ASAN_REDZONE_SIZE unused space on
513 * either size. */
514 alloc = (BYTE*)alloc + ZSTD_CWKSP_ASAN_REDZONE_SIZE;
515 if (ws->isStatic == ZSTD_cwksp_dynamic_alloc) {
516 __asan_unpoison_memory_region(alloc, bytes);
517 }
518#endif
519
520 return alloc;
521}
522
523MEM_STATIC void ZSTD_cwksp_mark_tables_dirty(ZSTD_cwksp* ws)
524{
525 DEBUGLOG(4, "cwksp: ZSTD_cwksp_mark_tables_dirty");
526
527#if ZSTD_MEMORY_SANITIZER && !defined (ZSTD_MSAN_DONT_POISON_WORKSPACE)
528 /* To validate that the table re-use logic is sound, and that we don't
529 * access table space that we haven't cleaned, we re-"poison" the table
530 * space every time we mark it dirty.
531 * Since tableValidEnd space and initOnce space may overlap we don't poison
532 * the initOnce portion as it break its promise. This means that this poisoning
533 * check isn't always applied fully. */
534 {
535 size_t size = (BYTE*)ws->tableValidEnd - (BYTE*)ws->objectEnd;
536 assert(__msan_test_shadow(ws->objectEnd, size) == -1);
537 if((BYTE*)ws->tableValidEnd < (BYTE*)ws->initOnceStart) {
538 __msan_poison(ws->objectEnd, size);
539 } else {
540 assert(ws->initOnceStart >= ws->objectEnd);
541 __msan_poison(ws->objectEnd, (BYTE*)ws->initOnceStart - (BYTE*)ws->objectEnd);
542 }
543 }
544#endif
545
546 assert(ws->tableValidEnd >= ws->objectEnd);
547 assert(ws->tableValidEnd <= ws->allocStart);
548 ws->tableValidEnd = ws->objectEnd;
549 ZSTD_cwksp_assert_internal_consistency(ws);
550}
551
552MEM_STATIC void ZSTD_cwksp_mark_tables_clean(ZSTD_cwksp* ws) {
553 DEBUGLOG(4, "cwksp: ZSTD_cwksp_mark_tables_clean");
554 assert(ws->tableValidEnd >= ws->objectEnd);
555 assert(ws->tableValidEnd <= ws->allocStart);
556 if (ws->tableValidEnd < ws->tableEnd) {
557 ws->tableValidEnd = ws->tableEnd;
558 }
559 ZSTD_cwksp_assert_internal_consistency(ws);
560}
561
562/**
563 * Zero the part of the allocated tables not already marked clean.
564 */
565MEM_STATIC void ZSTD_cwksp_clean_tables(ZSTD_cwksp* ws) {
566 DEBUGLOG(4, "cwksp: ZSTD_cwksp_clean_tables");
567 assert(ws->tableValidEnd >= ws->objectEnd);
568 assert(ws->tableValidEnd <= ws->allocStart);
569 if (ws->tableValidEnd < ws->tableEnd) {
570 ZSTD_memset(ws->tableValidEnd, 0, (size_t)((BYTE*)ws->tableEnd - (BYTE*)ws->tableValidEnd));
571 }
572 ZSTD_cwksp_mark_tables_clean(ws);
573}
574
575/**
576 * Invalidates table allocations.
577 * All other allocations remain valid.
578 */
579MEM_STATIC void ZSTD_cwksp_clear_tables(ZSTD_cwksp* ws) {
580 DEBUGLOG(4, "cwksp: clearing tables!");
581
582#if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
583 /* We don't do this when the workspace is statically allocated, because
584 * when that is the case, we have no capability to hook into the end of the
585 * workspace's lifecycle to unpoison the memory.
586 */
587 if (ws->isStatic == ZSTD_cwksp_dynamic_alloc) {
588 size_t size = (BYTE*)ws->tableValidEnd - (BYTE*)ws->objectEnd;
589 __asan_poison_memory_region(ws->objectEnd, size);
590 }
591#endif
592
593 ws->tableEnd = ws->objectEnd;
594 ZSTD_cwksp_assert_internal_consistency(ws);
595}
596
597/**
598 * Invalidates all buffer, aligned, and table allocations.
599 * Object allocations remain valid.
600 */
601MEM_STATIC void ZSTD_cwksp_clear(ZSTD_cwksp* ws) {
602 DEBUGLOG(4, "cwksp: clearing!");
603
604#if ZSTD_MEMORY_SANITIZER && !defined (ZSTD_MSAN_DONT_POISON_WORKSPACE)
605 /* To validate that the context re-use logic is sound, and that we don't
606 * access stuff that this compression hasn't initialized, we re-"poison"
607 * the workspace except for the areas in which we expect memory re-use
608 * without initialization (objects, valid tables area and init once
609 * memory). */
610 {
611 if((BYTE*)ws->tableValidEnd < (BYTE*)ws->initOnceStart) {
612 size_t size = (BYTE*)ws->initOnceStart - (BYTE*)ws->tableValidEnd;
613 __msan_poison(ws->tableValidEnd, size);
614 }
615 }
616#endif
617
618#if ZSTD_ADDRESS_SANITIZER && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
619 /* We don't do this when the workspace is statically allocated, because
620 * when that is the case, we have no capability to hook into the end of the
621 * workspace's lifecycle to unpoison the memory.
622 */
623 if (ws->isStatic == ZSTD_cwksp_dynamic_alloc) {
624 size_t size = (BYTE*)ws->workspaceEnd - (BYTE*)ws->objectEnd;
625 __asan_poison_memory_region(ws->objectEnd, size);
626 }
627#endif
628
629 ws->tableEnd = ws->objectEnd;
630 ws->allocStart = ZSTD_cwksp_initialAllocStart(ws);
631 ws->allocFailed = 0;
632 if (ws->phase > ZSTD_cwksp_alloc_aligned_init_once) {
633 ws->phase = ZSTD_cwksp_alloc_aligned_init_once;
634 }
635 ZSTD_cwksp_assert_internal_consistency(ws);
636}
637
638/**
639 * The provided workspace takes ownership of the buffer [start, start+size).
640 * Any existing values in the workspace are ignored (the previously managed
641 * buffer, if present, must be separately freed).
642 */
643MEM_STATIC void ZSTD_cwksp_init(ZSTD_cwksp* ws, void* start, size_t size, ZSTD_cwksp_static_alloc_e isStatic) {
644 DEBUGLOG(4, "cwksp: init'ing workspace with %zd bytes", size);
645 assert(((size_t)start & (sizeof(void*)-1)) == 0); /* ensure correct alignment */
646 ws->workspace = start;
647 ws->workspaceEnd = (BYTE*)start + size;
648 ws->objectEnd = ws->workspace;
649 ws->tableValidEnd = ws->objectEnd;
650 ws->initOnceStart = ZSTD_cwksp_initialAllocStart(ws);
651 ws->phase = ZSTD_cwksp_alloc_objects;
652 ws->isStatic = isStatic;
653 ZSTD_cwksp_clear(ws);
654 ws->workspaceOversizedDuration = 0;
655 ZSTD_cwksp_assert_internal_consistency(ws);
656}
657
658MEM_STATIC size_t ZSTD_cwksp_create(ZSTD_cwksp* ws, size_t size, ZSTD_customMem customMem) {
659 void* workspace = ZSTD_customMalloc(size, customMem);
660 DEBUGLOG(4, "cwksp: creating new workspace with %zd bytes", size);
661 RETURN_ERROR_IF(workspace == NULL, memory_allocation, "NULL pointer!");
662 ZSTD_cwksp_init(ws, workspace, size, ZSTD_cwksp_dynamic_alloc);
663 return 0;
664}
665
666MEM_STATIC void ZSTD_cwksp_free(ZSTD_cwksp* ws, ZSTD_customMem customMem) {
667 void *ptr = ws->workspace;
668 DEBUGLOG(4, "cwksp: freeing workspace");
669 ZSTD_memset(ws, 0, sizeof(ZSTD_cwksp));
670 ZSTD_customFree(ptr, customMem);
671}
672
673/**
674 * Moves the management of a workspace from one cwksp to another. The src cwksp
675 * is left in an invalid state (src must be re-init()'ed before it's used again).
676 */
677MEM_STATIC void ZSTD_cwksp_move(ZSTD_cwksp* dst, ZSTD_cwksp* src) {
678 *dst = *src;
679 ZSTD_memset(src, 0, sizeof(ZSTD_cwksp));
680}
681
682MEM_STATIC size_t ZSTD_cwksp_sizeof(const ZSTD_cwksp* ws) {
683 return (size_t)((BYTE*)ws->workspaceEnd - (BYTE*)ws->workspace);
684}
685
686MEM_STATIC size_t ZSTD_cwksp_used(const ZSTD_cwksp* ws) {
687 return (size_t)((BYTE*)ws->tableEnd - (BYTE*)ws->workspace)
688 + (size_t)((BYTE*)ws->workspaceEnd - (BYTE*)ws->allocStart);
689}
690
691MEM_STATIC int ZSTD_cwksp_reserve_failed(const ZSTD_cwksp* ws) {
692 return ws->allocFailed;
693}
694
695/*-*************************************
696* Functions Checking Free Space
697***************************************/
698
699/* ZSTD_alignmentSpaceWithinBounds() :
700 * Returns if the estimated space needed for a wksp is within an acceptable limit of the
701 * actual amount of space used.
702 */
703MEM_STATIC int ZSTD_cwksp_estimated_space_within_bounds(const ZSTD_cwksp *const ws, size_t const estimatedSpace) {
704 /* We have an alignment space between objects and tables between tables and buffers, so we can have up to twice
705 * the alignment bytes difference between estimation and actual usage */
706 return (estimatedSpace - ZSTD_cwksp_slack_space_required()) <= ZSTD_cwksp_used(ws) &&
707 ZSTD_cwksp_used(ws) <= estimatedSpace;
708}
709
710
711MEM_STATIC size_t ZSTD_cwksp_available_space(ZSTD_cwksp* ws) {
712 return (size_t)((BYTE*)ws->allocStart - (BYTE*)ws->tableEnd);
713}
714
715MEM_STATIC int ZSTD_cwksp_check_available(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
716 return ZSTD_cwksp_available_space(ws) >= additionalNeededSpace;
717}
718
719MEM_STATIC int ZSTD_cwksp_check_too_large(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
720 return ZSTD_cwksp_check_available(
721 ws, additionalNeededSpace * ZSTD_WORKSPACETOOLARGE_FACTOR);
722}
723
724MEM_STATIC int ZSTD_cwksp_check_wasteful(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
725 return ZSTD_cwksp_check_too_large(ws, additionalNeededSpace)
726 && ws->workspaceOversizedDuration > ZSTD_WORKSPACETOOLARGE_MAXDURATION;
727}
728
729MEM_STATIC void ZSTD_cwksp_bump_oversized_duration(
730 ZSTD_cwksp* ws, size_t additionalNeededSpace) {
731 if (ZSTD_cwksp_check_too_large(ws, additionalNeededSpace)) {
732 ws->workspaceOversizedDuration++;
733 } else {
734 ws->workspaceOversizedDuration = 0;
735 }
736}
737
738#if defined (__cplusplus)
739}
740#endif
741
742#endif /* ZSTD_CWKSP_H */
743