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 }; 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 deallocate(T * ptr,size_t n)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, const char* name); 105 void* alloc(); 106 void free(void* ptr); 107 get_block_size()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 const char* name_; 117 size_t block_size_; 118 119 size_t free_pages_cnt_; 120 small_object_block_record* free_blocks_list_; 121 122 // sorted vector of page records 123 linker_vector_t page_records_; 124 }; 125 126 class LinkerMemoryAllocator { 127 public: 128 LinkerMemoryAllocator(); 129 void* alloc(size_t size); 130 131 // Note that this implementation of realloc never shrinks allocation 132 void* realloc(void* ptr, size_t size); 133 void free(void* ptr); 134 private: 135 void* alloc_mmap(size_t size); 136 page_info* get_page_info(void* ptr); 137 LinkerSmallObjectAllocator* get_small_object_allocator(uint32_t type); 138 139 LinkerSmallObjectAllocator allocators_[kSmallObjectAllocatorsCount]; 140 }; 141 142 143 #endif /* __LINKER_ALLOCATOR_H */ 144