src/base/circlebuf.hh

   1 /*
   2  * Copyright (c) 2015,2017-2018 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Redistribution and use in source and binary forms, with or without
  15  * modification, are permitted provided that the following conditions are
  16  * met: redistributions of source code must retain the above copyright
  17  * notice, this list of conditions and the following disclaimer;
  18  * redistributions in binary form must reproduce the above copyright
  19  * notice, this list of conditions and the following disclaimer in the
  20  * documentation and/or other materials provided with the distribution;
  21  * neither the name of the copyright holders nor the names of its
  22  * contributors may be used to endorse or promote products derived from
  23  * this software without specific prior written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  35  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 #ifndef __BASE_CIRCLEBUF_HH__
  39 #define __BASE_CIRCLEBUF_HH__
  40
  41 #include <algorithm>
  42 #include <cassert>
  43 #include <iterator>
  44 #include <vector>
  45
  46 #include "base/logging.hh"
  47 #include "sim/serialize.hh"
  48
  49 /**
  50  * Circular buffer backed by a vector.
  51  *
  52  * The data in the cricular buffer is stored in a standard vector.
  53  */
  54 template<typename T>
  55 class CircleBuf
  56 {
  57   private:
  58     std::vector<T> buffer;
  59     size_t start = 0;
  60     size_t used = 0;
  61     size_t maxSize;
  62
  63   public:
  64     using value_type = T;
  65
  66     explicit CircleBuf(size_t size) : buffer(size), maxSize(size) {}
  67
  68     bool empty() const { return used == 0; }
  69     size_t size() const { return used; }
  70     size_t capacity() const { return maxSize; }
  71
  72     /**
  73      * Throw away any data in the buffer.
  74      */
  75     void
  76     flush()
  77     {
  78         start = 0;
  79         used = 0;
  80     }
  81
  82     /**
  83      * Copy buffer contents without advancing the read pointer
  84      *
  85      * @param out Output iterator/pointer
  86      * @param len Number of elements to copy
  87      */
  88     template <class OutputIterator>
  89     void
  90     peek(OutputIterator out, size_t len) const
  91     {
  92         peek(out, 0, len);
  93     }
  94
  95     /**
  96      * Copy buffer contents without advancing the read pointer
  97      *
  98      * @param out Output iterator/pointer
  99      * @param offset Offset into the ring buffer
 100      * @param len Number of elements to copy
 101      */
 102     template <class OutputIterator>
 103     void
 104     peek(OutputIterator out, off_t offset, size_t len) const
 105     {
 106         panic_if(offset + len > used,
 107                  "Trying to read past end of circular buffer.");
 108
 109         if (!len)
 110             return;
 111
 112         // The iterator for the next byte to copy out.
 113         auto next_it = buffer.begin() + (start + offset) % maxSize;
 114         // How much there is to copy from until the end of the buffer.
 115         const size_t to_end = buffer.end() - next_it;
 116
 117         // If the data to be copied wraps, take care of the first part.
 118         if (to_end < len) {
 119             // Copy it.
 120             out = std::copy_n(next_it, to_end, out);
 121             // Start copying again at the start of buffer.
 122             next_it = buffer.begin();
 123             len -= to_end;
 124         }
 125         // Copy the remaining (or only) chunk of data.
 126         std::copy_n(next_it, len, out);
 127     }
 128
 129     /**
 130      * Copy buffer contents and advance the read pointer
 131      *
 132      * @param out Output iterator/pointer
 133      * @param len Number of elements to read
 134      */
 135     template <class OutputIterator>
 136     void
 137     read(OutputIterator out, size_t len)
 138     {
 139         peek(out, len);
 140         used -= len;
 141         start += len;
 142     }
 143
 144     /**
 145      * Add elements to the end of the ring buffers and advance. Writes which
 146      * would exceed the capacity of the queue fill the avaialble space, and
 147      * then continue overwriting the head of the queue. The head advances as
 148      * if that data had been read out.
 149      *
 150      * @param in Input iterator/pointer
 151      * @param len Number of elements to read
 152      */
 153     template <class InputIterator>
 154     void
 155     write(InputIterator in, size_t len)
 156     {
 157         if (!len)
 158             return;
 159
 160         // Writes that are larger than the buffer size are allowed, but only
 161         // the last part of the date will be written since the rest will be
 162         // overwritten and not remain in the buffer.
 163         if (len > maxSize) {
 164             in += len - maxSize;
 165             flush();
 166             len = maxSize;
 167         }
 168
 169         // How much existing data will be overwritten?
 170         const size_t total_bytes = used + len;
 171         const size_t overflow = total_bytes > maxSize ?
 172                                 total_bytes - maxSize : 0;
 173         // The iterator of the next byte to add.
 174         auto next_it = buffer.begin() + (start + used) % maxSize;
 175         // How much there is to copy to the end of the buffer.
 176         const size_t to_end = buffer.end() - next_it;
 177
 178         // If this addition wraps, take care of the first part here.
 179         if (to_end < len) {
 180             // Copy it.
 181             std::copy_n(in, to_end, next_it);
 182             // Update state to reflect what's left.
 183             next_it = buffer.begin();
 184             std::advance(in, to_end);
 185             len -= to_end;
 186             used += to_end;
 187         }
 188         // Copy the remaining (or only) chunk of data.
 189         std::copy_n(in, len, next_it);
 190         used += len;
 191
 192         // Don't count data that was overwritten.
 193         used -= overflow;
 194         start += overflow;
 195     }
 196 };
 197
 198 /**
 199  * Simple FIFO implementation backed by a circular buffer.
 200  *
 201  * This class provides the same basic functionallity as the circular
 202  * buffer with the folling differences:
 203  * <ul>
 204  *    <li>Writes are checked to ensure that overflows can't happen.
 205  *    <li>Unserialization ensures that the data in the checkpoint fits
 206  *        in the buffer.
 207  * </ul>
 208  */
 209 template<typename T>
 210 class Fifo
 211 {
 212   public:
 213     typedef T value_type;
 214
 215   public:
 216     Fifo(size_t size) : buf(size) {}
 217
 218     bool empty() const { return buf.empty(); }
 219     size_t size() const { return buf.size(); }
 220     size_t capacity() const { return buf.capacity(); }
 221
 222     void flush() { buf.flush(); }
 223
 224     template <class OutputIterator>
 225     void peek(OutputIterator out, size_t len) const { buf.peek(out, len); }
 226     template <class OutputIterator>
 227     void read(OutputIterator out, size_t len) { buf.read(out, len); }
 228
 229     template <class InputIterator>
 230     void
 231     write(InputIterator in, size_t len)
 232     {
 233         panic_if(size() + len > capacity(), "Trying to overfill FIFO buffer.");
 234         buf.write(in, len);
 235     }
 236
 237   private:
 238     CircleBuf<value_type> buf;
 239 };
 240
 241
 242 template <typename T>
 243 void
 244 arrayParamOut(CheckpointOut &cp, const std::string &name,
 245               const CircleBuf<T> &param)
 246 {
 247     std::vector<T> temp(param.size());
 248     param.peek(temp.begin(), temp.size());
 249     arrayParamOut(cp, name, temp);
 250 }
 251
 252 template <typename T>
 253 void
 254 arrayParamIn(CheckpointIn &cp, const std::string &name, CircleBuf<T> &param)
 255 {
 256     std::vector<T> temp;
 257     arrayParamIn(cp, name, temp);
 258
 259     param.flush();
 260     param.write(temp.cbegin(), temp.size());
 261 }
 262
 263 template <typename T>
 264 void
 265 arrayParamOut(CheckpointOut &cp, const std::string &name, const Fifo<T> &param)
 266 {
 267     std::vector<T> temp(param.size());
 268     param.peek(temp.begin(), temp.size());
 269     arrayParamOut(cp, name, temp);
 270 }
 271
 272 template <typename T>
 273 void
 274 arrayParamIn(CheckpointIn &cp, const std::string &name, Fifo<T> &param)
 275 {
 276     std::vector<T> temp;
 277     arrayParamIn(cp, name, temp);
 278
 279     fatal_if(param.capacity() < temp.size(),
 280              "Trying to unserialize data into too small FIFO");
 281
 282     param.flush();
 283     param.write(temp.cbegin(), temp.size());
 284 }
 285
 286 #endif // __BASE_CIRCLEBUF_HH__