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