diff -r 000000000000 -r 4f2f89ce4247 JavaScriptCore/jit/ExecutableAllocatorFixedVMPool.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/JavaScriptCore/jit/ExecutableAllocatorFixedVMPool.cpp Fri Sep 17 09:02:29 2010 +0300 @@ -0,0 +1,479 @@ +/* + * Copyright (C) 2009 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#include "ExecutableAllocator.h" + +#if ENABLE(EXECUTABLE_ALLOCATOR_FIXED) + +#include + +#include "TCSpinLock.h" +#include +#include +#include +#include + +#if CPU(X86_64) + // These limits suitable on 64-bit platforms (particularly x86-64, where we require all jumps to have a 2Gb max range). + #define VM_POOL_SIZE (2u * 1024u * 1024u * 1024u) // 2Gb + #define COALESCE_LIMIT (16u * 1024u * 1024u) // 16Mb +#else + // These limits are hopefully sensible on embedded platforms. + #define VM_POOL_SIZE (32u * 1024u * 1024u) // 32Mb + #define COALESCE_LIMIT (4u * 1024u * 1024u) // 4Mb +#endif + +// ASLR currently only works on darwin (due to arc4random) & 64-bit (due to address space size). +#define VM_POOL_ASLR (OS(DARWIN) && CPU(X86_64)) + +using namespace WTF; + +namespace JSC { + +// FreeListEntry describes a free chunk of memory, stored in the freeList. +struct FreeListEntry { + FreeListEntry(void* pointer, size_t size) + : pointer(pointer) + , size(size) + , nextEntry(0) + , less(0) + , greater(0) + , balanceFactor(0) + { + } + + // All entries of the same size share a single entry + // in the AVLTree, and are linked together in a linked + // list, using nextEntry. + void* pointer; + size_t size; + FreeListEntry* nextEntry; + + // These fields are used by AVLTree. + FreeListEntry* less; + FreeListEntry* greater; + int balanceFactor; +}; + +// Abstractor class for use in AVLTree. +// Nodes in the AVLTree are of type FreeListEntry, keyed on +// (and thus sorted by) their size. +struct AVLTreeAbstractorForFreeList { + typedef FreeListEntry* handle; + typedef int32_t size; + typedef size_t key; + + handle get_less(handle h) { return h->less; } + void set_less(handle h, handle lh) { h->less = lh; } + handle get_greater(handle h) { return h->greater; } + void set_greater(handle h, handle gh) { h->greater = gh; } + int get_balance_factor(handle h) { return h->balanceFactor; } + void set_balance_factor(handle h, int bf) { h->balanceFactor = bf; } + + static handle null() { return 0; } + + int compare_key_key(key va, key vb) { return va - vb; } + int compare_key_node(key k, handle h) { return compare_key_key(k, h->size); } + int compare_node_node(handle h1, handle h2) { return compare_key_key(h1->size, h2->size); } +}; + +// Used to reverse sort an array of FreeListEntry pointers. +static int reverseSortFreeListEntriesByPointer(const void* leftPtr, const void* rightPtr) +{ + FreeListEntry* left = *(FreeListEntry**)leftPtr; + FreeListEntry* right = *(FreeListEntry**)rightPtr; + + return (intptr_t)(right->pointer) - (intptr_t)(left->pointer); +} + +// Used to reverse sort an array of pointers. +static int reverseSortCommonSizedAllocations(const void* leftPtr, const void* rightPtr) +{ + void* left = *(void**)leftPtr; + void* right = *(void**)rightPtr; + + return (intptr_t)right - (intptr_t)left; +} + +class FixedVMPoolAllocator +{ + // The free list is stored in a sorted tree. + typedef AVLTree SizeSortedFreeTree; + + // Use madvise as apropriate to prevent freed pages from being spilled, + // and to attempt to ensure that used memory is reported correctly. +#if HAVE(MADV_FREE_REUSE) + void release(void* position, size_t size) + { + while (madvise(position, size, MADV_FREE_REUSABLE) == -1 && errno == EAGAIN) { } + } + + void reuse(void* position, size_t size) + { + while (madvise(position, size, MADV_FREE_REUSE) == -1 && errno == EAGAIN) { } + } +#elif HAVE(MADV_DONTNEED) + void release(void* position, size_t size) + { + while (madvise(position, size, MADV_DONTNEED) == -1 && errno == EAGAIN) { } + } + + void reuse(void*, size_t) {} +#else + void release(void*, size_t) {} + void reuse(void*, size_t) {} +#endif + + // All addition to the free list should go through this method, rather than + // calling insert directly, to avoid multiple entries beging added with the + // same key. All nodes being added should be singletons, they should not + // already be a part of a chain. + void addToFreeList(FreeListEntry* entry) + { + ASSERT(!entry->nextEntry); + + if (entry->size == m_commonSize) { + m_commonSizedAllocations.append(entry->pointer); + delete entry; + } else if (FreeListEntry* entryInFreeList = m_freeList.search(entry->size, m_freeList.EQUAL)) { + // m_freeList already contain an entry for this size - insert this node into the chain. + entry->nextEntry = entryInFreeList->nextEntry; + entryInFreeList->nextEntry = entry; + } else + m_freeList.insert(entry); + } + + // We do not attempt to coalesce addition, which may lead to fragmentation; + // instead we periodically perform a sweep to try to coalesce neigboring + // entries in m_freeList. Presently this is triggered at the point 16MB + // of memory has been released. + void coalesceFreeSpace() + { + Vector freeListEntries; + SizeSortedFreeTree::Iterator iter; + iter.start_iter_least(m_freeList); + + // Empty m_freeList into a Vector. + for (FreeListEntry* entry; (entry = *iter); ++iter) { + // Each entry in m_freeList might correspond to multiple + // free chunks of memory (of the same size). Walk the chain + // (this is likely of couse only be one entry long!) adding + // each entry to the Vector (at reseting the next in chain + // pointer to separate each node out). + FreeListEntry* next; + do { + next = entry->nextEntry; + entry->nextEntry = 0; + freeListEntries.append(entry); + } while ((entry = next)); + } + // All entries are now in the Vector; purge the tree. + m_freeList.purge(); + + // Reverse-sort the freeListEntries and m_commonSizedAllocations Vectors. + // We reverse-sort so that we can logically work forwards through memory, + // whilst popping items off the end of the Vectors using last() and removeLast(). + qsort(freeListEntries.begin(), freeListEntries.size(), sizeof(FreeListEntry*), reverseSortFreeListEntriesByPointer); + qsort(m_commonSizedAllocations.begin(), m_commonSizedAllocations.size(), sizeof(void*), reverseSortCommonSizedAllocations); + + // The entries from m_commonSizedAllocations that cannot be + // coalesced into larger chunks will be temporarily stored here. + Vector newCommonSizedAllocations; + + // Keep processing so long as entries remain in either of the vectors. + while (freeListEntries.size() || m_commonSizedAllocations.size()) { + // We're going to try to find a FreeListEntry node that we can coalesce onto. + FreeListEntry* coalescionEntry = 0; + + // Is the lowest addressed chunk of free memory of common-size, or is it in the free list? + if (m_commonSizedAllocations.size() && (!freeListEntries.size() || (m_commonSizedAllocations.last() < freeListEntries.last()->pointer))) { + // Pop an item from the m_commonSizedAllocations vector - this is the lowest + // addressed free chunk. Find out the begin and end addresses of the memory chunk. + void* begin = m_commonSizedAllocations.last(); + void* end = (void*)((intptr_t)begin + m_commonSize); + m_commonSizedAllocations.removeLast(); + + // Try to find another free chunk abutting onto the end of the one we have already found. + if (freeListEntries.size() && (freeListEntries.last()->pointer == end)) { + // There is an existing FreeListEntry for the next chunk of memory! + // we can reuse this. Pop it off the end of m_freeList. + coalescionEntry = freeListEntries.last(); + freeListEntries.removeLast(); + // Update the existing node to include the common-sized chunk that we also found. + coalescionEntry->pointer = (void*)((intptr_t)coalescionEntry->pointer - m_commonSize); + coalescionEntry->size += m_commonSize; + } else if (m_commonSizedAllocations.size() && (m_commonSizedAllocations.last() == end)) { + // There is a second common-sized chunk that can be coalesced. + // Allocate a new node. + m_commonSizedAllocations.removeLast(); + coalescionEntry = new FreeListEntry(begin, 2 * m_commonSize); + } else { + // Nope - this poor little guy is all on his own. :-( + // Add him into the newCommonSizedAllocations vector for now, we're + // going to end up adding him back into the m_commonSizedAllocations + // list when we're done. + newCommonSizedAllocations.append(begin); + continue; + } + } else { + ASSERT(freeListEntries.size()); + ASSERT(!m_commonSizedAllocations.size() || (freeListEntries.last()->pointer < m_commonSizedAllocations.last())); + // The lowest addressed item is from m_freeList; pop it from the Vector. + coalescionEntry = freeListEntries.last(); + freeListEntries.removeLast(); + } + + // Right, we have a FreeListEntry, we just need check if there is anything else + // to coalesce onto the end. + ASSERT(coalescionEntry); + while (true) { + // Calculate the end address of the chunk we have found so far. + void* end = (void*)((intptr_t)coalescionEntry->pointer - coalescionEntry->size); + + // Is there another chunk adjacent to the one we already have? + if (freeListEntries.size() && (freeListEntries.last()->pointer == end)) { + // Yes - another FreeListEntry -pop it from the list. + FreeListEntry* coalescee = freeListEntries.last(); + freeListEntries.removeLast(); + // Add it's size onto our existing node. + coalescionEntry->size += coalescee->size; + delete coalescee; + } else if (m_commonSizedAllocations.size() && (m_commonSizedAllocations.last() == end)) { + // We can coalesce the next common-sized chunk. + m_commonSizedAllocations.removeLast(); + coalescionEntry->size += m_commonSize; + } else + break; // Nope, nothing to be added - stop here. + } + + // We've coalesced everything we can onto the current chunk. + // Add it back into m_freeList. + addToFreeList(coalescionEntry); + } + + // All chunks of free memory larger than m_commonSize should be + // back in m_freeList by now. All that remains to be done is to + // copy the contents on the newCommonSizedAllocations back into + // the m_commonSizedAllocations Vector. + ASSERT(m_commonSizedAllocations.size() == 0); + m_commonSizedAllocations.append(newCommonSizedAllocations); + } + +public: + + FixedVMPoolAllocator(size_t commonSize, size_t totalHeapSize) + : m_commonSize(commonSize) + , m_countFreedSinceLastCoalesce(0) + , m_totalHeapSize(totalHeapSize) + { + // Cook up an address to allocate at, using the following recipe: + // 17 bits of zero, stay in userspace kids. + // 26 bits of randomness for ASLR. + // 21 bits of zero, at least stay aligned within one level of the pagetables. + // + // But! - as a temporary workaround for some plugin problems (rdar://problem/6812854), + // for now instead of 2^26 bits of ASLR lets stick with 25 bits of randomization plus + // 2^24, which should put up somewhere in the middle of usespace (in the address range + // 0x200000000000 .. 0x5fffffffffff). + intptr_t randomLocation = 0; +#if VM_POOL_ASLR + randomLocation = arc4random() & ((1 << 25) - 1); + randomLocation += (1 << 24); + randomLocation <<= 21; +#endif + m_base = mmap(reinterpret_cast(randomLocation), m_totalHeapSize, INITIAL_PROTECTION_FLAGS, MAP_PRIVATE | MAP_ANON, VM_TAG_FOR_EXECUTABLEALLOCATOR_MEMORY, 0); + + if (m_base) { + // For simplicity, we keep all memory in m_freeList in a 'released' state. + // This means that we can simply reuse all memory when allocating, without + // worrying about it's previous state, and also makes coalescing m_freeList + // simpler since we need not worry about the possibility of coalescing released + // chunks with non-released ones. + release(m_base, m_totalHeapSize); + m_freeList.insert(new FreeListEntry(m_base, m_totalHeapSize)); + } +#if !ENABLE(INTERPRETER) + else + CRASH(); +#endif + } + + void* alloc(size_t size) + { +#if ENABLE(INTERPRETER) + if (!m_base) + return 0; +#else + ASSERT(m_base); +#endif + void* result; + + // Freed allocations of the common size are not stored back into the main + // m_freeList, but are instead stored in a separate vector. If the request + // is for a common sized allocation, check this list. + if ((size == m_commonSize) && m_commonSizedAllocations.size()) { + result = m_commonSizedAllocations.last(); + m_commonSizedAllocations.removeLast(); + } else { + // Serach m_freeList for a suitable sized chunk to allocate memory from. + FreeListEntry* entry = m_freeList.search(size, m_freeList.GREATER_EQUAL); + + // This would be bad news. + if (!entry) { + // Errk! Lets take a last-ditch desparation attempt at defragmentation... + coalesceFreeSpace(); + // Did that free up a large enough chunk? + entry = m_freeList.search(size, m_freeList.GREATER_EQUAL); + // No?... *BOOM!* + if (!entry) + CRASH(); + } + ASSERT(entry->size != m_commonSize); + + // Remove the entry from m_freeList. But! - + // Each entry in the tree may represent a chain of multiple chunks of the + // same size, and we only want to remove one on them. So, if this entry + // does have a chain, just remove the first-but-one item from the chain. + if (FreeListEntry* next = entry->nextEntry) { + // We're going to leave 'entry' in the tree; remove 'next' from its chain. + entry->nextEntry = next->nextEntry; + next->nextEntry = 0; + entry = next; + } else + m_freeList.remove(entry->size); + + // Whoo!, we have a result! + ASSERT(entry->size >= size); + result = entry->pointer; + + // If the allocation exactly fits the chunk we found in the, + // m_freeList then the FreeListEntry node is no longer needed. + if (entry->size == size) + delete entry; + else { + // There is memory left over, and it is not of the common size. + // We can reuse the existing FreeListEntry node to add this back + // into m_freeList. + entry->pointer = (void*)((intptr_t)entry->pointer + size); + entry->size -= size; + addToFreeList(entry); + } + } + + // Call reuse to report to the operating system that this memory is in use. + ASSERT(isWithinVMPool(result, size)); + reuse(result, size); + return result; + } + + void free(void* pointer, size_t size) + { + ASSERT(m_base); + // Call release to report to the operating system that this + // memory is no longer in use, and need not be paged out. + ASSERT(isWithinVMPool(pointer, size)); + release(pointer, size); + + // Common-sized allocations are stored in the m_commonSizedAllocations + // vector; all other freed chunks are added to m_freeList. + if (size == m_commonSize) + m_commonSizedAllocations.append(pointer); + else + addToFreeList(new FreeListEntry(pointer, size)); + + // Do some housekeeping. Every time we reach a point that + // 16MB of allocations have been freed, sweep m_freeList + // coalescing any neighboring fragments. + m_countFreedSinceLastCoalesce += size; + if (m_countFreedSinceLastCoalesce >= COALESCE_LIMIT) { + m_countFreedSinceLastCoalesce = 0; + coalesceFreeSpace(); + } + } + + bool isValid() const { return !!m_base; } + +private: + +#ifndef NDEBUG + bool isWithinVMPool(void* pointer, size_t size) + { + return pointer >= m_base && (reinterpret_cast(pointer) + size <= reinterpret_cast(m_base) + m_totalHeapSize); + } +#endif + + // Freed space from the most common sized allocations will be held in this list, ... + const size_t m_commonSize; + Vector m_commonSizedAllocations; + + // ... and all other freed allocations are held in m_freeList. + SizeSortedFreeTree m_freeList; + + // This is used for housekeeping, to trigger defragmentation of the freed lists. + size_t m_countFreedSinceLastCoalesce; + + void* m_base; + size_t m_totalHeapSize; +}; + +void ExecutableAllocator::intializePageSize() +{ + ExecutableAllocator::pageSize = getpagesize(); +} + +static FixedVMPoolAllocator* allocator = 0; +static SpinLock spinlock = SPINLOCK_INITIALIZER; + +bool ExecutableAllocator::isValid() const +{ + SpinLockHolder lock_holder(&spinlock); + if (!allocator) + allocator = new FixedVMPoolAllocator(JIT_ALLOCATOR_LARGE_ALLOC_SIZE, VM_POOL_SIZE); + return allocator->isValid(); +} + +ExecutablePool::Allocation ExecutablePool::systemAlloc(size_t size) +{ + SpinLockHolder lock_holder(&spinlock); + + ASSERT(allocator); + ExecutablePool::Allocation alloc = {reinterpret_cast(allocator->alloc(size)), size}; + return alloc; +} + +void ExecutablePool::systemRelease(const ExecutablePool::Allocation& allocation) +{ + SpinLockHolder lock_holder(&spinlock); + + ASSERT(allocator); + allocator->free(allocation.pages, allocation.size); +} + +} + + +#endif // HAVE(ASSEMBLER)