| OLD | NEW |
| 1 // Copyright (c) 2015 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2015 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "net/quic/core/quic_stream_sequencer_buffer.h" | 5 #include "net/quic/core/quic_stream_sequencer_buffer.h" |
| 6 | 6 |
| 7 #include "base/format_macros.h" | 7 #include "base/format_macros.h" |
| 8 #include "base/logging.h" | |
| 9 #include "net/quic/core/quic_flags.h" | 8 #include "net/quic/core/quic_flags.h" |
| 10 #include "net/quic/platform/api/quic_bug_tracker.h" | 9 #include "net/quic/platform/api/quic_bug_tracker.h" |
| 10 #include "net/quic/platform/api/quic_logging.h" |
| 11 #include "net/quic/platform/api/quic_str_cat.h" | 11 #include "net/quic/platform/api/quic_str_cat.h" |
| 12 | 12 |
| 13 using std::string; | 13 using std::string; |
| 14 | 14 |
| 15 namespace net { | 15 namespace net { |
| 16 namespace { | 16 namespace { |
| 17 | 17 |
| 18 // Upper limit of how many gaps allowed in buffer, which ensures a reasonable | 18 // Upper limit of how many gaps allowed in buffer, which ensures a reasonable |
| 19 // number of iterations needed to find the right gap to fill when a frame | 19 // number of iterations needed to find the right gap to fill when a frame |
| 20 // arrives. | 20 // arrives. |
| (...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 72 frame_arrival_time_map_.clear(); | 72 frame_arrival_time_map_.clear(); |
| 73 } | 73 } |
| 74 | 74 |
| 75 bool QuicStreamSequencerBuffer::RetireBlock(size_t idx) { | 75 bool QuicStreamSequencerBuffer::RetireBlock(size_t idx) { |
| 76 if (blocks_[idx] == nullptr) { | 76 if (blocks_[idx] == nullptr) { |
| 77 QUIC_BUG << "Try to retire block twice"; | 77 QUIC_BUG << "Try to retire block twice"; |
| 78 return false; | 78 return false; |
| 79 } | 79 } |
| 80 delete blocks_[idx]; | 80 delete blocks_[idx]; |
| 81 blocks_[idx] = nullptr; | 81 blocks_[idx] = nullptr; |
| 82 DVLOG(1) << "Retired block with index: " << idx; | 82 QUIC_DVLOG(1) << "Retired block with index: " << idx; |
| 83 return true; | 83 return true; |
| 84 } | 84 } |
| 85 | 85 |
| 86 QuicErrorCode QuicStreamSequencerBuffer::OnStreamData( | 86 QuicErrorCode QuicStreamSequencerBuffer::OnStreamData( |
| 87 QuicStreamOffset starting_offset, | 87 QuicStreamOffset starting_offset, |
| 88 base::StringPiece data, | 88 base::StringPiece data, |
| 89 QuicTime timestamp, | 89 QuicTime timestamp, |
| 90 size_t* const bytes_buffered, | 90 size_t* const bytes_buffered, |
| 91 std::string* error_details) { | 91 std::string* error_details) { |
| 92 CHECK_EQ(destruction_indicator_, 123456) << "This object has been destructed"; | 92 CHECK_EQ(destruction_indicator_, 123456) << "This object has been destructed"; |
| (...skipping 13 matching lines...) Expand all Loading... |
| 106 } | 106 } |
| 107 | 107 |
| 108 DCHECK(current_gap != gaps_.end()); | 108 DCHECK(current_gap != gaps_.end()); |
| 109 | 109 |
| 110 // "duplication": might duplicate with data alread filled,but also might | 110 // "duplication": might duplicate with data alread filled,but also might |
| 111 // overlap across different base::StringPiece objects already written. | 111 // overlap across different base::StringPiece objects already written. |
| 112 // In both cases, don't write the data, | 112 // In both cases, don't write the data, |
| 113 // and allow the caller of this method to handle the result. | 113 // and allow the caller of this method to handle the result. |
| 114 if (offset < current_gap->begin_offset && | 114 if (offset < current_gap->begin_offset && |
| 115 offset + size <= current_gap->begin_offset) { | 115 offset + size <= current_gap->begin_offset) { |
| 116 DVLOG(1) << "Duplicated data at offset: " << offset << " length: " << size; | 116 QUIC_DVLOG(1) << "Duplicated data at offset: " << offset |
| 117 << " length: " << size; |
| 117 return QUIC_NO_ERROR; | 118 return QUIC_NO_ERROR; |
| 118 } | 119 } |
| 119 if (offset < current_gap->begin_offset && | 120 if (offset < current_gap->begin_offset && |
| 120 offset + size > current_gap->begin_offset) { | 121 offset + size > current_gap->begin_offset) { |
| 121 // Beginning of new data overlaps data before current gap. | 122 // Beginning of new data overlaps data before current gap. |
| 122 string prefix(data.data(), data.length() < 128 ? data.length() : 128); | 123 string prefix(data.data(), data.length() < 128 ? data.length() : 128); |
| 123 *error_details = | 124 *error_details = |
| 124 QuicStrCat("Beginning of received data overlaps with buffered data.\n", | 125 QuicStrCat("Beginning of received data overlaps with buffered data.\n", |
| 125 "New frame range [", offset, ", ", offset + size, | 126 "New frame range [", offset, ", ", offset + size, |
| 126 ") with first 128 bytes: ", prefix, "\n", | 127 ") with first 128 bytes: ", prefix, "\n", |
| (...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 196 } | 197 } |
| 197 if (blocks_[write_block_num] == nullptr) { | 198 if (blocks_[write_block_num] == nullptr) { |
| 198 // TODO(danzh): Investigate if using a freelist would improve performance. | 199 // TODO(danzh): Investigate if using a freelist would improve performance. |
| 199 // Same as RetireBlock(). | 200 // Same as RetireBlock(). |
| 200 blocks_[write_block_num] = new BufferBlock(); | 201 blocks_[write_block_num] = new BufferBlock(); |
| 201 } | 202 } |
| 202 | 203 |
| 203 const size_t bytes_to_copy = | 204 const size_t bytes_to_copy = |
| 204 std::min<size_t>(bytes_avail, source_remaining); | 205 std::min<size_t>(bytes_avail, source_remaining); |
| 205 char* dest = blocks_[write_block_num]->buffer + write_block_offset; | 206 char* dest = blocks_[write_block_num]->buffer + write_block_offset; |
| 206 DVLOG(1) << "Write at offset: " << offset << " length: " << bytes_to_copy; | 207 QUIC_DVLOG(1) << "Write at offset: " << offset |
| 208 << " length: " << bytes_to_copy; |
| 207 | 209 |
| 208 if (dest == nullptr || source == nullptr) { | 210 if (dest == nullptr || source == nullptr) { |
| 209 *error_details = QuicStrCat( | 211 *error_details = QuicStrCat( |
| 210 "QuicStreamSequencerBuffer error: OnStreamData()" | 212 "QuicStreamSequencerBuffer error: OnStreamData()" |
| 211 " dest == nullptr: ", | 213 " dest == nullptr: ", |
| 212 (dest == nullptr), " source == nullptr: ", (source == nullptr), | 214 (dest == nullptr), " source == nullptr: ", (source == nullptr), |
| 213 " Writing at offset ", offset, " Gaps: ", GapsDebugString(), | 215 " Writing at offset ", offset, " Gaps: ", GapsDebugString(), |
| 214 " Remaining frames: ", ReceivedFramesDebugString(), | 216 " Remaining frames: ", ReceivedFramesDebugString(), |
| 215 " total_bytes_read_ = ", total_bytes_read_); | 217 " total_bytes_read_ = ", total_bytes_read_); |
| 216 return QUIC_STREAM_SEQUENCER_INVALID_STATE; | 218 return QUIC_STREAM_SEQUENCER_INVALID_STATE; |
| (...skipping 124 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 341 size_t start_block_idx = NextBlockToRead(); | 343 size_t start_block_idx = NextBlockToRead(); |
| 342 QuicStreamOffset readable_offset_end = gaps_.front().begin_offset - 1; | 344 QuicStreamOffset readable_offset_end = gaps_.front().begin_offset - 1; |
| 343 DCHECK_GE(readable_offset_end + 1, total_bytes_read_); | 345 DCHECK_GE(readable_offset_end + 1, total_bytes_read_); |
| 344 size_t end_block_offset = GetInBlockOffset(readable_offset_end); | 346 size_t end_block_offset = GetInBlockOffset(readable_offset_end); |
| 345 size_t end_block_idx = GetBlockIndex(readable_offset_end); | 347 size_t end_block_idx = GetBlockIndex(readable_offset_end); |
| 346 | 348 |
| 347 // If readable region is within one block, deal with it seperately. | 349 // If readable region is within one block, deal with it seperately. |
| 348 if (start_block_idx == end_block_idx && ReadOffset() <= end_block_offset) { | 350 if (start_block_idx == end_block_idx && ReadOffset() <= end_block_offset) { |
| 349 iov[0].iov_base = blocks_[start_block_idx]->buffer + ReadOffset(); | 351 iov[0].iov_base = blocks_[start_block_idx]->buffer + ReadOffset(); |
| 350 iov[0].iov_len = ReadableBytes(); | 352 iov[0].iov_len = ReadableBytes(); |
| 351 DVLOG(1) << "Got only a single block with index: " << start_block_idx; | 353 QUIC_DVLOG(1) << "Got only a single block with index: " << start_block_idx; |
| 352 return 1; | 354 return 1; |
| 353 } | 355 } |
| 354 | 356 |
| 355 // Get first block | 357 // Get first block |
| 356 iov[0].iov_base = blocks_[start_block_idx]->buffer + ReadOffset(); | 358 iov[0].iov_base = blocks_[start_block_idx]->buffer + ReadOffset(); |
| 357 iov[0].iov_len = GetBlockCapacity(start_block_idx) - ReadOffset(); | 359 iov[0].iov_len = GetBlockCapacity(start_block_idx) - ReadOffset(); |
| 358 DVLOG(1) << "Got first block " << start_block_idx << " with len " | 360 QUIC_DVLOG(1) << "Got first block " << start_block_idx << " with len " |
| 359 << iov[0].iov_len; | 361 << iov[0].iov_len; |
| 360 DCHECK_GT(readable_offset_end + 1, total_bytes_read_ + iov[0].iov_len) | 362 DCHECK_GT(readable_offset_end + 1, total_bytes_read_ + iov[0].iov_len) |
| 361 << "there should be more available data"; | 363 << "there should be more available data"; |
| 362 | 364 |
| 363 // Get readable regions of the rest blocks till either 2nd to last block | 365 // Get readable regions of the rest blocks till either 2nd to last block |
| 364 // before gap is met or |iov| is filled. For these blocks, one whole block is | 366 // before gap is met or |iov| is filled. For these blocks, one whole block is |
| 365 // a region. | 367 // a region. |
| 366 int iov_used = 1; | 368 int iov_used = 1; |
| 367 size_t block_idx = (start_block_idx + iov_used) % blocks_count_; | 369 size_t block_idx = (start_block_idx + iov_used) % blocks_count_; |
| 368 while (block_idx != end_block_idx && iov_used < iov_count) { | 370 while (block_idx != end_block_idx && iov_used < iov_count) { |
| 369 DCHECK_NE(static_cast<BufferBlock*>(nullptr), blocks_[block_idx]); | 371 DCHECK_NE(static_cast<BufferBlock*>(nullptr), blocks_[block_idx]); |
| 370 iov[iov_used].iov_base = blocks_[block_idx]->buffer; | 372 iov[iov_used].iov_base = blocks_[block_idx]->buffer; |
| 371 iov[iov_used].iov_len = GetBlockCapacity(block_idx); | 373 iov[iov_used].iov_len = GetBlockCapacity(block_idx); |
| 372 DVLOG(1) << "Got block with index: " << block_idx; | 374 QUIC_DVLOG(1) << "Got block with index: " << block_idx; |
| 373 ++iov_used; | 375 ++iov_used; |
| 374 block_idx = (start_block_idx + iov_used) % blocks_count_; | 376 block_idx = (start_block_idx + iov_used) % blocks_count_; |
| 375 } | 377 } |
| 376 | 378 |
| 377 // Deal with last block if |iov| can hold more. | 379 // Deal with last block if |iov| can hold more. |
| 378 if (iov_used < iov_count) { | 380 if (iov_used < iov_count) { |
| 379 DCHECK_NE(static_cast<BufferBlock*>(nullptr), blocks_[block_idx]); | 381 DCHECK_NE(static_cast<BufferBlock*>(nullptr), blocks_[block_idx]); |
| 380 iov[iov_used].iov_base = blocks_[end_block_idx]->buffer; | 382 iov[iov_used].iov_base = blocks_[end_block_idx]->buffer; |
| 381 iov[iov_used].iov_len = end_block_offset + 1; | 383 iov[iov_used].iov_len = end_block_offset + 1; |
| 382 DVLOG(1) << "Got last block with index: " << end_block_idx; | 384 QUIC_DVLOG(1) << "Got last block with index: " << end_block_idx; |
| 383 ++iov_used; | 385 ++iov_used; |
| 384 } | 386 } |
| 385 return iov_used; | 387 return iov_used; |
| 386 } | 388 } |
| 387 | 389 |
| 388 bool QuicStreamSequencerBuffer::GetReadableRegion(iovec* iov, | 390 bool QuicStreamSequencerBuffer::GetReadableRegion(iovec* iov, |
| 389 QuicTime* timestamp) const { | 391 QuicTime* timestamp) const { |
| 390 CHECK_EQ(destruction_indicator_, 123456) << "This object has been destructed"; | 392 CHECK_EQ(destruction_indicator_, 123456) << "This object has been destructed"; |
| 391 | 393 |
| 392 if (ReadableBytes() == 0) { | 394 if (ReadableBytes() == 0) { |
| 393 iov[0].iov_base = nullptr; | 395 iov[0].iov_base = nullptr; |
| 394 iov[0].iov_len = 0; | 396 iov[0].iov_len = 0; |
| 395 return false; | 397 return false; |
| 396 } | 398 } |
| 397 | 399 |
| 398 size_t start_block_idx = NextBlockToRead(); | 400 size_t start_block_idx = NextBlockToRead(); |
| 399 iov->iov_base = blocks_[start_block_idx]->buffer + ReadOffset(); | 401 iov->iov_base = blocks_[start_block_idx]->buffer + ReadOffset(); |
| 400 size_t readable_bytes_in_block = std::min<size_t>( | 402 size_t readable_bytes_in_block = std::min<size_t>( |
| 401 GetBlockCapacity(start_block_idx) - ReadOffset(), ReadableBytes()); | 403 GetBlockCapacity(start_block_idx) - ReadOffset(), ReadableBytes()); |
| 402 size_t region_len = 0; | 404 size_t region_len = 0; |
| 403 auto iter = frame_arrival_time_map_.begin(); | 405 auto iter = frame_arrival_time_map_.begin(); |
| 404 *timestamp = iter->second.timestamp; | 406 *timestamp = iter->second.timestamp; |
| 405 DVLOG(1) << "Readable bytes in block: " << readable_bytes_in_block; | 407 QUIC_DVLOG(1) << "Readable bytes in block: " << readable_bytes_in_block; |
| 406 for (; iter != frame_arrival_time_map_.end() && | 408 for (; iter != frame_arrival_time_map_.end() && |
| 407 region_len + iter->second.length <= readable_bytes_in_block; | 409 region_len + iter->second.length <= readable_bytes_in_block; |
| 408 ++iter) { | 410 ++iter) { |
| 409 if (iter->second.timestamp != *timestamp) { | 411 if (iter->second.timestamp != *timestamp) { |
| 410 // If reaches a frame arrive at another timestamp, stop expanding current | 412 // If reaches a frame arrive at another timestamp, stop expanding current |
| 411 // region. | 413 // region. |
| 412 DVLOG(1) << "Meet frame with different timestamp."; | 414 QUIC_DVLOG(1) << "Meet frame with different timestamp."; |
| 413 break; | 415 break; |
| 414 } | 416 } |
| 415 region_len += iter->second.length; | 417 region_len += iter->second.length; |
| 416 DVLOG(1) << "Added bytes to region: " << iter->second.length; | 418 QUIC_DVLOG(1) << "Added bytes to region: " << iter->second.length; |
| 417 } | 419 } |
| 418 if (iter == frame_arrival_time_map_.end() || | 420 if (iter == frame_arrival_time_map_.end() || |
| 419 iter->second.timestamp == *timestamp) { | 421 iter->second.timestamp == *timestamp) { |
| 420 // If encountered the end of readable bytes before reaching a different | 422 // If encountered the end of readable bytes before reaching a different |
| 421 // timestamp. | 423 // timestamp. |
| 422 DVLOG(1) << "Got all readable bytes in first block."; | 424 QUIC_DVLOG(1) << "Got all readable bytes in first block."; |
| 423 region_len = readable_bytes_in_block; | 425 region_len = readable_bytes_in_block; |
| 424 } | 426 } |
| 425 iov->iov_len = region_len; | 427 iov->iov_len = region_len; |
| 426 return true; | 428 return true; |
| 427 } | 429 } |
| 428 | 430 |
| 429 bool QuicStreamSequencerBuffer::MarkConsumed(size_t bytes_used) { | 431 bool QuicStreamSequencerBuffer::MarkConsumed(size_t bytes_used) { |
| 430 CHECK_EQ(destruction_indicator_, 123456) << "This object has been destructed"; | 432 CHECK_EQ(destruction_indicator_, 123456) << "This object has been destructed"; |
| 431 | 433 |
| 432 if (bytes_used > ReadableBytes()) { | 434 if (bytes_used > ReadableBytes()) { |
| (...skipping 118 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 551 } | 553 } |
| 552 | 554 |
| 553 void QuicStreamSequencerBuffer::UpdateFrameArrivalMap(QuicStreamOffset offset) { | 555 void QuicStreamSequencerBuffer::UpdateFrameArrivalMap(QuicStreamOffset offset) { |
| 554 // Get the frame before which all frames should be removed. | 556 // Get the frame before which all frames should be removed. |
| 555 auto next_frame = frame_arrival_time_map_.upper_bound(offset); | 557 auto next_frame = frame_arrival_time_map_.upper_bound(offset); |
| 556 DCHECK(next_frame != frame_arrival_time_map_.begin()); | 558 DCHECK(next_frame != frame_arrival_time_map_.begin()); |
| 557 auto iter = frame_arrival_time_map_.begin(); | 559 auto iter = frame_arrival_time_map_.begin(); |
| 558 while (iter != next_frame) { | 560 while (iter != next_frame) { |
| 559 auto erased = *iter; | 561 auto erased = *iter; |
| 560 iter = frame_arrival_time_map_.erase(iter); | 562 iter = frame_arrival_time_map_.erase(iter); |
| 561 DVLOG(1) << "Removed FrameInfo with offset: " << erased.first | 563 QUIC_DVLOG(1) << "Removed FrameInfo with offset: " << erased.first |
| 562 << " and length: " << erased.second.length; | 564 << " and length: " << erased.second.length; |
| 563 if (erased.first + erased.second.length > offset) { | 565 if (erased.first + erased.second.length > offset) { |
| 564 // If last frame is partially read out, update this FrameInfo and insert | 566 // If last frame is partially read out, update this FrameInfo and insert |
| 565 // it back. | 567 // it back. |
| 566 auto updated = std::make_pair( | 568 auto updated = std::make_pair( |
| 567 offset, FrameInfo(erased.first + erased.second.length - offset, | 569 offset, FrameInfo(erased.first + erased.second.length - offset, |
| 568 erased.second.timestamp)); | 570 erased.second.timestamp)); |
| 569 DVLOG(1) << "Inserted FrameInfo with offset: " << updated.first | 571 QUIC_DVLOG(1) << "Inserted FrameInfo with offset: " << updated.first |
| 570 << " and length: " << updated.second.length; | 572 << " and length: " << updated.second.length; |
| 571 frame_arrival_time_map_.insert(updated); | 573 frame_arrival_time_map_.insert(updated); |
| 572 } | 574 } |
| 573 } | 575 } |
| 574 } | 576 } |
| 575 | 577 |
| 576 string QuicStreamSequencerBuffer::GapsDebugString() { | 578 string QuicStreamSequencerBuffer::GapsDebugString() { |
| 577 string current_gaps_string; | 579 string current_gaps_string; |
| 578 for (const Gap& gap : gaps_) { | 580 for (const Gap& gap : gaps_) { |
| 579 QuicStreamOffset current_gap_begin = gap.begin_offset; | 581 QuicStreamOffset current_gap_begin = gap.begin_offset; |
| 580 QuicStreamOffset current_gap_end = gap.end_offset; | 582 QuicStreamOffset current_gap_end = gap.end_offset; |
| (...skipping 10 matching lines...) Expand all Loading... |
| 591 QuicStreamOffset current_frame_end_offset = | 593 QuicStreamOffset current_frame_end_offset = |
| 592 it.second.length + current_frame_begin_offset; | 594 it.second.length + current_frame_begin_offset; |
| 593 current_frames_string.append(QuicStrCat( | 595 current_frames_string.append(QuicStrCat( |
| 594 "[", current_frame_begin_offset, ", ", current_frame_end_offset, | 596 "[", current_frame_begin_offset, ", ", current_frame_end_offset, |
| 595 ") receiving time ", it.second.timestamp.ToDebuggingValue())); | 597 ") receiving time ", it.second.timestamp.ToDebuggingValue())); |
| 596 } | 598 } |
| 597 return current_frames_string; | 599 return current_frames_string; |
| 598 } | 600 } |
| 599 | 601 |
| 600 } // namespace net | 602 } // namespace net |
| OLD | NEW |