1 files changed, 288 insertions, 74 deletions

diff --git a/linker/linker_allocator.cpp b/linker/linker_allocator.cpp
index 92220e8..1b16cf1 100644
--- a/linker/linker_allocator.cpp
+++ b/linker/linker_allocator.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014 The Android Open Source Project
+ * 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.
@@ -13,120 +13,334 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
+
 #include "linker_allocator.h"
-#include <inttypes.h>
+#include "linker.h"
+
+#include <algorithm>
+#include <vector>
+
+#include <stdlib.h>
 #include <sys/mman.h>
 #include <unistd.h>
 
 #include "private/bionic_prctl.h"
 
-struct LinkerAllocatorPage {
-  LinkerAllocatorPage* next;
-  uint8_t bytes[PAGE_SIZE-sizeof(LinkerAllocatorPage*)];
-};
-
-struct FreeBlockInfo {
-  void* next_block;
-  size_t num_free_blocks;
-};
-
-LinkerBlockAllocator::LinkerBlockAllocator(size_t block_size)
-  : block_size_(block_size < sizeof(FreeBlockInfo) ? sizeof(FreeBlockInfo) : block_size),
-    page_list_(nullptr),
-    free_block_list_(nullptr)
-{}
-
-void* LinkerBlockAllocator::alloc() {
-  if (free_block_list_ == nullptr) {
-    create_new_page();
-  }
-
-  FreeBlockInfo* block_info = reinterpret_cast<FreeBlockInfo*>(free_block_list_);
-  if (block_info->num_free_blocks > 1) {
-    FreeBlockInfo* next_block_info = reinterpret_cast<FreeBlockInfo*>(
-      reinterpret_cast<char*>(free_block_list_) + block_size_);
-    next_block_info->next_block = block_info->next_block;
-    next_block_info->num_free_blocks = block_info->num_free_blocks - 1;
-    free_block_list_ = next_block_info;
+//
+// 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_block_list_ = block_info->next_block;
+    free_blocks_list_ = block_record->next;
   }
 
-  memset(block_info, 0, block_size_);
+  // bookkeeping...
+  auto page_record = find_page_record(block_record);
 
-  return block_info;
+  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 LinkerBlockAllocator::free(void* block) {
-  if (block == nullptr) {
-    return;
+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;
   }
 
-  LinkerAllocatorPage* page = find_page(block);
+  small_object_block_record* current = free_blocks_list_;
 
-  if (page == nullptr) {
-    abort();
+  while (current != nullptr) {
+    while (current->next > page_start && current->next < page_end) {
+      current->next = current->next->next;
+    }
+
+    current = current->next;
   }
 
-  ssize_t offset = reinterpret_cast<uint8_t*>(block) - page->bytes;
+  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) {
-    abort();
+    __libc_fatal("invalid pointer: %p (block_size=%zd)", ptr, block_size_);
   }
 
-  memset(block, 0, block_size_);
+  memset(ptr, 0, block_size_);
+  small_object_block_record* block_record = reinterpret_cast<small_object_block_record*>(ptr);
 
-  FreeBlockInfo* block_info = reinterpret_cast<FreeBlockInfo*>(block);
+  block_record->next = free_blocks_list_;
+  block_record->free_blocks_cnt = 1;
 
-  block_info->next_block = free_block_list_;
-  block_info->num_free_blocks = 1;
+  free_blocks_list_ = block_record;
 
-  free_block_list_ = block_info;
-}
+  page_record->free_blocks_cnt++;
+  page_record->allocated_blocks_cnt--;
 
-void LinkerBlockAllocator::protect_all(int prot) {
-  for (LinkerAllocatorPage* page = page_list_; page != nullptr; page = page->next) {
-    if (mprotect(page, PAGE_SIZE, prot) == -1) {
-      abort();
+  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 LinkerBlockAllocator::create_new_page() {
-  LinkerAllocatorPage* page = reinterpret_cast<LinkerAllocatorPage*>(mmap(nullptr, PAGE_SIZE,
-      PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0));
-  if (page == MAP_FAILED) {
-    abort(); // oom
+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, page, PAGE_SIZE, "linker_alloc");
+  prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, map_ptr, PAGE_SIZE, name_);
+
+  memset(map_ptr, 0, PAGE_SIZE);
 
-  memset(page, 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;
 
-  FreeBlockInfo* first_block = reinterpret_cast<FreeBlockInfo*>(page->bytes);
-  first_block->next_block = free_block_list_;
-  first_block->num_free_blocks = (PAGE_SIZE - sizeof(LinkerAllocatorPage*))/block_size_;
+  size_t free_blocks_cnt = (PAGE_SIZE - sizeof(page_info))/block_size_;
 
-  free_block_list_ = first_block;
+  create_page_record(map_ptr, free_blocks_cnt);
 
-  page->next = page_list_;
-  page_list_ = page;
+  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;
 }
 
-LinkerAllocatorPage* LinkerBlockAllocator::find_page(void* block) {
-  if (block == nullptr) {
-    abort();
+
+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]);
   }
+}
 
-  LinkerAllocatorPage* page = page_list_;
-  while (page != nullptr) {
-    const uint8_t* page_ptr = reinterpret_cast<const uint8_t*>(page);
-    if (block >= (page_ptr + sizeof(page->next)) && block < (page_ptr + PAGE_SIZE)) {
-      return page;
+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);
     }
 
-    page = page->next;
+    allocator->free(ptr);
+  }
+}
+
+LinkerSmallObjectAllocator* LinkerMemoryAllocator::get_small_object_allocator(uint32_t type) {
+  if (type < kSmallObjectMinSizeLog2 || type > kSmallObjectMaxSizeLog2) {
+    __libc_fatal("invalid type: %u", type);
   }
 
-  abort();
+  return &allocators_[type - kSmallObjectMinSizeLog2];
 }