ReactOS 0.4.15-dev-8100-g1887773
zstd_cwksp.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2016-2020, Yann Collet, Facebook, Inc.
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 "zstd_internal.h"
18
19#if defined (__cplusplus)
20extern "C" {
21#endif
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* Structures
40***************************************/
41typedef enum {
46
131typedef struct {
134
136 void* tableEnd;
139
143} ZSTD_cwksp;
144
145/*-*************************************
146* Functions
147***************************************/
148
150
152 (void)ws;
153 assert(ws->workspace <= ws->objectEnd);
154 assert(ws->objectEnd <= ws->tableEnd);
155 assert(ws->objectEnd <= ws->tableValidEnd);
156 assert(ws->tableEnd <= ws->allocStart);
157 assert(ws->tableValidEnd <= ws->allocStart);
158 assert(ws->allocStart <= ws->workspaceEnd);
159}
160
164MEM_STATIC size_t ZSTD_cwksp_align(size_t size, size_t const align) {
165 size_t const mask = align - 1;
166 assert((align & mask) == 0);
167 return (size + mask) & ~mask;
168}
169
181#if defined (ADDRESS_SANITIZER) && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
183#else
184 return size;
185#endif
186}
187
190 assert(phase >= ws->phase);
191 if (phase > ws->phase) {
192 if (ws->phase < ZSTD_cwksp_alloc_buffers &&
193 phase >= ZSTD_cwksp_alloc_buffers) {
194 ws->tableValidEnd = ws->objectEnd;
195 }
196 if (ws->phase < ZSTD_cwksp_alloc_aligned &&
197 phase >= ZSTD_cwksp_alloc_aligned) {
198 /* If unaligned allocations down from a too-large top have left us
199 * unaligned, we need to realign our alloc ptr. Technically, this
200 * can consume space that is unaccounted for in the neededSpace
201 * calculation. However, I believe this can only happen when the
202 * workspace is too large, and specifically when it is too large
203 * by a larger margin than the space that will be consumed. */
204 /* TODO: cleaner, compiler warning friendly way to do this??? */
205 ws->allocStart = (BYTE*)ws->allocStart - ((size_t)ws->allocStart & (sizeof(U32)-1));
206 if (ws->allocStart < ws->tableValidEnd) {
207 ws->tableValidEnd = ws->allocStart;
208 }
209 }
210 ws->phase = phase;
211 }
212}
213
217MEM_STATIC int ZSTD_cwksp_owns_buffer(const ZSTD_cwksp* ws, const void* ptr) {
218 return (ptr != NULL) && (ws->workspace <= ptr) && (ptr <= ws->workspaceEnd);
219}
220
225 ZSTD_cwksp* ws, size_t bytes, ZSTD_cwksp_alloc_phase_e phase) {
226 void* alloc;
227 void* bottom = ws->tableEnd;
229 alloc = (BYTE *)ws->allocStart - bytes;
230
231#if defined (ADDRESS_SANITIZER) && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
232 /* over-reserve space */
234#endif
235
236 DEBUGLOG(5, "cwksp: reserving %p %zd bytes, %zd bytes remaining",
239 assert(alloc >= bottom);
240 if (alloc < bottom) {
241 DEBUGLOG(4, "cwksp: alloc failed!");
242 ws->allocFailed = 1;
243 return NULL;
244 }
245 if (alloc < ws->tableValidEnd) {
246 ws->tableValidEnd = alloc;
247 }
248 ws->allocStart = alloc;
249
250#if defined (ADDRESS_SANITIZER) && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
251 /* Move alloc so there's ZSTD_CWKSP_ASAN_REDZONE_SIZE unused space on
252 * either size. */
254 __asan_unpoison_memory_region(alloc, bytes);
255#endif
256
257 return alloc;
258}
259
265}
266
271 assert((bytes & (sizeof(U32)-1)) == 0);
273}
274
282 void* alloc = ws->tableEnd;
283 void* end = (BYTE *)alloc + bytes;
284 void* top = ws->allocStart;
285
286 DEBUGLOG(5, "cwksp: reserving %p table %zd bytes, %zd bytes remaining",
288 assert((bytes & (sizeof(U32)-1)) == 0);
291 assert(end <= top);
292 if (end > top) {
293 DEBUGLOG(4, "cwksp: table alloc failed!");
294 ws->allocFailed = 1;
295 return NULL;
296 }
297 ws->tableEnd = end;
298
299#if defined (ADDRESS_SANITIZER) && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
300 __asan_unpoison_memory_region(alloc, bytes);
301#endif
302
303 return alloc;
304}
305
310 size_t roundedBytes = ZSTD_cwksp_align(bytes, sizeof(void*));
311 void* alloc = ws->objectEnd;
312 void* end = (BYTE*)alloc + roundedBytes;
313
314#if defined (ADDRESS_SANITIZER) && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
315 /* over-reserve space */
317#endif
318
319 DEBUGLOG(5,
320 "cwksp: reserving %p object %zd bytes (rounded to %zd), %zd bytes remaining",
321 alloc, bytes, roundedBytes, ZSTD_cwksp_available_space(ws) - roundedBytes);
322 assert(((size_t)alloc & (sizeof(void*)-1)) == 0);
323 assert((bytes & (sizeof(void*)-1)) == 0);
325 /* we must be in the first phase, no advance is possible */
326 if (ws->phase != ZSTD_cwksp_alloc_objects || end > ws->workspaceEnd) {
327 DEBUGLOG(4, "cwksp: object alloc failed!");
328 ws->allocFailed = 1;
329 return NULL;
330 }
331 ws->objectEnd = end;
332 ws->tableEnd = end;
333 ws->tableValidEnd = end;
334
335#if defined (ADDRESS_SANITIZER) && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
336 /* Move alloc so there's ZSTD_CWKSP_ASAN_REDZONE_SIZE unused space on
337 * either size. */
339 __asan_unpoison_memory_region(alloc, bytes);
340#endif
341
342 return alloc;
343}
344
346 DEBUGLOG(4, "cwksp: ZSTD_cwksp_mark_tables_dirty");
347
348#if defined (MEMORY_SANITIZER) && !defined (ZSTD_MSAN_DONT_POISON_WORKSPACE)
349 /* To validate that the table re-use logic is sound, and that we don't
350 * access table space that we haven't cleaned, we re-"poison" the table
351 * space every time we mark it dirty. */
352 {
353 size_t size = (BYTE*)ws->tableValidEnd - (BYTE*)ws->objectEnd;
354 assert(__msan_test_shadow(ws->objectEnd, size) == -1);
355 __msan_poison(ws->objectEnd, size);
356 }
357#endif
358
359 assert(ws->tableValidEnd >= ws->objectEnd);
360 assert(ws->tableValidEnd <= ws->allocStart);
361 ws->tableValidEnd = ws->objectEnd;
363}
364
366 DEBUGLOG(4, "cwksp: ZSTD_cwksp_mark_tables_clean");
367 assert(ws->tableValidEnd >= ws->objectEnd);
368 assert(ws->tableValidEnd <= ws->allocStart);
369 if (ws->tableValidEnd < ws->tableEnd) {
370 ws->tableValidEnd = ws->tableEnd;
371 }
373}
374
379 DEBUGLOG(4, "cwksp: ZSTD_cwksp_clean_tables");
380 assert(ws->tableValidEnd >= ws->objectEnd);
381 assert(ws->tableValidEnd <= ws->allocStart);
382 if (ws->tableValidEnd < ws->tableEnd) {
383 memset(ws->tableValidEnd, 0, (BYTE*)ws->tableEnd - (BYTE*)ws->tableValidEnd);
384 }
386}
387
393 DEBUGLOG(4, "cwksp: clearing tables!");
394
395#if defined (ADDRESS_SANITIZER) && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
396 {
397 size_t size = (BYTE*)ws->tableValidEnd - (BYTE*)ws->objectEnd;
398 __asan_poison_memory_region(ws->objectEnd, size);
399 }
400#endif
401
402 ws->tableEnd = ws->objectEnd;
404}
405
411 DEBUGLOG(4, "cwksp: clearing!");
412
413#if defined (MEMORY_SANITIZER) && !defined (ZSTD_MSAN_DONT_POISON_WORKSPACE)
414 /* To validate that the context re-use logic is sound, and that we don't
415 * access stuff that this compression hasn't initialized, we re-"poison"
416 * the workspace (or at least the non-static, non-table parts of it)
417 * every time we start a new compression. */
418 {
419 size_t size = (BYTE*)ws->workspaceEnd - (BYTE*)ws->tableValidEnd;
420 __msan_poison(ws->tableValidEnd, size);
421 }
422#endif
423
424#if defined (ADDRESS_SANITIZER) && !defined (ZSTD_ASAN_DONT_POISON_WORKSPACE)
425 {
426 size_t size = (BYTE*)ws->workspaceEnd - (BYTE*)ws->objectEnd;
427 __asan_poison_memory_region(ws->objectEnd, size);
428 }
429#endif
430
431 ws->tableEnd = ws->objectEnd;
432 ws->allocStart = ws->workspaceEnd;
433 ws->allocFailed = 0;
434 if (ws->phase > ZSTD_cwksp_alloc_buffers) {
436 }
438}
439
446 DEBUGLOG(4, "cwksp: init'ing workspace with %zd bytes", size);
447 assert(((size_t)start & (sizeof(void*)-1)) == 0); /* ensure correct alignment */
448 ws->workspace = start;
449 ws->workspaceEnd = (BYTE*)start + size;
450 ws->objectEnd = ws->workspace;
451 ws->tableValidEnd = ws->objectEnd;
454 ws->workspaceOversizedDuration = 0;
456}
457
458MEM_STATIC size_t ZSTD_cwksp_create(ZSTD_cwksp* ws, size_t size, ZSTD_customMem customMem) {
459 void* workspace = ZSTD_malloc(size, customMem);
460 DEBUGLOG(4, "cwksp: creating new workspace with %zd bytes", size);
461 RETURN_ERROR_IF(workspace == NULL, memory_allocation, "NULL pointer!");
462 ZSTD_cwksp_init(ws, workspace, size);
463 return 0;
464}
465
466MEM_STATIC void ZSTD_cwksp_free(ZSTD_cwksp* ws, ZSTD_customMem customMem) {
467 void *ptr = ws->workspace;
468 DEBUGLOG(4, "cwksp: freeing workspace");
469 memset(ws, 0, sizeof(ZSTD_cwksp));
470 ZSTD_free(ptr, customMem);
471}
472
478 *dst = *src;
479 memset(src, 0, sizeof(ZSTD_cwksp));
480}
481
483 return (size_t)((BYTE*)ws->workspaceEnd - (BYTE*)ws->workspace);
484}
485
487 return ws->allocFailed;
488}
489
490/*-*************************************
491* Functions Checking Free Space
492***************************************/
493
495 return (size_t)((BYTE*)ws->allocStart - (BYTE*)ws->tableEnd);
496}
497
498MEM_STATIC int ZSTD_cwksp_check_available(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
499 return ZSTD_cwksp_available_space(ws) >= additionalNeededSpace;
500}
501
502MEM_STATIC int ZSTD_cwksp_check_too_large(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
504 ws, additionalNeededSpace * ZSTD_WORKSPACETOOLARGE_FACTOR);
505}
506
507MEM_STATIC int ZSTD_cwksp_check_wasteful(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
508 return ZSTD_cwksp_check_too_large(ws, additionalNeededSpace)
509 && ws->workspaceOversizedDuration > ZSTD_WORKSPACETOOLARGE_MAXDURATION;
510}
511
513 ZSTD_cwksp* ws, size_t additionalNeededSpace) {
514 if (ZSTD_cwksp_check_too_large(ws, additionalNeededSpace)) {
515 ws->workspaceOversizedDuration++;
516 } else {
517 ws->workspaceOversizedDuration = 0;
518 }
519}
520
521#if defined (__cplusplus)
522}
523#endif
524
525#endif /* ZSTD_CWKSP_H */
static unsigned char bytes[4]
Definition: adnsresfilter.c:74
#define NULL
Definition: types.h:112
#define assert(x)
Definition: debug.h:53
#define DEBUGLOG(l,...)
Definition: debug.h:106
#define MEM_STATIC
Definition: mem.h:39
int align(int length, int align)
Definition: dsound8.c:36
GLuint start
Definition: gl.h:1545
GLuint GLuint end
Definition: gl.h:1545
GLsizeiptr size
Definition: glext.h:5919
GLenum src
Definition: glext.h:6340
GLenum GLint GLuint mask
Definition: glext.h:6028
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859
GLenum GLenum dst
Definition: glext.h:6340
GLint GLint bottom
Definition: glext.h:7726
static PVOID ptr
Definition: dispmode.c:27
#define alloc
Definition: rosglue.h:13
#define memset(x, y, z)
Definition: compat.h:39
const char * ws
Definition: skip_ws.cpp:7
void * tableValidEnd
Definition: zstd_cwksp.h:137
void * workspaceEnd
Definition: zstd_cwksp.h:133
int workspaceOversizedDuration
Definition: zstd_cwksp.h:141
void * tableEnd
Definition: zstd_cwksp.h:136
int allocFailed
Definition: zstd_cwksp.h:140
ZSTD_cwksp_alloc_phase_e phase
Definition: zstd_cwksp.h:142
void * objectEnd
Definition: zstd_cwksp.h:135
void * workspace
Definition: zstd_cwksp.h:132
void * allocStart
Definition: zstd_cwksp.h:138
unsigned char BYTE
Definition: xxhash.c:193
unsigned int U32
Definition: xxhash.c:195
void ZSTD_free(void *ptr, ZSTD_customMem customMem)
Definition: zstd_common.c:70
void * ZSTD_malloc(size_t size, ZSTD_customMem customMem)
Definition: zstd_common.c:56
MEM_STATIC size_t ZSTD_cwksp_create(ZSTD_cwksp *ws, size_t size, ZSTD_customMem customMem)
Definition: zstd_cwksp.h:458
MEM_STATIC size_t ZSTD_cwksp_align(size_t size, size_t const align)
Definition: zstd_cwksp.h:164
MEM_STATIC void ZSTD_cwksp_mark_tables_clean(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:365
MEM_STATIC int ZSTD_cwksp_reserve_failed(const ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:486
MEM_STATIC void ZSTD_cwksp_move(ZSTD_cwksp *dst, ZSTD_cwksp *src)
Definition: zstd_cwksp.h:477
MEM_STATIC void ZSTD_cwksp_clean_tables(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:378
MEM_STATIC int ZSTD_cwksp_check_too_large(ZSTD_cwksp *ws, size_t additionalNeededSpace)
Definition: zstd_cwksp.h:502
MEM_STATIC void ZSTD_cwksp_clear_tables(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:392
MEM_STATIC void ZSTD_cwksp_assert_internal_consistency(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:151
MEM_STATIC void ZSTD_cwksp_internal_advance_phase(ZSTD_cwksp *ws, ZSTD_cwksp_alloc_phase_e phase)
Definition: zstd_cwksp.h:188
MEM_STATIC int ZSTD_cwksp_owns_buffer(const ZSTD_cwksp *ws, const void *ptr)
Definition: zstd_cwksp.h:217
MEM_STATIC int ZSTD_cwksp_check_wasteful(ZSTD_cwksp *ws, size_t additionalNeededSpace)
Definition: zstd_cwksp.h:507
MEM_STATIC size_t ZSTD_cwksp_sizeof(const ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:482
MEM_STATIC void ZSTD_cwksp_bump_oversized_duration(ZSTD_cwksp *ws, size_t additionalNeededSpace)
Definition: zstd_cwksp.h:512
MEM_STATIC void ZSTD_cwksp_mark_tables_dirty(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:345
ZSTD_cwksp_alloc_phase_e
Definition: zstd_cwksp.h:41
@ ZSTD_cwksp_alloc_objects
Definition: zstd_cwksp.h:42
@ ZSTD_cwksp_alloc_buffers
Definition: zstd_cwksp.h:43
@ ZSTD_cwksp_alloc_aligned
Definition: zstd_cwksp.h:44
MEM_STATIC void ZSTD_cwksp_free(ZSTD_cwksp *ws, ZSTD_customMem customMem)
Definition: zstd_cwksp.h:466
MEM_STATIC void * ZSTD_cwksp_reserve_internal(ZSTD_cwksp *ws, size_t bytes, ZSTD_cwksp_alloc_phase_e phase)
Definition: zstd_cwksp.h:224
MEM_STATIC BYTE * ZSTD_cwksp_reserve_buffer(ZSTD_cwksp *ws, size_t bytes)
Definition: zstd_cwksp.h:263
MEM_STATIC void ZSTD_cwksp_clear(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:410
MEM_STATIC void * ZSTD_cwksp_reserve_object(ZSTD_cwksp *ws, size_t bytes)
Definition: zstd_cwksp.h:309
MEM_STATIC size_t ZSTD_cwksp_alloc_size(size_t size)
Definition: zstd_cwksp.h:180
MEM_STATIC int ZSTD_cwksp_check_available(ZSTD_cwksp *ws, size_t additionalNeededSpace)
Definition: zstd_cwksp.h:498
MEM_STATIC void * ZSTD_cwksp_reserve_table(ZSTD_cwksp *ws, size_t bytes)
Definition: zstd_cwksp.h:280
#define ZSTD_CWKSP_ASAN_REDZONE_SIZE
Definition: zstd_cwksp.h:35
MEM_STATIC void ZSTD_cwksp_init(ZSTD_cwksp *ws, void *start, size_t size)
Definition: zstd_cwksp.h:445
MEM_STATIC void * ZSTD_cwksp_reserve_aligned(ZSTD_cwksp *ws, size_t bytes)
Definition: zstd_cwksp.h:270
MEM_STATIC size_t ZSTD_cwksp_available_space(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:494
#define ZSTD_WORKSPACETOOLARGE_MAXDURATION
#define RETURN_ERROR_IF(cond, err,...)
Definition: zstd_internal.h:91
#define ZSTD_WORKSPACETOOLARGE_FACTOR