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