General purpose memory allocator for linker.
Add basic general purpose memory allocator to
linker in order to enable usage of other libraries
like libziparchive.
Change-Id: I4a680ebb36ed5ba67c61249f81dba9f567808434
diff --git a/linker/Android.mk b/linker/Android.mk
index 0ab0fda..f78a025 100644
--- a/linker/Android.mk
+++ b/linker/Android.mk
@@ -6,9 +6,11 @@
debugger.cpp \
dlfcn.cpp \
linker.cpp \
+ linker_allocator.cpp \
linker_block_allocator.cpp \
linker_environ.cpp \
linker_libc_support.c \
+ linker_memory.cpp \
linker_phdr.cpp \
rt.cpp \
diff --git a/linker/linker.cpp b/linker/linker.cpp
index ea7d637..18f8cdc 100644
--- a/linker/linker.cpp
+++ b/linker/linker.cpp
@@ -147,18 +147,6 @@
uint32_t bitmask[4096];
#endif
-// You shouldn't try to call memory-allocating functions in the dynamic linker.
-// Guard against the most obvious ones.
-#define DISALLOW_ALLOCATION(return_type, name, ...) \
- return_type name __VA_ARGS__ \
- { \
- __libc_fatal("ERROR: " #name " called from the dynamic linker!\n"); \
- }
-DISALLOW_ALLOCATION(void*, malloc, (size_t u __unused));
-DISALLOW_ALLOCATION(void, free, (void* u __unused));
-DISALLOW_ALLOCATION(void*, realloc, (void* u1 __unused, size_t u2 __unused));
-DISALLOW_ALLOCATION(void*, calloc, (size_t u1 __unused, size_t u2 __unused));
-
static char __linker_dl_err_buf[768];
char* linker_get_error_buffer() {
diff --git a/linker/linker_allocator.cpp b/linker/linker_allocator.cpp
new file mode 100644
index 0000000..1b16cf1
--- /dev/null
+++ b/linker/linker_allocator.cpp
@@ -0,0 +1,346 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "linker_allocator.h"
+#include "linker.h"
+
+#include <algorithm>
+#include <vector>
+
+#include <stdlib.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+#include "private/bionic_prctl.h"
+
+//
+// LinkerMemeoryAllocator is general purpose allocator
+// designed to provide the same functionality as the malloc/free/realloc
+// libc functions.
+//
+// On alloc:
+// If size is >= 1k allocator proxies malloc call directly to mmap
+// If size < 1k allocator uses SmallObjectAllocator for the size
+// rounded up to the nearest power of two.
+//
+// On free:
+//
+// For a pointer allocated using proxy-to-mmap allocator unmaps
+// the memory.
+//
+// For a pointer allocated using SmallObjectAllocator it adds
+// the block to free_blocks_list_. If the number of free pages reaches 2,
+// SmallObjectAllocator munmaps one of the pages keeping the other one
+// in reserve.
+
+static const char kSignature[4] = {'L', 'M', 'A', 1};
+
+static const size_t kSmallObjectMaxSize = 1 << kSmallObjectMaxSizeLog2;
+
+// This type is used for large allocations (with size >1k)
+static const uint32_t kLargeObject = 111;
+
+bool operator<(const small_object_page_record& one, const small_object_page_record& two) {
+ return one.page_addr < two.page_addr;
+}
+
+static inline uint16_t log2(size_t number) {
+ uint16_t result = 0;
+ number--;
+
+ while (number != 0) {
+ result++;
+ number >>= 1;
+ }
+
+ return result;
+}
+
+LinkerSmallObjectAllocator::LinkerSmallObjectAllocator()
+ : type_(0), name_(nullptr), block_size_(0), free_pages_cnt_(0), free_blocks_list_(nullptr) {}
+
+void* LinkerSmallObjectAllocator::alloc() {
+ if (free_blocks_list_ == nullptr) {
+ alloc_page();
+ }
+
+ small_object_block_record* block_record = free_blocks_list_;
+ if (block_record->free_blocks_cnt > 1) {
+ small_object_block_record* next_free = reinterpret_cast<small_object_block_record*>(
+ reinterpret_cast<uint8_t*>(block_record) + block_size_);
+ next_free->next = block_record->next;
+ next_free->free_blocks_cnt = block_record->free_blocks_cnt - 1;
+ free_blocks_list_ = next_free;
+ } else {
+ free_blocks_list_ = block_record->next;
+ }
+
+ // bookkeeping...
+ auto page_record = find_page_record(block_record);
+
+ if (page_record->allocated_blocks_cnt == 0) {
+ free_pages_cnt_--;
+ }
+
+ page_record->free_blocks_cnt--;
+ page_record->allocated_blocks_cnt++;
+
+ memset(block_record, 0, block_size_);
+
+ return block_record;
+}
+
+void LinkerSmallObjectAllocator::free_page(linker_vector_t::iterator page_record) {
+ void* page_start = reinterpret_cast<void*>(page_record->page_addr);
+ void* page_end = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(page_start) + PAGE_SIZE);
+
+ while (free_blocks_list_ != nullptr &&
+ free_blocks_list_ > page_start &&
+ free_blocks_list_ < page_end) {
+ free_blocks_list_ = free_blocks_list_->next;
+ }
+
+ small_object_block_record* current = free_blocks_list_;
+
+ while (current != nullptr) {
+ while (current->next > page_start && current->next < page_end) {
+ current->next = current->next->next;
+ }
+
+ current = current->next;
+ }
+
+ munmap(page_start, PAGE_SIZE);
+ page_records_.erase(page_record);
+ free_pages_cnt_--;
+}
+
+void LinkerSmallObjectAllocator::free(void* ptr) {
+ auto page_record = find_page_record(ptr);
+
+ ssize_t offset = reinterpret_cast<uintptr_t>(ptr) - sizeof(page_info);
+
+ if (offset % block_size_ != 0) {
+ __libc_fatal("invalid pointer: %p (block_size=%zd)", ptr, block_size_);
+ }
+
+ memset(ptr, 0, block_size_);
+ small_object_block_record* block_record = reinterpret_cast<small_object_block_record*>(ptr);
+
+ block_record->next = free_blocks_list_;
+ block_record->free_blocks_cnt = 1;
+
+ free_blocks_list_ = block_record;
+
+ page_record->free_blocks_cnt++;
+ page_record->allocated_blocks_cnt--;
+
+ if (page_record->allocated_blocks_cnt == 0) {
+ if (free_pages_cnt_++ > 1) {
+ // if we already have a free page - unmap this one.
+ free_page(page_record);
+ }
+ }
+}
+
+void LinkerSmallObjectAllocator::init(uint32_t type, size_t block_size, const char* name) {
+ type_ = type;
+ block_size_ = block_size;
+ name_ = name;
+}
+
+linker_vector_t::iterator LinkerSmallObjectAllocator::find_page_record(void* ptr) {
+ void* addr = reinterpret_cast<void*>(PAGE_START(reinterpret_cast<uintptr_t>(ptr)));
+ small_object_page_record boundary;
+ boundary.page_addr = addr;
+ linker_vector_t::iterator it = std::lower_bound(
+ page_records_.begin(), page_records_.end(), boundary);
+
+ if (it == page_records_.end() || it->page_addr != addr) {
+ // not found...
+ __libc_fatal("page record for %p was not found (block_size=%zd)", ptr, block_size_);
+ }
+
+ return it;
+}
+
+void LinkerSmallObjectAllocator::create_page_record(void* page_addr, size_t free_blocks_cnt) {
+ small_object_page_record record;
+ record.page_addr = page_addr;
+ record.free_blocks_cnt = free_blocks_cnt;
+ record.allocated_blocks_cnt = 0;
+
+ linker_vector_t::iterator it = std::lower_bound(
+ page_records_.begin(), page_records_.end(), record);
+ page_records_.insert(it, record);
+}
+
+void LinkerSmallObjectAllocator::alloc_page() {
+ void* map_ptr = mmap(nullptr, PAGE_SIZE,
+ PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
+ if (map_ptr == MAP_FAILED) {
+ __libc_fatal("mmap failed");
+ }
+
+ prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, map_ptr, PAGE_SIZE, name_);
+
+ memset(map_ptr, 0, PAGE_SIZE);
+
+ page_info* info = reinterpret_cast<page_info*>(map_ptr);
+ memcpy(info->signature, kSignature, sizeof(kSignature));
+ info->type = type_;
+ info->allocator_addr = this;
+
+ size_t free_blocks_cnt = (PAGE_SIZE - sizeof(page_info))/block_size_;
+
+ create_page_record(map_ptr, free_blocks_cnt);
+
+ small_object_block_record* first_block = reinterpret_cast<small_object_block_record*>(info + 1);
+
+ first_block->next = free_blocks_list_;
+ first_block->free_blocks_cnt = free_blocks_cnt;
+
+ free_blocks_list_ = first_block;
+}
+
+
+LinkerMemoryAllocator::LinkerMemoryAllocator() {
+ static const char* allocator_names[kSmallObjectAllocatorsCount] = {
+ "linker_alloc_16", // 2^4
+ "linker_alloc_32", // 2^5
+ "linker_alloc_64", // and so on...
+ "linker_alloc_128",
+ "linker_alloc_256",
+ "linker_alloc_512",
+ "linker_alloc_1024", // 2^10
+ };
+
+ for (size_t i = 0; i < kSmallObjectAllocatorsCount; ++i) {
+ uint32_t type = i + kSmallObjectMinSizeLog2;
+ allocators_[i].init(type, 1 << type, allocator_names[i]);
+ }
+}
+
+void* LinkerMemoryAllocator::alloc_mmap(size_t size) {
+ size_t allocated_size = PAGE_END(size + sizeof(page_info));
+ void* map_ptr = mmap(nullptr, allocated_size,
+ PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
+
+ if (map_ptr == MAP_FAILED) {
+ __libc_fatal("mmap failed");
+ }
+
+ prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, map_ptr, allocated_size, "linker_alloc_lob");
+
+ memset(map_ptr, 0, allocated_size);
+
+ page_info* info = reinterpret_cast<page_info*>(map_ptr);
+ memcpy(info->signature, kSignature, sizeof(kSignature));
+ info->type = kLargeObject;
+ info->allocated_size = allocated_size;
+
+ return info + 1;
+}
+
+void* LinkerMemoryAllocator::alloc(size_t size) {
+ // treat alloc(0) as alloc(1)
+ if (size == 0) {
+ size = 1;
+ }
+
+ if (size > kSmallObjectMaxSize) {
+ return alloc_mmap(size);
+ }
+
+ uint16_t log2_size = log2(size);
+
+ if (log2_size < kSmallObjectMinSizeLog2) {
+ log2_size = kSmallObjectMinSizeLog2;
+ }
+
+ return get_small_object_allocator(log2_size)->alloc();
+}
+
+page_info* LinkerMemoryAllocator::get_page_info(void* ptr) {
+ page_info* info = reinterpret_cast<page_info*>(PAGE_START(reinterpret_cast<size_t>(ptr)));
+ if (memcmp(info->signature, kSignature, sizeof(kSignature)) != 0) {
+ __libc_fatal("invalid pointer %p (page signature mismatch)", ptr);
+ }
+
+ return info;
+}
+
+void* LinkerMemoryAllocator::realloc(void* ptr, size_t size) {
+ if (ptr == nullptr) {
+ return alloc(size);
+ }
+
+ if (size == 0) {
+ free(ptr);
+ return nullptr;
+ }
+
+ page_info* info = get_page_info(ptr);
+
+ size_t old_size = 0;
+
+ if (info->type == kLargeObject) {
+ old_size = info->allocated_size - sizeof(page_info);
+ } else {
+ LinkerSmallObjectAllocator* allocator = get_small_object_allocator(info->type);
+ if (allocator != info->allocator_addr) {
+ __libc_fatal("invalid pointer %p (page signature mismatch)", ptr);
+ }
+
+ old_size = allocator->get_block_size();
+ }
+
+ if (old_size < size) {
+ void *result = alloc(size);
+ memcpy(result, ptr, old_size);
+ free(ptr);
+ return result;
+ }
+
+ return ptr;
+}
+
+void LinkerMemoryAllocator::free(void* ptr) {
+ if (ptr == nullptr) {
+ return;
+ }
+
+ page_info* info = get_page_info(ptr);
+
+ if (info->type == kLargeObject) {
+ munmap(info, info->allocated_size);
+ } else {
+ LinkerSmallObjectAllocator* allocator = get_small_object_allocator(info->type);
+ if (allocator != info->allocator_addr) {
+ __libc_fatal("invalid pointer %p (invalid allocator address for the page)", ptr);
+ }
+
+ allocator->free(ptr);
+ }
+}
+
+LinkerSmallObjectAllocator* LinkerMemoryAllocator::get_small_object_allocator(uint32_t type) {
+ if (type < kSmallObjectMinSizeLog2 || type > kSmallObjectMaxSizeLog2) {
+ __libc_fatal("invalid type: %u", type);
+ }
+
+ return &allocators_[type - kSmallObjectMinSizeLog2];
+}
diff --git a/linker/linker_allocator.h b/linker/linker_allocator.h
new file mode 100644
index 0000000..2adad56
--- /dev/null
+++ b/linker/linker_allocator.h
@@ -0,0 +1,143 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __LINKER_ALLOCATOR_H
+#define __LINKER_ALLOCATOR_H
+
+#include <stdlib.h>
+#include <sys/cdefs.h>
+#include <sys/mman.h>
+#include <stddef.h>
+#include <unistd.h>
+
+#include <vector>
+
+#include "private/bionic_prctl.h"
+#include "private/libc_logging.h"
+
+const uint32_t kSmallObjectMaxSizeLog2 = 10;
+const uint32_t kSmallObjectMinSizeLog2 = 4;
+const uint32_t kSmallObjectAllocatorsCount = kSmallObjectMaxSizeLog2 - kSmallObjectMinSizeLog2 + 1;
+
+class LinkerSmallObjectAllocator;
+
+// This structure is placed at the beginning of each addressable page
+// and has all information we need to find the corresponding memory allocator.
+struct page_info {
+ char signature[4];
+ uint32_t type;
+ union {
+ // we use allocated_size for large objects allocator
+ size_t allocated_size;
+ // and allocator_addr for small ones.
+ LinkerSmallObjectAllocator* allocator_addr;
+ };
+};
+
+struct small_object_page_record {
+ void* page_addr;
+ size_t free_blocks_cnt;
+ size_t allocated_blocks_cnt;
+};
+
+// for lower_bound...
+bool operator<(const small_object_page_record& one, const small_object_page_record& two);
+
+struct small_object_block_record {
+ small_object_block_record* next;
+ size_t free_blocks_cnt;
+};
+
+// This is implementation for std::vector allocator
+template <typename T>
+class linker_vector_allocator {
+ public:
+ typedef T value_type;
+ typedef T* pointer;
+ typedef const T* const_pointer;
+ typedef T& reference;
+ typedef const T& const_reference;
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+
+ T* allocate(size_t n, const T* hint = nullptr) {
+ size_t size = n * sizeof(T);
+ void* ptr = mmap(const_cast<T*>(hint), size,
+ PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
+ if (ptr == MAP_FAILED) {
+ // Spec says we need to throw std::bad_alloc here but because our
+ // code does not support exception handling anyways - we are going to abort.
+ __libc_fatal("mmap failed");
+ }
+
+ prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, ptr, size, "linker_alloc_vector");
+
+ return reinterpret_cast<T*>(ptr);
+ }
+
+ void deallocate(T* ptr, size_t n) {
+ munmap(ptr, n * sizeof(T));
+ }
+};
+
+typedef
+ std::vector<small_object_page_record, linker_vector_allocator<small_object_page_record>>
+ linker_vector_t;
+
+
+class LinkerSmallObjectAllocator {
+ public:
+ LinkerSmallObjectAllocator();
+ void init(uint32_t type, size_t block_size, const char* name);
+ void* alloc();
+ void free(void* ptr);
+
+ size_t get_block_size() const { return block_size_; }
+ private:
+ void alloc_page();
+ void free_page(linker_vector_t::iterator page_record);
+ linker_vector_t::iterator find_page_record(void* ptr);
+ void create_page_record(void* page_addr, size_t free_blocks_cnt);
+
+ uint32_t type_;
+ const char* name_;
+ size_t block_size_;
+
+ size_t free_pages_cnt_;
+ small_object_block_record* free_blocks_list_;
+
+ // sorted vector of page records
+ linker_vector_t page_records_;
+};
+
+class LinkerMemoryAllocator {
+ public:
+ LinkerMemoryAllocator();
+ void* alloc(size_t size);
+
+ // Note that this implementation of realloc never shrinks allocation
+ void* realloc(void* ptr, size_t size);
+ void free(void* ptr);
+ private:
+ void* alloc_mmap(size_t size);
+ page_info* get_page_info(void* ptr);
+ LinkerSmallObjectAllocator* get_small_object_allocator(uint32_t type);
+
+ LinkerSmallObjectAllocator allocators_[kSmallObjectAllocatorsCount];
+};
+
+
+#endif /* __LINKER_ALLOCATOR_H */
diff --git a/linker/linker_block_allocator.h b/linker/linker_block_allocator.h
index 1d41806..4b9b995 100644
--- a/linker/linker_block_allocator.h
+++ b/linker/linker_block_allocator.h
@@ -14,8 +14,8 @@
* limitations under the License.
*/
-#ifndef __LINKER_ALLOCATOR_H
-#define __LINKER_ALLOCATOR_H
+#ifndef __LINKER_BLOCK_ALLOCATOR_H
+#define __LINKER_BLOCK_ALLOCATOR_H
#include <stdlib.h>
#include <limits.h>
@@ -24,11 +24,11 @@
struct LinkerBlockAllocatorPage;
/*
- * This class is a non-template version of the LinkerAllocator
+ * This class is a non-template version of the LinkerTypeAllocator
* It keeps code inside .cpp file by keeping the interface
* template-free.
*
- * Please use LinkerAllocator<type> where possible (everywhere).
+ * Please use LinkerTypeAllocator<type> where possible (everywhere).
*/
class LinkerBlockAllocator {
public:
@@ -50,11 +50,21 @@
};
/*
- * We can't use malloc(3) in the dynamic linker.
- *
* A simple allocator for the dynamic linker. An allocator allocates instances
* of a single fixed-size type. Allocations are backed by page-sized private
* anonymous mmaps.
+ *
+ * The differences between this allocator and LinkerMemoryAllocator are:
+ * 1. This allocator manages space more efficiently. LinkerMemoryAllocator
+ * operates in power-of-two sized blocks up to 1k, when this implementation
+ * splits the page to aligned size of structure; For example for structures
+ * with size 513 this allocator will use 516 (520 for lp64) bytes of data
+ * where generalized implementation is going to use 1024 sized blocks.
+ *
+ * 2. This allocator does not munmap allocated memory, where LinkerMemoryAllocator does.
+ *
+ * 3. This allocator provides mprotect services to the user, where LinkerMemoryAllocator
+ * always treats it's memory as READ|WRITE.
*/
template<typename T>
class LinkerTypeAllocator {
@@ -68,4 +78,4 @@
DISALLOW_COPY_AND_ASSIGN(LinkerTypeAllocator);
};
-#endif // __LINKER_ALLOCATOR_H
+#endif // __LINKER_BLOCK_ALLOCATOR_H
diff --git a/linker/linker_memory.cpp b/linker/linker_memory.cpp
new file mode 100644
index 0000000..1892d02
--- /dev/null
+++ b/linker/linker_memory.cpp
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "linker_allocator.h"
+
+#include <stdlib.h>
+
+static LinkerMemoryAllocator g_linker_allocator;
+
+void* malloc(size_t byte_count) {
+ return g_linker_allocator.alloc(byte_count);
+}
+
+void* calloc(size_t item_count, size_t item_size) {
+ return g_linker_allocator.alloc(item_count*item_size);
+}
+
+void* realloc(void* p, size_t byte_count) {
+ return g_linker_allocator.realloc(p, byte_count);
+}
+
+void free(void* ptr) {
+ g_linker_allocator.free(ptr);
+}
+
diff --git a/linker/tests/Android.mk b/linker/tests/Android.mk
index 9a08bec..35992c5 100644
--- a/linker/tests/Android.mk
+++ b/linker/tests/Android.mk
@@ -29,6 +29,11 @@
LOCAL_SRC_FILES := \
linked_list_test.cpp \
linker_block_allocator_test.cpp \
- ../linker_block_allocator.cpp
+ ../linker_block_allocator.cpp \
+ linker_memory_allocator_test.cpp \
+ ../linker_allocator.cpp
+
+# for __libc_fatal
+LOCAL_SRC_FILES += ../../libc/bionic/libc_logging.cpp
include $(BUILD_NATIVE_TEST)
diff --git a/linker/tests/linker_memory_allocator_test.cpp b/linker/tests/linker_memory_allocator_test.cpp
new file mode 100644
index 0000000..f002a0d
--- /dev/null
+++ b/linker/tests/linker_memory_allocator_test.cpp
@@ -0,0 +1,193 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <sys/mman.h>
+
+#include <gtest/gtest.h>
+
+#include "../linker_allocator.h"
+
+#include <unistd.h>
+
+namespace {
+
+/*
+ * this one has size below allocator cap which is 2*sizeof(void*)
+ */
+struct test_struct_small {
+ char dummy_str[5];
+};
+
+struct test_struct_large {
+ char dummy_str[1009];
+};
+
+struct test_struct_huge {
+ char dummy_str[73939];
+};
+
+struct test_struct_512 {
+ char dummy_str[503];
+};
+
+};
+
+static size_t kPageSize = sysconf(_SC_PAGE_SIZE);
+
+TEST(linker_memory, test_alloc_0) {
+ LinkerMemoryAllocator allocator;
+ void* ptr = allocator.alloc(0);
+ ASSERT_TRUE(ptr != nullptr);
+ free(ptr);
+}
+
+TEST(linker_memory, test_free_nullptr) {
+ LinkerMemoryAllocator allocator;
+ allocator.free(nullptr);
+}
+
+TEST(linker_memory, test_realloc) {
+ LinkerMemoryAllocator allocator;
+ uint32_t* array = reinterpret_cast<uint32_t*>(allocator.alloc(512));
+ const size_t array_size = 512 / sizeof(uint32_t);
+
+ uint32_t model[1000];
+
+ model[0] = 1;
+ model[1] = 1;
+
+ for (size_t i = 2; i < 1000; ++i) {
+ model[i] = model[i - 1] + model[i - 2];
+ }
+
+ memcpy(array, model, array_size);
+
+ uint32_t* reallocated_ptr = reinterpret_cast<uint32_t*>(allocator.realloc(array, 1024));
+
+ ASSERT_TRUE(reallocated_ptr != nullptr);
+ ASSERT_TRUE(reallocated_ptr != array);
+
+ ASSERT_TRUE(memcmp(reallocated_ptr, model, array_size) == 0);
+
+ array = reallocated_ptr;
+
+ memcpy(array, model, 2*array_size);
+
+ reallocated_ptr = reinterpret_cast<uint32_t*>(allocator.realloc(array, 62));
+
+ ASSERT_TRUE(reallocated_ptr == array);
+
+ reallocated_ptr = reinterpret_cast<uint32_t*>(allocator.realloc(array, 4000));
+
+ ASSERT_TRUE(reallocated_ptr != nullptr);
+ ASSERT_TRUE(reallocated_ptr != array);
+
+ ASSERT_TRUE(memcmp(reallocated_ptr, model, array_size * 2) == 0);
+
+ array = reallocated_ptr;
+
+ memcpy(array, model, 4000);
+
+ reallocated_ptr = reinterpret_cast<uint32_t*>(allocator.realloc(array, 64000));
+
+ ASSERT_TRUE(reallocated_ptr != nullptr);
+ ASSERT_TRUE(reallocated_ptr != array);
+
+ ASSERT_TRUE(memcmp(reallocated_ptr, model, 4000) == 0);
+
+ ASSERT_EQ(nullptr, realloc(reallocated_ptr, 0));
+}
+
+TEST(linker_memory, test_small_smoke) {
+ LinkerMemoryAllocator allocator;
+
+ uint8_t zeros[16];
+ memset(zeros, 0, sizeof(zeros));
+
+ test_struct_small* ptr1 =
+ reinterpret_cast<test_struct_small*>(allocator.alloc(sizeof(test_struct_small)));
+ test_struct_small* ptr2 =
+ reinterpret_cast<test_struct_small*>(allocator.alloc(sizeof(test_struct_small)));
+
+ ASSERT_TRUE(ptr1 != nullptr);
+ ASSERT_TRUE(ptr2 != nullptr);
+ ASSERT_EQ(reinterpret_cast<uintptr_t>(ptr1)+16, reinterpret_cast<uintptr_t>(ptr2));
+ ASSERT_TRUE(memcmp(ptr1, zeros, 16) == 0);
+
+ allocator.free(ptr1);
+ allocator.free(ptr2);
+}
+
+TEST(linker_memory, test_huge_smoke) {
+ LinkerMemoryAllocator allocator;
+
+ // this should trigger proxy-to-mmap
+ test_struct_huge* ptr1 =
+ reinterpret_cast<test_struct_huge*>(allocator.alloc(sizeof(test_struct_huge)));
+ test_struct_huge* ptr2 =
+ reinterpret_cast<test_struct_huge*>(allocator.alloc(sizeof(test_struct_huge)));
+
+ ASSERT_TRUE(ptr1 != nullptr);
+ ASSERT_TRUE(ptr2 != nullptr);
+
+ ASSERT_TRUE(
+ reinterpret_cast<uintptr_t>(ptr1)/kPageSize != reinterpret_cast<uintptr_t>(ptr2)/kPageSize);
+ allocator.free(ptr2);
+ allocator.free(ptr1);
+}
+
+TEST(linker_memory, test_large) {
+ LinkerMemoryAllocator allocator;
+
+ test_struct_large* ptr1 =
+ reinterpret_cast<test_struct_large*>(allocator.alloc(sizeof(test_struct_large)));
+ test_struct_large* ptr2 =
+ reinterpret_cast<test_struct_large*>(allocator.alloc(1024));
+
+ ASSERT_TRUE(ptr1 != nullptr);
+ ASSERT_TRUE(ptr2 != nullptr);
+
+ ASSERT_EQ(reinterpret_cast<uintptr_t>(ptr1) + 1024, reinterpret_cast<uintptr_t>(ptr2));
+
+ // let's allocate until we reach the next page.
+ size_t n = kPageSize / sizeof(test_struct_large) + 1 - 2;
+ test_struct_large* objects[n];
+
+ for (size_t i = 0; i < n; ++i) {
+ test_struct_large* obj_ptr =
+ reinterpret_cast<test_struct_large*>(allocator.alloc(sizeof(test_struct_large)));
+ ASSERT_TRUE(obj_ptr != nullptr);
+ objects[i] = obj_ptr;
+ }
+
+ test_struct_large* ptr_to_free =
+ reinterpret_cast<test_struct_large*>(allocator.alloc(sizeof(test_struct_large)));
+
+ ASSERT_TRUE(ptr_to_free != nullptr);
+
+ allocator.free(ptr1);
+
+ for (size_t i=0; i<n; ++i) {
+ allocator.free(objects[i]);
+ }
+
+ allocator.free(ptr2);
+ allocator.free(ptr_to_free);
+}
+
+
