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