1bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross/* 2bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * Copyright (C) 2016 The Android Open Source Project 3bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * 4bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * Licensed under the Apache License, Version 2.0 (the "License"); 5bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * you may not use this file except in compliance with the License. 6bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * You may obtain a copy of the License at 7bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * 8bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * http://www.apache.org/licenses/LICENSE-2.0 9bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * 10bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * Unless required by applicable law or agreed to in writing, software 11bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * distributed under the License is distributed on an "AS IS" BASIS, 12bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * See the License for the specific language governing permissions and 14bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross * limitations under the License. 15bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross */ 16bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 17bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// Header page: 18bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// 19bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// For minimum allocation size (8 bytes), bitmap can store used allocations for 20bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// up to 4032*8*8=258048, which is 256KiB minus the header page 21bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 22bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include <assert.h> 23bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include <stdlib.h> 24bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 25bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include <sys/cdefs.h> 26bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include <sys/mman.h> 27bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 28bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include <cmath> 29bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include <cstddef> 30bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include <cstdint> 31bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include <memory> 32bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include <mutex> 33bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 34bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include "android-base/macros.h" 35bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 36bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include "Allocator.h" 37bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross#include "LinkedList.h" 38a83881e33ce29ee236c924d669cb41a9d816962dColin Cross#include "anon_vma_naming.h" 39bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 40a9939e9a23ea21f4f8dc69cf1dae8e95debadcfbColin Crossnamespace android { 41a9939e9a23ea21f4f8dc69cf1dae8e95debadcfbColin Cross 42bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// runtime interfaces used: 43bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// abort 44bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// assert - fprintf + mmap 45bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// mmap 46bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// munmap 47bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// prctl 48bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 49bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossconstexpr size_t const_log2(size_t n, size_t p = 0) { 50bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return (n <= 1) ? p : const_log2(n / 2, p + 1); 51bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 52bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 53bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossconstexpr unsigned int div_round_up(unsigned int x, unsigned int y) { 54bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return (x + y - 1) / y; 55bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 56bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 57bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstatic constexpr size_t kPageSize = 4096; 58bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstatic constexpr size_t kChunkSize = 256 * 1024; 59bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstatic constexpr size_t kUsableChunkSize = kChunkSize - kPageSize; 60bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstatic constexpr size_t kMaxBucketAllocationSize = kChunkSize / 4; 61bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstatic constexpr size_t kMinBucketAllocationSize = 8; 62a83881e33ce29ee236c924d669cb41a9d816962dColin Crossstatic constexpr unsigned int kNumBuckets = 63a83881e33ce29ee236c924d669cb41a9d816962dColin Cross const_log2(kMaxBucketAllocationSize) - const_log2(kMinBucketAllocationSize) + 1; 64a83881e33ce29ee236c924d669cb41a9d816962dColin Crossstatic constexpr unsigned int kUsablePagesPerChunk = kUsableChunkSize / kPageSize; 65bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 66bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstd::atomic<int> heap_count; 67bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 68bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossclass Chunk; 69bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 70bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossclass HeapImpl { 71bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross public: 72bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross HeapImpl(); 73bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross ~HeapImpl(); 74bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void* operator new(std::size_t count) noexcept; 75bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void operator delete(void* ptr); 76bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 77bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void* Alloc(size_t size); 78bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void Free(void* ptr); 79bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross bool Empty(); 80bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 81bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void MoveToFullList(Chunk* chunk, int bucket_); 82bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void MoveToFreeList(Chunk* chunk, int bucket_); 83bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 84bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross private: 85bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross DISALLOW_COPY_AND_ASSIGN(HeapImpl); 86bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 87bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross LinkedList<Chunk*> free_chunks_[kNumBuckets]; 88bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross LinkedList<Chunk*> full_chunks_[kNumBuckets]; 89bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 90bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void MoveToList(Chunk* chunk, LinkedList<Chunk*>* head); 91bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void* MapAlloc(size_t size); 92bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void MapFree(void* ptr); 93bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void* AllocLocked(size_t size); 94bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void FreeLocked(void* ptr); 95bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 96bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross struct MapAllocation { 97a83881e33ce29ee236c924d669cb41a9d816962dColin Cross void* ptr; 98bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross size_t size; 99bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross MapAllocation* next; 100bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross }; 101bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross MapAllocation* map_allocation_list_; 102bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross std::mutex m_; 103bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross}; 104bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 105bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// Integer log 2, rounds down 106bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstatic inline unsigned int log2(size_t n) { 107bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return 8 * sizeof(unsigned long long) - __builtin_clzll(n) - 1; 108bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 109bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 110bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstatic inline unsigned int size_to_bucket(size_t size) { 111a83881e33ce29ee236c924d669cb41a9d816962dColin Cross if (size < kMinBucketAllocationSize) return kMinBucketAllocationSize; 112bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return log2(size - 1) + 1 - const_log2(kMinBucketAllocationSize); 113bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 114bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 115bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstatic inline size_t bucket_to_size(unsigned int bucket) { 116bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return kMinBucketAllocationSize << bucket; 117bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 118bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 119bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstatic void* MapAligned(size_t size, size_t align) { 120bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross const int prot = PROT_READ | PROT_WRITE; 121bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross const int flags = MAP_ANONYMOUS | MAP_PRIVATE; 122bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 123bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross size = (size + kPageSize - 1) & ~(kPageSize - 1); 124bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 125bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // Over-allocate enough to align 126bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross size_t map_size = size + align - kPageSize; 127bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (map_size < size) { 128bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return nullptr; 129bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 130bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 131bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void* ptr = mmap(NULL, map_size, prot, flags, -1, 0); 132bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (ptr == MAP_FAILED) { 133bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return nullptr; 134bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 135bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 136bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross size_t aligned_size = map_size; 137bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void* aligned_ptr = ptr; 138bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 139bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross std::align(align, size, aligned_ptr, aligned_size); 140bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 141bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // Trim beginning 142bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (aligned_ptr != ptr) { 143a83881e33ce29ee236c924d669cb41a9d816962dColin Cross ptrdiff_t extra = reinterpret_cast<uintptr_t>(aligned_ptr) - reinterpret_cast<uintptr_t>(ptr); 144bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross munmap(ptr, extra); 145bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross map_size -= extra; 146bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross ptr = aligned_ptr; 147bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 148bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 149bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // Trim end 150bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (map_size != size) { 151bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(map_size > size); 152bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(ptr != NULL); 153a83881e33ce29ee236c924d669cb41a9d816962dColin Cross munmap(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(ptr) + size), map_size - size); 154bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 155bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 156a83881e33ce29ee236c924d669cb41a9d816962dColin Cross#define PR_SET_VMA 0x53564d41 157a83881e33ce29ee236c924d669cb41a9d816962dColin Cross#define PR_SET_VMA_ANON_NAME 0 158a83881e33ce29ee236c924d669cb41a9d816962dColin Cross prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, reinterpret_cast<uintptr_t>(ptr), size, 159a83881e33ce29ee236c924d669cb41a9d816962dColin Cross "leak_detector_malloc"); 160bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 161bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return ptr; 162bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 163bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 164bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossclass Chunk { 165bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross public: 166bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross static void* operator new(std::size_t count) noexcept; 167bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross static void operator delete(void* ptr); 168bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross Chunk(HeapImpl* heap, int bucket); 169bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross ~Chunk() {} 170bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 171a83881e33ce29ee236c924d669cb41a9d816962dColin Cross void* Alloc(); 172bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void Free(void* ptr); 173bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void Purge(); 174bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross bool Empty(); 175bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 176bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross static Chunk* ptr_to_chunk(void* ptr) { 177a83881e33ce29ee236c924d669cb41a9d816962dColin Cross return reinterpret_cast<Chunk*>(reinterpret_cast<uintptr_t>(ptr) & ~(kChunkSize - 1)); 178bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 179bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross static bool is_chunk(void* ptr) { 180bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return (reinterpret_cast<uintptr_t>(ptr) & (kChunkSize - 1)) != 0; 181bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 182bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 183a83881e33ce29ee236c924d669cb41a9d816962dColin Cross unsigned int free_count() { return free_count_; } 184a83881e33ce29ee236c924d669cb41a9d816962dColin Cross HeapImpl* heap() { return heap_; } 185a83881e33ce29ee236c924d669cb41a9d816962dColin Cross LinkedList<Chunk*> node_; // linked list sorted by minimum free count 186bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 187bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross private: 188bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross DISALLOW_COPY_AND_ASSIGN(Chunk); 189bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross HeapImpl* heap_; 190bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross unsigned int bucket_; 191a83881e33ce29ee236c924d669cb41a9d816962dColin Cross unsigned int allocation_size_; // size of allocations in chunk, min 8 bytes 192a83881e33ce29ee236c924d669cb41a9d816962dColin Cross unsigned int max_allocations_; // maximum number of allocations in the chunk 193a83881e33ce29ee236c924d669cb41a9d816962dColin Cross unsigned int first_free_bitmap_; // index into bitmap for first non-full entry 194a83881e33ce29ee236c924d669cb41a9d816962dColin Cross unsigned int free_count_; // number of available allocations 195a83881e33ce29ee236c924d669cb41a9d816962dColin Cross unsigned int frees_since_purge_; // number of calls to Free since last Purge 196bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 197bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // bitmap of pages that have been dirtied 198bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross uint32_t dirty_pages_[div_round_up(kUsablePagesPerChunk, 32)]; 199bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 200bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // bitmap of free allocations. 201bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross uint32_t free_bitmap_[kUsableChunkSize / kMinBucketAllocationSize / 32]; 202bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 203bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross char data_[0]; 204bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 205bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross unsigned int ptr_to_n(void* ptr) { 206a83881e33ce29ee236c924d669cb41a9d816962dColin Cross ptrdiff_t offset = reinterpret_cast<uintptr_t>(ptr) - reinterpret_cast<uintptr_t>(data_); 207bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return offset / allocation_size_; 208bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 209a83881e33ce29ee236c924d669cb41a9d816962dColin Cross void* n_to_ptr(unsigned int n) { return data_ + n * allocation_size_; } 210bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross}; 211bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossstatic_assert(sizeof(Chunk) <= kPageSize, "header must fit in page"); 212bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 213bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// Override new operator on chunk to use mmap to allocate kChunkSize 214bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossvoid* Chunk::operator new(std::size_t count __attribute__((unused))) noexcept { 215bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(count == sizeof(Chunk)); 216bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void* mem = MapAligned(kChunkSize, kChunkSize); 217bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (!mem) { 218a83881e33ce29ee236c924d669cb41a9d816962dColin Cross abort(); // throw std::bad_alloc; 219bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 220bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 221bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return mem; 222bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 223bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 224bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// Override new operator on chunk to use mmap to allocate kChunkSize 225a83881e33ce29ee236c924d669cb41a9d816962dColin Crossvoid Chunk::operator delete(void* ptr) { 226bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(reinterpret_cast<Chunk*>(ptr) == ptr_to_chunk(ptr)); 227bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross munmap(ptr, kChunkSize); 228bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 229bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 230a83881e33ce29ee236c924d669cb41a9d816962dColin CrossChunk::Chunk(HeapImpl* heap, int bucket) 231a83881e33ce29ee236c924d669cb41a9d816962dColin Cross : node_(this), 232a83881e33ce29ee236c924d669cb41a9d816962dColin Cross heap_(heap), 233a83881e33ce29ee236c924d669cb41a9d816962dColin Cross bucket_(bucket), 234a83881e33ce29ee236c924d669cb41a9d816962dColin Cross allocation_size_(bucket_to_size(bucket)), 235a83881e33ce29ee236c924d669cb41a9d816962dColin Cross max_allocations_(kUsableChunkSize / allocation_size_), 236a83881e33ce29ee236c924d669cb41a9d816962dColin Cross first_free_bitmap_(0), 237a83881e33ce29ee236c924d669cb41a9d816962dColin Cross free_count_(max_allocations_), 238a83881e33ce29ee236c924d669cb41a9d816962dColin Cross frees_since_purge_(0) { 239bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross memset(dirty_pages_, 0, sizeof(dirty_pages_)); 240bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross memset(free_bitmap_, 0xff, sizeof(free_bitmap_)); 241bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 242bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 243bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossbool Chunk::Empty() { 244bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return free_count_ == max_allocations_; 245bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 246bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 247bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossvoid* Chunk::Alloc() { 248bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(free_count_ > 0); 249bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 250bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross unsigned int i = first_free_bitmap_; 251a83881e33ce29ee236c924d669cb41a9d816962dColin Cross while (free_bitmap_[i] == 0) i++; 252749ae2d32f81301a2f998cf09d7a7d67aefd4104Elliott Hughes assert(i < arraysize(free_bitmap_)); 253bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross unsigned int bit = __builtin_ffs(free_bitmap_[i]) - 1; 254bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(free_bitmap_[i] & (1U << bit)); 255bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross free_bitmap_[i] &= ~(1U << bit); 256bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross unsigned int n = i * 32 + bit; 257bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(n < max_allocations_); 258bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 259bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross unsigned int page = n * allocation_size_ / kPageSize; 260749ae2d32f81301a2f998cf09d7a7d67aefd4104Elliott Hughes assert(page / 32 < arraysize(dirty_pages_)); 261bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross dirty_pages_[page / 32] |= 1U << (page % 32); 262bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 263bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross free_count_--; 264bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (free_count_ == 0) { 265bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross heap_->MoveToFullList(this, bucket_); 266bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 267bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 268bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return n_to_ptr(n); 269bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 270bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 271bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossvoid Chunk::Free(void* ptr) { 272bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(is_chunk(ptr)); 273bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(ptr_to_chunk(ptr) == this); 274bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 275bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross unsigned int n = ptr_to_n(ptr); 276bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross unsigned int i = n / 32; 277bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross unsigned int bit = n % 32; 278bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 279749ae2d32f81301a2f998cf09d7a7d67aefd4104Elliott Hughes assert(i < arraysize(free_bitmap_)); 280bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(!(free_bitmap_[i] & (1U << bit))); 281bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross free_bitmap_[i] |= 1U << bit; 282bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross free_count_++; 283bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 284bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (i < first_free_bitmap_) { 285bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross first_free_bitmap_ = i; 286bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 287bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 288bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (free_count_ == 1) { 289bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross heap_->MoveToFreeList(this, bucket_); 290bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } else { 291bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // TODO(ccross): move down free list if necessary 292bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 293bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 294bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (frees_since_purge_++ * allocation_size_ > 16 * kPageSize) { 295bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross Purge(); 296bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 297bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 298bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 299bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossvoid Chunk::Purge() { 300bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross frees_since_purge_ = 0; 301bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 302a83881e33ce29ee236c924d669cb41a9d816962dColin Cross // unsigned int allocsPerPage = kPageSize / allocation_size_; 303bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 304bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 305bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross// Override new operator on HeapImpl to use mmap to allocate a page 306a83881e33ce29ee236c924d669cb41a9d816962dColin Crossvoid* HeapImpl::operator new(std::size_t count __attribute__((unused))) noexcept { 307bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(count == sizeof(HeapImpl)); 308bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void* mem = MapAligned(kPageSize, kPageSize); 309bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (!mem) { 310a83881e33ce29ee236c924d669cb41a9d816962dColin Cross abort(); // throw std::bad_alloc; 311bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 312bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 313bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross heap_count++; 314bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return mem; 315bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 316bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 317a83881e33ce29ee236c924d669cb41a9d816962dColin Crossvoid HeapImpl::operator delete(void* ptr) { 318bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross munmap(ptr, kPageSize); 319bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 320bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 321a83881e33ce29ee236c924d669cb41a9d816962dColin CrossHeapImpl::HeapImpl() : free_chunks_(), full_chunks_(), map_allocation_list_(NULL) {} 322bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 323bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossbool HeapImpl::Empty() { 324bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross for (unsigned int i = 0; i < kNumBuckets; i++) { 325a83881e33ce29ee236c924d669cb41a9d816962dColin Cross for (LinkedList<Chunk*>* it = free_chunks_[i].next(); it->data() != NULL; it = it->next()) { 326bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (!it->data()->Empty()) { 327bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return false; 328bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 329bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 330a83881e33ce29ee236c924d669cb41a9d816962dColin Cross for (LinkedList<Chunk*>* it = full_chunks_[i].next(); it->data() != NULL; it = it->next()) { 331bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (!it->data()->Empty()) { 332bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return false; 333bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 334bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 335bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 336bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 337bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return true; 338bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 339bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 340bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin CrossHeapImpl::~HeapImpl() { 341bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross for (unsigned int i = 0; i < kNumBuckets; i++) { 342bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross while (!free_chunks_[i].empty()) { 343a83881e33ce29ee236c924d669cb41a9d816962dColin Cross Chunk* chunk = free_chunks_[i].next()->data(); 344bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross chunk->node_.remove(); 345bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross delete chunk; 346bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 347bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross while (!full_chunks_[i].empty()) { 348a83881e33ce29ee236c924d669cb41a9d816962dColin Cross Chunk* chunk = full_chunks_[i].next()->data(); 349bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross chunk->node_.remove(); 350bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross delete chunk; 351bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 352bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 353bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 354bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 355bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossvoid* HeapImpl::Alloc(size_t size) { 356bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross std::lock_guard<std::mutex> lk(m_); 357bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return AllocLocked(size); 358bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 359bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 360bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossvoid* HeapImpl::AllocLocked(size_t size) { 36154a1610404986c998216a41b4c61c8b7aea4126cColin Cross if (size > kMaxBucketAllocationSize) { 362bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return MapAlloc(size); 363bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 364bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross int bucket = size_to_bucket(size); 36554a1610404986c998216a41b4c61c8b7aea4126cColin Cross if (free_chunks_[bucket].empty()) { 366a83881e33ce29ee236c924d669cb41a9d816962dColin Cross Chunk* chunk = new Chunk(this, bucket); 367bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross free_chunks_[bucket].insert(chunk->node_); 368bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 369bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return free_chunks_[bucket].next()->data()->Alloc(); 370bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 371bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 372a83881e33ce29ee236c924d669cb41a9d816962dColin Crossvoid HeapImpl::Free(void* ptr) { 373bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross std::lock_guard<std::mutex> lk(m_); 374bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross FreeLocked(ptr); 375bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 376bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 377a83881e33ce29ee236c924d669cb41a9d816962dColin Crossvoid HeapImpl::FreeLocked(void* ptr) { 378bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (!Chunk::is_chunk(ptr)) { 379bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross HeapImpl::MapFree(ptr); 380bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } else { 381bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross Chunk* chunk = Chunk::ptr_to_chunk(ptr); 382bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(chunk->heap() == this); 383bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross chunk->Free(ptr); 384bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 385bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 386bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 387bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossvoid* HeapImpl::MapAlloc(size_t size) { 388bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross size = (size + kPageSize - 1) & ~(kPageSize - 1); 389bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 390a83881e33ce29ee236c924d669cb41a9d816962dColin Cross MapAllocation* allocation = reinterpret_cast<MapAllocation*>(AllocLocked(sizeof(MapAllocation))); 391bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross void* ptr = MapAligned(size, kChunkSize); 392bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (!ptr) { 393bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross FreeLocked(allocation); 394a83881e33ce29ee236c924d669cb41a9d816962dColin Cross abort(); // throw std::bad_alloc; 395bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 396bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross allocation->ptr = ptr; 397bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross allocation->size = size; 398bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross allocation->next = map_allocation_list_; 399bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross map_allocation_list_ = allocation; 400bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 401bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return ptr; 402bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 403bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 404a83881e33ce29ee236c924d669cb41a9d816962dColin Crossvoid HeapImpl::MapFree(void* ptr) { 405a83881e33ce29ee236c924d669cb41a9d816962dColin Cross MapAllocation** allocation = &map_allocation_list_; 406a83881e33ce29ee236c924d669cb41a9d816962dColin Cross while (*allocation && (*allocation)->ptr != ptr) allocation = &(*allocation)->next; 407bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 408bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross assert(*allocation != nullptr); 409bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 410bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross munmap((*allocation)->ptr, (*allocation)->size); 411bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross FreeLocked(*allocation); 412bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 413bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross *allocation = (*allocation)->next; 414bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 415bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 416a83881e33ce29ee236c924d669cb41a9d816962dColin Crossvoid HeapImpl::MoveToFreeList(Chunk* chunk, int bucket) { 417bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross MoveToList(chunk, &free_chunks_[bucket]); 418bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 419bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 420a83881e33ce29ee236c924d669cb41a9d816962dColin Crossvoid HeapImpl::MoveToFullList(Chunk* chunk, int bucket) { 421bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross MoveToList(chunk, &full_chunks_[bucket]); 422bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 423bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 424a83881e33ce29ee236c924d669cb41a9d816962dColin Crossvoid HeapImpl::MoveToList(Chunk* chunk, LinkedList<Chunk*>* head) { 425bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // Remove from old list 426bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross chunk->node_.remove(); 427bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 428a83881e33ce29ee236c924d669cb41a9d816962dColin Cross LinkedList<Chunk*>* node = head; 429bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // Insert into new list, sorted by lowest free count 430a83881e33ce29ee236c924d669cb41a9d816962dColin Cross while (node->next() != head && node->data() != nullptr && 431a83881e33ce29ee236c924d669cb41a9d816962dColin Cross node->data()->free_count() < chunk->free_count()) 432bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross node = node->next(); 433bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 434bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross node->insert(chunk->node_); 435bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 436bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 437bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin CrossHeap::Heap() { 438bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // HeapImpl overloads the operator new in order to mmap itself instead of 439bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // allocating with new. 440bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // Can't use a shared_ptr to store the result because shared_ptr needs to 441bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross // allocate, and Allocator<T> is still being constructed. 442bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross impl_ = new HeapImpl(); 443bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross owns_impl_ = true; 444bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 445bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 446bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin CrossHeap::~Heap() { 447bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross if (owns_impl_) { 448bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross delete impl_; 449bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross } 450bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 451bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 452bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossvoid* Heap::allocate(size_t size) { 453bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return impl_->Alloc(size); 454bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 455bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 456bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossvoid Heap::deallocate(void* ptr) { 457bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross impl_->Free(ptr); 458bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 459bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 460a83881e33ce29ee236c924d669cb41a9d816962dColin Crossvoid Heap::deallocate(HeapImpl* impl, void* ptr) { 461bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross impl->Free(ptr); 462bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 463bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross 464bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Crossbool Heap::empty() { 465bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross return impl_->Empty(); 466bcb4ed3eaa92d23949d4ab33dbf1b2604bba8a18Colin Cross} 467a9939e9a23ea21f4f8dc69cf1dae8e95debadcfbColin Cross 468a9939e9a23ea21f4f8dc69cf1dae8e95debadcfbColin Cross} // namespace android 469