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