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 3 // found in the LICENSE file. 4 5 #ifndef QUICHE_QUIC_CORE_QUIC_STREAM_SEQUENCER_BUFFER_H_ 6 #define QUICHE_QUIC_CORE_QUIC_STREAM_SEQUENCER_BUFFER_H_ 7 8 // QuicStreamSequencerBuffer is a circular stream buffer with random write and 9 // in-sequence read. It consists of a vector of pointers pointing 10 // to memory blocks created as needed and an interval set recording received 11 // data. 12 // - Data are written in with offset indicating where it should be in the 13 // stream, and the buffer grown as needed (up to the maximum buffer capacity), 14 // without expensive copying (extra blocks are allocated). 15 // - Data can be read from the buffer if there is no gap before it, 16 // and the buffer shrinks as the data are consumed. 17 // - An upper limit on the number of blocks in the buffer provides an upper 18 // bound on memory use. 19 // 20 // This class is thread-unsafe. 21 // 22 // QuicStreamSequencerBuffer maintains a concept of the readable region, which 23 // contains all written data that has not been read. 24 // It promises stability of the underlying memory addresses in the readable 25 // region, so pointers into it can be maintained, and the offset of a pointer 26 // from the start of the read region can be calculated. 27 // 28 // Expected Use: 29 // QuicStreamSequencerBuffer buffer(2.5 * 8 * 1024); 30 // std::string source(1024, 'a'); 31 // absl::string_view string_piece(source.data(), source.size()); 32 // size_t written = 0; 33 // buffer.OnStreamData(800, string_piece, GetEpollClockNow(), &written); 34 // source = std::string{800, 'b'}; 35 // absl::string_view string_piece1(source.data(), 800); 36 // // Try to write to [1, 801), but should fail due to overlapping, 37 // // res should be QUIC_INVALID_STREAM_DATA 38 // auto res = buffer.OnStreamData(1, string_piece1, &written)); 39 // // write to [0, 800), res should be QUIC_NO_ERROR 40 // auto res = buffer.OnStreamData(0, string_piece1, GetEpollClockNow(), 41 // &written); 42 // 43 // // Read into a iovec array with total capacity of 120 bytes. 44 // char dest[120]; 45 // iovec iovecs[3]{iovec{dest, 40}, iovec{dest + 40, 40}, 46 // iovec{dest + 80, 40}}; 47 // size_t read = buffer.Readv(iovecs, 3); 48 // 49 // // Get single readable region. 50 // iovec iov; 51 // buffer.GetReadableRegion(iov); 52 // 53 // // Get readable regions from [256, 1024) and consume some of it. 54 // iovec iovs[2]; 55 // int iov_count = buffer.GetReadableRegions(iovs, 2); 56 // // Consume some bytes in iovs, returning number of bytes having been 57 // consumed. 58 // size_t consumed = consume_iovs(iovs, iov_count); 59 // buffer.MarkConsumed(consumed); 60 61 #include <cstddef> 62 #include <functional> 63 #include <list> 64 #include <memory> 65 #include <string> 66 67 #include "absl/strings/string_view.h" 68 #include "quiche/quic/core/quic_interval_set.h" 69 #include "quiche/quic/core/quic_packets.h" 70 #include "quiche/quic/core/quic_types.h" 71 #include "quiche/quic/platform/api/quic_export.h" 72 #include "quiche/common/platform/api/quiche_iovec.h" 73 74 namespace quic { 75 76 namespace test { 77 class QuicStreamSequencerBufferPeer; 78 } // namespace test 79 80 class QUICHE_EXPORT QuicStreamSequencerBuffer { 81 public: 82 // Size of blocks used by this buffer. 83 // Choose 8K to make block large enough to hold multiple frames, each of 84 // which could be up to 1.5 KB. 85 static const size_t kBlockSizeBytes = 8 * 1024; // 8KB 86 87 // The basic storage block used by this buffer. 88 struct QUICHE_EXPORT BufferBlock { 89 char buffer[kBlockSizeBytes]; 90 }; 91 92 explicit QuicStreamSequencerBuffer(size_t max_capacity_bytes); 93 QuicStreamSequencerBuffer(const QuicStreamSequencerBuffer&) = delete; 94 QuicStreamSequencerBuffer(QuicStreamSequencerBuffer&&) = default; 95 QuicStreamSequencerBuffer& operator=(const QuicStreamSequencerBuffer&) = 96 delete; 97 QuicStreamSequencerBuffer& operator=(QuicStreamSequencerBuffer&&) = default; 98 ~QuicStreamSequencerBuffer(); 99 100 // Free the space used to buffer data. 101 void Clear(); 102 103 // Returns true if there is nothing to read in this buffer. 104 bool Empty() const; 105 106 // Called to buffer new data received for this stream. If the data was 107 // successfully buffered, returns QUIC_NO_ERROR and stores the number of 108 // bytes buffered in |bytes_buffered|. Returns an error otherwise. 109 QuicErrorCode OnStreamData(QuicStreamOffset offset, absl::string_view data, 110 size_t* bytes_buffered, 111 std::string* error_details); 112 113 // Reads from this buffer into given iovec array, up to number of iov_len 114 // iovec objects and returns the number of bytes read. 115 QuicErrorCode Readv(const struct iovec* dest_iov, size_t dest_count, 116 size_t* bytes_read, std::string* error_details); 117 118 // Returns the readable region of valid data in iovec format. The readable 119 // region is the buffer region where there is valid data not yet read by 120 // client. 121 // Returns the number of iovec entries in |iov| which were populated. 122 // If the region is empty, one iovec entry with 0 length 123 // is returned, and the function returns 0. If there are more readable 124 // regions than |iov_size|, the function only processes the first 125 // |iov_size| of them. 126 int GetReadableRegions(struct iovec* iov, int iov_len) const; 127 128 // Fills in one iovec with data from the next readable region. 129 // Returns false if there is no readable region available. 130 bool GetReadableRegion(iovec* iov) const; 131 132 // Returns true and sets |*iov| to point to a region starting at |offset|. 133 // Returns false if no data can be read at |offset|, which can be because data 134 // has not been received yet or it is already consumed. 135 // Does not consume data. 136 bool PeekRegion(QuicStreamOffset offset, iovec* iov) const; 137 138 // Called after GetReadableRegions() to free up |bytes_consumed| space if 139 // these bytes are processed. 140 // Pre-requisite: bytes_consumed <= available bytes to read. 141 bool MarkConsumed(size_t bytes_consumed); 142 143 // Deletes and records as consumed any buffered data and clear the buffer. 144 // (To be called only after sequencer's StopReading has been called.) 145 size_t FlushBufferedFrames(); 146 147 // Free the memory of buffered data. 148 void ReleaseWholeBuffer(); 149 150 // Whether there are bytes can be read out. 151 bool HasBytesToRead() const; 152 153 // Count how many bytes have been consumed (read out of buffer). 154 QuicStreamOffset BytesConsumed() const; 155 156 // Count how many bytes are in buffer at this moment. 157 size_t BytesBuffered() const; 158 159 // Returns number of bytes available to be read out. 160 size_t ReadableBytes() const; 161 162 // Returns offset of first missing byte. 163 QuicStreamOffset FirstMissingByte() const; 164 165 // Returns offset of highest received byte + 1. 166 QuicStreamOffset NextExpectedByte() const; 167 168 // Return all received frames as a string. 169 std::string ReceivedFramesDebugString() const; 170 171 private: 172 friend class test::QuicStreamSequencerBufferPeer; 173 174 // Copies |data| to blocks_, sets |bytes_copy|. Returns true if the copy is 175 // successful. Otherwise, sets |error_details| and returns false. 176 bool CopyStreamData(QuicStreamOffset offset, absl::string_view data, 177 size_t* bytes_copy, std::string* error_details); 178 179 // Dispose the given buffer block. 180 // After calling this method, blocks_[index] is set to nullptr 181 // in order to indicate that no memory set is allocated for that block. 182 // Returns true on success, false otherwise. 183 bool RetireBlock(size_t index); 184 185 // Should only be called after the indexed block is read till the end of the 186 // block or missing data has been reached. 187 // If the block at |block_index| contains no buffered data, the block 188 // should be retired. 189 // Returns true on success, or false otherwise. 190 bool RetireBlockIfEmpty(size_t block_index); 191 192 // Calculate the capacity of block at specified index. 193 // Return value should be either kBlockSizeBytes for non-trailing blocks and 194 // max_buffer_capacity % kBlockSizeBytes for trailing block. 195 size_t GetBlockCapacity(size_t index) const; 196 197 // Does not check if offset is within reasonable range. 198 size_t GetBlockIndex(QuicStreamOffset offset) const; 199 200 // Given an offset in the stream, return the offset from the beginning of the 201 // block which contains this data. 202 size_t GetInBlockOffset(QuicStreamOffset offset) const; 203 204 // Get offset relative to index 0 in logical 1st block to start next read. 205 size_t ReadOffset() const; 206 207 // Get the index of the logical 1st block to start next read. 208 size_t NextBlockToRead() const; 209 210 // Resize blocks_ if more blocks are needed to accomodate bytes before 211 // next_expected_byte. 212 void MaybeAddMoreBlocks(QuicStreamOffset next_expected_byte); 213 214 // The maximum total capacity of this buffer in byte, as constructed. 215 size_t max_buffer_capacity_bytes_; 216 217 // Number of blocks this buffer would have when it reaches full capacity, 218 // i.e., maximal number of blocks in blocks_. 219 size_t max_blocks_count_; 220 221 // Number of blocks this buffer currently has. 222 size_t current_blocks_count_; 223 224 // Number of bytes read out of buffer. 225 QuicStreamOffset total_bytes_read_; 226 227 // An ordered, variable-length list of blocks, with the length limited 228 // such that the number of blocks never exceeds max_blocks_count_. 229 // Each list entry can hold up to kBlockSizeBytes bytes. 230 std::unique_ptr<BufferBlock*[]> blocks_; 231 232 // Number of bytes in buffer. 233 size_t num_bytes_buffered_; 234 235 // Currently received data. 236 QuicIntervalSet<QuicStreamOffset> bytes_received_; 237 }; 238 239 } // namespace quic 240 241 #endif // QUICHE_QUIC_CORE_QUIC_STREAM_SEQUENCER_BUFFER_H_ 242