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 #ifndef __LINKER_ALLOCATOR_H
     18 #define __LINKER_ALLOCATOR_H
     19 
     20 #include <stdlib.h>
     21 #include <sys/cdefs.h>
     22 #include <sys/mman.h>
     23 #include <stddef.h>
     24 #include <unistd.h>
     25 
     26 #include <vector>
     27 
     28 #include "private/bionic_prctl.h"
     29 #include "private/libc_logging.h"
     30 
     31 const uint32_t kSmallObjectMaxSizeLog2 = 10;
     32 const uint32_t kSmallObjectMinSizeLog2 = 4;
     33 const uint32_t kSmallObjectAllocatorsCount = kSmallObjectMaxSizeLog2 - kSmallObjectMinSizeLog2 + 1;
     34 
     35 class LinkerSmallObjectAllocator;
     36 
     37 // This structure is placed at the beginning of each addressable page
     38 // and has all information we need to find the corresponding memory allocator.
     39 struct page_info {
     40   char signature[4];
     41   uint32_t type;
     42   union {
     43     // we use allocated_size for large objects allocator
     44     size_t allocated_size;
     45     // and allocator_addr for small ones.
     46     LinkerSmallObjectAllocator* allocator_addr;
     47   };
     48 } __attribute__((aligned(16)));
     49 
     50 struct small_object_page_record {
     51   void* page_addr;
     52   size_t free_blocks_cnt;
     53   size_t allocated_blocks_cnt;
     54 };
     55 
     56 // for lower_bound...
     57 bool operator<(const small_object_page_record& one, const small_object_page_record& two);
     58 
     59 struct small_object_block_record {
     60   small_object_block_record* next;
     61   size_t free_blocks_cnt;
     62 };
     63 
     64 // This is implementation for std::vector allocator
     65 template <typename T>
     66 class linker_vector_allocator {
     67  public:
     68   typedef T value_type;
     69   typedef T* pointer;
     70   typedef const T* const_pointer;
     71   typedef T& reference;
     72   typedef const T& const_reference;
     73   typedef size_t size_type;
     74   typedef ptrdiff_t difference_type;
     75 
     76   T* allocate(size_t n, const T* hint = nullptr) {
     77     size_t size = n * sizeof(T);
     78     void* ptr = mmap(const_cast<T*>(hint), size,
     79         PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
     80     if (ptr == MAP_FAILED) {
     81       // Spec says we need to throw std::bad_alloc here but because our
     82       // code does not support exception handling anyways - we are going to abort.
     83       __libc_fatal("mmap failed");
     84     }
     85 
     86     prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, ptr, size, "linker_alloc_vector");
     87 
     88     return reinterpret_cast<T*>(ptr);
     89   }
     90 
     91   void deallocate(T* ptr, size_t n) {
     92     munmap(ptr, n * sizeof(T));
     93   }
     94 };
     95 
     96 typedef
     97     std::vector<small_object_page_record, linker_vector_allocator<small_object_page_record>>
     98     linker_vector_t;
     99 
    100 
    101 class LinkerSmallObjectAllocator {
    102  public:
    103   LinkerSmallObjectAllocator();
    104   void init(uint32_t type, size_t block_size);
    105   void* alloc();
    106   void free(void* ptr);
    107 
    108   size_t get_block_size() const { return block_size_; }
    109  private:
    110   void alloc_page();
    111   void free_page(linker_vector_t::iterator page_record);
    112   linker_vector_t::iterator find_page_record(void* ptr);
    113   void create_page_record(void* page_addr, size_t free_blocks_cnt);
    114 
    115   uint32_t type_;
    116   size_t block_size_;
    117 
    118   size_t free_pages_cnt_;
    119   small_object_block_record* free_blocks_list_;
    120 
    121   // sorted vector of page records
    122   linker_vector_t page_records_;
    123 };
    124 
    125 class LinkerMemoryAllocator {
    126  public:
    127   LinkerMemoryAllocator();
    128   void* alloc(size_t size);
    129 
    130   // Note that this implementation of realloc never shrinks allocation
    131   void* realloc(void* ptr, size_t size);
    132   void free(void* ptr);
    133  private:
    134   void* alloc_mmap(size_t size);
    135   page_info* get_page_info(void* ptr);
    136   LinkerSmallObjectAllocator* get_small_object_allocator(uint32_t type);
    137 
    138   LinkerSmallObjectAllocator allocators_[kSmallObjectAllocatorsCount];
    139 };
    140 
    141 
    142 #endif  /* __LINKER_ALLOCATOR_H */
    143