1 | /* Copyright 2019 Google LLC. All Rights Reserved. |
2 | |
3 | Licensed under the Apache License, Version 2.0 (the "License"); |
4 | you may not use this file except in compliance with the License. |
5 | You may obtain a copy of the License at |
6 | |
7 | http://www.apache.org/licenses/LICENSE-2.0 |
8 | |
9 | Unless required by applicable law or agreed to in writing, software |
10 | distributed under the License is distributed on an "AS IS" BASIS, |
11 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | See the License for the specific language governing permissions and |
13 | limitations under the License. |
14 | ==============================================================================*/ |
15 | |
16 | #ifndef RUY_RUY_ALLOCATOR_H_ |
17 | #define RUY_RUY_ALLOCATOR_H_ |
18 | |
19 | #include <cstddef> |
20 | #include <cstdint> |
21 | #include <memory> |
22 | #include <vector> |
23 | |
24 | namespace ruy { |
25 | |
26 | // Specialized allocator designed to converge to a steady-state where all |
27 | // allocations are bump-ptr allocations from an already-allocated buffer. |
28 | // |
29 | // To support these constraints, this allocator only supports two |
30 | // operations. |
31 | // - AllocateBytes/Allocate<Pointer>: allocates a pointer to storage of a |
32 | // specified size, which will be aligned to kMinimumBlockAlignment. |
33 | // - FreeAll: frees all previous allocations (but retains the internal |
34 | // buffer to minimize future calls into the system allocator). |
35 | // |
36 | // This class is specialized for supporting just those two operations |
37 | // under this specific steady-state usage pattern. Extending this class |
38 | // with new allocation interfaces that don't fit that pattern is probably not |
39 | // the right choice. Instead, build a new class on top of |
40 | // SystemAlignedAlloc/SystemAlignedFree. |
41 | // |
42 | // All operations happen on aligned blocks for simplicity. |
43 | // |
44 | // Theory of operation: |
45 | // |
46 | // - ptr_, current_, and size_ implement a basic bump-ptr allocator. |
47 | // |
48 | // - in AllocateBytes, the fast path is just a bump-ptr |
49 | // allocation. If our bump-ptr allocator doesn't have enough space for an |
50 | // allocation, then we allocate a block from the system allocator to |
51 | // service the allocation request. We save that block in fallback_blocks_ |
52 | // and track the total size of the fallback blocks in |
53 | // fallback_blocks_total_size_. |
54 | // |
55 | // - in FreeAll, the fast path just resets the bump-ptr allocator. If |
56 | // there are any fallback blocks, we free them and reallocate the |
57 | // bump-ptr allocator's buffer so that the next sequence of allocations |
58 | // will hopefully not need any fallback blocks. |
59 | class Allocator final { |
60 | public: |
61 | ~Allocator(); |
62 | |
63 | // Allocate a buffer. |
64 | void* AllocateBytes(std::ptrdiff_t num_bytes); |
65 | // Allocate a buffer, trying to avoid having its address close to aliasing |
66 | // the specified `to_avoid` in the L1D cache. |
67 | void* AllocateBytesAvoidingAliasingWith(std::ptrdiff_t num_bytes, |
68 | const void* to_avoid); |
69 | // Allocate an array of `count` elements of type T. |
70 | template <typename T> |
71 | T* Allocate(std::ptrdiff_t count) { |
72 | return static_cast<T*>(AllocateBytes(count * sizeof(T))); |
73 | } |
74 | // Allocate an array of `count` elements of the given `Pointer` type's |
75 | // element_type. |
76 | template <typename Pointer> |
77 | void Allocate(std::ptrdiff_t count, Pointer* out) { |
78 | using T = typename std::pointer_traits<Pointer>::element_type; |
79 | *out = Allocate<T>(count); |
80 | } |
81 | |
82 | // Free all allocated blocks. Internally consolidate allocated buffers as |
83 | // explained in the class comment. |
84 | void FreeAll(); |
85 | |
86 | private: |
87 | void operator=(const Allocator&) = delete; |
88 | void* AllocateFast(std::ptrdiff_t num_bytes); |
89 | void* AllocateSlow(std::ptrdiff_t num_bytes); |
90 | |
91 | void* ptr_ = nullptr; |
92 | std::ptrdiff_t current_ = 0; |
93 | std::ptrdiff_t size_ = 0; |
94 | std::vector<void*> fallback_blocks_; |
95 | std::ptrdiff_t fallback_blocks_total_size_ = 0; |
96 | }; |
97 | |
98 | } // namespace ruy |
99 | |
100 | #endif // RUY_RUY_ALLOCATOR_H_ |
101 | |