Index: net/quic/quic_stream_sequencer_buffer.cc |
diff --git a/net/quic/quic_stream_sequencer_buffer.cc b/net/quic/quic_stream_sequencer_buffer.cc |
deleted file mode 100644 |
index 352db230dc6fffa32c78fe00bf5aee0e9ecab3ba..0000000000000000000000000000000000000000 |
--- a/net/quic/quic_stream_sequencer_buffer.cc |
+++ /dev/null |
@@ -1,505 +0,0 @@ |
-// 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_stream_sequencer_buffer.h" |
- |
-#include "base/logging.h" |
-#include "base/strings/string_number_conversions.h" |
-#include "net/quic/quic_bug_tracker.h" |
- |
-using std::min; |
-using std::string; |
- |
-namespace net { |
- |
-namespace { |
- |
-string RangeDebugString(QuicStreamOffset start, QuicStreamOffset end) { |
- return string("[") + base::Uint64ToString(start) + ", " + |
- base::Uint64ToString(end) + ") "; |
-} |
- |
-} // namespace |
- |
-QuicStreamSequencerBuffer::Gap::Gap(QuicStreamOffset begin_offset, |
- QuicStreamOffset end_offset) |
- : begin_offset(begin_offset), end_offset(end_offset) {} |
- |
-QuicStreamSequencerBuffer::FrameInfo::FrameInfo() |
- : length(1), timestamp(QuicTime::Zero()) {} |
- |
-QuicStreamSequencerBuffer::FrameInfo::FrameInfo(size_t length, |
- QuicTime timestamp) |
- : length(length), timestamp(timestamp) {} |
- |
-QuicStreamSequencerBuffer::QuicStreamSequencerBuffer(size_t max_capacity_bytes) |
- : max_buffer_capacity_bytes_(max_capacity_bytes), |
- blocks_count_( |
- ceil(static_cast<double>(max_capacity_bytes) / kBlockSizeBytes)), |
- total_bytes_read_(0), |
- blocks_(blocks_count_) { |
- Clear(); |
-} |
- |
-QuicStreamSequencerBuffer::~QuicStreamSequencerBuffer() { |
- Clear(); |
-} |
- |
-void QuicStreamSequencerBuffer::Clear() { |
- for (size_t i = 0; i < blocks_count_; ++i) { |
- if (blocks_[i] != nullptr) { |
- RetireBlock(i); |
- } |
- } |
- num_bytes_buffered_ = 0; |
- // Reset gaps_ so that buffer is in a state as if all data before |
- // total_bytes_read_ has been consumed, and those after total_bytes_read_ |
- // has never arrived. |
- gaps_ = std::list<Gap>( |
- 1, Gap(total_bytes_read_, std::numeric_limits<QuicStreamOffset>::max())), |
- frame_arrival_time_map_.clear(); |
-} |
- |
-void QuicStreamSequencerBuffer::RetireBlock(size_t idx) { |
- DCHECK(blocks_[idx] != nullptr); |
- delete blocks_[idx]; |
- blocks_[idx] = nullptr; |
- DVLOG(1) << "Retired block with index: " << idx; |
-} |
- |
-QuicErrorCode QuicStreamSequencerBuffer::OnStreamData( |
- QuicStreamOffset starting_offset, |
- base::StringPiece data, |
- QuicTime timestamp, |
- size_t* const bytes_buffered, |
- std::string* error_details) { |
- *bytes_buffered = 0; |
- QuicStreamOffset offset = starting_offset; |
- size_t size = data.size(); |
- if (size == 0) { |
- *error_details = "Received empty stream frame without FIN."; |
- return QUIC_EMPTY_STREAM_FRAME_NO_FIN; |
- } |
- |
- // Find the first gap not ending before |offset|. This gap maybe the gap to |
- // fill if the arriving frame doesn't overlaps with previous ones. |
- std::list<Gap>::iterator current_gap = gaps_.begin(); |
- while (current_gap != gaps_.end() && current_gap->end_offset <= offset) { |
- ++current_gap; |
- } |
- |
- DCHECK(current_gap != gaps_.end()); |
- |
- // "duplication": might duplicate with data alread filled,but also might |
- // overlap across different base::StringPiece objects already written. |
- // In both cases, don't write the data, |
- // and allow the caller of this method to handle the result. |
- if (offset < current_gap->begin_offset && |
- offset + size <= current_gap->begin_offset) { |
- DVLOG(1) << "Duplicated data at offset: " << offset << " length: " << size; |
- return QUIC_NO_ERROR; |
- } |
- if (offset < current_gap->begin_offset && |
- offset + size > current_gap->begin_offset) { |
- // Beginning of new data overlaps data before current gap. |
- *error_details = |
- string("Beginning of received data overlaps with buffered data.\n") + |
- "New frame range " + RangeDebugString(offset, offset + size) + |
- " with first 128 bytes: " + |
- string(data.data(), data.length() < 128 ? data.length() : 128) + |
- "\nCurrently received frames: " + ReceivedFramesDebugString() + |
- "\nCurrent gaps: " + GapsDebugString(); |
- return QUIC_OVERLAPPING_STREAM_DATA; |
- } |
- if (offset + size > current_gap->end_offset) { |
- // End of new data overlaps with data after current gap. |
- *error_details = |
- string("End of received data overlaps with buffered data.\n") + |
- "New frame range " + RangeDebugString(offset, offset + size) + |
- " with first 128 bytes: " + |
- string(data.data(), data.length() < 128 ? data.length() : 128) + |
- "\nCurrently received frames: " + ReceivedFramesDebugString() + |
- "\nCurrent gaps: " + GapsDebugString(); |
- return QUIC_OVERLAPPING_STREAM_DATA; |
- } |
- |
- // Write beyond the current range this buffer is covering. |
- if (offset + size > total_bytes_read_ + max_buffer_capacity_bytes_) { |
- *error_details = "Received data beyond available range."; |
- return QUIC_INTERNAL_ERROR; |
- } |
- |
- size_t total_written = 0; |
- size_t source_remaining = size; |
- const char* source = data.data(); |
- // Write data block by block. If corresponding block has not created yet, |
- // create it first. |
- // Stop when all data are written or reaches the logical end of the buffer. |
- while (source_remaining > 0) { |
- const size_t write_block_num = GetBlockIndex(offset); |
- const size_t write_block_offset = GetInBlockOffset(offset); |
- DCHECK_GT(blocks_count_, write_block_num); |
- |
- size_t block_capacity = GetBlockCapacity(write_block_num); |
- size_t bytes_avail = block_capacity - write_block_offset; |
- |
- // If this write meets the upper boundary of the buffer, |
- // reduce the available free bytes. |
- if (offset + bytes_avail > total_bytes_read_ + max_buffer_capacity_bytes_) { |
- bytes_avail = total_bytes_read_ + max_buffer_capacity_bytes_ - offset; |
- } |
- |
- if (blocks_[write_block_num] == nullptr) { |
- // TODO(danzh): Investigate if using a freelist would improve performance. |
- // Same as RetireBlock(). |
- blocks_[write_block_num] = new BufferBlock(); |
- } |
- |
- const size_t bytes_to_copy = min<size_t>(bytes_avail, source_remaining); |
- char* dest = blocks_[write_block_num]->buffer + write_block_offset; |
- DVLOG(1) << "Write at offset: " << offset << " length: " << bytes_to_copy; |
- memcpy(dest, source, bytes_to_copy); |
- source += bytes_to_copy; |
- source_remaining -= bytes_to_copy; |
- offset += bytes_to_copy; |
- total_written += bytes_to_copy; |
- } |
- |
- DCHECK_GT(total_written, 0u); |
- *bytes_buffered = total_written; |
- UpdateGapList(current_gap, starting_offset, total_written); |
- |
- frame_arrival_time_map_.insert( |
- std::make_pair(starting_offset, FrameInfo(size, timestamp))); |
- num_bytes_buffered_ += total_written; |
- return QUIC_NO_ERROR; |
-} |
- |
-inline void QuicStreamSequencerBuffer::UpdateGapList( |
- std::list<Gap>::iterator gap_with_new_data_written, |
- QuicStreamOffset start_offset, |
- size_t bytes_written) { |
- if (gap_with_new_data_written->begin_offset == start_offset && |
- gap_with_new_data_written->end_offset > start_offset + bytes_written) { |
- // New data has been written into the left part of the buffer. |
- gap_with_new_data_written->begin_offset = start_offset + bytes_written; |
- } else if (gap_with_new_data_written->begin_offset < start_offset && |
- gap_with_new_data_written->end_offset == |
- start_offset + bytes_written) { |
- // New data has been written into the right part of the buffer. |
- gap_with_new_data_written->end_offset = start_offset; |
- } else if (gap_with_new_data_written->begin_offset < start_offset && |
- gap_with_new_data_written->end_offset > |
- start_offset + bytes_written) { |
- // New data has been written into the middle of the buffer. |
- auto current = gap_with_new_data_written++; |
- QuicStreamOffset current_end = current->end_offset; |
- current->end_offset = start_offset; |
- gaps_.insert(gap_with_new_data_written, |
- Gap(start_offset + bytes_written, current_end)); |
- } else if (gap_with_new_data_written->begin_offset == start_offset && |
- gap_with_new_data_written->end_offset == |
- start_offset + bytes_written) { |
- // This gap has been filled with new data. So it's no longer a gap. |
- gaps_.erase(gap_with_new_data_written); |
- } |
-} |
- |
-size_t QuicStreamSequencerBuffer::Readv(const iovec* dest_iov, |
- size_t dest_count) { |
- size_t bytes_read = 0; |
- for (size_t i = 0; i < dest_count && ReadableBytes() > 0; ++i) { |
- char* dest = reinterpret_cast<char*>(dest_iov[i].iov_base); |
- size_t dest_remaining = dest_iov[i].iov_len; |
- while (dest_remaining > 0 && ReadableBytes() > 0) { |
- size_t block_idx = NextBlockToRead(); |
- size_t start_offset_in_block = ReadOffset(); |
- size_t block_capacity = GetBlockCapacity(block_idx); |
- size_t bytes_available_in_block = |
- min<size_t>(ReadableBytes(), block_capacity - start_offset_in_block); |
- size_t bytes_to_copy = |
- min<size_t>(bytes_available_in_block, dest_remaining); |
- DCHECK_GT(bytes_to_copy, 0u); |
- DCHECK_NE(static_cast<BufferBlock*>(nullptr), blocks_[block_idx]); |
- memcpy(dest, blocks_[block_idx]->buffer + start_offset_in_block, |
- bytes_to_copy); |
- dest += bytes_to_copy; |
- dest_remaining -= bytes_to_copy; |
- num_bytes_buffered_ -= bytes_to_copy; |
- total_bytes_read_ += bytes_to_copy; |
- bytes_read += bytes_to_copy; |
- |
- // Retire the block if all the data is read out |
- // and no other data is stored in this block. |
- if (bytes_to_copy == bytes_available_in_block) { |
- RetireBlockIfEmpty(block_idx); |
- } |
- } |
- } |
- |
- if (bytes_read > 0) { |
- UpdateFrameArrivalMap(total_bytes_read_); |
- } |
- return bytes_read; |
-} |
- |
-int QuicStreamSequencerBuffer::GetReadableRegions(struct iovec* iov, |
- int iov_count) const { |
- DCHECK(iov != nullptr); |
- DCHECK_GT(iov_count, 0); |
- |
- if (ReadableBytes() == 0) { |
- iov[0].iov_base = nullptr; |
- iov[0].iov_len = 0; |
- return 0; |
- } |
- |
- size_t start_block_idx = NextBlockToRead(); |
- QuicStreamOffset readable_offset_end = gaps_.front().begin_offset - 1; |
- DCHECK_GE(readable_offset_end + 1, total_bytes_read_); |
- size_t end_block_offset = GetInBlockOffset(readable_offset_end); |
- size_t end_block_idx = GetBlockIndex(readable_offset_end); |
- |
- // If readable region is within one block, deal with it seperately. |
- if (start_block_idx == end_block_idx && ReadOffset() <= end_block_offset) { |
- iov[0].iov_base = blocks_[start_block_idx]->buffer + ReadOffset(); |
- iov[0].iov_len = ReadableBytes(); |
- DVLOG(1) << "Got only a single block with index: " << start_block_idx; |
- return 1; |
- } |
- |
- // Get first block |
- iov[0].iov_base = blocks_[start_block_idx]->buffer + ReadOffset(); |
- iov[0].iov_len = GetBlockCapacity(start_block_idx) - ReadOffset(); |
- DVLOG(1) << "Got first block " << start_block_idx << " with len " |
- << iov[0].iov_len; |
- DCHECK_GT(readable_offset_end + 1, total_bytes_read_ + iov[0].iov_len) |
- << "there should be more available data"; |
- |
- // Get readable regions of the rest blocks till either 2nd to last block |
- // before gap is met or |iov| is filled. For these blocks, one whole block is |
- // a region. |
- int iov_used = 1; |
- size_t block_idx = (start_block_idx + iov_used) % blocks_count_; |
- while (block_idx != end_block_idx && iov_used < iov_count) { |
- DCHECK_NE(static_cast<BufferBlock*>(nullptr), blocks_[block_idx]); |
- iov[iov_used].iov_base = blocks_[block_idx]->buffer; |
- iov[iov_used].iov_len = GetBlockCapacity(block_idx); |
- DVLOG(1) << "Got block with index: " << block_idx; |
- ++iov_used; |
- block_idx = (start_block_idx + iov_used) % blocks_count_; |
- } |
- |
- // Deal with last block if |iov| can hold more. |
- if (iov_used < iov_count) { |
- DCHECK_NE(static_cast<BufferBlock*>(nullptr), blocks_[block_idx]); |
- iov[iov_used].iov_base = blocks_[end_block_idx]->buffer; |
- iov[iov_used].iov_len = end_block_offset + 1; |
- DVLOG(1) << "Got last block with index: " << end_block_idx; |
- ++iov_used; |
- } |
- return iov_used; |
-} |
- |
-bool QuicStreamSequencerBuffer::GetReadableRegion(iovec* iov, |
- QuicTime* timestamp) const { |
- if (ReadableBytes() == 0) { |
- iov[0].iov_base = nullptr; |
- iov[0].iov_len = 0; |
- return false; |
- } |
- |
- size_t start_block_idx = NextBlockToRead(); |
- iov->iov_base = blocks_[start_block_idx]->buffer + ReadOffset(); |
- size_t readable_bytes_in_block = min<size_t>( |
- GetBlockCapacity(start_block_idx) - ReadOffset(), ReadableBytes()); |
- size_t region_len = 0; |
- auto iter = frame_arrival_time_map_.begin(); |
- *timestamp = iter->second.timestamp; |
- DVLOG(1) << "Readable bytes in block: " << readable_bytes_in_block; |
- for (; iter != frame_arrival_time_map_.end() && |
- region_len + iter->second.length <= readable_bytes_in_block; |
- ++iter) { |
- if (iter->second.timestamp != *timestamp) { |
- // If reaches a frame arrive at another timestamp, stop expanding current |
- // region. |
- DVLOG(1) << "Meet frame with different timestamp."; |
- break; |
- } |
- region_len += iter->second.length; |
- DVLOG(1) << "Added bytes to region: " << iter->second.length; |
- } |
- if (iter == frame_arrival_time_map_.end() || |
- iter->second.timestamp == *timestamp) { |
- // If encountered the end of readable bytes before reaching a different |
- // timestamp. |
- DVLOG(1) << "Got all readable bytes in first block."; |
- region_len = readable_bytes_in_block; |
- } |
- iov->iov_len = region_len; |
- return true; |
-} |
- |
-bool QuicStreamSequencerBuffer::MarkConsumed(size_t bytes_used) { |
- if (bytes_used > ReadableBytes()) { |
- return false; |
- } |
- size_t bytes_to_consume = bytes_used; |
- while (bytes_to_consume > 0) { |
- size_t block_idx = NextBlockToRead(); |
- size_t offset_in_block = ReadOffset(); |
- size_t bytes_available = min<size_t>( |
- ReadableBytes(), GetBlockCapacity(block_idx) - offset_in_block); |
- size_t bytes_read = min<size_t>(bytes_to_consume, bytes_available); |
- total_bytes_read_ += bytes_read; |
- num_bytes_buffered_ -= bytes_read; |
- bytes_to_consume -= bytes_read; |
- // If advanced to the end of current block and end of buffer hasn't wrapped |
- // to this block yet. |
- if (bytes_available == bytes_read) { |
- RetireBlockIfEmpty(block_idx); |
- } |
- } |
- if (bytes_used > 0) { |
- UpdateFrameArrivalMap(total_bytes_read_); |
- } |
- return true; |
-} |
- |
-size_t QuicStreamSequencerBuffer::FlushBufferedFrames() { |
- size_t prev_total_bytes_read = total_bytes_read_; |
- total_bytes_read_ = gaps_.back().begin_offset; |
- Clear(); |
- return total_bytes_read_ - prev_total_bytes_read; |
-} |
- |
-size_t QuicStreamSequencerBuffer::ReadableBytes() const { |
- return gaps_.front().begin_offset - total_bytes_read_; |
-} |
- |
-bool QuicStreamSequencerBuffer::HasBytesToRead() const { |
- return ReadableBytes() > 0; |
-} |
- |
-QuicStreamOffset QuicStreamSequencerBuffer::BytesConsumed() const { |
- return total_bytes_read_; |
-} |
- |
-size_t QuicStreamSequencerBuffer::BytesBuffered() const { |
- return num_bytes_buffered_; |
-} |
- |
-size_t QuicStreamSequencerBuffer::GetBlockIndex(QuicStreamOffset offset) const { |
- return (offset % max_buffer_capacity_bytes_) / kBlockSizeBytes; |
-} |
- |
-size_t QuicStreamSequencerBuffer::GetInBlockOffset( |
- QuicStreamOffset offset) const { |
- return (offset % max_buffer_capacity_bytes_) % kBlockSizeBytes; |
-} |
- |
-size_t QuicStreamSequencerBuffer::ReadOffset() const { |
- return GetInBlockOffset(total_bytes_read_); |
-} |
- |
-size_t QuicStreamSequencerBuffer::NextBlockToRead() const { |
- return GetBlockIndex(total_bytes_read_); |
-} |
- |
-void QuicStreamSequencerBuffer::RetireBlockIfEmpty(size_t block_index) { |
- DCHECK(ReadableBytes() == 0 || GetInBlockOffset(total_bytes_read_) == 0) |
- << "RetireBlockIfEmpty() should only be called when advancing to next " |
- "block" |
- " or a gap has been reached."; |
- // If the whole buffer becomes empty, the last piece of data has been read. |
- if (Empty()) { |
- RetireBlock(block_index); |
- return; |
- } |
- |
- // Check where the logical end of this buffer is. |
- // Not empty if the end of circular buffer has been wrapped to this block. |
- if (GetBlockIndex(gaps_.back().begin_offset - 1) == block_index) { |
- return; |
- } |
- |
- // Read index remains in this block, which means a gap has been reached. |
- if (NextBlockToRead() == block_index) { |
- Gap first_gap = gaps_.front(); |
- DCHECK(first_gap.begin_offset == total_bytes_read_); |
- // Check where the next piece data is. |
- // Not empty if next piece of data is still in this chunk. |
- bool gap_extends_to_infinity = |
- (first_gap.end_offset != std::numeric_limits<QuicStreamOffset>::max()); |
- bool gap_ends_in_this_block = |
- (GetBlockIndex(first_gap.end_offset) == block_index); |
- if (gap_extends_to_infinity || gap_ends_in_this_block) { |
- return; |
- } |
- } |
- RetireBlock(block_index); |
-} |
- |
-bool QuicStreamSequencerBuffer::Empty() const { |
- return gaps_.size() == 1 && gaps_.front().begin_offset == total_bytes_read_; |
-} |
- |
-size_t QuicStreamSequencerBuffer::GetBlockCapacity(size_t block_index) const { |
- if ((block_index + 1) == blocks_count_) { |
- size_t result = max_buffer_capacity_bytes_ % kBlockSizeBytes; |
- if (result == 0) { // whole block |
- result = kBlockSizeBytes; |
- } |
- return result; |
- } else { |
- return kBlockSizeBytes; |
- } |
-} |
- |
-void QuicStreamSequencerBuffer::UpdateFrameArrivalMap(QuicStreamOffset offset) { |
- // Get the frame before which all frames should be removed. |
- auto next_frame = frame_arrival_time_map_.upper_bound(offset); |
- DCHECK(next_frame != frame_arrival_time_map_.begin()); |
- auto iter = frame_arrival_time_map_.begin(); |
- while (iter != next_frame) { |
- auto erased = *iter; |
- iter = frame_arrival_time_map_.erase(iter); |
- DVLOG(1) << "Removed FrameInfo with offset: " << erased.first |
- << " and length: " << erased.second.length; |
- if (erased.first + erased.second.length > offset) { |
- // If last frame is partially read out, update this FrameInfo and insert |
- // it back. |
- auto updated = std::make_pair( |
- offset, FrameInfo(erased.first + erased.second.length - offset, |
- erased.second.timestamp)); |
- DVLOG(1) << "Inserted FrameInfo with offset: " << updated.first |
- << " and length: " << updated.second.length; |
- frame_arrival_time_map_.insert(updated); |
- } |
- } |
-} |
- |
-string QuicStreamSequencerBuffer::GapsDebugString() { |
- string current_gaps_string; |
- for (const Gap& gap : gaps_) { |
- QuicStreamOffset current_gap_begin = gap.begin_offset; |
- QuicStreamOffset current_gap_end = gap.end_offset; |
- current_gaps_string += RangeDebugString(current_gap_begin, current_gap_end); |
- } |
- return current_gaps_string; |
-} |
- |
-string QuicStreamSequencerBuffer::ReceivedFramesDebugString() { |
- string current_frames_string; |
- for (auto it : frame_arrival_time_map_) { |
- QuicStreamOffset current_frame_begin_offset = it.first; |
- QuicStreamOffset current_frame_end_offset = |
- it.second.length + current_frame_begin_offset; |
- current_frames_string += |
- RangeDebugString(current_frame_begin_offset, current_frame_end_offset); |
- } |
- return current_frames_string; |
-} |
- |
-} // namespace net |