1/*
2 * Copyright (C) 2009 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27
28#include "ExecutableAllocator.h"
29
30#if ENABLE(EXECUTABLE_ALLOCATOR_FIXED)
31
32#include <errno.h>
33
34#include "TCSpinLock.h"
35#include <sys/mman.h>
36#include <unistd.h>
37#include <wtf/AVLTree.h>
38#include <wtf/VMTags.h>
39
40#if CPU(X86_64)
41 // These limits suitable on 64-bit platforms (particularly x86-64, where we require all jumps to have a 2Gb max range).
42#ifdef QT_USE_ONEGB_VMALLOCATOR
43 #define VM_POOL_SIZE (1024u * 1024u * 1024u) // 1Gb
44#else
45 #define VM_POOL_SIZE (2u * 1024u * 1024u * 1024u) // 2Gb
46#endif
47 #define COALESCE_LIMIT (16u * 1024u * 1024u) // 16Mb
48#else
49 // These limits are hopefully sensible on embedded platforms.
50 #define VM_POOL_SIZE (32u * 1024u * 1024u) // 32Mb
51 #define COALESCE_LIMIT (4u * 1024u * 1024u) // 4Mb
52#endif
53
54// ASLR currently only works on darwin (due to arc4random) & 64-bit (due to address space size).
55#define VM_POOL_ASLR (OS(DARWIN) && CPU(X86_64))
56
57using namespace WTF;
58
59namespace JSC {
60
61// FreeListEntry describes a free chunk of memory, stored in the freeList.
62struct FreeListEntry {
63 FreeListEntry(void* pointer, size_t size)
64 : pointer(pointer)
65 , size(size)
66 , nextEntry(0)
67 , less(0)
68 , greater(0)
69 , balanceFactor(0)
70 {
71 }
72
73 // All entries of the same size share a single entry
74 // in the AVLTree, and are linked together in a linked
75 // list, using nextEntry.
76 void* pointer;
77 size_t size;
78 FreeListEntry* nextEntry;
79
80 // These fields are used by AVLTree.
81 FreeListEntry* less;
82 FreeListEntry* greater;
83 int balanceFactor;
84};
85
86// Abstractor class for use in AVLTree.
87// Nodes in the AVLTree are of type FreeListEntry, keyed on
88// (and thus sorted by) their size.
89struct AVLTreeAbstractorForFreeList {
90 typedef FreeListEntry* handle;
91 typedef int32_t size;
92 typedef size_t key;
93
94 handle get_less(handle h) { return h->less; }
95 void set_less(handle h, handle lh) { h->less = lh; }
96 handle get_greater(handle h) { return h->greater; }
97 void set_greater(handle h, handle gh) { h->greater = gh; }
98 int get_balance_factor(handle h) { return h->balanceFactor; }
99 void set_balance_factor(handle h, int bf) { h->balanceFactor = bf; }
100
101 static handle null() { return 0; }
102
103 int compare_key_key(key va, key vb) { return va - vb; }
104 int compare_key_node(key k, handle h) { return compare_key_key(va: k, vb: h->size); }
105 int compare_node_node(handle h1, handle h2) { return compare_key_key(va: h1->size, vb: h2->size); }
106};
107
108// Used to reverse sort an array of FreeListEntry pointers.
109static int reverseSortFreeListEntriesByPointer(const void* leftPtr, const void* rightPtr)
110{
111 FreeListEntry* left = *(FreeListEntry**)leftPtr;
112 FreeListEntry* right = *(FreeListEntry**)rightPtr;
113
114 return (intptr_t)(right->pointer) - (intptr_t)(left->pointer);
115}
116
117// Used to reverse sort an array of pointers.
118static int reverseSortCommonSizedAllocations(const void* leftPtr, const void* rightPtr)
119{
120 void* left = *(void**)leftPtr;
121 void* right = *(void**)rightPtr;
122
123 return (intptr_t)right - (intptr_t)left;
124}
125
126class FixedVMPoolAllocator
127{
128 // The free list is stored in a sorted tree.
129 typedef AVLTree<AVLTreeAbstractorForFreeList, 40> SizeSortedFreeTree;
130
131 // Use madvise as apropriate to prevent freed pages from being spilled,
132 // and to attempt to ensure that used memory is reported correctly.
133#if HAVE(MADV_FREE_REUSE)
134 void release(void* position, size_t size)
135 {
136 while (madvise(position, size, MADV_FREE_REUSABLE) == -1 && errno == EAGAIN) { }
137 }
138
139 void reuse(void* position, size_t size)
140 {
141 while (madvise(position, size, MADV_FREE_REUSE) == -1 && errno == EAGAIN) { }
142 }
143#elif HAVE(MADV_DONTNEED)
144 void release(void* position, size_t size)
145 {
146 while (madvise(position, size, MADV_DONTNEED) == -1 && errno == EAGAIN) { }
147 }
148
149 void reuse(void*, size_t) {}
150#else
151 void release(void*, size_t) {}
152 void reuse(void*, size_t) {}
153#endif
154
155 // All addition to the free list should go through this method, rather than
156 // calling insert directly, to avoid multiple entries beging added with the
157 // same key. All nodes being added should be singletons, they should not
158 // already be a part of a chain.
159 void addToFreeList(FreeListEntry* entry)
160 {
161 ASSERT(!entry->nextEntry);
162
163 if (entry->size == m_commonSize) {
164 m_commonSizedAllocations.append(val: entry->pointer);
165 delete entry;
166 } else if (FreeListEntry* entryInFreeList = m_freeList.search(k: entry->size, st: m_freeList.EQUAL)) {
167 // m_freeList already contain an entry for this size - insert this node into the chain.
168 entry->nextEntry = entryInFreeList->nextEntry;
169 entryInFreeList->nextEntry = entry;
170 } else
171 m_freeList.insert(h: entry);
172 }
173
174 // We do not attempt to coalesce addition, which may lead to fragmentation;
175 // instead we periodically perform a sweep to try to coalesce neigboring
176 // entries in m_freeList. Presently this is triggered at the point 16MB
177 // of memory has been released.
178 void coalesceFreeSpace()
179 {
180 Vector<FreeListEntry*> freeListEntries;
181 SizeSortedFreeTree::Iterator iter;
182 iter.start_iter_least(tree&: m_freeList);
183
184 // Empty m_freeList into a Vector.
185 for (FreeListEntry* entry; (entry = *iter); ++iter) {
186 // Each entry in m_freeList might correspond to multiple
187 // free chunks of memory (of the same size). Walk the chain
188 // (this is likely of couse only be one entry long!) adding
189 // each entry to the Vector (at reseting the next in chain
190 // pointer to separate each node out).
191 FreeListEntry* next;
192 do {
193 next = entry->nextEntry;
194 entry->nextEntry = 0;
195 freeListEntries.append(val: entry);
196 } while ((entry = next));
197 }
198 // All entries are now in the Vector; purge the tree.
199 m_freeList.purge();
200
201 // Reverse-sort the freeListEntries and m_commonSizedAllocations Vectors.
202 // We reverse-sort so that we can logically work forwards through memory,
203 // whilst popping items off the end of the Vectors using last() and removeLast().
204 qsort(base: freeListEntries.begin(), nmemb: freeListEntries.size(), size: sizeof(FreeListEntry*), compar: reverseSortFreeListEntriesByPointer);
205 qsort(base: m_commonSizedAllocations.begin(), nmemb: m_commonSizedAllocations.size(), size: sizeof(void*), compar: reverseSortCommonSizedAllocations);
206
207 // The entries from m_commonSizedAllocations that cannot be
208 // coalesced into larger chunks will be temporarily stored here.
209 Vector<void*> newCommonSizedAllocations;
210
211 // Keep processing so long as entries remain in either of the vectors.
212 while (freeListEntries.size() || m_commonSizedAllocations.size()) {
213 // We're going to try to find a FreeListEntry node that we can coalesce onto.
214 FreeListEntry* coalescionEntry = 0;
215
216 // Is the lowest addressed chunk of free memory of common-size, or is it in the free list?
217 if (m_commonSizedAllocations.size() && (!freeListEntries.size() || (m_commonSizedAllocations.last() < freeListEntries.last()->pointer))) {
218 // Pop an item from the m_commonSizedAllocations vector - this is the lowest
219 // addressed free chunk. Find out the begin and end addresses of the memory chunk.
220 void* begin = m_commonSizedAllocations.last();
221 void* end = (void*)((intptr_t)begin + m_commonSize);
222 m_commonSizedAllocations.removeLast();
223
224 // Try to find another free chunk abutting onto the end of the one we have already found.
225 if (freeListEntries.size() && (freeListEntries.last()->pointer == end)) {
226 // There is an existing FreeListEntry for the next chunk of memory!
227 // we can reuse this. Pop it off the end of m_freeList.
228 coalescionEntry = freeListEntries.last();
229 freeListEntries.removeLast();
230 // Update the existing node to include the common-sized chunk that we also found.
231 coalescionEntry->pointer = (void*)((intptr_t)coalescionEntry->pointer - m_commonSize);
232 coalescionEntry->size += m_commonSize;
233 } else if (m_commonSizedAllocations.size() && (m_commonSizedAllocations.last() == end)) {
234 // There is a second common-sized chunk that can be coalesced.
235 // Allocate a new node.
236 m_commonSizedAllocations.removeLast();
237 coalescionEntry = new FreeListEntry(begin, 2 * m_commonSize);
238 } else {
239 // Nope - this poor little guy is all on his own. :-(
240 // Add him into the newCommonSizedAllocations vector for now, we're
241 // going to end up adding him back into the m_commonSizedAllocations
242 // list when we're done.
243 newCommonSizedAllocations.append(val: begin);
244 continue;
245 }
246 } else {
247 ASSERT(freeListEntries.size());
248 ASSERT(!m_commonSizedAllocations.size() || (freeListEntries.last()->pointer < m_commonSizedAllocations.last()));
249 // The lowest addressed item is from m_freeList; pop it from the Vector.
250 coalescionEntry = freeListEntries.last();
251 freeListEntries.removeLast();
252 }
253
254 // Right, we have a FreeListEntry, we just need check if there is anything else
255 // to coalesce onto the end.
256 ASSERT(coalescionEntry);
257 while (true) {
258 // Calculate the end address of the chunk we have found so far.
259 void* end = (void*)((intptr_t)coalescionEntry->pointer - coalescionEntry->size);
260
261 // Is there another chunk adjacent to the one we already have?
262 if (freeListEntries.size() && (freeListEntries.last()->pointer == end)) {
263 // Yes - another FreeListEntry -pop it from the list.
264 FreeListEntry* coalescee = freeListEntries.last();
265 freeListEntries.removeLast();
266 // Add it's size onto our existing node.
267 coalescionEntry->size += coalescee->size;
268 delete coalescee;
269 } else if (m_commonSizedAllocations.size() && (m_commonSizedAllocations.last() == end)) {
270 // We can coalesce the next common-sized chunk.
271 m_commonSizedAllocations.removeLast();
272 coalescionEntry->size += m_commonSize;
273 } else
274 break; // Nope, nothing to be added - stop here.
275 }
276
277 // We've coalesced everything we can onto the current chunk.
278 // Add it back into m_freeList.
279 addToFreeList(entry: coalescionEntry);
280 }
281
282 // All chunks of free memory larger than m_commonSize should be
283 // back in m_freeList by now. All that remains to be done is to
284 // copy the contents on the newCommonSizedAllocations back into
285 // the m_commonSizedAllocations Vector.
286 ASSERT(m_commonSizedAllocations.size() == 0);
287 m_commonSizedAllocations.append(val: newCommonSizedAllocations);
288 }
289
290public:
291
292 FixedVMPoolAllocator(size_t commonSize, size_t totalHeapSize)
293 : m_commonSize(commonSize)
294 , m_countFreedSinceLastCoalesce(0)
295 , m_totalHeapSize(totalHeapSize)
296 {
297 // Cook up an address to allocate at, using the following recipe:
298 // 17 bits of zero, stay in userspace kids.
299 // 26 bits of randomness for ASLR.
300 // 21 bits of zero, at least stay aligned within one level of the pagetables.
301 //
302 // But! - as a temporary workaround for some plugin problems (rdar://problem/6812854),
303 // for now instead of 2^26 bits of ASLR lets stick with 25 bits of randomization plus
304 // 2^24, which should put up somewhere in the middle of usespace (in the address range
305 // 0x200000000000 .. 0x5fffffffffff).
306 intptr_t randomLocation = 0;
307#if VM_POOL_ASLR
308 randomLocation = arc4random() & ((1 << 25) - 1);
309 randomLocation += (1 << 24);
310 randomLocation <<= 21;
311#endif
312 m_base = mmap(addr: reinterpret_cast<void*>(randomLocation), len: m_totalHeapSize, INITIAL_PROTECTION_FLAGS, MAP_PRIVATE | MAP_ANON | MAP_NORESERVE, VM_TAG_FOR_EXECUTABLEALLOCATOR_MEMORY, offset: 0);
313 if (m_base == MAP_FAILED)
314 CRASH();
315
316 // For simplicity, we keep all memory in m_freeList in a 'released' state.
317 // This means that we can simply reuse all memory when allocating, without
318 // worrying about it's previous state, and also makes coalescing m_freeList
319 // simpler since we need not worry about the possibility of coalescing released
320 // chunks with non-released ones.
321 release(m_base, m_totalHeapSize);
322 m_freeList.insert(h: new FreeListEntry(m_base, m_totalHeapSize));
323 }
324
325 void* alloc(size_t size)
326 {
327 void* result;
328
329 // Freed allocations of the common size are not stored back into the main
330 // m_freeList, but are instead stored in a separate vector. If the request
331 // is for a common sized allocation, check this list.
332 if ((size == m_commonSize) && m_commonSizedAllocations.size()) {
333 result = m_commonSizedAllocations.last();
334 m_commonSizedAllocations.removeLast();
335 } else {
336 // Serach m_freeList for a suitable sized chunk to allocate memory from.
337 FreeListEntry* entry = m_freeList.search(k: size, st: m_freeList.GREATER_EQUAL);
338
339 // This would be bad news.
340 if (!entry) {
341 // Errk! Lets take a last-ditch desparation attempt at defragmentation...
342 coalesceFreeSpace();
343 // Did that free up a large enough chunk?
344 entry = m_freeList.search(k: size, st: m_freeList.GREATER_EQUAL);
345 // No?... *BOOM!*
346 if (!entry)
347 CRASH();
348 }
349 ASSERT(entry->size != m_commonSize);
350
351 // Remove the entry from m_freeList. But! -
352 // Each entry in the tree may represent a chain of multiple chunks of the
353 // same size, and we only want to remove one on them. So, if this entry
354 // does have a chain, just remove the first-but-one item from the chain.
355 if (FreeListEntry* next = entry->nextEntry) {
356 // We're going to leave 'entry' in the tree; remove 'next' from its chain.
357 entry->nextEntry = next->nextEntry;
358 next->nextEntry = 0;
359 entry = next;
360 } else
361 m_freeList.remove(k: entry->size);
362
363 // Whoo!, we have a result!
364 ASSERT(entry->size >= size);
365 result = entry->pointer;
366
367 // If the allocation exactly fits the chunk we found in the,
368 // m_freeList then the FreeListEntry node is no longer needed.
369 if (entry->size == size)
370 delete entry;
371 else {
372 // There is memory left over, and it is not of the common size.
373 // We can reuse the existing FreeListEntry node to add this back
374 // into m_freeList.
375 entry->pointer = (void*)((intptr_t)entry->pointer + size);
376 entry->size -= size;
377 addToFreeList(entry);
378 }
379 }
380
381 // Call reuse to report to the operating system that this memory is in use.
382 ASSERT(isWithinVMPool(result, size));
383 reuse(result, size);
384 return result;
385 }
386
387 void free(void* pointer, size_t size)
388 {
389 // Call release to report to the operating system that this
390 // memory is no longer in use, and need not be paged out.
391 ASSERT(isWithinVMPool(pointer, size));
392 release(pointer, size);
393
394 // Common-sized allocations are stored in the m_commonSizedAllocations
395 // vector; all other freed chunks are added to m_freeList.
396 if (size == m_commonSize)
397 m_commonSizedAllocations.append(val: pointer);
398 else
399 addToFreeList(entry: new FreeListEntry(pointer, size));
400
401 // Do some housekeeping. Every time we reach a point that
402 // 16MB of allocations have been freed, sweep m_freeList
403 // coalescing any neighboring fragments.
404 m_countFreedSinceLastCoalesce += size;
405 if (m_countFreedSinceLastCoalesce >= COALESCE_LIMIT) {
406 m_countFreedSinceLastCoalesce = 0;
407 coalesceFreeSpace();
408 }
409 }
410
411private:
412
413#ifndef NDEBUG
414 bool isWithinVMPool(void* pointer, size_t size)
415 {
416 return pointer >= m_base && (reinterpret_cast<char*>(pointer) + size <= reinterpret_cast<char*>(m_base) + m_totalHeapSize);
417 }
418#endif
419
420 // Freed space from the most common sized allocations will be held in this list, ...
421 const size_t m_commonSize;
422 Vector<void*> m_commonSizedAllocations;
423
424 // ... and all other freed allocations are held in m_freeList.
425 SizeSortedFreeTree m_freeList;
426
427 // This is used for housekeeping, to trigger defragmentation of the freed lists.
428 size_t m_countFreedSinceLastCoalesce;
429
430 void* m_base;
431 size_t m_totalHeapSize;
432};
433
434void ExecutableAllocator::intializePageSize()
435{
436 ExecutableAllocator::pageSize = getpagesize();
437}
438
439static FixedVMPoolAllocator* allocator = 0;
440static SpinLock spinlock = SPINLOCK_INITIALIZER;
441
442ExecutablePool::Allocation ExecutablePool::systemAlloc(size_t size)
443{
444 SpinLockHolder lock_holder(&spinlock);
445
446 if (!allocator)
447 allocator = new FixedVMPoolAllocator(JIT_ALLOCATOR_LARGE_ALLOC_SIZE, VM_POOL_SIZE);
448 ExecutablePool::Allocation alloc = {.pages: reinterpret_cast<char*>(allocator->alloc(size)), .size: size};
449 return alloc;
450}
451
452void ExecutablePool::systemRelease(const ExecutablePool::Allocation& allocation)
453{
454 SpinLockHolder lock_holder(&spinlock);
455
456 ASSERT(allocator);
457 allocator->free(pointer: allocation.pages, size: allocation.size);
458}
459
460}
461
462#endif // HAVE(ASSEMBLER)
463

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/jit/ExecutableAllocatorFixedVMPool.cpp