[asan] Adhere to AddressSanitizer's alignment requirements for the end of a region.

[bobsayshilol]

Summary

vector<> is only annotated if the allocator it's using matches the default allocator, however client code can override the global operator new() and operator delete() which then controls how the default allocator behaves. If the allocation returned by these overridden operators doesn't come from the heap then AddressSanitizer requires that both the start and end be aligned to 8B. The start will always be aligned to at least 8B because the global operator new() doesn't know the type it's allocating for and therefore must match the natural alignment, however the end may not be aligned to 8B if the size of the allocation isn't a multiple of 8B.

This patch fixes the issue by rounding up the capacity of a vector<> on resize to a size that satisfies AddressSanitizer's requirements.

[mclow.lists]

libcxx/test/std/containers/sequences/vector/vector.capacity/shrink_to_fit.pass.cpp

27

shrink_to_fit cannot increase capacity.

[bobsayshilol]

• Fix backwards asserts that must have gotten trampled when reformatting.
• Add another resizing test by inserting elements into the middle of the vector<>.
• Remove TEST_STD_VER check in favour of UNSUPPORTED. The behaviour isn't specific to C++11 and above, but I don't know how to write parts of the test in a pre-C++11 way.
• Be explicit about the capacities in shrink_to_fit.pass.cpp when AddressSanitizer is enabled.
• Exclude a test that will no longer work if AddressSanitizer is enabled without exceptions in shrink_to_fit.pass.cpp.

[bobsayshilol]

libcxx/test/std/containers/sequences/vector/vector.capacity/shrink_to_fit.pass.cpp

27

I've updated the patch to be explicit about the capacity after all calls to shrink_to_fit(). It looks like I managed to miss a handful of other things when I initially submitted the patch but the new patch should fix those up too.

[bobsayshilol]

Forgot to mark this comment as done when I updated the patch.

libcxx/include/vector

#endif
     // may not meet the AddressSanitizer alignment constraints.
     // See the documentation for __sanitizer_annotate_contiguous_container for more details.
 #ifndef _LIBCPP_HAS_NO_ASAN
     void __annotate_contiguous_container(const void *__beg, const void *__end,
                                          const void *__old_mid,
                                          const void *__new_mid) const
     {
 
-      if (__beg && is_same<allocator_type, __default_allocator_type>::value)
+      if (__beg && is_same<allocator_type, __default_allocator_type>::value) {
+        _LIBCPP_ASSERT(
+            (!(reinterpret_cast<uintptr_t>(__beg) & static_cast<uintptr_t>(7))),
+            "Beginning of range isn't aligned appropriately for "
+            "AddressSanitizer");
+        _LIBCPP_ASSERT(
+            (!(reinterpret_cast<uintptr_t>(__end) & static_cast<uintptr_t>(7))),
+            "End of range isn't aligned appropriately for AddressSanitizer");
         __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid);
       }
+    }
+
+    // Even with constraints on the alignment of the default allocator it's still
+    // possible for the end of the range to end up on a non-8B boundary, ie in the
+    // case that _Tp is an int and a single element is allocated. To support this
+    // we round up the size of any allocations to the boundary alignment.
+    size_type __align_size(size_type __size) const _NOEXCEPT {
+      // This is what it should be, but we can't get to gcd from here (and it requires
+      // C++11 to use). Also note that we can't do these enum tricks at class scope
+      // because `value_type` might be incomplete.
+      //enum { __asan_size_align = 8 / gcd(8, sizeof(value_type)) };
+      enum {__size_mod_8 = sizeof(value_type) % 8};
+      enum {__alignment = (__size_mod_8 & 1) ? 8
+                        : (__size_mod_8 & 2) ? 4
+                        : (__size_mod_8 & 4) ? 2
+                        : 1};
+      static_assert(((__alignment * sizeof(value_type)) % 8) == 0,
+                    "End of allocation won't be aligned correctly");
+
+      const size_type __new_size = ((__size - 1) | (__alignment - 1)) + 1;
+      const size_type __ms = max_size();
+      if (__new_size < __size || __new_size > __ms)
+        this->__throw_length_error();
+      return __new_size;
+    }
 #else
     _LIBCPP_INLINE_VISIBILITY
     void __annotate_contiguous_container(const void*, const void*, const void*,
                                          const void*) const _NOEXCEPT {}
+    _LIBCPP_INLINE_VISIBILITY
+    size_type __align_size(size_type __new_size) const _NOEXCEPT {
+      return __new_size;
+    }
 #endif
     _LIBCPP_INLINE_VISIBILITY
     void __annotate_new(size_type __current_size) const _NOEXCEPT {
       __annotate_contiguous_container(data(), data() + capacity(),
                                       data() + capacity(), data() + __current_size);
     }
 
     _LIBCPP_INLINE_VISIBILITY

 //  Precondition:  __begin_ == __end_ == __end_cap() == 0
 //  Precondition:  __n > 0
 //  Postcondition:  capacity() == __n
 //  Postcondition:  size() == 0
 template <class _Tp, class _Allocator>
 void
 vector<_Tp, _Allocator>::__vallocate(size_type __n)
 {
+    __n = __align_size(__n);
     if (__n > max_size())
         this->__throw_length_error();
     this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
     this->__end_cap() = this->__begin_ + __n;
     __annotate_new(0);
 }
 
 template <class _Tp, class _Allocator>

 void
 vector<_Tp, _Allocator>::__append(size_type __n)
 {
     if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
         this->__construct_at_end(__n);
     else
     {
         allocator_type& __a = this->__alloc();
-        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
+        __split_buffer<value_type, allocator_type&> __v(
+            __align_size(__recommend(size() + __n)), size(), __a);
         __v.__construct_at_end(__n);
         __swap_out_circular_buffer(__v);
     }
 }
 
 //  Default constructs __n objects starting at __end_
 //  throws if construction throws
 //  Postcondition:  size() == size() + __n
 //  Exception safety: strong.
 template <class _Tp, class _Allocator>
 void
 vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
 {
     if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
         this->__construct_at_end(__n, __x);
     else
     {
         allocator_type& __a = this->__alloc();
-        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
+        __split_buffer<value_type, allocator_type&> __v(
+            __align_size(__recommend(size() + __n)), size(), __a);
         __v.__construct_at_end(__n, __x);
         __swap_out_circular_buffer(__v);
     }
 }
 
 template <class _Tp, class _Allocator>
 vector<_Tp, _Allocator>::vector(size_type __n)
 {

 
 template <class _Tp, class _Allocator>
 void
 vector<_Tp, _Allocator>::reserve(size_type __n)
 {
     if (__n > capacity())
     {
         allocator_type& __a = this->__alloc();
-        __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
+        __split_buffer<value_type, allocator_type&> __v(__align_size(__n),
+                                                        size(), __a);
         __swap_out_circular_buffer(__v);
     }
 }
 
 template <class _Tp, class _Allocator>
 void
 vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
 {
     if (capacity() > size())
     {
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             allocator_type& __a = this->__alloc();
-            __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
+            __split_buffer<value_type, allocator_type&> __v(
+                __align_size(size()), size(), __a);
             __swap_out_circular_buffer(__v);
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
         }
 #endif  // _LIBCPP_NO_EXCEPTIONS
     }
 }
 
 template <class _Tp, class _Allocator>
 template <class _Up>
 void
 #ifndef _LIBCPP_CXX03_LANG
 vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
 #else
 vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
 #endif
 {
     allocator_type& __a = this->__alloc();
-    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
+    __split_buffer<value_type, allocator_type&> __v(
+        __align_size(__recommend(size() + 1)), size(), __a);
     // __v.push_back(_VSTD::forward<_Up>(__x));
     __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Up>(__x));
     __v.__end_++;
     __swap_out_circular_buffer(__v);
 }
 
 template <class _Tp, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY

 }
 
 template <class _Tp, class _Allocator>
 template <class... _Args>
 void
 vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
 {
     allocator_type& __a = this->__alloc();
-    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
+    __split_buffer<value_type, allocator_type&> __v(
+        __align_size(__recommend(size() + 1)), size(), __a);
 //    __v.emplace_back(_VSTD::forward<_Args>(__args)...);
     __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Args>(__args)...);
     __v.__end_++;
     __swap_out_circular_buffer(__v);
 }
 
 template <class _Tp, class _Allocator>
 template <class... _Args>
if (this->__end_ < this->__end_cap())
             if (__p <= __xr && __xr < this->__end_)
                 ++__xr;
             *__p = *__xr;
         }
     }
     else
     {
         allocator_type& __a = this->__alloc();
-        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
+        __split_buffer<value_type, allocator_type&> __v(
+            __align_size(__recommend(size() + 1)), __p - this->__begin_, __a);
         __v.push_back(__x);
         __p = __swap_out_circular_buffer(__v, __p);
     }
     return __make_iter(__p);
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
if (this->__end_ < this->__end_cap())
         {
             __move_range(__p, this->__end_, __p + 1);
             *__p = _VSTD::move(__x);
         }
     }
     else
     {
         allocator_type& __a = this->__alloc();
-        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
+        __split_buffer<value_type, allocator_type&> __v(
+            __align_size(__recommend(size() + 1)), __p - this->__begin_, __a);
         __v.push_back(_VSTD::move(__x));
         __p = __swap_out_circular_buffer(__v, __p);
     }
     return __make_iter(__p);
 }
 
 template <class _Tp, class _Allocator>
 template <class... _Args>
if (this->__end_ < this->__end_cap())
             __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
             __move_range(__p, this->__end_, __p + 1);
             *__p = _VSTD::move(__tmp.get());
         }
     }
     else
     {
         allocator_type& __a = this->__alloc();
-        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
+        __split_buffer<value_type, allocator_type&> __v(
+            __align_size(__recommend(size() + 1)), __p - this->__begin_, __a);
         __v.emplace_back(_VSTD::forward<_Args>(__args)...);
         __p = __swap_out_circular_buffer(__v, __p);
     }
     return __make_iter(__p);
 }
 
 #endif  // !_LIBCPP_CXX03_LANG
 
if (__n > 0)
                 if (__p <= __xr && __xr < this->__end_)
                     __xr += __old_n;
                 _VSTD::fill_n(__p, __n, *__xr);
             }
         }
         else
         {
             allocator_type& __a = this->__alloc();
-            __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
+            __split_buffer<value_type, allocator_type&> __v(
+                __align_size(__recommend(size() + __n)), __p - this->__begin_,
+                __a);
             __v.__construct_at_end(__n, __x);
             __p = __swap_out_circular_buffer(__v, __p);
         }
     }
     return __make_iter(__p);
 }
 
 template <class _Tp, class _Allocator>
if (__n > 0)
             {
                 __move_range(__p, __old_last, __p + __old_n);
                 _VSTD::copy(__first, __m, __p);
             }
         }
         else
         {
             allocator_type& __a = this->__alloc();
-            __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
+            __split_buffer<value_type, allocator_type&> __v(
+                __align_size(__recommend(size() + __n)), __p - this->__begin_,
+                __a);
             __v.__construct_at_end(__first, __last);
             __p = __swap_out_circular_buffer(__v, __p);
         }
     }
     return __make_iter(__p);
 }
 
 template <class _Tp, class _Allocator>

libcxx/test/libcxx/containers/sequences/vector/asan_operator_overloads.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// UNSUPPORTED: c++98, c++03
+
+#include <cassert>
+#include <cstdint>
+#include <new>
+#include <vector>
+
+#include "asan_testing.h"
+
+constexpr std::size_t kAlignment = 16;
+alignas(kAlignment) uint8_t sBuffer[10 * 1024];
+std::size_t sBufferOffset;
+
+void* BufferNew(std::size_t size) {
+  // Adjust size to alignment and add space to save the size to
+  size = ((size - 1) | (kAlignment - 1)) + 1;
+  size += kAlignment;
+
+  // "Allocate"
+  uint8_t* ptr = sBuffer + sBufferOffset;
+  assert(ptr <= std::end(sBuffer));
+  sBufferOffset += size;
+
+  // Save the size
+  *reinterpret_cast<std::size_t*>(ptr) = size;
+  ptr += kAlignment;
+
+  return ptr;
+}
+
+void BufferDelete(void* p) noexcept {
+  volatile uint8_t* ptr = reinterpret_cast<volatile uint8_t*>(p);
+
+  // Read off the size
+  ptr -= kAlignment;
+  std::size_t size = *reinterpret_cast<volatile std::size_t*>(ptr);
+
+  // Zero out the contents
+  while (size > 0) {
+    *ptr++ = 0;
+    size--;
+  }
+}
+
+void BufferReset() { sBufferOffset = 0; }
+
+// Rather than overloading operator new/delete (since it's giving me linker
+// errors in the test suite) we'll instead trick libc++ into thinking that
+// the allocator FakeAllocator is the default allocator.
+#if 0
+void* operator new(std::size_t size) { return BufferNew(size); }
+
+void operator delete(void* ptr) noexcept { BufferDelete(ptr); }
+
+template <typename T>
+using FakeAllocator = std::allocator<T>;
+#else
+template <typename T>
+struct FakeAllocator {
+  using value_type = T;
+
+  FakeAllocator() = default;
+  template <typename P>
+  FakeAllocator(const FakeAllocator<P>&) noexcept {}
+
+  T* allocate(std::size_t n) {
+    return static_cast<T*>(BufferNew(n * sizeof(T)));
+  }
+  void deallocate(void* p, std::size_t) noexcept { BufferDelete(p); }
+};
+
+namespace std {
+template <typename T>
+struct is_same<FakeAllocator<T>, allocator<T> >
+    : std::integral_constant<bool, true> {};
+template <typename T>
+struct is_same<allocator<T>, FakeAllocator<T> >
+    : is_same<FakeAllocator<T>, allocator<T> > {};
+} // namespace std
+#endif
+
+template <typename T>
+void test_vector() {
+  using V = std::vector<T, FakeAllocator<T> >;
+  constexpr std::size_t kLoopCount = 32;
+
+  // resize
+  {
+    BufferReset();
+    V v;
+    for (std::size_t i = 0; i < kLoopCount; ++i) {
+      v.resize(i);
+      assert(is_contiguous_container_asan_correct(v));
+      assert(v.size() == i);
+    }
+    // Make sure this isn't optimised away
+    volatile T t = v[0];
+    (void)t;
+  }
+
+  // constructor
+  {
+    BufferReset();
+    for (std::size_t i = 1; i < kLoopCount; ++i) {
+      V v(i);
+      assert(is_contiguous_container_asan_correct(v));
+      assert(v.size() == i);
+      // Make sure this isn't optimised away
+      volatile T t = v[0];
+      (void)t;
+    }
+  }
+
+  // back
+  {
+    BufferReset();
+    V v;
+    for (std::size_t i = 0; i < kLoopCount; ++i) {
+      v.emplace_back();
+      assert(is_contiguous_container_asan_correct(v));
+      assert(v.size() == i + 1);
+    }
+    // Make sure this isn't optimised away
+    volatile T t = v[0];
+    (void)t;
+  }
+
+  // front
+  {
+    BufferReset();
+    V v;
+    for (std::size_t i = 0; i < kLoopCount; ++i) {
+      v.insert(v.begin(), T{});
+      assert(is_contiguous_container_asan_correct(v));
+      assert(v.size() == i + 1);
+    }
+    // Make sure this isn't optimised away
+    volatile T t = v[0];
+    (void)t;
+  }
+
+  // middle
+  {
+    BufferReset();
+    V v;
+    for (std::size_t i = 0; i < kLoopCount; ++i) {
+      v.insert(std::next(v.begin(), i / 2), T{});
+      assert(is_contiguous_container_asan_correct(v));
+      assert(v.size() == i + 1);
+    }
+    // Make sure this isn't optimised away
+    volatile T t = v[0];
+    (void)t;
+  }
+}
+
+template <std::size_t N>
+struct SizedElement {
+  uint8_t data[N];
+};
+
+template <std::size_t ElementSize>
+void test_sized_element() {
+  using T = SizedElement<ElementSize>;
+  test_vector<T>();
+}
+
+int main(int, char**) {
+  test_sized_element<1>();
+  test_sized_element<2>();
+  test_sized_element<3>();
+  test_sized_element<4>();
+  test_sized_element<5>();
+  test_sized_element<6>();
+  test_sized_element<7>();
+  test_sized_element<8>();
+
+  test_sized_element<9>();
+  test_sized_element<10>();
+  test_sized_element<11>();
+  test_sized_element<12>();
+  test_sized_element<13>();
+  test_sized_element<14>();
+  test_sized_element<15>();
+  test_sized_element<16>();
+
+  //test_vector<bool>();
+
+  test_vector<char>();
+  test_vector<short>();
+  test_vector<int>();
+  test_vector<long>();
+  test_vector<long long>();
+
+  test_vector<unsigned char>();
+  test_vector<unsigned short>();
+  test_vector<unsigned int>();
+  test_vector<unsigned long>();
+  test_vector<unsigned long long>();
+
+  return 0;
+}

libcxx/test/std/containers/sequences/vector/vector.capacity/shrink_to_fit.pass.cpp

 
 int main(int, char**)
 {
     {
         std::vector<int> v(100);
         v.push_back(1);
         assert(is_contiguous_container_asan_correct(v));
         v.shrink_to_fit();
+#ifndef _LIBCPP_HAS_NO_ASAN
+        assert(v.capacity() == 102);
+#else
         assert(v.capacity() == 101);
+#endif
         assert(v.size() == 101);
         assert(is_contiguous_container_asan_correct(v));
     }
+    // When ASAN is enabled the capacity grows to 102 rather than 101 after
+    // the call to push_back(). This leaves us with not enough space in the
+    // allocator to shrink it correctly so it throws internally, so disable
+    // this test when ASAN is enabled with no exceptions.
+#if defined(_LIBCPP_HAS_NO_ASAN) || !defined(_LIBCPP_NO_EXCEPTIONS)
     {
         std::vector<int, limited_allocator<int, 401> > v(100);
         v.push_back(1);
         assert(is_contiguous_container_asan_correct(v));
         v.shrink_to_fit();
+#ifndef _LIBCPP_HAS_NO_ASAN
+        // As above, shrink_to_fit() will throw internally, leaving us with
+        // a capacity of 200 from libc++'s 2x growth factor
+        assert(v.capacity() == 200);
+#else
         assert(v.capacity() == 101);
+#endif
         assert(v.size() == 101);
         assert(is_contiguous_container_asan_correct(v));
     }
+#endif
 #ifndef _LIBCPP_NO_EXCEPTIONS
     {
         std::vector<int, limited_allocator<int, 400> > v(100);
         v.push_back(1);
         assert(is_contiguous_container_asan_correct(v));
         v.shrink_to_fit();
         LIBCPP_ASSERT(v.capacity() == 200); // assumes libc++'s 2x growth factor
         assert(v.size() == 101);
         assert(is_contiguous_container_asan_correct(v));
     }
 #endif
 #if TEST_STD_VER >= 11
     {
         std::vector<int, min_allocator<int>> v(100);
         v.push_back(1);
         assert(is_contiguous_container_asan_correct(v));
         v.shrink_to_fit();
+#ifndef _LIBCPP_HAS_NO_ASAN
+        assert(v.capacity() == 102);
+#else
         assert(v.capacity() == 101);
+#endif
         assert(v.size() == 101);
         assert(is_contiguous_container_asan_correct(v));
     }
 #endif
 
   return 0;
 }