Add WebSocketFrameParser.

net/websockets/websocket_frame_parser.cc

+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/websockets/websocket_frame_parser.h"
+
+#include <algorithm>
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/memory/scoped_vector.h"
+#include "base/memory/ref_counted.h"
+#include "net/base/big_endian.h"
+#include "net/websockets/websocket_frame.h"
+
+const uint8 kFinalBit = 0x80;
+const uint8 kReserved1Bit = 0x40;
+const uint8 kReserved2Bit = 0x20;
+const uint8 kReserved3Bit = 0x10;
+const uint8 kOpCodeMask = 0xF;
+const uint8 kMaskBit = 0x80;
+const uint8 kPayloadLengthMask = 0x7F;
+const uint64 kMaxPayloadLengthWithoutExtendedLengthField = 125;
+const uint64 kPayloadLengthWithTwoByteExtendedLengthField = 126;
+const uint64 kPayloadLengthWithEightByteExtendedLengthField = 127;
+
+namespace net {
+
+WebSocketFrameParser::WebSocketFrameParser()
+    : buffer_pos_(0),
+      frame_offset_(0),
+      failed_(false) {
+  std::fill(masking_key_,
+            masking_key_ + WebSocketFrameHeader::kMaskingKeyLength,
+            '\0');
+}
+
+WebSocketFrameParser::~WebSocketFrameParser() {
+}
+
+bool WebSocketFrameParser::Decode(
+    const char* data,
+    size_t length,
+    ScopedVector<WebSocketPartialFrame>* frames) {
+  static const int kMaskingKeyLength = WebSocketFrameHeader::kMaskingKeyLength;
+
+  if (failed_)
+    return false;
+  if (!length)
+    return true;
+
+  // TODO(yutak): Remove copy.
+  buffer_.insert(buffer_.end(), data, data + length);
+
+  while (buffer_pos_ < buffer_.size()) {
+    if (!current_frame_header_.get()) {
+      DecodeFrameHeader();
+      if (failed_)
+        return false;
+      if (!current_frame_header_.get())
+        break;
+    }
+
+    // Reads frame payload. Unmasks it if necessary.

[bashi, 2012/04/03 09:35:50]

How about extracting the following payload-parsing code as private a function
like DecodeFrameHeader()?

[Yuta Kitamura, 2012/04/09 08:17:57]

Sounds like a good idea. Will do.

+    const char* current = &buffer_.front() + buffer_pos_;
+    const char* end = &buffer_.front() + buffer_.size();
+    uint64 next_size = std::min<uint64>(
+        end - current,
+        current_frame_header_->payload_length - frame_offset_);
+
+    scoped_ptr<WebSocketPartialFrame> frame(new WebSocketPartialFrame);
+    frame->header = current_frame_header_;
+    frame->final_part = false;
+    frame->data.assign(current, current + next_size);
+    if (current_frame_header_->masked) {
+      size_t key_offset = frame_offset_ % kMaskingKeyLength;
+      for (uint64 i = 0; i < next_size; ++i) {
+        frame->data[i] ^= masking_key_[key_offset];
+        key_offset = (key_offset + 1) % kMaskingKeyLength;
+      }
+    }
+
+    buffer_pos_ += next_size;
+    frame_offset_ += next_size;
+
+    DCHECK_LE(frame_offset_, current_frame_header_->payload_length);
+    if (frame_offset_ == current_frame_header_->payload_length) {
+      frame->final_part = true;
+      current_frame_header_ = NULL;
+      frame_offset_ = 0;
+      std::fill(masking_key_, masking_key_ + kMaskingKeyLength, '\0');
+    }
+
+    frames->push_back(frame.release());
+
+    if (current_frame_header_.get())
+      break;
+  }
+
+  // Drain unnecessary data. TODO(yutak): Remove copy. (but how?)
+  buffer_.erase(buffer_.begin(), buffer_.begin() + buffer_pos_);
+  buffer_pos_ = 0;
+
+  return true;
+}
+
+bool WebSocketFrameParser::failed() const {
+  return failed_;

[bashi, 2012/04/03 09:35:50]

WebKit's implementation tells the reason of the failure via
WebSocketChannel::fail(). It might be better to have similar mechanism.

[Yuta Kitamura, 2012/04/09 08:17:57]

I'll leave this as a TODO. It might be better for us to have an exhaustive list
of WebSocket errors and assign error code for each situation, instead of
returning a error message.

+}
+
+void WebSocketFrameParser::DecodeFrameHeader() {

[bashi, 2012/04/03 09:35:50]

Adding a comment that describes |buffer_pos_| only updates when the header is
completely parsed (or failed) will help to understand why it is safe to break at
line 61.

[Takashi Toyoshima, 2012/04/04 05:46:21]

Maybe this variable name is a little vague.
|buffer_pos_| reminds me two kinds of possible meaning.
One is data appending position, the other is parsing head position.
|buffer_caret_| is one of possible candidate for the latter meaning, I think.

[Yuta Kitamura, 2012/04/09 08:17:57]

Maybe |current_read_pos_|? Anyway I'm going to add comments to clarify the
usage.

[Takashi Toyoshima, 2012/04/09 23:12:16]

sounds good.

+  typedef WebSocketFrameHeader::OpCode OpCode;
+  static const int kMaskingKeyLength = WebSocketFrameHeader::kMaskingKeyLength;
+
+  const char* start = &buffer_.front() + buffer_pos_;
+  const char* current = start;
+  const char* end = &buffer_.front() + buffer_.size();

[Takashi Toyoshima, 2012/04/04 05:46:21]

I guess operator[] or iterator are enough to meet performance requirement here.
Also from the viewpoints of readability.

[Yuta Kitamura, 2012/04/09 08:17:57]

Using operator[] employs index arithmetic, and the code inside [] will look
messy as we need to use indices with the offset added (buffer_pos_). It sounds
harder to make sure the code doesn't include errors like index overflow or
off-by-one. Thus I'm against using operator[].

Using iterator is not so different from the current code, and I feel I'm mostly
fine with iterators, but there is a slight downside that we can't use
ReadBigEndian() directly.

I'm not inclined to use iterators, though, as the benefit of iterators over
char* is still unclear to me. Note that it's perfectly fine to get char* from
vector<char> like above, because it's guaranteed that elements of a vector<> are
stored in a contiguous storage.

[Takashi Toyoshima, 2012/04/09 23:12:16]

As a first impression, I prefer readability than optimization here because we
just handle a few bytes on parsing headers. I didn't have a clear idea on
performance because of following reason.
Generally speaking;
 - increasing local variables might cause problematic register spill and fill
 - memory aliasing makes compiler optimization difficult
 - additional calculation as you said will be hidden behind super scalar and out
of order execution

After my first comment, I did a trial on this and noticed that [] operation make
its assembly much simpler and faster than pointer operation. Each [] operation
will be mapped into one assembly like "movb %al, (%rsi, %rcx)". Compiler's
optimization seems to beat everything.

[Yuta Kitamura, 2012/04/10 05:34:00]

A big question: "Does that matter?"

All your discussion seems categorized as a "premature optimization"; we
shouldn't do that on an early stage like this. We'll defintely profile the
performance and fix performance issues later on, but at this point the primary
focus should be readability and mainteinability, not doing hacks on compilers.

[Takashi Toyoshima, 2012/04/11 05:37:54]

As I said, I prefer readability.
Please remove unreadable optimization here if it doesn't matter.

[Yuta Kitamura, 2012/04/11 08:48:53]

I didn't intend to do any optimization here. I don't think it's unreadable
either. The code is pretty straightforward and conforms to C++ standards. I
chose ".front()" instead of "[0]" just because the former doesn't include a
magic number. There's no intention of optimization at all.

Why did you think my code is doing some optimization? I misread your comment at
05:46:21 as "Use operator[] or iterator because they are faster", and your
comment at 23:12:16 as "optimize the code because local variables are bad and
operator[] is fast", but my understanding was apparently wrong.

When you make some review comments, please be specific about why your fix is
important (possibly with measurable/objective data). The reason and necessity of
fix weren't obvious in this case.

+
+  // Header needs 2 bytes at minimum.
+  if (end - current < 2)
+    return;

[Takashi Toyoshima, 2012/04/04 05:46:21]

This check must be done firstly as 'buffer_.size() < 2'.

[Yuta Kitamura, 2012/04/09 08:17:57]

|end - current| is used idiomatically to get the size of remaining data
available. So I think I should keep this as-is.

[Takashi Toyoshima, 2012/04/09 23:12:16]

I think it's true that "&buffer_.front() == &buffer_[0]" here.
If it's true, following code can be quite simpler.

[Yuta Kitamura, 2012/04/10 05:34:00]

I don't get your point, but actually "&buffer_.front() == &buffer_[0]" is always
true for non-empty vectors.

(I really wanted to use buffer_.data(), but data() is not defined in C++
standard and actually MSVC doesn't have it.)

[Takashi Toyoshima, 2012/04/12 06:08:50]

Sorry, I misunderstand this point.
My expectation that buffer_pos_ is always 0 at that start point of this function
looks wrong.

If this expectation was wrong, I guess my approach may not as smart as I expect.
Now, I'm OK to keep current code for header parsing.

+
+  uint8 first_byte = *current++;
+  uint8 second_byte = *current++;
+
+  bool final = (first_byte & kFinalBit) != 0;
+  bool reserved1 = (first_byte & kReserved1Bit) != 0;
+  bool reserved2 = (first_byte & kReserved2Bit) != 0;
+  bool reserved3 = (first_byte & kReserved3Bit) != 0;
+  OpCode opcode = first_byte & kOpCodeMask;
+
+  bool masked = (second_byte & kMaskBit) != 0;
+  uint64 payload_length = second_byte & kPayloadLengthMask;
+  bool valid_length_format = true;
+  if (payload_length == kPayloadLengthWithTwoByteExtendedLengthField) {
+    if (end - current < 2)
+      return;
+    uint16 payload_length_16;
+    ReadBigEndian(current, &payload_length_16);
+    current += 2;
+    payload_length = payload_length_16;
+    if (payload_length <= kMaxPayloadLengthWithoutExtendedLengthField)
+      valid_length_format = false;
+  } else if (payload_length == kPayloadLengthWithEightByteExtendedLengthField) {
+    if (end - current < 8)
+      return;
+    ReadBigEndian(current, &payload_length);
+    current += 8;
+    if (payload_length <= kuint16max ||
+        payload_length > static_cast<uint64>(kint64max)) {
+      valid_length_format = false;
+    }
+  }
+  if (!valid_length_format) {
+    failed_ = true;
+    buffer_.clear();
+    buffer_pos_ = 0;
+    current_frame_header_ = NULL;
+    frame_offset_ = 0;
+    return;
+  }
+
+  if (masked) {
+    if (end - current < kMaskingKeyLength)
+      return;
+    std::copy(current, current + kMaskingKeyLength, masking_key_);
+    current += kMaskingKeyLength;
+  }
+

[Takashi Toyoshima, 2012/04/04 05:46:21]

We should implement continuation opcode consistency check here.
Maybe recovering original opcode like text or binary is useful.
You may want to replace opcode, or add another field for restored opcode.

This change can be splited to another CL.

[Yuta Kitamura, 2012/04/09 08:17:57]

I'm ambivarent about doing a check here.

My original idea is that this class is a protocol-agnostic parser and hence does
not do semantic checks, and they are left as upper-layer's (WebSocketStream's)
responsibility. But checking here might be a good thing.

I need to make sure the interface is consistent between Parser and Builder (the
latter doesn't exist yet). Will need to revisit this later.

[Takashi Toyoshima, 2012/04/09 23:12:16]

Sharing semantic checker between parser and builder looks nice!

+  current_frame_header_ = new WebSocketFrameHeader;
+  current_frame_header_->final = final;
+  current_frame_header_->reserved1 = reserved1;
+  current_frame_header_->reserved2 = reserved2;
+  current_frame_header_->reserved3 = reserved3;
+  current_frame_header_->opcode = opcode;
+  current_frame_header_->masked = masked;
+  current_frame_header_->payload_length = payload_length;
+  buffer_pos_ += current - start;
+  DCHECK_EQ(0u, frame_offset_);
+}
+
+}  // namespace net