119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov/* 219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * Copyright (C) 2015 The Android Open Source Project 319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * 419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * Licensed under the Apache License, Version 2.0 (the "License"); 519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * you may not use this file except in compliance with the License. 619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * You may obtain a copy of the License at 719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * 819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * http://www.apache.org/licenses/LICENSE-2.0 919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * 1019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * Unless required by applicable law or agreed to in writing, software 1119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * distributed under the License is distributed on an "AS IS" BASIS, 1219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * See the License for the specific language governing permissions and 1419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov * limitations under the License. 1519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov */ 1619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 1719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#ifndef __LINKER_ALLOCATOR_H 1819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#define __LINKER_ALLOCATOR_H 1919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 2019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <stdlib.h> 2119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <sys/cdefs.h> 2219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <sys/mman.h> 2319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <stddef.h> 2419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <unistd.h> 2519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 2619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include <vector> 2719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 2819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include "private/bionic_prctl.h" 2919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#include "private/libc_logging.h" 3019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 3119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovconst uint32_t kSmallObjectMaxSizeLog2 = 10; 3219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovconst uint32_t kSmallObjectMinSizeLog2 = 4; 3319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovconst uint32_t kSmallObjectAllocatorsCount = kSmallObjectMaxSizeLog2 - kSmallObjectMinSizeLog2 + 1; 3419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 3519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovclass LinkerSmallObjectAllocator; 3619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 3719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// This structure is placed at the beginning of each addressable page 3819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// and has all information we need to find the corresponding memory allocator. 3919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovstruct page_info { 4019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov char signature[4]; 4119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov uint32_t type; 4219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov union { 4319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov // we use allocated_size for large objects allocator 4419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t allocated_size; 4519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov // and allocator_addr for small ones. 4619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov LinkerSmallObjectAllocator* allocator_addr; 4719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov }; 483edc5c41bbee7cf608a781e7056599f32ca1949cDimitry Ivanov} __attribute__((aligned(16))); 4919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 5019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovstruct small_object_page_record { 5119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void* page_addr; 5219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t free_blocks_cnt; 5319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t allocated_blocks_cnt; 5419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov}; 5519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 5619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// for lower_bound... 5719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovbool operator<(const small_object_page_record& one, const small_object_page_record& two); 5819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 5919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovstruct small_object_block_record { 6019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov small_object_block_record* next; 6119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t free_blocks_cnt; 6219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov}; 6319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 6419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov// This is implementation for std::vector allocator 6519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovtemplate <typename T> 6619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovclass linker_vector_allocator { 6719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov public: 6819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov typedef T value_type; 6919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov typedef T* pointer; 7019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov typedef const T* const_pointer; 7119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov typedef T& reference; 7219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov typedef const T& const_reference; 7319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov typedef size_t size_type; 7419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov typedef ptrdiff_t difference_type; 7519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 7619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov T* allocate(size_t n, const T* hint = nullptr) { 7719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t size = n * sizeof(T); 7819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void* ptr = mmap(const_cast<T*>(hint), size, 7919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0); 8019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov if (ptr == MAP_FAILED) { 8119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov // Spec says we need to throw std::bad_alloc here but because our 8219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov // code does not support exception handling anyways - we are going to abort. 8319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov __libc_fatal("mmap failed"); 8419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 8519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 8619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, ptr, size, "linker_alloc_vector"); 8719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 8819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov return reinterpret_cast<T*>(ptr); 8919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 9019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 9119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void deallocate(T* ptr, size_t n) { 9219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov munmap(ptr, n * sizeof(T)); 9319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov } 9419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov}; 9519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 9619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovtypedef 9719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov std::vector<small_object_page_record, linker_vector_allocator<small_object_page_record>> 9819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov linker_vector_t; 9919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 10019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 10119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovclass LinkerSmallObjectAllocator { 10219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov public: 10319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov LinkerSmallObjectAllocator(); 104d9d6a84c016abea6745c7e7a789755f3449c7e4bDimitry Ivanov void init(uint32_t type, size_t block_size); 10519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void* alloc(); 10619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void free(void* ptr); 10719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 10819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t get_block_size() const { return block_size_; } 10919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov private: 11019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void alloc_page(); 11119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void free_page(linker_vector_t::iterator page_record); 11219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov linker_vector_t::iterator find_page_record(void* ptr); 11319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void create_page_record(void* page_addr, size_t free_blocks_cnt); 11419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 11519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov uint32_t type_; 11619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t block_size_; 11719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 11819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov size_t free_pages_cnt_; 11919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov small_object_block_record* free_blocks_list_; 12019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 12119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov // sorted vector of page records 12219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov linker_vector_t page_records_; 12319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov}; 12419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 12519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanovclass LinkerMemoryAllocator { 12619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov public: 12719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov LinkerMemoryAllocator(); 12819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void* alloc(size_t size); 12919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 13019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov // Note that this implementation of realloc never shrinks allocation 13119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void* realloc(void* ptr, size_t size); 13219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void free(void* ptr); 13319656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov private: 13419656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov void* alloc_mmap(size_t size); 13519656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov page_info* get_page_info(void* ptr); 13619656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov LinkerSmallObjectAllocator* get_small_object_allocator(uint32_t type); 13719656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 13819656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov LinkerSmallObjectAllocator allocators_[kSmallObjectAllocatorsCount]; 13919656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov}; 14019656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 14119656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov 14219656ce5376c95ce0deebc4d0c6af1bb8d740934Dmitriy Ivanov#endif /* __LINKER_ALLOCATOR_H */ 143