src/common/torgzip.c

   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 */
   5
   6 /**
   7  * \file torgzip.c
   8  * \brief A simple in-memory gzip implementation.
   9  **/
  10
  11 #include "orconfig.h"
  12
  13 #include <stdlib.h>
  14 #include <stdio.h>
  15 #include <assert.h>
  16 #include <string.h>
  17 #include "torint.h"
  18
  19 #ifdef HAVE_NETINET_IN_H
  20 #include <netinet/in.h>
  21 #endif
  22
  23 #include "util.h"
  24 #include "torlog.h"
  25 #include "torgzip.h"
  26
  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.
  30
  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.
  33 */
  34 #ifndef _LARGEFILE64_SOURCE
  35 #define _LARGEFILE64_SOURCE 0
  36 #endif
  37 #ifndef _LFS64_LARGEFILE
  38 #define _LFS64_LARGEFILE 0
  39 #endif
  40 #ifndef _FILE_OFFSET_BITS
  41 #define _FILE_OFFSET_BITS 0
  42 #endif
  43 #ifndef off64_t
  44 #define off64_t int64_t
  45 #endif
  46
  47 #include <zlib.h>
  48
  49 #if defined ZLIB_VERNUM && ZLIB_VERNUM < 0x1200
  50 #error "We require zlib version 1.2 or later."
  51 #endif
  52
  53 static size_t tor_zlib_state_size_precalc(int inflate,
  54                                           int windowbits, int memlevel);
  55
  56 /** Total number of bytes allocated for zlib state */
  57 static size_t total_zlib_allocation = 0;
  58
  59 /** Return a string representation of the version of the currently running
  60  * version of zlib. */
  61 const char *
  62 tor_zlib_get_version_str(void)
  63 {
  64   return zlibVersion();
  65 }
  66
  67 /** Return a string representation of the version of the version of zlib
  68 * used at compilation. */
  69 const char *
  70 tor_zlib_get_header_version_str(void)
  71 {
  72   return ZLIB_VERSION;
  73 }
  74
  75 /** Return the 'bits' value to tell zlib to use <b>method</b>.*/
  76 static inline int
  77 method_bits(compress_method_t method, zlib_compression_level_t level)
  78 {
  79   /* Bits+16 means "use gzip" in zlib >= 1.2 */
  80   const int flag = method == GZIP_METHOD ? 16 : 0;
  81   switch (level) {
  82     default:
  83     case HIGH_COMPRESSION: return flag + 15;
  84     case MEDIUM_COMPRESSION: return flag + 13;
  85     case LOW_COMPRESSION: return flag + 11;
  86   }
  87 }
  88
  89 static inline int
  90 get_memlevel(zlib_compression_level_t level)
  91 {
  92   switch (level) {
  93     default:
  94     case HIGH_COMPRESSION: return 8;
  95     case MEDIUM_COMPRESSION: return 7;
  96     case LOW_COMPRESSION: return 6;
  97   }
  98 }
  99
 100 /** @{ */
 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.
 105  *
 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.
 113  */
 114 #define MAX_UNCOMPRESSION_FACTOR 25
 115 #define CHECK_FOR_COMPRESSION_BOMB_AFTER (1024*64)
 116 /** @} */
 117
 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. */
 120 static int
 121 is_compression_bomb(size_t size_in, size_t size_out)
 122 {
 123   if (size_in == 0 || size_out < CHECK_FOR_COMPRESSION_BOMB_AFTER)
 124     return 0;
 125
 126   return (size_out / size_in > MAX_UNCOMPRESSION_FACTOR);
 127 }
 128
 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.
 133  */
 134 int
 135 tor_gzip_compress(char **out, size_t *out_len,
 136                   const char *in, size_t in_len,
 137                   compress_method_t method)
 138 {
 139   struct z_stream_s *stream = NULL;
 140   size_t out_size, old_size;
 141   off_t offset;
 142
 143   tor_assert(out);
 144   tor_assert(out_len);
 145   tor_assert(in);
 146   tor_assert(in_len < UINT_MAX);
 147
 148   *out = NULL;
 149
 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;
 156
 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>");
 164     goto err;
 165     //LCOV_EXCL_STOP
 166   }
 167
 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;
 174
 175   while (1) {
 176     switch (deflate(stream, Z_FINISH))
 177       {
 178       case Z_STREAM_END:
 179         goto done;
 180       case Z_OK:
 181         /* In case zlib doesn't work as I think .... */
 182         if (stream->avail_out >= stream->avail_in+16)
 183           break;
 184         /* Falls through. */
 185       case Z_BUF_ERROR:
 186         offset = stream->next_out - ((unsigned char*)*out);
 187         old_size = out_size;
 188         out_size *= 2;
 189         if (out_size < old_size) {
 190           log_warn(LD_GENERAL, "Size overflow in compression.");
 191           goto err;
 192         }
 193         *out = tor_realloc(*out, out_size);
 194         stream->next_out = (unsigned char*)(*out + offset);
 195         if (out_size - offset > UINT_MAX) {
 196           log_warn(LD_BUG,  "Ran over unsigned int limit of zlib while "
 197                    "uncompressing.");
 198           goto err;
 199         }
 200         stream->avail_out = (unsigned int)(out_size - offset);
 201         break;
 202       default:
 203         log_warn(LD_GENERAL, "Gzip compression didn't finish: %s",
 204                  stream->msg ? stream->msg : "<no message>");
 205         goto err;
 206       }
 207   }
 208  done:
 209   *out_len = stream->total_out;
 210 #ifdef OPENBSD
 211   /* "Hey Rocky!  Watch me change an unsigned field to a signed field in a
 212    *    third-party API!"
 213    * "Oh, that trick will just make people do unsafe casts to the unsigned
 214    *    type in their cross-platform code!"
 215    * "Don't be foolish.  I'm _sure_ they'll have the good sense to make sure
 216    *    the newly unsigned field isn't negative." */
 217   tor_assert(stream->total_out >= 0);
 218 #endif
 219   if (deflateEnd(stream)!=Z_OK) {
 220     // LCOV_EXCL_START -- unreachable if we handled the zlib structure right
 221     tor_assert_nonfatal_unreached();
 222     log_warn(LD_BUG, "Error freeing gzip structures");
 223     goto err;
 224     // LCOV_EXCL_STOP
 225   }
 226   tor_free(stream);
 227
 228   if (is_compression_bomb(*out_len, in_len)) {
 229     log_warn(LD_BUG, "We compressed something and got an insanely high "
 230           "compression factor; other Tors would think this was a zlib bomb.");
 231     goto err;
 232   }
 233
 234   return 0;
 235  err:
 236   if (stream) {
 237     deflateEnd(stream);
 238     tor_free(stream);
 239   }
 240   tor_free(*out);
 241   return -1;
 242 }
 243
 244 /** Given zero or more zlib-compressed or gzip-compressed strings of
 245  * total length
 246  * <b>in_len</b> bytes at <b>in</b>, uncompress them into a newly allocated
 247  * buffer, using the method described in <b>method</b>.  Store the uncompressed
 248  * string in *<b>out</b>, and its length in *<b>out_len</b>.  Return 0 on
 249  * success, -1 on failure.
 250  *
 251  * If <b>complete_only</b> is true, we consider a truncated input as a
 252  * failure; otherwise we decompress as much as we can.  Warn about truncated
 253  * or corrupt inputs at <b>protocol_warn_level</b>.
 254  */
 255 int
 256 tor_gzip_uncompress(char **out, size_t *out_len,
 257                     const char *in, size_t in_len,
 258                     compress_method_t method,
 259                     int complete_only,
 260                     int protocol_warn_level)
 261 {
 262   struct z_stream_s *stream = NULL;
 263   size_t out_size, old_size;
 264   off_t offset;
 265   int r;
 266
 267   tor_assert(out);
 268   tor_assert(out_len);
 269   tor_assert(in);
 270   tor_assert(in_len < UINT_MAX);
 271
 272   *out = NULL;
 273
 274   stream = tor_malloc_zero(sizeof(struct z_stream_s));
 275   stream->zalloc = Z_NULL;
 276   stream->zfree = Z_NULL;
 277   stream->opaque = NULL;
 278   stream->next_in = (unsigned char*) in;
 279   stream->avail_in = (unsigned int)in_len;
 280
 281   if (inflateInit2(stream,
 282                    method_bits(method, HIGH_COMPRESSION)) != Z_OK) {
 283     // LCOV_EXCL_START -- can only hit this if we give bad inputs.
 284     log_warn(LD_GENERAL, "Error from inflateInit2: %s",
 285              stream->msg?stream->msg:"<no message>");
 286     goto err;
 287     // LCOV_EXCL_STOP
 288   }
 289
 290   out_size = in_len * 2;  /* guess 50% compression. */
 291   if (out_size < 1024) out_size = 1024;
 292   if (out_size >= SIZE_T_CEILING || out_size > UINT_MAX)
 293     goto err;
 294
 295   *out = tor_malloc(out_size);
 296   stream->next_out = (unsigned char*)*out;
 297   stream->avail_out = (unsigned int)out_size;
 298
 299   while (1) {
 300     switch (inflate(stream, complete_only ? Z_FINISH : Z_SYNC_FLUSH))
 301       {
 302       case Z_STREAM_END:
 303         if (stream->avail_in == 0)
 304           goto done;
 305         /* There may be more compressed data here. */
 306         if ((r = inflateEnd(stream)) != Z_OK) {
 307           log_warn(LD_BUG, "Error freeing gzip structures");
 308           goto err;
 309         }
 310         if (inflateInit2(stream,
 311                          method_bits(method,HIGH_COMPRESSION)) != Z_OK) {
 312           log_warn(LD_GENERAL, "Error from second inflateInit2: %s",
 313                    stream->msg?stream->msg:"<no message>");
 314           goto err;
 315         }
 316         break;
 317       case Z_OK:
 318         if (!complete_only && stream->avail_in == 0)
 319           goto done;
 320         /* In case zlib doesn't work as I think.... */
 321         if (stream->avail_out >= stream->avail_in+16)
 322           break;
 323         /* Falls through. */
 324       case Z_BUF_ERROR:
 325         if (stream->avail_out > 0) {
 326           log_fn(protocol_warn_level, LD_PROTOCOL,
 327                  "possible truncated or corrupt zlib data");
 328           goto err;
 329         }
 330         offset = stream->next_out - (unsigned char*)*out;
 331         old_size = out_size;
 332         out_size *= 2;
 333         if (out_size < old_size) {
 334           log_warn(LD_GENERAL, "Size overflow in uncompression.");
 335           goto err;
 336         }
 337         if (is_compression_bomb(in_len, out_size)) {
 338           log_warn(LD_GENERAL, "Input looks like a possible zlib bomb; "
 339                    "not proceeding.");
 340           goto err;
 341         }
 342         if (out_size >= SIZE_T_CEILING) {
 343           log_warn(LD_BUG, "Hit SIZE_T_CEILING limit while uncompressing.");
 344           goto err;
 345         }
 346         *out = tor_realloc(*out, out_size);
 347         stream->next_out = (unsigned char*)(*out + offset);
 348         if (out_size - offset > UINT_MAX) {
 349           log_warn(LD_BUG,  "Ran over unsigned int limit of zlib while "
 350                    "uncompressing.");
 351           goto err;
 352         }
 353         stream->avail_out = (unsigned int)(out_size - offset);
 354         break;
 355       default:
 356         log_warn(LD_GENERAL, "Gzip decompression returned an error: %s",
 357                  stream->msg ? stream->msg : "<no message>");
 358         goto err;
 359       }
 360   }
 361  done:
 362   *out_len = stream->next_out - (unsigned char*)*out;
 363   r = inflateEnd(stream);
 364   tor_free(stream);
 365   if (r != Z_OK) {
 366     log_warn(LD_BUG, "Error freeing gzip structures");
 367     goto err;
 368   }
 369
 370   /* NUL-terminate output. */
 371   if (out_size == *out_len)
 372     *out = tor_realloc(*out, out_size + 1);
 373   (*out)[*out_len] = '\0';
 374
 375   return 0;
 376  err:
 377   if (stream) {
 378     inflateEnd(stream);
 379     tor_free(stream);
 380   }
 381   if (*out) {
 382     tor_free(*out);
 383   }
 384   return -1;
 385 }
 386
 387 /** Try to tell whether the <b>in_len</b>-byte string in <b>in</b> is likely
 388  * to be compressed or not.  If it is, return the likeliest compression method.
 389  * Otherwise, return UNKNOWN_METHOD.
 390  */
 391 compress_method_t
 392 detect_compression_method(const char *in, size_t in_len)
 393 {
 394   if (in_len > 2 && fast_memeq(in, "\x1f\x8b", 2)) {
 395     return GZIP_METHOD;
 396   } else if (in_len > 2 && (in[0] & 0x0f) == 8 &&
 397              (ntohs(get_uint16(in)) % 31) == 0) {
 398     return ZLIB_METHOD;
 399   } else {
 400     return UNKNOWN_METHOD;
 401   }
 402 }
 403
 404 /** Internal state for an incremental zlib compression/decompression.  The
 405  * body of this struct is not exposed. */
 406 struct tor_zlib_state_t {
 407   struct z_stream_s stream; /**< The zlib stream */
 408   int compress; /**< True if we are compressing; false if we are inflating */
 409
 410   /** Number of bytes read so far.  Used to detect zlib bombs. */
 411   size_t input_so_far;
 412   /** Number of bytes written so far.  Used to detect zlib bombs. */
 413   size_t output_so_far;
 414
 415   /** Approximate number of bytes allocated for this object. */
 416   size_t allocation;
 417 };
 418
 419 /** Construct and return a tor_zlib_state_t object using <b>method</b>.  If
 420  * <b>compress</b>, it's for compression; otherwise it's for
 421  * decompression. */
 422 tor_zlib_state_t *
 423 tor_zlib_new(int compress_, compress_method_t method,
 424              zlib_compression_level_t compression_level)
 425 {
 426   tor_zlib_state_t *out;
 427   int bits, memlevel;
 428
 429  if (! compress_) {
 430    /* use this setting for decompression, since we might have the
 431     * max number of window bits */
 432    compression_level = HIGH_COMPRESSION;
 433  }
 434
 435  out = tor_malloc_zero(sizeof(tor_zlib_state_t));
 436  out->stream.zalloc = Z_NULL;
 437  out->stream.zfree = Z_NULL;
 438  out->stream.opaque = NULL;
 439  out->compress = compress_;
 440  bits = method_bits(method, compression_level);
 441  memlevel = get_memlevel(compression_level);
 442  if (compress_) {
 443    if (deflateInit2(&out->stream, Z_BEST_COMPRESSION, Z_DEFLATED,
 444                     bits, memlevel,
 445                     Z_DEFAULT_STRATEGY) != Z_OK)
 446      goto err; // LCOV_EXCL_LINE
 447  } else {
 448    if (inflateInit2(&out->stream, bits) != Z_OK)
 449      goto err; // LCOV_EXCL_LINE
 450  }
 451  out->allocation = tor_zlib_state_size_precalc(!compress_, bits, memlevel);
 452
 453  total_zlib_allocation += out->allocation;
 454
 455  return out;
 456
 457  err:
 458  tor_free(out);
 459  return NULL;
 460 }
 461
 462 /** Compress/decompress some bytes using <b>state</b>.  Read up to
 463  * *<b>in_len</b> bytes from *<b>in</b>, and write up to *<b>out_len</b> bytes
 464  * to *<b>out</b>, adjusting the values as we go.  If <b>finish</b> is true,
 465  * we've reached the end of the input.
 466  *
 467  * Return TOR_ZLIB_DONE if we've finished the entire compression/decompression.
 468  * Return TOR_ZLIB_OK if we're processed everything from the input.
 469  * Return TOR_ZLIB_BUF_FULL if we're out of space on <b>out</b>.
 470  * Return TOR_ZLIB_ERR if the stream is corrupt.
 471  */
 472 tor_zlib_output_t
 473 tor_zlib_process(tor_zlib_state_t *state,
 474                  char **out, size_t *out_len,
 475                  const char **in, size_t *in_len,
 476                  int finish)
 477 {
 478   int err;
 479   tor_assert(*in_len <= UINT_MAX);
 480   tor_assert(*out_len <= UINT_MAX);
 481   state->stream.next_in = (unsigned char*) *in;
 482   state->stream.avail_in = (unsigned int)*in_len;
 483   state->stream.next_out = (unsigned char*) *out;
 484   state->stream.avail_out = (unsigned int)*out_len;
 485
 486   if (state->compress) {
 487     err = deflate(&state->stream, finish ? Z_FINISH : Z_NO_FLUSH);
 488   } else {
 489     err = inflate(&state->stream, finish ? Z_FINISH : Z_SYNC_FLUSH);
 490   }
 491
 492   state->input_so_far += state->stream.next_in - ((unsigned char*)*in);
 493   state->output_so_far += state->stream.next_out - ((unsigned char*)*out);
 494
 495   *out = (char*) state->stream.next_out;
 496   *out_len = state->stream.avail_out;
 497   *in = (const char *) state->stream.next_in;
 498   *in_len = state->stream.avail_in;
 499
 500   if (! state->compress &&
 501       is_compression_bomb(state->input_so_far, state->output_so_far)) {
 502     log_warn(LD_DIR, "Possible zlib bomb; abandoning stream.");
 503     return TOR_ZLIB_ERR;
 504   }
 505
 506   switch (err)
 507     {
 508     case Z_STREAM_END:
 509       return TOR_ZLIB_DONE;
 510     case Z_BUF_ERROR:
 511       if (state->stream.avail_in == 0 && !finish)
 512         return TOR_ZLIB_OK;
 513       return TOR_ZLIB_BUF_FULL;
 514     case Z_OK:
 515       if (state->stream.avail_out == 0 || finish)
 516         return TOR_ZLIB_BUF_FULL;
 517       return TOR_ZLIB_OK;
 518     default:
 519       log_warn(LD_GENERAL, "Gzip returned an error: %s",
 520                state->stream.msg ? state->stream.msg : "<no message>");
 521       return TOR_ZLIB_ERR;
 522     }
 523 }
 524
 525 /** Deallocate <b>state</b>. */
 526 void
 527 tor_zlib_free(tor_zlib_state_t *state)
 528 {
 529   if (!state)
 530     return;
 531
 532  total_zlib_allocation -= state->allocation;
 533
 534   if (state->compress)
 535     deflateEnd(&state->stream);
 536   else
 537     inflateEnd(&state->stream);
 538
 539   tor_free(state);
 540 }
 541
 542 /** Return an approximate number of bytes used in RAM to hold a state with
 543  * window bits <b>windowBits</b> and compression level 'memlevel' */
 544 static size_t
 545 tor_zlib_state_size_precalc(int inflate_, int windowbits, int memlevel)
 546 {
 547   windowbits &= 15;
 548
 549 #define A_FEW_KILOBYTES 2048
 550
 551   if (inflate_) {
 552     /* From zconf.h:
 553
 554        "The memory requirements for inflate are (in bytes) 1 << windowBits
 555        that is, 32K for windowBits=15 (default value) plus a few kilobytes
 556        for small objects."
 557     */
 558     return sizeof(tor_zlib_state_t) + sizeof(struct z_stream_s) +
 559       (1 << 15) + A_FEW_KILOBYTES;
 560   } else {
 561     /* Also from zconf.h:
 562
 563        "The memory requirements for deflate are (in bytes):
 564             (1 << (windowBits+2)) +  (1 << (memLevel+9))
 565         ... plus a few kilobytes for small objects."
 566     */
 567     return sizeof(tor_zlib_state_t) + sizeof(struct z_stream_s) +
 568       (1 << (windowbits + 2)) + (1 << (memlevel + 9)) + A_FEW_KILOBYTES;
 569   }
 570 #undef A_FEW_KILOBYTES
 571 }
 572
 573 /** Return the approximate number of bytes allocated for <b>state</b>. */
 574 size_t
 575 tor_zlib_state_size(const tor_zlib_state_t *state)
 576 {
 577   return state->allocation;
 578 }
 579
 580 /** Return the approximate number of bytes allocated for all zlib states. */
 581 size_t
 582 tor_zlib_get_total_allocation(void)
 583 {
 584   return total_zlib_allocation;
 585 }
 586