1e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe/* 2e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * Copyright (C) 2014 The Android Open Source Project 3e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * 4e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * Licensed under the Apache License, Version 2.0 (the "License"); 5e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * you may not use this file except in compliance with the License. 6e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * You may obtain a copy of the License at 7e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * 8e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * http://www.apache.org/licenses/LICENSE-2.0 9e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * 10e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * Unless required by applicable law or agreed to in writing, software 11e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * distributed under the License is distributed on an "AS IS" BASIS, 12e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * See the License for the specific language governing permissions and 14e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe * limitations under the License. 15e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe */ 16e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 17e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe#include "swap_space.h" 18e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 19e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe#include <algorithm> 20e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe#include <numeric> 21ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko#include <sys/mman.h> 22e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 23e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe#include "base/logging.h" 24e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe#include "base/macros.h" 25e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe#include "base/mutex.h" 26e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe#include "thread-inl.h" 27e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 28e21dc3db191df04c100620965bee4617b3b24397Andreas Gampenamespace art { 29e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 30e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe// The chunk size by which the swap file is increased and mapped. 31e21dc3db191df04c100620965bee4617b3b24397Andreas Gampestatic constexpr size_t kMininumMapSize = 16 * MB; 32e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 33e21dc3db191df04c100620965bee4617b3b24397Andreas Gampestatic constexpr bool kCheckFreeMaps = false; 34e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 35e21dc3db191df04c100620965bee4617b3b24397Andreas Gampetemplate <typename FreeBySizeSet> 36e21dc3db191df04c100620965bee4617b3b24397Andreas Gampestatic void DumpFreeMap(const FreeBySizeSet& free_by_size) { 37e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe size_t last_size = static_cast<size_t>(-1); 38e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe for (const auto& entry : free_by_size) { 39e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (last_size != entry.first) { 40e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe last_size = entry.first; 41e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe LOG(INFO) << "Size " << last_size; 42e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 43e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe LOG(INFO) << " 0x" << std::hex << entry.second->Start() 44e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe << " size=" << std::dec << entry.second->size; 45e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 46e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe} 47e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 48ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Markovoid SwapSpace::RemoveChunk(FreeBySizeSet::const_iterator free_by_size_pos) { 49e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe auto free_by_start_pos = free_by_size_pos->second; 50ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko free_by_size_.erase(free_by_size_pos); 51ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko free_by_start_.erase(free_by_start_pos); 52e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe} 53e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 54ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Markoinline void SwapSpace::InsertChunk(const SpaceChunk& chunk) { 55e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe DCHECK_NE(chunk.size, 0u); 56ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko auto insert_result = free_by_start_.insert(chunk); 57e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe DCHECK(insert_result.second); 58ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko free_by_size_.emplace(chunk.size, insert_result.first); 59e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe} 60e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 61e21dc3db191df04c100620965bee4617b3b24397Andreas GampeSwapSpace::SwapSpace(int fd, size_t initial_size) 62e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe : fd_(fd), 63e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe size_(0), 64e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe lock_("SwapSpace lock", static_cast<LockLevel>(LockLevel::kDefaultMutexLevel - 1)) { 65e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // Assume that the file is unlinked. 66e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 67ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko InsertChunk(NewFileChunk(initial_size)); 68e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe} 69e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 70e21dc3db191df04c100620965bee4617b3b24397Andreas GampeSwapSpace::~SwapSpace() { 71ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko // Unmap all mmapped chunks. Nothing should be allocated anymore at 72ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko // this point, so there should be only full size chunks in free_by_start_. 73ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko for (const SpaceChunk& chunk : free_by_start_) { 74ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko if (munmap(chunk.ptr, chunk.size) != 0) { 75ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko PLOG(ERROR) << "Failed to unmap swap space chunk at " 76ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko << static_cast<const void*>(chunk.ptr) << " size=" << chunk.size; 77ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko } 78ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko } 79e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // All arenas are backed by the same file. Just close the descriptor. 80e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe close(fd_); 81e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe} 82e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 83e21dc3db191df04c100620965bee4617b3b24397Andreas Gampetemplate <typename FreeByStartSet, typename FreeBySizeSet> 84e21dc3db191df04c100620965bee4617b3b24397Andreas Gampestatic size_t CollectFree(const FreeByStartSet& free_by_start, const FreeBySizeSet& free_by_size) { 85e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (free_by_start.size() != free_by_size.size()) { 86e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe LOG(FATAL) << "Size: " << free_by_start.size() << " vs " << free_by_size.size(); 87e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 88e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 89e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // Calculate over free_by_size. 90e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe size_t sum1 = 0; 91e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe for (const auto& entry : free_by_size) { 92e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe sum1 += entry.second->size; 93e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 94e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 95e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // Calculate over free_by_start. 96e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe size_t sum2 = 0; 97e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe for (const auto& entry : free_by_start) { 98e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe sum2 += entry.size; 99e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 100e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 101e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (sum1 != sum2) { 102e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe LOG(FATAL) << "Sum: " << sum1 << " vs " << sum2; 103e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 104e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe return sum1; 105e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe} 106e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 107e21dc3db191df04c100620965bee4617b3b24397Andreas Gampevoid* SwapSpace::Alloc(size_t size) { 108e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe MutexLock lock(Thread::Current(), lock_); 109e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe size = RoundUp(size, 8U); 110e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 111e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // Check the free list for something that fits. 112e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // TODO: Smarter implementation. Global biggest chunk, ... 113e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe SpaceChunk old_chunk; 114e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe auto it = free_by_start_.empty() 115e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe ? free_by_size_.end() 116e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe : free_by_size_.lower_bound(FreeBySizeEntry { size, free_by_start_.begin() }); 117e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (it != free_by_size_.end()) { 118e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe old_chunk = *it->second; 119ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko RemoveChunk(it); 120e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } else { 121e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // Not a big enough free chunk, need to increase file size. 122e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe old_chunk = NewFileChunk(size); 123e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 124e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 125e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe void* ret = old_chunk.ptr; 126e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 127e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (old_chunk.size != size) { 128e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // Insert the remainder. 129e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe SpaceChunk new_chunk = { old_chunk.ptr + size, old_chunk.size - size }; 130ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko InsertChunk(new_chunk); 131e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 132e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 133e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe return ret; 134e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe} 135e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 136ef9230b63c66fc17304d45851c3482a25858ab6fVladimir MarkoSwapSpace::SpaceChunk SwapSpace::NewFileChunk(size_t min_size) { 137bed520b360f2aa81d00d30417cc96cc4f174c7ecAndreas Gampe#if !defined(__APPLE__) 138e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe size_t next_part = std::max(RoundUp(min_size, kPageSize), RoundUp(kMininumMapSize, kPageSize)); 139e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe int result = TEMP_FAILURE_RETRY(ftruncate64(fd_, size_ + next_part)); 140e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (result != 0) { 141e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe PLOG(FATAL) << "Unable to increase swap file."; 142e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 143e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe uint8_t* ptr = reinterpret_cast<uint8_t*>( 144e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe mmap(nullptr, next_part, PROT_READ | PROT_WRITE, MAP_SHARED, fd_, size_)); 145e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (ptr == MAP_FAILED) { 146e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe LOG(ERROR) << "Unable to mmap new swap file chunk."; 147e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe LOG(ERROR) << "Current size: " << size_ << " requested: " << next_part << "/" << min_size; 148e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe LOG(ERROR) << "Free list:"; 149e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe DumpFreeMap(free_by_size_); 150e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe LOG(ERROR) << "In free list: " << CollectFree(free_by_start_, free_by_size_); 151e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe LOG(FATAL) << "Aborting..."; 152e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 153e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe size_ += next_part; 154e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe SpaceChunk new_chunk = {ptr, next_part}; 155e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe return new_chunk; 156bed520b360f2aa81d00d30417cc96cc4f174c7ecAndreas Gampe#else 157edb157fa272b58be8bb90fa4dc9cb7ca4c2760f2Andreas Gampe UNUSED(min_size, kMininumMapSize); 158bed520b360f2aa81d00d30417cc96cc4f174c7ecAndreas Gampe LOG(FATAL) << "No swap file support on the Mac."; 159edb157fa272b58be8bb90fa4dc9cb7ca4c2760f2Andreas Gampe UNREACHABLE(); 160bed520b360f2aa81d00d30417cc96cc4f174c7ecAndreas Gampe#endif 161e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe} 162e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 163e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe// TODO: Full coalescing. 164ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Markovoid SwapSpace::Free(void* ptr, size_t size) { 165e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe MutexLock lock(Thread::Current(), lock_); 166e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe size = RoundUp(size, 8U); 167e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 168e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe size_t free_before = 0; 169e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (kCheckFreeMaps) { 170e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe free_before = CollectFree(free_by_start_, free_by_size_); 171e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 172e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 173ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko SpaceChunk chunk = { reinterpret_cast<uint8_t*>(ptr), size }; 174e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe auto it = free_by_start_.lower_bound(chunk); 175e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (it != free_by_start_.begin()) { 176e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe auto prev = it; 177e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe --prev; 178e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe CHECK_LE(prev->End(), chunk.Start()); 179e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (prev->End() == chunk.Start()) { 180e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // Merge *prev with this chunk. 181e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe chunk.size += prev->size; 182e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe chunk.ptr -= prev->size; 183e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe auto erase_pos = free_by_size_.find(FreeBySizeEntry { prev->size, prev }); 184e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe DCHECK(erase_pos != free_by_size_.end()); 185ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko RemoveChunk(erase_pos); 186e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // "prev" is invalidated but "it" remains valid. 187e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 188e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 189e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (it != free_by_start_.end()) { 190e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe CHECK_LE(chunk.End(), it->Start()); 191e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (chunk.End() == it->Start()) { 192e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // Merge *it with this chunk. 193e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe chunk.size += it->size; 194e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe auto erase_pos = free_by_size_.find(FreeBySizeEntry { it->size, it }); 195e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe DCHECK(erase_pos != free_by_size_.end()); 196ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko RemoveChunk(erase_pos); 197e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe // "it" is invalidated but we don't need it anymore. 198e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 199e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 200ef9230b63c66fc17304d45851c3482a25858ab6fVladimir Marko InsertChunk(chunk); 201e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 202e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (kCheckFreeMaps) { 203e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe size_t free_after = CollectFree(free_by_start_, free_by_size_); 204e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 205e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe if (free_after != free_before + size) { 206e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe DumpFreeMap(free_by_size_); 207e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe CHECK_EQ(free_after, free_before + size) << "Should be " << size << " difference from " << free_before; 208e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 209e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe } 210e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe} 211e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe 212e21dc3db191df04c100620965bee4617b3b24397Andreas Gampe} // namespace art 213