Home | History | Annotate | Download | only in linker
      1 /*
      2  * Copyright (C) 2015 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 
     17 #include "linker_allocator.h"
     18 #include "linker.h"
     19 
     20 #include <algorithm>
     21 #include <vector>
     22 
     23 #include <stdlib.h>
     24 #include <sys/mman.h>
     25 #include <unistd.h>
     26 
     27 #include "private/bionic_prctl.h"
     28 
     29 //
     30 // LinkerMemeoryAllocator is general purpose allocator
     31 // designed to provide the same functionality as the malloc/free/realloc
     32 // libc functions.
     33 //
     34 // On alloc:
     35 // If size is >= 1k allocator proxies malloc call directly to mmap
     36 // If size < 1k allocator uses SmallObjectAllocator for the size
     37 // rounded up to the nearest power of two.
     38 //
     39 // On free:
     40 //
     41 // For a pointer allocated using proxy-to-mmap allocator unmaps
     42 // the memory.
     43 //
     44 // For a pointer allocated using SmallObjectAllocator it adds
     45 // the block to free_blocks_list_. If the number of free pages reaches 2,
     46 // SmallObjectAllocator munmaps one of the pages keeping the other one
     47 // in reserve.
     48 
     49 static const char kSignature[4] = {'L', 'M', 'A', 1};
     50 
     51 static const size_t kSmallObjectMaxSize = 1 << kSmallObjectMaxSizeLog2;
     52 
     53 // This type is used for large allocations (with size >1k)
     54 static const uint32_t kLargeObject = 111;
     55 
     56 bool operator<(const small_object_page_record& one, const small_object_page_record& two) {
     57   return one.page_addr < two.page_addr;
     58 }
     59 
     60 static inline uint16_t log2(size_t number) {
     61   uint16_t result = 0;
     62   number--;
     63 
     64   while (number != 0) {
     65     result++;
     66     number >>= 1;
     67   }
     68 
     69   return result;
     70 }
     71 
     72 LinkerSmallObjectAllocator::LinkerSmallObjectAllocator()
     73     : type_(0), block_size_(0), free_pages_cnt_(0), free_blocks_list_(nullptr) {}
     74 
     75 void* LinkerSmallObjectAllocator::alloc() {
     76   if (free_blocks_list_ == nullptr) {
     77     alloc_page();
     78   }
     79 
     80   small_object_block_record* block_record = free_blocks_list_;
     81   if (block_record->free_blocks_cnt > 1) {
     82     small_object_block_record* next_free = reinterpret_cast<small_object_block_record*>(
     83         reinterpret_cast<uint8_t*>(block_record) + block_size_);
     84     next_free->next = block_record->next;
     85     next_free->free_blocks_cnt = block_record->free_blocks_cnt - 1;
     86     free_blocks_list_ = next_free;
     87   } else {
     88     free_blocks_list_ = block_record->next;
     89   }
     90 
     91   // bookkeeping...
     92   auto page_record = find_page_record(block_record);
     93 
     94   if (page_record->allocated_blocks_cnt == 0) {
     95     free_pages_cnt_--;
     96   }
     97 
     98   page_record->free_blocks_cnt--;
     99   page_record->allocated_blocks_cnt++;
    100 
    101   memset(block_record, 0, block_size_);
    102 
    103   return block_record;
    104 }
    105 
    106 void LinkerSmallObjectAllocator::free_page(linker_vector_t::iterator page_record) {
    107   void* page_start = reinterpret_cast<void*>(page_record->page_addr);
    108   void* page_end = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(page_start) + PAGE_SIZE);
    109 
    110   while (free_blocks_list_ != nullptr &&
    111       free_blocks_list_ > page_start &&
    112       free_blocks_list_ < page_end) {
    113     free_blocks_list_ = free_blocks_list_->next;
    114   }
    115 
    116   small_object_block_record* current = free_blocks_list_;
    117 
    118   while (current != nullptr) {
    119     while (current->next > page_start && current->next < page_end) {
    120       current->next = current->next->next;
    121     }
    122 
    123     current = current->next;
    124   }
    125 
    126   munmap(page_start, PAGE_SIZE);
    127   page_records_.erase(page_record);
    128   free_pages_cnt_--;
    129 }
    130 
    131 void LinkerSmallObjectAllocator::free(void* ptr) {
    132   auto page_record = find_page_record(ptr);
    133 
    134   ssize_t offset = reinterpret_cast<uintptr_t>(ptr) - sizeof(page_info);
    135 
    136   if (offset % block_size_ != 0) {
    137     __libc_fatal("invalid pointer: %p (block_size=%zd)", ptr, block_size_);
    138   }
    139 
    140   memset(ptr, 0, block_size_);
    141   small_object_block_record* block_record = reinterpret_cast<small_object_block_record*>(ptr);
    142 
    143   block_record->next = free_blocks_list_;
    144   block_record->free_blocks_cnt = 1;
    145 
    146   free_blocks_list_ = block_record;
    147 
    148   page_record->free_blocks_cnt++;
    149   page_record->allocated_blocks_cnt--;
    150 
    151   if (page_record->allocated_blocks_cnt == 0) {
    152     if (free_pages_cnt_++ > 1) {
    153       // if we already have a free page - unmap this one.
    154       free_page(page_record);
    155     }
    156   }
    157 }
    158 
    159 void LinkerSmallObjectAllocator::init(uint32_t type, size_t block_size) {
    160   type_ = type;
    161   block_size_ = block_size;
    162 }
    163 
    164 linker_vector_t::iterator LinkerSmallObjectAllocator::find_page_record(void* ptr) {
    165   void* addr = reinterpret_cast<void*>(PAGE_START(reinterpret_cast<uintptr_t>(ptr)));
    166   small_object_page_record boundary;
    167   boundary.page_addr = addr;
    168   linker_vector_t::iterator it = std::lower_bound(
    169       page_records_.begin(), page_records_.end(), boundary);
    170 
    171   if (it == page_records_.end() || it->page_addr != addr) {
    172     // not found...
    173     __libc_fatal("page record for %p was not found (block_size=%zd)", ptr, block_size_);
    174   }
    175 
    176   return it;
    177 }
    178 
    179 void LinkerSmallObjectAllocator::create_page_record(void* page_addr, size_t free_blocks_cnt) {
    180   small_object_page_record record;
    181   record.page_addr = page_addr;
    182   record.free_blocks_cnt = free_blocks_cnt;
    183   record.allocated_blocks_cnt = 0;
    184 
    185   linker_vector_t::iterator it = std::lower_bound(
    186       page_records_.begin(), page_records_.end(), record);
    187   page_records_.insert(it, record);
    188 }
    189 
    190 void LinkerSmallObjectAllocator::alloc_page() {
    191   static_assert(sizeof(page_info) % 16 == 0,
    192                 "sizeof(page_info) is not multiple of 16");
    193   void* map_ptr = mmap(nullptr, PAGE_SIZE,
    194       PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
    195   if (map_ptr == MAP_FAILED) {
    196     __libc_fatal("mmap failed");
    197   }
    198 
    199   prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, map_ptr, PAGE_SIZE, "linker_alloc_small_objects");
    200 
    201   memset(map_ptr, 0, PAGE_SIZE);
    202 
    203   page_info* info = reinterpret_cast<page_info*>(map_ptr);
    204   memcpy(info->signature, kSignature, sizeof(kSignature));
    205   info->type = type_;
    206   info->allocator_addr = this;
    207 
    208   size_t free_blocks_cnt = (PAGE_SIZE - sizeof(page_info))/block_size_;
    209 
    210   create_page_record(map_ptr, free_blocks_cnt);
    211 
    212   small_object_block_record* first_block = reinterpret_cast<small_object_block_record*>(info + 1);
    213 
    214   first_block->next = free_blocks_list_;
    215   first_block->free_blocks_cnt = free_blocks_cnt;
    216 
    217   free_blocks_list_ = first_block;
    218 }
    219 
    220 
    221 LinkerMemoryAllocator::LinkerMemoryAllocator() {
    222   for (size_t i = 0; i < kSmallObjectAllocatorsCount; ++i) {
    223     uint32_t type = i + kSmallObjectMinSizeLog2;
    224     allocators_[i].init(type, 1 << type);
    225   }
    226 }
    227 
    228 void* LinkerMemoryAllocator::alloc_mmap(size_t size) {
    229   size_t allocated_size = PAGE_END(size + sizeof(page_info));
    230   void* map_ptr = mmap(nullptr, allocated_size,
    231       PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
    232 
    233   if (map_ptr == MAP_FAILED) {
    234     __libc_fatal("mmap failed");
    235   }
    236 
    237   prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, map_ptr, allocated_size, "linker_alloc_lob");
    238 
    239   memset(map_ptr, 0, allocated_size);
    240 
    241   page_info* info = reinterpret_cast<page_info*>(map_ptr);
    242   memcpy(info->signature, kSignature, sizeof(kSignature));
    243   info->type = kLargeObject;
    244   info->allocated_size = allocated_size;
    245 
    246   return info + 1;
    247 }
    248 
    249 void* LinkerMemoryAllocator::alloc(size_t size) {
    250   // treat alloc(0) as alloc(1)
    251   if (size == 0) {
    252     size = 1;
    253   }
    254 
    255   if (size > kSmallObjectMaxSize) {
    256     return alloc_mmap(size);
    257   }
    258 
    259   uint16_t log2_size = log2(size);
    260 
    261   if (log2_size < kSmallObjectMinSizeLog2) {
    262     log2_size = kSmallObjectMinSizeLog2;
    263   }
    264 
    265   return get_small_object_allocator(log2_size)->alloc();
    266 }
    267 
    268 page_info* LinkerMemoryAllocator::get_page_info(void* ptr) {
    269   page_info* info = reinterpret_cast<page_info*>(PAGE_START(reinterpret_cast<size_t>(ptr)));
    270   if (memcmp(info->signature, kSignature, sizeof(kSignature)) != 0) {
    271     __libc_fatal("invalid pointer %p (page signature mismatch)", ptr);
    272   }
    273 
    274   return info;
    275 }
    276 
    277 void* LinkerMemoryAllocator::realloc(void* ptr, size_t size) {
    278   if (ptr == nullptr) {
    279     return alloc(size);
    280   }
    281 
    282   if (size == 0) {
    283     free(ptr);
    284     return nullptr;
    285   }
    286 
    287   page_info* info = get_page_info(ptr);
    288 
    289   size_t old_size = 0;
    290 
    291   if (info->type == kLargeObject) {
    292     old_size = info->allocated_size - sizeof(page_info);
    293   } else {
    294     LinkerSmallObjectAllocator* allocator = get_small_object_allocator(info->type);
    295     if (allocator != info->allocator_addr) {
    296       __libc_fatal("invalid pointer %p (page signature mismatch)", ptr);
    297     }
    298 
    299     old_size = allocator->get_block_size();
    300   }
    301 
    302   if (old_size < size) {
    303     void *result = alloc(size);
    304     memcpy(result, ptr, old_size);
    305     free(ptr);
    306     return result;
    307   }
    308 
    309   return ptr;
    310 }
    311 
    312 void LinkerMemoryAllocator::free(void* ptr) {
    313   if (ptr == nullptr) {
    314     return;
    315   }
    316 
    317   page_info* info = get_page_info(ptr);
    318 
    319   if (info->type == kLargeObject) {
    320     munmap(info, info->allocated_size);
    321   } else {
    322     LinkerSmallObjectAllocator* allocator = get_small_object_allocator(info->type);
    323     if (allocator != info->allocator_addr) {
    324       __libc_fatal("invalid pointer %p (invalid allocator address for the page)", ptr);
    325     }
    326 
    327     allocator->free(ptr);
    328   }
    329 }
    330 
    331 LinkerSmallObjectAllocator* LinkerMemoryAllocator::get_small_object_allocator(uint32_t type) {
    332   if (type < kSmallObjectMinSizeLog2 || type > kSmallObjectMaxSizeLog2) {
    333     __libc_fatal("invalid type: %u", type);
    334   }
    335 
    336   return &allocators_[type - kSmallObjectMinSizeLog2];
    337 }
    338