1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef SUPPORT_CONTROLLED_ALLOCATORS_H
10 #define SUPPORT_CONTROLLED_ALLOCATORS_H
11 
12 #include <memory>
13 #include <type_traits>
14 #include <cstddef>
15 #include <cstdlib>
16 #include <cstring>
17 #include <cstdint>
18 #include <cassert>
19 #include "test_macros.h"
20 #include "type_id.h"
21 
22 #if TEST_STD_VER < 11
23 #error This header requires C++11 or greater
24 #endif
25 
26 struct AllocController;
27     // 'AllocController' is a concrete type that instruments and controls the
28     // behavior of test allocators.
29 
30 template <class T, size_t ID = 0>
31 class CountingAllocator;
32     // 'CountingAllocator' is an basic implementation of the 'Allocator'
33     // requirements that use the 'AllocController' interface.
34 
35 template <class T>
36 class MinAlignAllocator;
37     // 'MinAlignAllocator' is an instrumented test type which implements the
38     // 'Allocator' requirements. 'MinAlignAllocator' ensures that it *never*
39     // returns a pointer to over-aligned storage. For example
40     // 'MinAlignPointer<char>{}.allocate(...)' will never a 2-byte aligned
41     // pointer.
42 
43 template <class T>
44 class NullAllocator;
45     // 'NullAllocator' is an instrumented test type which implements the
46     // 'Allocator' requirements except that 'allocator' and 'deallocate' are
47     // nops.
48 
49 
50 #define DISALLOW_COPY(Type) \
51   Type(Type const&) = delete; \
52   Type& operator=(Type const&) = delete
53 
54 constexpr std::size_t MaxAlignV = alignof(std::max_align_t);
55 
56 struct TestException {};
57 
58 struct AllocController {
59     int copy_constructed = 0;
60     int move_constructed = 0;
61 
62     int alive = 0;
63     int alloc_count = 0;
64     int dealloc_count = 0;
65     int is_equal_count = 0;
66 
67     std::size_t alive_size;
68     std::size_t allocated_size;
69     std::size_t deallocated_size;
70 
71     std::size_t last_size = 0;
72     std::size_t last_align = 0;
73     void * last_pointer = 0;
74 
75     std::size_t last_alloc_size = 0;
76     std::size_t last_alloc_align = 0;
77     void * last_alloc_pointer = nullptr;
78 
79     std::size_t last_dealloc_size = 0;
80     std::size_t last_dealloc_align = 0;
81     void * last_dealloc_pointer = nullptr;
82 
83     bool throw_on_alloc = false;
84 
85     int construct_called = 0;
86     void *last_construct_pointer = nullptr;
87     TypeID const* last_construct_alloc = nullptr;
88     TypeID const* last_construct_type = nullptr;
89     TypeID const* last_construct_args = nullptr;
90 
91     int destroy_called = 0;
92     void *last_destroy_pointer = nullptr;
93     TypeID const* last_destroy_alloc = nullptr;
94     TypeID const* last_destroy_type = nullptr;
95 
96     AllocController() = default;
97 
countAllocAllocController98     void countAlloc(void* p, size_t s, size_t a) {
99         ++alive;
100         ++alloc_count;
101         alive_size += s;
102         allocated_size += s;
103         last_pointer = last_alloc_pointer = p;
104         last_size = last_alloc_size = s;
105         last_align = last_alloc_align = a;
106     }
107 
countDeallocAllocController108     void countDealloc(void* p, size_t s, size_t a) {
109         --alive;
110         ++dealloc_count;
111         alive_size -= s;
112         deallocated_size += s;
113         last_pointer = last_dealloc_pointer = p;
114         last_size = last_dealloc_size = s;
115         last_align = last_dealloc_align = a;
116     }
117 
118     template <class ...Args, class Alloc, class Tp>
countConstructAllocController119     void countConstruct(Alloc const&, Tp *p) {
120       ++construct_called;
121       last_construct_pointer = p;
122       last_construct_alloc = &makeTypeID<Alloc>();
123       last_construct_type = &makeTypeID<Tp>();
124       last_construct_args = &makeArgumentID<Args...>();
125     }
126 
127     template <class Alloc, class Tp>
countDestroyAllocController128     void countDestroy(Alloc const&, Tp *p) {
129       ++destroy_called;
130       last_destroy_alloc = &makeTypeID<Alloc>();
131       last_destroy_type = &makeTypeID<Tp>();
132       last_destroy_pointer = p;
133     }
134 
resetAllocController135     void reset() { std::memset(this, 0, sizeof(*this)); }
resetConstructDestroyAllocController136     void resetConstructDestroy() {
137       construct_called = 0;
138       last_construct_pointer = nullptr;
139       last_construct_alloc = last_construct_args = last_construct_type = nullptr;
140       destroy_called = 0;
141       last_destroy_alloc = nullptr;
142       last_destroy_pointer = nullptr;
143     }
144 public:
checkAllocAllocController145     bool checkAlloc(void* p, size_t s, size_t a) const {
146         return p == last_alloc_pointer &&
147                s == last_alloc_size &&
148                a == last_alloc_align;
149     }
150 
checkAllocAllocController151     bool checkAlloc(void* p, size_t s) const {
152         return p == last_alloc_pointer &&
153                s == last_alloc_size;
154     }
155 
checkAllocAtLeastAllocController156     bool checkAllocAtLeast(void* p, size_t s, size_t a) const {
157         return p == last_alloc_pointer &&
158                s <= last_alloc_size &&
159                a <= last_alloc_align;
160     }
161 
checkAllocAtLeastAllocController162     bool checkAllocAtLeast(void* p, size_t s) const {
163         return p == last_alloc_pointer &&
164                s <= last_alloc_size;
165     }
166 
checkDeallocAllocController167     bool checkDealloc(void* p, size_t s, size_t a) const {
168         return p == last_dealloc_pointer &&
169                s == last_dealloc_size &&
170                a == last_dealloc_align;
171     }
172 
checkDeallocAllocController173     bool checkDealloc(void* p, size_t s) const {
174         return p == last_dealloc_pointer &&
175                s == last_dealloc_size;
176     }
177 
checkDeallocMatchesAllocAllocController178     bool checkDeallocMatchesAlloc() const {
179         return last_dealloc_pointer == last_alloc_pointer &&
180                last_dealloc_size == last_alloc_size &&
181                last_dealloc_align == last_alloc_align;
182     }
183 
184     template <class ...Args, class Alloc, class Tp>
checkConstructAllocController185     bool checkConstruct(Alloc const&, Tp *p) const {
186         auto expectAlloc = &makeTypeID<Alloc>();
187         auto expectTp = &makeTypeID<Tp>();
188         auto expectArgs = &makeArgumentID<Args...>();
189         if (last_construct_pointer != p)
190             return false;
191         if (last_construct_alloc != expectAlloc)
192             return false;
193         if (last_construct_type != expectTp)
194             return false;
195         if (last_construct_args != expectArgs)
196             return false;
197         return true;
198     }
199 
200     template <class Alloc, class Tp>
checkDestroyAllocController201     bool checkDestroy(Alloc const&, Tp *p) const {
202       return last_destroy_pointer == p &&
203           last_destroy_alloc == &makeTypeID<Alloc>() &&
204           last_destroy_type == &makeTypeID<Tp>();
205     }
206 
checkDestroyMatchesConstructAllocController207     bool checkDestroyMatchesConstruct() const {
208       return last_destroy_pointer == last_construct_pointer &&
209           last_destroy_type == last_construct_type;
210     }
211 
countIsEqualAllocController212     void countIsEqual() {
213         ++is_equal_count;
214     }
215 
checkIsEqualCalledEqAllocController216     bool checkIsEqualCalledEq(int n) const {
217         return is_equal_count == n;
218     }
219 private:
220   DISALLOW_COPY(AllocController);
221 };
222 
223 template <class T, size_t ID>
224 class CountingAllocator
225 {
226 public:
227     typedef T value_type;
228     typedef T* pointer;
229 
230     template <class U>
231     struct rebind { using other = CountingAllocator<U, ID>; };
232 
233     CountingAllocator() = delete;
CountingAllocator(AllocController & PP)234     explicit CountingAllocator(AllocController& PP) : P(&PP) {}
235 
CountingAllocator(CountingAllocator const & other)236     CountingAllocator(CountingAllocator const& other) : P(other.P) {
237         P->copy_constructed += 1;
238     }
239 
CountingAllocator(CountingAllocator && other)240     CountingAllocator(CountingAllocator&& other) : P(other.P) {
241         P->move_constructed += 1;
242     }
243 
244     template <class U>
CountingAllocator(CountingAllocator<U,ID> const & other)245     CountingAllocator(CountingAllocator<U, ID> const& other) TEST_NOEXCEPT : P(other.P) {
246         P->copy_constructed += 1;
247     }
248 
249     template <class U>
CountingAllocator(CountingAllocator<U,ID> && other)250     CountingAllocator(CountingAllocator<U, ID>&& other) TEST_NOEXCEPT : P(other.P) {
251         P->move_constructed += 1;
252     }
253 
allocate(std::size_t n)254     T* allocate(std::size_t n)
255     {
256         void* ret = ::operator new(n*sizeof(T));
257         P->countAlloc(ret, n*sizeof(T), alignof(T));
258         return static_cast<T*>(ret);
259     }
260 
deallocate(T * p,std::size_t n)261     void deallocate(T* p, std::size_t n)
262     {
263         void* vp = static_cast<void*>(p);
264         P->countDealloc(vp, n*sizeof(T), alignof(T));
265         ::operator delete(vp);
266     }
267 
268     template <class U, class ...Args>
construct(U * p,Args &&...args)269     void construct(U *p, Args&&... args) {
270       ::new ((void*)p) U(std::forward<Args>(args)...);
271       P->countConstruct<Args&&...>(*this, p);
272     }
273 
274     template <class U>
destroy(U * p)275     void destroy(U* p) {
276       p->~U();
277       P->countDestroy(*this, p);
278     }
279 
getController()280     AllocController& getController() const { return *P; }
281 
282 private:
283     template <class Tp, size_t XID> friend class CountingAllocator;
284     AllocController *P;
285 };
286 
287 
288 template <size_t ID>
289 class CountingAllocator<void, ID>
290 {
291 public:
292     typedef void* pointer;
293     typedef const void* const_pointer;
294     typedef void value_type;
295 
296     template <class U>
297     struct rebind { using other = CountingAllocator<U, ID>; };
298 
299     CountingAllocator() = delete;
CountingAllocator(AllocController & PP)300     explicit CountingAllocator(AllocController& PP) : P(&PP) {}
301 
CountingAllocator(CountingAllocator const & other)302     CountingAllocator(CountingAllocator const& other) : P(other.P) {
303         P->copy_constructed += 1;
304     }
305 
CountingAllocator(CountingAllocator && other)306     CountingAllocator(CountingAllocator&& other) : P(other.P) {
307         P->move_constructed += 1;
308     }
309 
310     template <class U>
CountingAllocator(CountingAllocator<U,ID> const & other)311     CountingAllocator(CountingAllocator<U, ID> const& other) TEST_NOEXCEPT : P(other.P) {
312         P->copy_constructed += 1;
313     }
314 
315     template <class U>
CountingAllocator(CountingAllocator<U,ID> && other)316     CountingAllocator(CountingAllocator<U, ID>&& other) TEST_NOEXCEPT : P(other.P) {
317         P->move_constructed += 1;
318     }
319 
320     void construct(...) = delete;
321     void destroy(void*) = delete;
322 
getController()323     AllocController& getController() const { return *P; }
324 
325 private:
326     template <class Tp, size_t> friend class CountingAllocator;
327     AllocController *P;
328 };
329 
330 template <class T, class U, size_t ID>
331 inline bool operator==(CountingAllocator<T, ID> const& x,
332                        CountingAllocator<U, ID> const& y) {
333     return &x.getController() == &y.getController();
334 }
335 
336 template <class T, class U, size_t ID>
337 inline bool operator!=(CountingAllocator<T, ID> const& x,
338                        CountingAllocator<U, ID> const& y) {
339     return !(x == y);
340 }
341 
342 template <class T>
343 class MinAlignedAllocator
344 {
345 public:
346     typedef T value_type;
347     typedef T* pointer;
348 
349     MinAlignedAllocator() = delete;
350 
MinAlignedAllocator(AllocController & R)351     explicit MinAlignedAllocator(AllocController& R) : P(&R) {}
352 
MinAlignedAllocator(MinAlignedAllocator const & other)353     MinAlignedAllocator(MinAlignedAllocator const& other) : P(other.P) {
354         P->copy_constructed += 1;
355     }
356 
MinAlignedAllocator(MinAlignedAllocator && other)357     MinAlignedAllocator(MinAlignedAllocator&& other) : P(other.P) {
358         P->move_constructed += 1;
359     }
360 
361     template <class U>
MinAlignedAllocator(MinAlignedAllocator<U> const & other)362     MinAlignedAllocator(MinAlignedAllocator<U> const& other) TEST_NOEXCEPT : P(other.P) {
363         P->copy_constructed += 1;
364     }
365 
366     template <class U>
MinAlignedAllocator(MinAlignedAllocator<U> && other)367     MinAlignedAllocator(MinAlignedAllocator<U>&& other) TEST_NOEXCEPT : P(other.P) {
368         P->move_constructed += 1;
369     }
370 
allocate(std::size_t n)371     T* allocate(std::size_t n) {
372         char* aligned_ptr = (char*)::operator new(alloc_size(n*sizeof(T)));
373         assert(is_max_aligned(aligned_ptr));
374 
375         char* unaligned_ptr = aligned_ptr + alignof(T);
376         assert(is_min_aligned(unaligned_ptr));
377 
378         P->countAlloc(unaligned_ptr, n * sizeof(T), alignof(T));
379 
380         return ((T*)unaligned_ptr);
381     }
382 
deallocate(T * p,std::size_t n)383     void deallocate(T* p, std::size_t n) {
384         assert(is_min_aligned(p));
385 
386         char* aligned_ptr = ((char*)p) - alignof(T);
387         assert(is_max_aligned(aligned_ptr));
388 
389         P->countDealloc(p, n*sizeof(T), alignof(T));
390 
391         return ::operator delete(static_cast<void*>(aligned_ptr));
392     }
393 
394     template <class U, class ...Args>
construct(U * p,Args &&...args)395     void construct(U *p, Args&&... args) {
396       auto *c = ::new ((void*)p) U(std::forward<Args>(args)...);
397       P->countConstruct<Args&&...>(*this, p);
398     }
399 
400     template <class U>
destroy(U * p)401     void destroy(U* p) {
402       p->~U();
403       P->countDestroy(*this, p);
404     }
405 
getController()406     AllocController& getController() const { return *P; }
407 
408 private:
409     static const std::size_t BlockSize = alignof(std::max_align_t);
410 
alloc_size(std::size_t s)411     static std::size_t alloc_size(std::size_t s) {
412         std::size_t bytes = (s + BlockSize - 1) & ~(BlockSize - 1);
413         bytes += BlockSize;
414         assert(bytes % BlockSize == 0);
415         return bytes;
416     }
417 
is_max_aligned(void * p)418     static bool is_max_aligned(void* p) {
419         return reinterpret_cast<std::uintptr_t>(p) % BlockSize == 0;
420     }
421 
is_min_aligned(void * p)422     static bool is_min_aligned(void* p) {
423         if (alignof(T) == BlockSize) {
424             return is_max_aligned(p);
425         } else {
426             return reinterpret_cast<std::uintptr_t>(p) % BlockSize == alignof(T);
427         }
428     }
429 
430     template <class Tp> friend class MinAlignedAllocator;
431     mutable AllocController *P;
432 };
433 
434 
435 template <class T, class U>
436 inline bool operator==(MinAlignedAllocator<T> const& x,
437                        MinAlignedAllocator<U> const& y) {
438     return &x.getController() == &y.getController();
439 }
440 
441 template <class T, class U>
442 inline bool operator!=(MinAlignedAllocator<T> const& x,
443                        MinAlignedAllocator<U> const& y) {
444     return !(x == y);
445 }
446 
447 template <class T>
448 class NullAllocator
449 {
450 public:
451     typedef T value_type;
452     typedef T* pointer;
453     NullAllocator() = delete;
NullAllocator(AllocController & PP)454     explicit NullAllocator(AllocController& PP) : P(&PP) {}
455 
NullAllocator(NullAllocator const & other)456     NullAllocator(NullAllocator const& other) : P(other.P) {
457         P->copy_constructed += 1;
458     }
459 
NullAllocator(NullAllocator && other)460     NullAllocator(NullAllocator&& other) : P(other.P) {
461         P->move_constructed += 1;
462     }
463 
464     template <class U>
NullAllocator(NullAllocator<U> const & other)465     NullAllocator(NullAllocator<U> const& other) TEST_NOEXCEPT : P(other.P) {
466         P->copy_constructed += 1;
467     }
468 
469     template <class U>
NullAllocator(NullAllocator<U> && other)470     NullAllocator(NullAllocator<U>&& other) TEST_NOEXCEPT : P(other.P) {
471         P->move_constructed += 1;
472     }
473 
allocate(std::size_t n)474     T* allocate(std::size_t n)
475     {
476         P->countAlloc(nullptr, n*sizeof(T), alignof(T));
477         return nullptr;
478     }
479 
deallocate(T * p,std::size_t n)480     void deallocate(T* p, std::size_t n)
481     {
482         void* vp = static_cast<void*>(p);
483         P->countDealloc(vp, n*sizeof(T), alignof(T));
484     }
485 
getController()486     AllocController& getController() const { return *P; }
487 
488 private:
489     template <class Tp> friend class NullAllocator;
490     AllocController *P;
491 };
492 
493 template <class T, class U>
494 inline bool operator==(NullAllocator<T> const& x,
495                        NullAllocator<U> const& y) {
496     return &x.getController() == &y.getController();
497 }
498 
499 template <class T, class U>
500 inline bool operator!=(NullAllocator<T> const& x,
501                        NullAllocator<U> const& y) {
502     return !(x == y);
503 }
504 
505 
506 #endif /* SUPPORT_CONTROLLED_ALLOCATORS_H */
507