ReactOS  0.4.15-dev-5455-g015cd25
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)
20 extern "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 ***************************************/
41 typedef enum {
46 
131 typedef struct {
132  void* workspace;
134 
135  void* objectEnd;
136  void* tableEnd;
138  void* allocStart;
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 
164 MEM_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)
182  return size + 2 * ZSTD_CWKSP_ASAN_REDZONE_SIZE;
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 
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) {
435  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;
452  ws->phase = ZSTD_cwksp_alloc_objects;
454  ws->workspaceOversizedDuration = 0;
456 }
457 
458 MEM_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 
466 MEM_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 
498 MEM_STATIC int ZSTD_cwksp_check_available(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
499  return ZSTD_cwksp_available_space(ws) >= additionalNeededSpace;
500 }
501 
502 MEM_STATIC int ZSTD_cwksp_check_too_large(ZSTD_cwksp* ws, size_t additionalNeededSpace) {
504  ws, additionalNeededSpace * ZSTD_WORKSPACETOOLARGE_FACTOR);
505 }
506 
507 MEM_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 */
ZSTD_cwksp_alloc_phase_e
Definition: zstd_cwksp.h:41
const char * ws
Definition: skip_ws.cpp:7
MEM_STATIC BYTE * ZSTD_cwksp_reserve_buffer(ZSTD_cwksp *ws, size_t bytes)
Definition: zstd_cwksp.h:263
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
int workspaceOversizedDuration
Definition: zstd_cwksp.h:141
void ZSTD_free(void *ptr, ZSTD_customMem customMem)
Definition: zstd_common.c:70
#define assert(x)
Definition: debug.h:53
MEM_STATIC void ZSTD_cwksp_clear_tables(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:392
int align(int length, int align)
Definition: dsound8.c:36
MEM_STATIC void ZSTD_cwksp_bump_oversized_duration(ZSTD_cwksp *ws, size_t additionalNeededSpace)
Definition: zstd_cwksp.h:512
MEM_STATIC size_t ZSTD_cwksp_alloc_size(size_t size)
Definition: zstd_cwksp.h:180
MEM_STATIC int ZSTD_cwksp_owns_buffer(const ZSTD_cwksp *ws, const void *ptr)
Definition: zstd_cwksp.h:217
MEM_STATIC void ZSTD_cwksp_free(ZSTD_cwksp *ws, ZSTD_customMem customMem)
Definition: zstd_cwksp.h:466
MEM_STATIC void ZSTD_cwksp_clear(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:410
#define DEBUGLOG(l,...)
Definition: debug.h:106
MEM_STATIC void * ZSTD_cwksp_reserve_aligned(ZSTD_cwksp *ws, size_t bytes)
Definition: zstd_cwksp.h:270
GLenum GLint GLuint mask
Definition: glext.h:6028
static unsigned char bytes[4]
Definition: adnsresfilter.c:74
MEM_STATIC int ZSTD_cwksp_reserve_failed(const ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:486
static PVOID ptr
Definition: dispmode.c:27
MEM_STATIC void ZSTD_cwksp_move(ZSTD_cwksp *dst, ZSTD_cwksp *src)
Definition: zstd_cwksp.h:477
GLint GLint bottom
Definition: glext.h:7726
MEM_STATIC int ZSTD_cwksp_check_too_large(ZSTD_cwksp *ws, size_t additionalNeededSpace)
Definition: zstd_cwksp.h:502
#define ZSTD_WORKSPACETOOLARGE_FACTOR
#define MEM_STATIC
Definition: mem.h:39
GLsizeiptr size
Definition: glext.h:5919
#define RETURN_ERROR_IF(cond, err,...)
Definition: zstd_internal.h:91
MEM_STATIC void ZSTD_cwksp_mark_tables_clean(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:365
MEM_STATIC size_t ZSTD_cwksp_available_space(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:494
int allocFailed
Definition: zstd_cwksp.h:140
void * workspace
Definition: zstd_cwksp.h:132
GLuint GLuint end
Definition: gl.h:1545
void * allocStart
Definition: zstd_cwksp.h:138
MEM_STATIC void ZSTD_cwksp_internal_advance_phase(ZSTD_cwksp *ws, ZSTD_cwksp_alloc_phase_e phase)
Definition: zstd_cwksp.h:188
#define ZSTD_WORKSPACETOOLARGE_MAXDURATION
MEM_STATIC size_t ZSTD_cwksp_align(size_t size, size_t const align)
Definition: zstd_cwksp.h:164
#define ZSTD_CWKSP_ASAN_REDZONE_SIZE
Definition: zstd_cwksp.h:35
MEM_STATIC void ZSTD_cwksp_assert_internal_consistency(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:151
GLenum src
Definition: glext.h:6340
void * objectEnd
Definition: zstd_cwksp.h:135
void * ZSTD_malloc(size_t size, ZSTD_customMem customMem)
Definition: zstd_common.c:56
unsigned char BYTE
Definition: xxhash.c:193
ZSTD_cwksp_alloc_phase_e phase
Definition: zstd_cwksp.h:142
void * tableEnd
Definition: zstd_cwksp.h:136
void * tableValidEnd
Definition: zstd_cwksp.h:137
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 int ZSTD_cwksp_check_wasteful(ZSTD_cwksp *ws, size_t additionalNeededSpace)
Definition: zstd_cwksp.h:507
GLuint start
Definition: gl.h:1545
MEM_STATIC void ZSTD_cwksp_init(ZSTD_cwksp *ws, void *start, size_t size)
Definition: zstd_cwksp.h:445
GLenum GLenum dst
Definition: glext.h:6340
#define alloc
Definition: rosglue.h:13
MEM_STATIC void * ZSTD_cwksp_reserve_object(ZSTD_cwksp *ws, size_t bytes)
Definition: zstd_cwksp.h:309
#define NULL
Definition: types.h:112
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859
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 memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195
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_sizeof(const ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:482
void * workspaceEnd
Definition: zstd_cwksp.h:133
MEM_STATIC void ZSTD_cwksp_clean_tables(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:378
MEM_STATIC void ZSTD_cwksp_mark_tables_dirty(ZSTD_cwksp *ws)
Definition: zstd_cwksp.h:345