ART: Swap-space in the compiler
Introduce a swap-space and corresponding allocator to transparently
switch native allocations to memory backed by a file.
Bug: 18596910
(cherry picked from commit 62746d8d9c4400e4764f162b22bfb1a32be287a9)
Change-Id: I131448f3907115054a592af73db86d2b9257ea33
diff --git a/compiler/utils/array_ref.h b/compiler/utils/array_ref.h
index 1a7f2e8..b1b0ee5 100644
--- a/compiler/utils/array_ref.h
+++ b/compiler/utils/array_ref.h
@@ -84,7 +84,7 @@
template <typename U, typename Alloc>
ArrayRef(const std::vector<U, Alloc>& v,
- typename std::enable_if<std::is_same<T, const U>::value, tag>::tag
+ typename std::enable_if<std::is_same<T, const U>::value, tag>::type
t ATTRIBUTE_UNUSED = tag())
: array_(v.data()), size_(v.size()) {
}
diff --git a/compiler/utils/assembler.h b/compiler/utils/assembler.h
index 67711e3..134dda4 100644
--- a/compiler/utils/assembler.h
+++ b/compiler/utils/assembler.h
@@ -502,6 +502,8 @@
virtual void InitializeFrameDescriptionEntry() {}
virtual void FinalizeFrameDescriptionEntry() {}
+ // Give a vector containing FDE data, or null if not used. Note: the assembler must take care
+ // of handling the lifecycle.
virtual std::vector<uint8_t>* GetFrameDescriptionEntry() { return nullptr; }
virtual ~Assembler() {}
diff --git a/compiler/utils/dedupe_set.h b/compiler/utils/dedupe_set.h
index 4c52174..b062a2a 100644
--- a/compiler/utils/dedupe_set.h
+++ b/compiler/utils/dedupe_set.h
@@ -17,50 +17,89 @@
#ifndef ART_COMPILER_UTILS_DEDUPE_SET_H_
#define ART_COMPILER_UTILS_DEDUPE_SET_H_
+#include <algorithm>
+#include <inttypes.h>
+#include <memory>
#include <set>
#include <string>
#include "base/mutex.h"
#include "base/stl_util.h"
#include "base/stringprintf.h"
+#include "utils/swap_space.h"
namespace art {
// A set of Keys that support a HashFunc returning HashType. Used to find duplicates of Key in the
// Add method. The data-structure is thread-safe through the use of internal locks, it also
// supports the lock being sharded.
-template <typename Key, typename HashType, typename HashFunc, HashType kShard = 1>
+template <typename InKey, typename StoreKey, typename HashType, typename HashFunc,
+ HashType kShard = 1>
class DedupeSet {
- typedef std::pair<HashType, Key*> HashedKey;
+ typedef std::pair<HashType, const InKey*> HashedInKey;
+ struct HashedKey {
+ StoreKey* store_ptr;
+ union {
+ HashType store_hash; // Valid if store_ptr != nullptr.
+ const HashedInKey* in_key; // Valid if store_ptr == nullptr.
+ };
+ };
class Comparator {
public:
bool operator()(const HashedKey& a, const HashedKey& b) const {
- if (a.first != b.first) {
- return a.first < b.first;
+ HashType a_hash = (a.store_ptr != nullptr) ? a.store_hash : a.in_key->first;
+ HashType b_hash = (b.store_ptr != nullptr) ? b.store_hash : b.in_key->first;
+ if (a_hash != b_hash) {
+ return a_hash < b_hash;
+ }
+ if (a.store_ptr != nullptr && b.store_ptr != nullptr) {
+ return std::lexicographical_compare(a.store_ptr->begin(), a.store_ptr->end(),
+ b.store_ptr->begin(), b.store_ptr->end());
+ } else if (a.store_ptr != nullptr && b.store_ptr == nullptr) {
+ return std::lexicographical_compare(a.store_ptr->begin(), a.store_ptr->end(),
+ b.in_key->second->begin(), b.in_key->second->end());
+ } else if (a.store_ptr == nullptr && b.store_ptr != nullptr) {
+ return std::lexicographical_compare(a.in_key->second->begin(), a.in_key->second->end(),
+ b.store_ptr->begin(), b.store_ptr->end());
} else {
- return *a.second < *b.second;
+ return std::lexicographical_compare(a.in_key->second->begin(), a.in_key->second->end(),
+ b.in_key->second->begin(), b.in_key->second->end());
}
}
};
public:
- Key* Add(Thread* self, const Key& key) {
+ StoreKey* Add(Thread* self, const InKey& key) {
+ uint64_t hash_start;
+ if (kIsDebugBuild) {
+ hash_start = NanoTime();
+ }
HashType raw_hash = HashFunc()(key);
+ if (kIsDebugBuild) {
+ uint64_t hash_end = NanoTime();
+ hash_time_ += hash_end - hash_start;
+ }
HashType shard_hash = raw_hash / kShard;
HashType shard_bin = raw_hash % kShard;
- HashedKey hashed_key(shard_hash, const_cast<Key*>(&key));
+ HashedInKey hashed_in_key(shard_hash, &key);
+ HashedKey hashed_key;
+ hashed_key.store_ptr = nullptr;
+ hashed_key.in_key = &hashed_in_key;
MutexLock lock(self, *lock_[shard_bin]);
auto it = keys_[shard_bin].find(hashed_key);
if (it != keys_[shard_bin].end()) {
- return it->second;
+ DCHECK(it->store_ptr != nullptr);
+ return it->store_ptr;
}
- hashed_key.second = new Key(key);
+ hashed_key.store_ptr = CreateStoreKey(key);
+ hashed_key.store_hash = shard_hash;
keys_[shard_bin].insert(hashed_key);
- return hashed_key.second;
+ return hashed_key.store_ptr;
}
- explicit DedupeSet(const char* set_name) {
+ explicit DedupeSet(const char* set_name, SwapAllocator<void>& alloc)
+ : allocator_(alloc), hash_time_(0) {
for (HashType i = 0; i < kShard; ++i) {
std::ostringstream oss;
oss << set_name << " lock " << i;
@@ -70,15 +109,59 @@
}
~DedupeSet() {
- for (HashType i = 0; i < kShard; ++i) {
- STLDeleteValues(&keys_[i]);
+ // Have to manually free all pointers.
+ for (auto& shard : keys_) {
+ for (const auto& hashed_key : shard) {
+ DCHECK(hashed_key.store_ptr != nullptr);
+ DeleteStoreKey(hashed_key.store_ptr);
+ }
}
}
+ std::string DumpStats() const {
+ size_t collision_sum = 0;
+ size_t collision_max = 0;
+ for (HashType shard = 0; shard < kShard; ++shard) {
+ HashType last_hash = 0;
+ size_t collision_cur_max = 0;
+ for (const HashedKey& key : keys_[shard]) {
+ DCHECK(key.store_ptr != nullptr);
+ if (key.store_hash == last_hash) {
+ collision_cur_max++;
+ if (collision_cur_max > 1) {
+ collision_sum++;
+ if (collision_cur_max > collision_max) {
+ collision_max = collision_cur_max;
+ }
+ }
+ } else {
+ collision_cur_max = 1;
+ last_hash = key.store_hash;
+ }
+ }
+ }
+ return StringPrintf("%zu collisions, %zu max bucket size, %" PRIu64 " ns hash time",
+ collision_sum, collision_max, hash_time_);
+ }
+
private:
+ StoreKey* CreateStoreKey(const InKey& key) {
+ StoreKey* ret = allocator_.allocate(1);
+ allocator_.construct(ret, key.begin(), key.end(), allocator_);
+ return ret;
+ }
+
+ void DeleteStoreKey(StoreKey* key) {
+ SwapAllocator<StoreKey> alloc(allocator_);
+ alloc.destroy(key);
+ alloc.deallocate(key, 1);
+ }
+
std::string lock_name_[kShard];
std::unique_ptr<Mutex> lock_[kShard];
std::set<HashedKey, Comparator> keys_[kShard];
+ SwapAllocator<StoreKey> allocator_;
+ uint64_t hash_time_;
DISALLOW_COPY_AND_ASSIGN(DedupeSet);
};
diff --git a/compiler/utils/dedupe_set_test.cc b/compiler/utils/dedupe_set_test.cc
index 8abe6de..637964e 100644
--- a/compiler/utils/dedupe_set_test.cc
+++ b/compiler/utils/dedupe_set_test.cc
@@ -15,6 +15,10 @@
*/
#include "dedupe_set.h"
+
+#include <algorithm>
+#include <cstdio>
+
#include "gtest/gtest.h"
#include "thread-inl.h"
@@ -35,19 +39,22 @@
TEST(DedupeSetTest, Test) {
Thread* self = Thread::Current();
typedef std::vector<uint8_t> ByteArray;
- DedupeSet<ByteArray, size_t, DedupeHashFunc> deduplicator("test");
- ByteArray* array1;
+ SwapAllocator<void> swap(nullptr);
+ DedupeSet<ByteArray, SwapVector<uint8_t>, size_t, DedupeHashFunc> deduplicator("test", swap);
+ SwapVector<uint8_t>* array1;
{
ByteArray test1;
test1.push_back(10);
test1.push_back(20);
test1.push_back(30);
test1.push_back(45);
+
array1 = deduplicator.Add(self, test1);
- ASSERT_EQ(test1, *array1);
+ ASSERT_NE(array1, nullptr);
+ ASSERT_TRUE(std::equal(test1.begin(), test1.end(), array1->begin()));
}
- ByteArray* array2;
+ SwapVector<uint8_t>* array2;
{
ByteArray test1;
test1.push_back(10);
@@ -56,10 +63,10 @@
test1.push_back(45);
array2 = deduplicator.Add(self, test1);
ASSERT_EQ(array2, array1);
- ASSERT_EQ(test1, *array2);
+ ASSERT_TRUE(std::equal(test1.begin(), test1.end(), array2->begin()));
}
- ByteArray* array3;
+ SwapVector<uint8_t>* array3;
{
ByteArray test1;
test1.push_back(10);
@@ -67,8 +74,8 @@
test1.push_back(30);
test1.push_back(47);
array3 = deduplicator.Add(self, test1);
- ASSERT_NE(array3, &test1);
- ASSERT_EQ(test1, *array3);
+ ASSERT_NE(array3, nullptr);
+ ASSERT_TRUE(std::equal(test1.begin(), test1.end(), array3->begin()));
}
}
diff --git a/compiler/utils/swap_space.cc b/compiler/utils/swap_space.cc
new file mode 100644
index 0000000..19338c0
--- /dev/null
+++ b/compiler/utils/swap_space.cc
@@ -0,0 +1,205 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "swap_space.h"
+
+#include <algorithm>
+#include <numeric>
+
+#include "base/logging.h"
+#include "base/macros.h"
+#include "base/mutex.h"
+#include "thread-inl.h"
+
+namespace art {
+
+// The chunk size by which the swap file is increased and mapped.
+static constexpr size_t kMininumMapSize = 16 * MB;
+
+static constexpr bool kCheckFreeMaps = false;
+
+template <typename FreeBySizeSet>
+static void DumpFreeMap(const FreeBySizeSet& free_by_size) {
+ size_t last_size = static_cast<size_t>(-1);
+ for (const auto& entry : free_by_size) {
+ if (last_size != entry.first) {
+ last_size = entry.first;
+ LOG(INFO) << "Size " << last_size;
+ }
+ LOG(INFO) << " 0x" << std::hex << entry.second->Start()
+ << " size=" << std::dec << entry.second->size;
+ }
+}
+
+template <typename FreeByStartSet, typename FreeBySizeSet>
+static void RemoveChunk(FreeByStartSet* free_by_start,
+ FreeBySizeSet* free_by_size,
+ typename FreeBySizeSet::const_iterator free_by_size_pos) {
+ auto free_by_start_pos = free_by_size_pos->second;
+ free_by_size->erase(free_by_size_pos);
+ free_by_start->erase(free_by_start_pos);
+}
+
+template <typename FreeByStartSet, typename FreeBySizeSet>
+static void InsertChunk(FreeByStartSet* free_by_start,
+ FreeBySizeSet* free_by_size,
+ const SpaceChunk& chunk) {
+ DCHECK_NE(chunk.size, 0u);
+ auto insert_result = free_by_start->insert(chunk);
+ DCHECK(insert_result.second);
+ free_by_size->emplace(chunk.size, insert_result.first);
+}
+
+SwapSpace::SwapSpace(int fd, size_t initial_size)
+ : fd_(fd),
+ size_(0),
+ lock_("SwapSpace lock", static_cast<LockLevel>(LockLevel::kDefaultMutexLevel - 1)) {
+ // Assume that the file is unlinked.
+
+ InsertChunk(&free_by_start_, &free_by_size_, NewFileChunk(initial_size));
+}
+
+SwapSpace::~SwapSpace() {
+ // All arenas are backed by the same file. Just close the descriptor.
+ close(fd_);
+}
+
+template <typename FreeByStartSet, typename FreeBySizeSet>
+static size_t CollectFree(const FreeByStartSet& free_by_start, const FreeBySizeSet& free_by_size) {
+ if (free_by_start.size() != free_by_size.size()) {
+ LOG(FATAL) << "Size: " << free_by_start.size() << " vs " << free_by_size.size();
+ }
+
+ // Calculate over free_by_size.
+ size_t sum1 = 0;
+ for (const auto& entry : free_by_size) {
+ sum1 += entry.second->size;
+ }
+
+ // Calculate over free_by_start.
+ size_t sum2 = 0;
+ for (const auto& entry : free_by_start) {
+ sum2 += entry.size;
+ }
+
+ if (sum1 != sum2) {
+ LOG(FATAL) << "Sum: " << sum1 << " vs " << sum2;
+ }
+ return sum1;
+}
+
+void* SwapSpace::Alloc(size_t size) {
+ MutexLock lock(Thread::Current(), lock_);
+ size = RoundUp(size, 8U);
+
+ // Check the free list for something that fits.
+ // TODO: Smarter implementation. Global biggest chunk, ...
+ SpaceChunk old_chunk;
+ auto it = free_by_start_.empty()
+ ? free_by_size_.end()
+ : free_by_size_.lower_bound(FreeBySizeEntry { size, free_by_start_.begin() });
+ if (it != free_by_size_.end()) {
+ old_chunk = *it->second;
+ RemoveChunk(&free_by_start_, &free_by_size_, it);
+ } else {
+ // Not a big enough free chunk, need to increase file size.
+ old_chunk = NewFileChunk(size);
+ }
+
+ void* ret = old_chunk.ptr;
+
+ if (old_chunk.size != size) {
+ // Insert the remainder.
+ SpaceChunk new_chunk = { old_chunk.ptr + size, old_chunk.size - size };
+ InsertChunk(&free_by_start_, &free_by_size_, new_chunk);
+ }
+
+ return ret;
+}
+
+SpaceChunk SwapSpace::NewFileChunk(size_t min_size) {
+ size_t next_part = std::max(RoundUp(min_size, kPageSize), RoundUp(kMininumMapSize, kPageSize));
+ int result = TEMP_FAILURE_RETRY(ftruncate64(fd_, size_ + next_part));
+ if (result != 0) {
+ PLOG(FATAL) << "Unable to increase swap file.";
+ }
+ uint8_t* ptr = reinterpret_cast<uint8_t*>(
+ mmap(nullptr, next_part, PROT_READ | PROT_WRITE, MAP_SHARED, fd_, size_));
+ if (ptr == MAP_FAILED) {
+ LOG(ERROR) << "Unable to mmap new swap file chunk.";
+ LOG(ERROR) << "Current size: " << size_ << " requested: " << next_part << "/" << min_size;
+ LOG(ERROR) << "Free list:";
+ MutexLock lock(Thread::Current(), lock_);
+ DumpFreeMap(free_by_size_);
+ LOG(ERROR) << "In free list: " << CollectFree(free_by_start_, free_by_size_);
+ LOG(FATAL) << "Aborting...";
+ }
+ size_ += next_part;
+ SpaceChunk new_chunk = {ptr, next_part};
+ maps_.push_back(new_chunk);
+ return new_chunk;
+}
+
+// TODO: Full coalescing.
+void SwapSpace::Free(void* ptrV, size_t size) {
+ MutexLock lock(Thread::Current(), lock_);
+ size = RoundUp(size, 8U);
+
+ size_t free_before = 0;
+ if (kCheckFreeMaps) {
+ free_before = CollectFree(free_by_start_, free_by_size_);
+ }
+
+ SpaceChunk chunk = { reinterpret_cast<uint8_t*>(ptrV), size };
+ auto it = free_by_start_.lower_bound(chunk);
+ if (it != free_by_start_.begin()) {
+ auto prev = it;
+ --prev;
+ CHECK_LE(prev->End(), chunk.Start());
+ if (prev->End() == chunk.Start()) {
+ // Merge *prev with this chunk.
+ chunk.size += prev->size;
+ chunk.ptr -= prev->size;
+ auto erase_pos = free_by_size_.find(FreeBySizeEntry { prev->size, prev });
+ DCHECK(erase_pos != free_by_size_.end());
+ RemoveChunk(&free_by_start_, &free_by_size_, erase_pos);
+ // "prev" is invalidated but "it" remains valid.
+ }
+ }
+ if (it != free_by_start_.end()) {
+ CHECK_LE(chunk.End(), it->Start());
+ if (chunk.End() == it->Start()) {
+ // Merge *it with this chunk.
+ chunk.size += it->size;
+ auto erase_pos = free_by_size_.find(FreeBySizeEntry { it->size, it });
+ DCHECK(erase_pos != free_by_size_.end());
+ RemoveChunk(&free_by_start_, &free_by_size_, erase_pos);
+ // "it" is invalidated but we don't need it anymore.
+ }
+ }
+ InsertChunk(&free_by_start_, &free_by_size_, chunk);
+
+ if (kCheckFreeMaps) {
+ size_t free_after = CollectFree(free_by_start_, free_by_size_);
+
+ if (free_after != free_before + size) {
+ DumpFreeMap(free_by_size_);
+ CHECK_EQ(free_after, free_before + size) << "Should be " << size << " difference from " << free_before;
+ }
+ }
+}
+
+} // namespace art
diff --git a/compiler/utils/swap_space.h b/compiler/utils/swap_space.h
new file mode 100644
index 0000000..2d0d77a
--- /dev/null
+++ b/compiler/utils/swap_space.h
@@ -0,0 +1,212 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_UTILS_SWAP_SPACE_H_
+#define ART_COMPILER_UTILS_SWAP_SPACE_H_
+
+#include <cstdlib>
+#include <list>
+#include <set>
+#include <stdint.h>
+#include <stddef.h>
+
+#include "base/logging.h"
+#include "base/macros.h"
+#include "base/mutex.h"
+#include "mem_map.h"
+#include "utils.h"
+#include "utils/debug_stack.h"
+
+namespace art {
+
+// Chunk of space.
+struct SpaceChunk {
+ uint8_t* ptr;
+ size_t size;
+
+ uintptr_t Start() const {
+ return reinterpret_cast<uintptr_t>(ptr);
+ }
+ uintptr_t End() const {
+ return reinterpret_cast<uintptr_t>(ptr) + size;
+ }
+};
+
+inline bool operator==(const SpaceChunk& lhs, const SpaceChunk& rhs) {
+ return (lhs.size == rhs.size) && (lhs.ptr == rhs.ptr);
+}
+
+class SortChunkByPtr {
+ public:
+ bool operator()(const SpaceChunk& a, const SpaceChunk& b) const {
+ return reinterpret_cast<uintptr_t>(a.ptr) < reinterpret_cast<uintptr_t>(b.ptr);
+ }
+};
+
+// An arena pool that creates arenas backed by an mmaped file.
+class SwapSpace {
+ public:
+ SwapSpace(int fd, size_t initial_size);
+ ~SwapSpace();
+ void* Alloc(size_t size) LOCKS_EXCLUDED(lock_);
+ void Free(void* ptr, size_t size) LOCKS_EXCLUDED(lock_);
+
+ size_t GetSize() {
+ return size_;
+ }
+
+ private:
+ SpaceChunk NewFileChunk(size_t min_size);
+
+ int fd_;
+ size_t size_;
+ std::list<SpaceChunk> maps_;
+
+ // NOTE: Boost.Bimap would be useful for the two following members.
+
+ // Map start of a free chunk to its size.
+ typedef std::set<SpaceChunk, SortChunkByPtr> FreeByStartSet;
+ FreeByStartSet free_by_start_ GUARDED_BY(lock_);
+
+ // Map size to an iterator to free_by_start_'s entry.
+ typedef std::pair<size_t, FreeByStartSet::const_iterator> FreeBySizeEntry;
+ struct FreeBySizeComparator {
+ bool operator()(const FreeBySizeEntry& lhs, const FreeBySizeEntry& rhs) {
+ if (lhs.first != rhs.first) {
+ return lhs.first < rhs.first;
+ } else {
+ return lhs.second->Start() < rhs.second->Start();
+ }
+ }
+ };
+ typedef std::set<FreeBySizeEntry, FreeBySizeComparator> FreeBySizeSet;
+ FreeBySizeSet free_by_size_ GUARDED_BY(lock_);
+
+ mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
+ DISALLOW_COPY_AND_ASSIGN(SwapSpace);
+};
+
+template <typename T> class SwapAllocator;
+
+template <>
+class SwapAllocator<void> {
+ public:
+ typedef void value_type;
+ typedef void* pointer;
+ typedef const void* const_pointer;
+
+ template <typename U>
+ struct rebind {
+ typedef SwapAllocator<U> other;
+ };
+
+ explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {}
+
+ template <typename U>
+ SwapAllocator(const SwapAllocator<U>& other) : swap_space_(other.swap_space_) {}
+
+ SwapAllocator(const SwapAllocator& other) = default;
+ SwapAllocator& operator=(const SwapAllocator& other) = default;
+ ~SwapAllocator() = default;
+
+ private:
+ SwapSpace* swap_space_;
+
+ template <typename U>
+ friend class SwapAllocator;
+};
+
+template <typename T>
+class SwapAllocator {
+ public:
+ typedef T value_type;
+ typedef T* pointer;
+ typedef T& reference;
+ typedef const T* const_pointer;
+ typedef const T& const_reference;
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+
+ template <typename U>
+ struct rebind {
+ typedef SwapAllocator<U> other;
+ };
+
+ explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {}
+
+ template <typename U>
+ SwapAllocator(const SwapAllocator<U>& other) : swap_space_(other.swap_space_) {}
+
+ SwapAllocator(const SwapAllocator& other) = default;
+ SwapAllocator& operator=(const SwapAllocator& other) = default;
+ ~SwapAllocator() = default;
+
+ size_type max_size() const {
+ return static_cast<size_type>(-1) / sizeof(T);
+ }
+
+ pointer address(reference x) const { return &x; }
+ const_pointer address(const_reference x) const { return &x; }
+
+ pointer allocate(size_type n, SwapAllocator<void>::pointer hint ATTRIBUTE_UNUSED = nullptr) {
+ DCHECK_LE(n, max_size());
+ if (swap_space_ == nullptr) {
+ return reinterpret_cast<T*>(malloc(n * sizeof(T)));
+ } else {
+ return reinterpret_cast<T*>(swap_space_->Alloc(n * sizeof(T)));
+ }
+ }
+ void deallocate(pointer p, size_type n) {
+ if (swap_space_ == nullptr) {
+ free(p);
+ } else {
+ swap_space_->Free(p, n * sizeof(T));
+ }
+ }
+
+ void construct(pointer p, const_reference val) {
+ new (static_cast<void*>(p)) value_type(val);
+ }
+ template <class U, class... Args>
+ void construct(U* p, Args&&... args) {
+ ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
+ }
+ void destroy(pointer p) {
+ p->~value_type();
+ }
+
+ inline bool operator==(SwapAllocator const& other) {
+ return swap_space_ == other.swap_space_;
+ }
+ inline bool operator!=(SwapAllocator const& other) {
+ return !operator==(other);
+ }
+
+ private:
+ SwapSpace* swap_space_;
+
+ template <typename U>
+ friend class SwapAllocator;
+};
+
+template <typename T>
+using SwapVector = std::vector<T, SwapAllocator<T>>;
+template <typename T, typename Comparator>
+using SwapSet = std::set<T, Comparator, SwapAllocator<T>>;
+
+} // namespace art
+
+#endif // ART_COMPILER_UTILS_SWAP_SPACE_H_
diff --git a/compiler/utils/swap_space_test.cc b/compiler/utils/swap_space_test.cc
new file mode 100644
index 0000000..bf50ac3
--- /dev/null
+++ b/compiler/utils/swap_space_test.cc
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "utils/swap_space.h"
+
+#include <cstdio>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include "gtest/gtest.h"
+
+#include "base/unix_file/fd_file.h"
+#include "common_runtime_test.h"
+#include "os.h"
+
+namespace art {
+
+class SwapSpaceTest : public CommonRuntimeTest {
+};
+
+static void SwapTest(bool use_file) {
+ ScratchFile scratch;
+ int fd = scratch.GetFd();
+ unlink(scratch.GetFilename().c_str());
+
+ SwapSpace pool(fd, 1 * MB);
+ SwapAllocator<void> alloc(use_file ? &pool : nullptr);
+
+ SwapVector<int32_t> v(alloc);
+ v.reserve(1000000);
+ for (int32_t i = 0; i < 1000000; ++i) {
+ v.push_back(i);
+ EXPECT_EQ(i, v[i]);
+ }
+
+ SwapVector<int32_t> v2(alloc);
+ v2.reserve(1000000);
+ for (int32_t i = 0; i < 1000000; ++i) {
+ v2.push_back(i);
+ EXPECT_EQ(i, v2[i]);
+ }
+
+ SwapVector<int32_t> v3(alloc);
+ v3.reserve(500000);
+ for (int32_t i = 0; i < 1000000; ++i) {
+ v3.push_back(i);
+ EXPECT_EQ(i, v2[i]);
+ }
+
+ // Verify contents.
+ for (int32_t i = 0; i < 1000000; ++i) {
+ EXPECT_EQ(i, v[i]);
+ EXPECT_EQ(i, v2[i]);
+ EXPECT_EQ(i, v3[i]);
+ }
+
+ scratch.Close();
+}
+
+TEST_F(SwapSpaceTest, Memory) {
+ SwapTest(false);
+}
+
+TEST_F(SwapSpaceTest, Swap) {
+ SwapTest(true);
+}
+
+} // namespace art