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/SConscript | 1 - src/base/circlebuf.cc | 215 --------------------------------------- src/base/circlebuf.hh | 276 +++++++++++++++++++++++++++++++++++++++++++++----- 3 files changed, 248 insertions(+), 244 deletions(-) delete mode 100644 src/base/circlebuf.cc (limited to 'src/base') diff --git a/src/base/SConscript b/src/base/SConscript index a00f8ad66..74a248be0 100644 --- a/src/base/SConscript +++ b/src/base/SConscript @@ -37,7 +37,6 @@ Source('atomicio.cc') Source('bigint.cc') Source('bitmap.cc') Source('callback.cc') -Source('circlebuf.cc') Source('cprintf.cc') Source('debug.cc') if env['USE_FENV']: diff --git a/src/base/circlebuf.cc b/src/base/circlebuf.cc deleted file mode 100644 index 2f04bc16e..000000000 --- a/src/base/circlebuf.cc +++ /dev/null @@ -1,215 +0,0 @@ -/* - * Copyright (c) 2002-2005 The Regents of The University of Michigan - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer; - * redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution; - * neither the name of the copyright holders nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (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 - */ - -#include -#include -#include -#include - -#include "base/atomicio.hh" -#include "base/circlebuf.hh" -#include "base/cprintf.hh" -#include "base/intmath.hh" - -using namespace std; - -CircleBuf::CircleBuf(int l) - : _rollover(false), _buflen(l), _size(0), _start(0), _stop(0) -{ - _buf = new char[_buflen]; -} - -CircleBuf::~CircleBuf() -{ - if (_buf) - delete [] _buf; -} - -void -CircleBuf::dump() -{ - cprintf("start = %10d, stop = %10d, buflen = %10d\n", - _start, _stop, _buflen); - fflush(stdout); - atomic_write(STDOUT_FILENO, _buf, _buflen); - atomic_write(STDOUT_FILENO, "<\n", 2); -} - -void -CircleBuf::flush() -{ - _start = 0; - _stop = 0; - _size = 0; - _rollover = false; -} - -void -CircleBuf::read(char *b, int len) -{ - _size -= len; - if (_size < 0) - _size = 0; - - if (_stop > _start) { - len = min(len, _stop - _start); - memcpy(b, _buf + _start, len); - _start += len; - } - else { - int endlen = _buflen - _start; - if (endlen > len) { - memcpy(b, _buf + _start, len); - _start += len; - } - else { - memcpy(b, _buf + _start, endlen); - _start = min(len - endlen, _stop); - memcpy(b + endlen, _buf, _start); - } - } -} - -void -CircleBuf::read(int fd, int len) -{ - _size -= len; - if (_size < 0) - _size = 0; - - if (_stop > _start) { - len = min(len, _stop - _start); - atomic_write(fd, _buf + _start, len); - _start += len; - } - else { - int endlen = _buflen - _start; - if (endlen > len) { - atomic_write(fd, _buf + _start, len); - _start += len; - } - else { - atomic_write(fd, _buf + _start, endlen); - _start = min(len - endlen, _stop); - atomic_write(fd, _buf, _start); - } - } -} - -void -CircleBuf::read(int fd) -{ - _size = 0; - - if (_stop > _start) { - atomic_write(fd, _buf + _start, _stop - _start); - } - else { - atomic_write(fd, _buf + _start, _buflen - _start); - atomic_write(fd, _buf, _stop); - } - - _start = _stop; -} - -void -CircleBuf::read(ostream &out) -{ - _size = 0; - - if (_stop > _start) { - out.write(_buf + _start, _stop - _start); - } - else { - out.write(_buf + _start, _buflen - _start); - out.write(_buf, _stop); - } - - _start = _stop; -} - -void -CircleBuf::readall(int fd) -{ - if (_rollover) - atomic_write(fd, _buf + _stop, _buflen - _stop); - - atomic_write(fd, _buf, _stop); - _start = _stop; -} - -void -CircleBuf::write(char b) -{ - write(&b, 1); -} - -void -CircleBuf::write(const char *b) -{ - write(b, strlen(b)); -} - -void -CircleBuf::write(const char *b, int len) -{ - if (len <= 0) - return; - - _size += len; - if (_size > _buflen) - _size = _buflen; - - int old_start = _start; - int old_stop = _stop; - - if (len >= _buflen) { - _start = 0; - _stop = _buflen; - _rollover = true; - memcpy(_buf, b + (len - _buflen), _buflen); - return; - } - - if (_stop + len <= _buflen) { - memcpy(_buf + _stop, b, len); - _stop += len; - } else { - int end_len = _buflen - old_stop; - _stop = len - end_len; - memcpy(_buf + old_stop, b, end_len); - memcpy(_buf, b + end_len, _stop); - _rollover = true; - } - - if ((old_start > old_stop && old_start < _stop) || - (old_start < old_stop && _stop < old_stop)) - _start = _stop + 1; -} 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