| // Copyright (c) 2015 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/quic/quic_frame_list.h" |
| |
| #include <algorithm> |
| |
| #include "base/logging.h" |
| |
| using std::list; |
| using std::string; |
| |
| namespace net { |
| |
| QuicFrameList::FrameData::FrameData(QuicStreamOffset offset, |
| string segment, |
| const QuicTime timestamp) |
| : offset(offset), segment(segment), timestamp(timestamp) {} |
| |
| QuicFrameList::QuicFrameList() {} |
| |
| QuicFrameList::~QuicFrameList() { |
| Clear(); |
| } |
| |
| void QuicFrameList::Clear() { |
| frame_list_.clear(); |
| num_bytes_buffered_ = 0; |
| } |
| |
| bool QuicFrameList::Empty() const { |
| return frame_list_.empty(); |
| } |
| |
| QuicErrorCode QuicFrameList::OnStreamData(QuicStreamOffset offset, |
| base::StringPiece data, |
| QuicTime timestamp, |
| size_t* const bytes_buffered) { |
| *bytes_buffered = 0; |
| const size_t data_len = data.size(); |
| auto insertion_point = FindInsertionPoint(offset, data_len); |
| if (IsDuplicate(offset, data_len, insertion_point)) { |
| return QUIC_NO_ERROR; |
| } |
| |
| if (FrameOverlapsBufferedData(offset, data_len, insertion_point)) { |
| return QUIC_INVALID_STREAM_DATA; |
| } |
| |
| DVLOG(1) << "Buffering stream data at offset " << offset; |
| // Inserting an empty string and then copying to avoid the extra copy. |
| insertion_point = |
| frame_list_.insert(insertion_point, FrameData(offset, "", timestamp)); |
| data.CopyToString(&insertion_point->segment); |
| *bytes_buffered = data_len; |
| num_bytes_buffered_ += data_len; |
| return QUIC_NO_ERROR; |
| } |
| |
| // Finds the place the frame should be inserted. If an identical frame is |
| // present, stops on the identical frame. |
| list<QuicFrameList::FrameData>::iterator QuicFrameList::FindInsertionPoint( |
| QuicStreamOffset offset, |
| size_t len) { |
| if (frame_list_.empty()) { |
| return frame_list_.begin(); |
| } |
| // If it's after all buffered_frames, return the end. |
| if (offset >= |
| (frame_list_.rbegin()->offset + frame_list_.rbegin()->segment.length())) { |
| return frame_list_.end(); |
| } |
| auto iter = frame_list_.begin(); |
| // Only advance the iterator if the data begins after the already received |
| // frame. If the new frame overlaps with an existing frame, the iterator will |
| // still point to the frame it overlaps with. |
| while (iter != frame_list_.end() && |
| offset >= iter->offset + iter->segment.length()) { |
| ++iter; |
| } |
| return iter; |
| } |
| |
| // Returns true if |frame| contains data which overlaps buffered data |
| // (indicating an invalid stream frame has been received). |
| bool QuicFrameList::FrameOverlapsBufferedData( |
| QuicStreamOffset offset, |
| size_t data_len, |
| list<FrameData>::const_iterator insertion_point) const { |
| if (frame_list_.empty() || insertion_point == frame_list_.end()) { |
| return false; |
| } |
| // If there is a buffered frame with a higher starting offset, then check to |
| // see if the new frame overlaps the beginning of the higher frame. |
| if (offset < insertion_point->offset && |
| offset + data_len > insertion_point->offset) { |
| DVLOG(1) << "New frame overlaps next frame: " << offset << " + " << data_len |
| << " > " << insertion_point->offset; |
| return true; |
| } |
| // If there is a buffered frame with a lower starting offset, then check to |
| // see if the buffered frame runs into the new frame. |
| if (offset >= insertion_point->offset && |
| offset < insertion_point->offset + insertion_point->segment.length()) { |
| DVLOG(1) << "Preceeding frame overlaps new frame: " |
| << insertion_point->offset << " + " |
| << insertion_point->segment.length() << " > " << offset; |
| return true; |
| } |
| |
| return false; |
| } |
| |
| // Returns true if the sequencer has received this frame before. |
| bool QuicFrameList::IsDuplicate( |
| QuicStreamOffset offset, |
| size_t data_len, |
| list<FrameData>::const_iterator insertion_point) const { |
| // A frame is duplicate if the frame offset is smaller than the bytes consumed |
| // or identical to an already received frame. |
| return offset < total_bytes_read_ || (insertion_point != frame_list_.end() && |
| offset == insertion_point->offset); |
| } |
| |
| int QuicFrameList::GetReadableRegions(struct iovec* iov, int iov_len) const { |
| list<FrameData>::const_iterator it = frame_list_.begin(); |
| int index = 0; |
| QuicStreamOffset offset = total_bytes_read_; |
| while (it != frame_list_.end() && index < iov_len) { |
| if (it->offset != offset) { |
| return index; |
| } |
| |
| iov[index].iov_base = |
| static_cast<void*>(const_cast<char*>(it->segment.data())); |
| iov[index].iov_len = it->segment.size(); |
| offset += it->segment.size(); |
| |
| ++index; |
| ++it; |
| } |
| return index; |
| } |
| |
| bool QuicFrameList::GetReadableRegion(iovec* iov, QuicTime* timestamp) const { |
| list<FrameData>::const_iterator it = frame_list_.begin(); |
| if (it == frame_list_.end() || it->offset != total_bytes_read_) { |
| return false; |
| } |
| iov->iov_base = static_cast<void*>(const_cast<char*>(it->segment.data())); |
| iov->iov_len = it->segment.size(); |
| *timestamp = it->timestamp; |
| return true; |
| } |
| |
| bool QuicFrameList::MarkConsumed(size_t bytes_used) { |
| size_t end_offset = total_bytes_read_ + bytes_used; |
| while (!frame_list_.empty() && end_offset != total_bytes_read_) { |
| list<FrameData>::iterator it = frame_list_.begin(); |
| if (it->offset != total_bytes_read_) { |
| return false; |
| } |
| |
| if (it->offset + it->segment.length() <= end_offset) { |
| total_bytes_read_ += it->segment.length(); |
| num_bytes_buffered_ -= it->segment.length(); |
| // This chunk is entirely consumed. |
| frame_list_.erase(it); |
| continue; |
| } |
| |
| // Partially consume this frame. |
| size_t delta = end_offset - it->offset; |
| total_bytes_read_ += delta; |
| num_bytes_buffered_ -= delta; |
| string new_data = it->segment.substr(delta); |
| const QuicTime timestamp = it->timestamp; |
| frame_list_.erase(it); |
| frame_list_.push_front(FrameData(total_bytes_read_, new_data, timestamp)); |
| break; |
| } |
| return true; |
| } |
| |
| size_t QuicFrameList::Readv(const struct iovec* iov, size_t iov_len) { |
| list<FrameData>::iterator it = frame_list_.begin(); |
| size_t iov_index = 0; |
| size_t iov_offset = 0; |
| size_t frame_offset = 0; |
| QuicStreamOffset initial_bytes_consumed = total_bytes_read_; |
| |
| while (iov_index < iov_len && it != frame_list_.end() && |
| it->offset == total_bytes_read_) { |
| int bytes_to_read = std::min(iov[iov_index].iov_len - iov_offset, |
| it->segment.size() - frame_offset); |
| |
| char* iov_ptr = static_cast<char*>(iov[iov_index].iov_base) + iov_offset; |
| memcpy(iov_ptr, it->segment.data() + frame_offset, bytes_to_read); |
| frame_offset += bytes_to_read; |
| iov_offset += bytes_to_read; |
| |
| if (iov[iov_index].iov_len == iov_offset) { |
| // We've filled this buffer. |
| iov_offset = 0; |
| ++iov_index; |
| } |
| if (it->segment.size() == frame_offset) { |
| // We've copied this whole frame |
| total_bytes_read_ += it->segment.size(); |
| num_bytes_buffered_ -= it->segment.size(); |
| frame_list_.erase(it); |
| it = frame_list_.begin(); |
| frame_offset = 0; |
| } |
| } |
| // Done copying. If there is a partial frame, update it. |
| if (frame_offset != 0) { |
| frame_list_.push_front(FrameData(it->offset + frame_offset, |
| it->segment.substr(frame_offset), |
| it->timestamp)); |
| frame_list_.erase(it); |
| total_bytes_read_ += frame_offset; |
| num_bytes_buffered_ -= frame_offset; |
| } |
| return total_bytes_read_ - initial_bytes_consumed; |
| } |
| |
| size_t QuicFrameList::FlushBufferedFrames() { |
| QuicStreamOffset initial_bytes_consumed = total_bytes_read_; |
| if (!frame_list_.empty()) { |
| // Consume all of the bytes up to the last byte yet seen, including the |
| // ones that haven't arrived yet. |
| auto it = frame_list_.back(); |
| total_bytes_read_ = it.offset + it.segment.length(); |
| frame_list_.clear(); |
| } |
| return total_bytes_read_ - initial_bytes_consumed; |
| } |
| |
| bool QuicFrameList::HasBytesToRead() const { |
| return !frame_list_.empty() && |
| frame_list_.begin()->offset == total_bytes_read_; |
| } |
| |
| QuicStreamOffset QuicFrameList::BytesConsumed() const { |
| return total_bytes_read_; |
| } |
| |
| size_t QuicFrameList::BytesBuffered() const { |
| return num_bytes_buffered_; |
| } |
| |
| } // namespace net |