diff options
Diffstat (limited to 'chromium/net/third_party/quiche/src/quic/core/quic_stream_sequencer_buffer.h')
-rw-r--r-- | chromium/net/third_party/quiche/src/quic/core/quic_stream_sequencer_buffer.h | 248 |
1 files changed, 248 insertions, 0 deletions
diff --git a/chromium/net/third_party/quiche/src/quic/core/quic_stream_sequencer_buffer.h b/chromium/net/third_party/quiche/src/quic/core/quic_stream_sequencer_buffer.h new file mode 100644 index 00000000000..6f4717d8ca6 --- /dev/null +++ b/chromium/net/third_party/quiche/src/quic/core/quic_stream_sequencer_buffer.h @@ -0,0 +1,248 @@ +// Copyright (c) 2015 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef QUICHE_QUIC_CORE_QUIC_STREAM_SEQUENCER_BUFFER_H_ +#define QUICHE_QUIC_CORE_QUIC_STREAM_SEQUENCER_BUFFER_H_ + +// QuicStreamSequencerBuffer is a circular stream buffer with random write and +// in-sequence read. It consists of a vector of pointers pointing +// to memory blocks created as needed and an interval set recording received +// data. +// - Data are written in with offset indicating where it should be in the +// stream, and the buffer grown as needed (up to the maximum buffer capacity), +// without expensive copying (extra blocks are allocated). +// - Data can be read from the buffer if there is no gap before it, +// and the buffer shrinks as the data are consumed. +// - An upper limit on the number of blocks in the buffer provides an upper +// bound on memory use. +// +// This class is thread-unsafe. +// +// QuicStreamSequencerBuffer maintains a concept of the readable region, which +// contains all written data that has not been read. +// It promises stability of the underlying memory addresses in the readable +// region, so pointers into it can be maintained, and the offset of a pointer +// from the start of the read region can be calculated. +// +// Expected Use: +// QuicStreamSequencerBuffer buffer(2.5 * 8 * 1024); +// std::string source(1024, 'a'); +// QuicStringPiece string_piece(source.data(), source.size()); +// size_t written = 0; +// buffer.OnStreamData(800, string_piece, GetEpollClockNow(), &written); +// source = std::string{800, 'b'}; +// QuicStringPiece string_piece1(source.data(), 800); +// // Try to write to [1, 801), but should fail due to overlapping, +// // res should be QUIC_INVALID_STREAM_DATA +// auto res = buffer.OnStreamData(1, string_piece1, &written)); +// // write to [0, 800), res should be QUIC_NO_ERROR +// auto res = buffer.OnStreamData(0, string_piece1, GetEpollClockNow(), +// &written); +// +// // Read into a iovec array with total capacity of 120 bytes. +// char dest[120]; +// iovec iovecs[3]{iovec{dest, 40}, iovec{dest + 40, 40}, +// iovec{dest + 80, 40}}; +// size_t read = buffer.Readv(iovecs, 3); +// +// // Get single readable region. +// iovec iov; +// buffer.GetReadableRegion(iov); +// +// // Get readable regions from [256, 1024) and consume some of it. +// iovec iovs[2]; +// int iov_count = buffer.GetReadableRegions(iovs, 2); +// // Consume some bytes in iovs, returning number of bytes having been +// consumed. +// size_t consumed = consume_iovs(iovs, iov_count); +// buffer.MarkConsumed(consumed); + +#include <cstddef> +#include <functional> +#include <list> +#include <memory> +#include <string> + +#include "net/third_party/quiche/src/quic/core/quic_interval_set.h" +#include "net/third_party/quiche/src/quic/core/quic_packets.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_export.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_iovec.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_string_piece.h" + +namespace quic { + +namespace test { +class QuicStreamSequencerBufferPeer; +} // namespace test + +class QUIC_EXPORT_PRIVATE QuicStreamSequencerBuffer { + public: + // Size of blocks used by this buffer. + // Choose 8K to make block large enough to hold multiple frames, each of + // which could be up to 1.5 KB. + static const size_t kBlockSizeBytes = 8 * 1024; // 8KB + + // The basic storage block used by this buffer. + struct BufferBlock { + char buffer[kBlockSizeBytes]; + }; + + explicit QuicStreamSequencerBuffer(size_t max_capacity_bytes); + QuicStreamSequencerBuffer(const QuicStreamSequencerBuffer&) = delete; + QuicStreamSequencerBuffer(QuicStreamSequencerBuffer&&) = default; + QuicStreamSequencerBuffer& operator=(const QuicStreamSequencerBuffer&) = + delete; + ~QuicStreamSequencerBuffer(); + + // Free the space used to buffer data. + void Clear(); + + // Returns true if there is nothing to read in this buffer. + bool Empty() const; + + // Called to buffer new data received for this stream. If the data was + // successfully buffered, returns QUIC_NO_ERROR and stores the number of + // bytes buffered in |bytes_buffered|. Returns an error otherwise. + QuicErrorCode OnStreamData(QuicStreamOffset offset, + QuicStringPiece data, + size_t* bytes_buffered, + std::string* error_details); + + // Reads from this buffer into given iovec array, up to number of iov_len + // iovec objects and returns the number of bytes read. + QuicErrorCode Readv(const struct iovec* dest_iov, + size_t dest_count, + size_t* bytes_read, + std::string* error_details); + + // Returns the readable region of valid data in iovec format. The readable + // region is the buffer region where there is valid data not yet read by + // client. + // Returns the number of iovec entries in |iov| which were populated. + // If the region is empty, one iovec entry with 0 length + // is returned, and the function returns 0. If there are more readable + // regions than |iov_size|, the function only processes the first + // |iov_size| of them. + int GetReadableRegions(struct iovec* iov, int iov_len) const; + + // Fills in one iovec with data from the next readable region. + // Returns false if there is no readable region available. + bool GetReadableRegion(iovec* iov) const; + + // Called to return the next region that has not been returned by this method + // previously. + // If this method is to be used along with Readv() or MarkConsumed(), make + // sure that they are consuming less data than is read by this method. + // This method only returns reference of underlying data. The caller is + // responsible for copying and consuming the data. + // Returns true if the data is read, false otherwise. + bool PrefetchNextRegion(iovec* iov); + + // Called after GetReadableRegions() to free up |bytes_used| space if these + // bytes are processed. + // Pre-requisite: bytes_used <= available bytes to read. + bool MarkConsumed(size_t bytes_buffered); + + // Deletes and records as consumed any buffered data and clear the buffer. + // (To be called only after sequencer's StopReading has been called.) + size_t FlushBufferedFrames(); + + // Free the memory of buffered data. + void ReleaseWholeBuffer(); + + // Whether there are bytes can be read out. + bool HasBytesToRead() const; + + // Count how many bytes have been consumed (read out of buffer). + QuicStreamOffset BytesConsumed() const; + + // Count how many bytes are in buffer at this moment. + size_t BytesBuffered() const; + + // Returns number of bytes available to be read out. + size_t ReadableBytes() const; + + private: + friend class test::QuicStreamSequencerBufferPeer; + + // Copies |data| to blocks_, sets |bytes_copy|. Returns true if the copy is + // successful. Otherwise, sets |error_details| and returns false. + bool CopyStreamData(QuicStreamOffset offset, + QuicStringPiece data, + size_t* bytes_copy, + std::string* error_details); + + // Dispose the given buffer block. + // After calling this method, blocks_[index] is set to nullptr + // in order to indicate that no memory set is allocated for that block. + // Returns true on success, false otherwise. + bool RetireBlock(size_t index); + + // Should only be called after the indexed block is read till the end of the + // block or missing data has been reached. + // If the block at |block_index| contains no buffered data, the block + // should be retired. + // Returns true on success, or false otherwise. + bool RetireBlockIfEmpty(size_t block_index); + + // Calculate the capacity of block at specified index. + // Return value should be either kBlockSizeBytes for non-trailing blocks and + // max_buffer_capacity % kBlockSizeBytes for trailing block. + size_t GetBlockCapacity(size_t index) const; + + // Does not check if offset is within reasonable range. + size_t GetBlockIndex(QuicStreamOffset offset) const; + + // Given an offset in the stream, return the offset from the beginning of the + // block which contains this data. + size_t GetInBlockOffset(QuicStreamOffset offset) const; + + // Get offset relative to index 0 in logical 1st block to start next read. + size_t ReadOffset() const; + + // Get the index of the logical 1st block to start next read. + size_t NextBlockToRead() const; + + // Returns offset of first missing byte. + QuicStreamOffset FirstMissingByte() const; + + // Returns offset of highest received byte + 1. + QuicStreamOffset NextExpectedByte() const; + + // Return |gaps_| as a string: [1024, 1500) [1800, 2048)... for debugging. + std::string GapsDebugString(); + + // Return all received frames as a string in same format as GapsDebugString(); + std::string ReceivedFramesDebugString(); + + // The maximum total capacity of this buffer in byte, as constructed. + const size_t max_buffer_capacity_bytes_; + + // How many blocks this buffer would need when it reaches full capacity. + const size_t blocks_count_; + + // Number of bytes read out of buffer. + QuicStreamOffset total_bytes_read_; + + // An ordered, variable-length list of blocks, with the length limited + // such that the number of blocks never exceeds blocks_count_. + // Each list entry can hold up to kBlockSizeBytes bytes. + std::unique_ptr<BufferBlock*[]> blocks_; + + // Number of bytes in buffer. + size_t num_bytes_buffered_; + + // Currently received data. + QuicIntervalSet<QuicStreamOffset> bytes_received_; + + // Total number of bytes that have been prefetched. + QuicStreamOffset total_bytes_prefetched_; + + // Latched value of --quic_faster_interval_add_in_sequence_buffer. + const bool faster_interval_add_in_sequence_buffer_; +}; +} // namespace quic + +#endif // QUICHE_QUIC_CORE_QUIC_STREAM_SEQUENCER_BUFFER_H_ |