Core: Respect scalar type alignment in scratch buffers

libeigen/eigen!3386

Closes #1758

Co-authored-by: Rasmus Munk Larsen <rmlarsen@gmail.com>
diff --git a/Eigen/src/Core/util/Memory.h b/Eigen/src/Core/util/Memory.h
index 904bf3f..de32b35 100644
--- a/Eigen/src/Core/util/Memory.h
+++ b/Eigen/src/Core/util/Memory.h
@@ -694,14 +694,51 @@
 #endif
 }
 
-/** \internal Like aligned_new, at the temporaries' alignment (EIGEN_STACK_ALIGN_BYTES); release with scratch_delete. */
+/** \internal Allocates size bytes without constructing T; release with scratch_free<T>. */
+template <typename T>
+EIGEN_DEVICE_FUNC inline T* scratch_malloc(std::size_t size) {
+  EIGEN_IF_CONSTEXPR (alignof(T) <= EIGEN_STACK_ALIGN_BYTES ||
+                      (EIGEN_STACK_ALIGN_BYTES == 0 && alignof(T) <= alignof(std::max_align_t))) {
+    return static_cast<T*>(scratch_malloc(size));
+  } else {
+    // Unlike the byte-offset allocator, this also supports alignments greater than 256.
+    constexpr std::size_t overhead = alignof(T) - 1 + sizeof(void*);
+    size += overhead;
+    if (size < overhead) throw_std_bad_alloc();
+    check_that_malloc_is_allowed();
+    void* original = std::malloc(size);
+    if (!original) throw_std_bad_alloc();
+    // std::align is host-only with CUDA.
+    char* start = static_cast<char*>(original) + sizeof(void*);
+    const std::uintptr_t offset = reinterpret_cast<std::uintptr_t>(start) % alignof(T);
+    const std::uintptr_t shift = offset > 0 ? alignof(T) - offset : 0;
+    void* aligned = start + shift;
+    std::memcpy(static_cast<char*>(aligned) - sizeof(void*), reinterpret_cast<const void*>(&original), sizeof(void*));
+    return static_cast<T*>(aligned);
+  }
+}
+
+template <typename T>
+EIGEN_DEVICE_FUNC inline void scratch_free(void* ptr) {
+  EIGEN_IF_CONSTEXPR (alignof(T) <= EIGEN_STACK_ALIGN_BYTES ||
+                      (EIGEN_STACK_ALIGN_BYTES == 0 && alignof(T) <= alignof(std::max_align_t))) {
+    scratch_free(ptr);
+  } else if (ptr) {
+    void* original;
+    std::memcpy(reinterpret_cast<void*>(&original), static_cast<char*>(ptr) - sizeof(void*), sizeof(void*));
+    check_that_free_is_allowed();
+    std::free(original);
+  }
+}
+
+/** \internal Like aligned_new, respecting both type and scratch alignment; release with scratch_delete. */
 template <typename T>
 EIGEN_DEVICE_FUNC inline T* scratch_new(std::size_t size) {
   check_size_for_overflow<T>(size);
-  T* result = static_cast<T*>(scratch_malloc(sizeof(T) * size));
+  T* result = scratch_malloc<T>(sizeof(T) * size);
   EIGEN_TRY { default_construct_elements_of_array(result, size); }
   EIGEN_CATCH(...) {
-    scratch_free(result);
+    scratch_free<T>(result);
     EIGEN_THROW;
   }
   return result;
@@ -711,7 +748,7 @@
 template <typename T>
 EIGEN_DEVICE_FUNC inline void scratch_delete(T* ptr, std::size_t size) {
   destruct_elements_of_array<T>(ptr, size);
-  scratch_free(ptr);
+  scratch_free<T>(ptr);
 }
 
 // This helper class construct the allocated memory, and takes care of destructing and freeing the handled data
@@ -738,7 +775,7 @@
     EIGEN_IF_CONSTEXPR (NumTraits<T>::RequireInitialization) {
       if (m_ptr) Eigen::internal::destruct_elements_of_array<T>(m_ptr, m_size);
     }
-    if (m_deallocate) Eigen::internal::scratch_free(m_ptr);
+    if (m_deallocate) Eigen::internal::scratch_free<T>(m_ptr);
   }
 
  protected:
@@ -772,8 +809,8 @@
   ObjectType object;
 
   EIGEN_DEVICE_FUNC local_nested_eval_wrapper(const Xpr& xpr, Scalar* ptr)
-      : object(ptr == 0 ? reinterpret_cast<Scalar*>(Eigen::internal::aligned_malloc(sizeof(Scalar) * xpr.size())) : ptr,
-               xpr.rows(), xpr.cols()),
+      : object(ptr == 0 ? Eigen::internal::scratch_malloc<Scalar>(sizeof(Scalar) * xpr.size()) : ptr, xpr.rows(),
+               xpr.cols()),
         m_deallocate(ptr == 0) {
     EIGEN_IF_CONSTEXPR (NumTraits<Scalar>::RequireInitialization) {
       if (object.data()) Eigen::internal::default_construct_elements_of_array(object.data(), object.size());
@@ -785,7 +822,7 @@
     EIGEN_IF_CONSTEXPR (NumTraits<Scalar>::RequireInitialization) {
       if (object.data()) Eigen::internal::destruct_elements_of_array(object.data(), object.size());
     }
-    if (m_deallocate) Eigen::internal::aligned_free(object.data());
+    if (m_deallocate) Eigen::internal::scratch_free<Scalar>(object.data());
   }
 
  private:
@@ -799,7 +836,9 @@
 /** \internal
  *
  * The macro ei_declare_aligned_stack_constructed_variable(TYPE,NAME,SIZE,BUFFER) declares, allocates,
- * and construct an aligned buffer named NAME of SIZE elements of type TYPE on the stack
+ * and construct an aligned buffer named NAME of SIZE elements of type TYPE on the stack.
+ * Allocated storage respects both alignof(TYPE) and EIGEN_STACK_ALIGN_BYTES, even when SIMD alignment is disabled.
+ * Storage is allocated on the stack
  * if the size in bytes is smaller than EIGEN_STACK_ALLOCATION_LIMIT, and if stack allocation is supported by the
  * platform (currently, this is Linux, OSX and Visual Studio only). Otherwise the memory is allocated on the heap;
  * in particular, a zero EIGEN_STACK_ALLOCATION_LIMIT disables stack allocation and every buffer is heap-allocated. The
@@ -843,32 +882,46 @@
 #define EIGEN_ALIGNED_ALLOCA(SIZE) EIGEN_ALLOCA(SIZE)
 #endif
 
-#define ei_declare_aligned_stack_constructed_variable(TYPE, NAME, SIZE, BUFFER)                                       \
-  Eigen::internal::check_size_for_overflow<TYPE>(SIZE);                                                               \
-  TYPE* NAME = (BUFFER) != 0 ? (BUFFER)                                                                               \
-                             : reinterpret_cast<TYPE*>((sizeof(TYPE) * (SIZE) <= EIGEN_STACK_ALLOCATION_LIMIT)        \
-                                                           ? EIGEN_ALIGNED_ALLOCA(sizeof(TYPE) * (SIZE))              \
-                                                           : Eigen::internal::scratch_malloc(sizeof(TYPE) * (SIZE))); \
-  Eigen::internal::aligned_stack_memory_handler<TYPE> EIGEN_CAT(NAME, _stack_memory_destructor)(                      \
-      (BUFFER) == 0 ? NAME : 0, SIZE, sizeof(TYPE) * (SIZE) > EIGEN_STACK_ALLOCATION_LIMIT)
+// Preserve the existing allocation path unless the scalar needs stronger alignment.
+#define EIGEN_TYPED_ALIGNED_ALLOCA(TYPE, SIZE)                                                                  \
+  (alignof(TYPE) <= EIGEN_STACK_ALIGN_BYTES                                                                     \
+       ? EIGEN_ALIGNED_ALLOCA(SIZE)                                                                             \
+       : reinterpret_cast<void*>(                                                                               \
+             (reinterpret_cast<std::uintptr_t>(EIGEN_ALLOCA((SIZE) + alignof(TYPE) - 1)) + alignof(TYPE) - 1) & \
+             ~(std::uintptr_t(alignof(TYPE)) - 1)))
 
-#define ei_declare_local_nested_eval(XPR_T, XPR, N, NAME)                                        \
-  Eigen::internal::local_nested_eval_wrapper<XPR_T, N> EIGEN_CAT(NAME, _wrapper)(                \
-      XPR, reinterpret_cast<typename XPR_T::Scalar*>(                                            \
-               ((Eigen::internal::local_nested_eval_wrapper<XPR_T, N>::NeedExternalBuffer) &&    \
-                ((sizeof(typename XPR_T::Scalar) * XPR.size()) <= EIGEN_STACK_ALLOCATION_LIMIT)) \
-                   ? EIGEN_ALIGNED_ALLOCA(sizeof(typename XPR_T::Scalar) * XPR.size())           \
-                   : 0));                                                                        \
+// TYPE and NAME form declarations, not expressions.
+// NOLINTBEGIN(bugprone-macro-parentheses)
+#define ei_declare_aligned_stack_constructed_variable(TYPE, NAME, SIZE, BUFFER)                                   \
+  Eigen::internal::check_size_for_overflow<TYPE>(SIZE);                                                           \
+  TYPE* NAME = (BUFFER) != 0                                                                                      \
+                   ? (BUFFER)                                                                                     \
+                   : reinterpret_cast<TYPE*>((sizeof(TYPE) * (SIZE) <= EIGEN_STACK_ALLOCATION_LIMIT)              \
+                                                 ? EIGEN_TYPED_ALIGNED_ALLOCA(TYPE, sizeof(TYPE) * (SIZE))        \
+                                                 : Eigen::internal::scratch_malloc<TYPE>(sizeof(TYPE) * (SIZE))); \
+  Eigen::internal::aligned_stack_memory_handler<TYPE> EIGEN_CAT(NAME, _stack_memory_destructor)(                  \
+      (BUFFER) == 0 ? NAME : 0, SIZE, sizeof(TYPE) * (SIZE) > EIGEN_STACK_ALLOCATION_LIMIT)
+// NOLINTEND(bugprone-macro-parentheses)
+
+#define ei_declare_local_nested_eval(XPR_T, XPR, N, NAME)                                                              \
+  Eigen::internal::local_nested_eval_wrapper<XPR_T, N> EIGEN_CAT(NAME, _wrapper)(                                      \
+      XPR, reinterpret_cast<typename XPR_T::Scalar*>(                                                                  \
+               ((Eigen::internal::local_nested_eval_wrapper<XPR_T, N>::NeedExternalBuffer) &&                          \
+                ((sizeof(typename XPR_T::Scalar) * (XPR).size()) <= EIGEN_STACK_ALLOCATION_LIMIT))                     \
+                   ? EIGEN_TYPED_ALIGNED_ALLOCA(typename XPR_T::Scalar, sizeof(typename XPR_T::Scalar) * (XPR).size()) \
+                   : 0));                                                                                              \
   typename Eigen::internal::local_nested_eval_wrapper<XPR_T, N>::ObjectType NAME(EIGEN_CAT(NAME, _wrapper).object)
 
 #else
 
-#define ei_declare_aligned_stack_constructed_variable(TYPE, NAME, SIZE, BUFFER)                                 \
-  Eigen::internal::check_size_for_overflow<TYPE>(SIZE);                                                         \
-  TYPE* NAME =                                                                                                  \
-      (BUFFER) != 0 ? BUFFER : reinterpret_cast<TYPE*>(Eigen::internal::scratch_malloc(sizeof(TYPE) * (SIZE))); \
-  Eigen::internal::aligned_stack_memory_handler<TYPE> EIGEN_CAT(NAME, _stack_memory_destructor)(                \
+// TYPE and NAME form declarations, not expressions.
+// NOLINTBEGIN(bugprone-macro-parentheses)
+#define ei_declare_aligned_stack_constructed_variable(TYPE, NAME, SIZE, BUFFER)                         \
+  Eigen::internal::check_size_for_overflow<TYPE>(SIZE);                                                 \
+  TYPE* NAME = (BUFFER) != 0 ? (BUFFER) : Eigen::internal::scratch_malloc<TYPE>(sizeof(TYPE) * (SIZE)); \
+  Eigen::internal::aligned_stack_memory_handler<TYPE> EIGEN_CAT(NAME, _stack_memory_destructor)(        \
       (BUFFER) == 0 ? NAME : 0, SIZE, true)
+// NOLINTEND(bugprone-macro-parentheses)
 
 #define ei_declare_local_nested_eval(XPR_T, XPR, N, NAME) \
   typename Eigen::internal::nested_eval<XPR_T, N>::type NAME(XPR)
diff --git a/test/dynalloc.cpp b/test/dynalloc.cpp
index df44818..321d148 100644
--- a/test/dynalloc.cpp
+++ b/test/dynalloc.cpp
@@ -140,7 +140,87 @@
 #endif
 }
 
+template <int Alignment>
+struct alignas(Alignment) ScratchScalar {
+  static int alive;
+  int value;
+  ScratchScalar() : value(17) {
+    VERIFY(std::uintptr_t(this) % Alignment == 0);
+    ++alive;
+  }
+  ~ScratchScalar() { --alive; }
+};
+template <int Alignment>
+int ScratchScalar<Alignment>::alive = 0;
+
+template <int Alignment>
+void check_typed_scratch() {
+  using T = ScratchScalar<Alignment>;
+  STATIC_CHECK((std::is_same<decltype(internal::scratch_malloc<T>(sizeof(T))), T *>::value));
+  const Index sizes[] = {1, 3, EIGEN_STACK_ALLOCATION_LIMIT / sizeof(T) + 1};
+  for (Index size : sizes) {
+    T *raw = internal::scratch_malloc<T>(sizeof(T) * size);
+    VERIFY(std::uintptr_t(raw) % Alignment == 0);
+    VERIFY_IS_EQUAL(T::alive, 0);
+    std::memset(static_cast<void *>(raw), 0, sizeof(T) * size);
+    internal::scratch_free<T>(raw);
+    {
+      ei_declare_aligned_stack_constructed_variable(T, data, size, nullptr);
+      VERIFY_IS_EQUAL(T::alive, size);
+      for (Index i = 0; i < size; ++i) VERIFY_IS_EQUAL(data[i].value, 17);
+    }
+    VERIFY_IS_EQUAL(T::alive, 0);
+    T *data = internal::scratch_new<T>(size);
+    VERIFY_IS_EQUAL(T::alive, size);
+    internal::scratch_delete(data, size);
+    VERIFY_IS_EQUAL(T::alive, 0);
+  }
+  internal::scratch_free<T>(nullptr);
+#ifdef EIGEN_EXCEPTIONS
+  EIGEN_IF_CONSTEXPR (alignof(T) > EIGEN_STACK_ALIGN_BYTES &&
+                      (EIGEN_STACK_ALIGN_BYTES != 0 || alignof(T) > alignof(std::max_align_t))) {
+    const std::size_t overhead = alignof(T) - 1 + sizeof(void *);
+    const std::size_t max_size = (std::numeric_limits<std::size_t>::max)();
+    for (std::size_t bytes : {max_size, max_size - overhead + 1}) {
+      bool threw = false;
+      try {
+        T *raw = internal::scratch_malloc<T>(bytes);
+        internal::scratch_free<T>(raw);
+      } catch (const std::bad_alloc &) {
+        threw = true;
+      }
+      VERIFY(threw);
+    }
+  }
+#endif
+  {
+    T supplied[2];
+    {
+      ei_declare_aligned_stack_constructed_variable(T, data, 2, supplied);
+      VERIFY(data == supplied);
+      VERIFY_IS_EQUAL(T::alive, 2);
+    }
+    VERIFY_IS_EQUAL(T::alive, 2);
+  }
+  VERIFY_IS_EQUAL(T::alive, 0);
+#if defined(EIGEN_ALLOCA) && !defined(EIGEN_NO_ALLOCA)
+  {
+    T supplied[3];
+    using Vector = Matrix<T, Dynamic, 1>;
+    using View = Map<Vector, Unaligned>;
+    View input(supplied, 3);
+    internal::local_nested_eval_wrapper<View, 2, true> copy(input, nullptr);
+    VERIFY(std::uintptr_t(copy.object.data()) % Alignment == 0);
+    VERIFY_IS_EQUAL(copy.object(0).value, 17);
+  }
+  VERIFY_IS_EQUAL(T::alive, 0);
+#endif
+}
+
 EIGEN_DECLARE_TEST(dynalloc) {
+  CALL_SUBTEST(check_typed_scratch<16>());
+  CALL_SUBTEST(check_typed_scratch<64>());
+  CALL_SUBTEST(check_typed_scratch<512>());
   // low level dynamic memory allocation
   CALL_SUBTEST(check_handmade_aligned_malloc());
   CALL_SUBTEST(check_aligned_malloc());