third_party/highway/hwy/aligned_allocator.h

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