15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/quic/quic_stream_sequencer.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <limits> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 11c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch#include "base/metrics/sparse_histogram.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/quic/reliable_quic_stream.h" 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 14f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)using std::make_pair; 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::min; 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::numeric_limits; 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace net { 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)QuicStreamSequencer::QuicStreamSequencer(ReliableQuicStream* quic_stream) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : stream_(quic_stream), 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_bytes_consumed_(0), 235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) close_offset_(numeric_limits<QuicStreamOffset>::max()), 245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) blocked_(false), 25c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch num_bytes_buffered_(0), 26c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch num_frames_received_(0), 27c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch num_duplicate_frames_received_(0) { 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)QuicStreamSequencer::~QuicStreamSequencer() { 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void QuicStreamSequencer::OnStreamFrame(const QuicStreamFrame& frame) { 34c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch ++num_frames_received_; 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (IsDuplicate(frame)) { 36c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch ++num_duplicate_frames_received_; 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Silently ignore duplicates. 385f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return; 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 41f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if (FrameOverlapsBufferedData(frame)) { 42f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) stream_->CloseConnectionWithDetails( 43f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) QUIC_INVALID_STREAM_FRAME, "Stream frame overlaps with buffered data."); 445f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return; 45f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 46f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuicStreamOffset byte_offset = frame.offset; 48f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) size_t data_len = frame.data.TotalBufferSize(); 49d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) if (data_len == 0 && !frame.fin) { 50d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) // Stream frames must have data or a fin flag. 511e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) stream_->CloseConnectionWithDetails(QUIC_INVALID_STREAM_FRAME, 521e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) "Empty stream frame without FIN set."); 535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return; 54d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) } 55d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) 56d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) if (frame.fin) { 57f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) CloseStreamAtOffset(frame.offset + data_len); 58d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) if (data_len == 0) { 595f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return; 60d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) } 61558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch } 62558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch 63f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) IOVector data; 64f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) data.AppendIovec(frame.data.iovec(), frame.data.Size()); 655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // If the frame has arrived in-order then we can process it immediately, only 675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // buffering if the stream is unable to process it. 685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!blocked_ && byte_offset == num_bytes_consumed_) { 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DVLOG(1) << "Processing byte offset " << byte_offset; 70f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) size_t bytes_consumed = 0; 71f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (size_t i = 0; i < data.Size(); ++i) { 72f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) bytes_consumed += stream_->ProcessRawData( 73f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) static_cast<char*>(data.iovec()[i].iov_base), 74f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) data.iovec()[i].iov_len); 75f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_bytes_consumed_ += bytes_consumed; 77010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) stream_->AddBytesConsumed(bytes_consumed); 78e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MaybeCloseStream()) { 805f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (bytes_consumed > data_len) { 83a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) stream_->Reset(QUIC_ERROR_PROCESSING_STREAM); 845f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (bytes_consumed == data_len) { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FlushBufferedFrames(); 875f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return; // it's safe to ack this frame. 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Set ourselves up to buffer what's left. 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) data_len -= bytes_consumed; 91f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) data.Consume(bytes_consumed); 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) byte_offset += bytes_consumed; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Buffer any remaining data to be consumed by the stream when ready. 97f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (size_t i = 0; i < data.Size(); ++i) { 98f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DVLOG(1) << "Buffering stream data at offset " << byte_offset; 995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const iovec& iov = data.iovec()[i]; 100f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) buffered_frames_.insert(make_pair( 1015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) byte_offset, string(static_cast<char*>(iov.iov_base), iov.iov_len))); 1025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) byte_offset += iov.iov_len; 1035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) num_bytes_buffered_ += iov.iov_len; 104f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 1055f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1087d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)void QuicStreamSequencer::CloseStreamAtOffset(QuicStreamOffset offset) { 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const QuicStreamOffset kMaxOffset = numeric_limits<QuicStreamOffset>::max(); 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we have a scheduled termination or close, any new offset should match 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // it. 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (close_offset_ != kMaxOffset && offset != close_offset_) { 114a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) stream_->Reset(QUIC_MULTIPLE_TERMINATION_OFFSETS); 1157d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) return; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) close_offset_ = offset; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MaybeCloseStream(); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool QuicStreamSequencer::MaybeCloseStream() { 1245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!blocked_ && IsClosed()) { 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DVLOG(1) << "Passing up termination, as we've processed " 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << num_bytes_consumed_ << " of " << close_offset_ 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << " bytes."; 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Technically it's an error if num_bytes_consumed isn't exactly 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // equal, but error handling seems silly at this point. 130a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) stream_->OnFinRead(); 131f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) buffered_frames_.clear(); 1325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) num_bytes_buffered_ = 0; 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 138868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)int QuicStreamSequencer::GetReadableRegions(iovec* iov, size_t iov_len) { 1395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(!blocked_); 140f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) FrameMap::iterator it = buffered_frames_.begin(); 141868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) size_t index = 0; 142868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) QuicStreamOffset offset = num_bytes_consumed_; 143f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) while (it != buffered_frames_.end() && index < iov_len) { 144b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) if (it->first != offset) return index; 145b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 146b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) iov[index].iov_base = static_cast<void*>( 147b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) const_cast<char*>(it->second.data())); 148b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) iov[index].iov_len = it->second.size(); 149b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) offset += it->second.size(); 150b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 151b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) ++index; 152b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) ++it; 153b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } 154b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) return index; 155b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)} 156b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 157868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)int QuicStreamSequencer::Readv(const struct iovec* iov, size_t iov_len) { 1585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(!blocked_); 159f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) FrameMap::iterator it = buffered_frames_.begin(); 160868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) size_t iov_index = 0; 161b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) size_t iov_offset = 0; 162b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) size_t frame_offset = 0; 163b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) size_t initial_bytes_consumed = num_bytes_consumed_; 164b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 165b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) while (iov_index < iov_len && 166f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) it != buffered_frames_.end() && 167b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) it->first == num_bytes_consumed_) { 168b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) int bytes_to_read = min(iov[iov_index].iov_len - iov_offset, 169b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) it->second.size() - frame_offset); 170b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 171b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) char* iov_ptr = static_cast<char*>(iov[iov_index].iov_base) + iov_offset; 172b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) memcpy(iov_ptr, 173b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) it->second.data() + frame_offset, bytes_to_read); 174b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) frame_offset += bytes_to_read; 175b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) iov_offset += bytes_to_read; 176b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 177b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) if (iov[iov_index].iov_len == iov_offset) { 178b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) // We've filled this buffer. 179b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) iov_offset = 0; 180b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) ++iov_index; 181b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } 182b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) if (it->second.size() == frame_offset) { 183b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) // We've copied this whole frame 1845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) RecordBytesConsumed(it->second.size()); 185f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) buffered_frames_.erase(it); 186f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) it = buffered_frames_.begin(); 187b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) frame_offset = 0; 188b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } 189b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } 190b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) // We've finished copying. If we have a partial frame, update it. 191b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) if (frame_offset != 0) { 192f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) buffered_frames_.insert( 193f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) make_pair(it->first + frame_offset, it->second.substr(frame_offset))); 194f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) buffered_frames_.erase(buffered_frames_.begin()); 1955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) RecordBytesConsumed(frame_offset); 196b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) } 197b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) return num_bytes_consumed_ - initial_bytes_consumed; 198b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)} 199b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool QuicStreamSequencer::HasBytesToRead() const { 201f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) FrameMap::const_iterator it = buffered_frames_.begin(); 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 203f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) return it != buffered_frames_.end() && it->first == num_bytes_consumed_; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 206a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)bool QuicStreamSequencer::IsClosed() const { 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return num_bytes_consumed_ >= close_offset_; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 210f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)bool QuicStreamSequencer::FrameOverlapsBufferedData( 211f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) const QuicStreamFrame& frame) const { 212f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if (buffered_frames_.empty()) { 213f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) return false; 214f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 215f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 216f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) FrameMap::const_iterator next_frame = 217f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) buffered_frames_.lower_bound(frame.offset); 218f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Duplicate frames should have been dropped in IsDuplicate. 219f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) DCHECK(next_frame == buffered_frames_.end() || 220f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) next_frame->first != frame.offset); 221f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 222f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // If there is a buffered frame with a higher starting offset, then we check 223f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // to see if the new frame runs into the higher frame. 224f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if (next_frame != buffered_frames_.end() && 225f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) (frame.offset + frame.data.TotalBufferSize()) > next_frame->first) { 226f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) DVLOG(1) << "New frame overlaps next frame: " << frame.offset << " + " 227f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) << frame.data.TotalBufferSize() << " > " << next_frame->first; 228f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) return true; 229f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 230f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 231f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // If there is a buffered frame with a lower starting offset, then we check 232f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // to see if the buffered frame runs into the new frame. 233f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if (next_frame != buffered_frames_.begin()) { 234f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) FrameMap::const_iterator preceeding_frame = --next_frame; 235f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) QuicStreamOffset offset = preceeding_frame->first; 236f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) uint64 data_length = preceeding_frame->second.length(); 237f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if ((offset + data_length) > frame.offset) { 238f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) DVLOG(1) << "Preceeding frame overlaps new frame: " << offset << " + " 239f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) << data_length << " > " << frame.offset; 240f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) return true; 241f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 242f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 243f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) return false; 244f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} 245f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 2462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)bool QuicStreamSequencer::IsDuplicate(const QuicStreamFrame& frame) const { 2472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // A frame is duplicate if the frame offset is smaller than our bytes consumed 2482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // or we have stored the frame in our map. 2492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // TODO(pwestin): Is it possible that a new frame contain more data even if 2502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // the offset is the same? 2512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return frame.offset < num_bytes_consumed_ || 252f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) buffered_frames_.find(frame.offset) != buffered_frames_.end(); 2532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void QuicStreamSequencer::SetBlockedUntilFlush() { 2565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) blocked_ = true; 2575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void QuicStreamSequencer::FlushBufferedFrames() { 2605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) blocked_ = false; 261f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) FrameMap::iterator it = buffered_frames_.find(num_bytes_consumed_); 262f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) while (it != buffered_frames_.end()) { 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DVLOG(1) << "Flushing buffered packet at offset " << it->first; 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) string* data = &it->second; 265b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) size_t bytes_consumed = stream_->ProcessRawData(data->c_str(), 266b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles) data->size()); 2675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) RecordBytesConsumed(bytes_consumed); 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MaybeCloseStream()) { 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (bytes_consumed > data->size()) { 272a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) stream_->Reset(QUIC_ERROR_PROCESSING_STREAM); // Programming error 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (bytes_consumed == data->size()) { 275f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) buffered_frames_.erase(it); 276f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) it = buffered_frames_.find(num_bytes_consumed_); 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) string new_data = it->second.substr(bytes_consumed); 279f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) buffered_frames_.erase(it); 280f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) buffered_frames_.insert(make_pair(num_bytes_consumed_, new_data)); 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) MaybeCloseStream(); 2855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void QuicStreamSequencer::RecordBytesConsumed(size_t bytes_consumed) { 2885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) num_bytes_consumed_ += bytes_consumed; 2895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) num_bytes_buffered_ -= bytes_consumed; 290e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 291010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) stream_->AddBytesConsumed(bytes_consumed); 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace net 295