[ASan][libc++] Annotating std::deque with all allocators

[AdvenamTacet]

Summary

This patch is part of our efforts to support container annotations with (almost) every allocator.
Annotating std::deque with default allocator is implemented in D132092.

Support in ASan API exests since rG1c5ad6d2c01294a0decde43a88e9c27d7437d157.

The motivation for a research and those changes was a bug, found by Trail of Bits, in a real code where an out-of-bounds read could happen as two strings were compared via a std::equals function that took iter1_begin, iter1_end, iter2_begin iterators (with a custom comparison function).
When object iter1 was longer than iter2, read out-of-bounds on iter2 could happen. Container sanitization would detect it.

If you have any questions, please email:

• [e-mail]
• [e-mail]

[AdvenamTacet]

I will add tests.

[AdvenamTacet]

This update resolves merge conflicts with new head.

[AdvenamTacet]

This update applies changes to the newest version of D132092.
It also adds tests similar to those in D136765.

I have a problem with local tests.

[AdvenamTacet]

This updates the base commit.

[AdvenamTacet]

Rebase.

[AdvenamTacet]

rebase

[AdvenamTacet]

rebase

[philnik]

libcxx/include/deque

980

This needs tests to make sure that custom allocators work and that customizing __asan_annotate_container_with_allocator can be customized to disable annotations.

[AdvenamTacet]

This update adds tests for the patch.

• Test for different allocators.
• Test confirming that turning off annotations work.

[AdvenamTacet]

rebase

[ldionne]

LGTM after comments are applied.

libcxx/test/libcxx/containers/sequences/deque/asan_turning_off.pass.cpp

20

Please use <cassert> instead.

<stdlib.h> shouldn't be necessary after my comments below.

29

Let's do new char[8 * 1024] instead (some platforms don't expose std::malloc).

33

And delete[] here.

[AdvenamTacet]

Rebase and suggested changes.

Thank you @ldionne for the review!

This update:

• assert.h -> cassert,
• removes stdlib.h,
• new char[...] instead of malloc,
• does rebase,
• delete[] instead of free.

@philnik is there anything more you want to see in the patch?

[ldionne]

You can try rebasing and re-uploading the patch to see if the issues persist. I think this was a fluke fixed by 1cad87c07aab0e3052ad61953fc30d5155fba336.

[AdvenamTacet]

Rebase

I also don't think the issue is related to the patch.

[ldionne]

IDK why but the build was cancelled, can you ping the CI again? Sorry this is kinda complicated

[AdvenamTacet]

CI rerun and rebase.

@ldionne, no worries, I know it and I will make it work.

libcxx/include/deque

template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
           class _DiffType, _DiffType _BlockSize>
 const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer,
                                  _DiffType, _BlockSize>::__block_size =
     __deque_block_size<_ValueType, _DiffType>::value;
 
 template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
 class _LIBCPP_TEMPLATE_VIS deque
 {
-private:
-  using __default_allocator_type = allocator<_Tp>;
-
 public:
     // types:
 
   using value_type = _Tp;
 
   static_assert((is_same<typename _Allocator::value_type, value_type>::value),
                 "Allocator::value_type must be same type as value_type");
 
#if !defined(_LIBCPP_HAS_NO_ASAN) && _LIBCPP_CLANG_VER >= 1600
     // TODO LLVM18: Remove the special-casing
     _LIBCPP_HIDE_FROM_ABI void __annotate_double_ended_contiguous_container(
         const void* __beg,
         const void* __end,
         const void* __old_con_beg,
         const void* __old_con_end,
         const void* __new_con_beg,
         const void* __new_con_end) const {
-        if (__beg && is_same<allocator_type, __default_allocator_type>::value)
+        if (__beg != nullptr && __asan_annotate_container_with_allocator<_Allocator>::value)
             __sanitizer_annotate_double_ended_contiguous_container(
                 __beg, __end, __old_con_beg, __old_con_end, __new_con_beg, __new_con_end);
     }
 #else
     _LIBCPP_HIDE_FROM_ABI void __annotate_double_ended_contiguous_container(
         const void*, const void*, const void*, const void*, const void*, const void*) const _NOEXCEPT {}
 #endif // !defined(_LIBCPP_HAS_NO_ASAN) && _LIBCPP_CLANG_VER >= 1600
 

libcxx/test/libcxx/containers/sequences/deque/asan.pass.cpp

 void do_exit() {
   exit(0);
 }
 
 int main(int, char**)
 {
     {
         typedef cpp17_input_iterator<int*> MyInputIter;
-        // Sould not trigger ASan.
+        // Should not trigger ASan.
         std::deque<int> v;
         int i[] = {42};
         v.insert(v.begin(), MyInputIter(i), MyInputIter(i + 1));
         assert(v[0] == 42);
         assert(is_double_ended_contiguous_container_asan_correct(v));
     }
+    {
+        typedef int T;
+        typedef std::deque<T, min_allocator<T> > C;
+        const T t[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+        C c(std::begin(t), std::end(t));
+        assert(is_double_ended_contiguous_container_asan_correct(c));
+    }
+    {
+        typedef char T;
+        typedef std::deque<T, safe_allocator<T> > C;
+        const T t[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
+        C c(std::begin(t), std::end(t));
+        c.pop_front();
+        assert(is_double_ended_contiguous_container_asan_correct(c));
+    }
     __sanitizer_set_death_callback(do_exit);
     {
         typedef int T;
         typedef std::deque<T> C;
         const T t[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
         C c(std::begin(t), std::end(t));
         assert(is_double_ended_contiguous_container_asan_correct(c));
         T* ptr = &c[0];
         for(size_t i = 0; i < (8 + sizeof(T) - 1)/sizeof(T); ++i)
           c.pop_front();
         *ptr = 1;
         volatile T foo = c[c.size()]; // should trigger ASAN. Use volatile to prevent being optimized away.
         assert(false);          // if we got here, ASAN didn't trigger
         ((void)foo);
     }
 }

libcxx/test/libcxx/containers/sequences/deque/asan_turning_off.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++03
+
+// <deque>
+
+// Test based on: https://bugs.chromium.org/p/chromium/issues/detail?id=1419798#c5
+// Some allocators during deallocation may not call destructors and just reuse memory.
+// In those situations, one may want to deactivate annotations for a specific allocator.
+// It's possible with __asan_annotate_container_with_allocator template class.
+// This test confirms that those allocators work after turning off annotations.
+
+#include <assert.h>
+#include <stdlib.h>
+#include <deque>
+#include <new>
+
+struct reuse_allocator {
+  static size_t const N = 100;
+  reuse_allocator() {
+    for (size_t i = 0; i < N; ++i)
+      __buffers[i] = malloc(8*1024);
+  }
+  ~reuse_allocator() {
+    for (size_t i = 0; i < N; ++i)
+      free(__buffers[i]);
+  }
+  void* alloc() {
+    assert(__next_id < N);
+    return __buffers[__next_id++];
+  }
+  void reset() { __next_id = 0; }
+  void* __buffers[N];
+  size_t __next_id = 0;
+} reuse_buffers;
+
+template <typename T>
+struct user_allocator {
+  using value_type = T;
+  user_allocator() = default;
+  template <class U>
+  user_allocator(user_allocator<U>) {}
+  friend bool operator==(user_allocator, user_allocator) {return true;}
+  friend bool operator!=(user_allocator x, user_allocator y) {return !(x == y);}
+
+  T* allocate(size_t) { return (T*)reuse_buffers.alloc(); }
+  void deallocate(T*, size_t) noexcept {}
+};
+
+#ifdef _LIBCPP_HAS_ASAN_CONTAINER_ANNOTATIONS_FOR_ALL_ALLOCATORS
+template <class T>
+struct std::__asan_annotate_container_with_allocator<user_allocator<T>> : false_type {};
+#endif
+
+int main(int, char**) {
+  using D = std::deque<int, user_allocator<int>>;
+
+  {
+    D* d = new (reuse_buffers.alloc()) D();
+    for (int i = 0; i < 100; i++)
+      d->push_back(i);
+  }
+  reuse_buffers.reset();
+  {
+    D d;
+    for (int i = 0; i < 1000; i++)
+      d.push_back(i);
+  }
+
+  return 0;
+}