From 9b2426ecfc4f004fe77badb4cc64f93af3a2d0d3 Mon Sep 17 00:00:00 2001 From: Andreas Sandberg Date: Fri, 7 Aug 2015 09:59:19 +0100 Subject: base: Rewrite the CircleBuf to fix bugs and add serialization The CircleBuf class has at least one bug causing it to overwrite the wrong elements when wrapping. The current code has a lot of unused functionality and duplicated code. This changeset replaces the old implementation with a new version that supports serialization and arbitrary types in the buffer (not just char). --- src/base/circlebuf.hh | 276 +++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 248 insertions(+), 28 deletions(-) (limited to 'src/base/circlebuf.hh') diff --git a/src/base/circlebuf.hh b/src/base/circlebuf.hh index 66583b7db..eca293669 100644 --- a/src/base/circlebuf.hh +++ b/src/base/circlebuf.hh @@ -1,6 +1,15 @@ /* - * Copyright (c) 2002-2005 The Regents of The University of Michigan - * All rights reserved. + * Copyright (c) 2015 ARM Limited + * All rights reserved + * + * The license below extends only to copyright in the software and shall + * not be construed as granting a license to any other intellectual + * property including but not limited to intellectual property relating + * to a hardware implementation of the functionality of the software + * licensed hereunder. You may use the software subject to the license + * terms below provided that you ensure that this notice is replicated + * unmodified and in its entirety in all distributions of the software, + * modified or unmodified, in source code or in binary form. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are @@ -25,40 +34,251 @@ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * - * Authors: Nathan Binkert + * Authors: Andreas Sandberg */ -#ifndef __CIRCLEBUF_HH__ -#define __CIRCLEBUF_HH__ +#ifndef __BASE_CIRCLEBUF_HH__ +#define __BASE_CIRCLEBUF_HH__ + +#include +#include +#include -#include +#include "base/misc.hh" +#include "sim/serialize.hh" +/** + * Circular buffer backed by a vector + * + * The data in the cricular buffer is stored in a standard + * vector. _start designates the first element in the buffer and _stop + * points to the last element + 1 (i.e., the position of the next + * insertion). The _stop index may be outside the range of the backing + * store, which means that the actual index must be calculated as + * _stop % capacity. + * + * Invariants: + *
    + *
  • _start <= _stop + *
  • _start < capacity + *
  • _stop < 2 * capacity + *
+ */ +template class CircleBuf { + public: + typedef T value_type; + + public: + explicit CircleBuf(size_t size) + : buf(size), _start(0), _stop(0) {} + + /** Is the buffer empty? */ + bool empty() const { return _stop == _start; } + /** + * Return the maximum number of elements that can be stored in + * the buffer at any one time. + */ + size_t capacity() const { return buf.size(); } + /** Return the number of elements stored in the buffer. */ + size_t size() const { return _stop - _start; } + + /** + * Remove all the elements in the buffer. + * + * Note: This does not actually remove elements from the backing + * store. + */ + void flush() { + _start = 0; + _stop = 0; + } + + /** + * Copy buffer contents without advancing the read pointer + * + * @param out Output iterator/pointer + * @param len Number of elements to copy + */ + template + void peek(OutputIterator out, size_t len) const { + panic_if(len > size(), + "Trying to read past end of circular buffer.\n"); + + if (_start + len <= buf.size()) { + std::copy(buf.begin() + _start, + buf.begin() + _start + len, + out); + } else { + const size_t head_size(buf.size() - _start); + const size_t tail_size(len - head_size); + std::copy(buf.begin() + _start, buf.end(), + out); + std::copy(buf.begin(), buf.begin() + tail_size, + out + head_size); + } + } + + + /** + * Copy buffer contents and advance the read pointer + * + * @param out Output iterator/pointer + * @param len Number of elements to read + */ + template + void read(OutputIterator out, size_t len) { + peek(out, len); + + _start += len; + normalize(); + } + + /** + * Add elements to the end of the ring buffers and advance. + * + * @param in Input iterator/pointer + * @param len Number of elements to read + */ + template + 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 > buf.size()) { + in += len - buf.size(); + len = buf.size(); + } + + const size_t next(_stop % buf.size()); + const size_t head_len(std::min(buf.size() - next, len)); + + std::copy(in, in + head_len, buf.begin() + next); + std::copy(in + head_len, in + len, buf.begin()); + + _stop += len; + // We may have written past the old _start pointer. Readjust + // the _start pointer to remove the oldest entries in that + // case. + if (size() > buf.size()) + _start = _stop - buf.size(); + + normalize(); + } + + protected: + /** + * Normalize the start and stop pointers to ensure that pointer + * invariants hold after updates. + */ + void normalize() { + if (_start >= buf.size()) { + _stop -= buf.size(); + _start -= buf.size(); + } + + assert(_start < buf.size()); + assert(_stop < 2 * buf.size()); + assert(_start <= _stop); + } + protected: - char *_buf; - bool _rollover; - int _buflen; - int _size; - int _start; - int _stop; + std::vector buf; + size_t _start; + size_t _stop; + +}; + + +/** + * Simple FIFO implementation backed by a circular buffer. + * + * This class provides the same basic functionallity as the circular + * buffer with the folling differences: + *
    + *
  • Writes are checked to ensure that overflows can't happen. + *
  • Unserialization ensures that the data in the checkpoint fits + * in the buffer. + *
+ */ +template +class Fifo +{ + public: + typedef T value_type; public: - explicit CircleBuf(int l); - ~CircleBuf(); - - bool empty() const { return _size == 0; } - int size() const { return _size; } - void dump(); - void flush(); - void read(char *b, int len); - void read(int fd, int len); - void read(int fd); - void read(std::ostream &out); - void readall(int fd); - void write(char b); - void write(const char *b); - void write(const char *b, int len); + Fifo(size_t size) + : buf(size) {} + + bool empty() const { return buf.empty(); } + size_t size() const { return buf.size(); } + size_t capacity() const { return buf.capacity(); } + + void flush() { buf.flush(); } + + template + void peek(OutputIterator out, size_t len) const { buf.peek(out, len); } + template + void read(OutputIterator out, size_t len) { buf.read(out, len); } + + template + void write(InputIterator in, size_t len) { + panic_if(size() + len > capacity(), + "Trying to overfill FIFO buffer.\n"); + buf.write(in, len); + } + + private: + CircleBuf buf; }; -#endif // __CIRCLEBUF_HH__ + +template +static void +arrayParamOut(CheckpointOut &cp, const std::string &name, + const CircleBuf ¶m) +{ + std::vector temp(param.size()); + param.peek(temp.begin(), temp.size()); + arrayParamOut(cp, name, temp); +} + +template +static void +arrayParamIn(CheckpointIn &cp, const std::string &name, + CircleBuf ¶m) +{ + std::vector temp; + arrayParamIn(cp, name, temp); + + param.flush(); + param.write(temp.cbegin(), temp.size()); +} + +template +static void +arrayParamOut(CheckpointOut &cp, const std::string &name, + const Fifo ¶m) +{ + std::vector temp(param.size()); + param.peek(temp.begin(), temp.size()); + arrayParamOut(cp, name, temp); +} + +template +static void +arrayParamIn(CheckpointIn &cp, const std::string &name, + Fifo ¶m) +{ + std::vector temp; + arrayParamIn(cp, name, temp); + + fatal_if(param.capacity() < temp.size(), + "Trying to unserialize data into too small FIFO\n"); + + param.flush(); + param.write(temp.cbegin(), temp.size()); +} + +#endif // __BASE_CIRCLEBUF_HH__ -- cgit v1.2.3