Initial commitHEADmaster

1 files changed, 165 insertions, 0 deletions

diff --git a/core/checkpoint.hpp b/core/checkpoint.hpp
new file mode 100644
index 0000000..44457b9
--- /dev/null
+++ b/core/checkpoint.hpp
@@ -0,0 +1,165 @@
+#ifndef a4jYavu7NKcD1XX5TXFDvm6LUn8
+#define a4jYavu7NKcD1XX5TXFDvm6LUn8
+
+#include <boost/static_assert.hpp>
+
+#include "array.hpp"
+#include "everything_else.hpp"
+#include "simlimits.hpp"
+#include "string_helpers.hpp"
+#include "template_helpers.hpp"
+#include "time.hpp"
+#include "vector.hpp"
+
+template<typename T, uint32_t size>
+class Checkpoint {
+public:
+  typedef uint32_t ptr_t;
+
+  Checkpoint() = delete;
+  Checkpoint(const string name, const T initialValue);
+
+  // read access
+  inline Time getTime (const Time t, const ptr_t i) __attribute__ ((pure)); // DANGER
+  inline T    getValue(const Time t, const ptr_t i);
+  inline Time getTime (const Time t); // only with size == 1
+  inline T    getValue(const Time t); // only with size == 1
+
+  // write access
+  inline void set(const Time t, const ptr_t i, const T val);
+  inline void set(const Time t, const T val); // only with size == 1
+
+  void sync() const;
+
+  // page turn-over: stores all checkpoints and open a new checkpoint
+  // table for the next interval
+  void addCheckpoints(const Time newTime);
+
+  // time managment
+  static const ptr_t binTime(const Time t) { return t.ceilDiv(interval()); }
+  static constexpr Time interval() { return checkpointInterval; }
+
+  Time timeLimit, // current interval's time limits (infimum, maximum)
+    timeInf;
+  ptr_t currentInterval;
+
+  // file backings; they store for each interval, for each element the ...
+  Vector< Array< T, size > > content;  // ... last known content
+  Vector< Array< Time, size > > times; // ... associated time
+};
+
+template<typename T, uint32_t size>
+inline void Checkpoint<T, size>::set(const Time t, const ptr_t i, const T val) {
+  if (unlikely(t > timeLimit)) addCheckpoints(t);
+  times  (currentInterval).set(i, t);
+  content(currentInterval).set(i, val);
+}
+
+template<typename T, uint32_t size>
+inline void Checkpoint<T, size>::set(const Time t, const T val) {
+  BOOST_STATIC_ASSERT(size == 1);
+  set(t, 0, val);
+}
+
+template<typename T, uint32_t size>
+void Checkpoint<T, size>::sync() const {
+  content.sync();
+  times.sync();
+}
+
+template<typename T, uint32_t size>
+inline Time Checkpoint<T, size>::getTime(const Time t, const ptr_t i) {
+  if (unlikely(t > timeLimit)) addCheckpoints(t);
+  ptr_t ival = likely(t > timeInf) ? currentInterval : binTime(t);
+  return times(ival).get(i);
+}
+
+template<typename T, uint32_t size>
+inline Time Checkpoint<T, size>::getTime(const Time t) {
+  BOOST_STATIC_ASSERT(size == 1);
+  return getTime(t, 0);
+}
+
+template<typename T, uint32_t size>
+inline T Checkpoint<T, size>::getValue(const Time t, const ptr_t i) {
+  if (unlikely(t > timeLimit)) addCheckpoints(t);
+  ptr_t ival = likely(t > timeInf) ? currentInterval : binTime(t);
+  return content(ival).get(i);
+}
+
+template<typename T, uint32_t size>
+inline T Checkpoint<T, size>::getValue(const Time t) {
+  BOOST_STATIC_ASSERT(size == 1);
+  return getValue(t, 0);
+}
+
+template<typename T, uint32_t size>
+Checkpoint<T, size>::Checkpoint(const string name, const T initialValue) :
+  timeLimit(0),
+  timeInf(Time(0) - interval()),
+  currentInterval(0),
+  content("checkpoint_content_" + name, maxCheckpoints),
+  times(  "checkpoint_times_"   + name, maxCheckpoints)
+{
+  assert(content.barrierWrite() == times.barrierWrite());
+
+  // check if we are the first to use this checkpoint and have to initialize it
+  if (content.barrierWrite() == 0) {
+    content.barrierWrite() = 1;
+    times.  barrierWrite() = 1;
+    content.barrierRead() = 0;
+    times  .barrierRead() = 0;
+
+    for (ptr_t i=0; i<size; i++) {
+      content(0).set(i, initialValue);
+      times(0).set(i, 0);
+    }
+  }
+
+  currentInterval = content.barrierWrite() - 1;
+  timeLimit = Time(currentInterval) * interval();
+  timeInf = Time(currentInterval - 1) * interval();
+}
+
+template<typename T, uint32_t size>
+void Checkpoint<T, size>::addCheckpoints(const Time t) {
+  assert(content.barrierWrite() == times.barrierWrite()); // is a pre- and postcondition
+  // check if the write barrier has been updated externally
+  assert(currentInterval == content.barrierWrite() - 1);
+
+  // now create new checkpoint(s)
+  //
+  //     usually the loop below is executed exactly once; only in the
+  //     rare case of having no event in an interval it may be
+  //     executed several times; if this happens more often one should
+  //     increase the interval length significantly to avoid wasting
+  //     space
+  while (t > timeLimit) {
+    // copy content and associated times to the new checkpoint
+    // TODO: store chekcpoint number in object, use as cache
+    currentInterval = content.barrierWrite(); // next checkpoint's number
+    for (uint32_t i=0; i<size; i++) {
+      // one could simply memcpy() instead of below, but this way it is intuitive (?)
+      content(currentInterval).set(i, content(currentInterval - 1).get(i));
+      times  (currentInterval).set(i, times  (currentInterval - 1).get(i));
+    }
+
+    // increase barriers and time limit
+    content.barrierWrite()++;
+    times.  barrierWrite()++;
+    content.barrierRead() = content.barrierWrite() - 1;
+    times.  barrierRead() = times.  barrierWrite() - 1;
+    timeLimit = interval() * currentInterval;
+    timeInf =   interval() * (currentInterval - 1);
+  }
+
+  assert(content.barrierWrite() == times.barrierWrite());
+
+  // memory advise that we do not need the past
+  if (currentInterval) {
+    content.advise(0, currentInterval, MADV_DONTNEED);
+    times.  advise(0, currentInterval, MADV_DONTNEED);
+  }
+}
+
+#endif // a4jYavu7NKcD1XX5TXFDvm6LUn8