1 // Copyright 2020 Google LLC
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 #ifndef HIGHWAY_HWY_ALIGNED_ALLOCATOR_H_
16 #define HIGHWAY_HWY_ALIGNED_ALLOCATOR_H_
17
18 // Memory allocator with support for alignment and offsets.
19
20 #include <stddef.h>
21 #include <memory>
22
23 namespace hwy {
24
25 // Minimum alignment of allocated memory for use in HWY_ASSUME_ALIGNED, which
26 // requires a literal. This matches typical L1 cache line sizes, which prevents
27 // false sharing.
28 #define HWY_ALIGNMENT 64
29
30 // Pointers to functions equivalent to malloc/free with an opaque void* passed
31 // to them.
32 using AllocPtr = void* (*)(void* opaque, size_t bytes);
33 using FreePtr = void (*)(void* opaque, void* memory);
34
35 // Returns null or a pointer to at least `payload_size` (which can be zero)
36 // bytes of newly allocated memory, aligned to the larger of HWY_ALIGNMENT and
37 // the vector size. Calls `alloc` with the passed `opaque` pointer to obtain
38 // memory or malloc() if it is null.
39 void* AllocateAlignedBytes(size_t payload_size, AllocPtr alloc_ptr,
40 void* opaque_ptr);
41
42 // Frees all memory. No effect if `aligned_pointer` == nullptr, otherwise it
43 // must have been returned from a previous call to `AllocateAlignedBytes`.
44 // Calls `free_ptr` with the passed `opaque_ptr` pointer to free the memory; if
45 // `free_ptr` function is null, uses the default free().
46 void FreeAlignedBytes(const void* aligned_pointer, FreePtr free_ptr,
47 void* opaque_ptr);
48
49 // Class that deletes the aligned pointer passed to operator() calling the
50 // destructor before freeing the pointer. This is equivalent to the
51 // std::default_delete but for aligned objects. For a similar deleter equivalent
52 // to free() for aligned memory see AlignedFreer().
53 class AlignedDeleter {
54 public:
AlignedDeleter()55 AlignedDeleter() : free_(nullptr), opaque_ptr_(nullptr) {}
AlignedDeleter(FreePtr free_ptr,void * opaque_ptr)56 AlignedDeleter(FreePtr free_ptr, void* opaque_ptr)
57 : free_(free_ptr), opaque_ptr_(opaque_ptr) {}
58
59 template <typename T>
operator()60 void operator()(T* aligned_pointer) const {
61 return DeleteAlignedArray(aligned_pointer, free_, opaque_ptr_,
62 TypedArrayDeleter<T>);
63 }
64
65 private:
66 template <typename T>
TypedArrayDeleter(void * ptr,size_t size_in_bytes)67 static void TypedArrayDeleter(void* ptr, size_t size_in_bytes) {
68 size_t elems = size_in_bytes / sizeof(T);
69 for (size_t i = 0; i < elems; i++) {
70 // Explicitly call the destructor on each element.
71 (static_cast<T*>(ptr) + i)->~T();
72 }
73 }
74
75 // Function prototype that calls the destructor for each element in a typed
76 // array. TypeArrayDeleter<T> would match this prototype.
77 using ArrayDeleter = void (*)(void* t_ptr, size_t t_size);
78
79 static void DeleteAlignedArray(void* aligned_pointer, FreePtr free_ptr,
80 void* opaque_ptr, ArrayDeleter deleter);
81
82 FreePtr free_;
83 void* opaque_ptr_;
84 };
85
86 // Unique pointer to T with custom aligned deleter. This can be a single
87 // element U or an array of element if T is a U[]. The custom aligned deleter
88 // will call the destructor on U or each element of a U[] in the array case.
89 template <typename T>
90 using AlignedUniquePtr = std::unique_ptr<T, AlignedDeleter>;
91
92 // Aligned memory equivalent of make_unique<T> using the custom allocators
93 // alloc/free with the passed `opaque` pointer. This function calls the
94 // constructor with the passed Args... and calls the destructor of the object
95 // when the AlignedUniquePtr is destroyed.
96 template <typename T, typename... Args>
MakeUniqueAlignedWithAlloc(AllocPtr alloc,FreePtr free,void * opaque,Args &&...args)97 AlignedUniquePtr<T> MakeUniqueAlignedWithAlloc(AllocPtr alloc, FreePtr free,
98 void* opaque, Args&&... args) {
99 T* ptr = static_cast<T*>(AllocateAlignedBytes(sizeof(T), alloc, opaque));
100 return AlignedUniquePtr<T>(new (ptr) T(std::forward<Args>(args)...),
101 AlignedDeleter(free, opaque));
102 }
103
104 // Similar to MakeUniqueAlignedWithAlloc but using the default alloc/free
105 // functions.
106 template <typename T, typename... Args>
MakeUniqueAligned(Args &&...args)107 AlignedUniquePtr<T> MakeUniqueAligned(Args&&... args) {
108 T* ptr = static_cast<T*>(AllocateAlignedBytes(
109 sizeof(T), /*alloc_ptr=*/nullptr, /*opaque_ptr=*/nullptr));
110 return AlignedUniquePtr<T>(
111 new (ptr) T(std::forward<Args>(args)...), AlignedDeleter());
112 }
113
114 // Helpers for array allocators (avoids overflow)
115 namespace detail {
116
117 // Returns x such that 1u << x == n (if n is a power of two).
ShiftCount(size_t n)118 static inline constexpr size_t ShiftCount(size_t n) {
119 return (n <= 1) ? 0 : 1 + ShiftCount(n / 2);
120 }
121
122 template <typename T>
AllocateAlignedItems(size_t items,AllocPtr alloc_ptr,void * opaque_ptr)123 T* AllocateAlignedItems(size_t items, AllocPtr alloc_ptr, void* opaque_ptr) {
124 constexpr size_t size = sizeof(T);
125
126 constexpr bool is_pow2 = (size & (size - 1)) == 0;
127 constexpr size_t bits = ShiftCount(size);
128 static_assert(!is_pow2 || (1ull << bits) == size, "ShiftCount is incorrect");
129
130 const size_t bytes = is_pow2 ? items << bits : items * size;
131 const size_t check = is_pow2 ? bytes >> bits : bytes / size;
132 if (check != items) {
133 return nullptr; // overflowed
134 }
135 return static_cast<T*>(AllocateAlignedBytes(bytes, alloc_ptr, opaque_ptr));
136 }
137
138 } // namespace detail
139
140 // Aligned memory equivalent of make_unique<T[]> for array types using the
141 // custom allocators alloc/free. This function calls the constructor with the
142 // passed Args... on every created item. The destructor of each element will be
143 // called when the AlignedUniquePtr is destroyed.
144 template <typename T, typename... Args>
MakeUniqueAlignedArrayWithAlloc(size_t items,AllocPtr alloc,FreePtr free,void * opaque,Args &&...args)145 AlignedUniquePtr<T[]> MakeUniqueAlignedArrayWithAlloc(
146 size_t items, AllocPtr alloc, FreePtr free, void* opaque, Args&&... args) {
147 T* ptr = detail::AllocateAlignedItems<T>(items, alloc, opaque);
148 if (ptr != nullptr) {
149 for (size_t i = 0; i < items; i++) {
150 new (ptr + i) T(std::forward<Args>(args)...);
151 }
152 }
153 return AlignedUniquePtr<T[]>(ptr, AlignedDeleter(free, opaque));
154 }
155
156 template <typename T, typename... Args>
MakeUniqueAlignedArray(size_t items,Args &&...args)157 AlignedUniquePtr<T[]> MakeUniqueAlignedArray(size_t items, Args&&... args) {
158 return MakeUniqueAlignedArrayWithAlloc<T, Args...>(
159 items, nullptr, nullptr, nullptr, std::forward<Args>(args)...);
160 }
161
162 // Custom deleter for std::unique_ptr equivalent to using free() as a deleter
163 // but for aligned memory.
164 class AlignedFreer {
165 public:
166 // Pass address of this to ctor to skip deleting externally-owned memory.
DoNothing(void *,void *)167 static void DoNothing(void* /*opaque*/, void* /*aligned_pointer*/) {}
168
AlignedFreer()169 AlignedFreer() : free_(nullptr), opaque_ptr_(nullptr) {}
AlignedFreer(FreePtr free_ptr,void * opaque_ptr)170 AlignedFreer(FreePtr free_ptr, void* opaque_ptr)
171 : free_(free_ptr), opaque_ptr_(opaque_ptr) {}
172
173 template <typename T>
operator()174 void operator()(T* aligned_pointer) const {
175 // TODO(deymo): assert that we are using a POD type T.
176 FreeAlignedBytes(aligned_pointer, free_, opaque_ptr_);
177 }
178
179 private:
180 FreePtr free_;
181 void* opaque_ptr_;
182 };
183
184 // Unique pointer to single POD, or (if T is U[]) an array of POD. For non POD
185 // data use AlignedUniquePtr.
186 template <typename T>
187 using AlignedFreeUniquePtr = std::unique_ptr<T, AlignedFreer>;
188
189 // Allocate an aligned and uninitialized array of POD values as a unique_ptr.
190 // Upon destruction of the unique_ptr the aligned array will be freed.
191 template <typename T>
AllocateAligned(const size_t items,AllocPtr alloc,FreePtr free,void * opaque)192 AlignedFreeUniquePtr<T[]> AllocateAligned(const size_t items, AllocPtr alloc,
193 FreePtr free, void* opaque) {
194 return AlignedFreeUniquePtr<T[]>(
195 detail::AllocateAlignedItems<T>(items, alloc, opaque),
196 AlignedFreer(free, opaque));
197 }
198
199 // Same as previous AllocateAligned(), using default allocate/free functions.
200 template <typename T>
AllocateAligned(const size_t items)201 AlignedFreeUniquePtr<T[]> AllocateAligned(const size_t items) {
202 return AllocateAligned<T>(items, nullptr, nullptr, nullptr);
203 }
204
205 } // namespace hwy
206 #endif // HIGHWAY_HWY_ALIGNED_ALLOCATOR_H_
207