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     uint8_t* ptr;
49     size_t size;
50 
StartSpaceChunk51     uintptr_t Start() const {
52       return reinterpret_cast<uintptr_t>(ptr);
53     }
EndSpaceChunk54     uintptr_t End() const {
55       return reinterpret_cast<uintptr_t>(ptr) + size;
56     }
57   };
58 
59   class SortChunkByPtr {
60    public:
operator()61     bool operator()(const SpaceChunk& a, const SpaceChunk& b) const {
62       return reinterpret_cast<uintptr_t>(a.ptr) < reinterpret_cast<uintptr_t>(b.ptr);
63     }
64   };
65 
66   typedef std::set<SpaceChunk, SortChunkByPtr> FreeByStartSet;
67 
68   // Map size to an iterator to free_by_start_'s entry.
69   typedef std::pair<size_t, FreeByStartSet::const_iterator> FreeBySizeEntry;
70   struct FreeBySizeComparator {
operatorFreeBySizeComparator71     bool operator()(const FreeBySizeEntry& lhs, const FreeBySizeEntry& rhs) {
72       if (lhs.first != rhs.first) {
73         return lhs.first < rhs.first;
74       } else {
75         return lhs.second->Start() < rhs.second->Start();
76       }
77     }
78   };
79   typedef std::set<FreeBySizeEntry, FreeBySizeComparator> FreeBySizeSet;
80 
81   SpaceChunk NewFileChunk(size_t min_size) REQUIRES(lock_);
82 
83   void RemoveChunk(FreeBySizeSet::const_iterator free_by_size_pos) REQUIRES(lock_);
84   void InsertChunk(const SpaceChunk& chunk) REQUIRES(lock_);
85 
86   int fd_;
87   size_t size_;
88 
89   // NOTE: Boost.Bimap would be useful for the two following members.
90 
91   // Map start of a free chunk to its size.
92   FreeByStartSet free_by_start_ GUARDED_BY(lock_);
93   // Free chunks ordered by size.
94   FreeBySizeSet free_by_size_ GUARDED_BY(lock_);
95 
96   mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
97   DISALLOW_COPY_AND_ASSIGN(SwapSpace);
98 };
99 
100 template <typename T> class SwapAllocator;
101 
102 template <>
103 class SwapAllocator<void> {
104  public:
105   typedef void value_type;
106   typedef void* pointer;
107   typedef const void* const_pointer;
108 
109   template <typename U>
110   struct rebind {
111     typedef SwapAllocator<U> other;
112   };
113 
SwapAllocator(SwapSpace * swap_space)114   explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {}
115 
116   template <typename U>
SwapAllocator(const SwapAllocator<U> & other)117   SwapAllocator(const SwapAllocator<U>& other) : swap_space_(other.swap_space_) {}
118 
119   SwapAllocator(const SwapAllocator& other) = default;
120   SwapAllocator& operator=(const SwapAllocator& other) = default;
121   ~SwapAllocator() = default;
122 
123  private:
124   SwapSpace* swap_space_;
125 
126   template <typename U>
127   friend class SwapAllocator;
128 
129   template <typename U>
130   friend bool operator==(const SwapAllocator<U>& lhs, const SwapAllocator<U>& rhs);
131 };
132 
133 template <typename T>
134 class SwapAllocator {
135  public:
136   typedef T value_type;
137   typedef T* pointer;
138   typedef T& reference;
139   typedef const T* const_pointer;
140   typedef const T& const_reference;
141   typedef size_t size_type;
142   typedef ptrdiff_t difference_type;
143 
144   template <typename U>
145   struct rebind {
146     typedef SwapAllocator<U> other;
147   };
148 
SwapAllocator(SwapSpace * swap_space)149   explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {}
150 
151   template <typename U>
SwapAllocator(const SwapAllocator<U> & other)152   SwapAllocator(const SwapAllocator<U>& other) : swap_space_(other.swap_space_) {}
153 
154   SwapAllocator(const SwapAllocator& other) = default;
155   SwapAllocator& operator=(const SwapAllocator& other) = default;
156   ~SwapAllocator() = default;
157 
max_size()158   size_type max_size() const {
159     return static_cast<size_type>(-1) / sizeof(T);
160   }
161 
address(reference x)162   pointer address(reference x) const { return &x; }
address(const_reference x)163   const_pointer address(const_reference x) const { return &x; }
164 
165   pointer allocate(size_type n, SwapAllocator<void>::pointer hint ATTRIBUTE_UNUSED = nullptr) {
166     DCHECK_LE(n, max_size());
167     if (swap_space_ == nullptr) {
168       T* result = reinterpret_cast<T*>(malloc(n * sizeof(T)));
169       CHECK(result != nullptr || n == 0u);  // Abort if malloc() fails.
170       return result;
171     } else {
172       return reinterpret_cast<T*>(swap_space_->Alloc(n * sizeof(T)));
173     }
174   }
deallocate(pointer p,size_type n)175   void deallocate(pointer p, size_type n) {
176     if (swap_space_ == nullptr) {
177       free(p);
178     } else {
179       swap_space_->Free(p, n * sizeof(T));
180     }
181   }
182 
construct(pointer p,const_reference val)183   void construct(pointer p, const_reference val) {
184     new (static_cast<void*>(p)) value_type(val);
185   }
186   template <class U, class... Args>
construct(U * p,Args &&...args)187   void construct(U* p, Args&&... args) {
188     ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
189   }
destroy(pointer p)190   void destroy(pointer p) {
191     p->~value_type();
192   }
193 
194   inline bool operator==(SwapAllocator const& other) {
195     return swap_space_ == other.swap_space_;
196   }
197   inline bool operator!=(SwapAllocator const& other) {
198     return !operator==(other);
199   }
200 
201  private:
202   SwapSpace* swap_space_;
203 
204   template <typename U>
205   friend class SwapAllocator;
206 
207   template <typename U>
208   friend bool operator==(const SwapAllocator<U>& lhs, const SwapAllocator<U>& rhs);
209 };
210 
211 template <typename T>
212 inline bool operator==(const SwapAllocator<T>& lhs, const SwapAllocator<T>& rhs) {
213   return lhs.swap_space_ == rhs.swap_space_;
214 }
215 
216 template <typename T>
217 inline bool operator!=(const SwapAllocator<T>& lhs, const SwapAllocator<T>& rhs) {
218   return !(lhs == rhs);
219 }
220 
221 template <typename T>
222 using SwapVector = std::vector<T, SwapAllocator<T>>;
223 template <typename T, typename Comparator>
224 using SwapSet = std::set<T, Comparator, SwapAllocator<T>>;
225 
226 }  // namespace art
227 
228 #endif  // ART_COMPILER_UTILS_SWAP_SPACE_H_
229