diff options
Diffstat (limited to 'lib/AsmJit/MemoryManager.cpp')
| -rw-r--r-- | lib/AsmJit/MemoryManager.cpp | 1227 |
1 files changed, 1227 insertions, 0 deletions
diff --git a/lib/AsmJit/MemoryManager.cpp b/lib/AsmJit/MemoryManager.cpp new file mode 100644 index 0000000..cb6ffa9 --- /dev/null +++ b/lib/AsmJit/MemoryManager.cpp @@ -0,0 +1,1227 @@ +// AsmJit - Complete JIT Assembler for C++ Language. + +// Copyright (c) 2008-2010, Petr Kobalicek <kobalicek.petr@gmail.com> +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following +// conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. + +// [Dependencies] +#include "Build.h" +#include "MemoryManager.h" +#include "Platform.h" + +#include <stdio.h> +#include <string.h> + +#include <new> + +// [Api-Begin] +#include "ApiBegin.h" + +// This file contains implementation of virtual memory management for AsmJit +// library. The initial concept is to keep this implementation simple but +// efficient. There are several goals I decided to write implementation myself. +// +// Goals: +// - We need usually to allocate blocks of 64 bytes long and more. +// - Alignment of allocated blocks is large - 32 bytes or 64 bytes. +// - Keep memory manager information outside allocated virtual memory pages +// (these pages allows execution of code). +// - Keep implementation small. +// +// I think that implementation is not small and probably not too much readable, +// so there is small know how. +// +// - Implementation is based on bit arrays and binary trees. Bit arrays +// contains information about allocated and unused blocks of memory. Each +// block size describes MemNode::density member. Count of blocks are +// stored in MemNode::blocks member. For example if density is 64 and +// count of blocks is 20, memory node contains 64*20 bytes of memory and +// smallest possible allocation (and also alignment) is 64 bytes. So density +// describes also memory alignment. Binary trees are used to enable fast +// lookup into all addresses allocated by memory manager instance. This is +// used mainly in MemoryManagerPrivate::free(). +// +// Bit array looks like this (empty = unused, X = used) - Size of block 64 +// ------------------------------------------------------------------------- +// | |X|X| | | | | |X|X|X|X|X|X| | | | | | | | | | | | |X| | | | |X|X|X| | | +// ------------------------------------------------------------------------- +// Bits array shows that there are 12 allocated blocks of 64 bytes, so total +// allocated size is 768 bytes. Maximum count of continuous blocks is 12 +// (see largest gap). + +namespace AsmJit { + +// ============================================================================ +// [Bits Manipulation] +// ============================================================================ + +#define BITS_PER_ENTITY (sizeof(sysuint_t) * 8) + +static void _SetBit(sysuint_t* buf, sysuint_t index) ASMJIT_NOTHROW +{ + sysuint_t i = index / BITS_PER_ENTITY; // sysuint_t[] + sysuint_t j = index % BITS_PER_ENTITY; // sysuint_t[][] bit index + + buf += i; + *buf |= (sysuint_t)1 << j; +} + +static void _ClearBit(sysuint_t* buf, sysuint_t index) ASMJIT_NOTHROW +{ + sysuint_t i = index / BITS_PER_ENTITY; // sysuint_t[] + sysuint_t j = index % BITS_PER_ENTITY; // sysuint_t[][] bit index + + buf += i; + *buf &= ~((sysuint_t)1 << j); +} + +static void _SetBits(sysuint_t* buf, sysuint_t index, sysuint_t len) ASMJIT_NOTHROW +{ + if (len == 0) return; + + sysuint_t i = index / BITS_PER_ENTITY; // sysuint_t[] + sysuint_t j = index % BITS_PER_ENTITY; // sysuint_t[][] bit index + + // How many bytes process in the first group. + sysuint_t c = BITS_PER_ENTITY - j; + if (c > len) c = len; + + // Offset. + buf += i; + + *buf++ |= (((sysuint_t)-1) >> (BITS_PER_ENTITY - c)) << j; + len -= c; + + while (len >= BITS_PER_ENTITY) + { + *buf++ = (sysuint_t)-1; + len -= BITS_PER_ENTITY; + } + + if (len) + { + *buf |= (((sysuint_t)-1) >> (BITS_PER_ENTITY - len)); + } +} + +static void _ClearBits(sysuint_t* buf, sysuint_t index, sysuint_t len) ASMJIT_NOTHROW +{ + if (len == 0) return; + + sysuint_t i = index / BITS_PER_ENTITY; // sysuint_t[] + sysuint_t j = index % BITS_PER_ENTITY; // sysuint_t[][] bit index + + // How many bytes process in the first group. + sysuint_t c = BITS_PER_ENTITY - j; + if (c > len) c = len; + + // Offset. + buf += i; + + *buf++ &= ~((((sysuint_t)-1) >> (BITS_PER_ENTITY - c)) << j); + len -= c; + + while (len >= BITS_PER_ENTITY) + { + *buf++ = 0; + len -= BITS_PER_ENTITY; + } + + if (len) + { + *buf &= ((sysuint_t)-1) << len; + } +} + +// ============================================================================ +// [AsmJit::MemNode] +// ============================================================================ + +#define M_DIV(x, y) ((x) / (y)) +#define M_MOD(x, y) ((x) % (y)) + +template<typename T> +struct ASMJIT_HIDDEN RbNode +{ + // -------------------------------------------------------------------------- + // [Node red-black tree tree, key is mem pointer]. + // -------------------------------------------------------------------------- + + // Implementation is based on article by Julienne Walker (Public Domain), + // including C code and original comments. Thanks for the excellent article. + + // Left[0] and right[1] nodes. + T* node[2]; + // Whether the node is RED. + uint32_t red; + + // -------------------------------------------------------------------------- + // [Chunk Memory] + // -------------------------------------------------------------------------- + + // Virtual memory address. + uint8_t* mem; +}; + +// Get whether the node is red (NULL or node with red flag). +template<typename T> +inline bool isRed(RbNode<T>* node) +{ + return node != NULL && node->red; +} + +struct ASMJIT_HIDDEN MemNode : public RbNode<MemNode> +{ + // -------------------------------------------------------------------------- + // [Node double-linked list] + // -------------------------------------------------------------------------- + + MemNode* prev; // Prev node in list. + MemNode* next; // Next node in list. + + // -------------------------------------------------------------------------- + // [Chunk Data] + // -------------------------------------------------------------------------- + + sysuint_t size; // How many bytes contain this node. + sysuint_t blocks; // How many blocks are here. + sysuint_t density; // Minimum count of allocated bytes in this node (also alignment). + sysuint_t used; // How many bytes are used in this node. + sysuint_t largestBlock; // Contains largest block that can be allocated. + + sysuint_t* baUsed; // Contains bits about used blocks. + // (0 = unused, 1 = used). + sysuint_t* baCont; // Contains bits about continuous blocks. + // (0 = stop, 1 = continue). + + // -------------------------------------------------------------------------- + // [Methods] + // -------------------------------------------------------------------------- + + // Get available space. + inline sysuint_t getAvailable() const ASMJIT_NOTHROW { return size - used; } + + inline void fillData(MemNode* other) + { + mem = other->mem; + + size = other->size; + blocks = other->blocks; + density = other->density; + used = other->used; + largestBlock = other->largestBlock; + baUsed = other->baUsed; + baCont = other->baCont; + } +}; + +// ============================================================================ +// [AsmJit::M_Permanent] +// ============================================================================ + +//! @brief Permanent node. +struct ASMJIT_HIDDEN PermanentNode +{ + uint8_t* mem; // Base pointer (virtual memory address). + sysuint_t size; // Count of bytes allocated. + sysuint_t used; // Count of bytes used. + PermanentNode* prev; // Pointer to prev chunk or NULL. + + // Get available space. + inline sysuint_t getAvailable() const ASMJIT_NOTHROW { return size - used; } +}; + +// ============================================================================ +// [AsmJit::MemoryManagerPrivate] +// ============================================================================ + +struct ASMJIT_HIDDEN MemoryManagerPrivate +{ + // -------------------------------------------------------------------------- + // [Construction / Destruction] + // -------------------------------------------------------------------------- + +#if !defined(ASMJIT_WINDOWS) + MemoryManagerPrivate() ASMJIT_NOTHROW; +#else + MemoryManagerPrivate(HANDLE hProcess) ASMJIT_NOTHROW; +#endif // ASMJIT_WINDOWS + ~MemoryManagerPrivate() ASMJIT_NOTHROW; + + // -------------------------------------------------------------------------- + // [Allocation] + // -------------------------------------------------------------------------- + + MemNode* createNode(sysuint_t size, sysuint_t density) ASMJIT_NOTHROW; + + void* allocPermanent(sysuint_t vsize) ASMJIT_NOTHROW; + void* allocFreeable(sysuint_t vsize) ASMJIT_NOTHROW; + + bool free(void* address) ASMJIT_NOTHROW; + bool shrink(void* address, sysuint_t used) ASMJIT_NOTHROW; + void freeAll(bool keepVirtualMemory) ASMJIT_NOTHROW; + + // Helpers to avoid ifdefs in the code. + inline uint8_t* allocVirtualMemory(sysuint_t size, sysuint_t* vsize) ASMJIT_NOTHROW + { +#if !defined(ASMJIT_WINDOWS) + return (uint8_t*)VirtualMemory::alloc(size, vsize, true); +#else + return (uint8_t*)VirtualMemory::allocProcessMemory(_hProcess, size, vsize, true); +#endif + } + + inline void freeVirtualMemory(void* vmem, sysuint_t vsize) ASMJIT_NOTHROW + { +#if !defined(ASMJIT_WINDOWS) + VirtualMemory::free(vmem, vsize); +#else + VirtualMemory::freeProcessMemory(_hProcess, vmem, vsize); +#endif + } + + // -------------------------------------------------------------------------- + // [NodeList RB-Tree] + // -------------------------------------------------------------------------- + + bool checkTree() ASMJIT_NOTHROW; + + void insertNode(MemNode* node) ASMJIT_NOTHROW; + MemNode* removeNode(MemNode* node) ASMJIT_NOTHROW; + MemNode* findPtr(uint8_t* mem) ASMJIT_NOTHROW; + + // -------------------------------------------------------------------------- + // [Members] + // -------------------------------------------------------------------------- + +#if defined(ASMJIT_WINDOWS) + HANDLE _hProcess; // Process where to allocate memory. +#endif // ASMJIT_WINDOWS + Lock _lock; // Lock for thread safety. + + sysuint_t _newChunkSize; // Default node size. + sysuint_t _newChunkDensity; // Default node density. + sysuint_t _allocated; // How many bytes are allocated. + sysuint_t _used; // How many bytes are used. + + // Memory nodes list. + MemNode* _first; + MemNode* _last; + MemNode* _optimal; + + // Memory nodes tree. + MemNode* _root; + + // Permanent memory. + PermanentNode* _permanent; + + // Whether to keep virtual memory after destroy. + bool _keepVirtualMemory; +}; + +// ============================================================================ +// [AsmJit::MemoryManagerPrivate - Construction / Destruction] +// ============================================================================ + +#if !defined(ASMJIT_WINDOWS) +MemoryManagerPrivate::MemoryManagerPrivate() ASMJIT_NOTHROW : +#else +MemoryManagerPrivate::MemoryManagerPrivate(HANDLE hProcess) ASMJIT_NOTHROW : + _hProcess(hProcess), +#endif + _newChunkSize(65536), + _newChunkDensity(64), + _allocated(0), + _used(0), + _root(NULL), + _first(NULL), + _last(NULL), + _optimal(NULL), + _permanent(NULL), + _keepVirtualMemory(false) +{ +} + +MemoryManagerPrivate::~MemoryManagerPrivate() ASMJIT_NOTHROW +{ + // Freeable memory cleanup - Also frees the virtual memory if configured to. + freeAll(_keepVirtualMemory); + + // Permanent memory cleanup - Never frees the virtual memory. + PermanentNode* node = _permanent; + while (node) + { + PermanentNode* prev = node->prev; + ASMJIT_FREE(node); + node = prev; + } +} + +// ============================================================================ +// [AsmJit::MemoryManagerPrivate - Allocation] +// ============================================================================ + +// Allocates virtual memory node and MemNode structure. +// +// Returns MemNode* on success, otherwise NULL. +MemNode* MemoryManagerPrivate::createNode(sysuint_t size, sysuint_t density) ASMJIT_NOTHROW +{ + sysuint_t vsize; + uint8_t* vmem = allocVirtualMemory(size, &vsize); + + // Out of memory. + if (vmem == NULL) return NULL; + + sysuint_t blocks = (vsize / density); + sysuint_t bsize = (((blocks + 7) >> 3) + sizeof(sysuint_t) - 1) & ~(sysuint_t)(sizeof(sysuint_t)-1); + + MemNode* node = reinterpret_cast<MemNode*>(ASMJIT_MALLOC(sizeof(MemNode))); + uint8_t* data = reinterpret_cast<uint8_t*>(ASMJIT_MALLOC(bsize * 2)); + + // Out of memory. + if (node == NULL || data == NULL) + { + freeVirtualMemory(vmem, vsize); + if (node) ASMJIT_FREE(node); + if (data) ASMJIT_FREE(data); + return NULL; + } + + // Initialize RbNode data. + node->node[0] = NULL; + node->node[1] = NULL; + node->red = 1; + node->mem = vmem; + + // Initialize MemNode data. + node->prev = NULL; + node->next = NULL; + + node->size = vsize; + node->blocks = blocks; + node->density = density; + node->used = 0; + node->largestBlock = vsize; + + memset(data, 0, bsize * 2); + node->baUsed = reinterpret_cast<sysuint_t*>(data); + node->baCont = reinterpret_cast<sysuint_t*>(data + bsize); + + return node; +} + +void* MemoryManagerPrivate::allocPermanent(sysuint_t vsize) ASMJIT_NOTHROW +{ + static const sysuint_t permanentAlignment = 32; + static const sysuint_t permanentNodeSize = 32768; + + sysuint_t over = vsize % permanentAlignment; + if (over) over = permanentAlignment - over; + sysuint_t alignedSize = vsize + over; + + AutoLock locked(_lock); + + PermanentNode* node = _permanent; + + // Try to find space in allocated chunks. + while (node && alignedSize > node->getAvailable()) node = node->prev; + + // Or allocate new node. + if (!node) + { + sysuint_t nodeSize = permanentNodeSize; + if (vsize > nodeSize) nodeSize = vsize; + + node = (PermanentNode*)ASMJIT_MALLOC(sizeof(PermanentNode)); + // Out of memory. + if (node == NULL) return NULL; + + node->mem = allocVirtualMemory(nodeSize, &node->size); + // Out of memory. + if (node->mem == NULL) + { + ASMJIT_FREE(node); + return NULL; + } + + node->used = 0; + node->prev = _permanent; + _permanent = node; + } + + // Finally, copy function code to our space we reserved for. + uint8_t* result = node->mem + node->used; + + // Update Statistics. + node->used += alignedSize; + _used += alignedSize; + + // Code can be null to only reserve space for code. + return (void*)result; +} + +void* MemoryManagerPrivate::allocFreeable(sysuint_t vsize) ASMJIT_NOTHROW +{ + sysuint_t i; // Current index. + sysuint_t need; // How many we need to be freed. + sysuint_t minVSize; + + // Align to 32 bytes (our default alignment). + vsize = (vsize + 31) & ~(sysuint_t)31; + if (vsize == 0) return NULL; + + AutoLock locked(_lock); + MemNode* node = _optimal; + + minVSize = _newChunkSize; + + // Try to find memory block in existing nodes. + while (node) + { + // Skip this node? + if ((node->getAvailable() < vsize) || + (node->largestBlock < vsize && node->largestBlock != 0)) + { + MemNode* next = node->next; + if (node->getAvailable() < minVSize && node == _optimal && next) _optimal = next; + node = next; + continue; + } + + sysuint_t* up = node->baUsed; // Current ubits address. + sysuint_t ubits; // Current ubits[0] value. + sysuint_t bit; // Current bit mask. + sysuint_t blocks = node->blocks; // Count of blocks in node. + sysuint_t cont = 0; // How many bits are currently freed in find loop. + sysuint_t maxCont = 0; // Largest continuous block (bits count). + sysuint_t j; + + need = M_DIV((vsize + node->density - 1), node->density); + i = 0; + + // Try to find node that is large enough. + while (i < blocks) + { + ubits = *up++; + + // Fast skip used blocks. + if (ubits == (sysuint_t)-1) + { + if (cont > maxCont) maxCont = cont; + cont = 0; + + i += BITS_PER_ENTITY; + continue; + } + + sysuint_t max = BITS_PER_ENTITY; + if (i + max > blocks) max = blocks - i; + + for (j = 0, bit = 1; j < max; bit <<= 1) + { + j++; + if ((ubits & bit) == 0) + { + if (++cont == need) { i += j; i -= cont; goto found; } + continue; + } + + if (cont > maxCont) maxCont = cont; + cont = 0; + } + + i += BITS_PER_ENTITY; + } + + // Because we traversed entire node, we can set largest node size that + // will be used to cache next traversing.. + node->largestBlock = maxCont * node->density; + + node = node->next; + } + + // If we are here, we failed to find existing memory block and we must + // allocate new. + { + sysuint_t chunkSize = _newChunkSize; + if (chunkSize < vsize) chunkSize = vsize; + + node = createNode(chunkSize, _newChunkDensity); + if (node == NULL) return NULL; + + // Update binary tree. + insertNode(node); + ASMJIT_ASSERT(checkTree()); + + // Alloc first node at start. + i = 0; + need = (vsize + node->density - 1) / node->density; + + // Update statistics. + _allocated += node->size; + } + +found: + // Update bits. + _SetBits(node->baUsed, i, need); + _SetBits(node->baCont, i, need - 1); + + // Update statistics. + { + sysuint_t u = need * node->density; + node->used += u; + node->largestBlock = 0; + _used += u; + } + + // And return pointer to allocated memory. + uint8_t* result = node->mem + i * node->density; + ASMJIT_ASSERT(result >= node->mem && result <= node->mem + node->size - vsize); + return result; +} + +bool MemoryManagerPrivate::free(void* address) ASMJIT_NOTHROW +{ + if (address == NULL) return true; + + AutoLock locked(_lock); + + MemNode* node = findPtr((uint8_t*)address); + if (node == NULL) + return false; + + sysuint_t offset = (sysuint_t)((uint8_t*)address - (uint8_t*)node->mem); + sysuint_t bitpos = M_DIV(offset, node->density); + sysuint_t i = (bitpos / BITS_PER_ENTITY); + + sysuint_t* up = node->baUsed + i; // Current ubits address. + sysuint_t* cp = node->baCont + i; // Current cbits address. + sysuint_t ubits = *up; // Current ubits[0] value. + sysuint_t cbits = *cp; // Current cbits[0] value. + sysuint_t bit = (sysuint_t)1 << (bitpos % BITS_PER_ENTITY); + + sysuint_t cont = 0; + bool stop; + + for (;;) + { + stop = (cbits & bit) == 0; + ubits &= ~bit; + cbits &= ~bit; + + bit <<= 1; + cont++; + + if (stop || bit == 0) + { + *up = ubits; + *cp = cbits; + if (stop) break; + + ubits = *++up; + cbits = *++cp; + bit = 1; + } + } + + // If the freed block is fully allocated node then it's needed to + // update 'optimal' pointer in memory manager. + if (node->used == node->size) + { + MemNode* cur = _optimal; + + do { + cur = cur->prev; + if (cur == node) { _optimal = node; break; } + } while (cur); + } + + // Statistics. + cont *= node->density; + if (node->largestBlock < cont) node->largestBlock = cont; + node->used -= cont; + _used -= cont; + + // If page is empty, we can free it. + if (node->used == 0) + { + // Free memory associated with node (this memory is not accessed + // anymore so it's safe). + freeVirtualMemory(node->mem, node->size); + ASMJIT_FREE(node->baUsed); + + node->baUsed = NULL; + node->baCont = NULL; + + // Statistics. + _allocated -= node->size; + + // Remove node. This function can return different node than + // passed into, but data is copied into previous node if needed. + ASMJIT_FREE(removeNode(node)); + ASMJIT_ASSERT(checkTree()); + } + + return true; +} + +bool MemoryManagerPrivate::shrink(void* address, sysuint_t used) ASMJIT_NOTHROW +{ + if (address == NULL) return false; + if (used == 0) return free(address); + + AutoLock locked(_lock); + + MemNode* node = findPtr((uint8_t*)address); + if (node == NULL) + return false; + + sysuint_t offset = (sysuint_t)((uint8_t*)address - (uint8_t*)node->mem); + sysuint_t bitpos = M_DIV(offset, node->density); + sysuint_t i = (bitpos / BITS_PER_ENTITY); + + sysuint_t* up = node->baUsed + i; // Current ubits address. + sysuint_t* cp = node->baCont + i; // Current cbits address. + sysuint_t ubits = *up; // Current ubits[0] value. + sysuint_t cbits = *cp; // Current cbits[0] value. + sysuint_t bit = (sysuint_t)1 << (bitpos % BITS_PER_ENTITY); + + sysuint_t cont = 0; + sysuint_t usedBlocks = (used + node->density - 1) / node->density; + + bool stop; + + // Find the first block we can mark as free. + for (;;) + { + stop = (cbits & bit) == 0; + if (stop) return true; + + if (++cont == usedBlocks) break; + + bit <<= 1; + if (bit == 0) + { + ubits = *++up; + cbits = *++cp; + bit = 1; + } + } + + // Free the tail blocks. + cont = (sysuint_t)-1; + goto enterFreeLoop; + + for (;;) + { + stop = (cbits & bit) == 0; + ubits &= ~bit; +enterFreeLoop: + cbits &= ~bit; + + bit <<= 1; + cont++; + + if (stop || bit == 0) + { + *up = ubits; + *cp = cbits; + if (stop) break; + + ubits = *++up; + cbits = *++cp; + bit = 1; + } + } + + // Statistics. + cont *= node->density; + if (node->largestBlock < cont) node->largestBlock = cont; + node->used -= cont; + _used -= cont; + + return true; +} + +void MemoryManagerPrivate::freeAll(bool keepVirtualMemory) ASMJIT_NOTHROW +{ + MemNode* node = _first; + + while (node) + { + MemNode* next = node->next; + + if (!keepVirtualMemory) freeVirtualMemory(node->mem, node->size); + ASMJIT_FREE(node->baUsed); + ASMJIT_FREE(node); + + node = next; + } + + _allocated = 0; + _used = 0; + + _root = NULL; + _first = NULL; + _last = NULL; + _optimal = NULL; +} + +// ============================================================================ +// [AsmJit::MemoryManagerPrivate - NodeList RB-Tree] +// ============================================================================ + +static int rbAssert(MemNode* root) +{ + if (root == NULL) return 1; + + MemNode* ln = root->node[0]; + MemNode* rn = root->node[1]; + + // Red violation. + ASMJIT_ASSERT( !(isRed(root) && (isRed(ln) || isRed(rn))) ); + + int lh = rbAssert(ln); + int rh = rbAssert(rn); + + // Invalid btree. + ASMJIT_ASSERT(ln == NULL || ln->mem < root->mem); + ASMJIT_ASSERT(rn == NULL || rn->mem > root->mem); + + // Black violation. + ASMJIT_ASSERT( !(lh != 0 && rh != 0 && lh != rh) ); + + // Only count black links. + if (lh != 0 && rh != 0) + return isRed(root) ? lh : lh + 1; + else + return 0; +} + +static inline MemNode* rbRotateSingle(MemNode* root, int dir) +{ + MemNode* save = root->node[!dir]; + + root->node[!dir] = save->node[dir]; + save->node[dir] = root; + + root->red = 1; + save->red = 0; + + return save; +} + +static inline MemNode* rbRotateDouble(MemNode* root, int dir) +{ + root->node[!dir] = rbRotateSingle(root->node[!dir], !dir); + return rbRotateSingle(root, dir); +} + +bool MemoryManagerPrivate::checkTree() ASMJIT_NOTHROW +{ + return rbAssert(_root) > 0; +} + +void MemoryManagerPrivate::insertNode(MemNode* node) ASMJIT_NOTHROW +{ + if (_root == NULL) + { + // Empty tree case. + _root = node; + } + else + { + // False tree root. + RbNode<MemNode> head = {0}; + + // Grandparent & parent. + MemNode* g = NULL; + MemNode* t = reinterpret_cast<MemNode*>(&head); + + // Iterator & parent. + MemNode* p = NULL; + MemNode* q = t->node[1] = _root; + + int dir = 0, last; + + // Search down the tree. + for (;;) + { + if (q == NULL) + { + // Insert new node at the bottom. + q = node; + p->node[dir] = node; + } + else if (isRed(q->node[0]) && isRed(q->node[1])) + { + // Color flip. + q->red = 1; + q->node[0]->red = 0; + q->node[1]->red = 0; + } + + // Fix red violation. + if (isRed(q) && isRed(p)) + { + int dir2 = t->node[1] == g; + t->node[dir2] = (q == p->node[last]) ? rbRotateSingle(g, !last) : rbRotateDouble(g, !last); + } + + // Stop if found. + if (q == node) break; + + last = dir; + dir = q->mem < node->mem; + + // Update helpers. + if (g != NULL) t = g; + g = p; + p = q; + q = q->node[dir]; + } + + // Update root. + _root = head.node[1]; + } + + // Make root black. + _root->red = 0; + + // Link with others. + node->prev = _last; + + if (_first == NULL) + { + _first = node; + _last = node; + _optimal = node; + } + else + { + node->prev = _last; + _last->next = node; + _last = node; + } +} + +MemNode* MemoryManagerPrivate::removeNode(MemNode* node) ASMJIT_NOTHROW +{ + // False tree root. + RbNode<MemNode> head = {0}; + + // Helpers. + MemNode* q = reinterpret_cast<MemNode*>(&head); + MemNode* p = NULL; + MemNode* g = NULL; + // Found item. + MemNode* f = NULL; + int dir = 1; + + // Set up. + q->node[1] = _root; + + // Search and push a red down. + while (q->node[dir] != NULL) + { + int last = dir; + + // Update helpers. + g = p; + p = q; + q = q->node[dir]; + dir = q->mem < node->mem; + + // Save found node. + if (q == node) f = q; + + // Push the red node down. + if (!isRed(q) && !isRed(q->node[dir])) + { + if (isRed(q->node[!dir])) + { + p = p->node[last] = rbRotateSingle(q, dir); + } + else if (!isRed(q->node[!dir])) + { + MemNode* s = p->node[!last]; + + if (s != NULL) + { + if (!isRed(s->node[!last]) && !isRed(s->node[last])) + { + // Color flip. + p->red = 0; + s->red = 1; + q->red = 1; + } + else + { + int dir2 = g->node[1] == p; + + if (isRed(s->node[last])) + g->node[dir2] = rbRotateDouble(p, last); + else if (isRed(s->node[!last])) + g->node[dir2] = rbRotateSingle(p, last); + + // Ensure correct coloring. + q->red = g->node[dir2]->red = 1; + g->node[dir2]->node[0]->red = 0; + g->node[dir2]->node[1]->red = 0; + } + } + } + } + } + + // Replace and remove. + ASMJIT_ASSERT(f != NULL); + ASMJIT_ASSERT(f != reinterpret_cast<MemNode*>(&head)); + ASMJIT_ASSERT(q != reinterpret_cast<MemNode*>(&head)); + + if (f != q) f->fillData(q); + p->node[p->node[1] == q] = q->node[q->node[0] == NULL]; + + // Update root and make it black. + if ((_root = head.node[1]) != NULL) _root->red = 0; + + // Unlink. + MemNode* next = q->next; + MemNode* prev = q->prev; + + if (prev) { prev->next = next; } else { _first = next; } + if (next) { next->prev = prev; } else { _last = prev; } + if (_optimal == q) { _optimal = prev ? prev : next; } + + return q; +} + +MemNode* MemoryManagerPrivate::findPtr(uint8_t* mem) ASMJIT_NOTHROW +{ + MemNode* cur = _root; + while (cur) + { + uint8_t* curMem = cur->mem; + if (mem < curMem) + { + // Go left. + cur = cur->node[0]; + continue; + } + else + { + uint8_t* curEnd = curMem + cur->size; + if (mem >= curEnd) + { + // Go right. + cur = cur->node[1]; + continue; + } + else + { + // Match. + break; + } + } + } + return cur; +} + +// ============================================================================ +// [AsmJit::MemoryManager] +// ============================================================================ + +MemoryManager::MemoryManager() ASMJIT_NOTHROW +{ +} + +MemoryManager::~MemoryManager() ASMJIT_NOTHROW +{ +} + +MemoryManager* MemoryManager::getGlobal() ASMJIT_NOTHROW +{ + static VirtualMemoryManager memmgr; + return &memmgr; +} + +// ============================================================================ +// [AsmJit::VirtualMemoryManager] +// ============================================================================ + +#if !defined(ASMJIT_WINDOWS) +VirtualMemoryManager::VirtualMemoryManager() ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = new(std::nothrow) MemoryManagerPrivate(); + _d = (void*)d; +} +#else +VirtualMemoryManager::VirtualMemoryManager() ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = new(std::nothrow) MemoryManagerPrivate(GetCurrentProcess()); + _d = (void*)d; +} + +VirtualMemoryManager::VirtualMemoryManager(HANDLE hProcess) ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = new(std::nothrow) MemoryManagerPrivate(hProcess); + _d = (void*)d; +} +#endif // ASMJIT_WINDOWS + +VirtualMemoryManager::~VirtualMemoryManager() ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = reinterpret_cast<MemoryManagerPrivate*>(_d); + delete d; +} + +void* VirtualMemoryManager::alloc(sysuint_t size, uint32_t type) ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = reinterpret_cast<MemoryManagerPrivate*>(_d); + + if (type == MEMORY_ALLOC_PERMANENT) + return d->allocPermanent(size); + else + return d->allocFreeable(size); +} + +bool VirtualMemoryManager::free(void* address) ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = reinterpret_cast<MemoryManagerPrivate*>(_d); + return d->free(address); +} + +bool VirtualMemoryManager::shrink(void* address, sysuint_t used) ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = reinterpret_cast<MemoryManagerPrivate*>(_d); + return d->shrink(address, used); +} + +void VirtualMemoryManager::freeAll() ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = reinterpret_cast<MemoryManagerPrivate*>(_d); + + // Calling MemoryManager::freeAll() will never keep allocated memory. + return d->freeAll(false); +} + +sysuint_t VirtualMemoryManager::getUsedBytes() ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = reinterpret_cast<MemoryManagerPrivate*>(_d); + return d->_used; +} + +sysuint_t VirtualMemoryManager::getAllocatedBytes() ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = reinterpret_cast<MemoryManagerPrivate*>(_d); + return d->_allocated; +} + +bool VirtualMemoryManager::getKeepVirtualMemory() const ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = reinterpret_cast<MemoryManagerPrivate*>(_d); + return d->_keepVirtualMemory; +} + +void VirtualMemoryManager::setKeepVirtualMemory(bool keepVirtualMemory) ASMJIT_NOTHROW +{ + MemoryManagerPrivate* d = reinterpret_cast<MemoryManagerPrivate*>(_d); + d->_keepVirtualMemory = keepVirtualMemory; +} + +// ============================================================================ +// [AsmJit::VirtualMemoryManager - Debug] +// ============================================================================ + +#if defined(ASMJIT_MEMORY_MANAGER_DUMP) + +struct ASMJIT_HIDDEN GraphVizContext +{ + GraphVizContext(); + ~GraphVizContext(); + + bool openFile(const char* fileName); + void closeFile(); + + void dumpNode(MemNode* node); + void connect(MemNode* node, MemNode* other, const char* dst); + + FILE* file; +}; + +GraphVizContext::GraphVizContext() : + file(NULL) +{ +} + +GraphVizContext::~GraphVizContext() +{ + closeFile(); +} + +bool GraphVizContext::openFile(const char* fileName) +{ + file = fopen(fileName, "w"); + return file != NULL; +} + +void GraphVizContext::closeFile() +{ + if (file) { fclose(file); file = NULL; } +} + +void GraphVizContext::dumpNode(MemNode* node) +{ + fprintf(file, " NODE_%p [shape=record, style=filled, color=%s, label=\"<L>|<C>Mem: %p, Used: %d/%d|<R>\"];\n", + node, + node->red ? "red" : "gray", + node->mem, node->used, node->size); + + if (node->node[0]) connect(node, node->node[0], "L"); + if (node->node[1]) connect(node, node->node[1], "R"); +} + +void GraphVizContext::connect(MemNode* node, MemNode* other, const char* dst) +{ + dumpNode(other); + + fprintf(file, " NODE_%p:%s -> NODE_%p:C", node, dst, other); + if (other->red) fprintf(file, " [style=bold, color=red]"); + fprintf(file, ";\n"); +} + +void VirtualMemoryManager::dump(const char* fileName) +{ + MemoryManagerPrivate* d = reinterpret_cast<MemoryManagerPrivate*>(_d); + GraphVizContext ctx; + if (!ctx.openFile(fileName)) return; + + fprintf(ctx.file, "digraph {\n"); + if (d->_root) ctx.dumpNode(d->_root); + fprintf(ctx.file, "}\n"); +} +#endif // ASMJIT_MEMORY_MANAGER_DUMP + +} // AsmJit namespace + +// [Api-End] +#include "ApiEnd.h" |