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 // quiche::QuicheStringPiece 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 // quiche::QuicheStringPiece 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 "net/third_party/quiche/src/quic/core/quic_interval_set.h" 68 #include "net/third_party/quiche/src/quic/core/quic_packets.h" 69 #include "net/third_party/quiche/src/quic/core/quic_types.h" 70 #include "net/third_party/quiche/src/quic/platform/api/quic_export.h" 71 #include "net/third_party/quiche/src/quic/platform/api/quic_iovec.h" 72 #include "net/third_party/quiche/src/common/platform/api/quiche_string_piece.h" 73 74 namespace quic { 75 76 namespace test { 77 class QuicStreamSequencerBufferPeer; 78 } // namespace test 79 80 class QUIC_EXPORT_PRIVATE 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 QUIC_EXPORT_PRIVATE 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(); 98 99 // Free the space used to buffer data. 100 void Clear(); 101 102 // Returns true if there is nothing to read in this buffer. 103 bool Empty() const; 104 105 // Called to buffer new data received for this stream. If the data was 106 // successfully buffered, returns QUIC_NO_ERROR and stores the number of 107 // bytes buffered in |bytes_buffered|. Returns an error otherwise. 108 QuicErrorCode OnStreamData(QuicStreamOffset offset, 109 quiche::QuicheStringPiece 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, 116 size_t dest_count, 117 size_t* bytes_read, 118 std::string* error_details); 119 120 // Returns the readable region of valid data in iovec format. The readable 121 // region is the buffer region where there is valid data not yet read by 122 // client. 123 // Returns the number of iovec entries in |iov| which were populated. 124 // If the region is empty, one iovec entry with 0 length 125 // is returned, and the function returns 0. If there are more readable 126 // regions than |iov_size|, the function only processes the first 127 // |iov_size| of them. 128 int GetReadableRegions(struct iovec* iov, int iov_len) const; 129 130 // Fills in one iovec with data from the next readable region. 131 // Returns false if there is no readable region available. 132 bool GetReadableRegion(iovec* iov) const; 133 134 // Returns true and sets |*iov| to point to a region starting at |offset|. 135 // Returns false if no data can be read at |offset|, which can be because data 136 // has not been received yet or it is already consumed. 137 // Does not consume data. 138 bool PeekRegion(QuicStreamOffset offset, iovec* iov) const; 139 140 // Called after GetReadableRegions() to free up |bytes_consumed| space if 141 // these bytes are processed. 142 // Pre-requisite: bytes_consumed <= available bytes to read. 143 bool MarkConsumed(size_t bytes_consumed); 144 145 // Deletes and records as consumed any buffered data and clear the buffer. 146 // (To be called only after sequencer's StopReading has been called.) 147 size_t FlushBufferedFrames(); 148 149 // Free the memory of buffered data. 150 void ReleaseWholeBuffer(); 151 152 // Whether there are bytes can be read out. 153 bool HasBytesToRead() const; 154 155 // Count how many bytes have been consumed (read out of buffer). 156 QuicStreamOffset BytesConsumed() const; 157 158 // Count how many bytes are in buffer at this moment. 159 size_t BytesBuffered() const; 160 161 // Returns number of bytes available to be read out. 162 size_t ReadableBytes() const; 163 164 private: 165 friend class test::QuicStreamSequencerBufferPeer; 166 167 // Copies |data| to blocks_, sets |bytes_copy|. Returns true if the copy is 168 // successful. Otherwise, sets |error_details| and returns false. 169 bool CopyStreamData(QuicStreamOffset offset, 170 quiche::QuicheStringPiece data, 171 size_t* bytes_copy, 172 std::string* error_details); 173 174 // Dispose the given buffer block. 175 // After calling this method, blocks_[index] is set to nullptr 176 // in order to indicate that no memory set is allocated for that block. 177 // Returns true on success, false otherwise. 178 bool RetireBlock(size_t index); 179 180 // Should only be called after the indexed block is read till the end of the 181 // block or missing data has been reached. 182 // If the block at |block_index| contains no buffered data, the block 183 // should be retired. 184 // Returns true on success, or false otherwise. 185 bool RetireBlockIfEmpty(size_t block_index); 186 187 // Calculate the capacity of block at specified index. 188 // Return value should be either kBlockSizeBytes for non-trailing blocks and 189 // max_buffer_capacity % kBlockSizeBytes for trailing block. 190 size_t GetBlockCapacity(size_t index) const; 191 192 // Does not check if offset is within reasonable range. 193 size_t GetBlockIndex(QuicStreamOffset offset) const; 194 195 // Given an offset in the stream, return the offset from the beginning of the 196 // block which contains this data. 197 size_t GetInBlockOffset(QuicStreamOffset offset) const; 198 199 // Get offset relative to index 0 in logical 1st block to start next read. 200 size_t ReadOffset() const; 201 202 // Get the index of the logical 1st block to start next read. 203 size_t NextBlockToRead() const; 204 205 // Returns offset of first missing byte. 206 QuicStreamOffset FirstMissingByte() const; 207 208 // Returns offset of highest received byte + 1. 209 QuicStreamOffset NextExpectedByte() const; 210 211 // Return all received frames as a string. 212 std::string ReceivedFramesDebugString() const; 213 214 // The maximum total capacity of this buffer in byte, as constructed. 215 const size_t max_buffer_capacity_bytes_; 216 217 // How many blocks this buffer would need when it reaches full capacity. 218 const size_t blocks_count_; 219 220 // Number of bytes read out of buffer. 221 QuicStreamOffset total_bytes_read_; 222 223 // An ordered, variable-length list of blocks, with the length limited 224 // such that the number of blocks never exceeds blocks_count_. 225 // Each list entry can hold up to kBlockSizeBytes bytes. 226 std::unique_ptr<BufferBlock*[]> blocks_; 227 228 // Number of bytes in buffer. 229 size_t num_bytes_buffered_; 230 231 // Currently received data. 232 QuicIntervalSet<QuicStreamOffset> bytes_received_; 233 }; 234 235 } // namespace quic 236 237 #endif // QUICHE_QUIC_CORE_QUIC_STREAM_SEQUENCER_BUFFER_H_ 238