648db22b |
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); |
f535537f |
195 | (void)offset; |
648db22b |
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 |
f535537f |
437 | * their values remain constrained, allowing us to reuse them without |
648db22b |
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) |
f535537f |
529 | /* To validate that the table reuse logic is sound, and that we don't |
648db22b |
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) |
f535537f |
606 | /* To validate that the context reuse logic is sound, and that we don't |
648db22b |
607 | * access stuff that this compression hasn't initialized, we re-"poison" |
f535537f |
608 | * the workspace except for the areas in which we expect memory reuse |
648db22b |
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 | |
f535537f |
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 | |
648db22b |
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"); |
f535537f |
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 |
648db22b |
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 | |
648db22b |
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 */ |