8#ifndef INCLUDED_SDSL_MEMORY_MANAGEMENT
9#define INCLUDED_SDSL_MEMORY_MANAGEMENT
25 using namespace std::chrono;
28 <<
"\"" << ev.
name <<
"\",\n";
34 out <<
"\t\t\t[" << duration_cast<milliseconds>(ev.
allocations[j].timestamp - m.
start_log).count() <<
","
36 if (j + 1 < ev.
allocations.size()) { out <<
",\n"; }
50 std::sort(events.begin(), events.end());
54 for (
size_t i = 0; i < events.size(); i++)
58 if (i < events.size() - 1) { out <<
"\t},\n"; }
69 std::stringstream jsonheader;
70 jsonheader <<
"<html>\n"
72 <<
"<meta charset=\"utf-8\">\n"
74 <<
" body { font: 11px sans-serif; }\n"
75 <<
" .rule { height: 90%; position: absolute; border-right: 1px dotted #000; "
76 "text-align: right; }\n"
78 <<
"<title>sdsl memory usage visualization</title>\n"
79 <<
"<script src=\"http://d3js.org/d3.v3.js\"></script>\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();
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] / "
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 + "
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\", "
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\", "
143 <<
"svg.selectAll(\".dot\").data(peakelem).enter().append(\"circle\").attr(\"r\", 3).attr(\"fill\", "
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\", "
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> "
185 <<
" \"<br> Phase Time: \" + pos.ptime + \" Seconds </p>\").style(\"visibility\", \"visible\");\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"
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 "
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("
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();
220 std::stringstream json_data;
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)
261 if (cur_bptr == first)
return nullptr;
271 if ((uint8_t *)((uint8_t *)cur_bptr +
UNMASK_SIZE(cur_bptr->
size)) >= top)
return nullptr;
286 return ((ptr->
size) & 1ULL);
322 return (
void *)((uint8_t *)ptr +
sizeof(
size_t));
349 uint8_t * m_base =
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;
356 inline void block_print(
int id,
mm_block_t * bptr)
359 "%d addr=%p size=%lu (%lu) free=%d\n",
368 inline uint64_t extract_number(std::string & line)
371 for (
size_t i = line.size() - 1; i + 1 >= 1; i--)
373 if (isdigit(line[i])) { num_str.insert(num_str.begin(), line[i]); }
376 if (num_str.size() > 0) {
break; }
379 return std::strtoull(num_str.c_str(),
nullptr, 10);
382 inline uint64_t extract_multiplier(std::string & line)
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; }
391 size_t determine_available_hugepage_memory()
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);
404 while (std::getline(mifs, line))
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); }
415 throw std::system_error(ENOMEM,
416 std::system_category(),
417 "hugepage_allocator could not automatically determine available hugepages");
430 remove_from_free_set(next);
439 remove_from_free_set(prev);
446 insert_into_free_set(newblock);
467 coalesce_block(newblock);
471 uint8_t * hsbrk(
size_t size)
473 ptrdiff_t left = (ptrdiff_t)m_total_size - (m_top - m_base);
474 if (left < (ptrdiff_t)
size)
476 throw std::system_error(ENOMEM,
477 std::system_category(),
478 "hugepage_allocator: not enough hugepage memory available");
480 uint8_t * new_mem = m_top;
498 auto eq_range = m_free_large.equal_range(block->
size);
500 auto itr = eq_range.first;
501 auto last = eq_range.second;
502 auto found = m_free_large.end();
505 if (itr->second == block) { found = itr; }
508 if (found == m_free_large.end()) { found = last; }
509 m_free_large.erase(found);
516 m_free_large.insert({ block->
size, block });
525 if (free_block != m_free_large.end())
527 bptr = free_block->second;
528 m_free_large.erase(free_block);
555 block_print(
id, bptr);
568 m_base = (uint8_t *)mmap(
nullptr,
570 (PROT_READ | PROT_WRITE),
571 (MAP_HUGETLB | MAP_ANONYMOUS | MAP_PRIVATE),
574 if (m_base == MAP_FAILED)
576 throw std::system_error(ENOMEM, std::system_category(),
"hugepage_allocator could not allocate hugepages");
585 throw std::system_error(ENOMEM,
586 std::system_category(),
587 "hugepage_allocator: MAP_HUGETLB / hugepage support not available");
604 bool need_malloc = 0;
607 if (
size == blockdatasize)
612 if (
size < blockdatasize)
617 split_block(bptr,
size);
630 size_t needed =
ALIGN(
size - blockdatasize);
646 remove_from_free_set(next);
665 remove_from_free_set(prev);
670 ptr = memmove(
block_data(prev), ptr, blockdatasize);
690 memcpy(newptr, ptr,
size);
723 remove_from_free_set(bptr);
748 coalesce_block(bptr);
756 if (ptr ==
nullptr) {
return true; }
757 if (ptr >= m_base && ptr < m_top) {
return true; }
771 bool hugepages =
false;
784 auto & m = the_manager();
792 auto & m = the_manager();
804 auto & m = the_manager();
810 return (uint64_t *)realloc(ptr,
size);
817 auto & m = the_manager();
821 throw std::runtime_error(std::string(
"hugepages not supported on Windows"));
826 template <
class t_vec>
827 static void resize(t_vec & v,
const typename t_vec::size_type capacity)
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;
834 if (do_realloc || v.m_data ==
nullptr)
840 size_t allocated_bytes = (size_t)(((v.m_capacity + 64) >> 6) << 3);
842 if (allocated_bytes != 0 && v.m_data ==
nullptr) {
throw std::bad_alloc(); }
845 if (do_realloc) {
memory_monitor::record((int64_t)new_capacity_in_bytes - (int64_t)old_capacity_in_bytes); }
848 template <
class t_vec>
865 if (!(mode & std::ios_base::out))
866 _sopen_s(&fd, filename.c_str(), _O_BINARY | _O_RDONLY, _SH_DENYNO, _S_IREAD);
868 _sopen_s(&fd, filename.c_str(), _O_BINARY | _O_RDWR, _SH_DENYNO, _S_IREAD | _S_IWRITE);
871 if (!(mode & std::ios_base::out))
872 return open(filename.c_str(), O_RDONLY);
874 return open(filename.c_str(), O_RDWR);
879 static void *
mmap_file(
int fd, uint64_t file_size, std::ios_base::openmode mode)
883 std::cout <<
"file_size=0" << std::endl;
890 return file_content.data();
894 HANDLE fh = (HANDLE)_get_osfhandle(fd);
895 if (fh == INVALID_HANDLE_VALUE) {
return nullptr; }
897 if (!(mode & std::ios_base::out))
899 fm = CreateFileMapping(fh, NULL, PAGE_READONLY, 0, 0, NULL);
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))
907 map = MapViewOfFile(fm, FILE_MAP_READ, 0, 0, file_size);
910 map = MapViewOfFile(fm, FILE_MAP_WRITE | FILE_MAP_READ, 0, 0, file_size);
918 void * map =
nullptr;
919 if (!(mode & std::ios_base::out))
920 map = mmap(NULL, file_size, PROT_READ, MAP_SHARED, fd, 0);
922 map = mmap(NULL, file_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
923 if (map == MAP_FAILED) map =
nullptr;
931 if (addr ==
nullptr) {
return 0; }
935 if (UnmapViewOfFile(addr))
return 0;
938 return munmap(addr,
size);
958 auto ret = _chsize_s(fd, new_size);
959 if (ret != 0) ret = -1;
962 return ftruncate(fd, new_size);
971#undef MM_BLOCK_OVERHEAD
976#undef SPLIT_THRESHOLD
bits.hpp contains the sdsl::bits class.
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()
bool in_address_space(void *ptr)
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 MM_BLOCK_OVERHEAD
#define UNMASK_SIZE(size)
memory_tracking.hpp contains two function for allocating and deallocating memory
int open(const std::string &name)
Get fd for file.
int close(const int fd)
Get fd for file.
size_t file_size(const std::string &name)
Get the file size.
content_type & content(const std::string &name)
Get the content.
int truncate(const int fd, size_t new_size)
Get the content with fd.
Namespace for the succinct data structure library.
bool is_ram_file(const std::string &file)
Determines if the given file is a RAM-file.
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)
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)
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 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.
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.
mm_block_t * block_cur(void *ptr)
std::vector< mm_alloc > allocations
std::vector< mm_event > completed_events
timer::time_point start_log