1 /*
2  * Copyright (C) 2016 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 LIBMEMUNREACHABLE_ALLOCATOR_H_
18 #define LIBMEMUNREACHABLE_ALLOCATOR_H_
19 
20 #include <atomic>
21 #include <cstddef>
22 #include <functional>
23 #include <list>
24 #include <map>
25 #include <memory>
26 #include <set>
27 #include <unordered_map>
28 #include <unordered_set>
29 #include <vector>
30 
31 namespace android {
32 
33 extern std::atomic<int> heap_count;
34 
35 class HeapImpl;
36 
37 template <typename T>
38 class Allocator;
39 
40 // Non-templated class that implements wraps HeapImpl to keep
41 // implementation out of the header file
42 class Heap {
43  public:
44   Heap();
45   ~Heap();
46 
47   // Copy constructor that does not take ownership of impl_
Heap(const Heap & other)48   Heap(const Heap& other) : impl_(other.impl_), owns_impl_(false) {}
49 
50   // Assignment disabled
51   Heap& operator=(const Heap&) = delete;
52 
53   // Allocate size bytes
54   void* allocate(size_t size);
55 
56   // Deallocate allocation returned by allocate
57   void deallocate(void*);
58 
59   bool empty();
60 
61   static void deallocate(HeapImpl* impl, void* ptr);
62 
63   // Allocate a class of type T
64   template <class T>
allocate()65   T* allocate() {
66     return reinterpret_cast<T*>(allocate(sizeof(T)));
67   }
68 
69   // Comparators, copied objects will be equal
70   bool operator==(const Heap& other) const { return impl_ == other.impl_; }
71   bool operator!=(const Heap& other) const { return !(*this == other); }
72 
73   // std::unique_ptr wrapper that allocates using allocate and deletes using
74   // deallocate
75   template <class T>
76   using unique_ptr = std::unique_ptr<T, std::function<void(void*)>>;
77 
78   template <class T, class... Args>
make_unique(Args &&...args)79   unique_ptr<T> make_unique(Args&&... args) {
80     HeapImpl* impl = impl_;
81     return unique_ptr<T>(new (allocate<T>()) T(std::forward<Args>(args)...), [impl](void* ptr) {
82       reinterpret_cast<T*>(ptr)->~T();
83       deallocate(impl, ptr);
84     });
85   }
86 
87   // std::unique_ptr wrapper that allocates using allocate and deletes using
88   // deallocate
89   template <class T>
90   using shared_ptr = std::shared_ptr<T>;
91 
92   template <class T, class... Args>
93   shared_ptr<T> make_shared(Args&&... args);
94 
95  protected:
96   HeapImpl* impl_;
97   bool owns_impl_;
98 };
99 
100 // STLAllocator implements the std allocator interface on top of a Heap
101 template <typename T>
102 class STLAllocator {
103  public:
104   using value_type = T;
~STLAllocator()105   ~STLAllocator() {}
106 
107   // Construct an STLAllocator on top of a Heap
STLAllocator(const Heap & heap)108   STLAllocator(const Heap& heap)
109       :  // NOLINT, implicit
110         heap_(heap) {}
111 
112   // Rebind an STLAllocator from an another STLAllocator
113   template <typename U>
STLAllocator(const STLAllocator<U> & other)114   STLAllocator(const STLAllocator<U>& other)
115       :  // NOLINT, implicit
116         heap_(other.heap_) {}
117 
118   STLAllocator(const STLAllocator&) = default;
119   STLAllocator<T>& operator=(const STLAllocator<T>&) = default;
120 
allocate(std::size_t n)121   T* allocate(std::size_t n) { return reinterpret_cast<T*>(heap_.allocate(n * sizeof(T))); }
122 
deallocate(T * ptr,std::size_t)123   void deallocate(T* ptr, std::size_t) { heap_.deallocate(ptr); }
124 
125   template <typename U>
126   bool operator==(const STLAllocator<U>& other) const {
127     return heap_ == other.heap_;
128   }
129   template <typename U>
130   inline bool operator!=(const STLAllocator<U>& other) const {
131     return !(this == other);
132   }
133 
134   template <typename U>
135   friend class STLAllocator;
136 
137  protected:
138   Heap heap_;
139 };
140 
141 // Allocator extends STLAllocator with some convenience methods for allocating
142 // a single object and for constructing unique_ptr and shared_ptr objects with
143 // appropriate deleters.
144 template <class T>
145 class Allocator : public STLAllocator<T> {
146  public:
~Allocator()147   ~Allocator() {}
148 
Allocator(const Heap & other)149   Allocator(const Heap& other)
150       :  // NOLINT, implicit
151         STLAllocator<T>(other) {}
152 
153   template <typename U>
Allocator(const STLAllocator<U> & other)154   Allocator(const STLAllocator<U>& other)
155       :  // NOLINT, implicit
156         STLAllocator<T>(other) {}
157 
158   Allocator(const Allocator&) = default;
159   Allocator<T>& operator=(const Allocator<T>&) = default;
160 
161   using STLAllocator<T>::allocate;
162   using STLAllocator<T>::deallocate;
163   using STLAllocator<T>::heap_;
164 
allocate()165   T* allocate() { return STLAllocator<T>::allocate(1); }
deallocate(void * ptr)166   void deallocate(void* ptr) { heap_.deallocate(ptr); }
167 
168   using shared_ptr = Heap::shared_ptr<T>;
169 
170   template <class... Args>
make_shared(Args &&...args)171   shared_ptr make_shared(Args&&... args) {
172     return heap_.template make_shared<T>(std::forward<Args>(args)...);
173   }
174 
175   using unique_ptr = Heap::unique_ptr<T>;
176 
177   template <class... Args>
make_unique(Args &&...args)178   unique_ptr make_unique(Args&&... args) {
179     return heap_.template make_unique<T>(std::forward<Args>(args)...);
180   }
181 };
182 
183 // std::unique_ptr wrapper that allocates using allocate and deletes using
184 // deallocate.  Implemented outside class definition in order to pass
185 // Allocator<T> to shared_ptr.
186 template <class T, class... Args>
make_shared(Args &&...args)187 inline Heap::shared_ptr<T> Heap::make_shared(Args&&... args) {
188   return std::allocate_shared<T, Allocator<T>, Args...>(Allocator<T>(*this),
189                                                         std::forward<Args>(args)...);
190 }
191 
192 namespace allocator {
193 
194 template <class T>
195 using vector = std::vector<T, Allocator<T>>;
196 
197 template <class T>
198 using list = std::list<T, Allocator<T>>;
199 
200 template <class Key, class T, class Compare = std::less<Key>>
201 using map = std::map<Key, T, Compare, Allocator<std::pair<const Key, T>>>;
202 
203 template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
204 using unordered_map =
205     std::unordered_map<Key, T, Hash, KeyEqual, Allocator<std::pair<const Key, T>>>;
206 
207 template <class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
208 using unordered_set = std::unordered_set<Key, Hash, KeyEqual, Allocator<Key>>;
209 
210 template <class Key, class Compare = std::less<Key>>
211 using set = std::set<Key, Compare, Allocator<Key>>;
212 
213 using string = std::basic_string<char, std::char_traits<char>, Allocator<char>>;
214 }
215 
216 }  // namespace android
217 
218 #endif
219