| 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 #include "net/quic/core/quic_stream_sequencer_buffer.h" | 4 #include "net/quic/core/quic_stream_sequencer_buffer.h" |
| 5 | 5 |
| 6 #include <algorithm> | 6 #include <algorithm> |
| 7 #include <limits> | 7 #include <limits> |
| 8 #include <map> | 8 #include <map> |
| 9 #include <string> | 9 #include <string> |
| 10 #include <utility> | 10 #include <utility> |
| 11 | 11 |
| 12 #include "base/logging.h" | |
| 13 #include "base/macros.h" | 12 #include "base/macros.h" |
| 13 #include "net/quic/platform/api/quic_logging.h" |
| 14 #include "net/quic/platform/api/quic_str_cat.h" | 14 #include "net/quic/platform/api/quic_str_cat.h" |
| 15 #include "net/quic/test_tools/mock_clock.h" | 15 #include "net/quic/test_tools/mock_clock.h" |
| 16 #include "net/quic/test_tools/quic_stream_sequencer_buffer_peer.h" | 16 #include "net/quic/test_tools/quic_stream_sequencer_buffer_peer.h" |
| 17 #include "net/quic/test_tools/quic_test_utils.h" | 17 #include "net/quic/test_tools/quic_test_utils.h" |
| 18 #include "net/test/gtest_util.h" | 18 #include "net/test/gtest_util.h" |
| 19 #include "testing/gmock/include/gmock/gmock.h" | 19 #include "testing/gmock/include/gmock/gmock.h" |
| 20 #include "testing/gmock_mutant.h" | 20 #include "testing/gmock_mutant.h" |
| 21 #include "testing/gtest/include/gtest/gtest.h" | 21 #include "testing/gtest/include/gtest/gtest.h" |
| 22 | 22 |
| 23 using std::string; | 23 using std::string; |
| (...skipping 292 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 316 QuicTime t2 = clock_.ApproximateNow(); | 316 QuicTime t2 = clock_.ApproximateNow(); |
| 317 // Write something into [0, 100). | 317 // Write something into [0, 100). |
| 318 buffer_->OnStreamData(0, source, t2, &written, &error_details_); | 318 buffer_->OnStreamData(0, source, t2, &written, &error_details_); |
| 319 EXPECT_TRUE(buffer_->HasBytesToRead()); | 319 EXPECT_TRUE(buffer_->HasBytesToRead()); |
| 320 EXPECT_EQ(2u, helper_->frame_arrival_time_map()->size()); | 320 EXPECT_EQ(2u, helper_->frame_arrival_time_map()->size()); |
| 321 // Read into a iovec array with total capacity of 120 bytes. | 321 // Read into a iovec array with total capacity of 120 bytes. |
| 322 char dest[120]; | 322 char dest[120]; |
| 323 iovec iovecs[3]{iovec{dest, 40}, iovec{dest + 40, 40}, iovec{dest + 80, 40}}; | 323 iovec iovecs[3]{iovec{dest, 40}, iovec{dest + 40, 40}, iovec{dest + 80, 40}}; |
| 324 size_t read; | 324 size_t read; |
| 325 EXPECT_EQ(QUIC_NO_ERROR, buffer_->Readv(iovecs, 3, &read, &error_details_)); | 325 EXPECT_EQ(QUIC_NO_ERROR, buffer_->Readv(iovecs, 3, &read, &error_details_)); |
| 326 LOG(ERROR) << error_details_; | 326 QUIC_LOG(ERROR) << error_details_; |
| 327 EXPECT_EQ(100u, read); | 327 EXPECT_EQ(100u, read); |
| 328 EXPECT_EQ(100u, buffer_->BytesConsumed()); | 328 EXPECT_EQ(100u, buffer_->BytesConsumed()); |
| 329 EXPECT_EQ(source, string(dest, read)); | 329 EXPECT_EQ(source, string(dest, read)); |
| 330 EXPECT_EQ(1u, helper_->frame_arrival_time_map()->size()); | 330 EXPECT_EQ(1u, helper_->frame_arrival_time_map()->size()); |
| 331 // The first block should be released as its data has been read out. | 331 // The first block should be released as its data has been read out. |
| 332 EXPECT_EQ(nullptr, helper_->GetBlock(0)); | 332 EXPECT_EQ(nullptr, helper_->GetBlock(0)); |
| 333 EXPECT_TRUE(helper_->CheckBufferInvariants()); | 333 EXPECT_TRUE(helper_->CheckBufferInvariants()); |
| 334 } | 334 } |
| 335 | 335 |
| 336 TEST_F(QuicStreamSequencerBufferTest, ReadvAcrossBlocks) { | 336 TEST_F(QuicStreamSequencerBufferTest, ReadvAcrossBlocks) { |
| (...skipping 477 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 814 void SetUp() override { | 814 void SetUp() override { |
| 815 // Test against a larger capacity then above tests. Also make sure the last | 815 // Test against a larger capacity then above tests. Also make sure the last |
| 816 // block is partially available to use. | 816 // block is partially available to use. |
| 817 max_capacity_bytes_ = 6.25 * kBlockSizeBytes; | 817 max_capacity_bytes_ = 6.25 * kBlockSizeBytes; |
| 818 // Stream to be buffered should be larger than the capacity to test wrap | 818 // Stream to be buffered should be larger than the capacity to test wrap |
| 819 // around. | 819 // around. |
| 820 bytes_to_buffer_ = 2 * max_capacity_bytes_; | 820 bytes_to_buffer_ = 2 * max_capacity_bytes_; |
| 821 Initialize(); | 821 Initialize(); |
| 822 | 822 |
| 823 uint64_t seed = QuicRandom::GetInstance()->RandUint64(); | 823 uint64_t seed = QuicRandom::GetInstance()->RandUint64(); |
| 824 VLOG(1) << "**** The current seed is " << seed << " ****"; | 824 QUIC_LOG(INFO) << "**** The current seed is " << seed << " ****"; |
| 825 rng_.set_seed(seed); | 825 rng_.set_seed(seed); |
| 826 } | 826 } |
| 827 | 827 |
| 828 // Create an out-of-order source stream with given size to populate | 828 // Create an out-of-order source stream with given size to populate |
| 829 // shuffled_buf_. | 829 // shuffled_buf_. |
| 830 void CreateSourceAndShuffle(size_t max_chunk_size_bytes) { | 830 void CreateSourceAndShuffle(size_t max_chunk_size_bytes) { |
| 831 max_chunk_size_bytes_ = max_chunk_size_bytes; | 831 max_chunk_size_bytes_ = max_chunk_size_bytes; |
| 832 std::unique_ptr<OffsetSizePair[]> chopped_stream( | 832 std::unique_ptr<OffsetSizePair[]> chopped_stream( |
| 833 new OffsetSizePair[bytes_to_buffer_]); | 833 new OffsetSizePair[bytes_to_buffer_]); |
| 834 | 834 |
| (...skipping 10 matching lines...) Expand all Loading... |
| 845 start_chopping_offset += chunk_size; | 845 start_chopping_offset += chunk_size; |
| 846 ++iterations; | 846 ++iterations; |
| 847 } | 847 } |
| 848 DCHECK(start_chopping_offset == bytes_to_buffer_); | 848 DCHECK(start_chopping_offset == bytes_to_buffer_); |
| 849 size_t chunk_num = iterations; | 849 size_t chunk_num = iterations; |
| 850 | 850 |
| 851 // Randomly change the sequence of in-ordered OffsetSizePairs to make a | 851 // Randomly change the sequence of in-ordered OffsetSizePairs to make a |
| 852 // out-of-order array of OffsetSizePairs. | 852 // out-of-order array of OffsetSizePairs. |
| 853 for (int i = chunk_num - 1; i >= 0; --i) { | 853 for (int i = chunk_num - 1; i >= 0; --i) { |
| 854 size_t random_idx = rng_.RandUint64() % (i + 1); | 854 size_t random_idx = rng_.RandUint64() % (i + 1); |
| 855 DVLOG(1) << "chunk offset " << chopped_stream[random_idx].first | 855 QUIC_DVLOG(1) << "chunk offset " << chopped_stream[random_idx].first |
| 856 << " size " << chopped_stream[random_idx].second; | 856 << " size " << chopped_stream[random_idx].second; |
| 857 shuffled_buf_.push_front(chopped_stream[random_idx]); | 857 shuffled_buf_.push_front(chopped_stream[random_idx]); |
| 858 chopped_stream[random_idx] = chopped_stream[i]; | 858 chopped_stream[random_idx] = chopped_stream[i]; |
| 859 } | 859 } |
| 860 } | 860 } |
| 861 | 861 |
| 862 // Write the currently first chunk of data in the out-of-order stream into | 862 // Write the currently first chunk of data in the out-of-order stream into |
| 863 // QuicStreamSequencerBuffer. If current chuck cannot be written into buffer | 863 // QuicStreamSequencerBuffer. If current chuck cannot be written into buffer |
| 864 // because it goes beyond current capacity, move it to the end of | 864 // because it goes beyond current capacity, move it to the end of |
| 865 // shuffled_buf_ and write it later. | 865 // shuffled_buf_ and write it later. |
| 866 void WriteNextChunkToBuffer() { | 866 void WriteNextChunkToBuffer() { |
| (...skipping 10 matching lines...) Expand all Loading... |
| 877 buffer_->OnStreamData(offset, string_piece_w, clock_.ApproximateNow(), | 877 buffer_->OnStreamData(offset, string_piece_w, clock_.ApproximateNow(), |
| 878 &written, &error_details_); | 878 &written, &error_details_); |
| 879 if (result == QUIC_NO_ERROR) { | 879 if (result == QUIC_NO_ERROR) { |
| 880 shuffled_buf_.pop_front(); | 880 shuffled_buf_.pop_front(); |
| 881 total_bytes_written_ += num_to_write; | 881 total_bytes_written_ += num_to_write; |
| 882 } else { | 882 } else { |
| 883 // This chunk offset exceeds window size. | 883 // This chunk offset exceeds window size. |
| 884 shuffled_buf_.push_back(chunk); | 884 shuffled_buf_.push_back(chunk); |
| 885 shuffled_buf_.pop_front(); | 885 shuffled_buf_.pop_front(); |
| 886 } | 886 } |
| 887 DVLOG(1) << " write at offset: " << offset | 887 QUIC_DVLOG(1) << " write at offset: " << offset |
| 888 << " len to write: " << num_to_write << " write result: " << result | 888 << " len to write: " << num_to_write |
| 889 << " left over: " << shuffled_buf_.size(); | 889 << " write result: " << result |
| 890 << " left over: " << shuffled_buf_.size(); |
| 890 } | 891 } |
| 891 | 892 |
| 892 protected: | 893 protected: |
| 893 std::list<OffsetSizePair> shuffled_buf_; | 894 std::list<OffsetSizePair> shuffled_buf_; |
| 894 size_t max_chunk_size_bytes_; | 895 size_t max_chunk_size_bytes_; |
| 895 QuicStreamOffset bytes_to_buffer_; | 896 QuicStreamOffset bytes_to_buffer_; |
| 896 size_t total_bytes_written_ = 0; | 897 size_t total_bytes_written_ = 0; |
| 897 size_t total_bytes_read_ = 0; | 898 size_t total_bytes_read_ = 0; |
| 898 SimpleRandom rng_; | 899 SimpleRandom rng_; |
| 899 }; | 900 }; |
| 900 | 901 |
| 901 TEST_F(QuicStreamSequencerBufferRandomIOTest, RandomWriteAndReadv) { | 902 TEST_F(QuicStreamSequencerBufferRandomIOTest, RandomWriteAndReadv) { |
| 902 // Set kMaxReadSize larger than kBlockSizeBytes to test both small and large | 903 // Set kMaxReadSize larger than kBlockSizeBytes to test both small and large |
| 903 // read. | 904 // read. |
| 904 const size_t kMaxReadSize = kBlockSizeBytes * 2; | 905 const size_t kMaxReadSize = kBlockSizeBytes * 2; |
| 905 // kNumReads is larger than 1 to test how multiple read destinations work. | 906 // kNumReads is larger than 1 to test how multiple read destinations work. |
| 906 const size_t kNumReads = 2; | 907 const size_t kNumReads = 2; |
| 907 // Since write and read operation have equal possibility to be called. Bytes | 908 // Since write and read operation have equal possibility to be called. Bytes |
| 908 // to be written into and read out of should roughly the same. | 909 // to be written into and read out of should roughly the same. |
| 909 const size_t kMaxWriteSize = kNumReads * kMaxReadSize; | 910 const size_t kMaxWriteSize = kNumReads * kMaxReadSize; |
| 910 size_t iterations = 0; | 911 size_t iterations = 0; |
| 911 | 912 |
| 912 CreateSourceAndShuffle(kMaxWriteSize); | 913 CreateSourceAndShuffle(kMaxWriteSize); |
| 913 | 914 |
| 914 while ((!shuffled_buf_.empty() || total_bytes_read_ < bytes_to_buffer_) && | 915 while ((!shuffled_buf_.empty() || total_bytes_read_ < bytes_to_buffer_) && |
| 915 iterations <= 2 * bytes_to_buffer_) { | 916 iterations <= 2 * bytes_to_buffer_) { |
| 916 uint8_t next_action = | 917 uint8_t next_action = |
| 917 shuffled_buf_.empty() ? uint8_t{1} : rng_.RandUint64() % 2; | 918 shuffled_buf_.empty() ? uint8_t{1} : rng_.RandUint64() % 2; |
| 918 DVLOG(1) << "iteration: " << iterations; | 919 QUIC_DVLOG(1) << "iteration: " << iterations; |
| 919 switch (next_action) { | 920 switch (next_action) { |
| 920 case 0: { // write | 921 case 0: { // write |
| 921 WriteNextChunkToBuffer(); | 922 WriteNextChunkToBuffer(); |
| 922 ASSERT_TRUE(helper_->CheckBufferInvariants()); | 923 ASSERT_TRUE(helper_->CheckBufferInvariants()); |
| 923 break; | 924 break; |
| 924 } | 925 } |
| 925 case 1: { // readv | 926 case 1: { // readv |
| 926 std::unique_ptr<char[][kMaxReadSize]> read_buf{ | 927 std::unique_ptr<char[][kMaxReadSize]> read_buf{ |
| 927 new char[kNumReads][kMaxReadSize]}; | 928 new char[kNumReads][kMaxReadSize]}; |
| 928 iovec dest_iov[kNumReads]; | 929 iovec dest_iov[kNumReads]; |
| 929 size_t num_to_read = 0; | 930 size_t num_to_read = 0; |
| 930 for (size_t i = 0; i < kNumReads; ++i) { | 931 for (size_t i = 0; i < kNumReads; ++i) { |
| 931 dest_iov[i].iov_base = | 932 dest_iov[i].iov_base = |
| 932 reinterpret_cast<void*>(const_cast<char*>(read_buf[i])); | 933 reinterpret_cast<void*>(const_cast<char*>(read_buf[i])); |
| 933 dest_iov[i].iov_len = rng_.RandUint64() % kMaxReadSize; | 934 dest_iov[i].iov_len = rng_.RandUint64() % kMaxReadSize; |
| 934 num_to_read += dest_iov[i].iov_len; | 935 num_to_read += dest_iov[i].iov_len; |
| 935 } | 936 } |
| 936 size_t actually_read; | 937 size_t actually_read; |
| 937 EXPECT_EQ(QUIC_NO_ERROR, | 938 EXPECT_EQ(QUIC_NO_ERROR, |
| 938 buffer_->Readv(dest_iov, kNumReads, &actually_read, | 939 buffer_->Readv(dest_iov, kNumReads, &actually_read, |
| 939 &error_details_)); | 940 &error_details_)); |
| 940 ASSERT_LE(actually_read, num_to_read); | 941 ASSERT_LE(actually_read, num_to_read); |
| 941 DVLOG(1) << " read from offset: " << total_bytes_read_ | 942 QUIC_DVLOG(1) << " read from offset: " << total_bytes_read_ |
| 942 << " size: " << num_to_read | 943 << " size: " << num_to_read |
| 943 << " actual read: " << actually_read; | 944 << " actual read: " << actually_read; |
| 944 for (size_t i = 0; i < actually_read; ++i) { | 945 for (size_t i = 0; i < actually_read; ++i) { |
| 945 char ch = (i + total_bytes_read_) % 256; | 946 char ch = (i + total_bytes_read_) % 256; |
| 946 ASSERT_EQ(ch, GetCharFromIOVecs(i, dest_iov, kNumReads)) | 947 ASSERT_EQ(ch, GetCharFromIOVecs(i, dest_iov, kNumReads)) |
| 947 << " at iteration " << iterations; | 948 << " at iteration " << iterations; |
| 948 } | 949 } |
| 949 total_bytes_read_ += actually_read; | 950 total_bytes_read_ += actually_read; |
| 950 ASSERT_EQ(total_bytes_read_, buffer_->BytesConsumed()); | 951 ASSERT_EQ(total_bytes_read_, buffer_->BytesConsumed()); |
| 951 ASSERT_TRUE(helper_->CheckBufferInvariants()); | 952 ASSERT_TRUE(helper_->CheckBufferInvariants()); |
| 952 break; | 953 break; |
| 953 } | 954 } |
| (...skipping 15 matching lines...) Expand all Loading... |
| 969 const size_t kMaxWriteSize = kMaxNumReads * kBlockSizeBytes; | 970 const size_t kMaxWriteSize = kMaxNumReads * kBlockSizeBytes; |
| 970 ASSERT_LE(kMaxWriteSize, max_capacity_bytes_); | 971 ASSERT_LE(kMaxWriteSize, max_capacity_bytes_); |
| 971 size_t iterations = 0; | 972 size_t iterations = 0; |
| 972 | 973 |
| 973 CreateSourceAndShuffle(kMaxWriteSize); | 974 CreateSourceAndShuffle(kMaxWriteSize); |
| 974 | 975 |
| 975 while ((!shuffled_buf_.empty() || total_bytes_read_ < bytes_to_buffer_) && | 976 while ((!shuffled_buf_.empty() || total_bytes_read_ < bytes_to_buffer_) && |
| 976 iterations <= 2 * bytes_to_buffer_) { | 977 iterations <= 2 * bytes_to_buffer_) { |
| 977 uint8_t next_action = | 978 uint8_t next_action = |
| 978 shuffled_buf_.empty() ? uint8_t{1} : rng_.RandUint64() % 2; | 979 shuffled_buf_.empty() ? uint8_t{1} : rng_.RandUint64() % 2; |
| 979 DVLOG(1) << "iteration: " << iterations; | 980 QUIC_DVLOG(1) << "iteration: " << iterations; |
| 980 switch (next_action) { | 981 switch (next_action) { |
| 981 case 0: { // write | 982 case 0: { // write |
| 982 WriteNextChunkToBuffer(); | 983 WriteNextChunkToBuffer(); |
| 983 ASSERT_TRUE(helper_->CheckBufferInvariants()); | 984 ASSERT_TRUE(helper_->CheckBufferInvariants()); |
| 984 break; | 985 break; |
| 985 } | 986 } |
| 986 case 1: { // GetReadableRegions and then MarkConsumed | 987 case 1: { // GetReadableRegions and then MarkConsumed |
| 987 size_t num_read = rng_.RandUint64() % kMaxNumReads + 1; | 988 size_t num_read = rng_.RandUint64() % kMaxNumReads + 1; |
| 988 iovec dest_iov[kMaxNumReads]; | 989 iovec dest_iov[kMaxNumReads]; |
| 989 ASSERT_TRUE(helper_->CheckBufferInvariants()); | 990 ASSERT_TRUE(helper_->CheckBufferInvariants()); |
| (...skipping 19 matching lines...) Expand all Loading... |
| 1009 (buffer_->BytesConsumed() + bytes_processed) % 256; | 1010 (buffer_->BytesConsumed() + bytes_processed) % 256; |
| 1010 ASSERT_EQ(char_expected, | 1011 ASSERT_EQ(char_expected, |
| 1011 reinterpret_cast<const char*>(dest_iov[i].iov_base)[j]) | 1012 reinterpret_cast<const char*>(dest_iov[i].iov_base)[j]) |
| 1012 << " at iteration " << iterations; | 1013 << " at iteration " << iterations; |
| 1013 ++bytes_processed; | 1014 ++bytes_processed; |
| 1014 } | 1015 } |
| 1015 } | 1016 } |
| 1016 | 1017 |
| 1017 buffer_->MarkConsumed(bytes_processed); | 1018 buffer_->MarkConsumed(bytes_processed); |
| 1018 | 1019 |
| 1019 DVLOG(1) << "iteration " << iterations << ": try to get " << num_read | 1020 QUIC_DVLOG(1) << "iteration " << iterations << ": try to get " |
| 1020 << " readable regions, actually get " << actually_num_read | 1021 << num_read << " readable regions, actually get " |
| 1021 << " from offset: " << total_bytes_read_ | 1022 << actually_num_read |
| 1022 << "\nprocesse bytes: " << bytes_processed; | 1023 << " from offset: " << total_bytes_read_ |
| 1024 << "\nprocesse bytes: " << bytes_processed; |
| 1023 total_bytes_read_ += bytes_processed; | 1025 total_bytes_read_ += bytes_processed; |
| 1024 ASSERT_EQ(total_bytes_read_, buffer_->BytesConsumed()); | 1026 ASSERT_EQ(total_bytes_read_, buffer_->BytesConsumed()); |
| 1025 ASSERT_TRUE(helper_->CheckBufferInvariants()); | 1027 ASSERT_TRUE(helper_->CheckBufferInvariants()); |
| 1026 break; | 1028 break; |
| 1027 } | 1029 } |
| 1028 } | 1030 } |
| 1029 ++iterations; | 1031 ++iterations; |
| 1030 ASSERT_LE(total_bytes_read_, total_bytes_written_); | 1032 ASSERT_LE(total_bytes_read_, total_bytes_written_); |
| 1031 } | 1033 } |
| 1032 EXPECT_LT(iterations, bytes_to_buffer_) << "runaway test"; | 1034 EXPECT_LT(iterations, bytes_to_buffer_) << "runaway test"; |
| 1033 EXPECT_LE(bytes_to_buffer_, total_bytes_read_) << "iterations: " | 1035 EXPECT_LE(bytes_to_buffer_, total_bytes_read_) << "iterations: " |
| 1034 << iterations; | 1036 << iterations; |
| 1035 EXPECT_LE(bytes_to_buffer_, total_bytes_written_); | 1037 EXPECT_LE(bytes_to_buffer_, total_bytes_written_); |
| 1036 } | 1038 } |
| 1037 | 1039 |
| 1038 } // anonymous namespace | 1040 } // anonymous namespace |
| 1039 | 1041 |
| 1040 } // namespace test | 1042 } // namespace test |
| 1041 | 1043 |
| 1042 } // namespace net | 1044 } // namespace net |
| OLD | NEW |