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 #ifndef ART_COMPILER_UTILS_SWAP_SPACE_H_
18 #define ART_COMPILER_UTILS_SWAP_SPACE_H_
19 
20 #include <stddef.h>
21 #include <stdint.h>
22 #include <cstdlib>
23 #include <list>
24 #include <set>
25 #include <vector>
26 
27 #include <android-base/logging.h>
28 
29 #include "base/macros.h"
30 #include "base/mutex.h"
31 
32 namespace art {
33 
34 // An arena pool that creates arenas backed by an mmaped file.
35 class SwapSpace {
36  public:
37   SwapSpace(int fd, size_t initial_size);
38   ~SwapSpace();
39   void* Alloc(size_t size) REQUIRES(!lock_);
40   void Free(void* ptr, size_t size) REQUIRES(!lock_);
41 
GetSize()42   size_t GetSize() {
43     return size_;
44   }
45 
46  private:
47   // Chunk of space.
48   struct SpaceChunk {
49     // We need mutable members as we keep these objects in a std::set<> (providing only const
50     // access) but we modify these members while carefully preserving the std::set<> ordering.
51     mutable uint8_t* ptr;
52     mutable size_t size;
53 
StartSpaceChunk54     uintptr_t Start() const {
55       return reinterpret_cast<uintptr_t>(ptr);
56     }
EndSpaceChunk57     uintptr_t End() const {
58       return reinterpret_cast<uintptr_t>(ptr) + size;
59     }
60   };
61 
62   class SortChunkByPtr {
63    public:
operator()64     bool operator()(const SpaceChunk& a, const SpaceChunk& b) const {
65       return reinterpret_cast<uintptr_t>(a.ptr) < reinterpret_cast<uintptr_t>(b.ptr);
66     }
67   };
68 
69   typedef std::set<SpaceChunk, SortChunkByPtr> FreeByStartSet;
70 
71   // Map size to an iterator to free_by_start_'s entry.
72   struct FreeBySizeEntry {
FreeBySizeEntryFreeBySizeEntry73     FreeBySizeEntry(size_t sz, FreeByStartSet::const_iterator entry)
74         : size(sz), free_by_start_entry(entry) { }
75 
76     // We need mutable members as we keep these objects in a std::set<> (providing only const
77     // access) but we modify these members while carefully preserving the std::set<> ordering.
78     mutable size_t size;
79     mutable FreeByStartSet::const_iterator free_by_start_entry;
80   };
81   struct FreeBySizeComparator {
operatorFreeBySizeComparator82     bool operator()(const FreeBySizeEntry& lhs, const FreeBySizeEntry& rhs) const {
83       if (lhs.size != rhs.size) {
84         return lhs.size < rhs.size;
85       } else {
86         return lhs.free_by_start_entry->Start() < rhs.free_by_start_entry->Start();
87       }
88     }
89   };
90   typedef std::set<FreeBySizeEntry, FreeBySizeComparator> FreeBySizeSet;
91 
92   SpaceChunk NewFileChunk(size_t min_size) REQUIRES(lock_);
93 
94   void RemoveChunk(FreeBySizeSet::const_iterator free_by_size_pos) REQUIRES(lock_);
95   void InsertChunk(const SpaceChunk& chunk) REQUIRES(lock_);
96 
97   int fd_;
98   size_t size_;
99 
100   // NOTE: Boost.Bimap would be useful for the two following members.
101 
102   // Map start of a free chunk to its size.
103   FreeByStartSet free_by_start_ GUARDED_BY(lock_);
104   // Free chunks ordered by size.
105   FreeBySizeSet free_by_size_ GUARDED_BY(lock_);
106 
107   mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
108   DISALLOW_COPY_AND_ASSIGN(SwapSpace);
109 };
110 
111 template <typename T> class SwapAllocator;
112 
113 template <>
114 class SwapAllocator<void> {
115  public:
116   typedef void value_type;
117   typedef void* pointer;
118   typedef const void* const_pointer;
119 
120   template <typename U>
121   struct rebind {
122     typedef SwapAllocator<U> other;
123   };
124 
SwapAllocator(SwapSpace * swap_space)125   explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {}
126 
127   template <typename U>
SwapAllocator(const SwapAllocator<U> & other)128   SwapAllocator(const SwapAllocator<U>& other)
129       : swap_space_(other.swap_space_) {}
130 
131   SwapAllocator(const SwapAllocator& other) = default;
132   SwapAllocator& operator=(const SwapAllocator& other) = default;
133   ~SwapAllocator() = default;
134 
135  private:
136   SwapSpace* swap_space_;
137 
138   template <typename U>
139   friend class SwapAllocator;
140 
141   template <typename U>
142   friend bool operator==(const SwapAllocator<U>& lhs, const SwapAllocator<U>& rhs);
143 };
144 
145 template <typename T>
146 class SwapAllocator {
147  public:
148   typedef T value_type;
149   typedef T* pointer;
150   typedef T& reference;
151   typedef const T* const_pointer;
152   typedef const T& const_reference;
153   typedef size_t size_type;
154   typedef ptrdiff_t difference_type;
155 
156   template <typename U>
157   struct rebind {
158     typedef SwapAllocator<U> other;
159   };
160 
SwapAllocator(SwapSpace * swap_space)161   explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {}
162 
163   template <typename U>
SwapAllocator(const SwapAllocator<U> & other)164   SwapAllocator(const SwapAllocator<U>& other)
165       : swap_space_(other.swap_space_) {}
166 
167   SwapAllocator(const SwapAllocator& other) = default;
168   SwapAllocator& operator=(const SwapAllocator& other) = default;
169   ~SwapAllocator() = default;
170 
max_size()171   size_type max_size() const {
172     return static_cast<size_type>(-1) / sizeof(T);
173   }
174 
address(reference x)175   pointer address(reference x) const { return &x; }
address(const_reference x)176   const_pointer address(const_reference x) const { return &x; }
177 
178   pointer allocate(size_type n, SwapAllocator<void>::pointer hint ATTRIBUTE_UNUSED = nullptr) {
179     DCHECK_LE(n, max_size());
180     if (swap_space_ == nullptr) {
181       T* result = reinterpret_cast<T*>(malloc(n * sizeof(T)));
182       CHECK(result != nullptr || n == 0u);  // Abort if malloc() fails.
183       return result;
184     } else {
185       return reinterpret_cast<T*>(swap_space_->Alloc(n * sizeof(T)));
186     }
187   }
deallocate(pointer p,size_type n)188   void deallocate(pointer p, size_type n) {
189     if (swap_space_ == nullptr) {
190       free(p);
191     } else {
192       swap_space_->Free(p, n * sizeof(T));
193     }
194   }
195 
construct(pointer p,const_reference val)196   void construct(pointer p, const_reference val) {
197     new (static_cast<void*>(p)) value_type(val);
198   }
199   template <class U, class... Args>
construct(U * p,Args &&...args)200   void construct(U* p, Args&&... args) {
201     ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
202   }
destroy(pointer p)203   void destroy(pointer p) {
204     p->~value_type();
205   }
206 
207   inline bool operator==(SwapAllocator const& other) {
208     return swap_space_ == other.swap_space_;
209   }
210   inline bool operator!=(SwapAllocator const& other) {
211     return !operator==(other);
212   }
213 
214  private:
215   SwapSpace* swap_space_;
216 
217   template <typename U>
218   friend class SwapAllocator;
219 
220   template <typename U>
221   friend bool operator==(const SwapAllocator<U>& lhs, const SwapAllocator<U>& rhs);
222 };
223 
224 template <typename T>
225 inline bool operator==(const SwapAllocator<T>& lhs, const SwapAllocator<T>& rhs) {
226   return lhs.swap_space_ == rhs.swap_space_;
227 }
228 
229 template <typename T>
230 inline bool operator!=(const SwapAllocator<T>& lhs, const SwapAllocator<T>& rhs) {
231   return !(lhs == rhs);
232 }
233 
234 template <typename T>
235 using SwapVector = std::vector<T, SwapAllocator<T>>;
236 template <typename T, typename Comparator>
237 using SwapSet = std::set<T, Comparator, SwapAllocator<T>>;
238 
239 }  // namespace art
240 
241 #endif  // ART_COMPILER_UTILS_SWAP_SPACE_H_
242