Line data Source code
1 : /* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 : Copyright (c) 2008-2017, Petr Kobalicek
3 :
4 : This software is provided 'as-is', without any express or implied
5 : warranty. In no event will the authors be held liable for any damages
6 : arising from the use of this software.
7 :
8 : Permission is granted to anyone to use this software for any purpose,
9 : including commercial applications, and to alter it and redistribute it
10 : freely, subject to the following restrictions:
11 :
12 : 1. The origin of this software must not be misrepresented; you must not
13 : claim that you wrote the original software. If you use this software
14 : in a product, an acknowledgment in the product documentation would be
15 : appreciated but is not required.
16 : 2. Altered source versions must be plainly marked as such, and must not be
17 : misrepresented as being the original software.
18 : 3. This notice may not be removed or altered from any source distribution.
19 : +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
20 : #ifdef __PLUMED_HAS_ASMJIT
21 : #pragma GCC diagnostic push
22 : #pragma GCC diagnostic ignored "-Wpedantic"
23 : // [AsmJit]
24 : // Complete x86/x64 JIT and Remote Assembler for C++.
25 : //
26 : // [License]
27 : // Zlib - See LICENSE.md file in the package.
28 :
29 : // [Export]
30 : #define ASMJIT_EXPORTS
31 :
32 : // [Dependencies]
33 : #include "./osutils.h"
34 : #include "./utils.h"
35 : #include "./vmem.h"
36 :
37 : // [Api-Begin]
38 : #include "./asmjit_apibegin.h"
39 :
40 : // This file contains implementation of virtual memory management for AsmJit
41 : // library. There are several goals I decided to write implementation myself:
42 : //
43 : // - Granularity of allocated blocks is different than granularity for a typical
44 : // C malloc. It is at least 64-bytes so CodeEmitter can guarantee the alignment
45 : // up to 64 bytes, which is the size of a cache-line and it's also required by
46 : // AVX-512 aligned loads and stores. Alignment requirements can grow in the future,
47 : // but at the moment 64 bytes is safe (we may jump to 128 bytes if necessary or
48 : // make it configurable).
49 : //
50 : // - Keep memory manager information outside of the allocated virtual memory
51 : // pages, because these pages allow machine code execution and there should
52 : // be not data required to keep track of these blocks. Another reason is that
53 : // some environments (i.e. iOS) allow to generate and run JIT code, but this
54 : // code has to be set to [Executable, but not Writable].
55 : //
56 : // - Keep implementation simple and easy to follow.
57 : //
58 : // Implementation is based on bit arrays and binary trees. Bit arrays contain
59 : // information related to allocated and unused blocks of memory. The size of
60 : // a block is described by `MemNode::density`. Count of blocks is stored in
61 : // `MemNode::blocks`. For example if density is 64 and count of blocks is 20,
62 : // memory node contains 64*20 bytes of memory and the smallest possible allocation
63 : // (and also alignment) is 64 bytes. So density is also related to memory
64 : // alignment. Binary trees (RB) are used to enable fast lookup into all addresses
65 : // allocated by memory manager instance. This is used mainly by `VMemPrivate::release()`.
66 : //
67 : // Bit array looks like this (empty = unused, X = used) - Size of block 64:
68 : //
69 : // -------------------------------------------------------------------------
70 : // | |X|X| | | | | |X|X|X|X|X|X| | | | | | | | | | | | |X| | | | |X|X|X| | |
71 : // -------------------------------------------------------------------------
72 : // (Maximum continuous block)
73 : //
74 : // These bits show that there are 12 allocated blocks (X) of 64 bytes, so total
75 : // size allocated is 768 bytes. Maximum count of continuous memory is 12 * 64.
76 :
77 : namespace PLMD {
78 : namespace asmjit {
79 :
80 : // ============================================================================
81 : // [asmjit::VMemMgr - BitOps]
82 : // ============================================================================
83 :
84 : #define M_DIV(x, y) ((x) / (y))
85 : #define M_MOD(x, y) ((x) % (y))
86 :
87 : //! \internal
88 : enum { kBitsPerEntity = (sizeof(size_t) * 8) };
89 :
90 : //! \internal
91 : //!
92 : //! Set `len` bits in `buf` starting at `index` bit index.
93 64222 : static void _SetBits(size_t* buf, size_t index, size_t len) noexcept {
94 64222 : if (len == 0)
95 : return;
96 :
97 42181 : size_t i = index / kBitsPerEntity; // size_t[]
98 42181 : size_t j = index % kBitsPerEntity; // size_t[][] bit index
99 :
100 : // How many bytes process in the first group.
101 42181 : size_t c = kBitsPerEntity - j;
102 : if (c > len)
103 : c = len;
104 :
105 : // Offset.
106 42181 : buf += i;
107 :
108 42181 : *buf++ |= ((~(size_t)0) >> (kBitsPerEntity - c)) << j;
109 42181 : len -= c;
110 :
111 42181 : while (len >= kBitsPerEntity) {
112 0 : *buf++ = ~(size_t)0;
113 0 : len -= kBitsPerEntity;
114 : }
115 :
116 42181 : if (len)
117 112 : *buf |= ((~(size_t)0) >> (kBitsPerEntity - len));
118 : }
119 :
120 : // ============================================================================
121 : // [asmjit::VMemMgr::TypeDefs]
122 : // ============================================================================
123 :
124 : typedef VMemMgr::RbNode RbNode;
125 : typedef VMemMgr::MemNode MemNode;
126 : typedef VMemMgr::PermanentNode PermanentNode;
127 :
128 : // ============================================================================
129 : // [asmjit::VMemMgr::RbNode]
130 : // ============================================================================
131 :
132 : //! \internal
133 : //!
134 : //! Base red-black tree node.
135 : struct VMemMgr::RbNode {
136 : // Implementation is based on article by Julienne Walker (Public Domain),
137 : // including C code and original comments. Thanks for the excellent article.
138 :
139 : RbNode* node[2]; //!< Left[0] and right[1] nodes.
140 : uint8_t* mem; //!< Virtual memory address.
141 : uint32_t red; //!< Node color (red vs. black).
142 : };
143 :
144 : //! \internal
145 : //!
146 : //! Get if the node is red (nullptr or node with red flag).
147 : static ASMJIT_INLINE bool rbIsRed(RbNode* node) noexcept {
148 0 : return node && node->red;
149 : }
150 :
151 : //! \internal
152 : //!
153 : //! Check whether the RB tree is valid.
154 : static int rbAssert(RbNode* root) noexcept {
155 : if (!root) return 1;
156 :
157 : RbNode* ln = root->node[0];
158 : RbNode* rn = root->node[1];
159 :
160 : // Red violation.
161 : ASMJIT_ASSERT(!(rbIsRed(root) && (rbIsRed(ln) || rbIsRed(rn))));
162 :
163 : int lh = rbAssert(ln);
164 : int rh = rbAssert(rn);
165 :
166 : // Invalid btree.
167 : ASMJIT_ASSERT(ln == nullptr || ln->mem < root->mem);
168 : ASMJIT_ASSERT(rn == nullptr || rn->mem > root->mem);
169 :
170 : // Black violation.
171 : ASMJIT_ASSERT(!(lh != 0 && rh != 0 && lh != rh));
172 :
173 : // Only count black links.
174 : if (lh != 0 && rh != 0)
175 : return rbIsRed(root) ? lh : lh + 1;
176 : else
177 : return 0;
178 : }
179 :
180 : //! \internal
181 : //!
182 : //! Single rotation.
183 : static ASMJIT_INLINE RbNode* rbRotateSingle(RbNode* root, int dir) noexcept {
184 0 : RbNode* save = root->node[!dir];
185 :
186 0 : root->node[!dir] = save->node[dir];
187 0 : save->node[dir] = root;
188 :
189 0 : root->red = 1;
190 0 : save->red = 0;
191 :
192 : return save;
193 : }
194 :
195 : //! \internal
196 : //!
197 : //! Double rotation.
198 : static ASMJIT_INLINE RbNode* rbRotateDouble(RbNode* root, int dir) noexcept {
199 0 : root->node[!dir] = rbRotateSingle(root->node[!dir], !dir);
200 : return rbRotateSingle(root, dir);
201 : }
202 :
203 : // ============================================================================
204 : // [asmjit::VMemMgr::MemNode]
205 : // ============================================================================
206 :
207 : struct VMemMgr::MemNode : public RbNode {
208 : ASMJIT_INLINE void init(MemNode* other) noexcept {
209 0 : mem = other->mem;
210 :
211 0 : size = other->size;
212 0 : used = other->used;
213 0 : blocks = other->blocks;
214 0 : density = other->density;
215 0 : largestBlock = other->largestBlock;
216 :
217 0 : baUsed = other->baUsed;
218 0 : baCont = other->baCont;
219 0 : }
220 :
221 : // Get available space.
222 0 : ASMJIT_INLINE size_t getAvailable() const noexcept { return size - used; }
223 :
224 : MemNode* prev; // Prev node in list.
225 : MemNode* next; // Next node in list.
226 :
227 : size_t size; // How many bytes contain this node.
228 : size_t used; // How many bytes are used in this node.
229 : size_t blocks; // How many blocks are here.
230 : size_t density; // Minimum count of allocated bytes in this node (also alignment).
231 : size_t largestBlock; // Contains largest block that can be allocated.
232 :
233 : size_t* baUsed; // Contains bits about used blocks (0 = unused, 1 = used).
234 : size_t* baCont; // Contains bits about continuous blocks (0 = stop , 1 = continue).
235 : };
236 :
237 : // ============================================================================
238 : // [asmjit::VMemMgr::PermanentNode]
239 : // ============================================================================
240 :
241 : //! \internal
242 : //!
243 : //! Permanent node.
244 : struct VMemMgr::PermanentNode {
245 : //! Get available space.
246 0 : ASMJIT_INLINE size_t getAvailable() const noexcept { return size - used; }
247 :
248 : PermanentNode* prev; // Pointer to prev chunk or nullptr.
249 : uint8_t* mem; // Base pointer (virtual memory address).
250 : size_t size; // Count of bytes allocated.
251 : size_t used; // Count of bytes used.
252 : };
253 :
254 : // ============================================================================
255 : // [asmjit::VMemMgr - Private]
256 : // ============================================================================
257 :
258 : //! \internal
259 : //!
260 : //! Helper to avoid `#ifdef`s in the code.
261 : ASMJIT_INLINE uint8_t* vMemMgrAllocVMem(VMemMgr* self, size_t size, size_t* vSize) noexcept {
262 : uint32_t flags = OSUtils::kVMWritable | OSUtils::kVMExecutable;
263 : #if !ASMJIT_OS_WINDOWS
264 32111 : return static_cast<uint8_t*>(OSUtils::allocVirtualMemory(size, vSize, flags));
265 : #else
266 : return static_cast<uint8_t*>(OSUtils::allocProcessMemory(self->_hProcess, size, vSize, flags));
267 : #endif
268 : }
269 :
270 : //! \internal
271 : //!
272 : //! Helper to avoid `#ifdef`s in the code.
273 : ASMJIT_INLINE Error vMemMgrReleaseVMem(VMemMgr* self, void* p, size_t vSize) noexcept {
274 : #if !ASMJIT_OS_WINDOWS
275 0 : return OSUtils::releaseVirtualMemory(p, vSize);
276 : #else
277 : return OSUtils::releaseProcessMemory(self->_hProcess, p, vSize);
278 : #endif
279 : }
280 :
281 : //! \internal
282 : //!
283 : //! Check whether the Red-Black tree is valid.
284 : static bool vMemMgrCheckTree(VMemMgr* self) noexcept {
285 : return rbAssert(self->_root) > 0;
286 : }
287 :
288 : //! \internal
289 : //!
290 : //! Alloc virtual memory including a heap memory needed for `MemNode` data.
291 : //!
292 : //! Returns set-up `MemNode*` or nullptr if allocation failed.
293 32111 : static MemNode* vMemMgrCreateNode(VMemMgr* self, size_t size, size_t density) noexcept {
294 : size_t vSize;
295 : uint8_t* vmem = vMemMgrAllocVMem(self, size, &vSize);
296 32111 : if (!vmem) return nullptr;
297 :
298 32111 : size_t blocks = (vSize / density);
299 32111 : size_t bsize = (((blocks + 7) >> 3) + sizeof(size_t) - 1) & ~(size_t)(sizeof(size_t) - 1);
300 :
301 : MemNode* node = static_cast<MemNode*>(Internal::allocMemory(sizeof(MemNode)));
302 32111 : uint8_t* data = static_cast<uint8_t*>(Internal::allocMemory(bsize * 2));
303 :
304 : // Out of memory.
305 32111 : if (!node || !data) {
306 : vMemMgrReleaseVMem(self, vmem, vSize);
307 0 : if (node) Internal::releaseMemory(node);
308 0 : if (data) Internal::releaseMemory(data);
309 0 : return nullptr;
310 : }
311 :
312 : // Initialize RbNode data.
313 32111 : node->node[0] = nullptr;
314 32111 : node->node[1] = nullptr;
315 32111 : node->mem = vmem;
316 32111 : node->red = 1;
317 :
318 : // Initialize MemNode data.
319 32111 : node->prev = nullptr;
320 32111 : node->next = nullptr;
321 :
322 32111 : node->size = vSize;
323 32111 : node->used = 0;
324 32111 : node->blocks = blocks;
325 32111 : node->density = density;
326 32111 : node->largestBlock = vSize;
327 :
328 : ::memset(data, 0, bsize * 2);
329 32111 : node->baUsed = reinterpret_cast<size_t*>(data);
330 32111 : node->baCont = reinterpret_cast<size_t*>(data + bsize);
331 :
332 32111 : return node;
333 : }
334 :
335 32111 : static void vMemMgrInsertNode(VMemMgr* self, MemNode* node) noexcept {
336 32111 : if (!self->_root) {
337 : // Empty tree case.
338 32111 : self->_root = node;
339 : }
340 : else {
341 : // False tree root.
342 0 : RbNode head = { { nullptr, nullptr }, 0, 0 };
343 :
344 : // Grandparent & parent.
345 : RbNode* g = nullptr;
346 : RbNode* t = &head;
347 :
348 : // Iterator & parent.
349 : RbNode* p = nullptr;
350 0 : RbNode* q = t->node[1] = self->_root;
351 :
352 : int dir = 0;
353 : int last = 0; // Not needed to initialize, but makes some tools happy.
354 :
355 : // Search down the tree.
356 : for (;;) {
357 0 : if (!q) {
358 : // Insert new node at the bottom.
359 : q = node;
360 0 : p->node[dir] = node;
361 : }
362 0 : else if (rbIsRed(q->node[0]) && rbIsRed(q->node[1])) {
363 : // Color flip.
364 0 : q->red = 1;
365 0 : q->node[0]->red = 0;
366 0 : q->node[1]->red = 0;
367 : }
368 :
369 : // Fix red violation.
370 : if (rbIsRed(q) && rbIsRed(p)) {
371 0 : int dir2 = t->node[1] == g;
372 0 : t->node[dir2] = q == p->node[last] ? rbRotateSingle(g, !last) : rbRotateDouble(g, !last);
373 : }
374 :
375 : // Stop if found.
376 0 : if (q == node)
377 : break;
378 :
379 : last = dir;
380 0 : dir = q->mem < node->mem;
381 :
382 : // Update helpers.
383 0 : if (g) t = g;
384 :
385 : g = p;
386 : p = q;
387 0 : q = q->node[dir];
388 0 : }
389 :
390 : // Update root.
391 0 : self->_root = static_cast<MemNode*>(head.node[1]);
392 : }
393 :
394 : // Make root black.
395 32111 : self->_root->red = 0;
396 :
397 : // Link with others.
398 32111 : node->prev = self->_last;
399 :
400 32111 : if (!self->_first) {
401 32111 : self->_first = node;
402 32111 : self->_last = node;
403 32111 : self->_optimal = node;
404 : }
405 : else {
406 : node->prev = self->_last;
407 0 : self->_last->next = node;
408 0 : self->_last = node;
409 : }
410 32111 : }
411 :
412 : //! \internal
413 : //!
414 : //! Remove node from Red-Black tree.
415 : //!
416 : //! Returns node that should be freed, but it doesn't have to be necessarily
417 : //! the `node` passed.
418 0 : static MemNode* vMemMgrRemoveNode(VMemMgr* self, MemNode* node) noexcept {
419 : // False tree root.
420 0 : RbNode head = { { nullptr, nullptr }, 0, 0 };
421 :
422 : // Helpers.
423 : RbNode* q = &head;
424 : RbNode* p = nullptr;
425 : RbNode* g = nullptr;
426 :
427 : // Found item.
428 : RbNode* f = nullptr;
429 : int dir = 1;
430 :
431 : // Set up.
432 0 : q->node[1] = self->_root;
433 :
434 : // Search and push a red down.
435 0 : while (q->node[dir]) {
436 : int last = dir;
437 :
438 : // Update helpers.
439 : g = p;
440 : p = q;
441 : q = q->node[dir];
442 0 : dir = q->mem < node->mem;
443 :
444 : // Save found node.
445 0 : if (q == node)
446 : f = q;
447 :
448 : // Push the red node down.
449 0 : if (!rbIsRed(q) && !rbIsRed(q->node[dir])) {
450 0 : if (rbIsRed(q->node[!dir])) {
451 0 : p = p->node[last] = rbRotateSingle(q, dir);
452 : }
453 : else if (!rbIsRed(q->node[!dir])) {
454 0 : RbNode* s = p->node[!last];
455 :
456 0 : if (s) {
457 0 : if (!rbIsRed(s->node[!last]) && !rbIsRed(s->node[last])) {
458 : // Color flip.
459 0 : p->red = 0;
460 0 : s->red = 1;
461 0 : q->red = 1;
462 : }
463 : else {
464 0 : int dir2 = g->node[1] == p;
465 :
466 0 : if (rbIsRed(s->node[last]))
467 0 : g->node[dir2] = rbRotateDouble(p, last);
468 : else if (rbIsRed(s->node[!last]))
469 0 : g->node[dir2] = rbRotateSingle(p, last);
470 :
471 : // Ensure correct coloring.
472 0 : q->red = g->node[dir2]->red = 1;
473 0 : g->node[dir2]->node[0]->red = 0;
474 0 : g->node[dir2]->node[1]->red = 0;
475 : }
476 : }
477 : }
478 : }
479 : }
480 :
481 : // Replace and remove.
482 : ASMJIT_ASSERT(f != nullptr);
483 : ASMJIT_ASSERT(f != &head);
484 : ASMJIT_ASSERT(q != &head);
485 :
486 0 : if (f != q) {
487 : ASMJIT_ASSERT(f != &head);
488 : static_cast<MemNode*>(f)->init(static_cast<MemNode*>(q));
489 : }
490 :
491 0 : p->node[p->node[1] == q] = q->node[q->node[0] == nullptr];
492 :
493 : // Update root and make it black.
494 0 : self->_root = static_cast<MemNode*>(head.node[1]);
495 0 : if (self->_root) self->_root->red = 0;
496 :
497 : // Unlink.
498 0 : MemNode* next = static_cast<MemNode*>(q)->next;
499 0 : MemNode* prev = static_cast<MemNode*>(q)->prev;
500 :
501 0 : if (prev)
502 0 : prev->next = next;
503 : else
504 0 : self->_first = next;
505 :
506 0 : if (next)
507 0 : next->prev = prev;
508 : else
509 0 : self->_last = prev;
510 :
511 0 : if (self->_optimal == q)
512 0 : self->_optimal = prev ? prev : next;
513 :
514 0 : return static_cast<MemNode*>(q);
515 : }
516 :
517 0 : static MemNode* vMemMgrFindNodeByPtr(VMemMgr* self, uint8_t* mem) noexcept {
518 0 : MemNode* node = self->_root;
519 0 : while (node) {
520 0 : uint8_t* nodeMem = node->mem;
521 :
522 : // Go left.
523 0 : if (mem < nodeMem) {
524 0 : node = static_cast<MemNode*>(node->node[0]);
525 0 : continue;
526 : }
527 :
528 : // Go right.
529 0 : uint8_t* nodeEnd = nodeMem + node->size;
530 0 : if (mem >= nodeEnd) {
531 0 : node = static_cast<MemNode*>(node->node[1]);
532 0 : continue;
533 : }
534 :
535 : // Match.
536 : break;
537 : }
538 0 : return node;
539 : }
540 :
541 0 : static void* vMemMgrAllocPermanent(VMemMgr* self, size_t vSize) noexcept {
542 : static const size_t permanentAlignment = 32;
543 : static const size_t permanentNodeSize = 32768;
544 :
545 : vSize = Utils::alignTo<size_t>(vSize, permanentAlignment);
546 :
547 : AutoLock locked(self->_lock);
548 0 : PermanentNode* node = self->_permanent;
549 :
550 : // Try to find space in allocated chunks.
551 0 : while (node && vSize > node->getAvailable())
552 0 : node = node->prev;
553 :
554 : // Or allocate new node.
555 0 : if (!node) {
556 : size_t nodeSize = permanentNodeSize;
557 : if (nodeSize < vSize) nodeSize = vSize;
558 :
559 : node = static_cast<PermanentNode*>(Internal::allocMemory(sizeof(PermanentNode)));
560 0 : if (!node) return nullptr;
561 :
562 0 : node->mem = vMemMgrAllocVMem(self, nodeSize, &node->size);
563 0 : if (!node->mem) {
564 : Internal::releaseMemory(node);
565 0 : return nullptr;
566 : }
567 :
568 0 : node->used = 0;
569 0 : node->prev = self->_permanent;
570 0 : self->_permanent = node;
571 : }
572 :
573 : // Finally, copy function code to our space we reserved for.
574 0 : uint8_t* result = node->mem + node->used;
575 :
576 : // Update Statistics.
577 0 : node->used += vSize;
578 0 : self->_usedBytes += vSize;
579 :
580 : // Code can be null to only reserve space for code.
581 0 : return static_cast<void*>(result);
582 : }
583 :
584 32111 : static void* vMemMgrAllocFreeable(VMemMgr* self, size_t vSize) noexcept {
585 : // Current index.
586 : size_t i;
587 :
588 : // How many we need to be freed.
589 : size_t need;
590 : size_t minVSize;
591 :
592 : // Align to 32 bytes by default.
593 : vSize = Utils::alignTo<size_t>(vSize, 32);
594 32111 : if (vSize == 0)
595 : return nullptr;
596 :
597 : AutoLock locked(self->_lock);
598 32111 : MemNode* node = self->_optimal;
599 32111 : minVSize = self->_blockSize;
600 :
601 : // Try to find memory block in existing nodes.
602 32111 : while (node) {
603 : // Skip this node?
604 0 : if ((node->getAvailable() < vSize) || (node->largestBlock < vSize && node->largestBlock != 0)) {
605 0 : MemNode* next = node->next;
606 :
607 0 : if (node->getAvailable() < minVSize && node == self->_optimal && next)
608 0 : self->_optimal = next;
609 :
610 : node = next;
611 0 : continue;
612 0 : }
613 :
614 0 : size_t* up = node->baUsed; // Current ubits address.
615 : size_t ubits; // Current ubits[0] value.
616 : size_t bit; // Current bit mask.
617 0 : size_t blocks = node->blocks; // Count of blocks in node.
618 : size_t cont = 0; // How many bits are currently freed in find loop.
619 : size_t maxCont = 0; // Largest continuous block (bits count).
620 : size_t j;
621 :
622 0 : need = M_DIV((vSize + node->density - 1), node->density);
623 : i = 0;
624 :
625 : // Try to find node that is large enough.
626 0 : while (i < blocks) {
627 0 : ubits = *up++;
628 :
629 : // Fast skip used blocks.
630 0 : if (ubits == ~(size_t)0) {
631 : if (cont > maxCont)
632 : maxCont = cont;
633 : cont = 0;
634 :
635 0 : i += kBitsPerEntity;
636 0 : continue;
637 : }
638 :
639 : size_t max = kBitsPerEntity;
640 0 : if (i + max > blocks)
641 0 : max = blocks - i;
642 :
643 0 : for (j = 0, bit = 1; j < max; bit <<= 1) {
644 0 : j++;
645 0 : if ((ubits & bit) == 0) {
646 0 : if (++cont == need) {
647 0 : i += j;
648 0 : i -= cont;
649 0 : goto L_Found;
650 : }
651 :
652 0 : continue;
653 : }
654 :
655 : if (cont > maxCont) maxCont = cont;
656 : cont = 0;
657 : }
658 :
659 : i += kBitsPerEntity;
660 : }
661 :
662 : // Because we traversed the entire node, we can set largest node size that
663 : // will be used to cache next traversing.
664 0 : node->largestBlock = maxCont * node->density;
665 :
666 0 : node = node->next;
667 : }
668 :
669 : // If we are here, we failed to find existing memory block and we must
670 : // allocate a new one.
671 : {
672 32111 : size_t blockSize = self->_blockSize;
673 : if (blockSize < vSize) blockSize = vSize;
674 :
675 32111 : node = vMemMgrCreateNode(self, blockSize, self->_blockDensity);
676 32111 : if (!node) return nullptr;
677 :
678 : // Update binary tree.
679 32111 : vMemMgrInsertNode(self, node);
680 : ASMJIT_ASSERT(vMemMgrCheckTree(self));
681 :
682 : // Alloc first node at start.
683 : i = 0;
684 32111 : need = (vSize + node->density - 1) / node->density;
685 :
686 : // Update statistics.
687 32111 : self->_allocatedBytes += node->size;
688 : }
689 :
690 32111 : L_Found:
691 : // Update bits.
692 32111 : _SetBits(node->baUsed, i, need);
693 32111 : _SetBits(node->baCont, i, need - 1);
694 :
695 : // Update statistics.
696 : {
697 32111 : size_t u = need * node->density;
698 32111 : node->used += u;
699 32111 : node->largestBlock = 0;
700 32111 : self->_usedBytes += u;
701 : }
702 :
703 : // And return pointer to allocated memory.
704 32111 : uint8_t* result = node->mem + i * node->density;
705 : ASMJIT_ASSERT(result >= node->mem && result <= node->mem + node->size - vSize);
706 32111 : return result;
707 : }
708 :
709 : //! \internal
710 : //!
711 : //! Reset the whole `VMemMgr` instance, freeing all heap memory allocated an
712 : //! virtual memory allocated unless `keepVirtualMemory` is true (and this is
713 : //! only used when writing data to a remote process).
714 32141 : static void vMemMgrReset(VMemMgr* self, bool keepVirtualMemory) noexcept {
715 32141 : MemNode* node = self->_first;
716 :
717 64252 : while (node) {
718 32111 : MemNode* next = node->next;
719 :
720 32111 : if (!keepVirtualMemory)
721 32111 : vMemMgrReleaseVMem(self, node->mem, node->size);
722 :
723 32111 : Internal::releaseMemory(node->baUsed);
724 : Internal::releaseMemory(node);
725 :
726 : node = next;
727 : }
728 :
729 32141 : self->_allocatedBytes = 0;
730 32141 : self->_usedBytes = 0;
731 :
732 32141 : self->_root = nullptr;
733 32141 : self->_first = nullptr;
734 32141 : self->_last = nullptr;
735 32141 : self->_optimal = nullptr;
736 32141 : }
737 :
738 : // ============================================================================
739 : // [asmjit::VMemMgr - Construction / Destruction]
740 : // ============================================================================
741 :
742 : #if !ASMJIT_OS_WINDOWS
743 32141 : VMemMgr::VMemMgr() noexcept {
744 : #else
745 : VMemMgr::VMemMgr(HANDLE hProcess) noexcept {
746 : #endif
747 :
748 32141 : VMemInfo vm = OSUtils::getVirtualMemoryInfo();
749 :
750 : #if ASMJIT_OS_WINDOWS
751 : _hProcess = hProcess ? hProcess : vm.hCurrentProcess;
752 : #endif // ASMJIT_OS_WINDOWS
753 :
754 32141 : _blockSize = vm.pageGranularity;
755 32141 : _blockDensity = 64;
756 :
757 32141 : _allocatedBytes = 0;
758 32141 : _usedBytes = 0;
759 :
760 32141 : _root = nullptr;
761 32141 : _first = nullptr;
762 32141 : _last = nullptr;
763 32141 : _optimal = nullptr;
764 :
765 32141 : _permanent = nullptr;
766 32141 : _keepVirtualMemory = false;
767 32141 : }
768 :
769 32141 : VMemMgr::~VMemMgr() noexcept {
770 : // Freeable memory cleanup - Also frees the virtual memory if configured to.
771 32141 : vMemMgrReset(this, _keepVirtualMemory);
772 :
773 : // Permanent memory cleanup - Never frees the virtual memory.
774 32141 : PermanentNode* node = _permanent;
775 32141 : while (node) {
776 0 : PermanentNode* prev = node->prev;
777 : Internal::releaseMemory(node);
778 : node = prev;
779 : }
780 32141 : }
781 :
782 : // ============================================================================
783 : // [asmjit::VMemMgr - Reset]
784 : // ============================================================================
785 :
786 0 : void VMemMgr::reset() noexcept {
787 0 : vMemMgrReset(this, false);
788 0 : }
789 :
790 : // ============================================================================
791 : // [asmjit::VMemMgr - Alloc / Release]
792 : // ============================================================================
793 :
794 32111 : void* VMemMgr::alloc(size_t size, uint32_t type) noexcept {
795 32111 : if (type == kAllocPermanent)
796 0 : return vMemMgrAllocPermanent(this, size);
797 : else
798 32111 : return vMemMgrAllocFreeable(this, size);
799 : }
800 :
801 0 : Error VMemMgr::release(void* p) noexcept {
802 0 : if (!p) return kErrorOk;
803 :
804 : AutoLock locked(_lock);
805 0 : MemNode* node = vMemMgrFindNodeByPtr(this, static_cast<uint8_t*>(p));
806 0 : if (!node) return DebugUtils::errored(kErrorInvalidArgument);
807 :
808 0 : size_t offset = (size_t)((uint8_t*)p - (uint8_t*)node->mem);
809 0 : size_t bitpos = M_DIV(offset, node->density);
810 0 : size_t i = (bitpos / kBitsPerEntity);
811 :
812 0 : size_t* up = node->baUsed + i; // Current ubits address.
813 0 : size_t* cp = node->baCont + i; // Current cbits address.
814 0 : size_t ubits = *up; // Current ubits[0] value.
815 0 : size_t cbits = *cp; // Current cbits[0] value.
816 0 : size_t bit = (size_t)1 << (bitpos % kBitsPerEntity);
817 :
818 : size_t cont = 0;
819 : bool stop;
820 :
821 : for (;;) {
822 0 : stop = (cbits & bit) == 0;
823 0 : ubits &= ~bit;
824 0 : cbits &= ~bit;
825 :
826 0 : bit <<= 1;
827 0 : cont++;
828 :
829 0 : if (stop || bit == 0) {
830 0 : *up = ubits;
831 0 : *cp = cbits;
832 0 : if (stop)
833 : break;
834 :
835 0 : ubits = *++up;
836 0 : cbits = *++cp;
837 : bit = 1;
838 : }
839 : }
840 :
841 : // If the freed block is fully allocated node then it's needed to
842 : // update 'optimal' pointer in memory manager.
843 0 : if (node->used == node->size) {
844 0 : MemNode* cur = _optimal;
845 :
846 : do {
847 0 : cur = cur->prev;
848 0 : if (cur == node) {
849 0 : _optimal = node;
850 0 : break;
851 : }
852 0 : } while (cur);
853 : }
854 :
855 : // Statistics.
856 0 : cont *= node->density;
857 0 : if (node->largestBlock < cont)
858 0 : node->largestBlock = cont;
859 :
860 0 : node->used -= cont;
861 0 : _usedBytes -= cont;
862 :
863 : // If page is empty, we can free it.
864 0 : if (node->used == 0) {
865 : // Free memory associated with node (this memory is not accessed
866 : // anymore so it's safe).
867 0 : vMemMgrReleaseVMem(this, node->mem, node->size);
868 0 : Internal::releaseMemory(node->baUsed);
869 :
870 0 : node->baUsed = nullptr;
871 0 : node->baCont = nullptr;
872 :
873 : // Statistics.
874 0 : _allocatedBytes -= node->size;
875 :
876 : // Remove node. This function can return different node than
877 : // passed into, but data is copied into previous node if needed.
878 0 : Internal::releaseMemory(vMemMgrRemoveNode(this, node));
879 : ASMJIT_ASSERT(vMemMgrCheckTree(this));
880 : }
881 :
882 : return kErrorOk;
883 : }
884 :
885 0 : Error VMemMgr::shrink(void* p, size_t used) noexcept {
886 0 : if (!p) return kErrorOk;
887 0 : if (used == 0)
888 0 : return release(p);
889 :
890 : AutoLock locked(_lock);
891 0 : MemNode* node = vMemMgrFindNodeByPtr(this, (uint8_t*)p);
892 0 : if (!node) return DebugUtils::errored(kErrorInvalidArgument);
893 :
894 0 : size_t offset = (size_t)((uint8_t*)p - (uint8_t*)node->mem);
895 0 : size_t bitpos = M_DIV(offset, node->density);
896 0 : size_t i = (bitpos / kBitsPerEntity);
897 :
898 0 : size_t* up = node->baUsed + i; // Current ubits address.
899 0 : size_t* cp = node->baCont + i; // Current cbits address.
900 0 : size_t ubits = *up; // Current ubits[0] value.
901 0 : size_t cbits = *cp; // Current cbits[0] value.
902 0 : size_t bit = (size_t)1 << (bitpos % kBitsPerEntity);
903 :
904 : size_t cont = 0;
905 0 : size_t usedBlocks = (used + node->density - 1) / node->density;
906 :
907 : bool stop;
908 :
909 : // Find the first block we can mark as free.
910 : for (;;) {
911 0 : stop = (cbits & bit) == 0;
912 0 : if (stop)
913 : return kErrorOk;
914 :
915 0 : if (++cont == usedBlocks)
916 : break;
917 :
918 0 : bit <<= 1;
919 0 : if (bit == 0) {
920 0 : ubits = *++up;
921 0 : cbits = *++cp;
922 : bit = 1;
923 : }
924 : }
925 :
926 : // Free the tail blocks.
927 : cont = ~(size_t)0;
928 0 : goto _EnterFreeLoop;
929 :
930 : for (;;) {
931 0 : stop = (cbits & bit) == 0;
932 0 : ubits &= ~bit;
933 :
934 0 : _EnterFreeLoop:
935 0 : cbits &= ~bit;
936 :
937 0 : bit <<= 1;
938 0 : cont++;
939 :
940 0 : if (stop || bit == 0) {
941 0 : *up = ubits;
942 0 : *cp = cbits;
943 0 : if (stop)
944 : break;
945 :
946 0 : ubits = *++up;
947 0 : cbits = *++cp;
948 : bit = 1;
949 : }
950 : }
951 :
952 : // Statistics.
953 0 : cont *= node->density;
954 0 : if (node->largestBlock < cont)
955 0 : node->largestBlock = cont;
956 :
957 0 : node->used -= cont;
958 0 : _usedBytes -= cont;
959 :
960 0 : return kErrorOk;
961 : }
962 :
963 : // ============================================================================
964 : // [asmjit::VMem - Test]
965 : // ============================================================================
966 :
967 : #if defined(ASMJIT_TEST)
968 : static void VMemTest_fill(void* a, void* b, int i) noexcept {
969 : int pattern = rand() % 256;
970 : *(int *)a = i;
971 : *(int *)b = i;
972 : ::memset((char*)a + sizeof(int), pattern, i - sizeof(int));
973 : ::memset((char*)b + sizeof(int), pattern, i - sizeof(int));
974 : }
975 :
976 : static void VMemTest_verify(void* a, void* b) noexcept {
977 : int ai = *(int*)a;
978 : int bi = *(int*)b;
979 :
980 : EXPECT(ai == bi,
981 : "The length of 'a' (%d) and 'b' (%d) should be same", ai, bi);
982 :
983 : EXPECT(::memcmp(a, b, ai) == 0,
984 : "Pattern (%p) doesn't match", a);
985 : }
986 :
987 : static void VMemTest_stats(VMemMgr& memmgr) noexcept {
988 : INFO("Used : %u", static_cast<unsigned int>(memmgr.getUsedBytes()));
989 : INFO("Allocated: %u", static_cast<unsigned int>(memmgr.getAllocatedBytes()));
990 : }
991 :
992 : static void VMemTest_shuffle(void** a, void** b, size_t count) noexcept {
993 : for (size_t i = 0; i < count; ++i) {
994 : size_t si = (size_t)rand() % count;
995 :
996 : void* ta = a[i];
997 : void* tb = b[i];
998 :
999 : a[i] = a[si];
1000 : b[i] = b[si];
1001 :
1002 : a[si] = ta;
1003 : b[si] = tb;
1004 : }
1005 : }
1006 :
1007 : UNIT(base_vmem) {
1008 : VMemMgr memmgr;
1009 :
1010 : // Should be predictible.
1011 : srand(100);
1012 :
1013 : int i;
1014 : int kCount = 200000;
1015 :
1016 : INFO("Memory alloc/free test - %d allocations", static_cast<int>(kCount));
1017 :
1018 : void** a = (void**)Internal::allocMemory(sizeof(void*) * kCount);
1019 : void** b = (void**)Internal::allocMemory(sizeof(void*) * kCount);
1020 :
1021 : EXPECT(a != nullptr && b != nullptr,
1022 : "Couldn't allocate %u bytes on heap", kCount * 2);
1023 :
1024 : INFO("Allocating virtual memory...");
1025 : for (i = 0; i < kCount; i++) {
1026 : int r = (rand() % 1000) + 4;
1027 :
1028 : a[i] = memmgr.alloc(r);
1029 : EXPECT(a[i] != nullptr,
1030 : "Couldn't allocate %d bytes of virtual memory", r);
1031 : ::memset(a[i], 0, r);
1032 : }
1033 : VMemTest_stats(memmgr);
1034 :
1035 : INFO("Freeing virtual memory...");
1036 : for (i = 0; i < kCount; i++) {
1037 : EXPECT(memmgr.release(a[i]) == kErrorOk,
1038 : "Failed to free %p", b[i]);
1039 : }
1040 : VMemTest_stats(memmgr);
1041 :
1042 : INFO("Verified alloc/free test - %d allocations", static_cast<int>(kCount));
1043 : for (i = 0; i < kCount; i++) {
1044 : int r = (rand() % 1000) + 4;
1045 :
1046 : a[i] = memmgr.alloc(r);
1047 : EXPECT(a[i] != nullptr,
1048 : "Couldn't allocate %d bytes of virtual memory", r);
1049 :
1050 : b[i] = Internal::allocMemory(r);
1051 : EXPECT(b[i] != nullptr,
1052 : "Couldn't allocate %d bytes on heap", r);
1053 :
1054 : VMemTest_fill(a[i], b[i], r);
1055 : }
1056 : VMemTest_stats(memmgr);
1057 :
1058 : INFO("Shuffling...");
1059 : VMemTest_shuffle(a, b, kCount);
1060 :
1061 : INFO("Verify and free...");
1062 : for (i = 0; i < kCount / 2; i++) {
1063 : VMemTest_verify(a[i], b[i]);
1064 : EXPECT(memmgr.release(a[i]) == kErrorOk,
1065 : "Failed to free %p", a[i]);
1066 : Internal::releaseMemory(b[i]);
1067 : }
1068 : VMemTest_stats(memmgr);
1069 :
1070 : INFO("Alloc again");
1071 : for (i = 0; i < kCount / 2; i++) {
1072 : int r = (rand() % 1000) + 4;
1073 :
1074 : a[i] = memmgr.alloc(r);
1075 : EXPECT(a[i] != nullptr,
1076 : "Couldn't allocate %d bytes of virtual memory", r);
1077 :
1078 : b[i] = Internal::allocMemory(r);
1079 : EXPECT(b[i] != nullptr,
1080 : "Couldn't allocate %d bytes on heap");
1081 :
1082 : VMemTest_fill(a[i], b[i], r);
1083 : }
1084 : VMemTest_stats(memmgr);
1085 :
1086 : INFO("Verify and free...");
1087 : for (i = 0; i < kCount; i++) {
1088 : VMemTest_verify(a[i], b[i]);
1089 : EXPECT(memmgr.release(a[i]) == kErrorOk,
1090 : "Failed to free %p", a[i]);
1091 : Internal::releaseMemory(b[i]);
1092 : }
1093 : VMemTest_stats(memmgr);
1094 :
1095 : Internal::releaseMemory(a);
1096 : Internal::releaseMemory(b);
1097 : }
1098 : #endif // ASMJIT_TEST
1099 :
1100 : } // asmjit namespace
1101 : } // namespace PLMD
1102 : #pragma GCC diagnostic pop
1103 : #endif // __PLUMED_HAS_ASMJIT
|
