Home | History | Annotate | Download | only in linker 
      1 /*
      2  * Copyright (C) 2014 The Android Open Source Project
      3  * All rights reserved.
      4  *
      5  * Redistribution and use in source and binary forms, with or without
      6  * modification, are permitted provided that the following conditions
      7  * are met:
      8  *  * Redistributions of source code must retain the above copyright
      9  *    notice, this list of conditions and the following disclaimer.
     10  *  * Redistributions in binary form must reproduce the above copyright
     11  *    notice, this list of conditions and the following disclaimer in
     12  *    the documentation and/or other materials provided with the
     13  *    distribution.
     14  *
     15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     16  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     17  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
     18  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
     19  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
     20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
     21  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
     22  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
     23  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     24  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
     25  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     26  * SUCH DAMAGE.
     27  */
     28 
     29 #include "linker_block_allocator.h"
     30 #include <inttypes.h>
     31 #include <string.h>
     32 #include <sys/mman.h>
     33 #include <unistd.h>
     34 
     35 #include "private/bionic_prctl.h"
     36 
     37 // the multiplier should be power of 2
     38 static constexpr size_t round_up(size_t size, size_t multiplier) {
     39   return (size + (multiplier - 1)) & ~(multiplier-1);
     40 }
     41 
     42 struct LinkerBlockAllocatorPage {
     43   LinkerBlockAllocatorPage* next;
     44   uint8_t bytes[PAGE_SIZE - 16] __attribute__((aligned(16)));
     45 };
     46 
     47 struct FreeBlockInfo {
     48   void* next_block;
     49   size_t num_free_blocks;
     50 };
     51 
     52 LinkerBlockAllocator::LinkerBlockAllocator(size_t block_size)
     53   : block_size_(
     54       round_up(block_size < sizeof(FreeBlockInfo) ? sizeof(FreeBlockInfo) : block_size, 16)),
     55     page_list_(nullptr),
     56     free_block_list_(nullptr)
     57 {}
     58 
     59 void* LinkerBlockAllocator::alloc() {
     60   if (free_block_list_ == nullptr) {
     61     create_new_page();
     62   }
     63 
     64   FreeBlockInfo* block_info = reinterpret_cast<FreeBlockInfo*>(free_block_list_);
     65   if (block_info->num_free_blocks > 1) {
     66     FreeBlockInfo* next_block_info = reinterpret_cast<FreeBlockInfo*>(
     67       reinterpret_cast<char*>(free_block_list_) + block_size_);
     68     next_block_info->next_block = block_info->next_block;
     69     next_block_info->num_free_blocks = block_info->num_free_blocks - 1;
     70     free_block_list_ = next_block_info;
     71   } else {
     72     free_block_list_ = block_info->next_block;
     73   }
     74 
     75   memset(block_info, 0, block_size_);
     76 
     77   return block_info;
     78 }
     79 
     80 void LinkerBlockAllocator::free(void* block) {
     81   if (block == nullptr) {
     82     return;
     83   }
     84 
     85   LinkerBlockAllocatorPage* page = find_page(block);
     86 
     87   if (page == nullptr) {
     88     abort();
     89   }
     90 
     91   ssize_t offset = reinterpret_cast<uint8_t*>(block) - page->bytes;
     92 
     93   if (offset % block_size_ != 0) {
     94     abort();
     95   }
     96 
     97   memset(block, 0, block_size_);
     98 
     99   FreeBlockInfo* block_info = reinterpret_cast<FreeBlockInfo*>(block);
    100 
    101   block_info->next_block = free_block_list_;
    102   block_info->num_free_blocks = 1;
    103 
    104   free_block_list_ = block_info;
    105 }
    106 
    107 void LinkerBlockAllocator::protect_all(int prot) {
    108   for (LinkerBlockAllocatorPage* page = page_list_; page != nullptr; page = page->next) {
    109     if (mprotect(page, PAGE_SIZE, prot) == -1) {
    110       abort();
    111     }
    112   }
    113 }
    114 
    115 void LinkerBlockAllocator::create_new_page() {
    116   static_assert(sizeof(LinkerBlockAllocatorPage) == PAGE_SIZE,
    117                 "Invalid sizeof(LinkerBlockAllocatorPage)");
    118 
    119   LinkerBlockAllocatorPage* page = reinterpret_cast<LinkerBlockAllocatorPage*>(
    120       mmap(nullptr, PAGE_SIZE, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0));
    121 
    122   if (page == MAP_FAILED) {
    123     abort(); // oom
    124   }
    125 
    126   prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, page, PAGE_SIZE, "linker_alloc");
    127 
    128   FreeBlockInfo* first_block = reinterpret_cast<FreeBlockInfo*>(page->bytes);
    129   first_block->next_block = free_block_list_;
    130   first_block->num_free_blocks = (PAGE_SIZE - sizeof(LinkerBlockAllocatorPage*))/block_size_;
    131 
    132   free_block_list_ = first_block;
    133 
    134   page->next = page_list_;
    135   page_list_ = page;
    136 }
    137 
    138 LinkerBlockAllocatorPage* LinkerBlockAllocator::find_page(void* block) {
    139   if (block == nullptr) {
    140     abort();
    141   }
    142 
    143   LinkerBlockAllocatorPage* page = page_list_;
    144   while (page != nullptr) {
    145     const uint8_t* page_ptr = reinterpret_cast<const uint8_t*>(page);
    146     if (block >= (page_ptr + sizeof(page->next)) && block < (page_ptr + PAGE_SIZE)) {
    147       return page;
    148     }
    149 
    150     page = page->next;
    151   }
    152 
    153   abort();
    154 }
    155