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