| /* |
| * Copyright (c) 2018-2019 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 "TestHarness.h" |
| #include <functional> |
| #include <memory> |
| #include "pas_bootstrap_free_heap.h" |
| #include "pas_fast_large_free_heap.h" |
| #include "pas_heap_lock.h" |
| #include "pas_large_free.h" |
| #include "pas_large_free_heap_config.h" |
| #include "pas_page_malloc.h" |
| #include "pas_simple_large_free_heap.h" |
| #include <set> |
| #include <vector> |
| |
| using namespace std; |
| |
| namespace { |
| |
| pas_alignment alignSimple(size_t size) |
| { |
| return pas_alignment_create_traditional(size); |
| } |
| |
| pas_aligned_allocation_result trappingAllocator(size_t size, pas_alignment alignment) |
| { |
| CHECK(!"Should not have called allocator"); |
| return pas_aligned_allocation_result_create_empty(); |
| } |
| |
| void trappingDeallocator(void* base, size_t size) |
| { |
| CHECK(!"Should not have called deallocator"); |
| } |
| |
| pas_aligned_allocation_result failingAllocator(size_t size, pas_alignment alignment) |
| { |
| return pas_aligned_allocation_result_create_empty(); |
| } |
| |
| struct Action { |
| enum Kind { |
| Allocate, |
| Deallocate |
| }; |
| |
| Action() = default; |
| |
| static Action allocate( |
| size_t size, pas_alignment alignment, uintptr_t expectedResult, |
| function<pas_aligned_allocation_result(size_t size, pas_alignment alignment)> allocator = trappingAllocator, |
| function<void(void* base, size_t size)> deallocator = trappingDeallocator) |
| { |
| Action result; |
| result.kind = Allocate; |
| result.size = size; |
| result.alignment = alignment; |
| result.allocator = allocator; |
| result.deallocator = deallocator; |
| result.result = expectedResult; |
| return result; |
| } |
| |
| static Action deallocate( |
| uintptr_t base, size_t size, |
| function<pas_aligned_allocation_result(size_t size, pas_alignment alignment)> allocator = trappingAllocator, |
| function<void(void* base, size_t size)> deallocator = trappingDeallocator) |
| { |
| Action result; |
| result.kind = Deallocate; |
| result.base = base; |
| result.size = size; |
| result.allocator = allocator; |
| result.deallocator = deallocator; |
| return result; |
| } |
| |
| Kind kind { Allocate }; |
| uintptr_t base { 0 }; |
| size_t size { 0 }; |
| pas_alignment alignment { 0 }; |
| function<pas_aligned_allocation_result(size_t size, pas_alignment alignment)> allocator; |
| function<void(void* base, size_t size)> deallocator; |
| uintptr_t result { 0 }; |
| }; |
| |
| struct Free { |
| Free() = default; |
| |
| Free(uintptr_t begin, uintptr_t end) |
| : begin(begin) |
| , end(end) |
| { |
| } |
| |
| bool operator==(const Free& other) const |
| { |
| return begin == other.begin |
| && end == other.end; |
| } |
| |
| bool operator<(const Free& other) const |
| { |
| if (begin != other.begin) |
| return begin < other.begin; |
| return end < other.end; |
| } |
| |
| uintptr_t begin; |
| uintptr_t end; |
| }; |
| |
| struct Allocation { |
| Allocation() = default; |
| |
| Allocation(size_t expectedSize, pas_alignment expectedAlignment, |
| uintptr_t leftPadding, uintptr_t resultBase, |
| uintptr_t rightPadding, uintptr_t end) |
| : expectedSize(expectedSize) |
| , expectedAlignment(expectedAlignment) |
| , leftPadding(leftPadding) |
| , resultBase(resultBase) |
| , rightPadding(rightPadding) |
| , end(end) |
| { |
| } |
| |
| size_t expectedSize { 0 }; |
| pas_alignment expectedAlignment { 0 }; |
| uintptr_t leftPadding { 0 }; |
| uintptr_t resultBase { 0 }; |
| uintptr_t rightPadding { 0 }; |
| uintptr_t end { 0 }; |
| }; |
| |
| function<pas_aligned_allocation_result(size_t size, pas_alignment alignment)> |
| allocateFinite(vector<Allocation> allocations) |
| { |
| shared_ptr<size_t> allocationCursor = make_shared<size_t>(0); |
| return [=] (size_t size, pas_alignment alignment) -> pas_aligned_allocation_result { |
| CHECK_LESS(*allocationCursor, allocations.size()); |
| |
| Allocation allocation = allocations[(*allocationCursor)++]; |
| |
| CHECK_EQUAL(size, allocation.expectedSize); |
| CHECK_ALIGNMENT_EQUAL(alignment, allocation.expectedAlignment); |
| |
| pas_aligned_allocation_result result; |
| result.left_padding = (void*)allocation.leftPadding; |
| result.left_padding_size = allocation.resultBase - allocation.leftPadding; |
| result.result = (void*)allocation.resultBase; |
| result.result_size = allocation.rightPadding - allocation.resultBase; |
| result.right_padding = (void*)allocation.rightPadding; |
| result.right_padding_size = allocation.end - allocation.rightPadding; |
| result.zero_mode = pas_zero_mode_may_have_non_zero; |
| |
| return result; |
| }; |
| } |
| |
| function<pas_aligned_allocation_result(size_t size, pas_alignment alignment)> |
| allocateOnce(size_t expectedSize, |
| pas_alignment expectedAlignment, |
| uintptr_t leftPadding, |
| uintptr_t resultBase, |
| uintptr_t rightPadding, |
| uintptr_t end) |
| { |
| return allocateFinite({ Allocation(expectedSize, expectedAlignment, |
| leftPadding, resultBase, |
| rightPadding, end) }); |
| } |
| |
| function<void(void* base, size_t size)> deallocateFinite(vector<Free> frees) |
| { |
| shared_ptr<size_t> freeCursor = make_shared<size_t>(0); |
| return [=] (void* base, size_t size) { |
| CHECK_LESS(*freeCursor, frees.size()); |
| CHECK_EQUAL(reinterpret_cast<uintptr_t>(base), frees[*freeCursor].begin); |
| CHECK_EQUAL(reinterpret_cast<uintptr_t>(base) + size, frees[*freeCursor].end); |
| (*freeCursor)++; |
| }; |
| } |
| |
| ostream& operator<<(ostream& out, const Free& free) |
| { |
| out << "{begin = " << free.begin << ", end = " << free.end |
| << ", size = " << (free.end - free.begin) << "}"; |
| return out; |
| } |
| |
| pas_aligned_allocation_result allocatorAdapter(size_t size, pas_alignment alignment, void* arg) |
| { |
| const function<pas_aligned_allocation_result(size_t size, pas_alignment alignment)>* allocator = |
| reinterpret_cast<const function<pas_aligned_allocation_result(size_t size, pas_alignment alignment)>*>(arg); |
| return (*allocator)(size, alignment); |
| } |
| |
| void deallocatorAdapter(void* base, size_t size, void* arg) |
| { |
| const function<void(void* base, size_t size)>* deallocator = |
| reinterpret_cast<const function<void(void* base, size_t size)>*>(arg); |
| (*deallocator)(base, size); |
| } |
| |
| bool iterateAdapter(pas_large_free free, |
| void* arg) |
| { |
| std::function<bool(pas_large_free)>* capturedFunc = |
| static_cast<std::function<bool(pas_large_free)>*>(arg); |
| return (*capturedFunc)(free); |
| } |
| |
| template<typename HeapType, |
| typename IterateFunc, |
| typename Func> |
| void iterateHeap(HeapType* heap, |
| const IterateFunc& iterateFunc, |
| const Func& func) |
| { |
| std::function<bool(pas_large_free)> capturedFunc = func; |
| iterateFunc(heap, iterateAdapter, &capturedFunc); |
| } |
| |
| template<typename HeapType, |
| typename AllocateFunc, |
| typename DeallocateFunc, |
| typename IterateFunc> |
| void testLargeFreeHeapImpl(HeapType* heap, |
| const vector<Action>& actions, |
| const set<Free>& frees, |
| size_t typeSize, |
| const AllocateFunc& allocateFunc, |
| const DeallocateFunc& deallocateFunc, |
| const IterateFunc& iterateFunc) |
| { |
| for (const Action& action : actions) { |
| pas_large_free_heap_config config; |
| |
| memset(&config, 0, sizeof(config)); |
| |
| config.type_size = typeSize; |
| config.min_alignment = 1; |
| CHECK(!!action.allocator); |
| config.aligned_allocator = allocatorAdapter; |
| config.aligned_allocator_arg = const_cast<void*>(reinterpret_cast<const void*>(&action.allocator)); |
| if (action.deallocator) { |
| config.deallocator = deallocatorAdapter; |
| config.deallocator_arg = const_cast<void*>(reinterpret_cast<const void*>(&action.deallocator)); |
| } else { |
| config.deallocator = nullptr; |
| config.deallocator_arg = nullptr; |
| } |
| |
| pas_heap_lock_lock(); |
| |
| switch (action.kind) { |
| case Action::Allocate: { |
| pas_string_stream stream; |
| stringStreamConstruct(&stream); |
| pas_alignment_dump(action.alignment, reinterpret_cast<pas_stream*>(&stream)); |
| cout << " Allocating size = " << action.size |
| << ", alignment = " << pas_string_stream_get_string(&stream) << endl; |
| pas_string_stream_destruct(&stream); |
| CHECK_EQUAL(allocateFunc(heap, action.size, action.alignment, &config).begin, |
| action.result); |
| break; |
| } |
| case Action::Deallocate: |
| cout << " Freeing base = " << action.base << endl; |
| deallocateFunc(heap, action.base, action.base + action.size, |
| pas_zero_mode_may_have_non_zero, |
| &config); |
| break; |
| } |
| |
| pas_heap_lock_unlock(); |
| } |
| |
| bool ok = true; |
| set<Free> freesFound; |
| iterateHeap( |
| heap, |
| iterateFunc, |
| [&] (pas_large_free largeFree) { |
| Free free(largeFree.begin, largeFree.end); |
| if (freesFound.count(free)) { |
| cout << " FAIL: Found duplicate entry " << free << endl; |
| ok = false; |
| } |
| freesFound.insert(free); |
| return true; |
| }); |
| |
| if (freesFound != frees || !ok) { |
| cout << " FAIL: Free validation failed." << endl; |
| |
| auto dumpFree = [] (const set<Free>& frees) { |
| bool first = true; |
| for (const Free& free : frees) { |
| if (first) |
| first = false; |
| else |
| cout << ", "; |
| cout << free; |
| } |
| }; |
| |
| cout << " Expected: "; |
| dumpFree(frees); |
| cout << endl; |
| cout << " Actual: "; |
| dumpFree(freesFound); |
| cout << endl; |
| CHECK(!"Free validation failed."); |
| } |
| } |
| |
| void testSimpleLargeFreeHeap(const vector<Action>& actions, |
| const set<Free>& frees, |
| size_t typeSize) |
| { |
| pas_simple_large_free_heap heap; |
| pas_simple_large_free_heap_construct(&heap); |
| testLargeFreeHeapImpl( |
| &heap, actions, frees, typeSize, |
| pas_simple_large_free_heap_try_allocate, |
| pas_simple_large_free_heap_deallocate, |
| pas_simple_large_free_heap_for_each_free); |
| } |
| |
| void testFastLargeFreeHeap(const vector<Action>& actions, |
| const set<Free>& frees, |
| size_t typeSize) |
| { |
| pas_fast_large_free_heap heap; |
| pas_fast_large_free_heap_construct(&heap); |
| testLargeFreeHeapImpl( |
| &heap, actions, frees, typeSize, |
| pas_fast_large_free_heap_try_allocate, |
| pas_fast_large_free_heap_deallocate, |
| pas_fast_large_free_heap_for_each_free); |
| } |
| |
| void testBootstrapHeap(const vector<Action>& actions, |
| const set<Free>& frees, |
| size_t typeSize) |
| { |
| static constexpr size_t slabSize = 1lu << 20; |
| void* slabPtr = pas_page_malloc_try_allocate_without_deallocating_padding( |
| slabSize, alignSimple(slabSize)).result; |
| CHECK(slabPtr); |
| uintptr_t slab = reinterpret_cast<uintptr_t>(slabPtr); |
| |
| cout << " Slab at " << slab << endl; |
| |
| vector<Action> newActions; |
| set<Free> newFrees; |
| |
| for (const Action& action : actions) { |
| Action newAction = action; |
| |
| if (newAction.base) |
| newAction.base += slab; |
| |
| newAction.allocator = [=] (size_t size, pas_alignment alignment) -> pas_aligned_allocation_result { |
| pas_aligned_allocation_result result = action.allocator(size, alignment); |
| if (!result.result) |
| return result; |
| result.result = reinterpret_cast<void*>( |
| reinterpret_cast<uintptr_t>(result.result) + slab); |
| result.left_padding = reinterpret_cast<void*>( |
| reinterpret_cast<uintptr_t>(result.left_padding) + slab); |
| result.right_padding = reinterpret_cast<void*>( |
| reinterpret_cast<uintptr_t>(result.right_padding) + slab); |
| return result; |
| }; |
| |
| if (action.deallocator) { |
| newAction.deallocator = [=] (void* base, size_t size) { |
| action.deallocator(reinterpret_cast<void*>( |
| reinterpret_cast<uintptr_t>(base) - slab), |
| size); |
| }; |
| } |
| |
| if (newAction.result) |
| newAction.result += slab; |
| |
| newActions.push_back(newAction); |
| } |
| |
| for (const Free& free : frees) |
| newFrees.insert(Free(free.begin + slab, free.end + slab)); |
| |
| testLargeFreeHeapImpl( |
| &pas_bootstrap_free_heap, newActions, newFrees, typeSize, |
| pas_simple_large_free_heap_try_allocate, |
| pas_simple_large_free_heap_deallocate, |
| pas_simple_large_free_heap_for_each_free); |
| } |
| |
| size_t freeListSize(size_t size) |
| { |
| return PAS_MAX(size, PAS_BOOTSTRAP_FREE_LIST_MINIMUM_SIZE) * sizeof(pas_large_free); |
| } |
| |
| } // anonymous namespace |
| |
| void addLargeFreeHeapTests() |
| { |
| ADD_TEST(testSimpleLargeFreeHeap({ }, { }, 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(666, alignSimple(4), 0, failingAllocator, { }) |
| }, |
| { |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::deallocate(4200, 3500), |
| Action::allocate(100, alignSimple(16), 4208), |
| Action::allocate(1000, alignSimple(4), 4308), |
| Action::allocate(2000, alignSimple(8), 5312), |
| }, |
| { |
| Free(4200, 4208), |
| Free(5308, 5312), |
| Free(7312, 7700) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 7700), |
| { }), |
| Action::allocate(1000, alignSimple(4), 4308), |
| Action::allocate(2000, alignSimple(8), 5312), |
| }, |
| { |
| Free(4200, 4208), |
| Free(5308, 5312), |
| Free(7312, 7700) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 7700), |
| deallocateFinite({ |
| Free(4200, 4208), |
| Free(4308, 7700) |
| })) |
| }, |
| { }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 7700), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 7700) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4500), |
| { }), |
| Action::allocate(1000, alignSimple(4), 4308, |
| allocateOnce(1000, alignSimple(4), |
| 4500, 4500, |
| 5500, 7700), |
| { }), |
| Action::allocate(2000, alignSimple(8), 5312), |
| }, |
| { |
| Free(4200, 4208), |
| Free(5308, 5312), |
| Free(7312, 7700) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4500), |
| { }), |
| Action::deallocate(7500, 200), |
| Action::allocate(1000, alignSimple(4), 4308, |
| allocateOnce(1000, alignSimple(4), |
| 4500, 4500, |
| 5500, 7500), |
| { }), |
| Action::allocate(2000, alignSimple(8), 5312), |
| }, |
| { |
| Free(4200, 4208), |
| Free(5308, 5312), |
| Free(7312, 7700) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4500), |
| { }), |
| Action::allocate(100, alignSimple(128), 4352) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4352), |
| Free(4452, 4500) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4208, 4208, |
| 4308, 4500), |
| { }), |
| Action::allocate(100, alignSimple(128), 4352) |
| }, |
| { |
| Free(4308, 4352), |
| Free(4452, 4500) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(128), 4352, |
| allocateOnce(100, alignSimple(128), |
| 4400, 4480, |
| 4580, 4608), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4352), |
| Free(4452, 4608) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(512), 4608, |
| allocateOnce(100, alignSimple(512), |
| 4400, 4608, |
| 4708, 5120), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4608), |
| Free(4708, 5120) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(4), 4308, |
| allocateOnce(100, alignSimple(4), |
| 4400, 4400, |
| 4500, 4600), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4408, 4600) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(512), 4608, |
| allocateOnce(100, alignSimple(512), |
| 4400, 4608, |
| 4708, 4708), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4608) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(512), 4608, |
| allocateOnce(100, alignSimple(512), |
| 4608, 4608, |
| 4708, 5120), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4400), |
| Free(4708, 5120) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(512), 4608, |
| allocateOnce(100, alignSimple(512), |
| 4608, 4608, |
| 4708, 4708), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4400) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(128), 4352, |
| allocateOnce(100, alignSimple(128), |
| 4400, 4480, |
| 4580, 4608), |
| deallocateFinite({ |
| Free(4452, 4608) |
| })) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4352) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(512), 4608, |
| allocateOnce(100, alignSimple(512), |
| 4400, 4608, |
| 4708, 5120), |
| deallocateFinite({ |
| Free(4400, 4608), |
| Free(4708, 5120) |
| })) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4400) |
| }, |
| 1)); |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(4), 4308, |
| allocateOnce(100, alignSimple(4), |
| 4400, 4400, |
| 4500, 4600), |
| deallocateFinite({ |
| Free(4408, 4600) |
| })) |
| }, |
| { |
| Free(4200, 4208) |
| }, |
| 1)); |
| |
| ADD_TEST(testFastLargeFreeHeap({ }, { }, 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(666, alignSimple(4), 0, failingAllocator, { }) |
| }, |
| { |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::deallocate(4200, 3500), |
| Action::allocate(100, alignSimple(16), 4208), |
| Action::allocate(1000, alignSimple(4), 4308), |
| Action::allocate(2000, alignSimple(8), 5312), |
| }, |
| { |
| Free(4200, 4208), |
| Free(5308, 5312), |
| Free(7312, 7700) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 7700), |
| { }), |
| Action::allocate(1000, alignSimple(4), 4308), |
| Action::allocate(2000, alignSimple(8), 5312), |
| }, |
| { |
| Free(4200, 4208), |
| Free(5308, 5312), |
| Free(7312, 7700) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 7700), |
| deallocateFinite({ |
| Free(4200, 4208), |
| Free(4308, 7700) |
| })) |
| }, |
| { }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 7700), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 7700) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4500), |
| { }), |
| Action::allocate(1000, alignSimple(4), 4308, |
| allocateOnce(1000, alignSimple(4), |
| 4500, 4500, |
| 5500, 7700), |
| { }), |
| Action::allocate(2000, alignSimple(8), 5312), |
| }, |
| { |
| Free(4200, 4208), |
| Free(5308, 5312), |
| Free(7312, 7700) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4500), |
| { }), |
| Action::deallocate(7500, 200), |
| Action::allocate(1000, alignSimple(4), 4308, |
| allocateOnce(1000, alignSimple(4), |
| 4500, 4500, |
| 5500, 7500), |
| { }), |
| Action::allocate(2000, alignSimple(8), 5312), |
| }, |
| { |
| Free(4200, 4208), |
| Free(5308, 5312), |
| Free(7312, 7700) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4500), |
| { }), |
| Action::allocate(100, alignSimple(128), 4352) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4352), |
| Free(4452, 4500) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4208, 4208, |
| 4308, 4500), |
| { }), |
| Action::allocate(100, alignSimple(128), 4352) |
| }, |
| { |
| Free(4308, 4352), |
| Free(4452, 4500) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(128), 4352, |
| allocateOnce(100, alignSimple(128), |
| 4400, 4480, |
| 4580, 4608), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4352), |
| Free(4452, 4608) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(512), 4608, |
| allocateOnce(100, alignSimple(512), |
| 4400, 4608, |
| 4708, 5120), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4608), |
| Free(4708, 5120) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(4), 4308, |
| allocateOnce(100, alignSimple(4), |
| 4400, 4400, |
| 4500, 4600), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4408, 4600) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(512), 4608, |
| allocateOnce(100, alignSimple(512), |
| 4400, 4608, |
| 4708, 4708), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4608) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(512), 4608, |
| allocateOnce(100, alignSimple(512), |
| 4608, 4608, |
| 4708, 5120), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4400), |
| Free(4708, 5120) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(512), 4608, |
| allocateOnce(100, alignSimple(512), |
| 4608, 4608, |
| 4708, 4708), |
| { }) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4400) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(128), 4352, |
| allocateOnce(100, alignSimple(128), |
| 4400, 4480, |
| 4580, 4608), |
| deallocateFinite({ |
| Free(4452, 4608) |
| })) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4352) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(512), 4608, |
| allocateOnce(100, alignSimple(512), |
| 4400, 4608, |
| 4708, 5120), |
| deallocateFinite({ |
| Free(4400, 4608), |
| Free(4708, 5120) |
| })) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4400) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 4400), |
| { }), |
| Action::allocate(100, alignSimple(4), 4308, |
| allocateOnce(100, alignSimple(4), |
| 4400, 4400, |
| 4500, 4600), |
| deallocateFinite({ |
| Free(4408, 4600) |
| })) |
| }, |
| { |
| Free(4200, 4208) |
| }, |
| 1)); |
| |
| ADD_TEST(testSimpleLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 5328), |
| { }), |
| Action::allocate(100, alignSimple(16), 4320), |
| Action::allocate(100, alignSimple(16), 4432), |
| Action::allocate(100, alignSimple(16), 4544), |
| Action::allocate(100, alignSimple(16), 4656), |
| Action::allocate(100, alignSimple(16), 4768), |
| Action::allocate(100, alignSimple(16), 4880), |
| Action::allocate(100, alignSimple(16), 4992), |
| Action::allocate(100, alignSimple(16), 5104), |
| Action::allocate(100, alignSimple(16), 5216), |
| Action::deallocate(4320, 100), |
| Action::deallocate(4544, 100), |
| Action::deallocate(4768, 100), |
| Action::deallocate(4992, 100), |
| Action::deallocate(5216, 100), |
| Action::allocate(100, alignSimple(16), 4320), |
| Action::deallocate(5104, 100) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4320), |
| Free(4420, 4432), |
| Free(4532, 4656), |
| Free(4756, 4880), |
| Free(4980, 5328) |
| }, |
| 1)); |
| ADD_TEST(testFastLargeFreeHeap( |
| { |
| Action::allocate(100, alignSimple(16), 4208, |
| allocateOnce(100, alignSimple(16), |
| 4200, 4208, |
| 4308, 5328), |
| { }), |
| Action::allocate(100, alignSimple(16), 4320), |
| Action::allocate(100, alignSimple(16), 4432), |
| Action::allocate(100, alignSimple(16), 4544), |
| Action::allocate(100, alignSimple(16), 4656), |
| Action::allocate(100, alignSimple(16), 4768), |
| Action::allocate(100, alignSimple(16), 4880), |
| Action::allocate(100, alignSimple(16), 4992), |
| Action::allocate(100, alignSimple(16), 5104), |
| Action::allocate(100, alignSimple(16), 5216), |
| Action::deallocate(4320, 100), |
| Action::deallocate(4544, 100), |
| Action::deallocate(4768, 100), |
| Action::deallocate(4992, 100), |
| Action::deallocate(5216, 100), |
| Action::allocate(100, alignSimple(16), 4320), |
| Action::deallocate(5104, 100) |
| }, |
| { |
| Free(4200, 4208), |
| Free(4308, 4320), |
| Free(4420, 4432), |
| Free(4532, 4656), |
| Free(4756, 4880), |
| Free(4980, 5328) |
| }, |
| 1)); |
| |
| ADD_TEST(testBootstrapHeap({ }, { }, 1)); |
| ADD_TEST(testBootstrapHeap( |
| { |
| Action::allocate(666, alignSimple(4), 0, failingAllocator, { }) |
| }, |
| { |
| }, |
| 1)); |
| ADD_TEST(testBootstrapHeap( |
| { |
| Action::deallocate(4200, 3500), |
| Action::allocate(104, alignSimple(8), freeListSize(1) + 4200), |
| Action::allocate(1000, alignSimple(8), freeListSize(1) + 4304), |
| Action::allocate(2000, alignSimple(8), freeListSize(1) + 5304), |
| }, |
| { |
| Free(freeListSize(1) + 7304, 7700) |
| }, |
| 1)); |
| ADD_TEST(testBootstrapHeap( |
| { |
| Action::allocate(104, alignSimple(8), 4200, |
| allocateOnce(104, alignSimple(8), |
| 4200, 4200, |
| 4304, 5000), |
| { }), |
| }, |
| { |
| Free(4304 + freeListSize(1), 5000) |
| }, |
| 1)); |
| ADD_TEST(testBootstrapHeap( |
| { |
| Action::allocate(104, alignSimple(8), 4200, |
| allocateOnce(104, alignSimple(8), |
| 4200, 4200, |
| 4304, 4304), |
| { }), |
| }, |
| { }, |
| 1)); |
| ADD_TEST(testBootstrapHeap( |
| { |
| Action::allocate(104, alignSimple(8), 4200, |
| allocateFinite( |
| { |
| Allocation(104, alignSimple(8), |
| 4200, 4200, |
| 4304, 4312), |
| Allocation(freeListSize(1), alignSimple(sizeof(void*)), |
| 4312, 4312, |
| 4312 + freeListSize(1), |
| 4312 + freeListSize(1)) |
| }), |
| { }), |
| }, |
| { |
| Free(4304 + freeListSize(1), 4312 + freeListSize(1)) |
| }, |
| 1)); |
| ADD_TEST(testBootstrapHeap( |
| { |
| Action::deallocate(4200, 800), |
| Action::deallocate(5200, 800), |
| Action::deallocate(6200, 800), |
| Action::deallocate(7200, 800), |
| Action::deallocate(8200, 800), |
| Action::deallocate(9200, 2000), |
| Action::deallocate(12200, 800), |
| Action::deallocate(13200, 800), |
| Action::deallocate(14200, 800), |
| Action::deallocate(15200, 800) |
| }, |
| { |
| Free(4200, 5000), |
| Free(5200 + freeListSize(22), 6000), |
| Free(6200, 7000), |
| Free(7200, 8000), |
| Free(8200, 9000), |
| Free(9200, 11200), |
| Free(12200, 13000), |
| Free(13200, 14000), |
| Free(14200, 15000), |
| Free(15200, 16000) |
| }, |
| 1)); |
| } |
| |
