1// Copyright (c) 2011 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// TODO(rtenhove) clean up frame buffer size calculations so that we aren't
6// constantly adding and subtracting header sizes; this is ugly and error-
7// prone.
8
9#include "net/spdy/spdy_framer.h"
10
11#include "base/memory/scoped_ptr.h"
12#include "base/metrics/stats_counters.h"
13#ifndef ANDROID
14#include "base/third_party/valgrind/memcheck.h"
15#endif
16#include "net/spdy/spdy_frame_builder.h"
17#include "net/spdy/spdy_bitmasks.h"
18
19#if defined(USE_SYSTEM_ZLIB)
20#include <zlib.h>
21#else
22#include "third_party/zlib/zlib.h"
23#endif
24
25namespace {
26
27// The following compression setting are based on Brian Olson's analysis. See
28// https://groups.google.com/group/spdy-dev/browse_thread/thread/dfaf498542fac792
29// for more details.
30#ifdef ANDROID
31const int kCompressorLevel = 0;
32#else
33const int kCompressorLevel = 9;
34#endif
35const int kCompressorWindowSizeInBits = 11;
36const int kCompressorMemLevel = 1;
37
38// Adler ID for the SPDY header compressor dictionary.
39uLong dictionary_id = 0;
40
41}  // namespace
42
43namespace spdy {
44
45// This is just a hacked dictionary to use for shrinking HTTP-like headers.
46// TODO(mbelshe): Use a scientific methodology for computing the dictionary.
47const char SpdyFramer::kDictionary[] =
48  "optionsgetheadpostputdeletetraceacceptaccept-charsetaccept-encodingaccept-"
49  "languageauthorizationexpectfromhostif-modified-sinceif-matchif-none-matchi"
50  "f-rangeif-unmodifiedsincemax-forwardsproxy-authorizationrangerefererteuser"
51  "-agent10010120020120220320420520630030130230330430530630740040140240340440"
52  "5406407408409410411412413414415416417500501502503504505accept-rangesageeta"
53  "glocationproxy-authenticatepublicretry-afterservervarywarningwww-authentic"
54  "ateallowcontent-basecontent-encodingcache-controlconnectiondatetrailertran"
55  "sfer-encodingupgradeviawarningcontent-languagecontent-lengthcontent-locati"
56  "oncontent-md5content-rangecontent-typeetagexpireslast-modifiedset-cookieMo"
57  "ndayTuesdayWednesdayThursdayFridaySaturdaySundayJanFebMarAprMayJunJulAugSe"
58  "pOctNovDecchunkedtext/htmlimage/pngimage/jpgimage/gifapplication/xmlapplic"
59  "ation/xhtmltext/plainpublicmax-agecharset=iso-8859-1utf-8gzipdeflateHTTP/1"
60  ".1statusversionurl";
61const int SpdyFramer::kDictionarySize = arraysize(kDictionary);
62
63// By default is compression on or off.
64bool SpdyFramer::compression_default_ = true;
65int SpdyFramer::spdy_version_ = kSpdyProtocolVersion;
66
67// The initial size of the control frame buffer; this is used internally
68// as we parse through control frames. (It is exposed here for unit test
69// purposes.)
70size_t SpdyFramer::kControlFrameBufferInitialSize = 8 * 1024;
71
72// The maximum size of the control frame buffer that we support.
73// TODO(mbelshe): We should make this stream-based so there are no limits.
74size_t SpdyFramer::kControlFrameBufferMaxSize = 16 * 1024;
75
76const SpdyStreamId SpdyFramer::kInvalidStream = -1;
77const size_t SpdyFramer::kHeaderDataChunkMaxSize = 1024;
78
79#ifdef DEBUG_SPDY_STATE_CHANGES
80#define CHANGE_STATE(newstate) \
81{ \
82  do { \
83    LOG(INFO) << "Changing state from: " \
84      << StateToString(state_) \
85      << " to " << StateToString(newstate) << "\n"; \
86    state_ = newstate; \
87  } while (false); \
88}
89#else
90#define CHANGE_STATE(newstate) (state_ = newstate)
91#endif
92
93int DecompressHeaderBlockInZStream(z_stream* decompressor) {
94  int rv = inflate(decompressor, Z_SYNC_FLUSH);
95  if (rv == Z_NEED_DICT) {
96    // Need to try again with the right dictionary.
97    if (decompressor->adler == dictionary_id) {
98      rv = inflateSetDictionary(decompressor,
99                                (const Bytef*)SpdyFramer::kDictionary,
100                                SpdyFramer::kDictionarySize);
101      if (rv == Z_OK)
102        rv = inflate(decompressor, Z_SYNC_FLUSH);
103    }
104  }
105  return rv;
106}
107
108// Retrieve serialized length of SpdyHeaderBlock.
109size_t GetSerializedLength(const SpdyHeaderBlock* headers) {
110  size_t total_length = SpdyControlFrame::kNumNameValuePairsSize;
111  SpdyHeaderBlock::const_iterator it;
112  for (it = headers->begin(); it != headers->end(); ++it) {
113    // We add space for the length of the name and the length of the value as
114    // well as the length of the name and the length of the value.
115    total_length += SpdyControlFrame::kLengthOfNameSize +
116                    it->first.size() +
117                    SpdyControlFrame::kLengthOfValueSize +
118                    it->second.size();
119  }
120  return total_length;
121}
122
123// Serializes a SpdyHeaderBlock.
124void WriteHeaderBlock(SpdyFrameBuilder* frame, const SpdyHeaderBlock* headers) {
125  frame->WriteUInt16(headers->size());  // Number of headers.
126  SpdyHeaderBlock::const_iterator it;
127  for (it = headers->begin(); it != headers->end(); ++it) {
128    bool wrote_header;
129    wrote_header = frame->WriteString(it->first);
130    wrote_header &= frame->WriteString(it->second);
131    DCHECK(wrote_header);
132  }
133}
134
135// Creates a FlagsAndLength.
136FlagsAndLength CreateFlagsAndLength(SpdyControlFlags flags, size_t length) {
137  DCHECK_EQ(0u, length & ~static_cast<size_t>(kLengthMask));
138  FlagsAndLength flags_length;
139  flags_length.length_ = htonl(static_cast<uint32>(length));
140  DCHECK_EQ(0, flags & ~kControlFlagsMask);
141  flags_length.flags_[0] = flags;
142  return flags_length;
143}
144
145SpdyFramer::SpdyFramer()
146    : state_(SPDY_RESET),
147      error_code_(SPDY_NO_ERROR),
148      remaining_data_(0),
149      remaining_control_payload_(0),
150      remaining_control_header_(0),
151      current_frame_buffer_(NULL),
152      current_frame_len_(0),
153      current_frame_capacity_(0),
154      validate_control_frame_sizes_(true),
155      enable_compression_(compression_default_),
156      visitor_(NULL) {
157}
158
159SpdyFramer::~SpdyFramer() {
160  if (header_compressor_.get()) {
161    deflateEnd(header_compressor_.get());
162  }
163  if (header_decompressor_.get()) {
164    inflateEnd(header_decompressor_.get());
165  }
166  CleanupStreamCompressorsAndDecompressors();
167  delete [] current_frame_buffer_;
168}
169
170const char* SpdyFramer::StatusCodeToString(int status_code) {
171  switch (status_code) {
172    case INVALID:
173      return "INVALID";
174    case PROTOCOL_ERROR:
175      return "PROTOCOL_ERROR";
176    case INVALID_STREAM:
177      return "INVALID_STREAM";
178    case REFUSED_STREAM:
179      return "REFUSED_STREAM";
180    case UNSUPPORTED_VERSION:
181      return "UNSUPPORTED_VERSION";
182    case CANCEL:
183      return "CANCEL";
184    case INTERNAL_ERROR:
185      return "INTERNAL_ERROR";
186    case FLOW_CONTROL_ERROR:
187      return "FLOW_CONTROL_ERROR";
188  }
189  return "UNKNOWN_STATUS";
190}
191
192const char* SpdyFramer::ControlTypeToString(SpdyControlType type) {
193  switch (type) {
194    case SYN_STREAM:
195      return "SYN_STREAM";
196    case SYN_REPLY:
197      return "SYN_REPLY";
198    case RST_STREAM:
199      return "RST_STREAM";
200    case SETTINGS:
201      return "SETTINGS";
202    case NOOP:
203      return "NOOP";
204    case PING:
205      return "PING";
206    case GOAWAY:
207      return "GOAWAY";
208    case HEADERS:
209      return "HEADERS";
210    case WINDOW_UPDATE:
211      return "WINDOW_UPDATE";
212    case NUM_CONTROL_FRAME_TYPES:
213      break;
214  }
215  return "UNKNOWN_CONTROL_TYPE";
216}
217
218size_t SpdyFramer::ProcessInput(const char* data, size_t len) {
219  DCHECK(visitor_);
220  DCHECK(data);
221
222  size_t original_len = len;
223  while (len != 0) {
224    switch (state_) {
225      case SPDY_ERROR:
226      case SPDY_DONE:
227        goto bottom;
228
229      case SPDY_AUTO_RESET:
230      case SPDY_RESET:
231        Reset();
232        CHANGE_STATE(SPDY_READING_COMMON_HEADER);
233        continue;
234
235      case SPDY_READING_COMMON_HEADER: {
236        size_t bytes_read = ProcessCommonHeader(data, len);
237        len -= bytes_read;
238        data += bytes_read;
239        continue;
240      }
241
242      // Arguably, this case is not necessary, as no bytes are consumed here.
243      // I felt it was a nice partitioning, however (which probably indicates
244      // that it should be refactored into its own function!)
245      // TODO(hkhalil): Remove -- while loop above prevents proper handling of
246      // zero-length control frames.
247      case SPDY_INTERPRET_CONTROL_FRAME_COMMON_HEADER:
248        ProcessControlFrameHeader();
249        continue;
250
251      case SPDY_CONTROL_FRAME_BEFORE_HEADER_BLOCK: {
252        // Control frames that contain header blocks (SYN_STREAM, SYN_REPLY,
253        // HEADERS) take a different path through the state machine - they
254        // will go:
255        //   1. SPDY_INTERPRET_CONTROL_FRAME_COMMON HEADER
256        //   2. SPDY_CONTROL_FRAME_BEFORE_HEADER_BLOCK
257        //   3. SPDY_CONTROL_FRAME_HEADER_BLOCK
258        //
259        //  All other control frames will use the alternate route:
260        //   1. SPDY_INTERPRET_CONTROL_FRAME_COMMON_HEADER
261        //   2. SPDY_CONTROL_FRAME_PAYLOAD
262        int bytes_read = ProcessControlFrameBeforeHeaderBlock(data, len);
263        len -= bytes_read;
264        data += bytes_read;
265        continue;
266      }
267
268      case SPDY_CONTROL_FRAME_HEADER_BLOCK: {
269        int bytes_read = ProcessControlFrameHeaderBlock(data, len);
270        len -= bytes_read;
271        data += bytes_read;
272        continue;
273      }
274
275      case SPDY_CONTROL_FRAME_PAYLOAD: {
276        size_t bytes_read = ProcessControlFramePayload(data, len);
277        len -= bytes_read;
278        data += bytes_read;
279      }
280        // intentional fallthrough
281      case SPDY_IGNORE_REMAINING_PAYLOAD:
282        // control frame has too-large payload
283        // intentional fallthrough
284      case SPDY_FORWARD_STREAM_FRAME: {
285        size_t bytes_read = ProcessDataFramePayload(data, len);
286        len -= bytes_read;
287        data += bytes_read;
288        continue;
289      }
290      default:
291        break;
292    }
293  }
294 bottom:
295  return original_len - len;
296}
297
298void SpdyFramer::Reset() {
299  state_ = SPDY_RESET;
300  error_code_ = SPDY_NO_ERROR;
301  remaining_data_ = 0;
302  remaining_control_payload_ = 0;
303  remaining_control_header_ = 0;
304  current_frame_len_ = 0;
305  if (current_frame_capacity_ != kControlFrameBufferInitialSize) {
306    delete [] current_frame_buffer_;
307    current_frame_buffer_ = 0;
308    current_frame_capacity_ = 0;
309    ExpandControlFrameBuffer(kControlFrameBufferInitialSize);
310  }
311}
312
313bool SpdyFramer::ParseHeaderBlock(const SpdyFrame* frame,
314                                  SpdyHeaderBlock* block) {
315  SpdyControlFrame control_frame(frame->data(), false);
316  uint32 type = control_frame.type();
317  if (type != SYN_STREAM && type != SYN_REPLY && type != HEADERS)
318    return false;
319
320  // Find the header data within the control frame.
321  scoped_ptr<SpdyFrame> decompressed_frame(DecompressFrame(*frame));
322  if (!decompressed_frame.get())
323    return false;
324
325  const char *header_data = NULL;
326  int header_length = 0;
327
328  switch (type) {
329    case SYN_STREAM:
330      {
331        SpdySynStreamControlFrame syn_frame(decompressed_frame->data(), false);
332        header_data = syn_frame.header_block();
333        header_length = syn_frame.header_block_len();
334      }
335      break;
336    case SYN_REPLY:
337      {
338        SpdySynReplyControlFrame syn_frame(decompressed_frame->data(), false);
339        header_data = syn_frame.header_block();
340        header_length = syn_frame.header_block_len();
341      }
342      break;
343    case HEADERS:
344      {
345        SpdyHeadersControlFrame header_frame(decompressed_frame->data(), false);
346        header_data = header_frame.header_block();
347        header_length = header_frame.header_block_len();
348      }
349      break;
350  }
351
352  SpdyFrameBuilder builder(header_data, header_length);
353  void* iter = NULL;
354  uint16 num_headers;
355  if (builder.ReadUInt16(&iter, &num_headers)) {
356    int index;
357    for (index = 0; index < num_headers; ++index) {
358      std::string name;
359      std::string value;
360      if (!builder.ReadString(&iter, &name))
361        break;
362      if (!builder.ReadString(&iter, &value))
363        break;
364      if (!name.size() || !value.size())
365        return false;
366      if (block->find(name) == block->end()) {
367        (*block)[name] = value;
368      } else {
369        return false;
370      }
371    }
372    return index == num_headers &&
373        iter == header_data + header_length;
374  }
375  return false;
376}
377
378size_t SpdyFramer::UpdateCurrentFrameBuffer(const char** data, size_t* len,
379                                            size_t max_bytes) {
380  size_t bytes_to_read = std::min(*len, max_bytes);
381  DCHECK_GE(current_frame_capacity_, current_frame_len_ + bytes_to_read);
382  memcpy(&current_frame_buffer_[current_frame_len_], *data, bytes_to_read);
383  current_frame_len_ += bytes_to_read;
384  *data += bytes_to_read;
385  *len -= bytes_to_read;
386  return bytes_to_read;
387}
388
389size_t SpdyFramer::ProcessControlFrameBeforeHeaderBlock(const char* data,
390                                                        size_t len) {
391  DCHECK_EQ(SPDY_CONTROL_FRAME_BEFORE_HEADER_BLOCK, state_);
392  DCHECK_GT(remaining_control_header_, 0u);
393  size_t original_len = len;
394
395  if (remaining_control_header_) {
396    size_t bytes_read = UpdateCurrentFrameBuffer(&data, &len,
397                                                 remaining_control_header_);
398    remaining_control_header_ -= bytes_read;
399    if (remaining_control_header_ == 0) {
400      SpdyControlFrame control_frame(current_frame_buffer_, false);
401      DCHECK(control_frame.type() == SYN_STREAM ||
402             control_frame.type() == SYN_REPLY ||
403             control_frame.type() == HEADERS);
404      visitor_->OnControl(&control_frame);
405
406      CHANGE_STATE(SPDY_CONTROL_FRAME_HEADER_BLOCK);
407    }
408  }
409  return original_len - len;
410}
411
412// Does not buffer the control payload. Instead, either passes directly to the
413// visitor or decompresses and then passes directly to the visitor, via
414// IncrementallyDeliverControlFrameHeaderData() or
415// IncrementallyDecompressControlFrameHeaderData() respectively.
416size_t SpdyFramer::NewProcessControlFrameHeaderBlock(const char* data,
417                                                     size_t data_len) {
418  DCHECK_EQ(SPDY_CONTROL_FRAME_HEADER_BLOCK, state_);
419  SpdyControlFrame control_frame(current_frame_buffer_, false);
420  bool processed_successfully = true;
421  DCHECK(control_frame.type() == SYN_STREAM ||
422         control_frame.type() == SYN_REPLY ||
423         control_frame.type() == HEADERS);
424  size_t process_bytes = std::min(data_len, remaining_control_payload_);
425  DCHECK_GT(process_bytes, 0u);
426
427  if (enable_compression_) {
428    processed_successfully = IncrementallyDecompressControlFrameHeaderData(
429        &control_frame, data, process_bytes);
430  } else {
431    processed_successfully = IncrementallyDeliverControlFrameHeaderData(
432        &control_frame, data, process_bytes);
433  }
434  remaining_control_payload_ -= process_bytes;
435
436  // Handle the case that there is no futher data in this frame.
437  if (remaining_control_payload_ == 0 && processed_successfully) {
438    // The complete header block has been delivered. We send a zero-length
439    // OnControlFrameHeaderData() to indicate this.
440    visitor_->OnControlFrameHeaderData(
441        GetControlFrameStreamId(&control_frame), NULL, 0);
442
443    // If this is a FIN, tell the caller.
444    if (control_frame.flags() & CONTROL_FLAG_FIN) {
445      visitor_->OnStreamFrameData(GetControlFrameStreamId(&control_frame),
446                                  NULL, 0);
447    }
448
449    CHANGE_STATE(SPDY_RESET);
450  }
451
452  // Handle error.
453  if (!processed_successfully) {
454    return data_len;
455  }
456
457  // Return amount processed.
458  return process_bytes;
459}
460
461size_t SpdyFramer::ProcessControlFrameHeaderBlock(const char* data,
462                                                  size_t data_len) {
463  DCHECK_EQ(SPDY_CONTROL_FRAME_HEADER_BLOCK, state_);
464  size_t original_data_len = data_len;
465  SpdyControlFrame control_frame(current_frame_buffer_, false);
466  bool read_successfully = true;
467  DCHECK(control_frame.type() == SYN_STREAM ||
468         control_frame.type() == SYN_REPLY ||
469         control_frame.type() == HEADERS);
470
471  if (enable_compression_) {
472    // Note that the header block is held in the frame's payload, and is not
473    // part of the frame's headers.
474    if (remaining_control_payload_ > 0) {
475      size_t bytes_read = UpdateCurrentFrameBuffer(
476          &data,
477          &data_len,
478          remaining_control_payload_);
479      remaining_control_payload_ -= bytes_read;
480      if (remaining_control_payload_ == 0) {
481        read_successfully = IncrementallyDecompressControlFrameHeaderData(
482            &control_frame);
483      }
484    }
485  } else {
486    size_t bytes_to_send = std::min(data_len, remaining_control_payload_);
487    DCHECK_GT(bytes_to_send, 0u);
488    read_successfully = IncrementallyDeliverControlFrameHeaderData(
489        &control_frame, data, bytes_to_send);
490    data_len -= bytes_to_send;
491    remaining_control_payload_ -= bytes_to_send;
492  }
493  if (remaining_control_payload_ == 0 && read_successfully) {
494    // The complete header block has been delivered.
495    visitor_->OnControlFrameHeaderData(GetControlFrameStreamId(&control_frame),
496                                       NULL, 0);
497
498    // If this is a FIN, tell the caller.
499    if (control_frame.flags() & CONTROL_FLAG_FIN) {
500      visitor_->OnStreamFrameData(GetControlFrameStreamId(&control_frame),
501                                  NULL, 0);
502    }
503
504    CHANGE_STATE(SPDY_RESET);
505  }
506  if (!read_successfully) {
507    return original_data_len;
508  }
509  return original_data_len - data_len;
510}
511
512/* static */
513bool SpdyFramer::ParseHeaderBlockInBuffer(const char* header_data,
514                                          size_t header_length,
515                                          SpdyHeaderBlock* block) {
516  SpdyFrameBuilder builder(header_data, header_length);
517  void* iter = NULL;
518  uint16 num_headers;
519  if (builder.ReadUInt16(&iter, &num_headers)) {
520    for (int index = 0; index < num_headers; ++index) {
521      std::string name;
522      std::string value;
523      if (!builder.ReadString(&iter, &name))
524        return false;
525      if (!builder.ReadString(&iter, &value))
526        return false;
527      if (block->find(name) == block->end()) {
528        (*block)[name] = value;
529      } else {
530        return false;
531      }
532    }
533    return true;
534  }
535  return false;
536}
537
538SpdySynStreamControlFrame* SpdyFramer::CreateSynStream(
539    SpdyStreamId stream_id, SpdyStreamId associated_stream_id, int priority,
540    SpdyControlFlags flags, bool compressed, const SpdyHeaderBlock* headers) {
541  SpdyFrameBuilder frame;
542
543  DCHECK_GT(stream_id, static_cast<SpdyStreamId>(0));
544  DCHECK_EQ(0u, stream_id & ~kStreamIdMask);
545  DCHECK_EQ(0u, associated_stream_id & ~kStreamIdMask);
546
547  frame.WriteUInt16(kControlFlagMask | spdy_version_);
548  frame.WriteUInt16(SYN_STREAM);
549  frame.WriteUInt32(0);  // Placeholder for the length and flags
550  frame.WriteUInt32(stream_id);
551  frame.WriteUInt32(associated_stream_id);
552  frame.WriteUInt16(ntohs(priority) << 6);  // Priority.
553
554  frame.WriteUInt16(headers->size());  // Number of headers.
555  SpdyHeaderBlock::const_iterator it;
556  for (it = headers->begin(); it != headers->end(); ++it) {
557    bool wrote_header;
558    wrote_header = frame.WriteString(it->first);
559    wrote_header &= frame.WriteString(it->second);
560    DCHECK(wrote_header);
561  }
562
563  // Write the length and flags.
564  size_t length = frame.length() - SpdyFrame::size();
565  DCHECK_EQ(0u, length & ~static_cast<size_t>(kLengthMask));
566  FlagsAndLength flags_length;
567  flags_length.length_ = htonl(static_cast<uint32>(length));
568  DCHECK_EQ(0, flags & ~kControlFlagsMask);
569  flags_length.flags_[0] = flags;
570  frame.WriteBytesToOffset(4, &flags_length, sizeof(flags_length));
571
572  scoped_ptr<SpdySynStreamControlFrame> syn_frame(
573      reinterpret_cast<SpdySynStreamControlFrame*>(frame.take()));
574  if (compressed) {
575    return reinterpret_cast<SpdySynStreamControlFrame*>(
576        CompressControlFrame(*syn_frame.get()));
577  }
578  return syn_frame.release();
579}
580
581SpdySynReplyControlFrame* SpdyFramer::CreateSynReply(SpdyStreamId stream_id,
582    SpdyControlFlags flags, bool compressed, const SpdyHeaderBlock* headers) {
583  DCHECK_GT(stream_id, 0u);
584  DCHECK_EQ(0u, stream_id & ~kStreamIdMask);
585
586  SpdyFrameBuilder frame;
587
588  frame.WriteUInt16(kControlFlagMask | spdy_version_);
589  frame.WriteUInt16(SYN_REPLY);
590  frame.WriteUInt32(0);  // Placeholder for the length and flags.
591  frame.WriteUInt32(stream_id);
592  frame.WriteUInt16(0);  // Unused
593
594  frame.WriteUInt16(headers->size());  // Number of headers.
595  SpdyHeaderBlock::const_iterator it;
596  for (it = headers->begin(); it != headers->end(); ++it) {
597    bool wrote_header;
598    wrote_header = frame.WriteString(it->first);
599    wrote_header &= frame.WriteString(it->second);
600    DCHECK(wrote_header);
601  }
602
603  // Write the length and flags.
604  size_t length = frame.length() - SpdyFrame::size();
605  DCHECK_EQ(0u, length & ~static_cast<size_t>(kLengthMask));
606  FlagsAndLength flags_length;
607  flags_length.length_ = htonl(static_cast<uint32>(length));
608  DCHECK_EQ(0, flags & ~kControlFlagsMask);
609  flags_length.flags_[0] = flags;
610  frame.WriteBytesToOffset(4, &flags_length, sizeof(flags_length));
611
612  scoped_ptr<SpdySynReplyControlFrame> reply_frame(
613      reinterpret_cast<SpdySynReplyControlFrame*>(frame.take()));
614  if (compressed) {
615    return reinterpret_cast<SpdySynReplyControlFrame*>(
616        CompressControlFrame(*reply_frame.get()));
617  }
618  return reply_frame.release();
619}
620
621/* static */
622SpdyRstStreamControlFrame* SpdyFramer::CreateRstStream(SpdyStreamId stream_id,
623                                                       SpdyStatusCodes status) {
624  DCHECK_GT(stream_id, 0u);
625  DCHECK_EQ(0u, stream_id & ~kStreamIdMask);
626  DCHECK_NE(status, INVALID);
627  DCHECK_LT(status, NUM_STATUS_CODES);
628
629  SpdyFrameBuilder frame;
630  frame.WriteUInt16(kControlFlagMask | spdy_version_);
631  frame.WriteUInt16(RST_STREAM);
632  frame.WriteUInt32(8);
633  frame.WriteUInt32(stream_id);
634  frame.WriteUInt32(status);
635  return reinterpret_cast<SpdyRstStreamControlFrame*>(frame.take());
636}
637
638/* static */
639SpdySettingsControlFrame* SpdyFramer::CreateSettings(
640    const SpdySettings& values) {
641  SpdyFrameBuilder frame;
642  frame.WriteUInt16(kControlFlagMask | spdy_version_);
643  frame.WriteUInt16(SETTINGS);
644  size_t settings_size = SpdySettingsControlFrame::size() - SpdyFrame::size() +
645      8 * values.size();
646  frame.WriteUInt32(settings_size);
647  frame.WriteUInt32(values.size());
648  SpdySettings::const_iterator it = values.begin();
649  while (it != values.end()) {
650    frame.WriteUInt32(it->first.id_);
651    frame.WriteUInt32(it->second);
652    ++it;
653  }
654  return reinterpret_cast<SpdySettingsControlFrame*>(frame.take());
655}
656
657/* static */
658SpdyNoOpControlFrame* SpdyFramer::CreateNopFrame() {
659  SpdyFrameBuilder frame;
660  frame.WriteUInt16(kControlFlagMask | spdy_version_);
661  frame.WriteUInt16(NOOP);
662  frame.WriteUInt32(0);
663  return reinterpret_cast<SpdyNoOpControlFrame*>(frame.take());
664}
665
666/* static */
667SpdyPingControlFrame* SpdyFramer::CreatePingFrame(uint32 unique_id) {
668  SpdyFrameBuilder frame;
669  frame.WriteUInt16(kControlFlagMask | kSpdyProtocolVersion);
670  frame.WriteUInt16(PING);
671  size_t ping_size = SpdyPingControlFrame::size() - SpdyFrame::size();
672  frame.WriteUInt32(ping_size);
673  frame.WriteUInt32(unique_id);
674  return reinterpret_cast<SpdyPingControlFrame*>(frame.take());
675}
676
677/* static */
678SpdyGoAwayControlFrame* SpdyFramer::CreateGoAway(
679    SpdyStreamId last_accepted_stream_id) {
680  DCHECK_EQ(0u, last_accepted_stream_id & ~kStreamIdMask);
681
682  SpdyFrameBuilder frame;
683  frame.WriteUInt16(kControlFlagMask | spdy_version_);
684  frame.WriteUInt16(GOAWAY);
685  size_t go_away_size = SpdyGoAwayControlFrame::size() - SpdyFrame::size();
686  frame.WriteUInt32(go_away_size);
687  frame.WriteUInt32(last_accepted_stream_id);
688  return reinterpret_cast<SpdyGoAwayControlFrame*>(frame.take());
689}
690
691SpdyHeadersControlFrame* SpdyFramer::CreateHeaders(SpdyStreamId stream_id,
692    SpdyControlFlags flags, bool compressed, const SpdyHeaderBlock* headers) {
693  // Basically the same as CreateSynReply().
694  DCHECK_GT(stream_id, 0u);
695  DCHECK_EQ(0u, stream_id & ~kStreamIdMask);
696
697  SpdyFrameBuilder frame;
698  frame.WriteUInt16(kControlFlagMask | kSpdyProtocolVersion);
699  frame.WriteUInt16(HEADERS);
700  frame.WriteUInt32(0);  // Placeholder for the length and flags.
701  frame.WriteUInt32(stream_id);
702  frame.WriteUInt16(0);  // Unused
703
704  frame.WriteUInt16(headers->size());  // Number of headers.
705  SpdyHeaderBlock::const_iterator it;
706  for (it = headers->begin(); it != headers->end(); ++it) {
707    bool wrote_header;
708    wrote_header = frame.WriteString(it->first);
709    wrote_header &= frame.WriteString(it->second);
710    DCHECK(wrote_header);
711  }
712
713  // Write the length and flags.
714  size_t length = frame.length() - SpdyFrame::size();
715  DCHECK_EQ(0u, length & ~static_cast<size_t>(kLengthMask));
716  FlagsAndLength flags_length;
717  flags_length.length_ = htonl(static_cast<uint32>(length));
718  DCHECK_EQ(0, flags & ~kControlFlagsMask);
719  flags_length.flags_[0] = flags;
720  frame.WriteBytesToOffset(4, &flags_length, sizeof(flags_length));
721
722  scoped_ptr<SpdyHeadersControlFrame> headers_frame(
723      reinterpret_cast<SpdyHeadersControlFrame*>(frame.take()));
724  if (compressed) {
725    return reinterpret_cast<SpdyHeadersControlFrame*>(
726        CompressControlFrame(*headers_frame.get()));
727  }
728  return headers_frame.release();
729}
730
731/* static */
732SpdyWindowUpdateControlFrame* SpdyFramer::CreateWindowUpdate(
733    SpdyStreamId stream_id,
734    uint32 delta_window_size) {
735  DCHECK_GT(stream_id, 0u);
736  DCHECK_EQ(0u, stream_id & ~kStreamIdMask);
737  DCHECK_GT(delta_window_size, 0u);
738  DCHECK_LE(delta_window_size, spdy::kSpdyStreamMaximumWindowSize);
739
740  SpdyFrameBuilder frame;
741  frame.WriteUInt16(kControlFlagMask | spdy_version_);
742  frame.WriteUInt16(WINDOW_UPDATE);
743  size_t window_update_size = SpdyWindowUpdateControlFrame::size() -
744      SpdyFrame::size();
745  frame.WriteUInt32(window_update_size);
746  frame.WriteUInt32(stream_id);
747  frame.WriteUInt32(delta_window_size);
748  return reinterpret_cast<SpdyWindowUpdateControlFrame*>(frame.take());
749}
750
751/* static */
752bool SpdyFramer::ParseSettings(const SpdySettingsControlFrame* frame,
753                               SpdySettings* settings) {
754  DCHECK_EQ(frame->type(), SETTINGS);
755  DCHECK(settings);
756
757  SpdyFrameBuilder parser(frame->header_block(), frame->header_block_len());
758  void* iter = NULL;
759  for (size_t index = 0; index < frame->num_entries(); ++index) {
760    uint32 id;
761    uint32 value;
762    if (!parser.ReadUInt32(&iter, &id))
763      return false;
764    if (!parser.ReadUInt32(&iter, &value))
765      return false;
766    settings->insert(settings->end(), std::make_pair(id, value));
767  }
768  return true;
769}
770
771SpdyDataFrame* SpdyFramer::CreateDataFrame(SpdyStreamId stream_id,
772                                           const char* data,
773                                           uint32 len, SpdyDataFlags flags) {
774  SpdyFrameBuilder frame;
775
776  DCHECK_GT(stream_id, 0u);
777  DCHECK_EQ(0u, stream_id & ~kStreamIdMask);
778  frame.WriteUInt32(stream_id);
779
780  DCHECK_EQ(0u, len & ~static_cast<size_t>(kLengthMask));
781  FlagsAndLength flags_length;
782  flags_length.length_ = htonl(len);
783  DCHECK_EQ(0, flags & ~kDataFlagsMask);
784  flags_length.flags_[0] = flags;
785  frame.WriteBytes(&flags_length, sizeof(flags_length));
786
787  frame.WriteBytes(data, len);
788  scoped_ptr<SpdyFrame> data_frame(frame.take());
789  SpdyDataFrame* rv;
790  if (flags & DATA_FLAG_COMPRESSED) {
791    rv = reinterpret_cast<SpdyDataFrame*>(CompressFrame(*data_frame.get()));
792  } else {
793    rv = reinterpret_cast<SpdyDataFrame*>(data_frame.release());
794  }
795
796  if (flags & DATA_FLAG_FIN) {
797    CleanupCompressorForStream(stream_id);
798  }
799
800  return rv;
801}
802
803SpdyFrame* SpdyFramer::CompressFrame(const SpdyFrame& frame) {
804  if (frame.is_control_frame()) {
805    return CompressControlFrame(
806        reinterpret_cast<const SpdyControlFrame&>(frame));
807  }
808  return CompressDataFrame(reinterpret_cast<const SpdyDataFrame&>(frame));
809}
810
811SpdyFrame* SpdyFramer::DecompressFrame(const SpdyFrame& frame) {
812  if (frame.is_control_frame()) {
813    return DecompressControlFrame(
814        reinterpret_cast<const SpdyControlFrame&>(frame));
815  }
816  return DecompressDataFrame(reinterpret_cast<const SpdyDataFrame&>(frame));
817}
818
819SpdyFrame* SpdyFramer::DuplicateFrame(const SpdyFrame& frame) {
820  int size = SpdyFrame::size() + frame.length();
821  SpdyFrame* new_frame = new SpdyFrame(size);
822  memcpy(new_frame->data(), frame.data(), size);
823  return new_frame;
824}
825
826bool SpdyFramer::IsCompressible(const SpdyFrame& frame) const {
827  // The important frames to compress are those which contain large
828  // amounts of compressible data - namely the headers in the SYN_STREAM
829  // and SYN_REPLY.
830  // TODO(mbelshe): Reconcile this with the spec when the spec is
831  // explicit about which frames compress and which do not.
832  if (frame.is_control_frame()) {
833    const SpdyControlFrame& control_frame =
834        reinterpret_cast<const SpdyControlFrame&>(frame);
835    return control_frame.type() == SYN_STREAM ||
836           control_frame.type() == SYN_REPLY;
837  }
838
839  const SpdyDataFrame& data_frame =
840      reinterpret_cast<const SpdyDataFrame&>(frame);
841  return (data_frame.flags() & DATA_FLAG_COMPRESSED) != 0;
842}
843
844const char* SpdyFramer::StateToString(int state) {
845  switch (state) {
846    case SPDY_ERROR:
847      return "ERROR";
848    case SPDY_DONE:
849      return "DONE";
850    case SPDY_AUTO_RESET:
851      return "AUTO_RESET";
852    case SPDY_RESET:
853      return "RESET";
854    case SPDY_READING_COMMON_HEADER:
855      return "READING_COMMON_HEADER";
856    case SPDY_INTERPRET_CONTROL_FRAME_COMMON_HEADER:
857      return "INTERPRET_CONTROL_FRAME_COMMON_HEADER";
858    case SPDY_CONTROL_FRAME_PAYLOAD:
859      return "CONTROL_FRAME_PAYLOAD";
860    case SPDY_IGNORE_REMAINING_PAYLOAD:
861      return "IGNORE_REMAINING_PAYLOAD";
862    case SPDY_FORWARD_STREAM_FRAME:
863      return "FORWARD_STREAM_FRAME";
864    case SPDY_CONTROL_FRAME_BEFORE_HEADER_BLOCK:
865      return "SPDY_CONTROL_FRAME_BEFORE_HEADER_BLOCK";
866    case SPDY_CONTROL_FRAME_HEADER_BLOCK:
867      return "SPDY_CONTROL_FRAME_HEADER_BLOCK";
868  }
869  return "UNKNOWN_STATE";
870}
871
872const char* SpdyFramer::ErrorCodeToString(int error_code) {
873  switch (error_code) {
874    case SPDY_NO_ERROR:
875      return "NO_ERROR";
876    case SPDY_INVALID_CONTROL_FRAME:
877      return "INVALID_CONTROL_FRAME";
878    case SPDY_CONTROL_PAYLOAD_TOO_LARGE:
879      return "CONTROL_PAYLOAD_TOO_LARGE";
880    case SPDY_ZLIB_INIT_FAILURE:
881      return "ZLIB_INIT_FAILURE";
882    case SPDY_UNSUPPORTED_VERSION:
883      return "UNSUPPORTED_VERSION";
884    case SPDY_DECOMPRESS_FAILURE:
885      return "DECOMPRESS_FAILURE";
886    case SPDY_COMPRESS_FAILURE:
887      return "COMPRESS_FAILURE";
888  }
889  return "UNKNOWN_ERROR";
890}
891
892void SpdyFramer::set_enable_compression(bool value) {
893  enable_compression_ = value;
894}
895
896void SpdyFramer::set_enable_compression_default(bool value) {
897  compression_default_ = value;
898}
899
900size_t SpdyFramer::ProcessCommonHeader(const char* data, size_t len) {
901  // This should only be called when we're in the SPDY_READING_COMMON_HEADER
902  // state.
903  DCHECK_EQ(state_, SPDY_READING_COMMON_HEADER);
904
905  size_t original_len = len;
906  SpdyFrame current_frame(current_frame_buffer_, false);
907
908  do {
909    if (current_frame_len_ < SpdyFrame::size()) {
910      size_t bytes_desired = SpdyFrame::size() - current_frame_len_;
911      UpdateCurrentFrameBuffer(&data, &len, bytes_desired);
912      // Check for an empty data frame.
913      if (current_frame_len_ == SpdyFrame::size() &&
914          !current_frame.is_control_frame() &&
915          current_frame.length() == 0) {
916        if (current_frame.flags() & CONTROL_FLAG_FIN) {
917          SpdyDataFrame data_frame(current_frame_buffer_, false);
918          visitor_->OnStreamFrameData(data_frame.stream_id(), NULL, 0);
919        }
920        CHANGE_STATE(SPDY_AUTO_RESET);
921      }
922      break;
923    }
924    remaining_data_ = current_frame.length();
925
926    // This is just a sanity check for help debugging early frame errors.
927    if (remaining_data_ > 1000000u) {
928      LOG(WARNING) <<
929          "Unexpectedly large frame.  Spdy session is likely corrupt.";
930    }
931
932    // if we're here, then we have the common header all received.
933    if (!current_frame.is_control_frame())
934      CHANGE_STATE(SPDY_FORWARD_STREAM_FRAME);
935    else
936      CHANGE_STATE(SPDY_INTERPRET_CONTROL_FRAME_COMMON_HEADER);
937  } while (false);
938
939  return original_len - len;
940}
941
942void SpdyFramer::ProcessControlFrameHeader() {
943  DCHECK_EQ(SPDY_NO_ERROR, error_code_);
944  DCHECK_LE(SpdyFrame::size(), current_frame_len_);
945  SpdyControlFrame current_control_frame(current_frame_buffer_, false);
946
947  // We check version before we check validity: version can never be 'invalid',
948  // it can only be unsupported.
949  if (current_control_frame.version() != spdy_version_) {
950    set_error(SPDY_UNSUPPORTED_VERSION);
951    return;
952  }
953
954  // Next up, check to see if we have valid data.  This should be after version
955  // checking (otherwise if the the type were out of bounds due to a version
956  // upgrade we would misclassify the error) and before checking the type
957  // (type can definitely be out of bounds)
958  if (!current_control_frame.AppearsToBeAValidControlFrame()) {
959    set_error(SPDY_INVALID_CONTROL_FRAME);
960    return;
961  }
962
963  // Do some sanity checking on the control frame sizes.
964  switch (current_control_frame.type()) {
965    case SYN_STREAM:
966      if (current_control_frame.length() <
967          SpdySynStreamControlFrame::size() - SpdyControlFrame::size())
968        set_error(SPDY_INVALID_CONTROL_FRAME);
969      break;
970    case SYN_REPLY:
971      if (current_control_frame.length() <
972          SpdySynReplyControlFrame::size() - SpdyControlFrame::size())
973        set_error(SPDY_INVALID_CONTROL_FRAME);
974      break;
975    case RST_STREAM:
976      if (current_control_frame.length() !=
977          SpdyRstStreamControlFrame::size() - SpdyFrame::size())
978        set_error(SPDY_INVALID_CONTROL_FRAME);
979      break;
980    case SETTINGS:
981      if (current_control_frame.length() <
982          SpdySettingsControlFrame::size() - SpdyControlFrame::size())
983        set_error(SPDY_INVALID_CONTROL_FRAME);
984      break;
985    // TODO(hkhalil): Remove NOOP.
986    case NOOP:
987      // NOOP.  Swallow it.
988      DLOG(INFO) << "Attempted frame size validation for NOOP. Resetting.";
989      CHANGE_STATE(SPDY_AUTO_RESET);
990      return;
991    case GOAWAY:
992      if (current_control_frame.length() !=
993          SpdyGoAwayControlFrame::size() - SpdyFrame::size())
994        set_error(SPDY_INVALID_CONTROL_FRAME);
995      break;
996    case HEADERS:
997      if (current_control_frame.length() <
998          SpdyHeadersControlFrame::size() - SpdyControlFrame::size())
999        set_error(SPDY_INVALID_CONTROL_FRAME);
1000      break;
1001    case WINDOW_UPDATE:
1002      if (current_control_frame.length() !=
1003          SpdyWindowUpdateControlFrame::size() - SpdyControlFrame::size())
1004        set_error(SPDY_INVALID_CONTROL_FRAME);
1005      break;
1006    case PING:
1007      if (current_control_frame.length() !=
1008          SpdyPingControlFrame::size() - SpdyControlFrame::size())
1009        set_error(SPDY_INVALID_CONTROL_FRAME);
1010      break;
1011    default:
1012      LOG(WARNING) << "Valid spdy control frame with unhandled type: "
1013                   << current_control_frame.type();
1014      DCHECK(false);
1015      set_error(SPDY_INVALID_CONTROL_FRAME);
1016      break;
1017  }
1018
1019  remaining_control_payload_ = current_control_frame.length();
1020  if (remaining_control_payload_ > kControlFrameBufferMaxSize) {
1021    set_error(SPDY_CONTROL_PAYLOAD_TOO_LARGE);
1022    return;
1023  }
1024
1025  ExpandControlFrameBuffer(remaining_control_payload_);
1026  CHANGE_STATE(SPDY_CONTROL_FRAME_PAYLOAD);
1027}
1028
1029size_t SpdyFramer::ProcessControlFramePayload(const char* data, size_t len) {
1030  size_t original_len = len;
1031  do {
1032    if (remaining_control_payload_) {
1033      size_t bytes_read = UpdateCurrentFrameBuffer(&data, &len,
1034                                                   remaining_control_payload_);
1035      remaining_control_payload_ -= bytes_read;
1036      remaining_data_ -= bytes_read;
1037      if (remaining_control_payload_)
1038        break;
1039    }
1040    SpdyControlFrame control_frame(current_frame_buffer_, false);
1041    visitor_->OnControl(&control_frame);
1042
1043    // If this is a FIN, tell the caller.
1044    if (control_frame.type() == SYN_REPLY &&
1045        control_frame.flags() & CONTROL_FLAG_FIN) {
1046      visitor_->OnStreamFrameData(reinterpret_cast<SpdySynReplyControlFrame*>(
1047                                      &control_frame)->stream_id(),
1048                                  NULL, 0);
1049    }
1050
1051    CHANGE_STATE(SPDY_IGNORE_REMAINING_PAYLOAD);
1052  } while (false);
1053  return original_len - len;
1054}
1055
1056size_t SpdyFramer::ProcessDataFramePayload(const char* data, size_t len) {
1057  size_t original_len = len;
1058
1059  SpdyDataFrame current_data_frame(current_frame_buffer_, false);
1060  if (remaining_data_) {
1061    size_t amount_to_forward = std::min(remaining_data_, len);
1062    if (amount_to_forward && state_ != SPDY_IGNORE_REMAINING_PAYLOAD) {
1063      if (current_data_frame.flags() & DATA_FLAG_COMPRESSED) {
1064        z_stream* decompressor =
1065            GetStreamDecompressor(current_data_frame.stream_id());
1066        if (!decompressor)
1067          return 0;
1068
1069        size_t decompressed_max_size = amount_to_forward * 100;
1070        scoped_array<char> decompressed(new char[decompressed_max_size]);
1071        decompressor->next_in = reinterpret_cast<Bytef*>(
1072            const_cast<char*>(data));
1073        decompressor->avail_in = amount_to_forward;
1074        decompressor->next_out =
1075            reinterpret_cast<Bytef*>(decompressed.get());
1076        decompressor->avail_out = decompressed_max_size;
1077
1078        int rv = inflate(decompressor, Z_SYNC_FLUSH);
1079        if (rv != Z_OK) {
1080          LOG(WARNING) << "inflate failure: " << rv;
1081          set_error(SPDY_DECOMPRESS_FAILURE);
1082          return 0;
1083        }
1084        size_t decompressed_size = decompressed_max_size -
1085                                   decompressor->avail_out;
1086
1087        // Only inform the visitor if there is data.
1088        if (decompressed_size)
1089          visitor_->OnStreamFrameData(current_data_frame.stream_id(),
1090                                      decompressed.get(),
1091                                      decompressed_size);
1092        amount_to_forward -= decompressor->avail_in;
1093      } else {
1094        // The data frame was not compressed.
1095        // Only inform the visitor if there is data.
1096        if (amount_to_forward)
1097          visitor_->OnStreamFrameData(current_data_frame.stream_id(),
1098                                      data, amount_to_forward);
1099      }
1100    }
1101    data += amount_to_forward;
1102    len -= amount_to_forward;
1103    remaining_data_ -= amount_to_forward;
1104
1105    // If the FIN flag is set, and there is no more data in this data
1106    // frame, inform the visitor of EOF via a 0-length data frame.
1107    if (!remaining_data_ &&
1108        current_data_frame.flags() & DATA_FLAG_FIN) {
1109      visitor_->OnStreamFrameData(current_data_frame.stream_id(), NULL, 0);
1110      CleanupDecompressorForStream(current_data_frame.stream_id());
1111    }
1112  } else {
1113    CHANGE_STATE(SPDY_AUTO_RESET);
1114  }
1115  return original_len - len;
1116}
1117
1118z_stream* SpdyFramer::GetHeaderCompressor() {
1119  if (header_compressor_.get())
1120    return header_compressor_.get();  // Already initialized.
1121
1122  header_compressor_.reset(new z_stream);
1123  memset(header_compressor_.get(), 0, sizeof(z_stream));
1124
1125  int success = deflateInit2(header_compressor_.get(),
1126                             kCompressorLevel,
1127                             Z_DEFLATED,
1128                             kCompressorWindowSizeInBits,
1129                             kCompressorMemLevel,
1130                             Z_DEFAULT_STRATEGY);
1131  if (success == Z_OK)
1132    success = deflateSetDictionary(header_compressor_.get(),
1133                                   reinterpret_cast<const Bytef*>(kDictionary),
1134                                   kDictionarySize);
1135  if (success != Z_OK) {
1136    LOG(WARNING) << "deflateSetDictionary failure: " << success;
1137    header_compressor_.reset(NULL);
1138    return NULL;
1139  }
1140  return header_compressor_.get();
1141}
1142
1143z_stream* SpdyFramer::GetHeaderDecompressor() {
1144  if (header_decompressor_.get())
1145    return header_decompressor_.get();  // Already initialized.
1146
1147  header_decompressor_.reset(new z_stream);
1148  memset(header_decompressor_.get(), 0, sizeof(z_stream));
1149
1150  // Compute the id of our dictionary so that we know we're using the
1151  // right one when asked for it.
1152  if (dictionary_id == 0) {
1153    dictionary_id = adler32(0L, Z_NULL, 0);
1154    dictionary_id = adler32(dictionary_id,
1155                            reinterpret_cast<const Bytef*>(kDictionary),
1156                            kDictionarySize);
1157  }
1158
1159  int success = inflateInit(header_decompressor_.get());
1160  if (success != Z_OK) {
1161    LOG(WARNING) << "inflateInit failure: " << success;
1162    header_decompressor_.reset(NULL);
1163    return NULL;
1164  }
1165  return header_decompressor_.get();
1166}
1167
1168z_stream* SpdyFramer::GetStreamCompressor(SpdyStreamId stream_id) {
1169  CompressorMap::iterator it = stream_compressors_.find(stream_id);
1170  if (it != stream_compressors_.end())
1171    return it->second;  // Already initialized.
1172
1173  scoped_ptr<z_stream> compressor(new z_stream);
1174  memset(compressor.get(), 0, sizeof(z_stream));
1175
1176  int success = deflateInit2(compressor.get(),
1177                             kCompressorLevel,
1178                             Z_DEFLATED,
1179                             kCompressorWindowSizeInBits,
1180                             kCompressorMemLevel,
1181                             Z_DEFAULT_STRATEGY);
1182  if (success != Z_OK) {
1183    LOG(WARNING) << "deflateInit failure: " << success;
1184    return NULL;
1185  }
1186  return stream_compressors_[stream_id] = compressor.release();
1187}
1188
1189z_stream* SpdyFramer::GetStreamDecompressor(SpdyStreamId stream_id) {
1190  CompressorMap::iterator it = stream_decompressors_.find(stream_id);
1191  if (it != stream_decompressors_.end())
1192    return it->second;  // Already initialized.
1193
1194  scoped_ptr<z_stream> decompressor(new z_stream);
1195  memset(decompressor.get(), 0, sizeof(z_stream));
1196
1197  int success = inflateInit(decompressor.get());
1198  if (success != Z_OK) {
1199    LOG(WARNING) << "inflateInit failure: " << success;
1200    return NULL;
1201  }
1202  return stream_decompressors_[stream_id] = decompressor.release();
1203}
1204
1205SpdyControlFrame* SpdyFramer::CompressControlFrame(
1206    const SpdyControlFrame& frame) {
1207  z_stream* compressor = GetHeaderCompressor();
1208  if (!compressor)
1209    return NULL;
1210  return reinterpret_cast<SpdyControlFrame*>(
1211      CompressFrameWithZStream(frame, compressor));
1212}
1213
1214SpdyDataFrame* SpdyFramer::CompressDataFrame(const SpdyDataFrame& frame) {
1215  z_stream* compressor = GetStreamCompressor(frame.stream_id());
1216  if (!compressor)
1217    return NULL;
1218  return reinterpret_cast<SpdyDataFrame*>(
1219      CompressFrameWithZStream(frame, compressor));
1220}
1221
1222SpdyControlFrame* SpdyFramer::DecompressControlFrame(
1223    const SpdyControlFrame& frame) {
1224  z_stream* decompressor = GetHeaderDecompressor();
1225  if (!decompressor)
1226    return NULL;
1227  return reinterpret_cast<SpdyControlFrame*>(
1228      DecompressFrameWithZStream(frame, decompressor));
1229}
1230
1231// Incrementally decompress the control frame's header block, feeding the
1232// result to the visitor in chunks. Continue this until the visitor
1233// indicates that it cannot process any more data, or (more commonly) we
1234// run out of data to deliver.
1235bool SpdyFramer::IncrementallyDecompressControlFrameHeaderData(
1236    const SpdyControlFrame* control_frame) {
1237  z_stream* decomp = GetHeaderDecompressor();
1238  int payload_length;
1239  int header_length;
1240  const char* payload;
1241  bool read_successfully = true;
1242  bool more = true;
1243  char buffer[kHeaderDataChunkMaxSize];
1244
1245  if (!GetFrameBoundaries(
1246      *control_frame, &payload_length, &header_length, &payload)) {
1247    DLOG(ERROR) << "Control frame of type "
1248                << SpdyFramer::ControlTypeToString(control_frame->type())
1249                <<" doesn't have headers";
1250    return false;
1251  }
1252  decomp->next_in = reinterpret_cast<Bytef*>(const_cast<char*>(payload));
1253  decomp->avail_in = payload_length;
1254  const SpdyStreamId stream_id = GetControlFrameStreamId(control_frame);
1255  DCHECK_LT(0u, stream_id);
1256  while (more && read_successfully) {
1257    decomp->next_out = reinterpret_cast<Bytef*>(buffer);
1258    decomp->avail_out = arraysize(buffer);
1259    int rv = DecompressHeaderBlockInZStream(decomp);
1260    if (rv != Z_OK) {
1261      set_error(SPDY_DECOMPRESS_FAILURE);
1262      DLOG(WARNING) << "inflate failure: " << rv;
1263      more = read_successfully = false;
1264    } else {
1265      DCHECK_GT(arraysize(buffer), decomp->avail_out);
1266      size_t len = arraysize(buffer) - decomp->avail_out;
1267      read_successfully = visitor_->OnControlFrameHeaderData(stream_id, buffer,
1268                                                             len);
1269      if (!read_successfully) {
1270        // Assume that the problem was the header block was too large for the
1271        // visitor.
1272        set_error(SPDY_CONTROL_PAYLOAD_TOO_LARGE);
1273      }
1274      more = decomp->avail_in > 0;
1275    }
1276  }
1277  return read_successfully;
1278}
1279
1280// Incrementally decompress the control frame's header block, feeding the
1281// result to the visitor in chunks. Continue this until the visitor
1282// indicates that it cannot process any more data, or (more commonly) we
1283// run out of data to deliver.
1284bool SpdyFramer::IncrementallyDecompressControlFrameHeaderData(
1285    const SpdyControlFrame* control_frame,
1286    const char* data,
1287    size_t len) {
1288  // Get a decompressor or set error.
1289  z_stream* decomp = GetHeaderDecompressor();
1290  if (decomp == NULL) {
1291    LOG(DFATAL) << "Couldn't get decompressor for handling compressed headers.";
1292    set_error(SPDY_DECOMPRESS_FAILURE);
1293    return false;
1294  }
1295
1296  bool processed_successfully = true;
1297  char buffer[kHeaderDataChunkMaxSize];
1298
1299  decomp->next_in = reinterpret_cast<Bytef*>(const_cast<char*>(data));
1300  decomp->avail_in = len;
1301  const SpdyStreamId stream_id = GetControlFrameStreamId(control_frame);
1302  DCHECK_LT(0u, stream_id);
1303  while (decomp->avail_in > 0 && processed_successfully) {
1304    decomp->next_out = reinterpret_cast<Bytef*>(buffer);
1305    decomp->avail_out = arraysize(buffer);
1306    int rv = DecompressHeaderBlockInZStream(decomp);
1307    if (rv != Z_OK) {
1308      set_error(SPDY_DECOMPRESS_FAILURE);
1309      DLOG(WARNING) << "inflate failure: " << rv;
1310      processed_successfully = false;
1311    } else {
1312      size_t decompressed_len = arraysize(buffer) - decomp->avail_out;
1313      if (decompressed_len > 0) {
1314        processed_successfully = visitor_->OnControlFrameHeaderData(
1315            stream_id, buffer, decompressed_len);
1316      }
1317      if (!processed_successfully) {
1318        // Assume that the problem was the header block was too large for the
1319        // visitor.
1320        set_error(SPDY_CONTROL_PAYLOAD_TOO_LARGE);
1321      }
1322    }
1323  }
1324  return processed_successfully;
1325}
1326
1327bool SpdyFramer::IncrementallyDeliverControlFrameHeaderData(
1328    const SpdyControlFrame* control_frame, const char* data, size_t len) {
1329  bool read_successfully = true;
1330  const SpdyStreamId stream_id = GetControlFrameStreamId(control_frame);
1331  DCHECK_LT(0u, stream_id);
1332  while (read_successfully && len > 0) {
1333    size_t bytes_to_deliver = std::min(len, kHeaderDataChunkMaxSize);
1334    read_successfully = visitor_->OnControlFrameHeaderData(stream_id, data,
1335                                                           bytes_to_deliver);
1336    data += bytes_to_deliver;
1337    len -= bytes_to_deliver;
1338    if (!read_successfully) {
1339      // Assume that the problem was the header block was too large for the
1340      // visitor.
1341      set_error(SPDY_CONTROL_PAYLOAD_TOO_LARGE);
1342    }
1343  }
1344  return read_successfully;
1345}
1346
1347size_t SpdyFramer::GetMinimumControlFrameSize(SpdyControlType type) {
1348  switch (type) {
1349    case SYN_STREAM:
1350      return SpdySynStreamControlFrame::size();
1351    case SYN_REPLY:
1352      return SpdySynReplyControlFrame::size();
1353    case RST_STREAM:
1354      return SpdyRstStreamControlFrame::size();
1355    case SETTINGS:
1356      return SpdySettingsControlFrame::size();
1357    case NOOP:
1358      return SpdyNoOpControlFrame::size();
1359    case PING:
1360      return SpdyPingControlFrame::size();
1361    case GOAWAY:
1362      return SpdyGoAwayControlFrame::size();
1363    case HEADERS:
1364      return SpdyHeadersControlFrame::size();
1365    case WINDOW_UPDATE:
1366      return SpdyWindowUpdateControlFrame::size();
1367    case NUM_CONTROL_FRAME_TYPES:
1368      break;
1369  }
1370  LOG(ERROR) << "Unknown SPDY control frame type " << type;
1371  return 0x7FFFFFFF;  // Max signed 32bit int
1372}
1373
1374/* static */
1375SpdyStreamId SpdyFramer::GetControlFrameStreamId(
1376    const SpdyControlFrame* control_frame) {
1377  SpdyStreamId stream_id = kInvalidStream;
1378  if (control_frame != NULL) {
1379    switch (control_frame->type()) {
1380      case SYN_STREAM:
1381        stream_id = reinterpret_cast<const SpdySynStreamControlFrame*>(
1382            control_frame)->stream_id();
1383        break;
1384      case SYN_REPLY:
1385        stream_id = reinterpret_cast<const SpdySynReplyControlFrame*>(
1386            control_frame)->stream_id();
1387        break;
1388      case HEADERS:
1389        stream_id = reinterpret_cast<const SpdyHeadersControlFrame*>(
1390            control_frame)->stream_id();
1391        break;
1392      case RST_STREAM:
1393        stream_id = reinterpret_cast<const SpdyRstStreamControlFrame*>(
1394            control_frame)->stream_id();
1395        break;
1396      case WINDOW_UPDATE:
1397        stream_id = reinterpret_cast<const SpdyWindowUpdateControlFrame*>(
1398            control_frame)->stream_id();
1399        break;
1400      // All of the following types are not part of a particular stream.
1401      // They all fall through to the invalid control frame type case.
1402      // (The default case isn't used so that the compile will break if a new
1403      // control frame type is added but not included here.)
1404      case SETTINGS:
1405      case NOOP:
1406      case PING:
1407      case GOAWAY:
1408      case NUM_CONTROL_FRAME_TYPES:  // makes compiler happy
1409        break;
1410    }
1411  }
1412  return stream_id;
1413}
1414
1415void SpdyFramer::set_validate_control_frame_sizes(bool value) {
1416  validate_control_frame_sizes_ = value;
1417}
1418
1419SpdyDataFrame* SpdyFramer::DecompressDataFrame(const SpdyDataFrame& frame) {
1420  z_stream* decompressor = GetStreamDecompressor(frame.stream_id());
1421  if (!decompressor)
1422    return NULL;
1423  return reinterpret_cast<SpdyDataFrame*>(
1424      DecompressFrameWithZStream(frame, decompressor));
1425}
1426
1427SpdyFrame* SpdyFramer::CompressFrameWithZStream(const SpdyFrame& frame,
1428                                                z_stream* compressor) {
1429  int payload_length;
1430  int header_length;
1431  const char* payload;
1432
1433  base::StatsCounter compressed_frames("spdy.CompressedFrames");
1434  base::StatsCounter pre_compress_bytes("spdy.PreCompressSize");
1435  base::StatsCounter post_compress_bytes("spdy.PostCompressSize");
1436
1437  if (!enable_compression_)
1438    return DuplicateFrame(frame);
1439
1440  if (!GetFrameBoundaries(frame, &payload_length, &header_length, &payload))
1441    return NULL;
1442
1443  // Create an output frame.
1444  int compressed_max_size = deflateBound(compressor, payload_length);
1445  int new_frame_size = header_length + compressed_max_size;
1446  scoped_ptr<SpdyFrame> new_frame(new SpdyFrame(new_frame_size));
1447  memcpy(new_frame->data(), frame.data(), frame.length() + SpdyFrame::size());
1448
1449  compressor->next_in = reinterpret_cast<Bytef*>(const_cast<char*>(payload));
1450  compressor->avail_in = payload_length;
1451  compressor->next_out = reinterpret_cast<Bytef*>(new_frame->data()) +
1452                          header_length;
1453  compressor->avail_out = compressed_max_size;
1454
1455  // Data packets have a 'compressed' flag.
1456  if (!new_frame->is_control_frame()) {
1457    SpdyDataFrame* data_frame =
1458        reinterpret_cast<SpdyDataFrame*>(new_frame.get());
1459    data_frame->set_flags(data_frame->flags() | DATA_FLAG_COMPRESSED);
1460  }
1461
1462#ifndef ANDROID
1463  // Make sure that all the data we pass to zlib is defined.
1464  // This way, all Valgrind reports on the compressed data are zlib's fault.
1465  (void)VALGRIND_CHECK_MEM_IS_DEFINED(compressor->next_in,
1466                                      compressor->avail_in);
1467#endif
1468
1469  int rv = deflate(compressor, Z_SYNC_FLUSH);
1470  if (rv != Z_OK) {  // How can we know that it compressed everything?
1471    // This shouldn't happen, right?
1472    LOG(WARNING) << "deflate failure: " << rv;
1473    return NULL;
1474  }
1475
1476  int compressed_size = compressed_max_size - compressor->avail_out;
1477
1478#ifndef ANDROID
1479  // We trust zlib. Also, we can't do anything about it.
1480  // See http://www.zlib.net/zlib_faq.html#faq36
1481  (void)VALGRIND_MAKE_MEM_DEFINED(new_frame->data() + header_length,
1482                                  compressed_size);
1483#endif
1484
1485  new_frame->set_length(header_length + compressed_size - SpdyFrame::size());
1486
1487  pre_compress_bytes.Add(payload_length);
1488  post_compress_bytes.Add(new_frame->length());
1489
1490  compressed_frames.Increment();
1491
1492  return new_frame.release();
1493}
1494
1495SpdyFrame* SpdyFramer::DecompressFrameWithZStream(const SpdyFrame& frame,
1496                                                  z_stream* decompressor) {
1497  int payload_length;
1498  int header_length;
1499  const char* payload;
1500
1501  base::StatsCounter decompressed_frames("spdy.DecompressedFrames");
1502  base::StatsCounter pre_decompress_bytes("spdy.PreDeCompressSize");
1503  base::StatsCounter post_decompress_bytes("spdy.PostDeCompressSize");
1504
1505  if (!enable_compression_)
1506    return DuplicateFrame(frame);
1507
1508  if (!GetFrameBoundaries(frame, &payload_length, &header_length, &payload))
1509    return NULL;
1510
1511  if (!frame.is_control_frame()) {
1512    const SpdyDataFrame& data_frame =
1513        reinterpret_cast<const SpdyDataFrame&>(frame);
1514    if ((data_frame.flags() & DATA_FLAG_COMPRESSED) == 0)
1515      return DuplicateFrame(frame);
1516  }
1517
1518  // Create an output frame.  Assume it does not need to be longer than
1519  // the input data.
1520  size_t decompressed_max_size = kControlFrameBufferInitialSize;
1521  int new_frame_size = header_length + decompressed_max_size;
1522  if (frame.length() > decompressed_max_size)
1523    return NULL;
1524  scoped_ptr<SpdyFrame> new_frame(new SpdyFrame(new_frame_size));
1525  memcpy(new_frame->data(), frame.data(), frame.length() + SpdyFrame::size());
1526
1527  decompressor->next_in = reinterpret_cast<Bytef*>(const_cast<char*>(payload));
1528  decompressor->avail_in = payload_length;
1529  decompressor->next_out = reinterpret_cast<Bytef*>(new_frame->data()) +
1530      header_length;
1531  decompressor->avail_out = decompressed_max_size;
1532
1533  int rv = inflate(decompressor, Z_SYNC_FLUSH);
1534  if (rv == Z_NEED_DICT) {
1535    // Need to try again with the right dictionary.
1536    if (decompressor->adler == dictionary_id) {
1537      rv = inflateSetDictionary(decompressor, (const Bytef*)kDictionary,
1538                                kDictionarySize);
1539      if (rv == Z_OK)
1540        rv = inflate(decompressor, Z_SYNC_FLUSH);
1541    }
1542  }
1543  if (rv != Z_OK) {  // How can we know that it decompressed everything?
1544    LOG(WARNING) << "inflate failure: " << rv;
1545    return NULL;
1546  }
1547
1548  // Unset the compressed flag for data frames.
1549  if (!new_frame->is_control_frame()) {
1550    SpdyDataFrame* data_frame =
1551        reinterpret_cast<SpdyDataFrame*>(new_frame.get());
1552    data_frame->set_flags(data_frame->flags() & ~DATA_FLAG_COMPRESSED);
1553  }
1554
1555  int decompressed_size = decompressed_max_size - decompressor->avail_out;
1556  new_frame->set_length(header_length + decompressed_size - SpdyFrame::size());
1557
1558  // If there is data left, then the frame didn't fully decompress.  This
1559  // means that there is stranded data at the end of this frame buffer which
1560  // will be ignored.
1561  DCHECK_EQ(decompressor->avail_in, 0u);
1562
1563  pre_decompress_bytes.Add(frame.length());
1564  post_decompress_bytes.Add(new_frame->length());
1565
1566  decompressed_frames.Increment();
1567
1568  return new_frame.release();
1569}
1570
1571void SpdyFramer::CleanupCompressorForStream(SpdyStreamId id) {
1572  CompressorMap::iterator it = stream_compressors_.find(id);
1573  if (it != stream_compressors_.end()) {
1574    z_stream* compressor = it->second;
1575    deflateEnd(compressor);
1576    delete compressor;
1577    stream_compressors_.erase(it);
1578  }
1579}
1580
1581void SpdyFramer::CleanupDecompressorForStream(SpdyStreamId id) {
1582  CompressorMap::iterator it = stream_decompressors_.find(id);
1583  if (it != stream_decompressors_.end()) {
1584    z_stream* decompressor = it->second;
1585    inflateEnd(decompressor);
1586    delete decompressor;
1587    stream_decompressors_.erase(it);
1588  }
1589}
1590
1591void SpdyFramer::CleanupStreamCompressorsAndDecompressors() {
1592  CompressorMap::iterator it;
1593
1594  it = stream_compressors_.begin();
1595  while (it != stream_compressors_.end()) {
1596    z_stream* compressor = it->second;
1597    deflateEnd(compressor);
1598    delete compressor;
1599    ++it;
1600  }
1601  stream_compressors_.clear();
1602
1603  it = stream_decompressors_.begin();
1604  while (it != stream_decompressors_.end()) {
1605    z_stream* decompressor = it->second;
1606    inflateEnd(decompressor);
1607    delete decompressor;
1608    ++it;
1609  }
1610  stream_decompressors_.clear();
1611}
1612
1613size_t SpdyFramer::BytesSafeToRead() const {
1614  switch (state_) {
1615    case SPDY_ERROR:
1616    case SPDY_DONE:
1617    case SPDY_AUTO_RESET:
1618    case SPDY_RESET:
1619      return 0;
1620    case SPDY_READING_COMMON_HEADER:
1621      DCHECK_LT(current_frame_len_, SpdyFrame::size());
1622      return SpdyFrame::size() - current_frame_len_;
1623    case SPDY_INTERPRET_CONTROL_FRAME_COMMON_HEADER:
1624      return 0;
1625    // TODO(rtenneti): Add support for SPDY_CONTROL_FRAME_BEFORE_HEADER_BLOCK
1626    // and SPDY_CONTROL_FRAME_HEADER_BLOCK.
1627    case SPDY_CONTROL_FRAME_BEFORE_HEADER_BLOCK:
1628    case SPDY_CONTROL_FRAME_HEADER_BLOCK:
1629      return 0;
1630    case SPDY_CONTROL_FRAME_PAYLOAD:
1631    case SPDY_IGNORE_REMAINING_PAYLOAD:
1632    case SPDY_FORWARD_STREAM_FRAME:
1633      return remaining_data_;
1634  }
1635  // We should never get to here.
1636  return 0;
1637}
1638
1639void SpdyFramer::set_error(SpdyError error) {
1640  DCHECK(visitor_);
1641  error_code_ = error;
1642  CHANGE_STATE(SPDY_ERROR);
1643  visitor_->OnError(this);
1644}
1645
1646void SpdyFramer::ExpandControlFrameBuffer(size_t size) {
1647  size_t alloc_size = size + SpdyFrame::size();
1648  DCHECK_LE(alloc_size, kControlFrameBufferMaxSize);
1649  if (alloc_size <= current_frame_capacity_)
1650    return;
1651  char* new_buffer = new char[alloc_size];
1652  memcpy(new_buffer, current_frame_buffer_, current_frame_len_);
1653  delete [] current_frame_buffer_;
1654  current_frame_capacity_ = alloc_size;
1655  current_frame_buffer_ = new_buffer;
1656}
1657
1658bool SpdyFramer::GetFrameBoundaries(const SpdyFrame& frame,
1659                                    int* payload_length,
1660                                    int* header_length,
1661                                    const char** payload) const {
1662  size_t frame_size;
1663  if (frame.is_control_frame()) {
1664    const SpdyControlFrame& control_frame =
1665        reinterpret_cast<const SpdyControlFrame&>(frame);
1666    switch (control_frame.type()) {
1667      case SYN_STREAM:
1668        {
1669          const SpdySynStreamControlFrame& syn_frame =
1670              reinterpret_cast<const SpdySynStreamControlFrame&>(frame);
1671          frame_size = SpdySynStreamControlFrame::size();
1672          *payload_length = syn_frame.header_block_len();
1673          *header_length = frame_size;
1674          *payload = frame.data() + *header_length;
1675        }
1676        break;
1677      case SYN_REPLY:
1678        {
1679          const SpdySynReplyControlFrame& syn_frame =
1680              reinterpret_cast<const SpdySynReplyControlFrame&>(frame);
1681          frame_size = SpdySynReplyControlFrame::size();
1682          *payload_length = syn_frame.header_block_len();
1683          *header_length = frame_size;
1684          *payload = frame.data() + *header_length;
1685        }
1686        break;
1687      case HEADERS:
1688        {
1689          const SpdyHeadersControlFrame& headers_frame =
1690              reinterpret_cast<const SpdyHeadersControlFrame&>(frame);
1691          frame_size = SpdyHeadersControlFrame::size();
1692          *payload_length = headers_frame.header_block_len();
1693          *header_length = frame_size;
1694          *payload = frame.data() + *header_length;
1695        }
1696        break;
1697      default:
1698        // TODO(mbelshe): set an error?
1699        return false;  // We can't compress this frame!
1700    }
1701  } else {
1702    frame_size = SpdyFrame::size();
1703    *header_length = frame_size;
1704    *payload_length = frame.length();
1705    *payload = frame.data() + SpdyFrame::size();
1706  }
1707  return true;
1708}
1709
1710}  // namespace spdy
1711