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).

3 files changed, 248 insertions, 244 deletions

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 <algorithm>
-#include <cstdio>
-#include <cstring>
-#include <string>
-
-#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 <algorithm>
+#include <cassert>
+#include <vector>
 
-#include <iosfwd>
+#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:
+ * <ul>
+ *   <li>_start <= _stop
+ *   <li>_start < capacity
+ *   <li>_stop < 2 * capacity
+ * </ul>
+ */
+template<typename T>
 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 <class OutputIterator>
+    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 <class OutputIterator>
+    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 <class InputIterator>
+    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<value_type> 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:
+ * <ul>
+ *    <li>Writes are checked to ensure that overflows can't happen.
+ *    <li>Unserialization ensures that the data in the checkpoint fits
+ *        in the buffer.
+ * </ul>
+ */
+template<typename T>
+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 <class OutputIterator>
+    void peek(OutputIterator out, size_t len) const { buf.peek(out, len); }
+    template <class OutputIterator>
+    void read(OutputIterator out, size_t len) { buf.read(out, len); }
+
+    template <class InputIterator>
+    void write(InputIterator in, size_t len) {
+        panic_if(size() + len > capacity(),
+                 "Trying to overfill FIFO buffer.\n");
+        buf.write(in, len);
+    }
+
+  private:
+    CircleBuf<value_type> buf;
 };
 
-#endif // __CIRCLEBUF_HH__
+
+template <typename T>
+static void
+arrayParamOut(CheckpointOut &cp, const std::string &name,
+              const CircleBuf<T> &param)
+{
+    std::vector<T> temp(param.size());
+    param.peek(temp.begin(), temp.size());
+    arrayParamOut(cp, name, temp);
+}
+
+template <typename T>
+static void
+arrayParamIn(CheckpointIn &cp, const std::string &name,
+             CircleBuf<T> &param)
+{
+    std::vector<T> temp;
+    arrayParamIn(cp, name, temp);
+
+    param.flush();
+    param.write(temp.cbegin(), temp.size());
+}
+
+template <typename T>
+static void
+arrayParamOut(CheckpointOut &cp, const std::string &name,
+              const Fifo<T> &param)
+{
+    std::vector<T> temp(param.size());
+    param.peek(temp.begin(), temp.size());
+    arrayParamOut(cp, name, temp);
+}
+
+template <typename T>
+static void
+arrayParamIn(CheckpointIn &cp, const std::string &name,
+             Fifo<T> &param)
+{
+    std::vector<T> 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__