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

8 files changed, 745 insertions, 20 deletions

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 @@ LOCAL_SRC_FILES:= \
     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 @@ void count_relocation(RelocationKind) {
 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 @@ class LinkerBlockAllocator {
 };
 
 /*
- * 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 @@ class LinkerTypeAllocator {
   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_C_INCLUDES := $(LOCAL_PATH)/../../libc/
 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);
+}
+
+