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 | |
57 | using namespace WTF; |
58 | |
59 | namespace JSC { |
60 | |
61 | // FreeListEntry describes a free chunk of memory, stored in the freeList. |
62 | struct 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. |
89 | struct 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. |
109 | static 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. |
118 | static 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 | |
126 | class 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 | |
290 | public: |
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 | |
411 | private: |
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 | |
434 | void ExecutableAllocator::intializePageSize() |
435 | { |
436 | ExecutableAllocator::pageSize = getpagesize(); |
437 | } |
438 | |
439 | static FixedVMPoolAllocator* allocator = 0; |
440 | static SpinLock spinlock = SPINLOCK_INITIALIZER; |
441 | |
442 | ExecutablePool::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 | |
452 | void 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 | |