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