SDSL  3.0.0
Succinct Data Structure Library
memory_management.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_MANAGEMENT
9 #define INCLUDED_SDSL_MEMORY_MANAGEMENT
10 
11 #include <algorithm>
12 #include <chrono>
13 
14 #include <sdsl/bits.hpp>
15 #include <sdsl/config.hpp>
16 #include <sdsl/memory_tracking.hpp>
17 #include <sdsl/ram_fs.hpp>
18 #include <sdsl/uintx_t.hpp>
19 
20 namespace sdsl
21 {
22 
23 inline void output_event_json(std::ostream & out, const mm_event & ev, const tracker_storage & m)
24 {
25  using namespace std::chrono;
26  out << "\t\t"
27  << "\"name\" : "
28  << "\"" << ev.name << "\",\n";
29  out << "\t\t"
30  << "\"usage\" : ["
31  << "\n";
32  for (size_t j = 0; j < ev.allocations.size(); j++)
33  {
34  out << "\t\t\t[" << duration_cast<milliseconds>(ev.allocations[j].timestamp - m.start_log).count() << ","
35  << ev.allocations[j].usage << "]";
36  if (j + 1 < ev.allocations.size()) { out << ",\n"; }
37  else
38  {
39  out << "\n";
40  }
41  }
42  out << "\t\t"
43  << "]\n";
44 }
45 
46 template <>
47 inline void write_mem_log<JSON_FORMAT>(std::ostream & out, const tracker_storage & m)
48 {
49  auto events = m.completed_events;
50  std::sort(events.begin(), events.end());
51 
52  // output
53  out << "[\n";
54  for (size_t i = 0; i < events.size(); i++)
55  {
56  out << "\t{\n";
57  output_event_json(out, events[i], m);
58  if (i < events.size() - 1) { out << "\t},\n"; }
59  else
60  {
61  out << "\t}\n";
62  }
63  }
64  out << "]\n";
65 }
66 
67 inline std::string create_mem_html_header()
68 {
69  std::stringstream jsonheader;
70  jsonheader << "<html>\n"
71  << "<head>\n"
72  << "<meta charset=\"utf-8\">\n"
73  << "<style>\n"
74  << " body { font: 11px sans-serif; }\n"
75  << " .rule { height: 90%; position: absolute; border-right: 1px dotted #000; "
76  "text-align: right; }\n"
77  << "</style>\n"
78  << "<title>sdsl memory usage visualization</title>\n"
79  << "<script src=\"http://d3js.org/d3.v3.js\"></script>\n"
80  << "</head>\n"
81  << "<body marginwidth=\"0\" marginheight=\"0\">\n"
82  << "<button><a id=\"download\">Save as SVG</a></button>\n"
83  << "<div class=\"chart\"><div id=\"visualization\"></div></div><script>\n";
84  return jsonheader.str();
85 }
86 
87 inline std::string create_mem_js_body(const std::string & jsonObject)
88 {
89  std::stringstream jsonbody;
90  jsonbody << "var events = " << jsonObject << ";\n"
91  << "var w = window,d = document,e = d.documentElement,g = d.getElementsByTagName('body')[0],\n"
92  << " xw = w.innerWidth || e.clientWidth || g.clientWidth,\n"
93  << " yh = w.innerHeight || e.clientHeight || g.clientHeight;\n\n"
94  << "var margin = {top: 20,right: 80,bottom: 120,left: 120},\n"
95  << " width = xw - margin.left - margin.right,height = yh - margin.top - margin.bottom;\n"
96  << "var x = d3.scale.linear().range([0, width]);\n"
97  << "var y = d3.scale.linear().range([height, 0]);\n"
98  << "var xAxis = d3.svg.axis().scale(x).orient(\"bottom\");\n"
99  << "var yAxis = d3.svg.axis().scale(y).orient(\"left\").ticks(5);\n"
100  << "var color = d3.scale.category10();\n"
101  << "var x_max = d3.max(events, function (d) { return d3.max(d.usage, function (u) { return u[0] / "
102  "1000;})})\n"
103  << "var y_max = d3.max(events, function (d) { return d3.max(d.usage, function (u) { return 1.1 * u[1] / "
104  "(1024 * 1024);})})\n"
105  << "var peak = d3.max(events, function (d) { return d3.max(d.usage, function (u) { return u[1]; })})\n"
106  << "var data = []\nevents.forEach(function (d) { data = data.concat(d.usage); });\n"
107  << "var peakelem = data.filter(function (a) { return a[1] == peak; });\n"
108  << "var peakelem = peakelem.splice(0,1);\n"
109  << "x.domain([0, x_max]);\n y.domain([0, y_max]);\n"
110  << "var svg = d3.select(\"#visualization\").append(\"svg\")\n"
111  << " .attr(\"width\", width + margin.left + margin.right)\n"
112  << " .attr(\"height\", height + margin.top + margin.bottom)\n"
113  << " .attr(\"xmlns\", \"http://www.w3.org/2000/svg\")\n"
114  << " .append(\"g\").attr(\"transform\",\"translate(\" + margin.left + \",\" + margin.top + \")\");\n\n"
115  << " svg.append(\"g\").attr(\"class\", \"xaxis\").attr(\"transform\", \"translate(0,\" + height + "
116  "\")\")\n"
117  << " .call(xAxis).append(\"text\").attr(\"text-anchor\", \"end\")\n"
118  << " .attr(\"shape-rendering\", \"crispEdges\").attr(\"x\", width / 2 + 50).attr(\"y\", "
119  "70).attr(\"shape-rendering\", \"crispEdges\")\n"
120  << " .attr(\"font-family\", \"sans-serif\").attr(\"font-size\", \"20px\").text(\"Time (seconds)\");\n\n"
121  << "svg.append(\"g\").attr(\"class\", \"yaxis\").call(yAxis).append(\"text\").attr(\"transform\", "
122  "\"rotate(-90)\").attr(\"x\", -height / 2 + 50)\n"
123  << " .attr(\"y\", -80).attr(\"shape-rendering\", \"crispEdges\").attr(\"font-family\", "
124  "\"sans-serif\").attr(\"font-size\", \"20px\").style(\"text-anchor\", \"end\")\n"
125  << " .text(\"Memory Usage (MiB)\");\n\n"
126  << "svg.selectAll(\".tick text\").style(\"font-size\", \"20px\");\n"
127  << "svg.selectAll(\".xaxis .tick text\").attr(\"dy\", 23);\nsvg.selectAll(\".yaxis .tick "
128  "text\").attr(\"dx\", -10);\n"
129  << "svg.selectAll(\"line\").attr(\"fill\", \"none\").attr(\"stroke\", "
130  "\"black\")\nsvg.selectAll(\"path\").attr(\"fill\", \"none\").attr(\"stroke\", \"black\")\n\n"
131  << "svg.selectAll(\"line.horizontalGrid\").data(y.ticks(5)).enter().append(\"line\")\n"
132  << " .attr({\"class\": \"horizontalGrid\",\"x1\": 0,\"x2\": width,\"y1\": function (d) { return y(d);},\n"
133  << " \"y2\": function (d) { return y(d); }, \"fill\": \"none\", \"shape-rendering\": \"crispEdges\",\n"
134  << " \"stroke\": \"lightgrey\",\"stroke-dasharray\": \"10,10\",\"stroke-width\": \"1.5px\"});\n\n"
135  << "var area = d3.svg.area().x(function (d) { return x(d[0] / 1000);}).y0(height).y1(function (d) { "
136  "return y(d[1] / (1024 * 1024))});\n\n"
137  << "var ev = svg.selectAll(\".event\").data(events).enter().append(\"svg:path\").attr(\"class\", "
138  "\"area\")\n"
139  << " .attr(\"fill\", function (d) { return d3.rgb(color(d.name)); })\n"
140  << " .attr(\"d\", function (d) { return area(d.usage) })\n"
141  << " .style(\"stroke\", function (d) { return d3.rgb(color(d.name)).darker(2);}).style(\"stroke-width\", "
142  "\"2px\")\n\n"
143  << "svg.selectAll(\".dot\").data(peakelem).enter().append(\"circle\").attr(\"r\", 3).attr(\"fill\", "
144  "\"red\")\n"
145  << " .attr(\"cx\", function (d) {return x(d[0] / 1000)})\n"
146  << " .attr(\"cy\", function (d) {return y(d[1] / (1024 * 1024))})\n"
147  << " .attr(\"fill\", \"red\").attr(\"stroke-width\", 2).attr(\"stroke\", \"#cc0000\")\n\n"
148  << "svg.selectAll(\".dot\").data(peakelem).enter().append(\"svg:text\")\n"
149  << " .attr(\"x\", function (d) {return x(d[0] / 1000)}).attr(\"y\", function (d) {return y(d[1] / (1024 "
150  "* 1024) * 1.025)})\n"
151  << " .text(function (d) {return \"Peak Usage: \" + Math.round(d[1] / (1024 * 1024)) + \" MB\"})\n"
152  << " .attr(\"font-size\", 12).attr(\"fill\", \"red\");\n\n"
153  << "svg.selectAll(\".dot\").data(peakelem).enter().append(\"circle\")\n"
154  << " .attr(\"r\", 5).attr(\"fill\", \"red\")\n"
155  << " .attr(\"cx\", function (d) {return x(d[0] / 1000)})\n"
156  << " .attr(\"cy\", function (d) {return y(d[1] / (1024 * 1024))})\n"
157  << " .attr(\"fill\", \"none\").attr(\"stroke-width\", 2).attr(\"stroke\", "
158  "\"#cc0000\").each(pulsepeak());\n\n"
159  << "function pulsepeak() { return function (d, i, j) {\n"
160  << " d3.select(this).attr(\"r\", 5).style(\"stroke-opacity\", 1.0).transition()\n"
161  << " .ease(\"linear\").duration(1000).attr(\"r\", 10).style(\"stroke-opacity\", 0.0).each(\"end\", "
162  "pulsepeak());};}\n\n"
163  << "var vertical = d3.select(\".chart\").append(\"div\").attr(\"class\", \"remove\")\n"
164  << " .style(\"position\", \"absolute\").style(\"z-index\", \"19\").style(\"width\", \"1px\")\n"
165  << " .style(\"height\", height - margin).style(\"top\", \"30px\").style(\"bottom\", \"50px\")\n"
166  << " .style(\"left\", \"0px\").style(\"opacity\", \"0.4\").style(\"background\", \"black\");\n\n"
167  << "var tooltip = d3.select(\".chart\").append(\"div\").attr(\"class\", \"remove\")\n"
168  << " .style(\"position\", \"absolute\").style(\"z-index\", \"20\").style(\"visibility\", "
169  "\"hidden\").style(\"top\", \"10px\");\n\n"
170  << "var circle = svg.append(\"circle\").attr(\"cx\", 100).attr(\"cy\", 350).attr(\"r\", 3).attr(\"fill\", "
171  "\"black\").style(\"opacity\", \"0\")\n\n"
172  << "d3.select(\"svg\").on(\"mousemove\", function () {\n"
173  << " mousex = d3.mouse(this);\n"
174  << " if (mousex[0] < margin.left + 3 || mousex[0] >= xw - margin.right) {\n"
175  << " vertical.style(\"opacity\", \"0\"); tooltip.style(\"opacity\", \"0\"); circle.style(\"opacity\", "
176  "\"0\")\n"
177  << " } else {\n"
178  << " var xvalue = x.invert(mousex[0] - margin.left); var pos = findPosition(xvalue)\n"
179  << " vertical.style(\"opacity\", \"0.4\"); tooltip.style(\"opacity\", \"1\"); "
180  "circle.style(\"opacity\", \"1\")\n"
181  << " circle.attr(\"cx\", pos.x).attr(\"cy\", pos.y); vertical.style(\"left\", mousex[0] + "
182  "\"px\");tooltip.style(\"left\", mousex[0] + 15 + \"px\")\n"
183  << " tooltip.html(\"<p>\" + xvalue.toFixed(2) + \" Seconds <br>\" + Math.round(pos.mem) + \" MiB <br> "
184  "\" + pos.name + "
185  << " \"<br> Phase Time: \" + pos.ptime + \" Seconds </p>\").style(\"visibility\", \"visible\");\n"
186  << " }\n})"
187  << ".on(\"mouseover\", function () {\n"
188  << " mousex = d3.mouse(this);\n if (mousex[0] < margin.left + 3 || mousex[0] > xw - margin.right) {\n"
189  << " vertical.style(\"opacity\", \"0\")\n } else {\n vertical.style(\"opacity\", "
190  "\"0.4\");vertical.style(\"left\", mousex[0] + 7 + \"px\")\n}})\n"
191  << "d3.select(\"#download\").on(\"click\", function () {\n"
192  << "d3.select(this).attr(\"href\", 'data:application/octet-stream;base64,' + "
193  "btoa(d3.select(\"#visualization\").html())).attr(\"download\", \"viz.svg\")})\n\n"
194  << "function "
195  "findPosition(e){correctArea=d3.selectAll(\".area\").filter(function(t){if(t.usage[0][0]<=e*1e3&&t."
196  "usage[t.usage.length-1][0]>=e*1e3){return true}"
197  << "return false});if(correctArea.empty()){return 0}var t=new "
198  "Array;correctArea[0].forEach(function(n){t.push(findYValueinArea(n,e))});"
199  << "max_elem=d3.max(t,function(e){return e.mem});var n=t.filter(function(e){return "
200  "e.mem==max_elem});return n[0]}"
201  << "function findYValueinArea(e,t){len=e.getTotalLength();var n=0;var r=len;for(var i=0;i<=len;i+=50){var "
202  "s=e.getPointAtLength(i);"
203  << "var o=x.invert(s.x);var u=y.invert(s.y);if(u>0&&o>t){n=Math.max(0,i-50);r=i;break}}var "
204  "a=e.getPointAtLength(0);"
205  << "var f=1;while(n<r){var "
206  "l=(r+n)/"
207  "2;a=e.getPointAtLength(l);target_x=x.invert(a.x);if((l==n||l==r)&&Math.abs(target_x-t)>.01){break}if("
208  "target_x>t)r=l;"
209  << "else if(target_x<t)n=l;else{break}if(f>50){break}f++}var c=new "
210  "function(){this.mem=y.invert(a.y);this.name=e.__data__.name;"
211  << "this.min=d3.min(e.__data__.usage,function(e){return "
212  "e[0]/1e3});this.max=d3.max(e.__data__.usage,function(e){return e[0]/1e3});"
213  << "this.ptime=Math.round(this.max-this.min);this.x=a.x;this.y=a.y};return c}\n</script></body></html>";
214  return jsonbody.str();
215 }
216 
217 template <>
218 inline void write_mem_log<HTML_FORMAT>(std::ostream & out, const tracker_storage & m)
219 {
220  std::stringstream json_data;
221  write_mem_log<JSON_FORMAT>(json_data, m);
222 
223  out << create_mem_html_header();
224  out << create_mem_js_body(json_data.str());
225 }
226 
227 #pragma pack(push, 1)
228 typedef struct mm_block
229 {
230  size_t size;
231  struct mm_block * next;
232  struct mm_block * prev;
234 
235 typedef struct bfoot
236 {
237  size_t size;
239 #pragma pack(pop)
240 
241 #define ALIGNMENT sizeof(uint64_t)
242 #define ALIGNSPLIT(size) (((size)) & ~0x7)
243 #define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
244 #define MM_BLOCK_OVERHEAD (sizeof(size_t) + sizeof(size_t))
245 #define MIN_BLOCKSIZE (ALIGN(sizeof(mm_block_t) + sizeof(mm_block_foot_t)))
246 #define UNMASK_SIZE(size) ((size) & ~1)
247 #define ISFREE(size) ((size)&1)
248 #define SETFREE(size) ((size) | 1)
249 #define SPLIT_THRESHOLD (MIN_BLOCKSIZE)
250 
251 inline mm_block_t * block_cur(void * ptr)
252 {
253  mm_block_t * bptr = (mm_block_t *)((uint8_t *)ptr - sizeof(size_t));
254  return bptr;
255 }
256 
257 /* given a block retrieve the previous block if any. nullptr otherwise */
258 inline mm_block_t * block_prev(mm_block_t * cur_bptr, mm_block_t * first)
259 {
260  /* start of the heap? */
261  if (cur_bptr == first) return nullptr;
262  mm_block_foot_t * prev_foot = (mm_block_foot_t *)((uint8_t *)cur_bptr - sizeof(mm_block_foot_t));
263  mm_block_t * prev_bptr = (mm_block_t *)((uint8_t *)cur_bptr - UNMASK_SIZE(prev_foot->size));
264  return prev_bptr;
265 }
266 
267 /* given a block retrieve the next block if any. nullptr otherwise */
268 inline mm_block_t * block_next(mm_block_t * cur_bptr, uint8_t * top)
269 {
270  /* end of the heap? */
271  if ((uint8_t *)((uint8_t *)cur_bptr + UNMASK_SIZE(cur_bptr->size)) >= top) return nullptr;
272 
273  mm_block_t * next_bptr = (mm_block_t *)((uint8_t *)cur_bptr + UNMASK_SIZE(cur_bptr->size));
274  return next_bptr;
275 }
276 
277 /* calculate the size of a memory block */
278 inline size_t block_size(void * ptr)
279 {
280  mm_block_t * bptr = block_cur(ptr);
281  return UNMASK_SIZE(bptr->size);
282 }
283 
284 inline bool block_isfree(mm_block_t * ptr)
285 {
286  return ((ptr->size) & 1ULL);
287 }
288 
289 /* is the next block free */
290 inline bool block_nextfree(mm_block_t * ptr, uint8_t * top)
291 {
292  mm_block_t * next = block_next(ptr, top);
293  if (next && block_isfree(next)) return true;
294  return false;
295 }
296 
297 /* is the prev block free */
298 inline bool block_prevfree(mm_block_t * ptr, mm_block_t * begin)
299 {
300  mm_block_t * prev = block_prev(ptr, begin);
301  if (prev && block_isfree(prev)) return 1;
302  return 0;
303 }
304 
305 /* update the footer with a new size */
306 inline void foot_update(mm_block_t * ptr, size_t size)
307 {
308  mm_block_foot_t * fptr = (mm_block_foot_t *)((uint8_t *)ptr + UNMASK_SIZE(size) - sizeof(mm_block_foot_t));
309  fptr->size = size;
310 }
311 
312 /* update the block with a new size */
313 inline void block_update(mm_block_t * ptr, size_t size)
314 {
315  ptr->size = size;
316  foot_update(ptr, size);
317 }
318 
319 /* return the pointer to the "data" */
320 inline void * block_data(mm_block_t * ptr)
321 {
322  return (void *)((uint8_t *)ptr + sizeof(size_t));
323 }
324 
325 /* return size of the data that can be stored in the block */
326 inline size_t block_getdatasize(mm_block_t * ptr)
327 {
328  size_t blocksize = UNMASK_SIZE(ptr->size);
329  return blocksize - sizeof(size_t) - sizeof(mm_block_foot_t);
330 }
331 
332 /* mark the block as free */
333 inline void block_markfree(mm_block_t * ptr)
334 {
335  block_update(ptr, SETFREE(ptr->size));
336 }
337 
338 /* mark the block as used */
339 inline void block_markused(mm_block_t * ptr)
340 {
341  block_update(ptr, UNMASK_SIZE(ptr->size));
342 }
343 
344 #ifndef _WIN32
345 
347 {
348  private:
349  uint8_t * m_base = nullptr;
350  mm_block_t * m_first_block = nullptr;
351  uint8_t * m_top = nullptr;
352  size_t m_total_size = 0;
353  std::multimap<size_t, mm_block_t *> m_free_large;
354 
355  private:
356  inline void block_print(int id, mm_block_t * bptr)
357  {
358  fprintf(stdout,
359  "%d addr=%p size=%lu (%lu) free=%d\n",
360  id,
361  ((void *)bptr),
362  UNMASK_SIZE(bptr->size),
363  bptr->size,
364  block_isfree(bptr));
365  fflush(stdout);
366  }
367 
368  inline uint64_t extract_number(std::string & line)
369  {
370  std::string num_str;
371  for (size_t i = line.size() - 1; i + 1 >= 1; i--)
372  {
373  if (isdigit(line[i])) { num_str.insert(num_str.begin(), line[i]); }
374  else
375  {
376  if (num_str.size() > 0) { break; }
377  }
378  }
379  return std::strtoull(num_str.c_str(), nullptr, 10);
380  }
381 
382  inline uint64_t extract_multiplier(std::string & line)
383  {
384  uint64_t num = 1;
385  if (line[line.size() - 2] == 'k' || line[line.size() - 2] == 'K') { num = 1024; }
386  if (line[line.size() - 2] == 'm' || line[line.size() - 2] == 'M') { num = 1024 * 1024; }
387  if (line[line.size() - 2] == 'g' || line[line.size() - 2] == 'G') { num = 1024 * 1024 * 1024; }
388  return num;
389  }
390 
391  size_t determine_available_hugepage_memory()
392  {
393  size_t size_in_bytes = 0;
394  size_t page_size_in_bytes = 0;
395  size_t num_free_pages = 0;
396  const std::string meminfo_file = "/proc/meminfo";
397  const std::string ps_str = "Hugepagesize:";
398  const std::string pf_str = "HugePages_Free:";
399  std::ifstream mifs(meminfo_file);
400  if (mifs.is_open())
401  {
402  // find size of one page
403  std::string line;
404  while (std::getline(mifs, line))
405  {
406  auto ps = std::mismatch(ps_str.begin(), ps_str.end(), line.begin());
407  if (ps.first == ps_str.end()) { page_size_in_bytes = extract_number(line) * extract_multiplier(line); }
408  auto pf = std::mismatch(pf_str.begin(), pf_str.end(), line.begin());
409  if (pf.first == pf_str.end()) { num_free_pages = extract_number(line); }
410  }
411  size_in_bytes = page_size_in_bytes * num_free_pages;
412  }
413  else
414  {
415  throw std::system_error(ENOMEM,
416  std::system_category(),
417  "hugepage_allocator could not automatically determine available hugepages");
418  }
419  return size_in_bytes;
420  }
421 
422  void coalesce_block(mm_block_t * block)
423  {
424  // std::cout << "coalesce_block()" << std::endl;
425  mm_block_t * newblock = block;
426  if (block_nextfree(block, m_top))
427  {
428  mm_block_t * next = block_next(block, m_top);
429  /* remove the "next" block from the free list */
430  remove_from_free_set(next);
431  /* add the size of our block */
432  block_update(block, UNMASK_SIZE(block->size) + UNMASK_SIZE(next->size));
433  }
434  if (block_prevfree(block, m_first_block))
435  {
436  mm_block_t * prev = block_prev(block, m_first_block);
437  /* we remove the old prev block and readd it to the correct
438  size list if necessary */
439  remove_from_free_set(prev);
440  newblock = prev;
441  block_update(prev, UNMASK_SIZE(prev->size) + UNMASK_SIZE(block->size));
442  }
443  if (newblock)
444  {
445  block_markfree(newblock);
446  insert_into_free_set(newblock);
447  }
448  }
449 
450  void split_block(mm_block_t * bptr, size_t size)
451  {
452  // std::cout << "split_block("<< (void*)bptr << ")" << std::endl;
453  size_t blocksize = UNMASK_SIZE(bptr->size);
454  // std::cout << "cur_block_size = " << blocksize << std::endl;
455  /* only split if we get at least a small block
456  out of it */
457  int64_t newblocksize = ALIGNSPLIT(blocksize - ALIGN(size + MM_BLOCK_OVERHEAD));
458  // std::cout << "new_block_size = " << newblocksize << std::endl;
459  if (newblocksize >= (int64_t)SPLIT_THRESHOLD)
460  {
461  /* update blocksize of old block */
462  // std::cout << "block_update = " << blocksize-newblocksize << std::endl;
463  block_update(bptr, blocksize - newblocksize);
464  mm_block_t * newblock = (mm_block_t *)((char *)bptr + (blocksize - newblocksize));
465  // std::cout << "new block ptr = " << (void*)newblock << std::endl;
466  block_update(newblock, newblocksize);
467  coalesce_block(newblock);
468  }
469  }
470 
471  uint8_t * hsbrk(size_t size)
472  {
473  ptrdiff_t left = (ptrdiff_t)m_total_size - (m_top - m_base);
474  if (left < (ptrdiff_t)size)
475  { // enough space left?
476  throw std::system_error(ENOMEM,
477  std::system_category(),
478  "hugepage_allocator: not enough hugepage memory available");
479  }
480  uint8_t * new_mem = m_top;
481  m_top += size;
482  return new_mem;
483  }
484 
485  mm_block_t * new_block(size_t size)
486  {
487  // std::cout << "new_block(" << size << ")" << std::endl;
490  mm_block_t * ptr = (mm_block_t *)hsbrk(size);
491  block_update(ptr, size);
492  return ptr;
493  }
494 
495  void remove_from_free_set(mm_block_t * block)
496  {
497  // std::cout << "remove_from_free_set()" << std::endl;
498  auto eq_range = m_free_large.equal_range(block->size);
499  // find the block amoung the blocks with equal size
500  auto itr = eq_range.first;
501  auto last = eq_range.second;
502  auto found = m_free_large.end();
503  while (itr != last)
504  {
505  if (itr->second == block) { found = itr; }
506  ++itr;
507  }
508  if (found == m_free_large.end()) { found = last; }
509  m_free_large.erase(found);
510  }
511 
512  void insert_into_free_set(mm_block_t * block)
513  {
514  // std::cout << "insert_into_free_set("<< (void*)block << "," << UNMASK_SIZE(block->size) << ")" << std::endl;
515  // std::cout << "insert_into_free_set("<< (void*)block << "," << block->size << ")" << std::endl;
516  m_free_large.insert({ block->size, block });
517  }
518 
519  mm_block_t * find_free_block(size_t size_in_bytes)
520  {
521  // std::cout << "find_free_block(" << size_in_bytes << ")" << std::endl;
522 
523  mm_block_t * bptr = nullptr;
524  auto free_block = m_free_large.lower_bound(size_in_bytes);
525  if (free_block != m_free_large.end())
526  {
527  bptr = free_block->second;
528  m_free_large.erase(free_block);
529  }
530  return bptr;
531  }
532 
533  mm_block_t * last_block()
534  {
535  mm_block_t * last = nullptr;
536  // std::cout << "m_top = " << (void*)m_top << std::endl;
537  // std::cout << "m_base = " << (void*)m_base << std::endl;
538  if (m_top != m_base)
539  {
540  mm_block_foot_t * fptr = (mm_block_foot_t *)(m_top - sizeof(size_t));
541  // std::cout << "foot of last = " << (void*)fptr << std::endl;
542  // std::cout << "size of last = " << UNMASK_SIZE(fptr->size) << std::endl;
543  last = (mm_block_t *)(((uint8_t *)fptr) - UNMASK_SIZE(fptr->size) + sizeof(size_t));
544  // std::cout << "last = " << (void*)last << std::endl;
545  }
546  return last;
547  }
548 
549  void print_heap()
550  {
551  mm_block_t * bptr = m_first_block;
552  size_t id = 0;
553  while (bptr)
554  {
555  block_print(id, bptr);
556  id++;
557  bptr = block_next(bptr, m_top);
558  }
559  }
560 
561  public:
562  void init(SDSL_UNUSED size_t size_in_bytes = 0)
563  {
564 #ifdef MAP_HUGETLB
565  if (size_in_bytes == 0) { size_in_bytes = determine_available_hugepage_memory(); }
566 
567  m_total_size = size_in_bytes;
568  m_base = (uint8_t *)mmap(nullptr,
569  m_total_size,
570  (PROT_READ | PROT_WRITE),
571  (MAP_HUGETLB | MAP_ANONYMOUS | MAP_PRIVATE),
572  0,
573  0);
574  if (m_base == MAP_FAILED)
575  {
576  throw std::system_error(ENOMEM, std::system_category(), "hugepage_allocator could not allocate hugepages");
577  }
578  else
579  {
580  // init the allocator
581  m_top = m_base;
582  m_first_block = (mm_block_t *)m_base;
583  }
584 #else
585  throw std::system_error(ENOMEM,
586  std::system_category(),
587  "hugepage_allocator: MAP_HUGETLB / hugepage support not available");
588 #endif
589  }
590 
591  void * mm_realloc(void * ptr, size_t size)
592  {
593  // print_heap();
594  // std::cout << "REALLOC(" << ptr << "," << size << ")" << std::endl;
595  /* handle special cases first */
596  if (nullptr == ptr) return mm_alloc(size);
597  if (size == 0)
598  {
599  mm_free(ptr);
600  return nullptr;
601  }
602  mm_block_t * bptr = block_cur(ptr);
603 
604  bool need_malloc = 0;
605  size_t blockdatasize = block_getdatasize(bptr);
606  /* we do nothing if the size is equal to the block */
607  if (size == blockdatasize)
608  {
609  // std::cout << "return ptr = " << ptr << std::endl;
610  return ptr; /* do nothing if size fits already */
611  }
612  if (size < blockdatasize)
613  {
614  /* we shrink */
615  /* do we shrink enough to perform a split? */
616  // std::cout << "shrink!" << std::endl;
617  split_block(bptr, size);
618  }
619  else
620  {
621  // std::cout << "expand!" << std::endl;
622  /* we expand */
623  /* if the next block is free we could use it! */
624  mm_block_t * next = block_next(bptr, m_top);
625  if (!next)
626  {
627  // std::cout << "no next! -> expand!" << std::endl;
628  // we are the last block so we just expand
629  blockdatasize = block_getdatasize(bptr);
630  size_t needed = ALIGN(size - blockdatasize);
631  hsbrk(needed);
632  block_update(bptr, UNMASK_SIZE(bptr->size) + needed);
633  return block_data(bptr);
634  }
635  else
636  {
637  // we are not the last block
638  // std::cout << "try combine next" << std::endl;
639  if (next && block_isfree(next))
640  {
641  /* do we have enough space if we use the next block */
642  if (blockdatasize + UNMASK_SIZE(next->size) >= size)
643  {
644  /* the next block is enough! */
645  /* remove the "next" block from the free list */
646  remove_from_free_set(next);
647  /* add the size of our block */
648  block_update(bptr, UNMASK_SIZE(bptr->size) + UNMASK_SIZE(next->size));
649  }
650  else
651  {
652  /* the next block is not enough. we allocate a new one instead */
653  need_malloc = true;
654  }
655  }
656  else
657  {
658  /* try combing the previous block if free */
659  // std::cout << "try combine prev" << std::endl;
660  mm_block_t * prev = block_prev(bptr, m_first_block);
661  if (prev && block_isfree(prev))
662  {
663  if (blockdatasize + UNMASK_SIZE(prev->size) >= size)
664  {
665  remove_from_free_set(prev);
666  size_t newsize = UNMASK_SIZE(prev->size) + UNMASK_SIZE(bptr->size);
667  block_update(prev, newsize);
668  block_markused(prev);
669  /* move the data into the previous block */
670  ptr = memmove(block_data(prev), ptr, blockdatasize);
671  }
672  else
673  {
674  /* not enough in the prev block */
675  need_malloc = true;
676  }
677  }
678  else
679  {
680  /* prev block not free. get more memory */
681  need_malloc = true;
682  }
683  }
684  }
685  }
686  if (need_malloc)
687  {
688  // std::cout << "need_alloc in REALLOC!" << std::endl;
689  void * newptr = mm_alloc(size);
690  memcpy(newptr, ptr, size);
691  mm_free(ptr);
692  ptr = newptr;
693  }
694  // print_heap();
695  // std::cout << "return ptr = " << ptr << std::endl;
696  return ptr;
697  }
698 
699  void * mm_alloc(size_t size_in_bytes)
700  {
701  // std::cout << "ALLOC(" << size_in_bytes << ")" << std::endl;
702  mm_block_t * bptr = nullptr;
703  if ((bptr = find_free_block(size_in_bytes + MM_BLOCK_OVERHEAD)) != nullptr)
704  {
705  // std::cout << "found free block = " << (void*)bptr << std::endl;
706  block_markused(bptr);
707  /* split if we have a block too large for us? */
708  split_block(bptr, size_in_bytes);
709  }
710  else
711  {
712  // std::cout << "no free block found that is big enough!" << std::endl;
713  // check if last block is free
714  // std::cout << "check last block" << std::endl;
715  bptr = last_block();
716  if (bptr && block_isfree(bptr))
717  {
718  // std::cout << "last block is free. -> extend!" << std::endl;
719  // extent last block as it is free
720  size_t blockdatasize = block_getdatasize(bptr);
721  size_t needed = ALIGN(size_in_bytes - blockdatasize);
722  hsbrk(needed);
723  remove_from_free_set(bptr);
724  block_update(bptr, blockdatasize + needed + sizeof(size_t) + sizeof(mm_block_foot_t));
725  // insert_into_free_set(bptr);
726  block_markused(bptr);
727  }
728  else
729  {
730  bptr = new_block(size_in_bytes);
731  }
732  }
733  // print_heap();
734  // void* ptr = block_data(bptr);
735  // std::cout << "return ptr = " << ptr << std::endl;
736  return block_data(bptr);
737  }
738 
739  void mm_free(void * ptr)
740  {
741  // print_heap();
742  // std::cout << "FREE(" << ptr << ")" << std::endl;
743  if (ptr)
744  {
745  mm_block_t * bptr = block_cur(ptr);
746  block_markfree(bptr);
747  /* coalesce if needed. otherwise just add */
748  coalesce_block(bptr);
749  }
750  // print_heap();
751  }
752 
753  bool in_address_space(void * ptr)
754  {
755  // check if ptr is in the hugepage address space
756  if (ptr == nullptr) { return true; }
757  if (ptr >= m_base && ptr < m_top) { return true; }
758  return false;
759  }
761  {
762  static hugepage_allocator a;
763  return a;
764  }
765 };
766 #endif
767 
769 {
770  private:
771  bool hugepages = false;
772 
773  private:
774  static memory_manager & the_manager()
775  {
776  static memory_manager m;
777  return m;
778  }
779 
780  public:
781  static uint64_t * alloc_mem(size_t size_in_bytes)
782  {
783 #ifndef _WIN32
784  auto & m = the_manager();
785  if (m.hugepages) { return (uint64_t *)hugepage_allocator::the_allocator().mm_alloc(size_in_bytes); }
786 #endif
787  return (uint64_t *)calloc(size_in_bytes, 1);
788  }
789  static void free_mem(uint64_t * ptr)
790  {
791 #ifndef _WIN32
792  auto & m = the_manager();
793  if (m.hugepages and hugepage_allocator::the_allocator().in_address_space(ptr))
794  {
796  return;
797  }
798 #endif
799  std::free(ptr);
800  }
801  static uint64_t * realloc_mem(uint64_t * ptr, size_t size)
802  {
803 #ifndef _WIN32
804  auto & m = the_manager();
805  if (m.hugepages and hugepage_allocator::the_allocator().in_address_space(ptr))
806  {
807  return (uint64_t *)hugepage_allocator::the_allocator().mm_realloc(ptr, size);
808  }
809 #endif
810  return (uint64_t *)realloc(ptr, size);
811  }
812 
813  public:
814  static void use_hugepages(size_t bytes = 0)
815  {
816 #ifndef _WIN32
817  auto & m = the_manager();
819  m.hugepages = true;
820 #else
821  throw std::runtime_error(std::string("hugepages not supported on Windows"));
822  // avoid error: unused parameter 'bytes' [-Werror=unused-parameter]
823  (void)bytes;
824 #endif
825  }
826  template <class t_vec>
827  static void resize(t_vec & v, const typename t_vec::size_type capacity)
828  {
829  uint64_t old_capacity_in_bytes = ((v.m_capacity + 63) >> 6) << 3;
830  uint64_t new_capacity_in_bytes = ((capacity + 63) >> 6) << 3;
831  bool do_realloc = old_capacity_in_bytes != new_capacity_in_bytes;
832  v.m_capacity = ((capacity + 63) >> 6) << 6; // set new_capacity to a multiple of 64
833 
834  if (do_realloc || v.m_data == nullptr)
835  {
836  // Note that we allocate 8 additional bytes if m_capacity % 64 == 0.
837  // We need this padding since rank data structures do a memory
838  // access to this padding to answer rank(size()) if capacity()%64 ==0.
839  // Note that this padding is not counted in the serialize method!
840  size_t allocated_bytes = (size_t)(((v.m_capacity + 64) >> 6) << 3);
841  v.m_data = memory_manager::realloc_mem(v.m_data, allocated_bytes);
842  if (allocated_bytes != 0 && v.m_data == nullptr) { throw std::bad_alloc(); }
843 
844  // update stats
845  if (do_realloc) { memory_monitor::record((int64_t)new_capacity_in_bytes - (int64_t)old_capacity_in_bytes); }
846  }
847  }
848  template <class t_vec>
849  static void clear(t_vec & v)
850  {
851  int64_t size_in_bytes = ((v.m_size + 63) >> 6) << 3;
852  // remove mem
853  memory_manager::free_mem(v.m_data);
854  v.m_data = nullptr;
855 
856  // update stats
858  }
859 
860  static int open_file_for_mmap(std::string & filename, std::ios_base::openmode mode)
861  {
862  if (is_ram_file(filename)) { return ram_fs::open(filename); }
863 #ifdef MSVC_COMPILER
864  int fd = -1;
865  if (!(mode & std::ios_base::out))
866  _sopen_s(&fd, filename.c_str(), _O_BINARY | _O_RDONLY, _SH_DENYNO, _S_IREAD);
867  else
868  _sopen_s(&fd, filename.c_str(), _O_BINARY | _O_RDWR, _SH_DENYNO, _S_IREAD | _S_IWRITE);
869  return fd;
870 #else
871  if (!(mode & std::ios_base::out))
872  return open(filename.c_str(), O_RDONLY);
873  else
874  return open(filename.c_str(), O_RDWR);
875 #endif
876  return -1;
877  }
878 
879  static void * mmap_file(int fd, uint64_t file_size, std::ios_base::openmode mode)
880  {
881  if (file_size == 0)
882  {
883  std::cout << "file_size=0" << std::endl;
884  return nullptr;
885  }
886  if (is_ram_file(fd))
887  {
888  if (ram_fs::file_size(fd) < file_size) return nullptr;
889  auto & file_content = ram_fs::content(fd);
890  return file_content.data();
891  }
893 #ifdef _WIN32
894  HANDLE fh = (HANDLE)_get_osfhandle(fd);
895  if (fh == INVALID_HANDLE_VALUE) { return nullptr; }
896  HANDLE fm;
897  if (!(mode & std::ios_base::out))
898  { // read only?
899  fm = CreateFileMapping(fh, NULL, PAGE_READONLY, 0, 0, NULL);
900  }
901  else
902  fm = CreateFileMapping(fh, NULL, PAGE_READWRITE, 0, 0, NULL);
903  if (fm == NULL) { return nullptr; }
904  void * map = nullptr;
905  if (!(mode & std::ios_base::out))
906  { // read only?
907  map = MapViewOfFile(fm, FILE_MAP_READ, 0, 0, file_size);
908  }
909  else
910  map = MapViewOfFile(fm, FILE_MAP_WRITE | FILE_MAP_READ, 0, 0, file_size);
911  // we can close the file handle before we unmap the view: (see UnmapViewOfFile Doc)
912  // Although an application may close the file handle used to create a file mapping object,
913  // the system holds the corresponding file open until the last view of the file is unmapped.
914  // Files for which the last view has not yet been unmapped are held open with no sharing restrictions.
915  CloseHandle(fm);
916  return map;
917 #else
918  void * map = nullptr;
919  if (!(mode & std::ios_base::out))
920  map = mmap(NULL, file_size, PROT_READ, MAP_SHARED, fd, 0);
921  else
922  map = mmap(NULL, file_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
923  if (map == MAP_FAILED) map = nullptr; // unify windows and unix error behaviour
924  return map;
925 #endif
926  return nullptr;
927  }
928 
929  static int mem_unmap(int fd, void * addr, const uint64_t size)
930  {
931  if (addr == nullptr) { return 0; }
932  if (is_ram_file(fd)) { return 0; }
933  memory_monitor::record(-((int64_t)size));
934 #ifdef _WIN32
935  if (UnmapViewOfFile(addr)) return 0;
936  return -1;
937 #else
938  return munmap(addr, size);
939 #endif
940  return -1;
941  }
942 
943  static int close_file_for_mmap(int fd)
944  {
945  if (is_ram_file(fd)) { return ram_fs::close(fd); }
946 #ifdef MSVC_COMPILER
947  return _close(fd);
948 #else
949  return close(fd);
950 #endif
951  return -1;
952  }
953 
954  static int truncate_file_mmap(int fd, const uint64_t new_size)
955  {
956  if (is_ram_file(fd)) { return ram_fs::truncate(fd, new_size); }
957 #ifdef _WIN32
958  auto ret = _chsize_s(fd, new_size);
959  if (ret != 0) ret = -1;
960  return ret;
961 #else
962  return ftruncate(fd, new_size);
963 #endif
964  return -1;
965  }
966 };
967 
968 #undef ALIGNMENT
969 #undef ALIGNSPLIT
970 #undef ALIGN
971 #undef MM_BLOCK_OVERHEAD
972 #undef MIN_BLOCKSIZE
973 #undef UNMASK_SIZE
974 #undef ISFREE
975 #undef SETFREE
976 #undef SPLIT_THRESHOLD
977 
978 } // namespace sdsl
979 
980 #endif
bits.hpp contains the sdsl::bits class.
void * mm_realloc(void *ptr, size_t size)
void init(SDSL_UNUSED size_t size_in_bytes=0)
void * mm_alloc(size_t size_in_bytes)
static hugepage_allocator & the_allocator()
static uint64_t * realloc_mem(uint64_t *ptr, size_t size)
static int close_file_for_mmap(int fd)
static void use_hugepages(size_t bytes=0)
static void free_mem(uint64_t *ptr)
static int mem_unmap(int fd, void *addr, const uint64_t size)
static int open_file_for_mmap(std::string &filename, std::ios_base::openmode mode)
static void resize(t_vec &v, const typename t_vec::size_type capacity)
static int truncate_file_mmap(int fd, const uint64_t new_size)
static void * mmap_file(int fd, uint64_t file_size, std::ios_base::openmode mode)
static void clear(t_vec &v)
static uint64_t * alloc_mem(size_t size_in_bytes)
static void record(int64_t delta)
#define SDSL_UNUSED
Definition: config.hpp:13
#define MM_BLOCK_OVERHEAD
#define SETFREE(size)
#define UNMASK_SIZE(size)
#define ALIGN(size)
#define ALIGNSPLIT(size)
#define SPLIT_THRESHOLD
#define MIN_BLOCKSIZE
memory_tracking.hpp contains two function for allocating and deallocating memory
int_vector ::size_type size_type
int open(const std::string &name)
Get fd for file.
Definition: ram_fs.hpp:88
content_type & content(const std::string &name)
Get the content.
Definition: ram_fs.hpp:61
int close(const int fd)
Get fd for file.
Definition: ram_fs.hpp:110
size_t file_size(const std::string &name)
Get the file size.
Definition: ram_fs.hpp:49
int truncate(const int fd, size_t new_size)
Get the content with fd.
Definition: ram_fs.hpp:134
Namespace for the succinct data structure library.
bool is_ram_file(const std::string &file)
Determines if the given file is a RAM-file.
Definition: ram_fs.hpp:158
size_t block_size(void *ptr)
std::string create_mem_html_header()
void block_markused(mm_block_t *ptr)
void block_markfree(mm_block_t *ptr)
bool block_prevfree(mm_block_t *ptr, mm_block_t *begin)
mm_block_t * block_prev(mm_block_t *cur_bptr, mm_block_t *first)
bool block_nextfree(mm_block_t *ptr, uint8_t *top)
struct sdsl::mm_block mm_block_t
void foot_update(mm_block_t *ptr, size_t size)
void * block_data(mm_block_t *ptr)
mm_block_t * block_next(mm_block_t *cur_bptr, uint8_t *top)
struct sdsl::bfoot mm_block_foot_t
size_t block_getdatasize(mm_block_t *ptr)
void block_update(mm_block_t *ptr, size_t size)
mm_block_t * block_cur(void *ptr)
bool block_isfree(mm_block_t *ptr)
std::string create_mem_js_body(const std::string &jsonObject)
void output_event_json(std::ostream &out, const mm_event &ev, const tracker_storage &m)
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
void write_mem_log< HTML_FORMAT >(std::ostream &out, const tracker_storage &m)
void write_mem_log< JSON_FORMAT >(std::ostream &out, const tracker_storage &m)
T::size_type size_in_bytes(const T &t)
Get the size of a data structure in bytes.
Definition: io.hpp:778
ram_fs.hpp
struct mm_block * prev
struct mm_block * next
std::vector< mm_alloc > allocations
std::vector< mm_event > completed_events
timer::time_point start_log