1 /* Copyright (c) 2004, Roger Dingledine.
2 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3 * Copyright (c) 2007-2016, The Tor Project, Inc. */
4 /* See LICENSE for licensing information */
8 * \brief A simple in-memory gzip implementation.
19 #ifdef HAVE_NETINET_IN_H
20 #include <netinet/in.h>
27 /* zlib 1.2.4 and 1.2.5 do some "clever" things with macros. Instead of
28 saying "(defined(FOO) ? FOO : 0)" they like to say "FOO-0", on the theory
29 that nobody will care if the compile outputs a no-such-identifier warning.
31 Sorry, but we like -Werror over here, so I guess we need to define these.
32 I hope that zlib 1.2.6 doesn't break these too.
34 #ifndef _LARGEFILE64_SOURCE
35 #define _LARGEFILE64_SOURCE 0
37 #ifndef _LFS64_LARGEFILE
38 #define _LFS64_LARGEFILE 0
40 #ifndef _FILE_OFFSET_BITS
41 #define _FILE_OFFSET_BITS 0
44 #define off64_t int64_t
49 #if defined ZLIB_VERNUM && ZLIB_VERNUM < 0x1200
50 #error "We require zlib version 1.2 or later."
53 static size_t tor_zlib_state_size_precalc(int inflate
,
54 int windowbits
, int memlevel
);
56 /** Total number of bytes allocated for zlib state */
57 static size_t total_zlib_allocation
= 0;
59 /** Return a string representation of the version of the currently running
62 tor_zlib_get_version_str(void)
67 /** Return a string representation of the version of the version of zlib
68 * used at compilation. */
70 tor_zlib_get_header_version_str(void)
75 /** Return the 'bits' value to tell zlib to use <b>method</b>.*/
77 method_bits(compress_method_t method
, zlib_compression_level_t level
)
79 /* Bits+16 means "use gzip" in zlib >= 1.2 */
80 const int flag
= method
== GZIP_METHOD
? 16 : 0;
83 case HIGH_COMPRESSION
: return flag
+ 15;
84 case MEDIUM_COMPRESSION
: return flag
+ 13;
85 case LOW_COMPRESSION
: return flag
+ 11;
90 get_memlevel(zlib_compression_level_t level
)
94 case HIGH_COMPRESSION
: return 8;
95 case MEDIUM_COMPRESSION
: return 7;
96 case LOW_COMPRESSION
: return 6;
101 /* These macros define the maximum allowable compression factor. Anything of
102 * size greater than CHECK_FOR_COMPRESSION_BOMB_AFTER is not allowed to
103 * have an uncompression factor (uncompressed size:compressed size ratio) of
104 * any greater than MAX_UNCOMPRESSION_FACTOR.
106 * Picking a value for MAX_UNCOMPRESSION_FACTOR is a trade-off: we want it to
107 * be small to limit the attack multiplier, but we also want it to be large
108 * enough so that no legitimate document --even ones we might invent in the
109 * future -- ever compresses by a factor of greater than
110 * MAX_UNCOMPRESSION_FACTOR. Within those parameters, there's a reasonably
111 * large range of possible values. IMO, anything over 8 is probably safe; IMO
112 * anything under 50 is probably sufficient.
114 #define MAX_UNCOMPRESSION_FACTOR 25
115 #define CHECK_FOR_COMPRESSION_BOMB_AFTER (1024*64)
118 /** Return true if uncompressing an input of size <b>in_size</b> to an input
119 * of size at least <b>size_out</b> looks like a compression bomb. */
121 is_compression_bomb(size_t size_in
, size_t size_out
)
123 if (size_in
== 0 || size_out
< CHECK_FOR_COMPRESSION_BOMB_AFTER
)
126 return (size_out
/ size_in
> MAX_UNCOMPRESSION_FACTOR
);
129 /** Given <b>in_len</b> bytes at <b>in</b>, compress them into a newly
130 * allocated buffer, using the method described in <b>method</b>. Store the
131 * compressed string in *<b>out</b>, and its length in *<b>out_len</b>.
132 * Return 0 on success, -1 on failure.
135 tor_gzip_compress(char **out
, size_t *out_len
,
136 const char *in
, size_t in_len
,
137 compress_method_t method
)
139 struct z_stream_s
*stream
= NULL
;
140 size_t out_size
, old_size
;
146 tor_assert(in_len
< UINT_MAX
);
150 stream
= tor_malloc_zero(sizeof(struct z_stream_s
));
151 stream
->zalloc
= Z_NULL
;
152 stream
->zfree
= Z_NULL
;
153 stream
->opaque
= NULL
;
154 stream
->next_in
= (unsigned char*) in
;
155 stream
->avail_in
= (unsigned int)in_len
;
157 if (deflateInit2(stream
, Z_BEST_COMPRESSION
, Z_DEFLATED
,
158 method_bits(method
, HIGH_COMPRESSION
),
159 get_memlevel(HIGH_COMPRESSION
),
160 Z_DEFAULT_STRATEGY
) != Z_OK
) {
161 //LCOV_EXCL_START -- we can only provoke failure by giving junk arguments.
162 log_warn(LD_GENERAL
, "Error from deflateInit2: %s",
163 stream
->msg
?stream
->msg
:"<no message>");
168 /* Guess 50% compression. */
169 out_size
= in_len
/ 2;
170 if (out_size
< 1024) out_size
= 1024;
171 *out
= tor_malloc(out_size
);
172 stream
->next_out
= (unsigned char*)*out
;
173 stream
->avail_out
= (unsigned int)out_size
;
176 switch (deflate(stream
, Z_FINISH
))
181 /* In case zlib doesn't work as I think .... */
182 if (stream
->avail_out
>= stream
->avail_in
+16)
185 offset
= stream
->next_out
- ((unsigned char*)*out
);
188 if (out_size
< old_size
) {
189 log_warn(LD_GENERAL
, "Size overflow in compression.");
192 *out
= tor_realloc(*out
, out_size
);
193 stream
->next_out
= (unsigned char*)(*out
+ offset
);
194 if (out_size
- offset
> UINT_MAX
) {
195 log_warn(LD_BUG
, "Ran over unsigned int limit of zlib while "
199 stream
->avail_out
= (unsigned int)(out_size
- offset
);
202 log_warn(LD_GENERAL
, "Gzip compression didn't finish: %s",
203 stream
->msg
? stream
->msg
: "<no message>");
208 *out_len
= stream
->total_out
;
210 /* "Hey Rocky! Watch me change an unsigned field to a signed field in a
212 * "Oh, that trick will just make people do unsafe casts to the unsigned
213 * type in their cross-platform code!"
214 * "Don't be foolish. I'm _sure_ they'll have the good sense to make sure
215 * the newly unsigned field isn't negative." */
216 tor_assert(stream
->total_out
>= 0);
218 if (deflateEnd(stream
)!=Z_OK
) {
219 // LCOV_EXCL_START -- unreachable if we handled the zlib structure right
220 tor_assert_nonfatal_unreached();
221 log_warn(LD_BUG
, "Error freeing gzip structures");
227 if (is_compression_bomb(*out_len
, in_len
)) {
228 log_warn(LD_BUG
, "We compressed something and got an insanely high "
229 "compression factor; other Tors would think this was a zlib bomb.");
243 /** Given zero or more zlib-compressed or gzip-compressed strings of
245 * <b>in_len</b> bytes at <b>in</b>, uncompress them into a newly allocated
246 * buffer, using the method described in <b>method</b>. Store the uncompressed
247 * string in *<b>out</b>, and its length in *<b>out_len</b>. Return 0 on
248 * success, -1 on failure.
250 * If <b>complete_only</b> is true, we consider a truncated input as a
251 * failure; otherwise we decompress as much as we can. Warn about truncated
252 * or corrupt inputs at <b>protocol_warn_level</b>.
255 tor_gzip_uncompress(char **out
, size_t *out_len
,
256 const char *in
, size_t in_len
,
257 compress_method_t method
,
259 int protocol_warn_level
)
261 struct z_stream_s
*stream
= NULL
;
262 size_t out_size
, old_size
;
269 tor_assert(in_len
< UINT_MAX
);
273 stream
= tor_malloc_zero(sizeof(struct z_stream_s
));
274 stream
->zalloc
= Z_NULL
;
275 stream
->zfree
= Z_NULL
;
276 stream
->opaque
= NULL
;
277 stream
->next_in
= (unsigned char*) in
;
278 stream
->avail_in
= (unsigned int)in_len
;
280 if (inflateInit2(stream
,
281 method_bits(method
, HIGH_COMPRESSION
)) != Z_OK
) {
282 // LCOV_EXCL_START -- can only hit this if we give bad inputs.
283 log_warn(LD_GENERAL
, "Error from inflateInit2: %s",
284 stream
->msg
?stream
->msg
:"<no message>");
289 out_size
= in_len
* 2; /* guess 50% compression. */
290 if (out_size
< 1024) out_size
= 1024;
291 if (out_size
>= SIZE_T_CEILING
|| out_size
> UINT_MAX
)
294 *out
= tor_malloc(out_size
);
295 stream
->next_out
= (unsigned char*)*out
;
296 stream
->avail_out
= (unsigned int)out_size
;
299 switch (inflate(stream
, complete_only
? Z_FINISH
: Z_SYNC_FLUSH
))
302 if (stream
->avail_in
== 0)
304 /* There may be more compressed data here. */
305 if ((r
= inflateEnd(stream
)) != Z_OK
) {
306 log_warn(LD_BUG
, "Error freeing gzip structures");
309 if (inflateInit2(stream
,
310 method_bits(method
,HIGH_COMPRESSION
)) != Z_OK
) {
311 log_warn(LD_GENERAL
, "Error from second inflateInit2: %s",
312 stream
->msg
?stream
->msg
:"<no message>");
317 if (!complete_only
&& stream
->avail_in
== 0)
319 /* In case zlib doesn't work as I think.... */
320 if (stream
->avail_out
>= stream
->avail_in
+16)
323 if (stream
->avail_out
> 0) {
324 log_fn(protocol_warn_level
, LD_PROTOCOL
,
325 "possible truncated or corrupt zlib data");
328 offset
= stream
->next_out
- (unsigned char*)*out
;
331 if (out_size
< old_size
) {
332 log_warn(LD_GENERAL
, "Size overflow in uncompression.");
335 if (is_compression_bomb(in_len
, out_size
)) {
336 log_warn(LD_GENERAL
, "Input looks like a possible zlib bomb; "
340 if (out_size
>= SIZE_T_CEILING
) {
341 log_warn(LD_BUG
, "Hit SIZE_T_CEILING limit while uncompressing.");
344 *out
= tor_realloc(*out
, out_size
);
345 stream
->next_out
= (unsigned char*)(*out
+ offset
);
346 if (out_size
- offset
> UINT_MAX
) {
347 log_warn(LD_BUG
, "Ran over unsigned int limit of zlib while "
351 stream
->avail_out
= (unsigned int)(out_size
- offset
);
354 log_warn(LD_GENERAL
, "Gzip decompression returned an error: %s",
355 stream
->msg
? stream
->msg
: "<no message>");
360 *out_len
= stream
->next_out
- (unsigned char*)*out
;
361 r
= inflateEnd(stream
);
364 log_warn(LD_BUG
, "Error freeing gzip structures");
368 /* NUL-terminate output. */
369 if (out_size
== *out_len
)
370 *out
= tor_realloc(*out
, out_size
+ 1);
371 (*out
)[*out_len
] = '\0';
385 /** Try to tell whether the <b>in_len</b>-byte string in <b>in</b> is likely
386 * to be compressed or not. If it is, return the likeliest compression method.
387 * Otherwise, return UNKNOWN_METHOD.
390 detect_compression_method(const char *in
, size_t in_len
)
392 if (in_len
> 2 && fast_memeq(in
, "\x1f\x8b", 2)) {
394 } else if (in_len
> 2 && (in
[0] & 0x0f) == 8 &&
395 (ntohs(get_uint16(in
)) % 31) == 0) {
398 return UNKNOWN_METHOD
;
402 /** Internal state for an incremental zlib compression/decompression. The
403 * body of this struct is not exposed. */
404 struct tor_zlib_state_t
{
405 struct z_stream_s stream
; /**< The zlib stream */
406 int compress
; /**< True if we are compressing; false if we are inflating */
408 /** Number of bytes read so far. Used to detect zlib bombs. */
410 /** Number of bytes written so far. Used to detect zlib bombs. */
411 size_t output_so_far
;
413 /** Approximate number of bytes allocated for this object. */
417 /** Construct and return a tor_zlib_state_t object using <b>method</b>. If
418 * <b>compress</b>, it's for compression; otherwise it's for
421 tor_zlib_new(int compress
, compress_method_t method
,
422 zlib_compression_level_t compression_level
)
424 tor_zlib_state_t
*out
;
428 /* use this setting for decompression, since we might have the
429 * max number of window bits */
430 compression_level
= HIGH_COMPRESSION
;
433 out
= tor_malloc_zero(sizeof(tor_zlib_state_t
));
434 out
->stream
.zalloc
= Z_NULL
;
435 out
->stream
.zfree
= Z_NULL
;
436 out
->stream
.opaque
= NULL
;
437 out
->compress
= compress
;
438 bits
= method_bits(method
, compression_level
);
439 memlevel
= get_memlevel(compression_level
);
441 if (deflateInit2(&out
->stream
, Z_BEST_COMPRESSION
, Z_DEFLATED
,
443 Z_DEFAULT_STRATEGY
) != Z_OK
)
444 goto err
; // LCOV_EXCL_LINE
446 if (inflateInit2(&out
->stream
, bits
) != Z_OK
)
447 goto err
; // LCOV_EXCL_LINE
449 out
->allocation
= tor_zlib_state_size_precalc(!compress
, bits
, memlevel
);
451 total_zlib_allocation
+= out
->allocation
;
460 /** Compress/decompress some bytes using <b>state</b>. Read up to
461 * *<b>in_len</b> bytes from *<b>in</b>, and write up to *<b>out_len</b> bytes
462 * to *<b>out</b>, adjusting the values as we go. If <b>finish</b> is true,
463 * we've reached the end of the input.
465 * Return TOR_ZLIB_DONE if we've finished the entire compression/decompression.
466 * Return TOR_ZLIB_OK if we're processed everything from the input.
467 * Return TOR_ZLIB_BUF_FULL if we're out of space on <b>out</b>.
468 * Return TOR_ZLIB_ERR if the stream is corrupt.
471 tor_zlib_process(tor_zlib_state_t
*state
,
472 char **out
, size_t *out_len
,
473 const char **in
, size_t *in_len
,
477 tor_assert(*in_len
<= UINT_MAX
);
478 tor_assert(*out_len
<= UINT_MAX
);
479 state
->stream
.next_in
= (unsigned char*) *in
;
480 state
->stream
.avail_in
= (unsigned int)*in_len
;
481 state
->stream
.next_out
= (unsigned char*) *out
;
482 state
->stream
.avail_out
= (unsigned int)*out_len
;
484 if (state
->compress
) {
485 err
= deflate(&state
->stream
, finish
? Z_FINISH
: Z_NO_FLUSH
);
487 err
= inflate(&state
->stream
, finish
? Z_FINISH
: Z_SYNC_FLUSH
);
490 state
->input_so_far
+= state
->stream
.next_in
- ((unsigned char*)*in
);
491 state
->output_so_far
+= state
->stream
.next_out
- ((unsigned char*)*out
);
493 *out
= (char*) state
->stream
.next_out
;
494 *out_len
= state
->stream
.avail_out
;
495 *in
= (const char *) state
->stream
.next_in
;
496 *in_len
= state
->stream
.avail_in
;
498 if (! state
->compress
&&
499 is_compression_bomb(state
->input_so_far
, state
->output_so_far
)) {
500 log_warn(LD_DIR
, "Possible zlib bomb; abandoning stream.");
507 return TOR_ZLIB_DONE
;
509 if (state
->stream
.avail_in
== 0 && !finish
)
511 return TOR_ZLIB_BUF_FULL
;
513 if (state
->stream
.avail_out
== 0 || finish
)
514 return TOR_ZLIB_BUF_FULL
;
517 log_warn(LD_GENERAL
, "Gzip returned an error: %s",
518 state
->stream
.msg
? state
->stream
.msg
: "<no message>");
523 /** Deallocate <b>state</b>. */
525 tor_zlib_free(tor_zlib_state_t
*state
)
530 total_zlib_allocation
-= state
->allocation
;
533 deflateEnd(&state
->stream
);
535 inflateEnd(&state
->stream
);
540 /** Return an approximate number of bytes used in RAM to hold a state with
541 * window bits <b>windowBits</b> and compression level 'memlevel' */
543 tor_zlib_state_size_precalc(int inflate
, int windowbits
, int memlevel
)
547 #define A_FEW_KILOBYTES 2048
552 "The memory requirements for inflate are (in bytes) 1 << windowBits
553 that is, 32K for windowBits=15 (default value) plus a few kilobytes
556 return sizeof(tor_zlib_state_t
) + sizeof(struct z_stream_s
) +
557 (1 << 15) + A_FEW_KILOBYTES
;
559 /* Also from zconf.h:
561 "The memory requirements for deflate are (in bytes):
562 (1 << (windowBits+2)) + (1 << (memLevel+9))
563 ... plus a few kilobytes for small objects."
565 return sizeof(tor_zlib_state_t
) + sizeof(struct z_stream_s
) +
566 (1 << (windowbits
+ 2)) + (1 << (memlevel
+ 9)) + A_FEW_KILOBYTES
;
568 #undef A_FEW_KILOBYTES
571 /** Return the approximate number of bytes allocated for <b>state</b>. */
573 tor_zlib_state_size(const tor_zlib_state_t
*state
)
575 return state
->allocation
;
578 /** Return the approximate number of bytes allocated for all zlib states. */
580 tor_zlib_get_total_allocation(void)
582 return total_zlib_allocation
;