1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
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
|
