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
19 #include <algorithm>
20 #include <numeric>
21
22 #include "base/logging.h"
23 #include "base/macros.h"
24 #include "base/mutex.h"
25 #include "thread-inl.h"
26
27 namespace art {
28
29 // The chunk size by which the swap file is increased and mapped.
30 static constexpr size_t kMininumMapSize = 16 * MB;
31
32 static constexpr bool kCheckFreeMaps = false;
33
34 template <typename FreeBySizeSet>
DumpFreeMap(const FreeBySizeSet & free_by_size)35 static void DumpFreeMap(const FreeBySizeSet& free_by_size) {
36 size_t last_size = static_cast<size_t>(-1);
37 for (const auto& entry : free_by_size) {
38 if (last_size != entry.first) {
39 last_size = entry.first;
40 LOG(INFO) << "Size " << last_size;
41 }
42 LOG(INFO) << " 0x" << std::hex << entry.second->Start()
43 << " size=" << std::dec << entry.second->size;
44 }
45 }
46
47 template <typename FreeByStartSet, typename FreeBySizeSet>
RemoveChunk(FreeByStartSet * free_by_start,FreeBySizeSet * free_by_size,typename FreeBySizeSet::const_iterator free_by_size_pos)48 static void RemoveChunk(FreeByStartSet* free_by_start,
49 FreeBySizeSet* free_by_size,
50 typename FreeBySizeSet::const_iterator free_by_size_pos) {
51 auto free_by_start_pos = free_by_size_pos->second;
52 free_by_size->erase(free_by_size_pos);
53 free_by_start->erase(free_by_start_pos);
54 }
55
56 template <typename FreeByStartSet, typename FreeBySizeSet>
InsertChunk(FreeByStartSet * free_by_start,FreeBySizeSet * free_by_size,const SpaceChunk & chunk)57 static void InsertChunk(FreeByStartSet* free_by_start,
58 FreeBySizeSet* free_by_size,
59 const SpaceChunk& chunk) {
60 DCHECK_NE(chunk.size, 0u);
61 auto insert_result = free_by_start->insert(chunk);
62 DCHECK(insert_result.second);
63 free_by_size->emplace(chunk.size, insert_result.first);
64 }
65
SwapSpace(int fd,size_t initial_size)66 SwapSpace::SwapSpace(int fd, size_t initial_size)
67 : fd_(fd),
68 size_(0),
69 lock_("SwapSpace lock", static_cast<LockLevel>(LockLevel::kDefaultMutexLevel - 1)) {
70 // Assume that the file is unlinked.
71
72 InsertChunk(&free_by_start_, &free_by_size_, NewFileChunk(initial_size));
73 }
74
~SwapSpace()75 SwapSpace::~SwapSpace() {
76 // All arenas are backed by the same file. Just close the descriptor.
77 close(fd_);
78 }
79
80 template <typename FreeByStartSet, typename FreeBySizeSet>
CollectFree(const FreeByStartSet & free_by_start,const FreeBySizeSet & free_by_size)81 static size_t CollectFree(const FreeByStartSet& free_by_start, const FreeBySizeSet& free_by_size) {
82 if (free_by_start.size() != free_by_size.size()) {
83 LOG(FATAL) << "Size: " << free_by_start.size() << " vs " << free_by_size.size();
84 }
85
86 // Calculate over free_by_size.
87 size_t sum1 = 0;
88 for (const auto& entry : free_by_size) {
89 sum1 += entry.second->size;
90 }
91
92 // Calculate over free_by_start.
93 size_t sum2 = 0;
94 for (const auto& entry : free_by_start) {
95 sum2 += entry.size;
96 }
97
98 if (sum1 != sum2) {
99 LOG(FATAL) << "Sum: " << sum1 << " vs " << sum2;
100 }
101 return sum1;
102 }
103
Alloc(size_t size)104 void* SwapSpace::Alloc(size_t size) {
105 MutexLock lock(Thread::Current(), lock_);
106 size = RoundUp(size, 8U);
107
108 // Check the free list for something that fits.
109 // TODO: Smarter implementation. Global biggest chunk, ...
110 SpaceChunk old_chunk;
111 auto it = free_by_start_.empty()
112 ? free_by_size_.end()
113 : free_by_size_.lower_bound(FreeBySizeEntry { size, free_by_start_.begin() });
114 if (it != free_by_size_.end()) {
115 old_chunk = *it->second;
116 RemoveChunk(&free_by_start_, &free_by_size_, it);
117 } else {
118 // Not a big enough free chunk, need to increase file size.
119 old_chunk = NewFileChunk(size);
120 }
121
122 void* ret = old_chunk.ptr;
123
124 if (old_chunk.size != size) {
125 // Insert the remainder.
126 SpaceChunk new_chunk = { old_chunk.ptr + size, old_chunk.size - size };
127 InsertChunk(&free_by_start_, &free_by_size_, new_chunk);
128 }
129
130 return ret;
131 }
132
NewFileChunk(size_t min_size)133 SpaceChunk SwapSpace::NewFileChunk(size_t min_size) {
134 #if !defined(__APPLE__)
135 size_t next_part = std::max(RoundUp(min_size, kPageSize), RoundUp(kMininumMapSize, kPageSize));
136 int result = TEMP_FAILURE_RETRY(ftruncate64(fd_, size_ + next_part));
137 if (result != 0) {
138 PLOG(FATAL) << "Unable to increase swap file.";
139 }
140 uint8_t* ptr = reinterpret_cast<uint8_t*>(
141 mmap(nullptr, next_part, PROT_READ | PROT_WRITE, MAP_SHARED, fd_, size_));
142 if (ptr == MAP_FAILED) {
143 LOG(ERROR) << "Unable to mmap new swap file chunk.";
144 LOG(ERROR) << "Current size: " << size_ << " requested: " << next_part << "/" << min_size;
145 LOG(ERROR) << "Free list:";
146 MutexLock lock(Thread::Current(), lock_);
147 DumpFreeMap(free_by_size_);
148 LOG(ERROR) << "In free list: " << CollectFree(free_by_start_, free_by_size_);
149 LOG(FATAL) << "Aborting...";
150 }
151 size_ += next_part;
152 SpaceChunk new_chunk = {ptr, next_part};
153 maps_.push_back(new_chunk);
154 return new_chunk;
155 #else
156 UNUSED(min_size, kMininumMapSize);
157 LOG(FATAL) << "No swap file support on the Mac.";
158 UNREACHABLE();
159 #endif
160 }
161
162 // TODO: Full coalescing.
Free(void * ptrV,size_t size)163 void SwapSpace::Free(void* ptrV, size_t size) {
164 MutexLock lock(Thread::Current(), lock_);
165 size = RoundUp(size, 8U);
166
167 size_t free_before = 0;
168 if (kCheckFreeMaps) {
169 free_before = CollectFree(free_by_start_, free_by_size_);
170 }
171
172 SpaceChunk chunk = { reinterpret_cast<uint8_t*>(ptrV), size };
173 auto it = free_by_start_.lower_bound(chunk);
174 if (it != free_by_start_.begin()) {
175 auto prev = it;
176 --prev;
177 CHECK_LE(prev->End(), chunk.Start());
178 if (prev->End() == chunk.Start()) {
179 // Merge *prev with this chunk.
180 chunk.size += prev->size;
181 chunk.ptr -= prev->size;
182 auto erase_pos = free_by_size_.find(FreeBySizeEntry { prev->size, prev });
183 DCHECK(erase_pos != free_by_size_.end());
184 RemoveChunk(&free_by_start_, &free_by_size_, erase_pos);
185 // "prev" is invalidated but "it" remains valid.
186 }
187 }
188 if (it != free_by_start_.end()) {
189 CHECK_LE(chunk.End(), it->Start());
190 if (chunk.End() == it->Start()) {
191 // Merge *it with this chunk.
192 chunk.size += it->size;
193 auto erase_pos = free_by_size_.find(FreeBySizeEntry { it->size, it });
194 DCHECK(erase_pos != free_by_size_.end());
195 RemoveChunk(&free_by_start_, &free_by_size_, erase_pos);
196 // "it" is invalidated but we don't need it anymore.
197 }
198 }
199 InsertChunk(&free_by_start_, &free_by_size_, chunk);
200
201 if (kCheckFreeMaps) {
202 size_t free_after = CollectFree(free_by_start_, free_by_size_);
203
204 if (free_after != free_before + size) {
205 DumpFreeMap(free_by_size_);
206 CHECK_EQ(free_after, free_before + size) << "Should be " << size << " difference from " << free_before;
207 }
208 }
209 }
210
211 } // namespace art
212