SDSL  3.0.0
Succinct Data Structure Library
memory_tracking.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
8 #ifndef INCLUDED_SDSL_MEMORY_TRACKING
9 #define INCLUDED_SDSL_MEMORY_TRACKING
10 
11 #include <sdsl/bits.hpp>
12 #include <sdsl/config.hpp>
13 #include <sdsl/uintx_t.hpp>
14 //#include <sdsl/ram_fs.hpp>
15 
16 #include <atomic>
17 #include <chrono>
18 #include <cstddef>
19 #include <cstdlib>
20 #include <cstring>
21 #include <fcntl.h>
22 #include <fstream>
23 #include <iostream>
24 #include <map>
25 #include <mutex>
26 #include <set>
27 #include <sstream>
28 #include <stack>
29 #include <vector>
30 
31 #include <sdsl/config.hpp>
32 
33 #ifdef _WIN32
34 #ifndef NOMINMAX
35 // windows.h has min/max macro which causes problems when using std::min/max
36 #define NOMINMAX 1
37 #endif
38 #include <io.h>
39 #include <windows.h>
40 #else
41 #include <unistd.h> // for getpid, file_size, clock_gettime
42 
43 #include <sys/mman.h>
44 #endif
45 
46 namespace sdsl
47 {
48 
49 // forward declare
50 void memory_monitor_record(int64_t);
51 
52 // minimal allocator from http://stackoverflow.com/a/21083096
53 template <typename T>
55 {
56  using value_type = T;
57 
58  track_allocator() = default;
59  template <class U>
61  {}
62 
63  T * allocate(std::size_t n)
64  {
65  if (n <= std::numeric_limits<std::size_t>::max() / sizeof(T))
66  {
67  size_t s = n * sizeof(T);
68  if (auto ptr = std::malloc(s))
69  {
71  return static_cast<T *>(ptr);
72  }
73  }
74  throw std::bad_alloc();
75  }
76  void deallocate(T * ptr, std::size_t n)
77  {
78  std::free(ptr);
79  std::size_t s = n * sizeof(T);
80  memory_monitor_record(-((int64_t)s));
81  }
82 };
83 
84 template <typename T, typename U>
85 inline bool operator==(const track_allocator<T> &, const track_allocator<U> &)
86 {
87  return true;
88 }
89 
90 template <typename T, typename U>
91 inline bool operator!=(const track_allocator<T> & a, const track_allocator<U> & b)
92 {
93  return !(a == b);
94 }
95 
96 // spin lock
97 class spin_lock
98 {
99  private:
100  std::atomic_flag m_slock;
101 
102  public:
103  spin_lock() { m_slock.clear(); }
104  void lock()
105  {
106  while (m_slock.test_and_set(std::memory_order_acquire))
107  { /* spin */
108  }
109  };
110  void unlock() { m_slock.clear(std::memory_order_release); };
111 };
112 
113 namespace ram_fs
114 {
115 typedef std::vector<char, track_allocator<char>> content_type;
116 }
117 
119 {
120  typedef std::map<std::string, ram_fs::content_type> mss_type;
121  typedef std::map<int, std::string> mis_type;
122  std::recursive_mutex m_rlock;
123 
126 
127  ramfs_storage() { m_fd_map[-1] = ""; }
128 
130 };
131 
132 struct mm_alloc
133 {
134  using timer = std::chrono::high_resolution_clock;
135  timer::time_point timestamp;
136  int64_t usage;
137  mm_alloc(timer::time_point t, int64_t u)
138  : timestamp(t)
139  , usage(u){};
140 };
141 
142 struct mm_event
143 {
144  using timer = std::chrono::high_resolution_clock;
145  std::string name;
146  std::vector<mm_alloc> allocations;
147  mm_event(std::string n, int64_t usage)
148  : name(n)
149  {
150  allocations.emplace_back(timer::now(), usage);
151  };
152  bool operator<(const mm_event & a) const
153  {
154  if (a.allocations.size() && this->allocations.size())
155  {
156  if (this->allocations[0].timestamp == a.allocations[0].timestamp)
157  {
158  return this->allocations.back().timestamp < a.allocations.back().timestamp;
159  }
160  else
161  {
162  return this->allocations[0].timestamp < a.allocations[0].timestamp;
163  }
164  }
165  return true;
166  }
167 };
168 
170 {
171  using timer = std::chrono::high_resolution_clock;
172  std::chrono::milliseconds log_granularity = std::chrono::milliseconds(20ULL);
173  int64_t current_usage = 0;
174  bool track_usage = false;
175  std::vector<mm_event> completed_events;
176  std::stack<mm_event> event_stack;
177  timer::time_point start_log;
178  timer::time_point last_event;
180 
182 
184 };
185 
186 template <format_type F>
187 void write_mem_log(std::ostream & out, const tracker_storage & m);
188 
190 {
191  public:
192  using timer = std::chrono::high_resolution_clock;
193 
195  {
196  bool add;
197  timer::time_point created;
198  mm_event_proxy(const std::string & name, int64_t usage, bool a)
199  : add(a)
200  {
201  if (add)
202  {
203  auto & m = *(the_monitor().m_tracker);
204  std::lock_guard<spin_lock> lock(m.spinlock);
205  m.event_stack.emplace(name, usage);
206  }
207  }
209  {
210  if (add)
211  {
212  auto & m = *(the_monitor().m_tracker);
213  std::lock_guard<spin_lock> lock(m.spinlock);
214  auto & cur = m.event_stack.top();
215  auto cur_time = timer::now();
216  cur.allocations.emplace_back(cur_time, m.current_usage);
217  m.completed_events.emplace_back(std::move(cur));
218  m.event_stack.pop();
219  // add a point to the new "top" with the same memory
220  // as before but just ahead in time
221  if (!m.event_stack.empty())
222  {
223  if (m.event_stack.top().allocations.size())
224  {
225  auto last_usage = m.event_stack.top().allocations.back().usage;
226  m.event_stack.top().allocations.emplace_back(cur_time, last_usage);
227  }
228  }
229  }
230  }
231  };
232 
233  private:
234  tracker_storage * m_tracker;
235  ramfs_storage * m_ram_fs;
236 
237  // disable construction of the object
239  {
240  m_tracker = new tracker_storage();
241  m_ram_fs = new ramfs_storage();
242  };
243 
244  ~memory_monitor()
245  {
246  if (m_tracker->track_usage) { stop(); }
247  delete m_ram_fs;
248  delete m_tracker;
249  }
250  memory_monitor(const memory_monitor &) = delete;
251  memory_monitor & operator=(const memory_monitor &) = delete;
252 
253  static memory_monitor & the_monitor()
254  {
255  static memory_monitor m;
256  return m;
257  }
258 
259  public:
260  static void granularity(std::chrono::milliseconds ms)
261  {
262  auto & m = *(the_monitor().m_tracker);
263  m.log_granularity = ms;
264  }
265  static int64_t peak()
266  {
267  auto & m = *(the_monitor().m_tracker);
268  int64_t max = 0;
269  for (auto events : m.completed_events)
270  {
271  for (auto alloc : events.allocations)
272  {
273  if (max < alloc.usage) { max = alloc.usage; }
274  }
275  }
276  return max;
277  }
278 
279  static ramfs_storage & ram_fs() { return *(the_monitor().m_ram_fs); }
280 
281  static void start()
282  {
283  auto & m = *(the_monitor().m_tracker);
284  m.track_usage = true;
285  // clear if there is something there
286  if (m.completed_events.size()) { m.completed_events.clear(); }
287  while (m.event_stack.size()) { m.event_stack.pop(); }
288  m.start_log = timer::now();
289  m.current_usage = 0;
290  m.last_event = m.start_log;
291  m.event_stack.emplace("unknown", 0);
292  }
293  static void stop()
294  {
295  auto & m = *(the_monitor().m_tracker);
296  while (!m.event_stack.empty())
297  {
298  m.completed_events.emplace_back(std::move(m.event_stack.top()));
299  m.event_stack.pop();
300  }
301  m.track_usage = false;
302  }
303  static void record(int64_t delta)
304  {
305  auto & m = *(the_monitor().m_tracker);
306  if (m.track_usage)
307  {
308  std::lock_guard<spin_lock> lock(m.spinlock);
309  auto cur = timer::now();
310  if (m.last_event + m.log_granularity < cur)
311  {
312  m.event_stack.top().allocations.emplace_back(cur, m.current_usage);
313  m.current_usage = m.current_usage + delta;
314  m.event_stack.top().allocations.emplace_back(cur, m.current_usage);
315  m.last_event = cur;
316  }
317  else
318  {
319  if (m.event_stack.top().allocations.size())
320  {
321  m.current_usage = m.current_usage + delta;
322  m.event_stack.top().allocations.back().usage = m.current_usage;
323  m.event_stack.top().allocations.back().timestamp = cur;
324  }
325  }
326  }
327  }
328 
329  static mm_event_proxy event(const std::string & name)
330  {
331  auto & m = *(the_monitor().m_tracker);
332  if (m.track_usage) { return mm_event_proxy(name, m.current_usage, true); }
333  return mm_event_proxy(name, m.current_usage, false);
334  }
335 
336  template <format_type F>
337  static void write_memory_log(std::ostream & out)
338  {
339  write_mem_log<F>(out, *(the_monitor().m_tracker));
340  }
341 };
342 
343 inline void memory_monitor_record(int64_t delta)
344 {
345  memory_monitor::record(delta);
346 }
347 
348 } // namespace sdsl
349 
350 #endif
bits.hpp contains the sdsl::bits class.
static ramfs_storage & ram_fs()
static void granularity(std::chrono::milliseconds ms)
static int64_t peak()
std::chrono::high_resolution_clock timer
static void record(int64_t delta)
static mm_event_proxy event(const std::string &name)
static void write_memory_log(std::ostream &out)
std::vector< char, track_allocator< char > > content_type
Namespace for the succinct data structure library.
void memory_monitor_record(int64_t)
bool operator==(const track_allocator< T > &, const track_allocator< U > &)
bool operator!=(const track_allocator< T > &a, const track_allocator< U > &b)
void write_mem_log(std::ostream &out, const tracker_storage &m)
mm_event_proxy(const std::string &name, int64_t usage, bool a)
std::chrono::high_resolution_clock timer
mm_alloc(timer::time_point t, int64_t u)
timer::time_point timestamp
std::vector< mm_alloc > allocations
std::chrono::high_resolution_clock timer
bool operator<(const mm_event &a) const
mm_event(std::string n, int64_t usage)
std::recursive_mutex m_rlock
std::map< int, std::string > mis_type
std::map< std::string, ram_fs::content_type > mss_type
T * allocate(std::size_t n)
void deallocate(T *ptr, std::size_t n)
track_allocator(const track_allocator< U > &)
std::vector< mm_event > completed_events
std::stack< mm_event > event_stack
timer::time_point start_log
std::chrono::milliseconds log_granularity
std::chrono::high_resolution_clock timer
timer::time_point last_event