compress_zstd.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541
  1. /* Copyright (c) 2004, Roger Dingledine.
  2. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  3. * Copyright (c) 2007-2018, The Tor Project, Inc. */
  4. /* See LICENSE for licensing information */
  5. /**
  6. * \file compress_zstd.c
  7. * \brief Compression backend for Zstandard.
  8. *
  9. * This module should never be invoked directly. Use the compress module
  10. * instead.
  11. **/
  12. #include "orconfig.h"
  13. #include "lib/log/log.h"
  14. #include "lib/log/util_bug.h"
  15. #include "lib/compress/compress.h"
  16. #include "lib/compress/compress_zstd.h"
  17. #include "lib/string/printf.h"
  18. #include "lib/thread/threads.h"
  19. #ifdef ENABLE_ZSTD_ADVANCED_APIS
  20. /* This is a lie, but we make sure it doesn't get us in trouble by wrapping
  21. * all invocations of zstd's static-only functions in a check to make sure
  22. * that the compile-time version matches the run-time version. */
  23. #define ZSTD_STATIC_LINKING_ONLY
  24. #endif
  25. #ifdef HAVE_ZSTD
  26. #ifdef HAVE_CFLAG_WUNUSED_CONST_VARIABLE
  27. DISABLE_GCC_WARNING(unused-const-variable)
  28. #endif
  29. #include <zstd.h>
  30. #ifdef HAVE_CFLAG_WUNUSED_CONST_VARIABLE
  31. ENABLE_GCC_WARNING(unused-const-variable)
  32. #endif
  33. #endif
  34. /** Total number of bytes allocated for Zstandard state. */
  35. static atomic_counter_t total_zstd_allocation;
  36. #ifdef HAVE_ZSTD
  37. /** Given <b>level</b> return the memory level. */
  38. static int
  39. memory_level(compression_level_t level)
  40. {
  41. switch (level) {
  42. default:
  43. case BEST_COMPRESSION:
  44. case HIGH_COMPRESSION: return 9;
  45. case MEDIUM_COMPRESSION: return 8;
  46. case LOW_COMPRESSION: return 7;
  47. }
  48. }
  49. #endif /* defined(HAVE_ZSTD) */
  50. /** Return 1 if Zstandard compression is supported; otherwise 0. */
  51. int
  52. tor_zstd_method_supported(void)
  53. {
  54. #ifdef HAVE_ZSTD
  55. return 1;
  56. #else
  57. return 0;
  58. #endif
  59. }
  60. #ifdef HAVE_ZSTD
  61. /** Format a zstd version number as a string in <b>buf</b>. */
  62. static void
  63. tor_zstd_format_version(char *buf, size_t buflen, unsigned version_number)
  64. {
  65. tor_snprintf(buf, buflen,
  66. "%u.%u.%u",
  67. version_number / 10000 % 100,
  68. version_number / 100 % 100,
  69. version_number % 100);
  70. }
  71. #endif
  72. #define VERSION_STR_MAX_LEN 16 /* more than enough space for 99.99.99 */
  73. /** Return a string representation of the version of the currently running
  74. * version of libzstd. Returns NULL if Zstandard is unsupported. */
  75. const char *
  76. tor_zstd_get_version_str(void)
  77. {
  78. #ifdef HAVE_ZSTD
  79. static char version_str[VERSION_STR_MAX_LEN];
  80. tor_zstd_format_version(version_str, sizeof(version_str),
  81. ZSTD_versionNumber());
  82. return version_str;
  83. #else /* !(defined(HAVE_ZSTD)) */
  84. return NULL;
  85. #endif /* defined(HAVE_ZSTD) */
  86. }
  87. /** Return a string representation of the version of the version of libzstd
  88. * used at compilation time. Returns NULL if Zstandard is unsupported. */
  89. const char *
  90. tor_zstd_get_header_version_str(void)
  91. {
  92. #ifdef HAVE_ZSTD
  93. return ZSTD_VERSION_STRING;
  94. #else
  95. return NULL;
  96. #endif
  97. }
  98. #ifdef TOR_UNIT_TESTS
  99. static int static_apis_disable_for_testing = 0;
  100. #endif
  101. /** Return true iff we can use the "static-only" APIs. */
  102. int
  103. tor_zstd_can_use_static_apis(void)
  104. {
  105. #if defined(ZSTD_STATIC_LINKING_ONLY) && defined(HAVE_ZSTD)
  106. #ifdef TOR_UNIT_TESTS
  107. if (static_apis_disable_for_testing) {
  108. return 0;
  109. }
  110. #endif
  111. return (ZSTD_VERSION_NUMBER == ZSTD_versionNumber());
  112. #else
  113. return 0;
  114. #endif
  115. }
  116. /** Internal Zstandard state for incremental compression/decompression.
  117. * The body of this struct is not exposed. */
  118. struct tor_zstd_compress_state_t {
  119. #ifdef HAVE_ZSTD
  120. union {
  121. /** Compression stream. Used when <b>compress</b> is true. */
  122. ZSTD_CStream *compress_stream;
  123. /** Decompression stream. Used when <b>compress</b> is false. */
  124. ZSTD_DStream *decompress_stream;
  125. } u; /**< Zstandard stream objects. */
  126. #endif /* defined(HAVE_ZSTD) */
  127. int compress; /**< True if we are compressing; false if we are inflating */
  128. int have_called_end; /**< True if we are compressing and we've called
  129. * ZSTD_endStream */
  130. /** Number of bytes read so far. Used to detect compression bombs. */
  131. size_t input_so_far;
  132. /** Number of bytes written so far. Used to detect compression bombs. */
  133. size_t output_so_far;
  134. /** Approximate number of bytes allocated for this object. */
  135. size_t allocation;
  136. };
  137. #ifdef HAVE_ZSTD
  138. /** Return an approximate number of bytes stored in memory to hold the
  139. * Zstandard compression/decompression state. This is a fake estimate
  140. * based on inspecting the zstd source: tor_zstd_state_size_precalc() is
  141. * more accurate when it's allowed to use "static-only" functions */
  142. static size_t
  143. tor_zstd_state_size_precalc_fake(int compress, int preset)
  144. {
  145. tor_assert(preset > 0);
  146. size_t memory_usage = sizeof(tor_zstd_compress_state_t);
  147. // The Zstandard library provides a number of functions that would be useful
  148. // here, but they are, unfortunately, still considered experimental and are
  149. // thus only available in libzstd if we link against the library statically.
  150. //
  151. // The code in this function tries to approximate the calculations without
  152. // being able to use the following:
  153. //
  154. // - We do not have access to neither the internal members of ZSTD_CStream
  155. // and ZSTD_DStream and their internal context objects.
  156. //
  157. // - We cannot use ZSTD_sizeof_CStream() and ZSTD_sizeof_DStream() since they
  158. // are unexposed.
  159. //
  160. // In the future it might be useful to check if libzstd have started
  161. // providing these functions in a stable manner and simplify this function.
  162. if (compress) {
  163. // We try to approximate the ZSTD_sizeof_CStream(ZSTD_CStream *stream)
  164. // function here. This function uses the following fields to make its
  165. // estimate:
  166. // - sizeof(ZSTD_CStream): Around 192 bytes on a 64-bit machine:
  167. memory_usage += 192;
  168. // - ZSTD_sizeof_CCtx(stream->cctx): This function requires access to
  169. // variables that are not exposed via the public API. We use a _very_
  170. // simplified function to calculate the estimated amount of bytes used in
  171. // this struct.
  172. // memory_usage += (preset - 0.5) * 1024 * 1024;
  173. memory_usage += (preset * 1024 * 1024) - (512 * 1024);
  174. // - ZSTD_sizeof_CDict(stream->cdictLocal): Unused in Tor: 0 bytes.
  175. // - stream->outBuffSize: 128 KB:
  176. memory_usage += 128 * 1024;
  177. // - stream->inBuffSize: 2048 KB:
  178. memory_usage += 2048 * 1024;
  179. } else {
  180. // We try to approximate the ZSTD_sizeof_DStream(ZSTD_DStream *stream)
  181. // function here. This function uses the following fields to make its
  182. // estimate:
  183. // - sizeof(ZSTD_DStream): Around 208 bytes on a 64-bit machine:
  184. memory_usage += 208;
  185. // - ZSTD_sizeof_DCtx(stream->dctx): Around 150 KB.
  186. memory_usage += 150 * 1024;
  187. // - ZSTD_sizeof_DDict(stream->ddictLocal): Unused in Tor: 0 bytes.
  188. // - stream->inBuffSize: 0 KB.
  189. // - stream->outBuffSize: 0 KB.
  190. }
  191. return memory_usage;
  192. }
  193. /** Return an approximate number of bytes stored in memory to hold the
  194. * Zstandard compression/decompression state. */
  195. static size_t
  196. tor_zstd_state_size_precalc(int compress, int preset)
  197. {
  198. #ifdef ZSTD_STATIC_LINKING_ONLY
  199. if (tor_zstd_can_use_static_apis()) {
  200. if (compress) {
  201. #ifdef HAVE_ZSTD_ESTIMATECSTREAMSIZE
  202. return ZSTD_estimateCStreamSize(preset);
  203. #endif
  204. } else {
  205. #ifdef HAVE_ZSTD_ESTIMATEDCTXSIZE
  206. /* Could use DStream, but that takes a windowSize. */
  207. return ZSTD_estimateDCtxSize();
  208. #endif
  209. }
  210. }
  211. #endif
  212. return tor_zstd_state_size_precalc_fake(compress, preset);
  213. }
  214. #endif /* defined(HAVE_ZSTD) */
  215. /** Construct and return a tor_zstd_compress_state_t object using
  216. * <b>method</b>. If <b>compress</b>, it's for compression; otherwise it's for
  217. * decompression. */
  218. tor_zstd_compress_state_t *
  219. tor_zstd_compress_new(int compress,
  220. compress_method_t method,
  221. compression_level_t level)
  222. {
  223. tor_assert(method == ZSTD_METHOD);
  224. #ifdef HAVE_ZSTD
  225. const int preset = memory_level(level);
  226. tor_zstd_compress_state_t *result;
  227. size_t retval;
  228. result = tor_malloc_zero(sizeof(tor_zstd_compress_state_t));
  229. result->compress = compress;
  230. result->allocation = tor_zstd_state_size_precalc(compress, preset);
  231. if (compress) {
  232. result->u.compress_stream = ZSTD_createCStream();
  233. if (result->u.compress_stream == NULL) {
  234. // LCOV_EXCL_START
  235. log_warn(LD_GENERAL, "Error while creating Zstandard compression "
  236. "stream");
  237. goto err;
  238. // LCOV_EXCL_STOP
  239. }
  240. retval = ZSTD_initCStream(result->u.compress_stream, preset);
  241. if (ZSTD_isError(retval)) {
  242. // LCOV_EXCL_START
  243. log_warn(LD_GENERAL, "Zstandard stream initialization error: %s",
  244. ZSTD_getErrorName(retval));
  245. goto err;
  246. // LCOV_EXCL_STOP
  247. }
  248. } else {
  249. result->u.decompress_stream = ZSTD_createDStream();
  250. if (result->u.decompress_stream == NULL) {
  251. // LCOV_EXCL_START
  252. log_warn(LD_GENERAL, "Error while creating Zstandard decompression "
  253. "stream");
  254. goto err;
  255. // LCOV_EXCL_STOP
  256. }
  257. retval = ZSTD_initDStream(result->u.decompress_stream);
  258. if (ZSTD_isError(retval)) {
  259. // LCOV_EXCL_START
  260. log_warn(LD_GENERAL, "Zstandard stream initialization error: %s",
  261. ZSTD_getErrorName(retval));
  262. goto err;
  263. // LCOV_EXCL_STOP
  264. }
  265. }
  266. atomic_counter_add(&total_zstd_allocation, result->allocation);
  267. return result;
  268. err:
  269. // LCOV_EXCL_START
  270. if (compress) {
  271. ZSTD_freeCStream(result->u.compress_stream);
  272. } else {
  273. ZSTD_freeDStream(result->u.decompress_stream);
  274. }
  275. tor_free(result);
  276. return NULL;
  277. // LCOV_EXCL_STOP
  278. #else /* !(defined(HAVE_ZSTD)) */
  279. (void)compress;
  280. (void)method;
  281. (void)level;
  282. return NULL;
  283. #endif /* defined(HAVE_ZSTD) */
  284. }
  285. /** Compress/decompress some bytes using <b>state</b>. Read up to
  286. * *<b>in_len</b> bytes from *<b>in</b>, and write up to *<b>out_len</b> bytes
  287. * to *<b>out</b>, adjusting the values as we go. If <b>finish</b> is true,
  288. * we've reached the end of the input.
  289. *
  290. * Return TOR_COMPRESS_DONE if we've finished the entire
  291. * compression/decompression.
  292. * Return TOR_COMPRESS_OK if we're processed everything from the input.
  293. * Return TOR_COMPRESS_BUFFER_FULL if we're out of space on <b>out</b>.
  294. * Return TOR_COMPRESS_ERROR if the stream is corrupt.
  295. */
  296. tor_compress_output_t
  297. tor_zstd_compress_process(tor_zstd_compress_state_t *state,
  298. char **out, size_t *out_len,
  299. const char **in, size_t *in_len,
  300. int finish)
  301. {
  302. #ifdef HAVE_ZSTD
  303. size_t retval;
  304. tor_assert(state != NULL);
  305. tor_assert(*in_len <= UINT_MAX);
  306. tor_assert(*out_len <= UINT_MAX);
  307. ZSTD_inBuffer input = { *in, *in_len, 0 };
  308. ZSTD_outBuffer output = { *out, *out_len, 0 };
  309. if (BUG(finish == 0 && state->have_called_end)) {
  310. finish = 1;
  311. }
  312. if (state->compress) {
  313. if (! state->have_called_end)
  314. retval = ZSTD_compressStream(state->u.compress_stream,
  315. &output, &input);
  316. else
  317. retval = 0;
  318. } else {
  319. retval = ZSTD_decompressStream(state->u.decompress_stream,
  320. &output, &input);
  321. }
  322. state->input_so_far += input.pos;
  323. state->output_so_far += output.pos;
  324. *out = (char *)output.dst + output.pos;
  325. *out_len = output.size - output.pos;
  326. *in = (char *)input.src + input.pos;
  327. *in_len = input.size - input.pos;
  328. if (! state->compress &&
  329. tor_compress_is_compression_bomb(state->input_so_far,
  330. state->output_so_far)) {
  331. log_warn(LD_DIR, "Possible compression bomb; abandoning stream.");
  332. return TOR_COMPRESS_ERROR;
  333. }
  334. if (ZSTD_isError(retval)) {
  335. log_warn(LD_GENERAL, "Zstandard %s didn't finish: %s.",
  336. state->compress ? "compression" : "decompression",
  337. ZSTD_getErrorName(retval));
  338. return TOR_COMPRESS_ERROR;
  339. }
  340. if (state->compress && !state->have_called_end) {
  341. retval = ZSTD_flushStream(state->u.compress_stream, &output);
  342. *out = (char *)output.dst + output.pos;
  343. *out_len = output.size - output.pos;
  344. if (ZSTD_isError(retval)) {
  345. log_warn(LD_GENERAL, "Zstandard compression unable to flush: %s.",
  346. ZSTD_getErrorName(retval));
  347. return TOR_COMPRESS_ERROR;
  348. }
  349. // ZSTD_flushStream returns 0 if the frame is done, or >0 if it
  350. // is incomplete.
  351. if (retval > 0) {
  352. return TOR_COMPRESS_BUFFER_FULL;
  353. }
  354. }
  355. if (!finish) {
  356. // The caller says we're not done with the input, so no need to write an
  357. // epilogue.
  358. return TOR_COMPRESS_OK;
  359. } else if (state->compress) {
  360. if (*in_len) {
  361. // We say that we're not done with the input, so we can't write an
  362. // epilogue.
  363. return TOR_COMPRESS_OK;
  364. }
  365. retval = ZSTD_endStream(state->u.compress_stream, &output);
  366. state->have_called_end = 1;
  367. *out = (char *)output.dst + output.pos;
  368. *out_len = output.size - output.pos;
  369. if (ZSTD_isError(retval)) {
  370. log_warn(LD_GENERAL, "Zstandard compression unable to write "
  371. "epilogue: %s.",
  372. ZSTD_getErrorName(retval));
  373. return TOR_COMPRESS_ERROR;
  374. }
  375. // endStream returns the number of bytes that is needed to write the
  376. // epilogue.
  377. if (retval > 0)
  378. return TOR_COMPRESS_BUFFER_FULL;
  379. return TOR_COMPRESS_DONE;
  380. } else /* if (!state->compress) */ {
  381. // ZSTD_decompressStream returns 0 if the frame is done, or >0 if it
  382. // is incomplete.
  383. // We check this above.
  384. tor_assert_nonfatal(!ZSTD_isError(retval));
  385. // Start a new frame if this frame is done
  386. if (retval == 0)
  387. return TOR_COMPRESS_DONE;
  388. // Don't check out_len, it might have some space left if the next output
  389. // chunk is larger than the remaining space
  390. else if (*in_len > 0)
  391. return TOR_COMPRESS_BUFFER_FULL;
  392. else
  393. return TOR_COMPRESS_OK;
  394. }
  395. #else /* !(defined(HAVE_ZSTD)) */
  396. (void)state;
  397. (void)out;
  398. (void)out_len;
  399. (void)in;
  400. (void)in_len;
  401. (void)finish;
  402. return TOR_COMPRESS_ERROR;
  403. #endif /* defined(HAVE_ZSTD) */
  404. }
  405. /** Deallocate <b>state</b>. */
  406. void
  407. tor_zstd_compress_free_(tor_zstd_compress_state_t *state)
  408. {
  409. if (state == NULL)
  410. return;
  411. atomic_counter_sub(&total_zstd_allocation, state->allocation);
  412. #ifdef HAVE_ZSTD
  413. if (state->compress) {
  414. ZSTD_freeCStream(state->u.compress_stream);
  415. } else {
  416. ZSTD_freeDStream(state->u.decompress_stream);
  417. }
  418. #endif /* defined(HAVE_ZSTD) */
  419. tor_free(state);
  420. }
  421. /** Return the approximate number of bytes allocated for <b>state</b>. */
  422. size_t
  423. tor_zstd_compress_state_size(const tor_zstd_compress_state_t *state)
  424. {
  425. tor_assert(state != NULL);
  426. return state->allocation;
  427. }
  428. /** Return the approximate number of bytes allocated for all Zstandard
  429. * states. */
  430. size_t
  431. tor_zstd_get_total_allocation(void)
  432. {
  433. return atomic_counter_get(&total_zstd_allocation);
  434. }
  435. /** Initialize the zstd module */
  436. void
  437. tor_zstd_init(void)
  438. {
  439. atomic_counter_init(&total_zstd_allocation);
  440. }
  441. /** Warn if the header and library versions don't match. */
  442. void
  443. tor_zstd_warn_if_version_mismatched(void)
  444. {
  445. #if defined(HAVE_ZSTD) && defined(ENABLE_ZSTD_ADVANCED_APIS)
  446. if (! tor_zstd_can_use_static_apis()) {
  447. char header_version[VERSION_STR_MAX_LEN];
  448. char runtime_version[VERSION_STR_MAX_LEN];
  449. tor_zstd_format_version(header_version, sizeof(header_version),
  450. ZSTD_VERSION_NUMBER);
  451. tor_zstd_format_version(runtime_version, sizeof(runtime_version),
  452. ZSTD_versionNumber());
  453. log_warn(LD_GENERAL,
  454. "Tor was compiled with zstd %s, but is running with zstd %s. "
  455. "For safety, we'll avoid using advanced zstd functionality.",
  456. header_version, runtime_version);
  457. }
  458. #endif
  459. }
  460. #ifdef TOR_UNIT_TESTS
  461. /** Testing only: disable usage of static-only APIs, so we can make sure that
  462. * we still work without them. */
  463. void
  464. tor_zstd_set_static_apis_disabled_for_testing(int disabled)
  465. {
  466. static_apis_disable_for_testing = disabled;
  467. }
  468. #endif