From 65828b2735706ff7ec3aea5fb9e38d1e6f0be300 Mon Sep 17 00:00:00 2001 From: Gabe Black Date: Sun, 10 Jan 2021 21:56:49 -0800 Subject: [PATCH] base: Re-implement CircleBuf without using CircularQueue. CircularQueue provides iterators which make it easier for users to interact with it and helps abstract its internal state, but at the same time it prevents standard algorithms like std::copy from recognizing opportunities to use bulk copies to speed up execution. It also hides the seams when wrapping around the buffer happens which std::copy wouldn't know how to handle. CircleBuf seems to be intended as a simpler type which doesn't hold complex entries like the CircularQueue does, and instead just acts as a wrap around buffer, like the name suggests. This change reimplements it to not use CircularQueue, and to instead use an underlying vector. The way internal indexing is handled CircularQueue was simplified recently, and using the same scheme here means that this code is actually not much more verbose than it was before. It also intrinsically handles indexing and bulk accesses, and uses std::copy_n in a way that lets it recognize and take advantage of contiguous storage and bulk copies. Change-Id: I78e7cfe174c52f60c95c81e5cd3d71c6052d4d41 Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/38896 Reviewed-by: Daniel Carvalho Maintainer: Gabe Black Maintainer: Andreas Sandberg Tested-by: kokoro --- src/base/circlebuf.hh | 123 +++++++++++++++++++++++++++++++++--------- 1 file changed, 97 insertions(+), 26 deletions(-) diff --git a/src/base/circlebuf.hh b/src/base/circlebuf.hh index 8d7297a0e..0f1cea638 100644 --- a/src/base/circlebuf.hh +++ b/src/base/circlebuf.hh @@ -40,32 +40,55 @@ #include #include +#include #include -#include "base/circular_queue.hh" #include "base/logging.hh" #include "sim/serialize.hh" /** - * Circular buffer backed by a vector though a CircularQueue. - * - * The data in the cricular buffer is stored in a standard - * vector. + * Circular buffer backed by a vector. * + * The data in the cricular buffer is stored in a standard vector. */ template -class CircleBuf : public CircularQueue +class CircleBuf { + private: + std::vector buffer; + size_t start = 0; + size_t used = 0; + size_t maxSize; + public: - explicit CircleBuf(size_t size) - : CircularQueue(size) {} - using CircularQueue::empty; - using CircularQueue::size; - using CircularQueue::capacity; - using CircularQueue::begin; - using CircularQueue::end; - using CircularQueue::pop_front; - using CircularQueue::advance_tail; + using value_type = T; + using iterator = typename std::vector::iterator; + using const_iterator = typename std::vector::const_iterator; + + explicit CircleBuf(size_t size) : buffer(size), maxSize(size) {} + + bool empty() const { return used == 0; } + size_t size() const { return used; } + size_t capacity() const { return maxSize; } + + iterator begin() { return buffer.begin() + start % maxSize; } + const_iterator begin() const { return buffer.begin() + start % maxSize; } + iterator end() { return buffer.begin() + (start + used) % maxSize; } + const_iterator + end() const + { + return buffer.begin() + (start + used) % maxSize; + } + + /** + * Throw away any data in the buffer. + */ + void + flush() + { + start = 0; + used = 0; + } /** * Copy buffer contents without advancing the read pointer @@ -91,10 +114,27 @@ class CircleBuf : public CircularQueue void peek(OutputIterator out, off_t offset, size_t len) const { - panic_if(offset + len > size(), + panic_if(offset + len > used, "Trying to read past end of circular buffer."); - std::copy(begin() + offset, begin() + offset + len, out); + if (!len) + return; + + // The iterator for the next byte to copy out. + auto next_it = buffer.begin() + (start + offset) % maxSize; + // How much there is to copy from until the end of the buffer. + const size_t to_end = buffer.end() - next_it; + + // If the data to be copied wraps, take care of the first part. + if (to_end < len) { + // Copy it. + out = std::copy_n(next_it, to_end, out); + // Start copying again at the start of buffer. + next_it = buffer.begin(); + len -= to_end; + } + // Copy the remaining (or only) chunk of data. + std::copy_n(next_it, len, out); } /** @@ -108,11 +148,15 @@ class CircleBuf : public CircularQueue read(OutputIterator out, size_t len) { peek(out, len); - pop_front(len); + used -= len; + start += len; } /** - * Add elements to the end of the ring buffers and advance. + * Add elements to the end of the ring buffers and advance. Writes which + * would exceed the capacity of the queue fill the avaialble space, and + * then continue overwriting the head of the queue. The head advances as + * if that data had been read out. * * @param in Input iterator/pointer * @param len Number of elements to read @@ -121,15 +165,42 @@ class CircleBuf : public CircularQueue void write(InputIterator in, size_t len) { - // Writes that are larger than the backing store are allowed, - // but only the last part of the buffer will be written. - if (len > capacity()) { - in += len - capacity(); - len = capacity(); + if (!len) + return; + + // Writes that are larger than the buffer size are allowed, but only + // the last part of the date will be written since the rest will be + // overwritten and not remain in the buffer. + if (len > maxSize) { + in += len - maxSize; + flush(); + len = maxSize; + } + + // How much existing data will be overwritten? + const size_t overflow = std::max(0, used + len - maxSize); + // The iterator of the next byte to add. + auto next_it = buffer.begin() + (start + used) % maxSize; + // How much there is to copy to the end of the buffer. + const size_t to_end = buffer.end() - next_it; + + // If this addition wraps, take care of the first part here. + if (to_end < len) { + // Copy it. + std::copy_n(in, to_end, next_it); + // Update state to reflect what's left. + next_it = buffer.begin(); + std::advance(in, to_end); + len -= to_end; + used += to_end; } + // Copy the remaining (or only) chunk of data. + std::copy_n(in, len, next_it); + used += len; - std::copy(in, in + len, end()); - advance_tail(len); + // Don't count data that was overwritten. + used -= overflow; + start += overflow; } }; -- 2.30.2