119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov/* 219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * Copyright (C) 2015 The Android Open Source Project 3bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * All rights reserved. 419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * 5bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * Redistribution and use in source and binary forms, with or without 6bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * modification, are permitted provided that the following conditions 7bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * are met: 8bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * * Redistributions of source code must retain the above copyright 9bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * notice, this list of conditions and the following disclaimer. 10bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * * Redistributions in binary form must reproduce the above copyright 11bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * notice, this list of conditions and the following disclaimer in 12bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * the documentation and/or other materials provided with the 13bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * distribution. 1419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * 15bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 16bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 17bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 18bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 19bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 20bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 21bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 22bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 23bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 24bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 25bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26bcc4da9b752f0def46d63ed7b31f3f49cc2435adDimitry Ivanov * SUCH DAMAGE. 2719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov */ 2819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 2919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include "linker_allocator.h" 30f857211675dcfe7abd311e4a7bef6d1685fb4a93Dimitry Ivanov#include "linker_debug.h" 3119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include "linker.h" 3219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 3319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <algorithm> 3419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <vector> 3519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 3619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <stdlib.h> 3719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <sys/mman.h> 3819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <unistd.h> 3919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 407a3681e5b6c39bc2b3b62031ca5941dbf7bc4e63Christopher Ferris#include <async_safe/log.h> 417a3681e5b6c39bc2b3b62031ca5941dbf7bc4e63Christopher Ferris 4219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include "private/bionic_prctl.h" 4319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 4419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// 4519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// LinkerMemeoryAllocator is general purpose allocator 4619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// designed to provide the same functionality as the malloc/free/realloc 4719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// libc functions. 4819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// 4919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// On alloc: 5019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// If size is >= 1k allocator proxies malloc call directly to mmap 5119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// If size < 1k allocator uses SmallObjectAllocator for the size 5219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// rounded up to the nearest power of two. 5319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// 5419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// On free: 5519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// 5619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// For a pointer allocated using proxy-to-mmap allocator unmaps 5719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// the memory. 5819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// 5919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// For a pointer allocated using SmallObjectAllocator it adds 6019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// the block to free_blocks_list_. If the number of free pages reaches 2, 6119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// SmallObjectAllocator munmaps one of the pages keeping the other one 6219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// in reserve. 6319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 6419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovstatic const char kSignature[4] = {'L', 'M', 'A', 1}; 6519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 6619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovstatic const size_t kSmallObjectMaxSize = 1 << kSmallObjectMaxSizeLog2; 6719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 6819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// This type is used for large allocations (with size >1k) 6919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovstatic const uint32_t kLargeObject = 111; 7019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 7119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovbool operator<(const small_object_page_record& one, const small_object_page_record& two) { 7219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return one.page_addr < two.page_addr; 7319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 7419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 7519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovstatic inline uint16_t log2(size_t number) { 7619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov uint16_t result = 0; 7719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov number--; 7819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 7919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov while (number != 0) { 8019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov result++; 8119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov number >>= 1; 8219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 8319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 8419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return result; 8519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 8619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 8765707b696a59f28b3980c78bdb4b049231610e64Dimitry IvanovLinkerSmallObjectAllocator::LinkerSmallObjectAllocator(uint32_t type, size_t block_size) 8865707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov : type_(type), block_size_(block_size), free_pages_cnt_(0), free_blocks_list_(nullptr) {} 8919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 9019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovvoid* LinkerSmallObjectAllocator::alloc() { 91f857211675dcfe7abd311e4a7bef6d1685fb4a93Dimitry Ivanov CHECK(block_size_ != 0); 92f857211675dcfe7abd311e4a7bef6d1685fb4a93Dimitry Ivanov 9319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (free_blocks_list_ == nullptr) { 9419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov alloc_page(); 9519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 9619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 9719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov small_object_block_record* block_record = free_blocks_list_; 9819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (block_record->free_blocks_cnt > 1) { 9919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov small_object_block_record* next_free = reinterpret_cast<small_object_block_record*>( 10019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov reinterpret_cast<uint8_t*>(block_record) + block_size_); 10119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov next_free->next = block_record->next; 10219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov next_free->free_blocks_cnt = block_record->free_blocks_cnt - 1; 10319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free_blocks_list_ = next_free; 10419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } else { 10519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free_blocks_list_ = block_record->next; 10619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 10719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 10819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov // bookkeeping... 10919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov auto page_record = find_page_record(block_record); 11019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 11119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (page_record->allocated_blocks_cnt == 0) { 11219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free_pages_cnt_--; 11319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 11419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 11519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_record->free_blocks_cnt--; 11619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_record->allocated_blocks_cnt++; 11719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 11819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov memset(block_record, 0, block_size_); 11919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 12019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return block_record; 12119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 12219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 12319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovvoid LinkerSmallObjectAllocator::free_page(linker_vector_t::iterator page_record) { 12419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void* page_start = reinterpret_cast<void*>(page_record->page_addr); 12519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void* page_end = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(page_start) + PAGE_SIZE); 12619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 12719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov while (free_blocks_list_ != nullptr && 12819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free_blocks_list_ > page_start && 12919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free_blocks_list_ < page_end) { 13019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free_blocks_list_ = free_blocks_list_->next; 13119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 13219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 13319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov small_object_block_record* current = free_blocks_list_; 13419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 13519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov while (current != nullptr) { 13619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov while (current->next > page_start && current->next < page_end) { 13719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov current->next = current->next->next; 13819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 13919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 14019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov current = current->next; 14119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 14219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 14319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov munmap(page_start, PAGE_SIZE); 14419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_records_.erase(page_record); 14519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free_pages_cnt_--; 14619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 14719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 14819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovvoid LinkerSmallObjectAllocator::free(void* ptr) { 14919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov auto page_record = find_page_record(ptr); 15019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 15119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov ssize_t offset = reinterpret_cast<uintptr_t>(ptr) - sizeof(page_info); 15219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 15319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (offset % block_size_ != 0) { 1547a3681e5b6c39bc2b3b62031ca5941dbf7bc4e63Christopher Ferris async_safe_fatal("invalid pointer: %p (block_size=%zd)", ptr, block_size_); 15519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 15619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 15719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov memset(ptr, 0, block_size_); 15819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov small_object_block_record* block_record = reinterpret_cast<small_object_block_record*>(ptr); 15919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 16019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov block_record->next = free_blocks_list_; 16119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov block_record->free_blocks_cnt = 1; 16219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 16319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free_blocks_list_ = block_record; 16419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 16519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_record->free_blocks_cnt++; 16619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_record->allocated_blocks_cnt--; 16719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 16819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (page_record->allocated_blocks_cnt == 0) { 16919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (free_pages_cnt_++ > 1) { 17019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov // if we already have a free page - unmap this one. 17119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free_page(page_record); 17219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 17319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 17419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 17519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 17619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovlinker_vector_t::iterator LinkerSmallObjectAllocator::find_page_record(void* ptr) { 17719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void* addr = reinterpret_cast<void*>(PAGE_START(reinterpret_cast<uintptr_t>(ptr))); 17819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov small_object_page_record boundary; 17919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov boundary.page_addr = addr; 18019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov linker_vector_t::iterator it = std::lower_bound( 18119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_records_.begin(), page_records_.end(), boundary); 18219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 18319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (it == page_records_.end() || it->page_addr != addr) { 18419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov // not found... 1857a3681e5b6c39bc2b3b62031ca5941dbf7bc4e63Christopher Ferris async_safe_fatal("page record for %p was not found (block_size=%zd)", ptr, block_size_); 18619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 18719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 18819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return it; 18919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 19019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 19119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovvoid LinkerSmallObjectAllocator::create_page_record(void* page_addr, size_t free_blocks_cnt) { 19219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov small_object_page_record record; 19319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov record.page_addr = page_addr; 19419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov record.free_blocks_cnt = free_blocks_cnt; 19519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov record.allocated_blocks_cnt = 0; 19619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 19719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov linker_vector_t::iterator it = std::lower_bound( 19819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_records_.begin(), page_records_.end(), record); 19919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_records_.insert(it, record); 20019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 20119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 20219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovvoid LinkerSmallObjectAllocator::alloc_page() { 2037b0af7ad82fcf88e800d1a553d81fda29dc064bdElliott Hughes static_assert(sizeof(page_info) % 16 == 0, "sizeof(page_info) is not multiple of 16"); 2047b0af7ad82fcf88e800d1a553d81fda29dc064bdElliott Hughes void* map_ptr = mmap(nullptr, PAGE_SIZE, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); 20519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (map_ptr == MAP_FAILED) { 2067b0af7ad82fcf88e800d1a553d81fda29dc064bdElliott Hughes async_safe_fatal("mmap failed: %s", strerror(errno)); 20719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 20819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 209d9d6a84c016abea6745c7e7a789755f3449c7e4bDimitry Ivanov prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, map_ptr, PAGE_SIZE, "linker_alloc_small_objects"); 21019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 21119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_info* info = reinterpret_cast<page_info*>(map_ptr); 21219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov memcpy(info->signature, kSignature, sizeof(kSignature)); 21319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov info->type = type_; 21419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov info->allocator_addr = this; 21519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 21619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t free_blocks_cnt = (PAGE_SIZE - sizeof(page_info))/block_size_; 21719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 21819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov create_page_record(map_ptr, free_blocks_cnt); 21919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 22019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov small_object_block_record* first_block = reinterpret_cast<small_object_block_record*>(info + 1); 22119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 22219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov first_block->next = free_blocks_list_; 22319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov first_block->free_blocks_cnt = free_blocks_cnt; 22419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 22519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free_blocks_list_ = first_block; 22619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 22719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 22819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 22965707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanovvoid LinkerMemoryAllocator::initialize_allocators() { 23065707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov if (allocators_ != nullptr) { 23165707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov return; 23265707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov } 23365707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov 23465707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov LinkerSmallObjectAllocator* allocators = 23565707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov reinterpret_cast<LinkerSmallObjectAllocator*>(allocators_buf_); 23665707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov 23719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov for (size_t i = 0; i < kSmallObjectAllocatorsCount; ++i) { 23819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov uint32_t type = i + kSmallObjectMinSizeLog2; 23965707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov new (allocators + i) LinkerSmallObjectAllocator(type, 1 << type); 24019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 24165707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov 24265707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov allocators_ = allocators; 24319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 24419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 24519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovvoid* LinkerMemoryAllocator::alloc_mmap(size_t size) { 24619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t allocated_size = PAGE_END(size + sizeof(page_info)); 2477b0af7ad82fcf88e800d1a553d81fda29dc064bdElliott Hughes void* map_ptr = mmap(nullptr, allocated_size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 2487b0af7ad82fcf88e800d1a553d81fda29dc064bdElliott Hughes -1, 0); 24919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 25019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (map_ptr == MAP_FAILED) { 2517b0af7ad82fcf88e800d1a553d81fda29dc064bdElliott Hughes async_safe_fatal("mmap failed: %s", strerror(errno)); 25219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 25319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 25419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, map_ptr, allocated_size, "linker_alloc_lob"); 25519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 25619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_info* info = reinterpret_cast<page_info*>(map_ptr); 25719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov memcpy(info->signature, kSignature, sizeof(kSignature)); 25819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov info->type = kLargeObject; 25919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov info->allocated_size = allocated_size; 26019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 26119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return info + 1; 26219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 26319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 26419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovvoid* LinkerMemoryAllocator::alloc(size_t size) { 26519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov // treat alloc(0) as alloc(1) 26619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (size == 0) { 26719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size = 1; 26819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 26919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 27019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (size > kSmallObjectMaxSize) { 27119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return alloc_mmap(size); 27219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 27319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 27419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov uint16_t log2_size = log2(size); 27519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 27619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (log2_size < kSmallObjectMinSizeLog2) { 27719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov log2_size = kSmallObjectMinSizeLog2; 27819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 27919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 28019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return get_small_object_allocator(log2_size)->alloc(); 28119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 28219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 28319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovpage_info* LinkerMemoryAllocator::get_page_info(void* ptr) { 28419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_info* info = reinterpret_cast<page_info*>(PAGE_START(reinterpret_cast<size_t>(ptr))); 28519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (memcmp(info->signature, kSignature, sizeof(kSignature)) != 0) { 2867a3681e5b6c39bc2b3b62031ca5941dbf7bc4e63Christopher Ferris async_safe_fatal("invalid pointer %p (page signature mismatch)", ptr); 28719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 28819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 28919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return info; 29019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 29119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 29219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovvoid* LinkerMemoryAllocator::realloc(void* ptr, size_t size) { 29319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (ptr == nullptr) { 29419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return alloc(size); 29519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 29619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 29719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (size == 0) { 29819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free(ptr); 29919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return nullptr; 30019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 30119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 30219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_info* info = get_page_info(ptr); 30319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 30419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t old_size = 0; 30519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 30619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (info->type == kLargeObject) { 30719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov old_size = info->allocated_size - sizeof(page_info); 30819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } else { 30919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov LinkerSmallObjectAllocator* allocator = get_small_object_allocator(info->type); 31019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (allocator != info->allocator_addr) { 3117a3681e5b6c39bc2b3b62031ca5941dbf7bc4e63Christopher Ferris async_safe_fatal("invalid pointer %p (page signature mismatch)", ptr); 31219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 31319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 31419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov old_size = allocator->get_block_size(); 31519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 31619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 31719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (old_size < size) { 31819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void *result = alloc(size); 31919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov memcpy(result, ptr, old_size); 32019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov free(ptr); 32119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return result; 32219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 32319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 32419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return ptr; 32519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 32619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 32719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovvoid LinkerMemoryAllocator::free(void* ptr) { 32819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (ptr == nullptr) { 32919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return; 33019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 33119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 33219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_info* info = get_page_info(ptr); 33319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 33419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (info->type == kLargeObject) { 33519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov munmap(info, info->allocated_size); 33619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } else { 33719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov LinkerSmallObjectAllocator* allocator = get_small_object_allocator(info->type); 33819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (allocator != info->allocator_addr) { 3397a3681e5b6c39bc2b3b62031ca5941dbf7bc4e63Christopher Ferris async_safe_fatal("invalid pointer %p (invalid allocator address for the page)", ptr); 34019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 34119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 34219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov allocator->free(ptr); 34319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 34419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 34519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 34619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy IvanovLinkerSmallObjectAllocator* LinkerMemoryAllocator::get_small_object_allocator(uint32_t type) { 34719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (type < kSmallObjectMinSizeLog2 || type > kSmallObjectMaxSizeLog2) { 3487a3681e5b6c39bc2b3b62031ca5941dbf7bc4e63Christopher Ferris async_safe_fatal("invalid type: %u", type); 34919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 35019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 35165707b696a59f28b3980c78bdb4b049231610e64Dimitry Ivanov initialize_allocators(); 35219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return &allocators_[type - kSmallObjectMinSizeLog2]; 35319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov} 354