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