linker/linker_allocator.cpp

   1 /*
   2  * Copyright (C) 2014 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #include "linker_allocator.h"
  17 #include <inttypes.h>
  18 #include <sys/mman.h>
  19 #include <unistd.h>
  20
  21 struct LinkerAllocatorPage {
  22   LinkerAllocatorPage* next;
  23   uint8_t bytes[PAGE_SIZE-sizeof(LinkerAllocatorPage*)];
  24 };
  25
  26 struct FreeBlockInfo {
  27   void* next_block;
  28   size_t num_free_blocks;
  29 };
  30
  31 LinkerBlockAllocator::LinkerBlockAllocator()
  32   : block_size_(0),
  33     page_list_(nullptr),
  34     free_block_list_(nullptr)
  35 {}
  36
  37 void LinkerBlockAllocator::init(size_t block_size) {
  38   block_size_ = block_size < sizeof(FreeBlockInfo) ? sizeof(FreeBlockInfo) : block_size;
  39 }
  40
  41
  42 void* LinkerBlockAllocator::alloc() {
  43   if (free_block_list_ == nullptr) {
  44     create_new_page();
  45   }
  46
  47   FreeBlockInfo* block_info = reinterpret_cast<FreeBlockInfo*>(free_block_list_);
  48   if (block_info->num_free_blocks > 1) {
  49     FreeBlockInfo* next_block_info = reinterpret_cast<FreeBlockInfo*>(
  50       reinterpret_cast<char*>(free_block_list_) + block_size_);
  51     next_block_info->next_block = block_info->next_block;
  52     next_block_info->num_free_blocks = block_info->num_free_blocks - 1;
  53     free_block_list_ = next_block_info;
  54   } else {
  55     free_block_list_ = block_info->next_block;
  56   }
  57
  58   memset(block_info, 0, block_size_);
  59
  60   return block_info;
  61 }
  62
  63 void LinkerBlockAllocator::free(void* block) {
  64   if (block == nullptr) {
  65     return;
  66   }
  67
  68   LinkerAllocatorPage* page = find_page(block);
  69
  70   if (page == nullptr) {
  71     abort();
  72   }
  73
  74   ssize_t offset = reinterpret_cast<uint8_t*>(block) - page->bytes;
  75
  76   if (offset % block_size_ != 0) {
  77     abort();
  78   }
  79
  80   memset(block, 0, block_size_);
  81
  82   FreeBlockInfo* block_info = reinterpret_cast<FreeBlockInfo*>(block);
  83
  84   block_info->next_block = free_block_list_;
  85   block_info->num_free_blocks = 1;
  86
  87   free_block_list_ = block_info;
  88 }
  89
  90 void LinkerBlockAllocator::protect_all(int prot) {
  91   for (LinkerAllocatorPage* page = page_list_; page != nullptr; page = page->next) {
  92     if (mprotect(page, PAGE_SIZE, prot) == -1) {
  93       abort();
  94     }
  95   }
  96 }
  97
  98 void LinkerBlockAllocator::create_new_page() {
  99   LinkerAllocatorPage* page = reinterpret_cast<LinkerAllocatorPage*>(mmap(nullptr, PAGE_SIZE,
 100       PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0));
 101   if (page == MAP_FAILED) {
 102     abort(); // oom
 103   }
 104   memset(page, 0, PAGE_SIZE);
 105
 106   FreeBlockInfo* first_block = reinterpret_cast<FreeBlockInfo*>(page->bytes);
 107   first_block->next_block = free_block_list_;
 108   first_block->num_free_blocks = (PAGE_SIZE - sizeof(LinkerAllocatorPage*))/block_size_;
 109
 110   free_block_list_ = first_block;
 111
 112   page->next = page_list_;
 113   page_list_ = page;
 114 }
 115
 116 LinkerAllocatorPage* LinkerBlockAllocator::find_page(void* block) {
 117   if (block == nullptr) {
 118     abort();
 119   }
 120
 121   LinkerAllocatorPage* page = page_list_;
 122   while (page != nullptr) {
 123     const uint8_t* page_ptr = reinterpret_cast<const uint8_t*>(page);
 124     if (block >= (page_ptr + sizeof(page->next)) && block < (page_ptr + PAGE_SIZE)) {
 125       return page;
 126     }
 127
 128     page = page->next;
 129   }
 130
 131   abort();
 132 }